Math 407A: Linear Optimization - University of Washington

Math 407A: Linear Optimization

Lecture 4: LP Standard Form 2

2Author: James Burke, University of Washington Lecture 4: LP Standard Form 3

Math 407A: Linear Optimization

1 / 27

1 LPs in Standard Form 2 Minimization maximization 3 Linear equations to linear inequalities 4 Lower and upper bounded variables 5 Interval variable bounds 6 Free variable 7 Two Step Process to Standard Form

Lecture 4: LP Standard Form 4

Math 407A: Linear Optimization

2 / 27

LPs in Standard Form

We say that an LP is in standard form if its matrix representation has the form

Lecture 4: LP Standard Form 5

Math 407A: Linear Optimization

3 / 27

LPs in Standard Form

We say that an LP is in standard form if its matrix representation has the form

max cT x s.t. Ax b

0x

5Author: James Burke, University of Washington Lecture 4: LP Standard Form 5

Math 407A: Linear Optimization

3 / 27

LPs in Standard Form

We say that an LP is in standard form if its matrix representation has the form

max cT x s.t. Ax b

0x

It must be a maximization problem.

5Author: James Burke, University of Washington Lecture 4: LP Standard Form 5

Math 407A: Linear Optimization

3 / 27

LPs in Standard Form

We say that an LP is in standard form if its matrix representation has the form

max cT x s.t. Ax b

0x

It must be a maximization problem. Only inequalities of the correct direction.

5Author: James Burke, University of Washington Lecture 4: LP Standard Form 5

Math 407A: Linear Optimization

3 / 27

LPs in Standard Form

We say that an LP is in standard form if its matrix representation has the form

max cT x s.t. Ax b

0x

It must be a maximization problem. Only inequalities of the correct direction. All variables must be non-negative.

5Author: James Burke, University of Washington Lecture 4: LP Standard Form 6

Math 407A: Linear Optimization

3 / 27

Every LP can be Transformed to Standard Form

Lecture 4: LP Standard Form 7

Math 407A: Linear Optimization

4 / 27

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download