Bahçeşehir Cyprus University

DEPARTMENT OF INDUSTRIAL ENGINEERING

OPERATIONS RESEARCH II
INE 3201
 DUAL SIMPLEX ALGORITHM
• Dual Simplex method is used in 3 cases;
1. Adding a new constraint into the model
2. Changing the right hand side values of the current constraints
3. Solving minimization problems
• In a Simplex Tableau, if the optimality condition is satisfied (i.e., z row values of all non-
basic decision variables are non-positive (≤0) in a minimization problem, non-negative (≥0)
in a maximization problem) but feasibility condition is violated (i.e., there are basic decision
variables with negative values), we may use the Dual Simplex Algorithm.
• We may have such a Simplex Tableau if some new constraints are added to the model
and the optimal Simplex tableau of the old model is updated according to the new
constraints.
 DUAL SIMPLEX ALGORITHM
• Suppose that you have an LP model and you solved it by the Simplex Algorithm. Then
some new constraints are added to the model. You may follow two alternate ways:
(1) Cancelling the previous solution and searching the new optimal solution by the Simplex
Algorithm from the very beginning,
(2) Updating the optimal Simplex Tableau of the old model according to the new constraints
and continue by the Dual Simplex Algorithm.

• 3 different cases appear by adding a new constraint into the model;

(1) Current optimal solution satisfies the new constraint.
(2) Current optimal solution does not satisfy the new constraint but the model with
the new constraint has still a feasible solution.
(3) The new constraint yields infeasibility.
 DUAL SIMPLEX ALGORITHM
• Assume that there is an old model and its optimal Simplex Tableau. Then some
new constraints are added to the model. Assume that you want to modify the
optimal Simplex Tableau of the old model and find the new solution of the model
by the Dual Simplex Algorithm.
• First you have to write all the new constraints in “≤” type.
• If a new constraint is “≥” type, you may multiply it by -1 and you may write it “≤”
type.
• If a new constraint is “=” type then you should replace this constraint with two
constraints: one “≤” type and other one “≥” type. Then the one in “≥” type should
be converted to “≤” type by multiplying by -1.
• RHS values of these new constraints can be negative.
• Having negative RHS values is not a problem for the Dual Simplex Algorithm.
 DUAL SIMPLEX ALGORITHM
• Second, you should add a new slack variable to each of those new “≤” type
constraints and you should write them in “=” type.
• Third, you should add a new row to the optimal Simplex Tableau of the old
model for each of these new “=” type constraints. Slack variables in these new
constraints should be added to basis column of the Simplex Tableau. You should
add a new column for each of these new slack variables.
• Last, in the columns of the newly added basic variables all the entries must be 0,
only the intersection cells of their rows and columns must be 1. If this is not
satisfied it should be satisfied by doing necessary row operations. There can be
negative values in the RHS column of the tableau, it is not a problem.
• At the end, you are ready to search the new solution of the modified model by
the Dual Simplex Algorithm
 DUAL SIMPLEX ALGORITHM
• If there is any artificial variable and its column at the old optimal Simplex
Tableau, then before starting the Dual Simplex Algorithm, its objective row entry
(or the entire column of the artificial variable) should be deleted and no artificial
variable should be determined as the entering variable in the Dual Simplex
Algorithm.
(“Step 4: Minimum Ratio Test (MRT) for determining the entering variable” of the
below Dual Simplex Algorithm should not be applied for the artificial variables)
 STEPS OF THE DUAL SIMPLEX ALGORITHM
• Step 1: Find a Simplex Tableau that the optimality condition is satisfied but
feasibility condition is violated.
• Step 2: If feasibility condition is satisfied STOP, the optimal solution. (Feasibility
test)
• Step 3: (Finding the basic decision variable that will leave the basic decision
variable set XB and move to the non-basic decision variable set XN)
• Let RHSj be the value of the jth basic decision variable.
• Let k = arg min{RHS j }
j =1, 2 ,...,m
RHS j 0

• Then, Xl is the basic decision variable in the kth constraint row of the current
Simplex Tableau.
• Note that arg min returns the value of j that yields the searched minimum value.
 STEPS OF THE DUAL SIMPLEX ALGORITHM
• Step 4: (Finding the non-basic decision variable that will enter to the basic decision variable
set XB)
ZCi
For all non-basic decision variable Xi, having negative caik value, compute: ca | Select
|
ik

the one having the minimum ratio as the entering variable: Xe.
If there is no non-basic with negative caik value STOP: Infeasible Solution.
• Step 5: Constructing the Simplex Tableau of the next basic decision variable set
Step 5-a) Replace Xl with Xe in the “Basic” column of the next Simplex Tableau.
Step 5-b) New pivot row = (current pivot row) / pivot element
Step 5-c) All other rows, including objective row,
New row = (current row) – (its pivot column coefficient in the current tableau)*(New
pivot row)
Go to Step 2.
 EXAMPLE 1
• Max z = 4x1 + 3x2 + x3 Basis X1 X2 X3 S1 S2 RHS
s.t.
3x1 + 2x2 + x3 + S1 =7 Max Z 1/2 0 1/2 3/2 0 21/2
2x1 + x2 + 2x3 + S2 = 11
X2 3/2 1 1/2 1/2 0 7/2
x1, x2, x3, S1, S2 ≥ 0
• The optimal Simplex Tableau is given as: S2 1/2 0 3/2 -1/2 1 15/2

• Assume that the following constraint is added to the model.

x2 ≤ 3
• Search the new optimal solution.
 EXAMPLE 1
• Max z = 4x1 + 3x2 + x3
s.t.
3x1 + 2x2 + x3 + S1 =7
2x1 + x2 + 2x3 + S2 = 11
x2 ≤ 3
x1, x2, x3, S1, S2 ≥ 0
• The optimal Simplex Tableau is given as:

• Assume that the following constraint is added to the model.

x2 ≤ 3
• Search the new optimal solution.
 EXAMPLE 1
• Max z = 4x1 + 3x2 + x3 Basis X1 X2 X3 S1 S2 RHS
s.t.
3x1 + 2x2 + x3 + S1 =7 Max Z 1/2 0 1/2 3/2 0 21/2
2x1 + x2 + 2x3 + S2 = 11
X2 3/2 1 1/2 1/2 0 7/2
x2 + S3= 3
x1, x2, x3, S1, S2 ≥ 0 S2 1/2 0 3/2 -1/2 1 15/2
• The optimal Simplex Tableau is given as:

• Assume that the following constraint is added to the model.

x2 ≤ 3
• Search the new optimal solution.
 EXAMPLE 1
Basis X1 X2 X3 S1 S2 RHS Basis X1 X2 X3 S1 S2 S3 RHS

Max Z 1/2 0 1/2 3/2 0 0 21/2

1 Max Z 1/2 0 1/2 3/2 0 21/2 2
X2 3/2 1 1/2 1/2 0 0 7/2
X2 3/2 1 1/2 1/2 0 7/2
S2 1/2 0 3/2 -1/2 1 0 15/2
S2 1/2 0 3/2 -1/2 1 15/2 S3 0 1 0 0 0 1 3
1- Leavıng ıs
Table 3: New row S3 = old row s3 – 1*row X2
S3 Basis X1 X2 X3 S1 S2 S3 RHS
Basis X1 X2 X3 S1 S2 S3 RHS
Max Z 0 0 1/3 4/3 0 1/3 31/3
Max Z 1/2 0 1/2 3/2 0 0 21/2
3 X2 0 1 0 0 0 1 3
3 X2 3/2 1 1/2 1/2 0 0 7/2
S2 0 0 4/3 -2/3 1 1/3 22/3
S2 1/2 0 3/2 -1/2 1 0 15/2
X1 1 0 1/3 1/3 0 -2/3 1/3
S3 -3/2 0 -1/2 -1/2 0 1 -1/2
 EXAMPLE 1
1- Leavıng ıs
Table 3: New row S3 = old row s3 – 1*row X2
S3 Rename S3 by X1
New X1 = old S3 / (-3/2)
Basis X1 X2 X3 S1 S2 S3 RHS New Z row = old Z row – (1/2)* New X1 row
New row X2 = old row X2 – (3/2)* New X1 row
Max Z 1/2 0 1/2 3/2 0 0 21/2 New row S2 = old row S2 – (1/2)* New X1 row
3
3 X2 3/2 1 1/2 1/2 0 0 7/2

S2 1/2 0 3/2 -1/2 1 0 15/2

S3 -3/2 0 -1/2 -1/2 0 1 -1/2 Basis X1 X2 X3 S1 S2 S3 RHS

MRT 𝟏/𝟐 -- 𝟏/𝟐 𝟑/𝟐 - -- Max Z 0 0 1/3 4/3 0 1/3 31/3

−𝟑/𝟐 −𝟏/𝟐 −𝟏/𝟐
𝟏 -- −1 -3 -- ---- X2 0 1 0 0 0 1 3
−𝟑
S2 0 0 4/3 -2/3 1 1/3 22/3
2- Entering 0,3 -- 1 3 -- ----
X1 1 0 1/3 1/3 0 -2/3 1/3
is X1
 EXAMPLE 2

• Max z = 4x1 + 3x2 + x3

Basis X1 X2 X3 S1 S2 RHS
s.t.
3x1 + 2x2 + x3 + S1 =7 Max Z 1/2 0 1/2 3/2 0 21/2
2x1 + x2 + 2x3 + S2 = 11
x1, x2, x3, S1, S2 ≥ 0 X2 3/2 1 1/2 1/2 0 7/2
The optimal Simplex Tableau is given as;
S2 1/2 0 3/2 -1/2 1 15/2

Assume that the following constraint is added to the model.

-x1 + 2x2 ≥ 5
• Search the new optimal solution.
 EXAMPLE 2

• Max z = 4x1 + 3x2 + x3

Basis X1 X2 X3 S1 S2 RHS
s.t.
3x1 + 2x2 + x3 + S1 =7 Max Z 1/2 0 1/2 3/2 0 21/2
2x1 + x2 + 2x3 + S2 = 11
-x1 + 2x2 ≥ 5 X2 3/2 1 1/2 1/2 0 7/2

S2 1/2 0 3/2 -1/2 1 15/2

x1, x2, x3, S1, S2 ≥ 0
The optimal Simplex Tableau is given as;

Assume that the following constraint is added to the model.

-x1 + 2x2 ≥ 5
• Search the new optimal solution.
 EXAMPLE 2

• Max z = 4x1 + 3x2 + x3

Basis X1 X2 X3 S1 S2 RHS
s.t.
3x1 + 2x2 + x3 + S1 =7 Max Z 1/2 0 1/2 3/2 0 21/2
2x1 + x2 + 2x3 + S2 = 11
x1 - 2x2 <= -5 X2 3/2 1 1/2 1/2 0 7/2

S2 1/2 0 3/2 -1/2 1 15/2

x1, x2, x3, S1, S2 ≥ 0
The optimal Simplex Tableau is given as;

Assume that the following constraint is added to the model.

-x1 + 2x2 ≥ 5
• Search the new optimal solution.
 EXAMPLE 2

• Max z = 4x1 + 3x2 + x3

Basis X1 X2 X3 S1 S2 RHS
s.t.
3x1 + 2x2 + x3 + S1 =7 Max Z 1/2 0 1/2 3/2 0 21/2
2x1 + x2 + 2x3 + S2 = 11
x1 - 2x2 + S3 = -5 X2 3/2 1 1/2 1/2 0 7/2

S2 1/2 0 3/2 -1/2 1 15/2

x1, x2, x3, S1, S2 ≥ 0
The optimal Simplex Tableau is given as;

Assume that the following constraint is added to the model.

-x1 + 2x2 ≥ 5
• Search the new optimal solution.
 EXAMPLE 2
Basis X1 X2 X3 S1 S2 RHS Basis X1 X2 X3 S1 S2 S3 RHS

Max Z 1/2 0 1/2 3/2 0 0 21/2

Max Z 1/2 0 1/2 3/2 0 21/2
X2 3/2 1 1/2 1/2 0 0 7/2
X2 3/2 1 1/2 1/2 0 7/2
S2 1/2 0 3/2 -1/2 1 0 15/2
S2 1/2 0 3/2 -1/2 1 15/2 S3 1 -2 0 0 0 1 -5

Basis X1 X2 X3 S1 S2 S3 RHS

Max Z 1/2 0 1/2 3/2 0 0 21/2

X2 3/2 1 1/2 1/2 0 0 7/2

S2 1/2 0 3/2 -1/2 1 0 15/2

S3 4 0 1 1 0 1 2
 EXAMPLE 3
• Consider the following primal LP model: Basis X1 X2 E2 S3 A1 A2 RHS
Min z = 4 X1 + X2
s.t. Min Z 0 0 0 -1/5 (7/5-M) -M 17/5
3 X1 + X2 = 3
4 X1 + 3 X2 ≥ 6 X1 1 0 0 -1/5 2/5 0 2/5
X1 + 2 X2 ≤ 4 X2 0 1 0 3/5 -1/5 0 9/5
X1, X2 ≥ 0
E2 0 0 1 1 1 -1 1
• The artificial model:
Min z = 4 X1 + X2 + MA1 + MA2
s.t. Assume that the following constraints are added to the model.
3 X1 + X2 + A1 =3 x1 ≤ 4
4 X1 + 3 X2 – E2 + A2 = 6 -x1 + 2x2 ≥ 5
X1 + 2 X2 + S3 =4 3x1 – x2 = 10
Search the new optimal solution.
X1, X2, E2, S3, A1, A2 ≥ 0
• The optimal Simplex Tableau is given as;
 EXAMPLE 3
• The artificial model:
Min z = 4 X1 + X2 + MA1 + MA2 Assume that the following constraints are added to the mod
s.t. x1 ≤ 4
3 X1 + X2 + A1 =3 -x1 + 2x2 ≥ 5
4 X1 + 3 X2 – E2 + A2 = 6 3x1 – x2 = 10
X1 + 2 X2 + S3 =4 Search the new optimal solution.
• x1 ≤ 4
• -x1 + 2x2 ≥ 5
• 3x1 – x2 = 10

X1, X2, E2, S3, A1, A2 ≥ 0

• The optimal Simplex Tableau is given as;
 EXAMPLE 3
• The artificial model:
Min z = 4 X1 + X2 + MA1 + MA2 Assume that the following constraints are added to the mod
s.t. x1 ≤ 4
3 X1 + X2 + A1 =3 -x1 + 2x2 ≥ 5
4 X1 + 3 X2 – E2 + A2 = 6 3x1 – x2 = 10
X1 + 2 X2 + S3 =4 Search the new optimal solution.
• X1 + S4 = 4
• x1 - 2x2 + S5 = -5
• 3x1 – x2 >= 10
• 3x1 – x2 <= 10

X1, X2, E2, S3, A1, A2 ≥ 0

• The optimal Simplex Tableau is given as;
 EXAMPLE 3
• The artificial model:
Min z = 4 X1 + X2 + MA1 + MA2 Assume that the following constraints are added to the mod
s.t. x1 ≤ 4
3 X1 + X2 + A1 =3 -x1 + 2x2 ≥ 5
4 X1 + 3 X2 – E2 + A2 = 6 3x1 – x2 = 10
X1 + 2 X2 + S3 =4 Search the new optimal solution.
• X1 + S4 = 4
• x1 - 2x2 + S5 = -5
• -3x1 +x2 +S6 = -10
• 3x1 – x2 +S7 = 10

X1, X2, E2, S3, A1, A2 ≥ 0

• The optimal Simplex Tableau is given as;
• x1 ≤ 4
EXAMPLE 3
• x1 - 2x2 ≤ -5
• 3x1 – x2 ≤ 10
• -3x1 + x2 ≤ -10 Basis X1 X2 E2 S3 A1 A2 S4 S5 S6 S7 RHS

Min Z 0 0 0 -1/5 (7/5-M) -M 0 0 0 0 17/5

• Then we will add a slack variable to each of
these X1 1 0 0 -1/5 2/5 0 0 0 0 0 2/5

new constraints and we will write them in “=” X2 0 1 0 3/5 -1/5 0 0 0 0 0 9/5
form.
E2 0 0 1 1 1 -1 0 0 0 0 1
x1 + S4 =4
x1 - 2x2 + S5 = -5 S4 1 0 0 0 0 0 1 0 0 0 4

3x1 – x2 + S6 = 10 S5 1 -2 0 0 0 0 0 1 0 0 -5
-3x1 + x2 + S7 = -10
S6 3 -1 0 0 0 0 0 0 1 0 10

S7 -3 1 0 0 0 0 0 0 0 1 -10
• Now these new constraints and new slack
variables can be added to the above old
Simplex Tableau.
 EXAMPLE 3
Basis X1 X2 E2 S3 A1 A2 S4 S5 S6 S7 RHS Basis X1 X2 E2 S3 S4 S5 S6 S7 RHS

(7/5-
Min Z 0 0 0 -1/5 -M 0 0 0 0 17/5 Min Z 0 0 0 -1/5 0 0 0 0 17/5
M)

X1 1 0 0 -1/5 2/5 0 0 0 0 0 2/5 X1 1 0 0 -1/5 0 0 0 0 2/5

X2 0 1 0 3/5 -1/5 0 0 0 0 0 9/5 X2 0 1 0 3/5 0 0 0 0 9/5

E2 0 0 1 1 1 -1 0 0 0 0 1 E2 0 0 1 1 0 0 0 0 1

S4 1 0 0 0 0 0 1 0 0 0 4 S4 1 0 0 0 1 0 0 0 4

S5 1 -2 0 0 0 0 0 1 0 0 -5 S5 1 -2 0 0 0 1 0 0 -5

S6 3 -1 0 0 0 0 0 0 1 0 10 S6 3 -1 0 0 0 0 1 0 10

S7 -3 1 0 0 0 0 0 0 0 1 -10 S7 -3 1 0 0 0 0 0 1 -10
 EXAMPLE 3
Basis X1 X2 E2 S3 S4 S5 S6 S7 RHS Basis X1 X2 E2 S3 S4 S5 S6 S7 RHS

Min Z 0 0 0 0 0 0 0 -1/6 31/6

Min Z 0 0 0 -1/5 0 0 0 0 17/5
X1 1 0 0 0 0 0 0 -1/6 13/6
X1 1 0 0 -1/5 0 0 0 0 2/5
X2 0 1 0 0 0 0 0 1/2 -21/6

X2 0 1 0 3/5 0 0 0 0 9/5 E2 0 0 1 0 0 0 0 5/6 -47/6

E2 0 0 1 1 0 0 0 0 1 S4 0 0 0 0 1 0 0 1/6 11/6

S5 0 0 0 0 0 1 0 7/6 -85/6
S4 0 0 0 1/5 1 0 0 0 18/5
S6 0 0 0 0 0 0 1 1 0

S5 0 0 0 7/5 0 1 0 0 -9/5
S3 0 0 0 1 0 0 0 -5/6 53/6

S6 0 0 0 6/5 0 0 1 0 53/5
We fail to apply MRT. There is no entering
S7 0 0 0 -6/5 0 0 0 1 -53/5 variable. Hence, answer of the model with the
new constraints is INFEASIBLE SOLUTION. STOP.
 EXAMPLE 4
Consider the following original LP model. The standard form of this model is given below.

Max z = 2X1 – 2X2 + X3 + 3X4 Max z = 2X1 – 2X2 + X3 + 3X4

s.t. s.t.
2X2 + X3 + X4 ≤ 80 2X2 + X3 + X4 + S1 = 80
2X1 + X2 - X3 ≤ 60 2X1 + X2 - X3 + S2 = 60
X1, X2, X3, X4 ≥ 0 X1, X2, X3, X4, S1, S2 ≥ 0

The following Simplex Tableau shows the optimal solution of the above model.
Assume that the constraint “X1 - 2X2 ≤ 20” is
added to the above model. Update the
Basic X1 X2 X3 X4 S1 S2 RHS
above optimal Simplex Tableau and find the
Z 0 9 1 0 3 1 300 new optimal solution by the Dual Simplex
Algorithm. Write your conclusion such as
X4 0 2 1 1 1 0 80
“optimal solution”, “unbounded solution” or
X1 1 1/2 -1/2 0 0 1/2 30 “infeasible solution”.
 EXAMPLE 4
S3
Basi Basic X1 X2 X3 X4 S1 S2 S3 RHS
X1 X2 X3 X4 S1 S2 RHS
c
0 Z 0 9 1 0 3 1 0 300
Z 0 9 1 0 3 1 300

X4 0 2 1 1 1 0
0
80
X4 0 2 1 1 1 0 0 80

X1 1 1/2 -1/2 0 0 1/2

0
30 X1 1 1/2 -1/2 0 0 1/2 0 30
1 S3 0 -5/2 1/2 0 0 -1/2 1 -10
S3 1 -2 0 0 0 0 20

Basic X1 X2 X3 X4 S1 S2 S3 RHS

Z 0 4 2 0 3 0 2 280

X4 0 2 1 1 1 0 0 80

X1 1 -2 0 0 0 0 1 20

S2 0 5 -1 0 0 1 -2 20
 EXAMPLE 5
Consider the following original LP model. The standard form of this model is given below.

Max z = 2X1 – 2X2 + X3 + 3X4 Max z = 2X1 – 2X2 + X3 + 3X4

s.t. s.t.
2X2 + X3 + X4 ≤ 80 2X2 + X3 + X4 + S1 = 80
2X1 + X2 - X3 ≤ 60 2X1 + X2 - X3 + S2 = 60
X1, X2, X3, X4 ≥ 0 X1, X2, X3, X4, S1, S2 ≥ 0

The following Simplex Tableau shows the optimal solution of the Assume that the constraint
above model.
“2X1 – X4 = 20” is added to the above model.
Basic X1 X2 X3 X4 S1 S2 RHS
Update the above optimal Simplex Tableau and
Z 0 9 1 0 3 1 300
find the new optimal solution by the Dual
Simplex Algorithm. Write your conclusion such
X4 0 2 1 1 1 0 80
as “optimal solution”, “unbounded solution” or
X1 1 1/2 -1/2 0 0 1/2 30 “infeasible solution”.
 EXAMPLE 5
Basic X1 X2 X3 X4 S1 S2 RHS

Z 0 9 1 0 3 1 300

X4 0 2 1 1 1 0 80

X1 1 1/2 -1/2 0 0 1/2 30

S3 S4 TAKE HOME
Basi
X1 X2 X3 X4 S1 S2 RHS
c

0 0
Z 0 9 1 0 3 1 300

0 0
X4 0 2 1 1 1 0 80

0 0
X1 1 1/2 -1/2 0 0 1/2 30

1 0
S3 2 0 0 -1 0 0 20

0 1
S4 -2 0 0 1 0 0 -20
DUAL SIMPLEX EXAMPLE

S1 S2 S3

S1
S2
S3
DUAL SIMPLEX EXAMPLE
S1 S2 S3

S1
S2
S3

S2
 DUAL SIMPLEX EXAMPLE
S1 S2 S3

S1
S2
S3

S1 S2 S3

S1

S3
 DUAL SIMPLEX EXAMPLE
S1 S2 S3

S1

S3

S1 S2 S3

S3
DUAL SIMPLEX EXAMPLE

New Constraint:

3x1+x2+x3 ≤ 500
 HOMEWORK
Solve the following problem with Dual Simplex Algorithm
 Bahçeşehir Cyprus University
DEPARTMENT OF INDUSTRIAL ENGINEERING
OPERATIONS RESEARCH II
INE 3201
In a Simplex Table if :
✓ The optimality condition is satisfied (i.e., ZCi values of all non-basic decision variables are
non-positive (<=0) in a minimization problem, non-negative (>=0) in a maximization problem)
X but feasibility condition is violated (i.e., there are basic decision variables with negative values)

➢ we may use the Dual Simplex Algorithm.

➢ These solutions are called “dual feasible solution”.
➢ We may have such a Simplex Table if some new constraints are added to the model and the
optimal Simplex table of the old model is updated according to the new constraints.
Dual Simplex Rules:
➢ In order to add this constraint to the Simplex Table it should be transformed to the equality type
by adding a new slack variable.
➢ If the new constraint type is (>=0) type, multiply it by (-1) to avoid artificial variables.
➢ The new slack variable is added to the Basis as a basic solutions, then the Table should be
updated and transformed to a SIMPLEX TABLE by row operations.
➢ Row operations are the same as in the Simplex method.
Contrary to simplex method, the leaving variable is defined first, and then the entering one as
follows:
➢ Leaving variable : the one with negative RHS
➢ Entering variable: the one with the smallest MRT
The MRT for the Dual Simplex = (Z row )/ leaving variable row
 Example 1: Dual Simplex Algorithm

The following Simplex Table shows the Optimal Solution of the

below model where:
S1 is the slack variable added to the first constraint.
S2 is the slack variable added to the second constraint.

max Z = x1+2*x2+6*x3
S.T
2*x1+x2 + x3 <=10
Basic X1 X2 X3 S1 S2 RHS
-x2 +x3 <=4
X1,X2,X3 >=0 Z 7 0 0 4 2 48
X2 1 1 0 1/2 - 1/2 3
X3 1 0 1 1/2 1/2 7

Question:
Assume that the constraint “ –x1+2x2>=8” is added to the above model.
Find the new optimal solution By the Dual Simplex Algorithm.
Optimal solution before adding
the new constraint
Optimal solution after adding the
new constraint
Ex 2
• Dyal simplex 2 variables
• 3 cases
• A no change redundant cont
• B FSS changes but not the OS
• C FSS changes and the OS changes
• D FSS changes infeasible