Linear Programming (lp) Linear Programming (lp)

Linear LinearProgramming Programming(LP) (LP)

Optimization in Engineering Design

Georgia Institute of Technology Systems Realization Laboratory 1

Why WhyTalk TalkAbout AboutLinear Linear Programming? Programming?

• LP is simpler than NLP, hence, good for a foundation • Linearity has some unique features for optimization • A lot of problems are or can be converted to a LP formulation • Some NLP algorithms are based upon LP simplex method

Optimization in Engineering Design

Georgia Institute of Technology Systems Realization Laboratory 2

Bolted BoltedJoint Joint Design Design Given At - tensile strength area, function of d Db - bolt circle diameter Pt - total load

Question: Question: Is Is this this aa linear linear or or nonlinear model? nonlinear model?

C - joint constant Fi - preload (= 0.75 Sp At) Find

N - number of bolts, Sp - proof strength, d - diameter Satisfy 3d ≤ π Db / N

good wrench rule

π Db / N ≤ 6d

good seal rule

C Pt / N ≤ Sp At - Fi

static loading constraint

Fi ≥ (1 - C) Pt / N

joint separation constraint

Minimize Z= [ f1(N, d, Sp), f2(N, d, Sp), ..] Optimization in Engineering Design

Georgia Institute of Technology Systems Realization Laboratory 3

Bolted BoltedJoint Joint Design Design (2) (2) Given d - diameter At - tensile strength area, function of d Db - bolt circle diameter Pt - total load

Question: Question: Is Is this this aa linear linear or or nonlinear problem? nonlinear problem?

C - joint constant Fi - preload (= 0.75 Sp At) Find N - number of bolts, Sp - proof strength Satisfy 3d ≤ π Db / N

good wrench rule

π Db / N ≤ 6d

good seal rule

C Pt / N ≤ Sp At - Fi

static loading constraint

Fi ≥ (1 - C) Pt / N

joint separation constraint

Minimize Z= [ f1(N, Sp), f2(N, Sp), ..] Optimization in Engineering Design

Georgia Institute of Technology Systems Realization Laboratory 4

Historical Historical Perspective Perspective 1928 – John von Neumann published related central theorem of game theory 1944 – Von Neumann and Morgenstern published Theory of Games and Economic Behavior 1936 – W.W. Leontief published "Quantitative Input and Output Relations in the Economic Systems of the US" which was a linear model without objective function. 1939 – Kantoravich (Russia) actually formulated and solved a LP problem 1941 – Hitchcock poses transportation problem (special LP) WWII – Allied forces formulate and solve several LP problems related to military A breakthrough occurred in 1947...

Optimization in Engineering Design

Georgia Institute of Technology Systems Realization Laboratory 5

SCOOP SCOOP •

US Air Force wanted to investigate the feasibility of applying mathematical techniques to military budgeting and planning.

•

George Dantzig had proposed that interrelations between activities of a large organization can be viewed as a LP model and that the optimal program (solution) can be obtained by minimizing a (single) linear objective function.

•

Air Force initiated project SCOOP (Scientific Computing of Optimum Programs)

NOTE: SCOOP began in June 1947 and at the end of the same summer, Dantzig and associates had developed: 1) An initial mathematical model of the general linear programming problem. 2) A general method of solution called the simplex method.

Optimization in Engineering Design

Georgia Institute of Technology Systems Realization Laboratory 6

Simplex SimplexToday Today • A large variety of Simplex-based algorithms exist to solve LP problems. • Other (polynomial time) algorithms have been developed for solving LP problems: –

Khachian algorithm (1979)

–

Kamarkar algorithm (AT&T Bell Labs, mid 80s)

–

See Section 4.10

BUT, none of these algorithms have been able to beat Simplex in actual practical applications. HENCE, Simplex (in its various forms) is and will most likely remain the most dominant LP algorithm for at least the near future Optimization in Engineering Design

Georgia Institute of Technology Systems Realization Laboratory 7

Fundamental Fundamental Theorem Theorem Extreme Extremepoint point(or (or Simplex Simplex filter) filter) theorem: theorem: IfIf the the maximum maximum or or minimum minimum value value of of aa linear linear function function defined defined over over aa polygonal polygonal convex convex region region exists, exists, then thenitit is is to to be be found found at at the theboundary boundaryof ofthe theregion. region. Convex Convexset: set: AAset set(or (orregion) region)is isconvex convexif, if,for forany anytwo twopoints points(say, (say,x1 x1 and x2) in that set, the line segment joining these points and x2) in that set, the line segment joining these points lies liesentirely entirelywithin withinthe theset. set. AApoint pointis isby bydefinition definitionconvex. convex.

Optimization in Engineering Design

Georgia Institute of Technology Systems Realization Laboratory 8

What What does doesthe theextreme extremepoint pointtheorem theorem imply? imply? • A finite number of extreme points implies a finite number of solutions! • Hence, search is reduced to a finite set of points • However, a finite set can still be too large for practical purposes • Simplex method provides an efficient systematic search guaranteed to converge in a finite number of steps.

Optimization in Engineering Design

Georgia Institute of Technology Systems Realization Laboratory 9

Basic Basic Steps Steps of of Simplex Simplex 1. Begin the search at an extreme point (i.e., a basic feasible solution). 2. Determine if the movement to an adjacent extreme can improve on the optimization of the objective function. If not, the current solution is optimal. If, however, improvement is possible, then proceed to the next step. 3. Move to the adjacent extreme point which offers (or, perhaps, appears to offer) the most improvement in the objective function. 4. Continue steps 2 and 3 until the optimal solution is found or it can be shown that the problem is either unbounded or infeasible. Optimization in Engineering Design

Georgia Institute of Technology Systems Realization Laboratory 10

Step Step 00––Obtain ObtainCanonical Canonical Form Form IMPORTANT: Simplex only deals with equalities General Simplex LP model: min (or max) z = Σ ci xi s.t. Ax=b x≥ 0 In order to get and maintain this form, use • slack, if x ≤ b, then x + slack = b •

surplus, if x ≥ b, then x - surplus = b

•

artificial variables (sometimes need to be added to ensure all variables ≥ 0, see page 101)

Compare Compare constraint constraint conversion conversion with with goal goal conversions conversionsusing usingdeviation deviation variables variables Optimization in Engineering Design

Georgia Institute of Technology Systems Realization Laboratory 11

Different Different "components" "components" of of aaLP LP model model

• LP model can always be split into a basic and a non-basic part. • “Transformed” or “reduced” model is another good way to show this. • This can be represented in mathematical terms as well as in a LP or simplex tableau.

Optimization in Engineering Design

Georgia Institute of Technology Systems Realization Laboratory 12

Movement Movement to to Adjacent Adjacent Extreme Extreme Point Point

Given any basis we move to an adjacent extreme point (another basic feasible solution) of the solution space by exchanging one of the columns that is in the basis for a column that is not in the basis.

Two things to determine: 1) which (nonbasic) column of A should be brought into the basis so that the solution improves? 2) which column can be removed from the basis such that the solution stays feasible?

Optimization in Engineering Design

Georgia Institute of Technology Systems Realization Laboratory 13

Entering Enteringand andDeparting Departing Vector Vector (Variable) (Variable) Rules Rules

General rules: •

The one non-basic variable to come in is the one which provides the highest reduction in the objective function.

•

The one basic variable to leave is the one which is expected to go infeasible first.

NOTE: THESE ARE HEURISTICS!! Variations on these rules exist, but are rare.

Optimization in Engineering Design

Georgia Institute of Technology Systems Realization Laboratory 14

Simplex SimplexVariations Variations

Various variations on the simplex method exist: • "regular" simplex (see Section 4.4) •

two-phase method: Phase I for feasibility and Phase II for optimality (see Section 4.5.1)

•

condensed/reduced/revised method: only use the nonbasic columns to work with (see Section 4.6)

•

(revised) dual simplex (see Section 4.8), etc.

Optimization in Engineering Design

Georgia Institute of Technology Systems Realization Laboratory 15

Computational Computational Considerations Considerations

•

Unrestricted variables (unboundedness)

•

Redundancy (linear dependency, modeling errors)

•

Degeneracy (some basic variables = 0)

•

Round-off errors

Optimization in Engineering Design

Georgia Institute of Technology Systems Realization Laboratory 16

Limitations Limitationsof ofSimplex Simplex 1.

Inability to deal with multiple objectives

2.

Inability to handle problems with integer variables

Problem 1 is solved using Multiplex Problem 2 has resulted in: • Cutting plane algorithms (Gomory, 1958) •

Branch and Bound (Land and Doig, 1960)

However, solution methods to LP problems with integer or Boolean variables are still far less efficient than those which include continuous variables only

Optimization in Engineering Design

Georgia Institute of Technology Systems Realization Laboratory 17

Example ExampleProblem Problem Maximize Z = 5x1 + 2x2 + x3 subject to

x1 + 3x2 - x3 ≤ 6, x2 + x3 ≤ 4, 3x1 + x2

≤ 7,

x1, x2, x3 ≥ 0.

Optimization in Engineering Design

Georgia Institute of Technology Systems Realization Laboratory 18

Simplex Simplexand and Example Example Problem Problem Step 1. Convert to Standard Form a11 x1 + a12 x2 + ••• + a1n xn ≤ b1,

a11 x1 + a12 x2 + ••• + a1n xn + xn+1 = b1,

a21 x1 + a22 x2 + ••• + a2n xn ≥ b2,

a21 x1 + a22 x2 + ••• + a2n xn - xn+2 = b2,

am1 x1 + am2 x2 + ••• + amn xn ≤ bm,

am1 x1 + am2 x2 + ••• + amn xn + xn+k = bm,



In our example problem: x1 + 3x2 - x3 ≤ 6, x2 + x3 ≤ 4, 3x1 + x2

≤ 7,

x1, x2, x3 ≥ 0. Optimization in Engineering Design

x1 + 3x2 - x3 + x4 x2 + x3 3x1 + x2

= 6,

+ x5

= 4,

+ x6 = 7,

x1, x2, x3, x4, x5, x6 ≥ 0. Georgia Institute of Technology Systems Realization Laboratory 19

Simplex: Simplex: Step Step22 Step 2. Start with an initial basic feasible solution (b.f.s.) and set up the initial tableau. In our example Maximize Z = 5x1 + 2x2 + x3 x1 + 3x2 - x3 + x4 x 2 + x3 3x1 + x2

= 6,

+ x5

= 4,

+ x6 = 7,

x1, x2, x3, x4, x5, x6 ≥ 0.

cB 0 0 0

Optimization in Engineering Design

Basis

x4 x5 x6 c row

cj

Constants

5 2 1 0 0 0 x1 x2 x3 x4 x5 x6 1 3 -1 1 0 0 0 1 1 0 1 0 3 1 0 0 0 1 5 2 1 0 0 0

6 4 7 Z=0

Georgia Institute of Technology Systems Realization Laboratory 20

Step Step2: 2:Explanation Explanation Adjacent Basic Feasible Solution If we bring a nonbasic variable xs into the basis, our system changes from the basis, xb, to the following (same notation as the book): x1 + ā1s xs= b1 x = b −a for i =1, …, m i

i

xr

is

xs = 1

+ ārs xr= b r 

xj = 0

for j=m+1, ..., n and j≠ s

xm + āms xs= bs The new value of the objective function becomes: m

Z=

∑ c (b − a i

i

is ) + c s

i =1

Thus the change in the value of Z per unit increase in xs is

cs = new value of Z - old mvalue of Z m =

∑ c (b − a c − ∑c a i

i =1

=

i

m

s

i is

i =1

Optimization in Engineering Design

is ) + c s

−

∑c b

i i

i =1

This is the Inner Product rule Georgia Institute of Technology Systems Realization Laboratory 21

Simplex: Simplex: Step Step33 Use the inner product rule to find the relative profit coefficients cB 0 0 0

Basis

x4 x5 x6 c row

cj

Constants

5 2 1 0 0 0 x1 x2 x3 x4 x5 x6 1 3 -1 1 0 0 0 1 1 0 1 0 3 1 0 0 0 1 5 2 1 0 0 0

6 4 7 Z=0

c j = c j − cB Pj c1 = 5 - 0(1) - 0(0) - 0(3) = 5 -> largest positive c2 = …. c3 = …. Step 4: Is this an optimal basic feasible solution? Optimization in Engineering Design

Georgia Institute of Technology Systems Realization Laboratory 22

Simplex: Simplex: Step Step55 Apply the minimum ratio rule to determine the basic variable to leave the basis. The new values of the basis variables: xi = b i

− a is x s

for i = 1, ..., m

 bi  max x s = min   a is > 0 a is   In our example: Row 1 2 3

Optimization in Engineering Design

Basic Variable x4 x5 x6

Ratio 6 7/3

Georgia Institute of Technology Systems Realization Laboratory 23

Simplex: Simplex: Step Step66 Perform the pivot operation to get the new tableau and the b.f.s.

New iteration: find entering variable:

c j = c j − c B Pj cB = (0 0 5)

c2 = 2 - (0) 8/3 - (0) 1 - (5) 1/3 = 1/3 c3 = 1 - (0) (-1) - (0) 1 - (5) 0 = 1 c6 = 0 - (0) 0 - (0) 0 - (5) 1/3 = -5/3 Optimization in Engineering Design

Georgia Institute of Technology Systems Realization Laboratory 24

Final Final Tableau Tableau x3 enters basis, x5 leaves basis

Wrong value! 4 should be 11/3

Optimization in Engineering Design

Georgia Institute of Technology Systems Realization Laboratory 25