Lec 05

-z x1 x2 x3 s1 s2 s3 x8 RHS Col Ratio
Pivot Pivot 1 5 4.5 6 0 0 0 0

Column Row 0 6 5 8 1 0 0 60 8 7.5
I 12 0 10 20 10 0 1 0 150 10 15
0 1 0 0 0 0 1 8 0 -
0 0 0 1 0 0 0
1 0.5 0.75 0 -0.75 0 0 -45

0 0.75 0.625 1 0.125 0 0 7.5 0 -
0 2.5 13.75 0 -1.25 1 0 75 0 -
0 1 0 0 0 0 1 8 0 -
0 0 0 0 0 0 0
0 -
0 -
0 -
0 0 0 0 0 0 0
0 -
0 -
0 -
0 0 0 0 0 0 0
0 -
0 -
0 -
0 0 0 0 0 0 0
0 -
0 -
0 -
0 0 0 0 0 0 0
0 -
0 -
0 -
0 0 0 0 0 0 0
0 -
0 -
0 -
0 0 1 0 0 0
0 0 0 0 0 ###
### 0
Hi, McGraph and I will be
1 helping out with carrying out
the big M method.
The original variables are x1 to

x4. The variables y1 to y3 are
2
artificial variables, which are
not part of the original problem.
You will notice that there is a

3 box with a "-5" in it to the right
of "M"
The value is stored as a penalty

for the artificial variables. If -M
4 is big enough, then each
artificial variable will be 0 in an
optimal solution.
It's clear that there will be a

basic feasible solution for this
5 problem with basic variables y1,
y2, and y3. But the tableau is
not in canonical form.
Now carry out the simplex

algorithm until you have an
6
optimal solution for this
problem.
If you did it correctly, you will

find that the artificial variable
7
y3 is basic in the optimal
solution.
Now continue the simplex

8 algorithm until you have a new
optimal solution.
9 That's it. Bye
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
J 5
K 6
L 7 2
M 8
N 9 4 2
0 0
P 11
###
###
###
###
###
###
###
###
###
###
###
###
###
###
###
###
To pivot, you just need to enter the
pivot column and the pivot row in
the boxes to the left of the tableau.
It's OK to have variables y1 to y3

show up in the tableaus. But they
need to be nonbasic variables in the
optimal solution if we want to solve
the original problem.
It's right above me.
It turns out that -5 is not small

enough. But don’t change the
value, until we say so.
So, carry out three pivots to get the

tableau with basic variables y1, y2,
y3 to be in canonical form. We
have already carried out the first
pivot for you.
Don't worry. This occurred because

the penalty was not big enough.
Change the value of M from -5 to -
10. You will notice that the last
tableau is no longer optimal.
If you did it correctly, the three

artificial variables will all be non-
basic, and thus they are 0 in the
bfs. This implies that the bfs is also
optimal for the original problem.
1 6 0 0
2 8 1 0.125
3 10 0 0 0 0.75 0.63 1 0.13 0.13 0 0 0 0
4 0 0 0
5
6
7 #N/A 0 0
8 #N/A 0 0
9 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
10 #N/A 0 0
11
12
13 #N/A 0 0
14 #N/A 0 0
15 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
16 #N/A 0 0
17
18
19 #N/A 0 0
20 #N/A 0 0
21 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
22 #N/A 0 0
23
24
25 #N/A 0 0
26 #N/A 0 0
27 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
28 #N/A 0 0
29
30
31 #N/A 0 0
32 #N/A 0 0
33 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
34 #N/A 0 0
35
36
37 #N/A 0 0
38 #N/A 0 0
39 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
40 #N/A 0 0
41
42
43 #N/A 0 0
44 #N/A 0 0
45 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
46 #N/A 0 0
47
48
49 #N/A 0 0
50 #N/A 0 0
51 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
52 #N/A 0 0
53
1 0.5 0.75 0 1.25 -0.8 0 0 0 0 -45
0 0.75 0.63 1 0.13 0.13 0 0 0 0 7.5
7.5 0 2.5 14 0 -1.3 -1.3 1 0 0 0 75
0 1 0 0 1 0 0 1 0 0 8
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0
-z x1 x2 x3 x4 s1 s2 s3 x8 RHS Col Ratio
Pivot Pivot 1 0.75 -20 0.5 -6 0 0 0 -3
Column Row 0 0.25 -8 -1 9 1 0 0 0 0.25 0
G 0 0.5 -12 -0.5 3 0 1 0 0 0.5 0
0 0 0 1 0 0 0 1 1 0 -
0 1 0 0 0 0 0 0
0 -
0 -
0 -
0 0 0 0 0 0 0 0
0 -
0 -
0 -
0 0 0 0 0 0 0 0
0 -
0 -
0 -
0 0 0 0 0 0 0 0
0 -
0 -
0 -
0 0 0 0 0 0 0 0
0 -
0 -
0 -
0 0 0 0 0 0 0 0
0 -
0 -
0 -
0 0 0 0 0 0 0 0
0 0 0 0 0 ###
### 0
Ratio Choose col with
largest reduced cost
Choose row according

to min ratio rule
In case of tie, choose

the first row.
Hi, this is an example of cycling
1
in the simplex method.
Each pivot satisfies the min

ratio rule, and the final tableau
2
is the same as the intial
tableau.
There is no problem to be
3
solved on this slide.
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
J 5
K 6
L 7 ###
M 8
N 9 2
0 0
P 11
###
###
###
###
###
###
###
###
###
###
###
###
###
###
###
###
Each pivot is degenerate. The bfs
is the same for all tableaus, even
though the tableaus are different.
You can go to Problem 4. Goodbye.

1 0.75 0 0
2 0.25 0 0
3 0.5 0 0 0 0 0 0 0 0 0 0 0 0
4 0 0 0
5
6
7 #N/A 0 0
8 #N/A 0 0
9 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
10 #N/A 0 0
11
12
13 #N/A 0 0
14 #N/A 0 0
15 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
16 #N/A 0 0
17
18
19 #N/A 0 0
20 #N/A 0 0
21 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
22 #N/A 0 0
23
24
25 #N/A 0 0
26 #N/A 0 0
27 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
28 #N/A 0 0
29
30
31 #N/A 0 0
32 #N/A 0 0
33 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
34 #N/A 0 0
35
36
37 #N/A 0 0
38 #N/A 0 0
39 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
40 #N/A 0 0
41
42
43 #N/A 0 0
44 #N/A 0 0
45 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
46 #N/A 0 0
47
48
49 #N/A 0 0
50 #N/A 0 0
51 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
52 #N/A 0 0
53
1 0.75 -20 0.5 -6 0 0 0 0 0 -3
0 0.25 -8 -1 9 1 0 0 0 0 0
0 0 0.5 -12 -0.5 3 0 1 0 0 0 0
0 0 0 1 0 0 0 1 0 0 1
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0
-z x1 x2 x3 x4 s1 s2 s3 x8 RHS Col Ratio
Pivot Pivot 1 0.75 -20 0.5 -6 0 0 0 -3
Column Row 0 0.25 -8 -1 9 1 0 0 0 0.25 0
G 0 0.5 -12 -0.5 3 0 1 0 0 0.5 0
0 0 0 1 0 0 0 1 1 0 -
0 1 0 0 0 0 0 0
0 -
0 -
0 -
0 0 0 0 0 0 0 0
0 -
0 -
0 -
0 0 0 0 0 0 0 0
0 -
0 -
0 -
0 0 0 0 0 0 0 0
0 -
0 -
0 -
0 0 0 0 0 0 0 0
0 -
0 -
0 -
0 0 0 0 0 0 0 0
0 -
0 -
0 -
0 0 0 0 0 0 0 0
0 0 0 0 0 ###
### 0
Ratio
Bland's rule
1. Pivot in the first eligible variable
2. Pivot out using the min ratio rule.
In case of ties, choose the row with least index.
Hi, this is an example of cycling
1
in the simplex method.
Each pivot satisfies the min

ratio rule, and the final tableau
2
is the same as the intial
tableau.
There is no problem to be
3
solved on this slide.
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
J 5
K 6
L 7 ###
M 8
N 9 2
0 0
P 11
###
###
###
###
###
###
###
###
###
###
###
###
###
###
###
###
Each pivot is degenerate. The bfs
is the same for all tableaus, even
though the tableaus are different.
You can go to Problem 4. Goodbye.

1 0.75 0 0
2 0.25 0 0
3 0.5 0 0 0 0 0 0 0 0 0 0 0 0
4 0 0 0
5
6
7 #N/A 0 0
8 #N/A 0 0
9 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
10 #N/A 0 0
11
12
13 #N/A 0 0
14 #N/A 0 0
15 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
16 #N/A 0 0
17
18
19 #N/A 0 0
20 #N/A 0 0
21 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
22 #N/A 0 0
23
24
25 #N/A 0 0
26 #N/A 0 0
27 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
28 #N/A 0 0
29
30
31 #N/A 0 0
32 #N/A 0 0
33 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
34 #N/A 0 0
35
36
37 #N/A 0 0
38 #N/A 0 0
39 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
40 #N/A 0 0
41
42
43 #N/A 0 0
44 #N/A 0 0
45 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
46 #N/A 0 0
47
48
49 #N/A 0 0
50 #N/A 0 0
51 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
52 #N/A 0 0
53
1 0.75 -20 0.5 -6 0 0 0 0 0 -3
0 0.25 -8 -1 9 1 0 0 0 0 0
0 0 0.5 -12 -0.5 3 0 1 0 0 0 0
0 0 0 1 0 0 0 1 0 0 1
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
-z x1 x2 x3 s1 s2 s3 x8 RHS
Pivot Pivot 1 5 4.5 6 0 0 0 0
Column Row 0 6 5 -8 1 0 0 15
I 14 0 -10 20 2 0 1 0 20
0 -1 0 1 0 0 1 2
1 11 4.5 0 0 0 -6 -12
0 -2 5 0 1 0 8 31
0 -8 20 0 0 1 -2 16
0 -1 0 1 0 0 1 2
0 0 0 0 0 ###
### 0
the big M method.

2

of "M"

optimal solution.


6
problem.

7
solution.

optimal solution.
9 That's it. Bye
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
J 5
K 6
L 7 4
M 8
N 9 4 4
0 0
P 11
###
###
###
###
###
###
###
###
###
###
###
###
###
###
###
###



pivot for you.


1 6 0 0
2 -8 0 0
3 2 0 0 0 -1 0 1 1 0 0 1 0 0
4 1 1 1
5
6
7 #N/A 0 0
8 #N/A 0 0
9 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
10 #N/A 0 0
11
12
13 #N/A 0 0
14 #N/A 0 0
15 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
16 #N/A 0 0
17
18
19 #N/A 0 0
20 #N/A 0 0
21 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
22 #N/A 0 0
23
24
25 #N/A 0 0
26 #N/A 0 0
27 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
28 #N/A 0 0
29
30
31 #N/A 0 0
32 #N/A 0 0
33 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
34 #N/A 0 0
35
36
37 #N/A 0 0
38 #N/A 0 0
39 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
40 #N/A 0 0
41
42
43 #N/A 0 0
44 #N/A 0 0
45 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
46 #N/A 0 0
47
48
49 #N/A 0 0
50 #N/A 0 0
51 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
52 #N/A 0 0
53
1 11 4.5 0 -4 0 0 -6 0 0 -12
0 -2 5 0 9 1 0 8 0 0 31
2 0 -8 20 0 -2 0 1 -2 0 0 16
0 -1 0 1 1 0 0 1 0 0 2
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
-z x1 x2 x3 x4 x5 ssx
38 RHS
Pivot Pivot 1 0 0 0 0 -1###
### -2
Column Row 0 0 2 1 0 -1###
### 4
H 14 0 0 -1 0 1 2 ###
### 1
0 1 6 0 0 3 ###
### 3
1 0 0 0 0 -1###
### -2
0 -0.33 0 1 0 -2###
### 3
0 0.167 0 0 1 2.5###
### 1.5
0 0.167 1 0 0 0.5###
### 0.5
0 0 0 ###
###
###
### 0
the big M method.

2

of "M"

optimal solution.


6
problem.

7
solution.

optimal solution.
9 That's it. Bye
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
J 5
K 6
L 7 4
M 8
N 9 3 4
0 0
P 11
###
###
###
###
###
###
###
###
###
###
###
###
###
###
###
###



pivot for you.


1 0 0 0
2 2 0 0
3 -1 0 0 0 0.17 1 0 0 0.5 0 0.17 0 0
4 6 1 0.167
5
6
7 #N/A 0 0
8 #N/A 0 0
9 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
10 #N/A 0 0
11
12
13 #N/A 0 0
14 #N/A 0 0
15 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
16 #N/A 0 0
17
18
19 #N/A 0 0
20 #N/A 0 0
21 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
22 #N/A 0 0
23
24
25 #N/A 0 0
26 #N/A 0 0
27 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
28 #N/A 0 0
29
30
31 #N/A 0 0
32 #N/A 0 0
33 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
34 #N/A 0 0
35
36
37 #N/A 0 0
38 #N/A 0 0
39 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
40 #N/A 0 0
41
42
43 #N/A 0 0
44 #N/A 0 0
45 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
46 #N/A 0 0
47
48
49 #N/A 0 0
50 #N/A 0 0
51 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
52 #N/A 0 0
53
1 0 0 0 0 -1 0 0 0 0 -2
0 -0.3 0 1 0 -2 0 -0.3 0 0 3
0.5 0 0.17 0 0 1 2.5 1 0.17 0 0 1.5
0 0.17 1 0 0 0.5 0 0.17 0 0 0.5
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0
-z x1 x2 x3 x4 s1 s2 s3 x8 RHS
Pivot Pivot 1 0.75 -20 0.5 -6 0 0 0 -3
Column Row 0 0.25 -8 -1 9 1 0 0 0
G 13 0 0.5 -12 -0.5 3 0 1 0 0
0 0 0 1 0 0 0 1 1
1 0 -2 1.25 -10.5 0 -1.5 0 -3

0 0 -2 -0.75 7.5 1 -0.5 0 0
I 20 0 1 -24 -1 6 0 2 0 0
0 0 0 1 0 0 0 1 1
1 0 -2 0 -10.5 0 -1.5 -1.25 -4.25

0 0 -2 0 7.5 1 -0.5 0.75 0.75
0 1 -24 0 6 0 2 1 1
0 0 0 1 0 0 0 1 1
0 0 0 0 0 0 0 0
Hi, This problem is dealing with
1 the perturbation method for
linear programming.
If you look at the spreadsheet

entiteled "Degeneracy Ex." you
2
will see an example in which
the simplex method "cycles."
In this example, we perturbed

3 the RHS by a little bit using a
randomly selected perturbation.
A random perturbation is one in

which the RHS is very close to
4 the original RHS, and the
difference is a very small
randomly selected number.
Now optimize using the simplex

5 algorithm using the min ratio
rule.
In fact, you may find the

7 optimum bfs after only a couple
of pivots.
If you look again at the pivot

8 elements, you will see that they
all satisfy the min ratio rule.
There was nothing special about
the perturbation used in this
9
example. It really was chosen
randomly.
In practice, there is a really tiny

probability that even with the
10
perturbation, there will be a
degenerate pivot.
In practice, this technique will

11
work very well.
12 That's all for now.
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
J 5
K 6
L 7 3
M 8
N 9 2 3
0 0
P 11
4 10
###
###
###
###
###
###
###
###
###
###
###
###
###
###
This method is discussed in the
tutorial on degeneracy
That is, there is a sequence of

degenerate pivots so that after the
sequence of pivots, the ending
basis is the same as the starting
basis.
It's a little different than what was

done in the tutorial but it still
works.
You will see that there are no

longer any ties for the leaving
variable, and no basis is
degenerate.
After you find the optimum, you can

modify the RHS by getting rid of the
perturbation and making it 0, 0, 1.
This shows that there is a choice of

pivot elements for the original
problem that leads to the optimum
bfs.
If you wanted, you could do the
problem again yourself with a
differently chosen random
perturbation. It will still work.
But you would have to be

amazingly unlucky to ever see it in
practice.
See you next problem.

1 0.75 0 0
2 0.25 0 0
3 0.5 1 2 0 1 -24 -1 6 0 2 0 0 0
4 0 0 0
5
6
7 1.25 0 0
8 -0.75 0 0
9 -1 0 0 0 0 0 1 0 0 0 1 0 0
10 1 1 1
11
12
13 #N/A 0 0
14 #N/A 0 0
15 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
16 #N/A 0 0
17
18
19 #N/A 0 0
20 #N/A 0 0
21 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
22 #N/A 0 0
23
24
25 #N/A 0 0
26 #N/A 0 0
27 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
28 #N/A 0 0
29
30
31 #N/A 0 0
32 #N/A 0 0
33 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
34 #N/A 0 0
35
36
37 #N/A 0 0
38 #N/A 0 0
39 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
40 #N/A 0 0
41
42
43 #N/A 0 0
44 #N/A 0 0
45 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
46 #N/A 0 0
47
48
49 #N/A 0 0
50 #N/A 0 0
51 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
52 #N/A 0 0
53
1 0 -2 1.25 -11 0 -1.5 0 0 0 -3
0 0 -2 -0.8 7.5 1 -0.5 0 0 0 0
0 0 1 -24 -1 6 0 2 0 0 0 0
0 0 0 1 0 0 0 1 0 0 1
1 0 -2 0 -11 0 -1.5 -1.3 0 0 -4.3

0 0 -2 0 7.5 1 -0.5 0.75 0 0 0.75
1 0 1 -24 0 6 0 2 1 0 0 1
0 0 0 1 0 0 0 1 0 0 1
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0.3 0.4 0.6
-3 -5 -7 -1 0
-z x1 x2 x3 x4 s1 s2 s3 x8 RHS
Pivot Pivot 1 5.4 6.2 9.8 -1 0 0 0 0 q
Column Row 0 1 4 2 -1 1 0 0 10 28
G 13 0 4 2 1 1 0 1 0 20
0 0 0 0 -1 0 0 1 10
1 0 3.5 8.45 -2.35 0 -1.35 0 -27

0 0 3.5 1.75 -1.25 1 -0.25 0 5
I 18 0 1 0.5 0.25 0.25 0 0.25 0 5
0 0 0 0 -1 0 0 1 10
1 0 -13.4 0 3.686 -4.83 -0.14 0 -51

0 0 2 1 -0.71 0.571 -0.14 0 2.857
J 25 0 1 0 0 0.429 -0.14 0.286 0 4.286
0 0 0 0 -1 0 0 1 10
1 -8.6 -13.4 0 0 -3.6 -2.6 0 -88

0 1.667 2 1 0 0.333 0.333 0 10
0 2.333 0 0 1 -0.33 0.667 0 10
0 2.333 0 0 0 -0.33 0.667 1 20
0 0 0 0 0 ###
### 0
1 helping out with the parametric
simplex method.
Here the objective function is as

follows: c1 = -3 + .2q, c2 = -5
2 + .4q, c3 = -7 + .4q, c4 = -1.
The other variables have a cost
of 0.
The objective function is

3 already set up with the correct
values as a function of q.
For q close to 0, the current bfs

4 is optimal. We will refer to the
initial bfs as BFS 1.
On the "Answer Sheet" write

down BFS 1 as well as the
5
interval in which this bfs is
optimal.
For this problem, you can

express all intervals rounded to
6 the nearest integer. You will
get extra credit if you give the
intervals exactly.
Now set q = 13, and find the

7 optimal bfs for this problem.
You can call this BFS 2.
Write BFS 2 on the Answer

8 sheet as well as the interval in
which the bfs is optimal.
Continue until you have a bfs
that is optimal for the current
9
value of q as welll as all larger
values of q.
At this point, you can write the

10 BFS on the answer sheet and
put the upper bound as infinity.
There is a chart at the bottom

of the answer sheet. As you
11 enter values into the table for
Problem 6, the charge will
change.
When you vary the cost

coefficients of a max LP in a
12 linear manner, the optimal
objective function is always
concave.
13
You may have noticed that you

only need to carry out one pivot
14 to obtain the next bfs in each
tableau in this example. That is
a coincidence.
15 That's all for this problem. Bye.
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
I 4
J 5
K 6
L 7 3
M 8
N 9 2 3
0 0
P 11
4 8
5 15
###
###
###
###
###
###
###
###
###
###
###
###
The method is discussed in Section
3.8 of Applied Mathematical
Programming in the subsection
"Objective Function Parametrics."
We want you to solve the problem

for all values of q from 0 to infinity.
We'll offer guidance along the way.
You can vary q by clicking on the

spinner above me.
As q increases, BFS 1 will

eventually stop being optimal.
HINT: it is optimal in the interval

(0, I1) for some I1 between 12 and
13. You can write the interval as
[0,13].
Now increase the value of q until

you reach the value at which BFS 2
is no longer optimal. Then find the
optimal bfs for this problem, and
call it BFS 3.
You can tell when this happens
because the cost coefficients of the
non-basic variables decrease or
stay the same as q increases.
If the chart worked properly, it

should give the optimal objective
value as a q. You will notice that
the objective function is concave.
This can be proved using the fact

that convex combinations of
feasible solutions are feasible. If
you like working with convexity,
you can try this on your own.
But we are not asking you to prove

it. So, feel free to move on.
In general, it could take many

pivots to go from an optimal bfs to
the next optimal bfs when carrying
out the parametric simplex
algorithm.
1 5.4 0 0
2 1 0 0
3 4 1 0.25 0 1 0.5 0.25 0.25 0 0.25 0 0 0
4 0 0 0
5
6
7 8.45 0 0
8 1.75 1 0.571
9 0.25 0 0 0 0 2 1 -0.7 0.57 -0.1 0 0 0
10 0 0 0
11
12
13 3.6857 0 0
14 -0.714 0 0
15 0.4286 1 2.333 0 2.33 0 0 1 -0.3 0.67 0 0 0
16 -1 0 0
17
18
19 #N/A 0 0
20 #N/A 0 0
21 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
22 #N/A 0 0
23
24
25 #N/A 0 0
26 #N/A 0 0
27 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
28 #N/A 0 0
29
30
31 #N/A 0 0
32 #N/A 0 0
33 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
34 #N/A 0 0
35
36
37 #N/A 0 0
38 #N/A 0 0
39 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
40 #N/A 0 0
41
42
43 #N/A 0 0
44 #N/A 0 0
45 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
46 #N/A 0 0
47
48
49 #N/A 0 0
50 #N/A 0 0
51 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
52 #N/A 0 0
53
1 0 3.5 8.45 -2.4 0 -1.4 0 0 0 -27
0 0 3.5 1.75 -1.3 1 -0.3 0 0 0 5
5 0 1 0.5 0.25 0.25 0 0.25 0 0 0 5
0 0 0 0 -1 0 0 1 0 0 10
1 0 -13 0 3.69 -4.8 -0.1 0 0 0 -51

0 0 2 1 -0.7 0.57 -0.1 0 0 0 2.86
2.86 0 1 0 0 0.43 -0.1 0.29 0 0 0 4.29
0 0 0 0 -1 0 0 1 0 0 10
1 -8.6 -13 0 0 -3.6 -2.6 0 0 0 -88

0 1.67 2 1 0 0.33 0.33 0 0 0 10
10 0 2.33 0 0 1 -0.3 0.67 0 0 0 10
0 2.33 0 0 0 -0.3 0.67 1 0 0 20
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
-z x1 x2 x3 x4 y1 y2 y3 x8 RHS
Pivot Pivot 1 -3 1 1 2 -20 -20 -20 0
Column Row 0 1 1 1 1 1 0 0 4
K 12 0 -2 1 -1 0 0 1 0 1
0 -1 3 0 1 0 0 1 8
1 17 21 21 22 0 -20 -20 80
0 1 1 1 1 1 0 0 4
L 19 0 -2 1 -1 0 0 1 0 1
0 -1 3 0 1 0 0 1 8
1 -23 41 1 22 0 0 -20 100

0 1 1 1 1 1 0 0 4
M 26 0 -2 1 -1 0 0 1 0 1
0 -1 3 0 1 0 0 1 8
1 -43 101 1 42 0 0 0 260

0 1 1 1 1 1 0 0 4
J 30 0 -2 1 -1 0 0 1 0 1
0 -1 3 0 1 0 0 1 8
1 -85 59 -41 0 -42 0 0 92

0 1 1 1 1 1 0 0 4
H 37 0 -2 1 -1 0 0 1 0 1
0 -2 2 -1 0 -1 0 1 4
1 33 0 18 0 -42 -59 0 33
0 3 0 2 1 1 -1 0 3
I 42 0 -2 1 -1 0 0 1 0 1
0 2 0 1 0 -1 -2 1 2
1 6 0 0 -9 -51 -50 0 6
0 1.5 0 1 0.5 0.5 -0.5 0 1.5
G 48 0 -0.5 1 0 0.5 0.5 0.5 0 2.5
0 0.5 0 0 -0.5 -1.5 -1.5 1 0.5
1 0 0 -4 -11 -53 -48 0 0

0 1 0 0.667 0.333 0.333 -0.33 0 1
I 56 0 0 1 0.333 0.667 0.667 0.333 0 3
0 0 0 -0.33 -0.67 -1.67 -1.33 1 0
1 0 0 0 -3 -33 -32 -12 0

0 1 0 0 -1 -3 -3 2 1
0 0 1 0 0 -1 -1 1 3
0 0 0 1 2 5 4 -3 0
0 0 0 0 0 0 0 0
the big M method.
Start off as before so that the

basic variables are y1, y2, and
2
y3 and so that the tableau is in
canonical form.
Then pivot until you get an

3
optimal solution.
You can try decreasing M, say

to -100, you will find that the
cost coefficients get even more
4
negative. No matter what you
do, the current bfs remains
optimal.
I'm about to explain why the

5 problem is infeasible. Have you
already tried to see why?
Pivots do not change the set of

feasible solutions. Write out
6 the three constraints
corresponding to the last three
rows of the optimal tableau.

see that one of the constraints
7 cannot be satisfied with any
non-negative choice of original
variables.
In general, if there is no
feasible solution, then the big M
8 method will terminate when
there is a an infeasible
constraint in a tableau.
9 That's all for now.
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
J 5
K 6
L 7 2
M 8
N 9 6 2
0 0
P 11
7 9
8 16
5 20
3 27
4 32
2 38
4
4 46
###
###
This problem is almost identical to
the previous problem. The only
differences are that we start with
M=-10, and the RHS of the third
constraint is lowered from 9 to 5.
If you did it correctly, you will find

that y2 is a basic variable in the
optimal solution.
This implies that the original

problem is infeasible. Before going
on, see if you can figure out
whether whether there is a simple
"proof" that the problem is
infeasible.
However, you should restrict

yourself to the original variables x1,
x2, x3, and x4. The variables y1,
y2, and y3 were not part of the
original problem.
Highlight this constraint by

selecting the constraint and making
the font red. You will also need to
write the constraint on the "answer
sheet."
This assumes that you choose M to

be sufficiently negative, as we did
here.
1 -20 0 0
2 1 1 1
3 0 0 0 0 1 1 1 1 1 0 0 0 0
4 0 0 0
5
6
7 -20 0 0
8 0 0 0
9 1 1 1 0 -2 1 -1 0 0 1 0 0 0
10 0 0 0
11
12
13 -20 0 0
14 0 0 0
15 0 0 0 0 -1 3 0 1 0 0 1 0 0
16 1 1 1
17
18
19 42 0 0
20 1 1 1
21 0 0 0 0 1 1 1 1 1 0 0 0 0
22 1 0 0
23
24
25 59 0 0
26 1 0 0
27 1 1 1 0 -2 1 -1 0 0 1 0 0 0
28 2 0 0
29
30
31 18 0 0
32 2 1 0.5
33 -1 0 0 0 1.5 0 1 0.5 0.5 -0.5 0 0 0
34 1 0 0
35
36
37 6 0 0
38 1.5 1 0.667
39 -0.5 0 0 0 1 0 0.67 0.33 0.33 -0.3 0 0 0
40 0.5 0 0
41
42
43 -4 0 0
44 0.6667 0 0
45 0.3333 0 0 0 0 0 1 2 5 4 -3 0 0
46 -0.333 1 -3
47
48
49 #N/A 0 0
50 #N/A 0 0
51 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
52 #N/A 0 0
53
1 17 21 21 22 0 -20 -20 0 0 80
0 1 1 1 1 1 0 0 0 0 4
4 0 -2 1 -1 0 0 1 0 0 0 1
0 -1 3 0 1 0 0 1 0 0 8
1 -23 41 1 22 0 0 -20 0 0 100

0 1 1 1 1 1 0 0 0 0 4
1 0 -2 1 -1 0 0 1 0 0 0 1
0 -1 3 0 1 0 0 1 0 0 8
1 -43 101 1 42 0 0 0 0 0 260

0 1 1 1 1 1 0 0 0 0 4
8 0 -2 1 -1 0 0 1 0 0 0 1
0 -1 3 0 1 0 0 1 0 0 8
1 -85 59 -41 0 -42 0 0 0 0 92

0 1 1 1 1 1 0 0 0 0 4
4 0 -2 1 -1 0 0 1 0 0 0 1
0 -2 2 -1 0 -1 0 1 0 0 4
1 33 0 18 0 -42 -59 0 0 0 33
0 3 0 2 1 1 -1 0 0 0 3
1 0 -2 1 -1 0 0 1 0 0 0 1
0 2 0 1 0 -1 -2 1 0 0 2
1 6 0 0 -9 -51 -50 0 0 0 6
0 1.5 0 1 0.5 0.5 -0.5 0 0 0 1.5
1.5 0 -0.5 1 0 0.5 0.5 0.5 0 0 0 2.5
0 0.5 0 0 -0.5 -1.5 -1.5 1 0 0 0.5
1 0 0 -4 -11 -53 -48 0 0 0 0

0 1 0 0.67 0.33 0.33 -0.3 0 0 0 1
1 0 0 1 0.33 0.67 0.67 0.33 0 0 0 3
0 0 0 -0.3 -0.7 -1.7 -1.3 1 0 0 0
1 0 0 0 -3 -33 -32 -12 0 0 0

0 1 0 0 -1 -3 -3 2 0 0 1
0 0 0 1 0 0 -1 -1 1 0 0 3
0 0 0 1 2 5 4 -3 0 0 0
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
-3 1 1 2
-z x1 x2 x3 x4 y1 y2 y3 x8 RHS
Pivot Pivot 1 0 0 0 0 -1 -1 -1 0
Column Row 0 1 1 1 1 1 0 0 4
0 -2 1 -1 0 0 1 0 1
0 -1 3 0 1 0 0 1 8
Sum 1 -2 5 0 2 0 0 0 13
0 0 0 0 0 0
### 0
helping out with the Phase 1 -
1
Phase 2 method for linear
programming.
In the big M method, we

penalize the artifiical variables
by making the costs -M. One
2
difficulty is that we don't know
the right value of -M to begin
with.
If we guess a really negative

number such as - 1 trillion, it
3
might make the computations
numerically unstable.
In the Phase 1 method, we

avoid this problem by ignoring
4 the original costs. Instead we
ask for a solution that
maximizes -y1 -y2 -y3.
We've already put the phase 1

objective into the initial tableau.
The correct cost coefficients for
6
the original variables are
written above the initial
tableau.
Now, carry out two additional

pivots so that the tableau is in
7
canonical form with basic
variables y1, y2 and y3.

algorithm until you have a new
8
optimal solution for the phase 1
problem.
We are now halfway there. We
9 now have a feasible basis for
At this point, change the

objective of the FIRST tableau
10 so that the objective function is
the original objective function:
-3 x1 + x2 + x3 + 2 x4.
You will notice that the

bottommost tableau is in
11 canonical form. If it is optimal
(ignoring the artificial
variables), then you can quit.
That's it for the Phase1- Phase

2 method. The Phase 1
problem refers to the LP with
12
artificial variables that led you
to a feasible basis for the
original problem.
The Phase 1 is used in practice

13 more widely than the big M
method.
We will now admit that we left

out a weakness of the big M
14 method. Suppose that there is
no feasible solution for the
original problem.
That is, it may contain an

15 artificial variable that is
positive.
It's possible that the original

problem is infeasible. It's also
16 possible that the original
problem is feasible and
unbounded from above.
In the Phase 1 method, the
optimal objective value is 0 or
17
lower. There is no danger of
having an unbounded solution.
18 That's all for now. Bye.
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
I 4
J 5
K 6
L 7 ###
M 8
N 9 ###
0 0
P 11
###
###
###
###
###
###
###
###
###
###
###
###
###
###
###
###
It's a lot like the big M method.
That's computer-speak for saying

that the computer round-off errors
will be so large that the answers
will be very inaccurate.
If there is a feasible solution for the

original problem, then there will be
an optimal solution to this "Phase 1
problem" in which y1 = y2 = y3 =
0.
If there is no feasible solution for

the original problem, then the
optimal solution will require that
some y variable is positive.
Don't erase them. We'll need them

later.
You will notice that all three

artificial variables are nonbasic.
That's good.
Don't worry about the costs of the
artificial variables. We are not
going to permit them to become
basic in any future pivot.
Otherwise, pivot until you have an

optimal basis for the original
problem. The artificial variables
should be ignored and not
permitted into the basis.
The Phase 2 problem refers to the

problem starting from the bfs for
the original problem and using the
original cost coefficients.
In practice, Phase 1 sometimes is

very easy. And sometimes, it takes
more time than Phase 2. It's hard
to predict how easy or hard it will
be.
It's possible that the big M method

will end with an unbounded
solution. But it may be an
unbounded infeasible solution.
This would be bad. The simplex

algorithm terminates, but there is
no feasible solution when it
terminates.
There are ways around this

difficulty for the big M method, but
we won't bother with them for now.
It's another subtlety of linear
programming.
So, Phase 1 ends either with a bfs
for the original problem or it ends
with a proof that there is no
feasible solution for the original
problem.
1 #N/A 0 0
2 #N/A 0 0
3 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
4 #N/A 0 0
5
6
7 #N/A 0 0
8 #N/A 0 0
9 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
10 #N/A 0 0
11
12
13 #N/A 0 0
14 #N/A 0 0
15 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
16 #N/A 0 0
17
18
19 #N/A 0 0
20 #N/A 0 0
21 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
22 #N/A 0 0
23
24
25 #N/A 0 0
26 #N/A 0 0
27 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
28 #N/A 0 0
29
30
31 #N/A 0 0
32 #N/A 0 0
33 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
34 #N/A 0 0
35
36
37 #N/A 0 0
38 #N/A 0 0
39 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
40 #N/A 0 0
41
42
43 #N/A 0 0
44 #N/A 0 0
45 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
46 #N/A 0 0
47
48
49 #N/A 0 0
50 #N/A 0 0
51 #N/A 0 0 0 0 0 0 0 0 0 0 0 0
52 #N/A 0 0
53
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###
0 ### ### ### ### ### ### ### ### ### ### ###
### ### ### ### ### ### ### ### ### ### ###

Lec 05

Uploaded by

Copyright:

Available Formats

Lec 05

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lec 05

Uploaded by

Copyright:

Available Formats

-z x1 x2 x3 s1 s2 s3 x8 RHS Col Ratio

Pivot Pivot 1 5 4.5 6 0 0 0 0

1 0.5 0.75 0 -0.75 0 0 -45

The original variables are x1 to

You will notice that there is a

The value is stored as a penalty

It's clear that there will be a

Now carry out the simplex

If you did it correctly, you will

Now continue the simplex

It's OK to have variables y1 to y3

It's right above me.

It turns out that -5 is not small

So, carry out three pivots to get the

Don't worry. This occurred because

If you did it correctly, the three

Choose row according

In case of tie, choose

Each pivot satisfies the min

You can go to Problem 4. Goodbye.

Each pivot satisfies the min

You can go to Problem 4. Goodbye.

The original variables are x1 to

You will notice that there is a

The value is stored as a penalty

It's clear that there will be a

Now carry out the simplex

If you did it correctly, you will

Now continue the simplex

It's OK to have variables y1 to y3

It's right above me.

It turns out that -5 is not small

So, carry out three pivots to get the

Don't worry. This occurred because

If you did it correctly, the three

The original variables are x1 to

You will notice that there is a

The value is stored as a penalty

It's clear that there will be a

Now carry out the simplex

If you did it correctly, you will

Now continue the simplex

It's OK to have variables y1 to y3

It's right above me.

It turns out that -5 is not small

So, carry out three pivots to get the

Don't worry. This occurred because

If you did it correctly, the three

1 0 -2 1.25 -10.5 0 -1.5 0 -3

1 0 -2 0 -10.5 0 -1.5 -1.25 -4.25

If you look at the spreadsheet

In this example, we perturbed

A random perturbation is one in

Now optimize using the simplex

In fact, you may find the

If you look again at the pivot

In practice, there is a really tiny

In practice, this technique will

12 That's all for now.