Two-Phase Simplex Method

Karla Johanna Guevara Panama, Isaura Melany Jingo Cevallos, Blanca Luciana Segovia Rosero
Faculty of Engineering in Applied Sciences
Degree in Electronic Engineering and Communication Networks
Technical University of the North
Ibarra-Ecuador
kjguevarap@[Link], imjingoc@[Link], blsegoviar@[Link]
 auxiliary variables X4 and X5 base be gets
Summary - This document models of Programming they have a reduced cost equal to Min{8/2}=4,
explain the Linear simplex method that later is one (given their respective determining that X5 leaves from
of two phases that consists of carried out a its shape coefficients in the function the base. To update the
a standard algorithmic strategy does not allow obtaining objective of that phase. table we add row 2 to the
that applies when a feasible basic solution is later row 3 (so that the cost
of carrying an initial model in the variables of the reduced of X1 it
linear programming to its model. To face this transform into zero) and then
standard form does not exist in different situations we multiply the row by 1/2
has a solution of algorithmic strategies between 2 and we add it to row 1
basic feasible initial, those that highlight the Method (so that in this way X1
examining Two-Phase Simplex intervals and basic sea associated with the row
Table 1
feasibility and intervals of the M Great Method 2, taking the structure of
optimality. the which ones are usual to be The following are conducted to the basic outgoing variable
Analysis of duality discussed in courses of zero the reduced costs of X5).
sensitivity analysis and Research Operational X4 and X5. For this, it is
programming models (Research of they perform row operations,
primal linear (MPL) y Operations). In the for example, first
dual. next article us multiplying row 1 by -1
we will concentrate in the and adding it to row 3, for
Keywords-phenomena analysis of the first then multiply by -1 the
electrification, charge alternative through a add row 2 to row 3. Table 5
electric insulators, theoretical-practical approach.
It is verified that it is concluded.
drivers.
Example Simplex Method the Phase I of the Method
of Two Phases Simplex of Two Phases. This
INTRODUCTION Consider the MPL using the situation is detected when
On many occasions we theTwo-Person Simplex Method a solution is available
we will find with models Phases. basic that satisfies the
where the set of Max Z = X1 + 3X2 Table 2
conditions of no
solutions feasible S.A. X1-X2 ≤ -2 negativity where the
they do not consider the origin X1 + X2 = 10 Note now that the variables
non-basic variables have
X1, X2 ≥ 0 basics are X4 and X5 and the
as one of them, therefore reduced costs greater or
what will be impossible to use non-basic variables are X1,
equal to zero and the value of the
the simplex method Phase I (Simplex Method of X2 and X3. Among the variablesobjective function is equal to
For this type of cases, we Two Phases not basic the one that has cost
zero.
Han created negative reduced is X2, for
many methodologies that In this case result so that variable enters into
the Base and based on the criterion
Phase II (Simplex Method of
they seek to resolve this typeconvenient to multiply by Two Phases
of problems searching -1 the first restriction of of feasibility or minimum
the solution through so that the right side quotient himself
determines
The following begins with
various processes. One of be positive, which has that basic variable that
Phase II of the Method
leave the base. This is obtained
these alternatives are the as an additional effect that Simplex of Two Phases. In
two-phase method, the change the meaning of thefrom Min{2/1; 10/1}=2. By this stage eliminates the
which, as its name suggests inequality. In so much X4 leaves the base andcolumns associated with the
indicates, works through the consequence of the problem perform an iteration.
variables helpers
2 phases or procedures, what defines Phase I of used in Phase I of the
with the aim of finding Two-Phase Simplex Method method (in the example the
first a solution Phases are: variables X4 and X5) and it
feasible initial update the cost vector
and then move on to solving the MIN X4+X5 reduced considering the
model through the method S.A. -X1+X2-X3+X4 function objective delete
simplex. To use this =2 Table 3 problem original in
method should be taken X1+X2 +X5 minimization format
the model in his shape =10 After finishing the this is MIN -X1–3X2.
expanded the variables Xi >= 0 for i = 1, 2, 3, 4, 5 iteration is now available
they must make a decision to be two non-basic variables with
real and greater than zero. Where X3 is variable of negative reduced cost: X1
[1] excess and X4 and X5 are y X3. Having in
artificial variables of the consideration a criterion of
SIMPLEX METHOD OF TWO restriction 1 y 2 rate of convergence is
FACES respectively. Then privileges entry to the
Table 5
we are in a position to base of X1 having this
The Two-Phase Simplex Method reduced cost more negative.
create the initial table It is worth remembering that the
Phases allow to address the
from Phase I where the The basic variable that leaves
resolution of those basic variables completed
Phase I are X2 and X1 and they allow obtain Maximize or minimize =
after the update of additional information about a V. MODEL OF
the line of reduced costs optimization problem PROGRAMAC
(row 3) it will be necessary to bring
general. This in relationships LINEAR ION
sus respective costs
of linear programming we DUAL This is subject to:
reduced to zero, for which
row 2 is added to row 3 and leads to primal relationships
The dual problem is a
then it is multiplied by 3 dual.
defined linear programming
row 1 and is added to row 3, This relationship consists of that
obtaining the following: in form direct y
everything problem of
systematic a as of
primal optimization has a The variables xj, j = 1,
original model (or primal)
dual associated problem. 2, ..., n, include the
of linear programming. The
The theory of duality is variables surpluses,
two problems they are
important, both from the clearances and artificial.
related in such a way
theoretical point of view as Table 1 shows how
narrower than the resolution
of the practical. [3] build the dual problem to
Table 6 optimal of a problem starting from the primal and it is given
produced automatically
From the previous procedure IV. MODEL OF what:
it turns out that the variable does not the optimal resolution of
PROGRAMAC
Basic X3 has a cost another.
LINEAR ION
reduced and therefore enters The dual model is defined
PRIMAL
the base. The basic variable for various forms of the
what the base leaves is obtained The changes that are made in primal, depending on the
from Min {4/1/2} = 8 and for
the original model of sense of optimization
X1 is leaving the base. maximization o mini-
This results in a linear programming affects
iteration Del method to the elements of the table minimization) that goes away
obtaining the next optimal is current (the one that to give, types of restrictions Illustration 1.
table: have at the moment), that to (≤, ≥ or =), and the orientation CONSTRUCTION
can also affect the of the variables (non-negative DEL MODEL
optimality y/o the or unrestricted). DUAL A LEAVE
feasibility of the solution This type of treatment DEL MODEL
actual. For this reason It can be confusing because of this. PRIMAL
we will study how only one reason is presented
himself
they recalculate the elements of definition that encompasses in
Illustration 2 indicates the
Table 7 rules for building the
the optimal simplex table automatically to all the
dual model
Observe that the variable does not to reflect the new ones forms of the primal. The
basic X1 has a cost changes. definition of the dual problem The rules to determine the
reduced equal to 2 (that The relationship between the requires to express the meaning of optimization
meets the conditions of maximization o
problem Dual y yes primal problem in the form of
no negativity), in addition to minimization), the type of
associate is to say the equations, such that all the
face a solution restriction (≤, ≥ or =), and the
original problem called restrictions are equations,
basic feasible for X2 and X3. sign of the dual variables
primal presents various with non-negative right side
(still not restricted) it
Therefore, the Phase concludes. utilities how, for and all the variables are no
II of the Simplex Method of example: negatives. summary in the following
Two Phases with Solution table:
- Provides elements This requirement is consistent
optimal X1=0, X2=10 and X3= that increase with the table format of
8 and optimal value V(P)=30. start simplex. In
substantially the
[2]
understanding of the consequence, every result
III. DUALITY PL obtained from the
- The analysis of the optimal primal solution is
All problem of duality is applied directly to the Illustration 2.
optimization (primal), has useful tool in associated dual problem. [3] RULES FOR
a related (dual) problem the solution to show how it is formed TO BUILD THE
with numerous properties PL problems the dual problem is defined MODEL
that relate them and us - The dual problem the primal in the form of
allow for a better has equation like this:
Note that the meaning of the
analysis of the problems. interpretations e dual optimization
The duality results from information is always the opposite of the
to search relationships what important. primal. An easy way to
remember the type THEOREM To obtain the solution, the parameters of the problem
restriction (i.e., ≤ or ≥) DUALITY optimal since like in a so that the optimal base
in the dual it's that if the WEAK: In general, the linear problem the solution found follows being
objective del dual it value of any optimum (if it exists) optimal.
The goal is to identify the
minimization (that is, a feasible solution is at a vertex, this sensitive parameters. For
"points downwards" problem it implies solving a system example, the parameters
restrictions are all of the minimization provides from equations (with whose values cannot
type ≥ (that is, "they point an upper bound on equality constraints. change without changing the
upward). When the value optimal del [4] optimal solution.
objective dual es problem de It is important because we
VII. USE OF allows to investigate the effect
maximization the opposite is maximization. what would the solution have
valid. [3] Similarly, the value SOFTWARE
optimal provided by the
Steps from the objective function of FOR simplex method in fact
For the resolution of this any solution DUALITY that the parameters (data
model the steps to follow feasible of the problem of WinQSB they will take others
they are the following: maximization is a possible values [5].
If the cousin is a problem lower bound of the value For the solution of
problems in WinQSB are Through the analysis of
of Maximization, the dual is optimal of the problem of
proceed in the same way sensitivity can exist
a problem of minimization. different types of exchanges
What about the previous ones
Minimization and vice versa in the original model as:
therefore: problems that are solved.
1. If define a THEOREM DE Suggesting since a 1. Changes in the
DUALITY first the theme, the number coefficients of the function
dual variable for
STRONG: In the optimal of variables and the function to objective, Cij
each equation
primal (restriction). the value of the function make in this case if the 2. Changes in resources,
objective of the problem the problem is to maximize or
bi
2. It define one 3. Changes in the
dual restriction by primal will be equal tominimize. technological coefficients, aij
As is known
each variable value of the function
objective of the problem our we resolve the 4. Addition of a new
primal. variable y Xi
3. The coefficients of problem by means of the 5. Addition of a new
dual evaluated in the
restriction simplex method of restriction. aij >= bi[6].
optimal dual solution. If
(column) of a program to thus have of
the primal problem is
quickly shapes the results Shadow Price: change in
variable primal not limited, then the
of the problem. the value of the function
define the dual it infectable.
When solving the simplex,objective for increase
coefficients in the Alternatively, if the
we will give a click about unitary in the value of the side
left side of the the primal problem is right of a restriction,
the 'Results' tab where
dual constraint, and unfeasible, so the the shadow price corresponds
we can observe the options at an exchange rate of
his coefficient dual is unbounded.
forsensitvityanalysisfor optimal value in the face of a
objective defines the
hte obejcvite funcoitn and for hte marginal modification of a
right side.
shadow function side law of a
4. The coefficients COMPLEMENTARY:
Byccilknigontheanaylsiofthe restriction. Another aspect
objective of the dual Unvariable in the primal relevant of the shadow price
they are equal to the side is
obejcvitefuncoitn,hte..
associated a a it turns out to be its meaning
decsionvaraibelsandchanges
right of the restriction in the dual (y economic. The sides
posbielfohrtemandkilewsie rights in the case of a
equations of vice versa). In this sense if
sedaparalafunciónsombra, etc. maximization model
primal constraint in the primal there is a
It shoudl aslo be noetd htat generally they are
like in the table variable not basic (value
thereportingtoolexists related to availability
that is shown in the equal to zero), in the dual the
combniedni,whcihyoudsipalyhtemof scarce resources, due to
top. associated restriction is not example, for utilization
5. The procedure is from theactive, that is, it is not fulfilled
posbiel changesinhtesame
table. in a production process
the same way that in equality. Similarly, (materials, man-hours,
in the method if the variable is basic in the financial resources, etc). In
VIII. ANALYSIS OF this meaning the shadow price
simplex primal the restriction SENSITIVITY can
associated in the dual to represent a
D disposition a pay for
VI. THEOREMS fulfills in equality. This
additional resource unit.
theoretical result is useful all The sensitivity analysis If the price of the resource is
time that simplifies the form it involves determining which lower than the shadow price
it is the range of variation of
then will exist a zero, with their respective X1 -1 0 0.3 -0.4 1 F3*
incentive to 'buy' more slack variables. 1
due to the fact that this will have a Z-4X1-6X2+OS1+OS2=0 Table 11.
net positive impact on R1 2X1 + 4X2 + S1 + OS2 <=
objective function[7]. 120 HR DISP PROD Step 5 Step 8
R2 Multiply the matrix B-1* With the variation of the hours
Optimality interval: 4X1 + 3X2 + OS1 + S2 <= 100 B*, which is the resultant of the available for inspection and
is the interval HR DISP INSPE AND EMPQE variation of the packaging can be manufactured:
variability of a availability of hours of 1 leather strap
coefficient of the simplex table function inspection and packaging. X2=2 canvas straps
objective. X1 X2 S1 S2 RES XB=B-1*B* Obtaining a profit of
XB=B-1 $2.
-4 -6 0 0 0
Feasibility interval. 0.15 -0.2 120
It is the interval 2of 4 1 0 120
-1 IX.
variability on one side 4 3 0 1 100
-0.3 0.4 IX.
right of a restriction. Table 8. Simplex table 95 IX.
2
0.15(120) + IX.
Procedure for the Simplex table result (-0.2)(95)=-1 ANALYSIS OF
sensitivity analysis optimal -0.3(120) + (0.4)(0.95) = 2 SENSITIVITY
Model review. CJ X1 X2 S1 OF USING
Review of the simplex table Z 0 0 1,2 WINQSB
final. 6 X2 0 1 0.15 When we write a
Conversion a the form 4 X1 1 0 -0.3 Z*=CB1(XB)=6.4 -1 model, we assume by
appropriate. Table 9. Simplex table on 6() - 1 + 2(2) accepted that the values of
Feasibility test. optimal result -6+8=2 2 the parameters are known
Optimality test. with certainty; but in the
Re-optimization. X1=4 X2=28 Z=184 reality no
Step 6 it is always the case that the
Exercise1: Step 2 The solution is not optimal, values be truthful, already
A company that is dedicated to I select the coefficients due to the fact that there is 1 hour left from
what for example the
the manufacture of two types of of the variables of the production for power variations in costs of
economic belts one of restrictions of X1, X2, of to comply with the the materials, in the hand of
leather and another of canvas, gives to maximization of the work or on the price of a
my first table a1=X1,
to know the maximum profit a2=X2. earnings, for that reason product, cause changes
what is obtained from the we must carry out in the
production of the two classes A1 2 A2 4
another table for what coefficients of the function
from belts, the profit of the values of the objective. Likewise the
a leather strap is 4 4 3 variables sean delays in shipments of the
dollars and the canvas one is 6 positives for the providers, the
dollars. mayor strikes, the damages do not
If count with a 120 4 maximization foreseen and other factors
B CB
availability of 120 hours imponderables will generate
for production and 100h 100 6 Step 7 changes in the
for the inspection y In this table is availability of the
packaging. Step 3 multiply F3*-1 so that resources.[8]
A leather strap requires We select the the coefficients of the
2 hours of production and 2 hours of variables take a value Example:
coefficients of the variables
packaging. A canvas strap of the final table's slack positive to maximize the MPL
requires 4 hours of production and of optimization resources according to a Maximize Z = 3X1 + 5X2
3 hours of packaging B -1 variation of the Subject to
The same. X1 ≤ 4 (Available hours in )
0.15 -0.2
Variables X1 S2 RS the plant 1)
X1= leather straps 2X2 ≤ 12 (Available hours)
-0.3 0.4
X2=canvas belts Z 0 0 1,2 1 2 on the second floor
factory X2 0 1 0,1 -0.2 2 3X1 + 2X2 ≤ 18 (Hours)
MPL has decided to decrease by 5% 5 available on the 3rd floor)
4X1 + 6X2 the available hours of X1 1 0 -0.3 0.4 -1 X1, X2 ≥ 0 (Constraint of
S.A. inspection and packaging. no negativity
R1: 2X1 + 4X2 <= 120 Table 10.
R2:4X1+3X2<=100 Step 4
X1, X2 >= 0 Modify the availability X1 X2 S1 S2 RS
in the given initial restriction.
Step 1 R2 4X1 + 3X2 = 95 Z 0 0 1,2 1 2
Build the restrictions and X2 0 1 0.1 -0.2 2
objective function equating it B* 5
120

95
 If the restriction is >= analyze the
so a shadow price
no positive increases the
costs.
If the restriction is <=
Non-negative shadow price
increase profits. For
the example, the restrictions
2 and 3 have shadow prices
Illustration 3. Final solution positives, which indicates to us
using WINQSB how much does the FO increase by
each unit of resource
Sensitivity can be additional.
analyzing by checking the
Yes the restriction of
changes in: equality
It can be: Positive, negative, sensitivity of the solution The Figure 6 allows us
1. Changes in the to zero. optimal, when added to understanding as what happened
coefficients of the Function model a restriction that was that the new restriction
Objective (FO). Upon reviewing the4. Slack variables that were not initially considered affected the region of
final table of the methodexcess. In the table at the end either due to forgetfulness or the feasibility of the problem,
simplex, we find the of the simplex method, decision of who proposed the eliminating of it the sector
columns: obtained with WinQSB there is a model. what does the solution include
- Allowable Min C(j) a column labeled: Slack The first
(minimum allowed) o Surplus (Defect o step in the
- Allowable Max. C(j) Excess), a value against analysis of
(maximum allowed) each restriction. the
In front of each variable of Any restriction with changes
decision we find in shadow price not zero, must suffer
the range in those columns to be one restriction the solution
which can vary the mandatory (is optimal
coefficients of said to say, to have a margin, or current to the
variables. For the example, excess equal to zero). In considering
X1 can vary between 0 and 7.5 example previous the a new
without the optimality of the restrictions 2 and 3 are restriction
solution changed. mandatory.
Likewise, X2 may vary. Any restriction with determining
between 2 and M (M is a value a slack excess oif this is
very large number). For different from zero, has a requirement for the optimal solution actual. We must
the example, the utility for shadow price equal optimal. To do this, they must then find the new
each product unit 1 to zero. In the example, replace the values solution optimal what
can vary between 0 and 7.5 withoutrestriction 1 (C1) has an optimum of the variables that correspond a the new
what the value of the solution 2 unit clearance, therefore the new restriction y feasible region
I changed (Use WinQSB to as much to determine if it is met
try with some of those increase that resource only expressed condition.
values). Likewise, for the it will increase costs. We conclude that the solution
product 2, any income -If the current shadow price is not altered, then Illustration 4
above 2 will not change as the slack (or excess) new restriction also
the value of the solution It is zero, meaning that at a birthday for her. Such case Illustration 5
optimal. vertex it happens in situations like
they are converging more than we can observe in
2. Changes in the coefficient two restrictions. Figure 4, where the
of a non-basic variable There are also two new restrictions A does not alter
(V.N.B) in the Function columns: Allowable Min. the feasibility region.
Objective. A change in a RHS (Minimum resource of the other situation of the same
coefficient of a V.N.B in right side) and Allowable case is the one shown in
the F.O can change the Max. RHS (Maximum resource Figure 5 for the new
optimal solution. on the right side) which gives us restriction B, which does alter the
they indicate the range in which the feasibility region is located, but
3. Shadow prices. Also the right side can vary without changing the point
called dual prices. They are of each restriction without the optimal.
an indicator of when optimality is affected. But when the values
it is advisable to increase the side
optimums do not satisfy the
right of restrictions. 5. Addition of a new new restriction
In general for the restriction on the model. we conclude that the solution
restrictions we can Many times the optimal current situation is unfeasible.
consider
Illustration 6 Excel Solver [Online].
Available:
X. REFERENCE [Link]
S. [Link]/analysis_of_s
[Link]
L. D. Reyes Escalera [Link] Vargas,
programmingmethods University National
ealdan, [Online]. Available: autonomous of
Cannot translate or access external nicaragua"2010.
links. [Online].
online programming methods Available:
aldan/two-methods- [Link]
phases. [Accessed 26 12 dspace/bitstream/handle/110
2017. 59/2008/[Link];seq
F. 'simplex method,' 25 uence=1.
September 2015. [Online]. Available: E. Romero "Analysis of
[Link] sensitivity [Online].
om/simplex-method-of-two- Available:
phases/. [Accessed 26 12 [Link]
2017. s_universidad/Inv_Oper_I/A
ANONYMOUS, "SCIENCES Sensitivity [Link]
- PREYMOND, " 23
NOVEMBER 2011.
[Online]. Available:
[Link]
preymond/Others/optimization
n2./[Link]. [Accessed 1
JANUARY 2018.
RESEARCH OF
OPERATIONS, 16
JANUARY 2016. [Online].
Available:
[Link]
[Link]/duality_in_
linear_programming.html.
[Accessed 1 JANUARY 2018].
Theory
of duality and analysis of
The Sensitivity" [Online].
Available:
Invalid input. Please provide text for translation.
andresaceroalmonacid/teora-
of duality and analysis of
sensitivity
[6]
Operations Research.
Sensitivity analysis
o postoptimal in
Linear Programming -
Sensitivity Reports of