CS计算机代考程序代写 min P  cT x Summary subject to Ax  b,

min P  cT x Summary subject to Ax  b,
x, b  0.  Initialization: Select a basic feasible solution
ˆ 1
xB bB b0,
with B the basis matrix.
 Optimality Test: The current basis is optimal, if
Reduced costs
cT cT cTB1N0. ˆN N B
Otherwise, select a variable
ˆ
x that satisfies c  0 as the entering variable.
tt
2/24/2020 @2020 New York University Tandon 85 School of Engineering

 Recursive Step: Compute
Find an index s (determining the leaving variable, s‐th. basic variable in B) such that:
ˆˆ bs bi a0
ˆ minˆ ˆi,t 
a 1im a s,t  i,t
 
ˆ
The Pivot: From the “pivot entry” as,t , update the
basis matrix B and the vector of basis variables GO BACK TO STEP 2.
x. B
2/24/2020 @2020 New York University Tandon School of Engineering
86
ˆ 1 ABA.
tt

min Px 2x 12
In compact notation:
An Exercise
subjectto 2xx x 2 123
x 2x x 7 124
x x3 15
x , x , x , x , x  0. 12345
minPcTx, subjectto: Axb, x0, b0.
2/24/2020 @2020 New York University Tandon 87 School of Engineering

Answer
Check the sign of reduced cost at each step cT cT cTB1N.Ifall 0,thenSTOP.
ˆN N B Step 1:
Step 2:
2/24/2020
@2020 New York University Tandon 88 School of Engineering
TT x x,x,x,x x,x
B345N12 cT 0, 0, 0, cT 1, 2
BN
TT x x,x,x,x x,x
B245N13 cT 2, 0, 0, cT 1, 0
BN

Step 3:
TT x x,x,x,x x,x
Step 4:
TT x x,x,x,x x,x
2/24/2020
@2020 New York University Tandon 89
B215N34 cT 2, 1, 0, cT 0, 0
BN
B213N45 cT 2, 1, 0, cT 0, 0
BN
Optimal, because
cT cT cTB1N(1,2)0.
ˆN
School of Engineering
NB

Initial tableau:
The Simplex Tableau
Basic xB xN rhs -P cBT cTN 0
xB BNb Next, Basic xB xN rhs
2/24/2020
B I B1N B1b @2020 New York University Tandon
90
-P 0 cT cTB1N cTB1b xNBB
School of Engineering

The Simplex Tableau
For illustration purpose, study the same example.
Basic x1 x2 x3 x4 x5 rhs -P -1 -2 0 0 0 0
x3 -211002
x4 x5
-1 2 0 1 0 7 100013
2/24/2020
@2020 New York University Tandon 91 School of Engineering

Use the rule to select the pivot entry
s=3, t=2:
ˆˆ b ba0
s mini ˆi,t 
ˆˆ
a 1im a 
s,t  i,t  Basic x1 x2 x3 x4 x5 rhs
-P -1 -2 0 0 0 0 x
x3 -211002
x4 5
-1 2 0 1 0 7 100013
2/24/2020
@2020 New York University Tandon 92 School of Engineering

Add 2 times the x3 row to the –P row and subtract 2 times the x3 row from the x4 row:
Basic x1 x2 x3 x4 x5 rhs -P -5 0 2 0 0 4
x2 -211002
x4 5
3 0 -2 1 0 3 100013
2/24/2020
@2020 New York University Tandon 93 School of Engineering

Basic x1 x2 x3 x4 x5 rhs -P 0 0 -4/3 5/3 0 9
x x2
0 1 -1/3 2/3 0 4 1 0 -2/3 1/3 0 1 0 0 2/3 -1/3 1 2
x1 5
2/24/2020
@2020 New York University Tandon 94 School of Engineering

Final Step (Optimal solution):
Basic x x x3 x4 x rhs
125
-P 0 0 0 1 2 13
x2 x1
0 1 0 1/2 1/2 5 100013 0 0 1 -1/2 3/2 3
x3 2/24/2020
@2020 New York University Tandon School of Engineering
95

Final Step (Optimal solution):
Basic x x x3 x4 x rhs
125
-P 0 0 0 1 2 13
x2 x1
0 1 0 1/2 1/2 5 100013
x3
P 13, atx x 3, x 5.
3
0 0 1 -1/2 3/2
2/24/2020 @2020 New York University Tandon School of Engineering
96
132

Solve the minimization problem:
2/24/2020
@2020 New York University Tandon 97 School of Engineering
An Exercise
minP  3x x 3x 123
subjectto 2x x x 2 123
x 2x 3x 5 123
2x 2x x 6 123
x  0, x  0, x  0. 123

-P
Answer
First tableau (pivoting 1 leads to less computation):
x1 x2 x3 x4 x5 x6
-3 -1 -3 0 0 0 0
2111002 1230105 2210016
2/24/2020 @2020 New York University Tandon 98 School of Engineering
rhs

-P
Answer (cont’d)
Second tableau:
x1 x2 x3 x4 x5 x6
-1 0 -2 1 0 0 2
2111002 -3 0 1 -2 1 0 1 -2 0 -1 -2 0 1 2
2/24/2020 @2020 New York University Tandon 99 School of Engineering
rhs

-P
Answer (cont’d)
Third tableau:
x1 x2 x3 x4 x5 x6
-7 0 0 -3 2 0 4
5 1 0 3 -1 0 1 -3 0 1 -2 1 0 1 -5 0 0 -4 1 1 3
2/24/2020 @2020 New York University Tandon 100 School of Engineering
rhs

-P
0 6/5
0 3/5 -1/5 0 1/5 1 -1/5 2/5 0 8/5
Answer (cont’d)
Fourth tableau:
x1 x2 x3 x4
x5 x6
3/5 0 27/5
0 7/5
1 1/5
0 3/5
0 1 0 -1 0 1 4
2/24/2020 @2020 New York University Tandon 101 School of Engineering
rhs

Answer (cont’d)
2/24/2020
@2020 New York University Tandon 102 School of Engineering
Optimal solution, read from the last tableau: x* 1,x* 0,x* 8,x* 0,x* 0,x* 4.
15235456
P* 27. 5

Artificial Variables
Goal: Find an (initial) basic feasible solution for the standard LP Problem:
min PcTx subject to Ax  b,
2/24/2020 @2020 New York University Tandon 103 School of Engineering
x  0.

The Two‐Phase Method
The phase-I problem:


min P a
i i
subjectto Ax ab, x, a  0,
T
a  a ,, a  : artificial variables
1m
A direct application of the simplex method yields a basic feasible solution (not optimal)
for the original P !!
2/24/2020 @2020 New York University Tandon 104 School of Engineering

2/24/2020
@2020 New York University Tandon 105 School of Engineering
An Example
min P2x 3x 12
subjectto 3x2x14 12
2x 4x 2 12
4x 3x 19 12
x , x  0. 12

2/24/2020
@2020 New York University Tandon 106 School of Engineering
An Example (cont’d)
min P2x 3x 12
subjectto 3x2x 12
14 2
2x 4x x 123
x 19 124
4x 3x
x , x , x , x  0.
1234
No obvious basic feasible solution, due to less than (three) slack variables.

Phase‐1 Problem:
subjectto
3x 2x a 14 121

min Pa a 12
2x 4x x a 2 1232
4x 3x x 19 124
x,x,x,x,a,a 0. 123412
Now the (initial) basic feasible variable
TT x  a,a,x withvalues 14,2,19 .

B124
2/24/2020 @2020 New York University Tandon 107 School of Engineering

Applying the simplex technique,
Initial tableau:

x1 x2 x3 x4 a1 a2 0000110
P
3 2 0 0 1 0 14
2/24/2020
@2020 New York University Tandon 108 School of Engineering
2 -4 -1 0 0 1 2 4 3 0 1 0 0 19
rhs


(Use elimination to the first row to make the entries for the initial basic variables 0.)
First tableau:
x1 x2 x3 x4 a1 a2
-5 2 1 0 0 0 -16
P
3 2 0 0 1 0 14
2 -4 -1 0 0 1 2
4 3 0 1 0 0 19
2/24/2020 @2020 New York University Tandon 109 School of Engineering
rhs

(The basic variable a2 leaving, so delete the irrelevant a2 column:)
Second tableau:

x1 x2 x3 x4 a1
0 -8 -3/2 0 0 -11
P
0 8 3/2 0 1 11
2/24/2020
@2020 New York University Tandon 110 School of Engineering
1 -2 -1/2 0 0 1 011210 15
rhs

(The basic variable x4 leaving, but cannot delete the relevant x4 column:)
Third tableau:
 0 P
0 -1/22 8/11
-1/11 1/11
2/24/2020
@2020 New York University Tandon School of Engineering
111
x1 x2 x3 x4
a1 0
rhs
0 0
1 0
0 1
1/22 -8/11 -3/22 2/11
1
2/11 1/11
0 0
41/11 15/11

(The basic variable a1 leaving, so delete the irrelevant a1 column:)
Third tableau:
x1 x2 x3 x4 P
rhs 0000 0
2/24/2020
@2020 New York University Tandon 112 School of Engineering
0 0 1 -16 2 1 0 0 -2 4 0103 1

Phase–II Problem: P=2×1 + 3×2
Initial tableau:
-P
2/24/2020
@2020 New York University Tandon 113 School of Engineering
x1 x2 x3 x4
2300 0
0 0 1 -16 2 1 0 0 -2 4 0103 1
rhs

Phase–II Problem: P=2×1 + 3×2
First tableau (Use elimination to the first row to make the entries for the initial basic variables 0):
-P
2/24/2020
@2020 New York University Tandon 114 School of Engineering
x1 x2 x3 x4
0 0 0 -5 -11
0 0 1 -16 2 1 0 0 -2 4 0103 1
rhs

Phase–II Problem: P=2×1 + 3×2
Second tableau:
-P
-28/3 22/3 14/3
2/24/2020
@2020 New York University Tandon School of Engineering
115
x1 x2 x3 x4 0 5/3 0 0
rhs
016/3 1 0 1 2/3 0 0 0 1/3 0 1
1/3

So, the optimal solution is
 P*   28 , or P*  28
33
which is attained at the following minimizer:
x* 14, x* 0, x* 22, x* 1. 132 3343
2/24/2020 @2020 New York University Tandon 116 School of Engineering

2/24/2020
@2020 New York University Tandon 117 School of Engineering
An Exercise
minP4x x x 123
subjectto 2x x 2x 4 123
3x 3x x 3 123
x 0, i1,2,3 i

Degeneracy
A linear program is degenerate, if a basic variable equals zero, i.e., the last column b contains a zero.
2/24/2020 @2020 New York University Tandon 118 School of Engineering

x ba0b0 t min i ˆi,t  s
ˆˆ 1ima a
Cycling
In case of degeneracy, it may happen that ˆˆ
 i,t  s,t
Then, the performance function does not improve:
ˆˆ ˆ
PPcxP tt
eventually leading to the cycling problem,
i.e., the (leaving) basic variable xs will be re-chosen as the entering variable in a few steps.
2/24/2020 @2020 New York University Tandon 119 School of Engineering

2/24/2020
@2020 New York University Tandon School of Engineering
120
A Degenerate LP Problem
For the following LP problem, the simplex method cycles indefinitely!
minP3x 150x  1 x 6x 41 2503 4
subjectto 1x60x1x9x0 41 2253 4
1x 90x  1 x 3x 0 21 2503 4
x3 1 xi 0, 1i4.

Bland’s Rule
Goal: to avoid cycling. Make the following changes in the simplex method,
a) select the lowest‐indexed favorable column to enter the basis, using the rule:
b) In case of ties or undecision, select the lowest indexed column to leave the basis.

jmin j: c 0 . ˆj
2/24/2020 @2020 New York University Tandon 121 School of Engineering

2/24/2020
@2020 New York University Tandon 122 School of Engineering
The Perturbation Method
This is another efficient method to avoid cycling or minimize computation time.
The simplex method will surely terminate if applied to the LP with perturbed constraints:
Ax  b where,forsufficientlysmall0 0,
 ,2,,m 000