LINEAR PROGRAMMING METHOD

SIMPLEX

RESEARCH

JEVA / PTI
1
LINEAR PROGRAMMING METHOD
SIMPLEX

LINEAR PROGRAMMING: PROBLEM SOLVING WITH THE SIMPLEX METHOD

The Simplex Method solves Linear Programming problems of any size, from two to 'n'
decision variables. The problems can be maximization or minimization depending on the type of
Objective Function they have and regarding the type of optimal solution they provide, they can be a unique solution of
multiple or alternative solution.

The computer is a technological medium that provides great support in solving problems in Programming.
Linear, using its great data processing speed. The computer can use any type of
software designed for this purpose, but they will all use the mathematical algorithm of the Method
Simplex. Some software packages that can be used to solve these problems are, the
WinQSB, Storm, Lindo, etc. An electronic spreadsheet can also be programmed for this purpose, using the Solver of
Excel.

An essential requirement to use the computer with this orientation is to have the problem previously.
model to facilitate the capture of input data, which must be in accordance with the software format
used and proceed with its execution. The solution provided by the computer in its output report must be
interpret to support decision-making.

The focus of this topic is to understand the fundamentals of the Simplex Method as support for interpretation.
optimal solution, which is the mathematical solution provided by the computer. To achieve this, the
methodology that follows the Simplex Method in the manual solution of Linear Programming problems whether they are
of maximization or minimization:

1. Equalize the restrictions of the modeled problem.

2. Create the 'Initial Table'.
3. Recognize if the solution given by the Table is optimal, checking the compliance with the 'Criterion of
Optimability (Cj-ZjIf the solution is not optimal, it should:
4. Calculate the "New Table" until finding the optimal solution.
5. Repeat "Step 3 and 4" until the calculated table meets the optimality criterion.
6. Give the 'Optimal Solution' to the problem.
7. Interpret the optimal solution to the problem.

To present the application of this methodology, it will be done with three problems: one of maximization, another of
minimization and the last of optimal alternate or multiple solution.

1. MAXIMIZATION PROBLEM.

This general methodology will be explained with a maximization problem, involving two decision variables, which is
a small problem just to illustrate the Simplex Method.

In order to compare the Graphic Method and the Simplex, the problem of 'manufacturing of
"fertilizers" that was previously solved with the Graphical Method and will now be done with the Simplex.
First, the solution to the problem is presented and then the comparison between both methods will be made.

1.1. Solution of the problem by the Simplex Method.

Below is the model of the fertilizer problem (problem presented in the Method notes)
Graph) to be solved with the Simplex Method:

Max. Z = 185X1+ 200X2

s. a. Nitrate 0.05X1+ 0.05X2≤1,100
Phosphate 0.05X1+ 0.10X2≤1,800
Potassium 0.10X1+ 0.05X2<=2,000

JEVA / PTI
2
LINEAR PROGRAMMING METHOD
SIMPLEX

Step 1. Equalize the constraints.

The constraints are equalized to have the identity matrix of the problem. This identity matrix is the point.
of departure that uses the Simplex Method to solve the problem.

The following rules exist for making the equalization of the restrictions:

If there is a less than or equal restriction, a slack variable (H) will be added. If the restriction
if greater than or equal to, an excess variable (E) will be subtracted and an artificial variable (A) will be added.
the constraint is an equality, an artificial variable (A) will be added.

A small example to demonstrate the application of these rules is equalizing the following
restrictions:

Restrictions Equalizing the restrictions

2X1+ 4X2≤80 2X1+ 4X2+ H1+ 0 + 0 = 80

8X1+ 6X2≥12 8X1+ 6X2+ 0 - E2+ A1= 12
X1+ 3X2= 15 X1+ 3X2+ 0 + 0 + A2= 15
identity matrix

Now, applying these rules to match the constraints of the fertilizer problem, we have:

Nitrate 0.05X1+ 0.05X2≤1,100 0.05X1+ 0.05X2+ H1= 1,100

Phosphate 0.05X1+ 0.10X2≤1,800 0.05X1+ 0.10X2+ H21,800
Potassium 0.10X1+ 0.05X2≤2,000 0.10X1+ 0.05X2+ H32,000

Step 2. Form the Initial Table.

There are different table formats that can be used for the Simplex Method. The formats are
they only differ in the placement of the data but the essence is the same.

Once the format of the table is defined, it will remain the same throughout the development of the problem.
regardless of the stage that is being done. We will use the following format to
make the tables:

Initial Table or Table 1.

Objective Function:
Base Cj X1 X2 H1 H2 H3 BI Variables
185 200 0 0 0 Contribution Coefficients
H1 0 0.05 0.05 1 0 0 1100 Restrictions:
H2 0 0.05 0.10 0 1 0 1800 Coefficients and Terms
H3 0 0.10 0.05 0 0 1 2000 Independents

Unit Loss of the Objective Function

Zj 0 0 0 0 0 0
(Shadow Price)
∆j 185 200 0 0 0
Marginal Increase of the value of the
Objective Function

To calculate Zj y∆jthey will be made with the following relationships:

Zj= Σ Ai,jCj
∆j= Cj - Zj

JEVA / PTI
3
LINEAR PROGRAMMING METHOD
SIMPLEX

Step 3. Recognize if the solution provided by the table is optimal. Verify compliance with the Criterion of
Optimability (∆j≤0)

The Simplex Method uses the Optimality Criterion to determine if it has reached the optimal solution.
problem. If the table you have does not meet this criterion, you will have to proceed with others.
iterations, that is, calculating more tables until meeting it. The optimality criterion is stated in the
following form:
The solution will be optimal if and only if ∆j≤0. That is, the values of the row of the∆jthey must be
zeroes or negatives. A positive value indicates that the solution of the table is not optimal.

As the Simplex Method works through iterations (moving from one table to another until reaching the solution
Optimal), it is possible to read the solution available in any of the calculated tables.

To read the solution of a table that has been calculated, it is necessary to look at two columns, the column
Basenos will give us the Basic Variables that form the solution and the column 'Bi' will give us the value of these
variables. Any variable not included in the database is a Non-Basic Variable with a value of zero.

Upon reading the solution of the previous table, it is understood that:

Basic Variables Non-basic Variables

Table Solution
H1equals 1100 X 1= 0
H21800 X 2= 0
H3= 2000
Z = 0

This solution is not optimal as if you observe the rowjit has positive values that do not comply
with the criterion of optimality. Therefore, a new table must be created to find the
next feasible solution and see if it is optimal.

Step 4. Calculate the "New Table".

To calculate the new table, the 'Input Variable (IV)' and the 'Output Variable (OV)' must be defined.
"The 'Pivot' and the 'Adjustment Criteria' for the new lines."

The 'Criterion for defining the Input Variable' is to select the variable with the maximum value in the row.
∆jIn this case, the input variable is X.2which has a value of 200, which is the highest value. This
it means that for every ton produced of the fertilizer 5-10-5 (X 2You will earn $200 per ton
but if the 5-5-10 (X had been selected as an input variable 1It would only earn $185. The variable
X2will enter the 'Base' of the new table.

Bi
The 'Criterion for defining the Output Variable' is to select the minimum positive value of the quotient. .
AI h a v e
First, the quotient must be calculated and then the output variable must be selected. In this problem the
the output variable is H2.

The 'Pivot' is the intersection of the Input Variable column with the row of the Variable of
Exit and this pivot must be 'marked' as it will be used to make the adjustment criteria.

The 'Adjustment Criteria' consist of making the required equations to calculate the rows of the
new table without using matrix calculation; obviously these calculations can also be done with
matrices.

JEVA / PTI
4
LINEAR PROGRAMMING METHOD
SIMPLEX

It is recommended to make calculations by 'rows' to avoid errors rather than doing them cell by cell.
In general, the 'adjustment criteria' for calculating the rows of the new table can be defined
in the following way:

Vp
Pivot Line Np =
p
NpPivot row for the new table
VpRow of the old table where the pivot is marked
pValue of the pivot marked in the old table

N iViA NpI've
NiLine 'i' calculated for the new table
VISelected row 'i' from the old table
AI'veCoefficients of the input variable column in row 'i' (table
old)
NpPivot row for the new table
The following are the calculations for the problem being developed:

Table 1

Base Cj X1 X2 H1 H2 H3 Bi Bi
185 200 0 0 0
AI h a v e
V1 H1 0 0.05 0.05 1 0 0 1100 22,000
V2 H2 0 0.05 0.10 0 1 0 1800 18,000 →VS = H2
V3 H3 0 0.10 0.05 0 0 1 2000 40,000
Zj 0 0 0 0 0 0
∆j 185 200 0 0 0

VE = X2

The adjustment criteria for calculating the rows of the new table are:

V2
Pivot Line N2 =
0.10
N1 =V1 − 0.05N2
N 3V30.05N2

The calculations of the rows for the new table are presented:

One should always start by calculating the 'pivot row' for the new table, which in this case is N.2:

Line N2:
V2 0.05 0.10 0 1 0 1,800
V 0.5 1 0 10 0 18,000
N2 = 2
0.10
This 'pivot line' of the new table is very important as it will be used as a reference for
calculate the other rows of the table, as shown below:

JEVA / PTI
5
LINEAR PROGRAMMING METHOD
SIMPLEX

Line N1:
V2 0.05 0.05 1 0 0 1,100
0.05 N2 - 0.025 0.05 0 0.5 0 900
N1 0.025 0 1 0.5 0 200

Line N3:
V3 0.10 0.05 0 0 1 2,000
0.05N2 - 0.025 - 0.05 0 0.5 0 900
N3 0.075 0 0 0.5 1 1,100

Arranging the calculated rows in the new table results in the following form:

Table 2

Base Cj X1 X2 H1 H2 H3 Bi BI
185 200 0 0 0
AI ' v e
N1 H1 0 0.025 0 1 - 0.5 0 200 8,000→VS = H1
N2 X2 200 0.5 1 0 10 0 18,000 36,000
N3 H3 0 0.075 0 0 0.5 1 1,100 14,666.7
Zj 100 200 0 2,000 0 3,600,000
∆j 85 0 0 2,000 0

VE = X1

Step 5. Repeat 'Step 3 and 4' until the calculated table meets the optimality criterion.

If the optimality criterion is met, then the solution of that table is optimal; if not, it
continue 'iterating' that is, making new tables until finding the optimal solution to the problem by
what repeats again is step 4.

The solution of the above table is: H1= 200

X218,000
H3= 1,100
Max. Z = 3,600,000

This solution is not optimal, then the following 'new table' is calculated by defining the Input Variable,
the Output Variable, Pivot, and Adjustment Criteria.

To calculate Table 3, the Input Variable is X.1, the Output Variable is H1the Pivot is
0.025 and the Adjustment Criteria are:

V1
Pivot Line N1 =
0.025
N 2 = V 2 − 0.5N1
N 3 =V3 −0.075N1
Table 3
Base Cj X1 X2 H1 H2 H3 BI
185 200 0 0 0
X1 185 1 0 40 20 0 8,000
X2 200 0 1 20 20 0 14,000
H3 0 0 0 3 1 1 500

JEVA / PTI
6
LINEAR PROGRAMMING METHOD
SIMPLEX

Zj 185 200 3,400 300 0 4,280,000

∆j 0 0 - 3,400 - 300 0

This table meets the optimality criterion ∆.j≤0 so a solution has been reached
optimal of the problem.

Step 6. Provide the 'Optimal Solution' to the problem.

The optimal solution to the problem found in Table 3 is:

X1= 8,000
X214,000
H3= 500
Max. Z = 4,280,000

This optimal solution is a 'mathematical solution' that needs to be interpreted.

Step 7. "Interpret" the optimal solution of the problem.

In the interpretation of the optimal solution, it is necessary to see if the problem has 'discrete variables' or
"continuous variables". If there are discrete variables, when interpreting the optimal solution of the
problem, it will have to be given in "integer" values making the required adjustments in the solution
mathematics obtained. If they are continuous variables, the interpretation will be made directly with the values
obtained without making any adjustments.

In our problem, there are continuous variables, so it is not necessary to make adjustments. So, the
the interpretation of the optimal solution will be as follows:

The production plan for next month will be 8,000 tons of fertilizer 5-5-10 (X 1=8,000) and
14,000 tons of 5-10-5 (X 2=14,000) to have the maximum profit of $4,280,000 (Max.Z=4,280,000).
After implementing this production program, there will be 500 surplus tons of Potassium.
Dominant restrictions or "bottlenecks" are Nitrate and Phosphate.

1.2. Comparison between the Simplex Method and the Graphical Method.
Addressing the issue of "fertilizers", which has just been solved by the Simplex Method, a will be made
Comparative analysis between the Simplex Method and the Graphic Method.

The Simplex Method is 'iterative,' meaning it repeats the calculation of the tables, moving from one to another, until
find the optimal solution while the Graphic Method evaluates the Objective Function at each vertex of the
feasible region to choose the optimal solution. The big difference between the two methods is that the
The solution provided by the Graphical Method can be visualized graphically, while that of the Simplex cannot.

To analyze the logic of the calculations of the Simplex Method and compare them with the Graphical Method, the following is presented
next graphic:

JEVA / PTI
7
LINEAR PROGRAMMING METHOD
SIMPLEX

H1= 200 X1= 0

X2= 18,000 H2= X1= 8,000 H1=
0 0
H31,100 X214,000 H2=
Z = 3’600,000 0
VERTEX H3= 500
A Max. Z =
4,280,000
VERTEX 'B'

H11,100 X1= 0
H21,800 X2= 0
H3= 2,000
VERTEX 'E'

The Simplex Method when calculating the 'Initial Table (Table 1)' with the identity matrix of the problem, positions itself in the
Vertex "E" located at the origin point (0,0). In this way, the Simplex is ready to start the solution.
from the problem. In this initial table, the following solution is given:

Basic Variables Non-Basic Variables

H1= 1100 X 1= 0
H2equals 1800 X 2= 0
H3= 2000
Z=0

This solution of the "Initial Table" is the same as the solution found at vertex "E" in the Graphical Method.
Being at the vertex 'E', the Simplex Method evaluates the movement alternatives it has, in this case two,
one direction leads you to vertex 'A' and the other to 'D'. The line of the 'Marginal Increase of the value of the Function
Objective (∆jin the Initial Table, indicates that the profit per ton that can be obtained by producing X2is from
$200/ton while with the X1It is $185. The best alternative is to produce X.2it is for this reason that
chose as "Input Variable" (IV = X2to the Base of the "New Table" (Table 2). This is equivalent to moving
in the direction of the X axis2as can be seen in the graph.

Once the address is selected, the Simplex needs to know how far it can move, this is achieved by defining
the 'Output Variable' of the Initial Table Base which is H2(VS = H2that is linked to the restriction of
Phosphate. This restriction sets the maximum limit to which one can reach according to the graph, that is, up to
the vertex "A".

The solution at vertex 'A' (see the solution in Table 2 of the Simplex Method) is:

Basic Variables Non-Basic Variables

H1= 200 X 1= 0
X2= 18,000 H2= 0
H3= 1,100
Z = 3,600,000

At vertex "A", the previously explained steps are repeated; according to the graph, the evaluations are made.
movement directions (move to vertex 'B' or to vertex 'E') and how far it can go at maximum in the
direction selected in such a way that the value of the Objective Function increases. According to the graph,
it is selected to move to vertex 'B' (Nitrate constraint). When analyzing what the Simplex does to move to
Vertex "B" is to select the direction of movement through the input variable of Table 2 which is X.1

JEVA / PTI
8
LINEAR PROGRAMMING METHOD
SIMPLEX

(VE = X1At vertex 'B' is the optimal solution of the problem that can be seen in Table 3 of the Method.
Simplex, that is, this table meets the optimality criterion.

The optimal solution is:

Basic Variables Non-Basic Variables

X1= 8,000 H1= 0

X214,000 H2= 0
H3= 500
Max.Z = 4,280,000

If you wanted to move to another vertex, for example to 'C', as can be seen in the graph, this would give a value of the
Objective function is lower than the one at vertex 'B', therefore it is reaffirmed that this vertex is the solution.
optimal. The solution found at vertex 'C' is:

Basic Variables Non-Basic Variables

X1= 18,000 H1= 0

X24,000 H3= 0
H2= 500
Z = 4,130,000

2. 'MINIMIZATION' PROBLEM.
When one wants to solve a Linear Programming problem, it is necessary to develop a
three-step cycle: model the problem, solve the model to find the optimal solution, and interpret the
optimal solution found. Below is a "minimization" problem that presents the three
mentioned steps:

Foods for bodybuilders.

A company that manufactures food for bodybuilders has received an order for 1000 kilograms of
a high protein content product. The company knows that the formulation of this order is made
with three staple foods. Currently, there is a stock availability of 800 kilograms of the
food 'A', 100 of 'B' and 400 of 'C'. The final product requires at least 600.
kilograms of food 'A' and no more than 500 of foods 'B' and 'C' combined. The cost of the
The kilogram is $15 for 'A', $12 for 'B', and $10 for 'C'. The company wants to develop a
model to minimize the cost of this order.

Modeling.
Decision Variables.
XiKilograms of Food 'i' that will be used in the fabrication of the order
(Kg)

Objective Function.
min. Z = 15X1+ 12X2+ 10X3
$ ($/Kg)(Kg) = $

Restrictions.
1. Balancing Condition.
X1+ X2+ X31000
Kg Kg

JEVA / PTI
9
LINEAR PROGRAMMING METHOD
SIMPLEX

2. Order Specifications.
Food "A" X1>=600
Food "B" X2+ X3<=500
Kg Kg

3. Availability of Materials.
Food 'A' X1≤800
Food "B" X2<=100
Food "C" X3≤400
Kg Kg

4. No negativity Xi≥0

Dimensional Analysis: Approved.

Solution by the Simplex Method.

To solve a 'minimization' problem using the Simplex Method, the same methodology can be used.
that was applied to the Maximization problems. To do this, it is necessary to transform the problem of
minimization to maximization applying the following principle:
min.Z = Max.(-Z)

Original Objective Function Transformed Objective Function

min. Z = 15X1+ 12X2+ 10X3 Max. Z = - 15X1- 12X210X3

The problem has been transformed, and it is solved as if it were a maximization problem. The following steps are presented.
for the solution of the problem:

• Equalize the restrictions.

The equalization of the constraints to form the 'identity matrix' of this problem is presented:

Restrictions Equalization of Constraints

Balance Condition X1+ X2+ X3= 1000 X1+ X2+ X3+ A1= 1000
Specification Food 'A' X1≥600 X1- E1+ A2= 600
Specification Food 'B' X2+ X3<=500 X2+ X3+ H2500
Availability Food 'A' X1≤800 X1+ H3= 800
Disponibilidad Alimento "B" X2≤100 X2+ H4 = 100
Food Availability 'C X3≤400 X3+ H5= 400

• Initial Table of the problem.

Considering the transformation of the problem as if it were Maximization, we have the following
"Tabla Inicial":

Initial Table (Table 1)

Base Cj X1 X2 X3 A1 E1 A2 H2 H3 H4 H5 Bi BI
-15 -12 -10 -150 0 -150 0 0 0 0
AI ' v e
A1 -150 1 1 1 1 0 0 0 0 0 0 1,000 1,000
A2 -150 1 0 0 0 -1 1 0 0 0 0 600 600→VS
H2 0 0 1 1 0 0 0 1 0 0 0 500 Infinite
H3 0 1 0 0 0 0 0 0 1 0 0 800 800
H4 0 0 1 0 0 0 0 0 0 1 0 100 Infinite
H5 0 0 0 1 0 0 0 0 0 0 1 400 Infinite
Zj -300 -150 -150 -150 150 -150 0 0 0 0 -240,000
∆j 285 138 140 -1500 0 0 0 0 0

JEVA / PTI
10
LINEAR PROGRAMMING METHOD
SIMPLEX

VE

• Recognize if the solution of the table is optimal.

When analyzing the linejwe find positive numbers, which indicates that the solution we have in
this table is not optimal since the optimality criterion is not met. Therefore, it needs to be calculated
the following iteration or table 2 ('New Table')

• Calcular la "Nueva Tabla".

Based on the Initial Table (Table 1), the 'Adjustment Criteria' are established to move to the next
table, remaining in the following form:

Renglón Pivote N2= V2

N1= V1-N2
N3= V3
N4= V4-N2
N5= V5
N6= V6

With these criteria, the rows of the following table were calculated:

Table 2
Base Cj X1 X2 X3 A1 E1 A2 H2 H3 H4 H5 Bi BI
-15 -12 -10 -150 0 -150 0 0 0 0
AI ' v e
A1 -150 0 1 1 1 1 -1 0 0 0 0 400 400→VS
X1 -15 1 0 0 0 -1 1 0 0 0 0 600 Infinite
H2 0 0 1 1 0 0 0 1 0 0 0 500 500
H3 0 0 0 0 0 1 -1 0 1 0 0 200 Infinite
H4 0 0 1 0 0 0 0 0 0 1 0 100 Infinite
H5 0 0 0 1 0 0 0 0 0 0 1 400 400
Zj -15 -150 -150 -150 -135 135 0 0 0 0 -69,000
∆j 0 138 140 -1500 0 0 0 0

VE

• If the calculated Table does not meet the 'Optimality Criterion', new ones must continue to be made.
Tables" until reaching the optimal solution of the problem.
Table 2 is not the optimal solution for the problem, so it is necessary to continue iterating.
new tables) until reaching the optimal solution of it. Below are the calculations of
the calculated tables:

Adjustment Criteria to move to Table 3:

Pivot Line N1= V1

N2= V2
N3= V3-N1
N4= V4
N5= V5
N6= V6-N1

Table 3
Base Cj X1 X2 X3 A1 E1 A2 H2 H3 H4 H5 Bi
-15 -12 -10 -150 0 -150 0 0 0 0

JEVA / PTI
11
LINEAR PROGRAMMING METHOD
SIMPLEX

X3-10 0 1 1 1 1 -1 0 0 0 0 400
X1-15 1 0 0 0 -1 1 0 0 0 0 600
H2 0 0 0 0 -1 -1 1 1 0 0 0 100
H3 0 0 0 0 0 1 -1 0 1 0 0 200
H4 0 0 1 0 0 0 0 0 0 1 0 100
H5 0 0 -1 0 -1 -1 1 0 0 0 1 0
Zj -15 -10 -10 -10 5 -5 0 0 0 0 -13,000
∆j 0 -2 0 -140 -5 -145 0 0 0 0

In this Table 3, the optimality criterion is fulfilled, that is, all the numbers in the row ∆json
negatives or zeros. Therefore, the solution to this table is optimal.

• Optimal solution of the problem.

The optimal solution that can be read in the table is as follows:

X3= 400
X1= 600
H2= 100
H3= 200 (??)
H4= 100
H5= 0
Max. Z = -13,000 which is equal to min. Z = 13,000

• Interpret the optimal solution.

The problem has continuous variables, so the following interpretation remains:
To manufacture the order that meets the requirements, 600 kilograms of it must be used.
food "A" (X600)
1 and 400 kilograms of food "C" (X=400)
3 to have the minimum cost of
$13,000 (min.Z=13,000). When making this manufacturing plan for the order, the following analysis will be available.
from the resources: in the requirement for the combination of food "B" and "C" there will be a surplus of
100 kilograms (H2=100), that is, 400 kilograms were used instead of 500; there is a surplus of
200 kilograms of food "A" (H3=200) and 100 kilograms of food 'B' (H4=100) that was not used.
The Food “C” (H 5=0) it has ended. The dominant constraint is the specification of Food "A", the
availability of Food 'C' and respect the balance condition.

3. PROBLEM OF 'ALTERNATE OPTIMAL SOLUTION' AND 'OPTIMAL SOLUTIONS'

MULTIPLES.

To find out if a problem has one or more 'alternative optimal solutions', one has to look in the 'Table
Final" (the table with the optimal solution of the problem) the variables that meet the following conditions:

• Non-basic variable
• With a value of zero in the linej
• And at least one positive coefficient in its column

For each variable in the Final Table that meets these conditions, there will be a new solution.
optimal alternate.

To calculate a 'new optimal solution', the variable that meets the conditions will be enforced as the Input Variable.
conditions. The procedure will be followed to calculate the following table ("new table"), where the ...
new optimal solution (alternative optimal solution).

If there are several variables in the Final Table that meet the conditions, then there will be
Multiple Optimal Solutions. Depending on the number of these variables, there will be at least this
number or more different optimal solutions for the problem.

JEVA / PTI
12
LINEAR PROGRAMMING METHOD
SIMPLEX

To calculate these multiple solutions, one of them will first be forced to be the Input Variable in the
Final table and following the procedure to calculate the next table, the first solution will be found.
optimal alternative of the problem. If the different variables are introduced as Input Variables,
Once the conditions are met, the different optimal alternative solutions that the problem has will be calculated.

Below are two problems to present the situations where there is a 'Solution
"Optimal Alternate" and where multiple "Multiple Optimal Solutions" are present:

3.1. Alternate Optimal Solution.

To analyze a problem with an 'alternative optimal solution', the fertilizer problem will be addressed again.
but slightly modified the Objective Function. The same constraints were left but the
Objective function to a new one, leaving the model as follows:

Objective Function Max. Z = 100X1+ 200X2

Restrictions: Nitrate 0.05X1+ 0.05X2≤1,100

Phosphate 0.05X1+ 0.10X2<=1,800
Potassium 0.10X1+ 0.05X2≤2,000

Solution by the Simplex Method.

The following are all the tables (iterations) of the problem:

Initial Table (Table 1)

Base Cj X1 X2 H1 H2 H3 Bi BI
100 200 0 0 0
AI ' v e
V1 H1 0 0.05 0.05 1 0 0 1100 22,000
V2 H2 0 0.05 0.10 0 1 0 1800 18,000 →VS
V3 H3 0 0.10 0.05 0 0 1 2000 40,000
Zj 0 0 0 0 0 0
∆j 100 200 0 0 0

VE

"Adjustment Criteria" to move to Table 2:

V2
Pivot Line N2=
0.10
N1= V1- 0.05N2
N3= V30.05N2

Table 2 (Final Table).

Base Cj X1 X2 H1 H2 H3 Bi BI
100 200 0 0 0
AI ' v e
N1 H1 0 0.025 0 1 -0.5 0 200 8,000→VS
N2 X2 200 0.5 1 0 10 0 18,000 36,000
N3 H3 0 0.075 0 0 -0.5 1 1,100 14,666.7

JEVA / PTI
13
LINEAR PROGRAMMING METHOD
SIMPLEX

Zj 100 200 0 2,000 0 3,600,000

∆j 0 0 0 -2,000 0

VE

The optimal solution to this problem is:

H1= 200
X218,000
H31,100
Max. Z = 3,600,000

When analyzing the 'Final Table' of the problem, two non-basic variables are found, the X1and the H2. The H2does not meet
with all the conditions but the X1Yes. So the problem has an alternative optimal solution. To calculate
this optimal alternating solution is forced as Input Variable X1and the following Table is calculated.

"Adjustment Criteria" to move to the next table:

V1
Pivot Line N1=
0.025
N2= V2-0.5N1
N3= V3-0.075N1

Table of the Alternate Optimal Solution.

Base Cj X1 X2 H1 H2 H3 Bi
100 200 0 0 0
X1 100 1 0 40 -20 0 8,000
X2 200 0 1 -20 20 0 14,000
H3 0 0 0 3 1 1 500
Zj 100 200 0 2000 0 3,600,000
∆j 0 0 0 -2000 0

An alternate optimal solution has been calculated for the problem which is:
X1= 8,000
X2= 14,000
H3= 500
Max. Z = 3,600,000

A characteristic of the alternate optimal solution is that it must provide a different solution but the same value of.
the Objective Function that the optimal solution normal, in this case 3,600,000.

If the 'Final Table' is analyzed again, it will be seen that the variable H1meets all the conditions. To
solving, by following the same procedure, the previous optimal solution will be found. The two are presented
optimal solutions to the problem:

Optimal Solution Optimal Alternate Solution

H1= 200 X18,000
X2equals 18,000 X214,000
H3= 1,100 H3= 500
Max. Z = 3,600,000 Max. Z = 3,600,000

Interpretation of the 'Optimal Solutions' of the problem.

JEVA / PTI
14
LINEAR PROGRAMMING METHOD
SIMPLEX

The production program for the next month can be manufactured in two possible ways. One way
It will produce 18,000 tons of the 5-10-5 fertilizer. 2=18,000) to have the maximum utility of
$3,600,000 (Max.Z=3600,000). By doing this manufacturing program, there will be 200 tons left over.
Nitrate (H1=200) and 1,100 tons of Potassium (H3=0).
Another alternative solution is to produce 8,000 tons of the fertilizer 5-5-10 (X 1=8,000) and 14,000
tons of 5-10-5 (X 2to have the maximum profit of $3,600,000 (Max.Z=3600,000). At
This program will leave 500 tons of Potassium.3=500).

Optimal Range.
In most problems, the slope of the Objective Function passes through a vertex of the feasible region.
generating a unique or specific solution. When a problem has an optimal alternate solution, it means that the
the Objective Function slope passes through one side of the feasible region generating different solutions
optimal. This is a consequence of the fact that the slope of the Objective Function is parallel to one side of the
feasible region. This serves as a basis for establishing the 'Optimal Range' of the problem, by setting the range of
variation for each of the variables.

To calculate the Optimal Range, it should be remembered that the variables that are not part of the optimal solution
initial of the problem, they have a value of 'zero'. With this consideration and comparing the two solutions
optimal solutions found for this problem that has only two decision variables, it can be established the
Optimal range remaining in the following form:
Optimal Range: X ≤ 8,0001greater than or equal to 0
18,000≥X2>=14,000
200≥H1greater than or equal to 0
1,100≥H3≥500
Max. Z = 3,600,000

Knowing the Optimal Range for this problem with two decision variables allows us to plan different
optimal solutions that respond to specific needs. For example, if you want to manufacture 5,000
tons of fertilizer 5-5-10 (X 1From 5,000) it can be calculated how many tons of the 5-10-5 fertilizer are available.
what to produce to have the maximum utility of $3,600,000. This is calculated as follows:

3,600,000 = 100(5,000) + 200 X2

X2 = 15,000

According to this calculation, 15,500 tons of the fertilizer 5-10-5 must be produced.215,500)

If within the values of the optimal range, the values of X are set simultaneously.1y X2, it can be generated
a non-optimal solution, so it is necessary to verify it. It must be checked that the value of the Function
The objective is the same in any case.

3.2. Multiple Optimal Solutions.

A problem that has several optimal solutions is also said to have 'multiple optimal solutions'. The
The following problem is an example of this type:

Chain of stores.
A large chain of grocery stores has several establishments that operate 24 hours a day.
From past experiences in the stores, it was observed that better service can be provided to
the client assigns 8-hour shifts to their employees but staggered in 4-hour periods, it is
It is said that a shift starts every 4 hours.
The company's management has determined the staffing needs for the next month.
presented in the table provided below:

Shift Period Personal

Required
1 8 to 12 hours 35
2 12 a 16 30
3 16 to 20 40

JEVA / PTI
15
LINEAR PROGRAMMING METHOD
SIMPLEX

4 20 to 24 20
5 24 to 4 10
6 4 to 8 25

The Administration would like to have a model that allows them to determine how many employees should
work in each shift in such a way that the total number of employees is minimal.

Modeling.
Decision Variables.
Xi = Employees to work the Shift 'i'
(e)

Función Objetivo.
min. Z = X1+ X2+ X3+ X4+ X5+ X6
e e

Restrictions.
1. Periods.
8 to 12 hours X1+ X6>=35
12 to 16 X1+ X2≥30
16 to 20 X2+ X3≥40
20 to 24 X3+ X4greater than or equal to 20
24 to 4 X4+ X5greater than or equal to 10
4 to 8 X5+ X6≥25
e e
2. No negativity Xi => 0

Dimensional Analysis: Tested.

Solution of the problem modeled on the computer.

By solving this problem on the computer, the following 'Final Table' was obtained where it can be read the
optimal solution:

Final Table (First Optimal Solution)

* * *
Base Cj X1 X2 X3 X4 X5 X6 E1 E2 E3 E4 E5 E6 Bi Bi
-1 -1 -1 -1 -1 -1 0 0 0 0 0 0
AI h a v e
X1 -1 1 0 0 1 0 0 -1 0 0 0 -1 1 20 20
X2 -1 0 1 0 -1 0 0 1 -1 0 0 1 -1 10 -10
X3 -1 0 0 1 1 0 0 -1 1 -1 0 -1 1 30 30
E4 0 0 0 0 0 0 0 -1 1 -1 1 -1 1 10 Infinite
X5 -1 0 0 0 1 1 0 0 0 0 0 -1 0 10 10→VS
X6 -1 0 0 0 -1 0 1 0 0 0 0 1 -1 15 -15
Zj -1 -1 -1 -1 -1 -1 1 0 1 0 1 0 -85
∆j 0 0 0 0 0 0 -1 0 -1 0 -1 0

VE

Upon analyzing the 'Final Table' of the problem, it was found that X4, E2y E6they are the 'non-basic' variables that
They meet the conditions to have alternative optimal solutions. In this case, there is a problem with
multiple optimal solutions, with at least four different solutions.

In the 'Final Table' you can read the first optimal solution to the problem, which is the following:
X1= 20
X2= 10

JEVA / PTI
16
LINEAR PROGRAMMING METHOD
SIMPLEX

X3= 30
E4= 10
X5= 10
X6= 15
min. Z = 85

To calculate the second optimal solution of the problem, X was forced as an Input Variable.4and were applied
the Adjustment Criteria to calculate the following table:

Adjustment Criteria to calculate the 'second optimal solution' of the problem:

Pivot Line N5= V5

N1= V1 - N5
N2= V2+ N5
N3= V3- N5
N4= V4
N6= V6+ N5

Final Table (Second Optimal Solution)

* * *
Base Cj X1 X2 X3 X4 X5 X6 E1 E2 E3 E4 E5 E6 BI Bi
-1 -1 -1 -1 -1 -1 0 0 0 0 0 0
AI ' v e
X1 -1 1 0 0 0 -1 0 -1 0 0 0 0 1 10 Infinite
X2 -1 0 1 0 0 1 0 1 -1 0 0 0 -1 20 -20
X3 -1 0 0 1 0 -1 0 -1 1 -1 0 0 1 20 20
E4 0 0 0 0 0 0 0 -1 1 -1 1 -1 1 10 10→VS
X4 -1 0 0 0 1 1 0 0 0 0 0 -1 0 10 Infinite
X6 -1 0 0 0 0 1 1 0 0 0 0 0 -1 25 Infinite
Zj -1 -1 -1 -1 -1 -1 1 0 1 0 1 0 -85
∆j 0 0 0 0 0 0 -1 0 -1 0 -1 0

VE

In this "Final Table" the "second optimal solution" of the problem can be read, which is:
X1= 10
X2= 20
X3= 20
E4= 10
X4= 10
X6= 25
min. Z = 85

JEVA / PTI
17
LINEAR PROGRAMMING METHOD
SIMPLEX

After calculating the second optimal solution, we return to the Final Table of the first solution and continue.
calculating the other optimal solutions. Now E is selected as the Input Variable2to calculate the
"third optimal solution" of the problem. The same procedure described earlier is followed. It is presented
the calculations to find the other optimal solutions to the problem:

Adjustment criteria to calculate the 'third optimal solution' of the problem:

Pivot Line N4= V4

N1= V1
N2= V2+ N4
N3= V3- N4
N5= V5
N6= V6

Final Table (Third Optimal Solution)

Base Cj X1 X2 X3 X4 X5 X6 E1 E2 E3 E4 E5 E6 BI BI
-1 -1 -1 -1 -1 -1 0 0 0 0 0 0
AI ' v e
X1 -1 1 0 0 0 -1 0 -1 0 0 0 0 1 10 10→VS
X2 -1 0 1 0 0 1 0 0 0 -1 1 -1 0 30 Infinite
X3 -1 0 0 1 0 -1 0 0 0 0 -1 1 0 10 Infinite
E2 0 0 0 0 0 0 0 -1 1 -1 1 -1 1 10 10
X4 -1 0 0 0 1 1 0 0 0 0 0 -1 0 10 Infinite
X6 -1 0 0 0 0 1 1 0 0 0 0 0 -1 25 - 25
Zj -1 -1 -1 -1 -1 -1 1 0 1 0 1 0 -85
∆j 0 0 0 0 0 0 -1 0 -1 0 -1 0

VE

Third optimal solution:

X1= 10
X2= 30
X3= 10
S2= 10
X4= 10
X625
min. Z = 85

Adjustment criteria to calculate the 'fourth optimal solution' of the problem:

Pivot Row N1= V1

N2= V2
N3= V3
N4= V4- N1
N5= V5
N6= V6+ N1

Final Table (Fourth Optimal Solution)

Base Cj X1 X2 X3 X4 X5 X6 E1 E2 E3 E4 E5 E6 BI
-1 -1 -1 -1 -1 -1 0 0 0 0 0 0
E6 0 1 0 0 0 -1 0 -1 0 0
X2 -1 0 1 0 0 1 0 0 0 1

JEVA / PTI
18
LINEAR PROGRAMMING METHOD
SIMPLEX

X3 -1 0 0 1 0 -1 0 0 0 -1
E2 0 -1 0 0 0 1 0 0 1 1
X4 -1 0 0 0 1 1 0 0 0 0
X6 -1 1 0 0 0 0 1 -1 0 0
Zj -1 -1 -1 -1 -1 -1 1 0 1 0 1 0 -85
∆j 0 0 0 0 0 0 -1 0 -1 0 -1 0

Fourth optimal solution:

E6= 10
X2= 30
X3= 10
E 2= 0
X4= 10
X6= 35
min. Z = 85

In the Table of the 'third optimal solution', if X is entered as the Input Variable5a 'fifth' will be obtained
optimal solution" that will be:
X1 = 20
X2= 20
X3= 20
E2= 10
X5= 10
X6= 10
min. Z = 85

A summary of the "multiple optimal solutions" of the problem is presented:

Variables Multiple Optimal Solutions

Basic 1 2 3 4 5
X1 20 10 10 20
X2 10 20 30 30 20
X3 30 20 10 10 20
X4 10 10 10
X5 10 10
X6 15 25 25 35 15
E2 10 0 10
E4 10 10
E6 10
min. Z 85 85 85 85 85

Interpretation of the problem solution.

This problem has five different optimal solutions that are characterized by having the same value of the
Objective Function (min.Z=85). The interpretation of the first optimal solution of the problem is presented.
example way:

JEVA / PTI
19
LINEAR PROGRAMMING METHOD
SIMPLEX

Schedule 20 employees to work shift 1 (X1=20), 10 in shift 2 (X2=10), 30 in shift 3

(X3=30), 10 in turn 5 (X5=10) and 15 in turn 6 (X6=15). In this way, there will be a total of 85
employees being the minimum amount to cover all requirements (min.Z=85). With this
The assignment will have in shift 4, 10 employees more than the minimum required, which is 20.

For problems with multiple optimal solutions, as is this problem, it is not practical to make a ranking.
optimal solutions but rather to calculate all possible optimal solutions to the problem. It
It is recommended to use a computer with suitable software to calculate all optimal solutions for.
the end.

JEVA / PTI
20