Introduction to Linear Programming
Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
X1
X2
X3
X4
Unit: thousand
To win at least 50000 urban votes: -2x1+8x2+0x3+10x4 50.
To win at least 100000 suburban votes: 5x1+2x2+0x3+0x4 100.
To win at least 25000 rural votes: 3x1-5x2+10x3-2x4 25.
Want to minimize x1 + x2 + x3 + x4
Minimization linear program:
minimize x1 + x2 + x3 + x4
subject to
-2x1+ 8x2 + 0x3 + 10x4 50
5x1+ 2x2 + 0x3 + 0x4 100
3x1- 5x2 +10x3- 2x4 25
x1 , x2 , x3 , x4 0.
Maximization linear program:
maximize x1 + x2
subject to
4x1 - x2 8
2x1 + x2 10
5x1 - 2x2 -2
x1 , x2 0.
Standard form, objective function, feasible solution and region,
simplex algorithm, ellipsoid algorithm, interior-point method
Copyright The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Standard and Slack forms:
Standard form:
maximize cj xj
subject to
aij xj bi for i=1, …, m.

xj 0 for j=1, …, n.
Objective function
Constraints
Nonnegative constraints
maximize cT x
subject to
A x b

下一页