Chapter 3

Analytic Solution of Linear programming

Problems
Artificial Starting Solution for the Primal Simplex Method:
Consider the following Problem: 𝑛

max 𝑧 = ෍ 𝑐𝑖 𝑥𝑗
𝑗=1 (1)
Subject to:
σ𝑛𝑗=1 𝑎𝑖𝑗 𝑥𝑗 ≥ 𝑏𝑖 , 𝑖 = 1,2, … , 𝑚, 𝑥𝑗 ≥ 0.
To solve this problem, we put it in the standard
𝑛
form
max 𝑧 = ෍ 𝑐𝑖 𝑥𝑗
𝑗=1 (2)
Subject to:
σ𝑛𝑗=1 𝑎𝑖𝑗 𝑥𝑗 − 𝑆𝑖 = 𝑏𝑖 , 𝑖 = 1,2, … , 𝑚, 𝑥𝑗 , 𝑆𝑖 ≥ 0.
Where 𝑆𝑖 are surplus variables.
Since these constraints have no slack variables, then we add artificial variables
and we have
𝑛

max 𝑧 = ෍ 𝑐𝑖 𝑥𝑗
𝑗=1 (3)
Subject to:
σ𝑛𝑗=1 𝑎𝑖𝑗 𝑥𝑗 − 𝑆𝑖 + 𝑅𝑖 = 𝑏𝑖 , 𝑖 = 1,2, … , 𝑚, 𝑥𝑗 , 𝑆𝑖 , 𝑅𝑖 ≥ 0.
Where 𝑅𝑖 are artificial variables, we use it to start the solution.
(𝑅𝑖 basic variables)

We solve the problem (3) by two methods:

1- The m-technique (Method of Penalty).
2- The Two-phase Technique.
1- M- Technique:
If some of the constraints in the linear programming problems are of the
type ( > ) or ( = ), we have to use the M- technique for maximization as
well as minimization of an objective function.

The steps of the M-technique are given below:

-We can penalize 𝑅𝑖 in the objective function by assigning them very
large positive coefficients in the objective function.
-Let 𝑀 > 0 be very large constant, the problem (3) with its artificial
variable becomes:
Solve the modified linear programming problem by simplex method.
Note: If the problem is min 𝑍 then it takes the following form
The first and second equations do not have variables that play the role of
a slack. Hence, we augment the two artificial variables 𝑅1 and 𝑅2 in the
two equations as follows:

Let 𝑀 > 0 be a very large constant, then the Linear programming with its
artificial variables becomes
min 𝑍 = 4𝑥1 + 𝑥2 + 𝑀(𝑅1 + 𝑅2 )
subject to
 𝑅1 + 𝑅2 = 9 − 7𝑥1 − 4𝑥2 + 𝑆2
We substitute out 𝑅1 and 𝑅2 in the objective function, then it becomes

𝑍 = 4𝑥1 + 𝑥2 + 𝑀(9 − 7𝑥1 − 4𝑥2 + 𝑆2 )

= 4 − 7𝑀 𝑥1 + 1 − 4𝑀 𝑥2 + 𝑀𝑆2 + 9𝑀
and the Z-equation now appears in the tableau as

𝑍 − 4 − 7𝑀 𝑥1 − 1 − 4𝑀 𝑥2 − 𝑀𝑆2 = 9𝑀
subject to
 2 9 17
The optimal solution is 𝑥1 = , 𝑥2 = , 𝑥3 = 1 and 𝑍 =
5 5 5
2-The Two-Phase technique:
Phase I: (works to achieve feasibility)
Let us consider the following linear programs:

subject to

(𝑀 is the feasible region)

and
To put the linear program 𝐿′ in the canonical form, 𝑟 must be represented
in terms of the non-basic variables in the form

with this form of 𝑟, the linear program 𝐿′ can be solved using the rules of
the simplex method.
In phase I after using the optimality conditions:
1. If min 𝑟 > 0, then 𝑀 = ∅ and the original problem is non-feasible.
2. If min 𝑟 = 0, then 𝑀 ≠ ∅, then convert to phase II.
Phase II: (works to achieve optimality)
and to start phase II with an objective 𝑍, we must do the following:
1. Cancel the 𝑟-row.
2. Cancel the columns of the non-basic artificial variables.
3. If at the end of phase I with min 𝑟 = 0, one of the artificial variables
remains as basic variable, then it must assume zero value and, in this
case, to start phase II we must cancel the row of this artificial
variables.
Apply the usual rules of the simplex method on the obtained table in
phase II.
Note: If the problem is m𝑎𝑥 𝑍 then it takes the following form

𝑚𝑎𝑥 𝑟 = − ෍ 𝑅𝑖
𝑖=1
Because 𝑅1 and 𝑅2 are in the starting solutions, they must be substituted
out in the objective function as follows:

𝑟 = 𝑅1 + 𝑅2 = 3 − 3𝑥1 − 𝑥2 + 6 − 4𝑥1 − 3𝑥2 + 𝑥3

𝑟 = −7𝑥1 − 4𝑥2 + 𝑥3 + 9
𝑟 + 7𝑥1 + 4𝑥2 − 𝑥3 = 9
r
r

r
From the previous constraints we have:
3 1
𝑥1 = − 𝑥3
5 5
6 3
𝑥2 = + 𝑥3
5 5
Substitute in the objective function:
3 1 6 3
min 𝑍 = 4 − 𝑥3 + + 𝑥3
5 5 5 5

1 18
min 𝑍 = − 𝑥3 +
5 5
 1 18 1 18
min 𝑍 = − 𝑥3 + 𝑍 + 𝑥3 =
5 5 5 5
 𝑥3 𝑥1 𝑥𝟐 𝑥𝟒 𝑠𝑜𝑙.
𝑍 1 0 0 0 18
5 5
𝑥1 1 1 0 0 3
5 5
𝑥2 3 0 1 0 6
−
5 5
𝑥4 1 0 0 1 1

𝑥3 𝑥1 𝑥𝟐 𝑥𝟒 𝑠𝑜𝑙.
𝑍 0 0 0 1 17
−
5 5
𝑥1 0 1 0 1 2
5 5
𝑥2 0 0 1 3 9
−
5 5
𝑥3 1 0 0 1 1

2 9 17
The optimal solution is 𝑥1 = , 𝑥2 = , 𝑥3 = 1 and 𝑍 =
5 5 5