CS计算机代考程序代写 finance LP: Linear Programming Overview

LP: Linear Programming Overview
LP is a tool for solving optimization problems with linear cost functions and constraints (Dantzig, 1947). Motivated by addressing military problems during World War II, LP has now found a wide range of industrial applications in banking, economics & finance, transportation, petroleum, and IT, etc.
2/8/2021 @2020 New York University Tandon 44 School of Engineering

•
Standard Form and Basic Solutions
• •
The Simplex Method (G. Dantzig, 1947)
Key topics to be covered:
Duality and Sensitivity,
and the Interior‐Point Method
2/8/2021 @2020 New York University Tandon 45 School of Engineering

2/8/2021
@2020 New York University Tandon 46 School of Engineering
problem:
min Px 2x 12
A Geometric Look at LP
Consider a second‐order linear programming
subjectto 2xx2 12
xx3 12
x , x  0. 12
x3 1

The Feasible Region
P = -15
2/8/2021
@2020 New York University Tandon 47 School of Engineering
-3
-1 3 P=0
X1
X 2
𝑥 􏰂 􏰃 􏰄 12 𝑥 􏰅 􏰄 12 𝑃
3
6
P = -4 P = -2

Observations
• The minimizer occurs at the corner or extreme point (3, 6).
• The feasible region (defined by linear constraints) is convex.
• The geometric approach is useful for two‐ dimensional LP problems.
There is no uniqueness of LP solutions. Indeed, the optimal solutions may be the line sengment between two corner points.
2/8/2021 @2020 New York University Tandon 48 School of Engineering

Exercise for the Geometric Approach
2/8/2021
@2020 New York University Tandon 49 School of Engineering
Can you apply the geometric approach to solve the following LP problem:
maxP6x 2x , 12
subject to
4x 5x 20,
12 3x x 6,
12
x , x  0. 12

The Simplex Method
A more systematic tool
• Require a standard form
• Require an initial basic and feasible solution • Applicable to any-size LP problem
2/8/2021 @2020 New York University Tandon 50 School of Engineering

2/8/2021
@2020 New York University Tandon 51 School of Engineering
Standard Form
Using matrix‐vector notation, an LP problem in standard form is written as:
min PcTx subject to Ax  b,
x  0, Amn, bm, b0.

2/8/2021
@2020 New York University Tandon 52 School of Engineering
Transformation to Standard Form
• A link between max and min:
max{PcTx}  min{PcTx}
xS xS
• From “inequality” to “=“ using slack variable:
axax b i1 1 in n i

a x a x s  b
i11 innii

Transformation to SF (cont’d)
• From “inequality” to “=“ using excess variable: a x a x  b
j1 1 jn n j 
a x a x e  b j11 jnnjj
• For a “free” or “unrestricted” variable x,
x  x  x , with x , x  0
1212
2/8/2021 @2020 New York University Tandon 53 School of Engineering

2/8/2021
@2020 New York University Tandon 54 School of Engineering
An Example
Convert the following LP problem into standard form:
max P5x3x7x 123
subjectto 2x4x6x7 123
3x 5x 3x 5 123
4x 9x 4x 4 123
x  2, 0  x  4, x free 123

New Unknowns
2/8/2021
@2020 New York University Tandon 55 School of Engineering
Example (cont’d)
z  x  2, z  x , z  z  4, z  z  x 112223453
3x 5x 3x z 5 1236
4x 9x 4x z 4 1237
7 All new unknowns zi 
are  0.
i1

New Objective Function
2/8/2021
@2020 New York University Tandon 56 School of Engineering
Example (cont’d)
P5x 3x 7x 123
105z 3z 7z 7z 1245
10  cT z where
cT 5, 3, 0, 7, 7, 0, 0, zT z,z,,z.
127

New Constraints
z2 z3 4,
3x 5x 3x z 5
2/8/2021
@2020 New York University Tandon 57 School of Engineering
2x 4x 6x 7, 123
1236
4x 9x 4x z 4 1237

2z 4z 6z 6z 11,
1245  z 2  z 3  4 ,
3z 5z 3z 3z z 11, 12456
4z 9z 4z 4z z 12. 12457

New Constraints
2/8/2021
@2020 New York University Tandon 58 School of Engineering
Az  b 
11 2 4 0 6 6 0 0 
4  0 1 1 0 0 0 0  b , A  11 3 5 0 3 3 1 0 

12 4 9 0 4 4 0 1 

2/8/2021
@2020 New York University Tandon 59 School of Engineering
subject to
Exercise
Convert the following optimization problem into an LP in the standard form:
minPx 2x 12
xx 4. 12

2/8/2021
@2020 New York University Tandon 60 School of Engineering
Standard Form (cont’d)
min PcTx subject to Ax  b,
x  0, Amn, bm, b0.
Assumptions:
1. m  n : Less constraints than variables. 2. The matrix A has full (row) rank.

Extreme Points
A point xS is an extreme point if x is not inside a line segment connecting any two points (y, z) of S:
xy(1)z, 01, y,zx.
2/8/2021 @2020 New York University Tandon 61 School of Engineering

A Geometric Result
Assuming a finite minimum of the LP problem exists, it is attained at (at least) one extreme point of the constraint set, or called vertices.
Proof. – See the book, where the constraint set, S, defined by linear constraints, is convex:
y,zS y1 zS,01. 
2/8/2021 @2020 New York University Tandon 62 School of Engineering

Basic Solutions
A point x is a basic solution if:
i) x satisfies the equality constraints of the LP
problem.
ii) the columns of the constraint matrix A corresponding to the nonzero components of x are linearly independent.
A basic feasible solution is a basic solution that satisfies x > = 0.
2/8/2021 @2020 New York University Tandon 63 School of Engineering

Comment
• Abasicfeasiblesolutionisanextremepoint.Lookat the motivating example:
2/8/2021
@2020 New York University Tandon 64 School of Engineering
min Px 2x 12
subjectto 2xx2 12
xx3 12
x , x  0. 12
x3 1

2/8/2021
@2020 New York University Tandon 65 School of Engineering
Standard Form
min Px 2x 12
subjectto 2xxs2 121
xxs3 122
xs3 13
x , x , s , s , s  0. 12123

Basic Solutions
• For the basis x , s , s , the basic solution follows: 213
x x s s s03103 12123
• For the basiss1 , s2 , s3 ,the basic solution follows: x x s s s00223
12123
• For the basisx1 , x 2 , s1 , the basic solution follows:
x x s s s36200 12123
2/8/2021 @2020 New York University Tandon School of Engineering
66
Optimal !

An Equivalence Theorem
A point x is an extreme point of the set {x: Ax=b, x>=0} if and only if
it is a basic feasible solution.
2/8/2021 @2020 New York University Tandon 67 School of Engineering

The Sufficiency
If x is a basic feasible solution, then after re‐ordering,
xxB xB  and AB N x  0 
N
where B is an invertible matrix.
By contradiction, assume x is not an extreme point. Then,
xy(1)z, y0, z0, (0,1) TT
yyB yN, zzB zN, yz.
2/8/2021 @2020 New York University Tandon 68 School of Engineering

Therefore, it holds
The Sufficiency (cont’d)
yN zN 0, BxB ByB BzB b
Since B is an invertible matrix, we reach a contradiction.
2/8/2021 @2020 New York University Tandon 69 School of Engineering

The Necessity
If x is an extreme point, we prove by contradiction that x is a basic feasible solution:
xxB xB,x >0 and AB N,Bfullcolumnrank x  0  B
N
If B is not full column rank, then there is a nonzero vector
p such that
Bp  B p  B p  0, with B the i-th column of B.
11kki
2/8/2021 @2020 New York University Tandon 70 School of Engineering

2/8/2021
@2020 New York University Tandon 71 School of Engineering
The Necessity (cont’d)
It is direct to check that the following points are feasible and distinct from x :
yxB p and zxB p, 0small xx
NN
x  1 y  1 z, Contradiction ! 22

Comments
A basic feasible solution is called degenerate vertex, if one or more of the basic variables are zero.
The LP Problem, in this case, is called degenerate.
2/8/2021 @2020 New York University Tandon 72 School of Engineering

Lecture objective
Key points:
The Simplex Method
Comparing with the geometric approach, the simplex method is a systematic, powerful tool applicable to linear programming problems of any size.
• Principles of the simplex method.
• Step‐by‐step implementation: simplex tableau
• Initialization via “Artificial Variables”
2/8/2021 @2020 New York University Tandon 73 School of Engineering

Principles of the Simplex Method
• Begin with an (initial) basic feasible solution, or an extreme point.
• Move to a (new) basic feasible solution, to improve the performance function.
2/8/2021 @2020 New York University Tandon 74 School of Engineering

2/8/2021
@2020 New York University Tandon 75 School of Engineering
An Example
min Px 2x 12
subjectto 2xx2 12
x 2x 7 12
x , x  0. 12
x3 1

The Feasible Region
2/8/2021
@2020 New York University Tandon School of Engineering
76
-3
-1A 3
E
X1
X2
6
D
C 3
B

2/8/2021
@2020 New York University Tandon 77 School of Engineering
Conversion to Standard Form
min Px 2x 12
subjectto 2xx x 2 123
In compact notation:
x 2x x 7 124
min P  cT x
subjectto: Axb, x0, b0.
x x3 15
x , x , x , x , x  0. 12345

Basic Feasible Solutions
PointA:(0,0,2,7,3)x (x,x,x),x (x,x) B 345N 12
subjecttox 22x x , x 7x 2x , x 3x. 31241251

next, increase x to 2 (while x =0!) to give: 21
PointB:(0,2,0,3,3)x (x,x,x),x (x,x) B 245N 13
based on the above equality constraints!
Thisstepyields:P45x 2x 13
subjecttox 22xx,x 33x2x,x 3x. 21341351

2/8/2021 @2020 New York University Tandon 78 School of Engineering

Observations
• The slack variables are good candidates for (initial choice of) basic variables.
• At each step, P is rewritten as a (linear) function of non-basic variables only.
2/8/2021 @2020 New York University Tandon 79 School of Engineering

min PcTx
subject to
AB  N x,PcTx cTx
2/8/2021
@2020 New York University Tandon 80 School of Engineering
General Formulas
Ax  b,
x, b  0.
xB  BBNN
x N
BxB  NxN  b, B invertible xB B1bB1NxN

General Formulas (Cont’d)
PyTb cTyTNx NN

cˆ T reduced costs N
withyT cBTB1
At each step, setting xN  0 leads to
1 ˆˆT1 xB B bb, PcBB b.
2/8/2021 @2020 New York University Tandon 81 School of Engineering

Then,
General Formulas (Cont’d)
t
ˆ
PPcTx ˆN N
ˆˆ
Let c j be the entry of cN corresponding to x j .
Ifc 0forsomej,thenPcanbeimproved ˆj
(or minimized) by increasing xj from zero.
Letx besuchavariablechosentoenterthebasis.
ˆ1 ˆˆ
x bB Nx bAx
BNtt ˆ 1
withA B A, A t-thcolumnofA. ttt
2/8/2021 @2020 New York University Tandon 82 School of Engineering

General Formulas (Cont’d)
ˆ1 ˆˆ
x bB Nx bAx
BNtt can be rewritten as: i,
ˆ
(x )  b  a x B i i ˆi,t t
Only when a  0, (x ) decreases as x increases! ˆi,t Bi t
Therefore,increasext usingtherule:
2/8/2021
 i,t  i,t @2020 New York University Tandon
83
ˆˆ bb
x i
tminˆ ˆi,t  Biˆ tˆi,t
a 0, noting(x) i xa 1ima a
School of Engineering

Remark:
When a  0 for all i, then, as x
2/8/2021
@2020 New York University Tandon School of Engineering
84
General Formulas (Cont’d)
This yields the new basic variables and an improved performance function:
ˆˆ
x bAx
Btt
ˆˆ
PP  cx, c reducedcostofx
ˆˆ
tttt
ˆi,t fromzero,P !
t
increases

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/8/2021 @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  as,t 1im ai,t 
ˆ 1 ABA.
tt

ˆ
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/8/2021 @2020 New York University Tandon School of Engineering
86

2/8/2021
@2020 New York University Tandon 87 School of Engineering
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.

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/8/2021
@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/8/2021
@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