Linear Programming:

Claudio Arbib

Università di L’Aquila

Operations Research

Linear Programming:

geometric issues

Contents

• Hyperplanes of IR

• Linear Programming: a geometric intuition

– a dynamic system viewed as an LP – the geometry of the dual problem – a more prosaic problem

– direction of improvement

• Directions of a polyhedron

– the recession cone and its features

• Weyl’s Theorem

• Fundamental Theorem of Linear Programming

Hyperplanes of IR ⁿ

3x

+ 4x

= 12 (3, 4) ⋅ (x

, x

) = 12

(3, 4)

x

x

(x

, x

)

Vector (3, 4) is orthogonal to the line 3x

+ 4x

= 12

An example

Hyperplanes of IR ⁿ

a

x

+ a

x

= b

2A

= b

/a

a

= dp

= √(b/a₂)² + (b/a₁)² = ^b√a1

2 + a₂² a₁a₂ b² a₁a₂

a₁a₂ b√a₁² + a₂²

d = 2A/p

√a₁² + a₂²

=

(a

, a

)⋅(x

, x

) = d|(a

, a

)|

b/a

b/a

d

p

d√a

+ a

=

x

x

In general

d

p

In generale

Hyperplanes of IR ⁿ

a

x

+ a

x

= b

= √(b/a₂)² + (b/a₁)² = ^b√a1

2 + a₂² a₁a₂ b² a₁a₂

a₁a₂ b√a₁² + a₂²

d = 2A/p

√a₁² + a₂²

=

(a

, a

)⋅(x

, x

) = d|a|

b/a

b/a

d√a

+ a

=

x

x

The hyperplane is the locus of all vectors x = (x

, …, x

) of IR

whose projection on the direction of versor u = (u

, …, u

) equals d (distance of the hyperplane from 0)

(x

, x

)

(u

, u

)

2A

= b

/a

a

= dp ( , )⋅(x

, x

) = d

|a| |a|

(u

, u

)

Galileiana

• Where does a point-shaped mass subject to gravity end, in a constrained space?

a11x

1 + a

12x

2 >

b1

a ²¹ x ¹+ a ²²

x ²

> b ²

min P = mgx

a

x

+ a

x

> b

…

a

x

+ a

x

> b

x

x

potential energy

( analysis of a dynamic system )

active constraints

min P = mgx

a

x

+ a

x

> b

…

a

x

+ a

x

> b

min P = mgx

u

x

+ u

x

> d

…

u

x

+ u

x

> d

u₁

Galileiana

x

x

a11x

1 + a

12x

2 >

b1

a ²¹ x ¹+ a ²²

x ²

> b ²

first active

constraint reaction

• What is the value of the reaction forces expressed by the constraints to withstand the force of gravity?

(u₁₁, u₁₂)

|force of gravity| = mg

u ²¹ x ¹+ u ²²

x ²

> d ²

u11x

1 + u

12x

2 >

d1

Let us normalize constraints by dividing inequalities by |a₁|, …, |a_m|: their

expression contains versors u₁, …, u_m

and the distances d₁, …, d_m of hyperplanes from the origin 0

x

|force of gravity| = mg

Galileiana

x

u11x

1 + u

12x

2 >

d1

min P = mgx

u

x

+ u

x

> d

…

u

x

+ u

x

> d

x ¹+ u ²² x ²

> d ²

second a ctive constra

int reac tion (u₂₁, u₂₂)

• What is the value of the reaction forces expressed by the constraints to

withstand the force of gravity?

x

Galileiana

x

min P = mgx

u

x

+ u

x

> d

…

u

x

+ u

x

> d

(u₁₁, u₁₂)

The horizontal components of the reaction counterwork:

y

u

+ y

u

+ … + u

y

= 0

• y

= intensity of the reaction force of constraint i

• y

= 0 for i = 3, …, m

(non-active constraints)

(u₂₁, u₂₂)

(u₂₁, u₂₂)

x

Galileiana

x

min P = mgx

u

x

+ u

x

> d

…

u

x

+ u

x

> d

(u₁₁, u₁₂)

The vertical components of reaction balance gravity:

y

u

+ y

u

+ … + y

u

= mg

• y

= intensity of the reaction force of constraint i

• y

= 0 for i = 3, …, m

(non-active constraints)

(u₂₁, u₂₂)

x

Galileiana

x

min P = mgx

u

x

+ u

x

> d

…

u

x

+ u

x

> d

(u₁₁, u₁₂)

y

u

+ y

u

+ … + y

u

= 0 y

u

+ y

u

+ … + y

u

= mg y

, y

, …, y

> 0

max y

d

+ y

d

+ … + y

d

• y

= intensity of the reaction force of constraint i

• y

= 0 for i = 3, …, m

(non-active constraints)

labor done by the constraints

potential energy d₂

equilibrium of the forces involved

Strong duality and

energy conservation

A more prosaic problem

Because the prices per kilogram are 24 € for a milfoil cake and 28€ for a profiterol, he wonders what amount of each cake would be convenient to make in order to maximize income

200 0

5 250

Profiterol 250

1000 100

20 3000

Ambry 1500

0 20

2 100

Milfoil 300

Cocoa (g) Vanilla (g)

Eggs (n.) Sugar (g)

Flour (g)

Ingredients per kg Cake

A confectioner prepares two types of cakes using some set of ingredients.

He finds in the ambry 1.5 kg of flour, 3.0 of sugar, 1.0 of cocoa, 20 eggs and

100 g of vanilla.

A more prosaic problem

200 0

5 250

Profiterol 250

1000 100

20 3000

Ambry 1500

0 20

2 100

Milfoil 300

Cocoa (g) Vanilla (g)

Eggs (n.) Sugar (g)

Flour (g)

Ingredients per kg Cake

The flour necessary to prepare x

kg of milfoil and x

kg of profiterol, expressed in grams, is given by:

300x₁

+

Such an amount must not exceed flour availability:

300x₁

+

< 1500

A more prosaic problem

For a feasible production one must then ensure:

300x

+ 250x

< 1500 100x

+ 250x

< 3000 2x

+ 5x

< 20

20x

< 100

200x

< 1000 with x

, x

> 0.

The objective of income maximization is then written as:

max 24x

+ 28x

A more prosaic problem

The problem constraints can be rewritten as follows:

6x

+ 5x

< 30 2x

+ 5x

< 60 2x

+ 5x

< 20

x

< 5

x

< 5 with x

, x

> 0.

Notice that the second inequality is dominated by the third, and therefore can be suppressed.

Let us draw the polyhedron of this LP in IR

.

x

x

A more prosaic problem

0 < x₁, x₂ < 5

6x1

+ 5x

2 <

30 2x1 + 5x

2 < 20

P

x

x

Direction of improvement

P

The locus of the points of IR

such that the objective function

f(x) = 24x

+ 28x

attains a given value k are represented by the line (isogram) having equation

x

= –

x

+

7

k

28

The intersection of the isogram and P collects the solutions with the same value k

112 84 56 28

k = 0

x

x

Direction of improvement

P

Since P is limited and non-empty the problem certainly has an

optimal finite-valued solution

In the present case, an optimal solution lies at the intersection of the lines

2x

+ 5x

= 20 6x

+ 5x

= 30

112 84 56 28

k = 0

It corresponds to the point x* having coordinates 5/2, 3 and its value is f(x*) = 144.

x

x

Direction of improvement

If the polyhedron P is not limited, then the problem can have a finite optimum or not, depending on

whether the objective function value increases along every half-line contained in P, or there exists a half- line contained in P along which the objective function gets an indefinite improvement

P

direction of improvement

To better specify this concept, let us introduce the notion of direction of a

polyhedron P

Direction of a polyhedron

Let P = P(A, b) ⊆ IR

be a polyhedron.

Definition: A vector d ∈ IR

is said to be a direction of P if for any x ∈ P and any λ ∈ IR one has

x + λ _{d ∈ P} Example 1: Let P be defined by inequalities

x

+ 3x

< 6 3x

+ 2x

< 6

x

> 0

P

The vector d = (–1, 1) is not a

direction of P, whereas vector

is

Direction of a polyhedron

Definition: The set of all the vectors that are directions of P is called the recession cone of P, and is denoted as rec(P).

Example 2:

3x

+ 2x

< 6 x

> 0 Let P be defined by inequalities

rec(P) P

3x

+ 2x

< 6 x

> 1

Direction of a polyhedron

Example 3: Let P be defined by inequalities

rec(P)

Note: rec(P) does not change and is not contained in P

P

Direction of a polyhedron

x

> 0 3x

+ 2x

< 6 x

> 1 Example 4: Let P be defined by inequalities

Note: rec(P) boils down to the set {0}

rec(P)

P

Features of the recession cone

Theorem 1 ∀ polyhedron P, rec(P) ≠ ∅

Proof: For any λ > 0 and x ∈ P one has x + λ 0 = x ∈ P. Hence 0 ∈ rec(P).

Theorem 2 Let P = {x ∈ IR

: Ax < b}. Then

rec(P) = {z ∈ IR

: Az < 0}

Proof: If z is such that Az < 0, then z is a direction of P:

Ax < b, Az < 0 Ax + λ Az = A(x + λ _{z) < b} ∀ λ > 0 Vice-versa, if z is a direction of P, then Az < 0:

(abs.) let A(x + λ z) < b ∀ λ > 0, but ∃i for which (Az)

> 0

then choosing λ _{> [b}

_{– (Ax)}

_]/(Az)

one gets out of P

Weyl’s Theorem

Notation: Let us denote as Ext(P) the set of the extreme points (vertices) of polyhedron P.

Theorem 2 (Weyl, 1936)

Any x in a polyhedron P = P(A, b) with Ext(P) ≠

can be expressed as the sum of a point u ∈ conv(Ext(P)) and a direction d ∈ rec(P):

P = conv(Ext(P)) + rec(P) Exercise:

P = {x ∈ IR

: – x

+ 2x

> 2, x

– x

> –2, 5x

+ 3x

> 15}

Ext(P) = {(

,

), (

,

)}

rec(P) = {x ∈ IR

: – x

+ 2x

> 0, x

– x

> 0, 5x

+ 3x

> 0}

• verify that (3, 3) ∈ P

• find u ∈ conv(Ext(P)), d ∈ rec(P) such that (3, 3) = u + d

2x

+ x

> 4

x

, x

> 0 Example 5: Let P be defined by inequalities x

+ x

> 3

rec(P) = {x∈IR²: x₁, x₂ > 0}

conv(Ext(P))

P

Ext(P) = {(0, 4), (1, 2), (3, 0)}

Weyl’s Theorem

Fundamental Theorem of LP

Consider the problem in general form

P: max cx

Ax < b

Theorem 3

Let P = {x ∈ IR

: Ax < b}, and x° ∈ P. Then 1) ∃d ∈ rec(P): cd > 0 P unbounded

2) ∀d ∈ rec(P), cd < 0 if Ext(P) ≠

, then P has an optimal

solution x* ∈ Ext(P).

2x

+ x

> 4

x

> 0, x

> 0 x

+ x

> 3

rec(P)

Example 6: Consider the problem P) max 3x

+ 2x

–2x

– x

< –4

–x

< 0, –x

< 0 – x

– x

< –3

P

For d = (1, 1) one has cd = 3⋅1 + 2⋅1 = 5 > 0

Hence P is unbounded

Fundamental Theorem of LP

i.e., max 3x

+ 2x

For any d ∈ rec(P) one now has cd < 0

2x

+ x

> 4

x

> 0, x

> 0 x

+ x

> 3

rec(P)

Example 7: Consider the problem P) min 4x

+ x

–2x

– x

< –4

–x

< 0, –x

< 0 – x

– x

< –3

P

Hence one of the red points is an optimal solution

Ext(P)

Teorema fondamentale della PL

i.e., max –4x

– x

Fundamental Theorem of LP

Proof:

1) ∃d ∈ rec(P): cd > 0 P unbounded

By definition of direction, x° ∈ P, d ∈ rec(P) x° + λ _{d ∈ P for any} λ _{> 0.}

By contradiction, let x* be optimal for P.

Then cx* > c(x° + λ _d).

But since cd > 0, this is clearly not true for every λ > 0: for instance, for λ > (cx* – cx°)/cd

Hence P is unbounded.

Fundamental Theorem of LP

2) ∀d ∈ rec(P), cd < 0 P has an optimal solution x* ∈ Ext(P)

Let E = Ext(P) = {v

, …, v

} and let k be such that cv

> cv

i = 1, …, p.

By Weyl’s Theorem, every x ∈ P can be written as x = u + d, with u ∈ conv(E) and d ∈ rec(P). Clearly

cx = cu + cd < cu (in fact by assumption cd < 0) Moreover

cu = c( λ

v

+ … + λ

v

)

with λ

_{+ … +} λ

_{= 1,} λ

_{, …,} λ

> 0 (in fact u ∈ conv(E)) Thus

cx < c( λ

v

+ … + λ

v

) = λ

cv

+ … + λ

cv

<

< ( λ

_{+ … +} λ

_)cv

_{= cv}

This then implies that v

∈ Ext(P) is an optimal solution for P.