Numerical Methods for Optimization

8. Linear Programming: towards the algebraic solution

Content

¨ Example
¨ Equivalent forms
 Observations

Due to the fundamental theorem of Linear Programming, to solve any LP it

‘suffices’ to consider the vertices (finitely many) of the polyhedron P of the
feasible solutions.

Since the geometrical definition of vertex cannot be exploited algorithmically, we

we move towards and an algebraic characterization
8.1 Example
Rappresentazione grafica
min z = -3x1 - 5x2 8

s.t. 7
x2

x1 + x2 ≤ 12 6
x1 + 2x2 ≤ 16
5
x1 ≤ 10
x2 ≤ 6 4

3
x1, x2 ≥ 0
2

0
x1
-1
-1 0 1 2 3 4 5 6 7 8 9 10 11

Figura: Regione ammissibile

 Example
Rappresentazione grafica
min z = -3x1 - 5x2 8

s.t. 7
x2

x1 + x2 ≤ 12 (I) (IV)
6
x1 + 2x2 ≤ 16 (II)
x1 ≤ 10 (III)
5
(II)
x2 ≤ 6 (IV) 4

3
(I)
x1, x2 ≥ 0
2

1
(III)
0
x1
-1
-1 0 1 2 3 4 5 6 7 8 9 10 11
A vertex corresponds to the Figura: Regione ammissibile
intersection of the hyperplanes
associated to n=2 inequalities.
 Example: towards the algebraic solution

(P)
min z = -3x1 - 5x2
s.t.
x1 + x2 ≤ 12
x1 + 2x2 ≤ 16
x1 ≤ 10
Rappresentazione grafica
x2 ≤ 6
x1, x2 ≥ 0 8
x2
7

0
x1
-1
-1 0 1 2 3 4 5 6 7 8 9 10 11

Figura: Regione ammissibile

 Example: towards the algebraic solution

(P) (P’)
min z = -3x1 - 5x2 min z = -3x1 + 5x2 +0s1 +0s2 +0s3 +0s4
s.t. s.t.
x1 + x2 ≤ 12 x1 + x2 + s1= 12
x1 + 2x2 ≤ 16 x1 + 2x2 + s2 = 16
x1 ≤ 10 x 1 + s3 = 10
Add slack x 2 + s4 = 6
x2 ≤ 6
variables Rappresentazione grafica
x1, x2 ≥ 0 x1, x2 s1, s2,s3,s4 ≥ 0
8
x2
Observation
7

6
Every constraint in P corresponds to a variable in P’,
5
when the variable is set to 0 the constraint is satisfied
4
with = in P. 3

Vertex of P is the intersection of n=2 1

inequalities in P’ º setting the corresponding 0

x1
slack variables in P’ to 0 -1
-1 0 1 2 3 4 5 6 7 8 9 10 11

Figura: Regione ammissibile

 Example: towards the algebraic solution
Rappresentazione grafica Ola
(P’)
min z = -3x1 - 5x2 +0s1 +0s2 +0s3 +0s4
s.t.
12
x1 + x2 + s1= 12
11
x1 + 2x2 + s2 = 16
10
x1 + s3 = 10 x2
9
x 2 + s4 = 6
8
x1, x2 s1, s2,s3,s4 ≥ 0 7

0
x1
-1
-1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Figura: Regione ammissibile

 Example: towards the algebraic solution
(P’)
min z = -3x1 + 5x2 +0s1 +0s2 +0s3 +0s4
s.t. (x1, x2, s1, s2, s3, s4)
x1 + x2 + s1= 12 1) (0,0,12,16,10,6)
x1 + 2x2 + s2 = 16 2) (0,6,6,4,10,0)
x 1 + s3 = 10 3) (0,8,4, 0,10,-2)
Rappresentazione
x 2 + s4 = 6 grafica Ola 4) (0,12,0,-8,10,-6)
x1, x2, s1,s2,s3,s4 ≥ 0 5) (4,6,2,0,4,0)
6) (8,4,0,0,2,2)
12
7) …
11
4)
10
x2
9

8 3)
7
7) 8)
6

2)
5
5)
11)
4

3
6)
2
10)
1
1) 12) 13)
0 9)
x1
-1
-1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Figura: Regione ammissibile

 Example: towards the algebraic solution
(P’)
min z = -3x1 + 5x2 +0s1 +0s2 +0s3 +0s4
(x1, x2, s1, s2, s3,
s.t. s4)
x1 + x2 + s1= 12 1) (0,0,12,16,10,6)
x1 + 2x2 + s2 = 16 2) (0,6,6,4,10,0)
x 1 + s3 = 10
Rappresentazione grafica Ola 3) (0,8,4, 0,10,-2)
x 2 + s4 = 6
4) (0,12,0,-8,10,-6)
x1, x2 s1, s2,s3,s4 ≥ 0
5) (4,6,2,0,4,0)
12 6) (8,4,0,0,2,2)
11
4)
10
x2
9
Idea: choose an initial vertex and
8 3) move to a feasible neighboring
7
7) 8) vertex that will improve the
6

2) solution.
5
5)
For example: vertex 1) and 5) are
11)
4

3
6) feasible neighbors of vertex 2)
2
10)
1
1) 12) 13)
0 9)
x1
-1
-1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Figura: Regione ammissibile

 Example: Initial solution
(P’)
min z = -3x1 - 5x2 +0s1 +0s2 +0s3 +0s4
s.t.
x1 + x2 + s1= 12
x1 + 2x2 + s2 = 16
x 1 + s3 = 10
x 2 + s4 = 6
x1, x2,s1,s2,s3,s4 ≥ 0
 Example: Initial solution
(P’)
min z = -3x1 - 5x2 +0s1 +0s2 +0s3 +0s4
s.t.
x1 + x2 + s1= 12
x1 + 2x2 + s2 = 16
x 1 + s3 = 10
x 2 + s4 = 6
x1, x2,s1,s2,s3,s4 ≥ 0
 Example: Initial solution

(P’)
min -z + -3x1 - 5x2 +0s1 +0s2 +0s3 +0s4=0
s.t. Suppose we start from the initial
x1 + x2 + s1=12 solution (0,0,12,16,10,6) with z=0.
x1 + 2x2 + s2 = 16 The equations are said to be in
canonical form.
x 1 + s3 = 10
x 2 + s4 = 6
x1, x2,s1,s2,s3,s4 ≥ 0

x1 currently has a value of zero, however, it has a negative coefficient in the objective function
(while the coefficients of s1, s2, s3, s4 are zero), it appears promising to increase the value of x1
as much as possible. Considering x2 = 0, we have
x1 + x2 + s1= 12 (x2 = 0) x1 + s1= 12
x1 + 2x2 + s2 = 16 (x2 = 0) x1 + s2 = 16
x 1 + s3 = 10 (x2 = 0) x1 + s3 = 10
x 2 + s4 = 6 (x2 = 0) s4 = 6
The maximum possible increase in x1 while ensuring that s1, s2 , s3, s4 ≥0 is min={12,16,10,-}
= 10. Thus, x1 should be set to 10 and as a consequence s3 = 0 and x2 = 0
3/34
 Example continued: reproduce the new solution
(canonical form)
Convert the system (I-IV) to a conical system (I’-IV’) in (x1,s1,s2,s4)
min–z + -3x1 - 5x2 +0s1 +0s2 +0s3 +0s4=0
Step 1: x1 has to have a coefficient of 1 in (III)
s.t.
(I) 1x1 + 1x2 + 1s1=12 (III’=II/1)
(II) 1x1 + 2x2 + 1s2 = 16 (III’) 1x1 + 0x2 + 0s1 + 0s2 + 1s3 + 0s4 = 10
(III) 1x1 + s3 = 10
(IV) 1x2 + s4 = 6 Step 2: x1 has to have a coefficient of 0 in (I’)
x1, x2,s1,s2,s3,s4 ≥ 0 (I’=I –1III’)
(I’) 0x1 + 1x2 + 1s1 + 0s2 -1s3 + 0s4 = 2
Step 3: x1 has to have a coefficient of 0 in (II’)
(II’=II –1III’)
(II’) 0x1 + 2x2 + 0s1 + 1s2 -1s3 + 0s4 = 6

Step 4: x1 has to have a coefficient of 0 in (IV’)

(IV’=IV –1III’)
(IV’) 0x1 + 1x2 + 0s1 + 0s2 +0s3 + 1s4 = 6
 Example continued: reproduce the new solution
(canonical form)
Convert the system (I-IV) to a conical system (I’-IV’) in (x1,s1, s2,s4)
min (obj) –z + -3x1 - 5x2 +0s1 +0s2 +0s3 +0s4 =0
s.t.
(I) 1x1 + 1x2 + 1s1=12
(II) 1x1 + 2x2 + 1s2 = 16
(III) 1x1 + s3 = 10
(IV) 1x2 + s4 = 6
x1, x2,s1,s2,s3,s4 ≥ 0

x1 has to have a coefficient of 0 in the objective Step 5:(obj’=obj - -3III’)

(obj’) 0x1 + -5x2 + 0s1 + 0s2 +3s3 + 0s4 = 30
 Example continued: reproduce the new solution
(canonical form)
Putting obj’ and (I’-IV’) we get
min (obj) -z + 0x1 + -5x2 + 0s1 + 0s2 +3s3 + 0s4 = 30
s.t.
0x1 + 1x2 + 1s1 + 0s2 -1s3 + 0s4 = 2
0x1 + 2x2 + 0s1 + 1s2 -1s3 + 0s4 = 6
1x1 + 0x2 + 0s1 + 0s2 + 1s3 + 0s4 = 10 Current solution (0,2,6,10,0,6) with
0x1 + 1x2 + 0s1 + 0s2 +0s3 + 1s4 = 6 z=-30.
x1, x2,s1,s2,s3,s4 ≥ 0 The equations are said to be in
canonical form.
 Example continued: reproduce the new solution
(canonical form)
Putting obj’ and (I’-IV’) we get
min (obj) -z + 0x1 + -5x2 + 0s1 + 0s2 +3s3 + 0s4 = 30
s.t.
0x1 + 1x2 + 1s1 + 0s2 -1s3 + 0s4 = 2
0x1 + 2x2 + 0s1 + 1s2 -1s3 + 0s4 = 6
1x1 + 0x2 + 0s1 + 0s2 + 1s3 + 0s4 = 10
0x1 + 1x2 + 0s1 + 0s2 +0s3 + 1s4 = 6
x1, x2,s1,s2,s3,s4 ≥ 0
 Example continued: second iteration

Putting obj’ and (I’-IV’) we get

(P’)
min (obj) -z + 0x1 + -5x2 + 0s1 + 0s2 +3s3 + 0s4 = 30
s.t.
0x1 + 1x2 + 1s1 + 0s2 -1s3 + 0s4 = 2
0x1 + 2x2 + 0s1 + 1s2 -1s3 + 0s4 = 6
1x1 + 0x2 + 0s1 + 0s2 + 1s3 + 0s4 = 10
0x1 + 1x2 + 0s1 + 0s2 +0s3 + 1s4 = 6
x1, x2,s1, s2,s3,s4 ≥ 0
x2 currently has a value of zero, however, it has a negative coefficient in the objective function
(while the coefficients of x1, s1, s2, s4 are zero), it appears promising to increase the value of x2
as much as possible. Considering s3 = 0, we have
0x1 + 1x2 + 1s1 + 0s2 -1s3 + 0s4 = 2 (s3 = 0) x2 + s1= 2
0x1 + 2x2 + 0s1 + 1s2 -1s3 + 0s4 = 6 (s3 = 0) 2x2 + s2 = 6
1x1 + 0x2 + 0s1 + 0s2 + 1s3 + 0s4 = 10 (s3 = 0) 1x1 + 0x2 = 10
0x1 + 1x2 + 0s1 + 0s2 +0s3 + 1s4 = 6 (s3 = 0) x 2 + s4 = 6
The maximum possible increase in x2 while ensuring that s1, s2 , x1, s4 ≥0 is min={2,6/2, ,6}=2.
Thus, x2 should be set to 2 and as a consequence s1 = 0 and s3 = 0
 Example continued: reproduce the new solution
(canonical form)
Convert the system (I-IV) to a conical system (I’-IV’) in (x1,x2,s2,s4)

min (obj) z = 0x1 + -5x2 + 0s1 + 0s2 +3s3 + 0s4 = 30

(I) 0x1 + 1x2 + 1s1 + 0s2 -1s3 + 0s4 = 2
(II) 0x1 + 2x2 + 0s1 + 1s2 -1s3 + 0s4 = 6
(III) 1x1 + 0x2 + 0s1 + 0s2 + 1s3 + 0s4 = 10
(IV) 0x1 + 1x2 + 0s1 + 0s2 +0s3 + 1s4 = 6

x1, x2,s1, s2,s3,s4 ≥ 0 Step 1 (I’=I/1)

(I’) 0x1 + 1x2 + 1s1 + 0s2 + -s3 + 0s4 = 2
Step 2 (II’=II –2I’)
(II’) 0x1 + 0x2 + -2s1 + 1s2 +1s3 + 0s4 = 2
Step 3: (III’=III –0I’)
(III’) 1x1 + 0x2 + 0s1 + 0s2 +1s3 + 0s4 = 10

Step 4 (IV’=IV –1I’)

(IV’) 0x1 + 0x2 - 1s1 + 0s2 +1s3 + 1s4 = 4
 Example continued: reproduce the new solution
(canonical form)
Convert the system (I-IV) to a conical system (I’-IV’) in (x1,s1, s2,s4)
min (obj) -z + 0x1 + -5x2 + 0s1 + 0s2 +3s3 + 0s4 = 30
(I) 0x1 + 1x2 + 1s1 + 0s2 -1s3 + 0s4 = 2
(II) 0x1 + 2x2 + 0s1 + 1s2 -1s3 + 0s4 = 6
(III) 1x1 + 0x2 + 0s1 + 0s2 + 1s3 + 0s4 = 10
(IV) 0x1 + 1x2 + 0s1 + 0s2 +0s3 + 1s4 = 6
x1, x2,s1,s2,s3,s4 ≥ 0

x2 has to have a coefficient of 0 in the objective Step 5:(obj’=obj - -5III’)

(obj’) 0x1 + 0x2 + 5s1 + 0s2 -2s3 + 0s4 = 40
 Example continued: reproduce the new solution
(canonical form)
Putting obj’ and (I’-IV’) we get
min -z+0x1 + 0x2 + 5s1 + 0s2 -2s3 + 0s4 = 40
s.t. Current solution (10,2,0,2,0,4) with
0x1 + 1x2 + 1s1 + 0s2 -s3 + 0s4 = 2 z=-40.
0x1 + 0x2 -2s1 + 1s2 +1s3 + 0s4 = 2 The equations are said to be in
1x1 + 0x2 + 0s1 + 0s2 +1s3 + 0s4 = 10 canonical form.
0x1 + 0x2 - 1s1 + 0s2 +1s3 + 1s4 = 4
x1, x2,s1,s2,s3,s4 ≥ 0
 Example continued: third iteration

Putting obj’ and (I’-IV’) we get

min -z+0x1 + 0x2 + 5s1 + 0s2 -2s3 + 0s4 = 40
s.t.
0x1 + 1x2 + 1s1 + 0s2 -s3 + 0s4 = 2
0x1 + 0x2 -2s1 + 1s2 +1s3 + 0s4 = 2
1x1 + 0x2 + 0s1 + 0s2 +1s3 + 0s4 = 10
0x1 + 0x2 - 1s1 + 0s2 +1s3 + 1s4 = 4
x1, x2,s1,s2,s3,s4 ≥ 0

s3 currently has a value of zero, however, it has a negative coefficient in the objective function
it appears promising to increase the value of s3 as much as possible. Considering s3 = 0, we
have
0x1 + 1x2 + 1s1 + 0s2 -s3 + 0s4 = 2 (s1 = 0) 1x2 -s3 = 2 (not binding)
0x1 + 0x2 -2s1 + 1s2 +1s3 + 0s4 =2 (s1 = 0) 1s2 +1s3 =2
1x1 + 0x2 + 0s1 + 0s2 +1s3 + 0s4 = 10 (s1 = 0) 1x1 + 1s3 = 10
0x1 + 0x2 - 1s1 + 0s2 +1s3 + 1s4 = 4 (s1 = 0) 1s3 + s4 = 4
The maximum possible increase in x2 while ensuring that s1, s2 , x1, s4 ≥0 is min={-,2,
10,4}=2. Thus, s3 should be set to 2 and as a consequence s2 = 0 and s3 = 0
 Example continued: reproduce the new solution
(canonical form)
Putting obj’ and (I’-IV’) we get
min -z+0x1 + 0x2 + 5s1 + 0s2 -2s3 + 0s4 = 40
s.t.
0x1 + 1x2 + 1s1 + 0s2 -s3 + 0s4 = 2
0x1 + 0x2 -2s1 + 1s2 +1s3 + 0s4 = 2
1x1 + 0x2 + 0s1 + 0s2 +1s3 + 0s4 = 10
0x1 + 0x2 - 1s1 + 0s2 +1s3 + 1s4 = 4
x1, x2,s1,s2,s3,s4 ≥ 0
 Example continued: reproduce the new solution
(canonical form)
Convert the system (I-IV) to a conical system (I’-IV’) in (x1,x2,s2,s4)

min (obj) -z+0x1 + 0x2 + 5s1 + 0s2 -2s3 + 0s4 = 40

s.t.
(I) 0x1 + 1x2 + 1s1 + 0s2 -1s3 + 0s4 = 2
(II) 0x1 + 0x2 -2s1 + 1s2 +1s3 + 0s4 = 2
(III)1x1 + 0x2 + 0s1 + 0s2 +1s3 + 0s4 = 10
(IV )0x1 + 0x2 - 1s1 + 0s2 +1s3 + 1s4 = 4
Step 1 (II’=I/1)
x1, x2,s1,s2,s3,s4 ≥ 0 (II’) 0x1 + 0x2 - 2s1 + 1s2 + 1s3 + 0s4 = 2
Step 2 (I’=II - -1I’)
(I’) 0x1 + 1x2 -1s1 + 1s2 +0s3 + 0s4 = 4
Step 3: (III’=III –1I’)
(III’) 1x1 + 0x2 + 2s1 -1s2 +0s3 + 0s4 = 8

Step 4 (IV’=IV –1I’)

(IV’) 0x1 + 0x2 +1s1 -1s2 +0s3 + 1s4 = 2
 Example continued: reproduce the new solution
(canonical form)
Convert the system (I-IV) to a conical system (I’-IV’) in (x1,x2, s4,s4)
min (obj) -z+0x1 + 0x2 + 5s1 + 0s2 -2s3 + 0s4 = 40
s.t.
(I) 0x1 + 1x2 + 1s1 + 0s2 -1s3 + 0s4 = 2
(II) 0x1 + 0x2 -2s1 + 1s2 +1s3 + 0s4 = 2
(III)1x1 + 0x2 + 0s1 + 0s2 +1s3 + 0s4 = 10
(IV )0x1 + 0x2 - 1s1 + 0s2 +1s3 + 1s4 = 4
x1, x2,s1,s2,s3,s4 ≥ 0

s3 has to have a coefficient of 0 in the objective

Step 5:(obj’=obj - -2III’)

(obj’) 0x1 + 0x2 + 1s1 + 2s2 +0s3 + 0s4 = 44
 Example continued: reproduce the new solution
(canonical form)
Putting obj’ and (I’-IV’) we get
min -z+ 0x1 + 0x2 + 1s1 + 2s2 +0s3 + 0s4 = 44
s.t.
0x1 + 1x2 -1s1 + 1s2 +0s3 + 0s4 = 4
0x1 + 0x2 - 2s1 + 1s2 + 1s3 + 0s4 = 2
1x1 + 0x2 + 2s1 -1s2 +0s3 + 0s4 = 8
0x1 + 0x2 +1s1 -1s2 +0s3 + 1s4 = 2
x1, x2,s1,s2,s3,s4 ≥ 0
 Example continued: reproduce the new solution
(canonical form)
Putting obj’ and (I’-IV’) we get
min -z+ 0x1 + 0x2 + 1s1 + 2s2 +0s3 + 0s4 = 44
s.t.
0x1 + 1x2 -1s1 + 1s2 +0s3 + 0s4 = 4
0x1 + 0x2 - 2s1 + 1s2 + 1s3 + 0s4 = 2
1x1 + 0x2 + 2s1 -1s2 +0s3 + 0s4 = 8
0x1 + 0x2 +1s1 -1s2 +0s3 + 1s4 = 2
x1, x2,s1,s2,s3,s4 ≥ 0
 Example: vertices
Rappresentazione grafica
min z = -3x1 + -5x2 8
s.t. x2
x1 + x2 ≤ 12 7
x1 + 2x2 ≤ 16
x1 ≤ 10 6
x2 ≤ 6
5
x1, x2 ≥ 0
4 (8,4) z=44

2
(10,2) z=40

0 (10,0) z=30
(0,0) z=0 x1
-1
-1 0 1 2 3 4 5 6 7 8 9 10 11

Figura: Regione ammissibile

 8.2 Equivalent forms

General from Definition: Standard form

min z = cTx
(max) min z = cTx
A1 x ≥ b1 Ax = b
A2 x ≤ b2 x≥0
A3 x = b3
xj ≥ 0 for j ∈ J ⊆{1,…, n}
xj free for j ∈ {1,…, n} \ J
Equivalent forms

¨ Simple transformation rules allow to pass form one form to

the other form
¨ The transformation may involve adding/deleting
variables and/or constraints
Transformation rules

¨ max cTx = - min - cTx

aTx + s = b
¨ aTx ≤ b ⇒
s≥0 slack variable

T
¨ a x ≥b ⇒ aTx - s = b
s≥0 surplus variable
Transformation rules

ì x j = x +j - x -j
xj unrestricted in sign ⇒ ï
¨
í x +
j
³0
ï x- ³ 0
î j

Note: after substituting xj with xj+– xj–, we delete xj from the problem.
 Equivalent forms: example

General form
max 2x1 – 3x2
s.t. 4x1 – 7x2 ≤ 5
6x1 – 2x2 ≥ 4 Step 1
x1 ≥ 0, x2 unrestricted x2 = x3 – x4
x 3, x 4 ≥ 0

max 2x1 – 3x3 + 3x4

s.t. 4x1 – 7x3 + 7x4 ≤ 5
6x1 – 2x3 + 2x4 ≥ 4
x 1, x 3, x 4 ≥ 0
 Equivalent forms

Step 2 : introduce slack and surplus variables x5 and x6

Step 3 : change the objective function sign

min -2x1 + 3x3 - 3x4

4x1 – 7x3 + 7x4 + x5 = 5
6x1 – 2x3 + 2x4 – x 6= 4
x 1, x 3, x 4 , x 5, x 6 ≥ 0
Other transformations

a x ≤ b ® -a x ≥-b

a x ≥ b ® -a x ≤-b

ax ≥ b ax ≥ b
ax = b ® ®
ax ≤ b -a x ≥-b