Operations research

Special cases of linear programming (Graphical Method)

To start, it is important to remember that in a linear programming model, the goal is to find the optimal solution that maximizes or minimizes an objective function, subject to a set of constraints. In the graphical method, the objective function and the constraints are represented graphically on a Cartesian plane, forming a feasible region that contains all possible solutions. However, in some cases, the optimal solution is not always found at one of the vertices of the feasible region. These are known as special cases of linear programming.

Let us remember that the solution area contains all possible solutions that satisfy the set of constraints, which is called feasibility. Optimality is different, as within the feasible solutions, one or some of them will minimize or maximize the objective function. This is essential, both in teaching linear programming and in learning.

Special cases

Multiple optimal solutions

Sometimes, there may be multiple solutions that maximize or minimize the objective function of a linear programming model, that is, multiple optimal solutions. The choice of solution in a practical application context will depend on both the sensitivity of active constraints and the system-specific factors that are not considered in a mathematical model.

In the case where the solution vectors are consecutive, this number of optimal solutions may tend to infinity.

For example, let’s consider the following linear programming model:

Lopez S.A.S.” carpentry has received a large number of prefabricated parts for the manufacture of tables, but has not been able to start a production plan focused on them due to the high demand for their other products. The tables that can be made with the prefabricated parts are of two models: A and B. These tables only need to be assembled and painted.

This week it has been determined to dedicate 10 hours to assemble and 8 hours to paint to make the most tables possible, taking into account that each table model A requires 2 hours of assembly and 1 hour of painting, while each table model B requires 1 hour of assembly and 2 hours of painting. If the margin of profit is $20000 for each table model A and $10000 for each table model B, determine the appropriate production model for this week.

Variables

x = number of model A tables to be manufactured this week

y = number of model B tables to be manufactured this week

Constraints

2x + y <= 10        “Assembly hours”

x + 2y <= 8          “Painting hours”

x >= 0                  “Non-negativity”

y >= 0                  “Non-negativity”

Objective function

Zmax = 20000x + 10000y

Graphical solution:

As we can see, the feasible region has two vertices that maximize the Z function: C(4,2) and D(6,0). Both solutions are optimal, since they maximize the Z function within the constraints of the model. In this case, the choice of solution will depend on system-specific factors that are not considered in the mathematical model, such as resource availability or production cost; similarly, it would be convenient to evaluate the sensitivity of the active constraints at each vertex.

Optimal solutions 20000(x) 10000(y) Z
Vertex C 20000(4) 10000(2) 100000
Vertex D 20000(5) 10000(0) 100000

In this case, a particular condition arises, since the vertices are consecutive. This implies that every point on the segment connecting C and D are optimal solutions.

With the help of GeoGebra, you can move the scroll bar representing the utility and evaluate that the objective function reaches a maximum of 100000 at both C and D, as well as any point on segment CD. This demonstrates that in this case there are multiple optimal solutions and that any point on segment CD is a valid solution.


Unbounded optimal solution

Another variant of linear programming models is the unbounded optimal solution, that is, problems with infinite optimal solutions. Given the finite nature of constraints in real-world contexts, these problems often result from a poor formulation of constraints, but in the academic world it is common to evaluate this type of problem.

For example, let’s suppose we have the following linear programming model:

The energy drink company “WILD” is promoting two new drinks: type A and type B. Since they are on promotion, it can ensure the coverage of any demand. However, the company must take into account two policies:

The amount of type A drinks sold cannot be less than that of type B.

At least 1500 drinks of any type must be sold.

These policies can be represented by constraints in a linear programming model, which will allow us to determine the optimal amount of type A and B drinks to sell on promotion.

The selling price of both drinks is $1800 per unit.

Before moving on to the mathematical model, it is important to critically evaluate the problem at hand. The first assumption considers the ability to meet any demand, that is, an infinite demand. In reality, this would imply the existence of infinite production resources, which is a highly unrealistic assumption. In fact, it is an appeal to the absurd that is used to define the management of constraints in linear programming.

It is important to take these assumptions into account and adjust the mathematical model accordingly, in order to obtain realistic and viable solutions in a practical application context.

Variables

x = type A drinks to sell on promotion

y = type B drinks to sell on promotion

Constraints

x >= y “Sales policies”

x + y >= 1500 “Painting hours”

x >= 0 “Non-negativity”

y >= 0 “Non-negativity”

Objective function

Zmax = 1800x + 1800y

Graphical solution:

As you can see, the feasible region is unbounded, which means that the set of possible feasible solutions is infinite. Consequently, the optimal solution tends to infinity, making the model unsolvable.

In this case, the problem posed has a poor formulation of the constraints, which has led to an unbounded solution. To solve this problem, it is necessary to adjust the constraints of the model so that the feasible region is bounded and has a finite optimal solution.

In my teaching experience, this is one of the most frequent cases that arise in modeling by students. It is important that students develop skills to understand whether the constraints present sufficiently bound the model or not. This is essential for obtaining realistic and viable solutions in a practical application context.

Unbounded optimal solution

The infeasible solution is a common case in linear programming, and corresponds to those cases in which there are no solutions that meet all the constraints of the model. The constraints bound the system and set limits to achieve the model’s objective. When these constraints cannot be fully met, the solution is infeasible.

In a practical application context, this case is more common than it seems, and occurs in scenarios in which unfeasible supply and demand proportions are posed in the model.

In my experience, burnout syndrome is one of the main consequences of poor resource management in a work plan (a typical scenario of unbounded solutions in a real context). When a worker is in charge of meeting a plan that does not have the necessary resources, they are forced to make excessive effort to achieve the established goals, which can lead to job burnout and a decrease in their performance and quality of life.

For example, let’s suppose we have the following linear programming model:

The cookie company “CAROLA” wants to plan the production of cookies that it must deliver to its customer in two weeks. According to the contract, the company commits to delivering at least 300 boxes of cookies, regardless of their type (presentation D, presentation N, or a combination of both).

The production of each box of presentation D cookies requires 2 hours of preparation and 3 hours of baking, while the production of each box of presentation N requires 3 hours of preparation and 1 hour of baking. The company has 550 hours of preparation and 480 hours of baking in the next two weeks.

The margin of profit for each box of presentation D cookies is $8500, and the margin of profit for each box of presentation N is $8100. To maximize profits, the company must use a linear programming model that allows it to determine the appropriate production plan.

Variables

x = Number of presentation D cookies to produce in two weeks

y = Number of presentation N cookies to produce in two weeks

Constraints

2x + 3y <= 550       “Hours of preparation”

3x + y <= 480         “Hours of baking”

x + y >= 300           “Demand according to the contract”

x >= 0                     “Non-negativity”

y >= 0                     “Non-negativity”

Objective function

Zmax = 8500x + 8100y

Graphical solution:

The graph shows the shaded area that is delimited from the representation of the constraints that correspond to the production resources. It is possible to see how there is no intersection between the capacity constraints and the demand constraint (shaded blue), indicating that there are no solutions that meet all the constraints of the model. In this case, it is an infeasible solution.


Redundant constraints

There are a type of constraints in linear programming models that have no effect on the determination of the solution set (nor on the optimal solution). These constraints are known as redundant, as they do not affect the solution of the model.

In some cases, redundant constraints can be useful for sensitivity analysis, as they allow us to evaluate how the optimal solution changes with changes in the values of the constraints. Instead of eliminating these constraints, they can be left in the model and marked as inactive. In this way, they do not affect the optimal solution of the model, but they can be used for sensitivity analysis.

It is important to note that, although some authors recommend removing redundant constraints to improve the accuracy of the model, this practice is not always advisable, in fact, I definitely do not recommend this practice.

In real-world application contexts, the professional must manage the constraints of the system, which means that the active constraint can change over time and the actions taken (the constraint of a system moves, the constraints are activated in response to changes in the parameters). Therefore, it is important to consider all the constraints of the model and use them in sensitivity analysis.

For example, let’s suppose we have the following linear programming model:

The company “CONGELADORES MAJO” is in need of planning its weekly production of type A and B freezers. Each of them requires going through three operations: Assembly, painting and quality control. Type A freezers require 2 hours of assembly, 3 kg of paint and 4 hours of quality control; type B freezers require 3 hours of assembly, 6 kg of paint and 5 hours of quality control. The company has a contributory margin of $102,000 and $98,000 for each type A and B freezer, respectively. The weekly availability of resources is limited to 300 hours of assembly, 840 kg of paint and 450 hours of quality control. From this information, the quantity of units to be produced weekly of each reference must be determined in order to maximize profits.

Variables

x = Type A freezers to produce weekly

y = Type B freezers to produce weekly

Constraints

2x + 3y <= 300        “Assembly hours”

3x + 5y <= 840        “Paint kg”

4x + 5y <= 450        “Quality control hours”

x >= 0                      “Non negativity”

y >= 0                      “Non negativity”

Objective function

Zmax = 102000x + 98000y

Graphic solution:

The graph shows how constraints 1 and 2 (assembly hours and paint kg) do not determine the solution set. The solution is at the vertex C(112.5, 0), with a utility of $11475000.

However, calling the constraints that do not determine the feasibility area or the optimal point, as redundant or superfluous (or excluding them from the model), may not be the correct way; it is preferable to call these constraints as inactive. Suppose we are in a scenario where we evaluate the possibility of increasing the capacity of constraint 3 (quality control hours); it is essential to recognize the limits within which such an increase in capacity would activate constraints 1 and 2.


In summary, special cases in linear programming can be given by a poor formulation of the constraints, the presence of infeasible or infinite solutions. It is important to always consider all the constraints of the model and use sensitivity analysis to evaluate their effect on the optimal solution.

If you liked this article on special cases in linear programming, share it with your contacts!

Bryan Salazar López

By profession, Industrial Engineer, Master in Logistics, specialized in productivity, with interest and experience in modeling processes under sustainability indicators. Founder of Ingenieriaindustrialonline.com, site where research contributions, articles and references are collected.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Back to top button