[PDF] Linear Programming A feasible solution is a

View - Download Linear Programming

Previous PDF

Next PDF

Linear Programming

Neil Laws

TT 2010

1.11 Introduction

A general optimization problem is of the form: choosexto maximisef(x) subject tox2S where x= (x1;:::;xn)T, f:Rn!Ris theobjective function,

SRnis thefeasible set.

We might write this problem:

max xf(x) subject tox2S:

1.2For example

f(x) =cTxfor some vectorc2Rn,

S=fx:Ax6bgfor somemnmatrixAand some

vectorb2Rm.

Iffis linear andSRncan be described by linear

equalities/inequalities then we have alinear programming(LP) problem.

Ifx2Sthenxis called afeasible solution.

If the maximum off(x) overx2Soccurs atx=xthen

xis anoptimal solution, and f(x) is theoptimal value.

1.3Questions

In general:

does a feasible solutionx2Sexist? if so, does an optimal solution exist? if so, is it unique? 1.4

Example

A company produces drugsAandBusing machinesM1and

M 2.

1 ton of drugArequires 1 hour of processing onM1and 2

hours onM2

1 ton of drugBrequires 3 hours of processing onM1and 1

hour onM2

9 hours of processing onM1and 8 hours onM2are

available each day Each ton of drug produced (of either type) yields$1 million prot To maximise its prot, how much of each drug should the company make per day?

1.5Solution

Let x1= number of tons ofAproduced x2= number of tons ofBproduced

P1 : maximisex1+x2(prot in$million)

subject tox1+ 3x269 (M1processing)

2x1+x268 (M2processing)

x

1;x2>0

1.6x 1x 2x

1+ 3x2= 92x1+x2= 8x

1+x2= 5The shaded region is the feasible set forP1. The maximum

occurs atx= (3;2) with value 5.

1.7Diet problem

A pig-farmer can choose between four dierent varieties of food, providing dierent quantities of various nutrients. food required1 2 3 4amount/wk

A1:5 2:0 1:0 4:14:0

nutrientB1:0 3:1 0 2:08:0 C4:2 1:5 5:6 1:19:5cost/kg$5$7$7$9The (i;j) entry is the amount of nutrientiper kg of foodj. 1.8

ProblemP2:

minimise 5x1+ 7x2+ 7x3+ 9x4 subject to 1:5x1+ 2x2+x3+ 4:1x4>4 x

1+ 3:1x2+ 2x4>8

4:2x1+ 1:5x2+ 5:6x3+ 1:1x4>9:5

x

1; x2; x3; x4>0

1.9General form of the diet problem

Foodsj= 1;:::;n, nutrientsi= 1;:::;m.

Data: aij= amount of nutrientiin one unit of foodj bi= required amount of nutrienti cj= cost per unit of foodj

Letxj= number of units of foodjin the diet.

The diet problem is

minimisec1x1++cnxn subject toai1x1++ainxn>bifori= 1;:::;m x

1;:::;xn>0:

1.10In matrix notation the diet problem is

min xcTxsubject toAx>b,x>0.

Note that our vectors are always column vectors.

We writex>0to meanxi>0 for alli. (0is a vector of zeros.)

SimilarlyAx>bmeans (Ax)i>bifor alli.

1.11Real applications

\Programming" = \planning"

Maybe many thousands of variables or constraints

Production management: realistic versions ofP1, large manufacturing plants, farms, etc

Scheduling, e.g. airline crews:

need all ights covered restrictions on working hours and patterns minimise costs: wages, accommodation, use of seats by non-working sta shift workers (call centres, factories, etc) Yield management (airline ticket pricing: multihops, business/economy mix, discounts, etc) Network problems: transportation capacity planning in telecoms networks Game theory: economics, evolution, animal behaviour 1.12

Free variables

Some variables may be positive or negative, e.g. omit the constraintx1>0.

Such afree variablecan be replaced by

x

1=u1v1

whereu1;v1>0.

1.13Slack variables

InP1 we had

maximisex1+x2 subject tox1+ 3x269

2x1+x268

x

1;x2>0:

We can rewrite by

maximisex1+x2 subject tox1+ 3x2+x3= 9

2x1+x2+x4= 8

x

1;:::;x4>0:

x3= unused time on machineM1 x4= unused time on machineM2 x

3andx4are calledslack variables.

1.14With the slack variables included, the problem has the form

max xcTxsubject toAx=b x>0:

1.15Two standard forms

In fact any LP (with equality constraints, weak inequality constraints, or a mixture) can be converted to the form max xcTxsubject toAx=b x>0 since: minimisingcTxis equivalent to maximisingcTx, inequalities can be converted to equalities by adding slack variables, free variables can be replaced as above. 1.16

Similarly, anyLPcan be put into the form

max xcTxsubject toAx6b x>0 since e.g.

Ax=b()(Ax6b

Ax6b (more ecient rewriting may be possible!). So it isOKfor us to concentrate onLPs in these forms.

1.17Remark

We always assume that the underlying space isRn.

In particularx1;:::;xnneed not be integers. If we restrict to x2Znwe have aninteger linear program(ILP). ILPs are in some senseharderthanLPs. Note that the optimal value of anLPgives aboundon the optimal value of the associatedILP. 1.18

1.191.20

2 Geometry of linear programming

Denition 2.1

A setSRnis calledconvexif for allu;v2Sand all

2(0;1), we haveu+ (1)v2S.uv

convexv u convexuv not convex That is, a set is convex if all points on the line segment joining uandvare inS, for all possible line segments.

2.1For now we will considerLPs in the form

maxcTxsubject toAx=b x>0:

2.2Theorem 2.2

The feasible set

S=fx2Rn:Ax=b;x>0g

is convex.Proof.

Supposeu;v2S,2(0;1). Letw=u+ (1)v. Then

Aw=A[u+ (1)v]

=Au+ (1)Av = [+ (1)]b =b andw>0+ (1)0=0. Sow2S.2.3Extreme points

Denition 2.3

A pointxin a convex setSis called anextreme pointofSif there are no two distinct pointsu;v2S, and2(0;1), such thatx=u+ (1)v.That is, an extreme pointxis not in the interior of any line segment lying inS.2.4

Theorem 2.4

If anLPhas an optimal solution, then it has an optimal solution at an extreme point of the feasible set.Proof. Idea: If the optimum is not extremal, it's on some line withinS all of which is optimal: go to the end of that line, repeat if necessary. Since there exists an optimal solution, there exists an optimal solutionxwith a minimal number of non-zero components.

Supposexis not extremal, so that

x=u+ (1)v for someu6=v2S,2(0;1).2.5Sincexis optimal,cTu6cTxandcTv6cTx.

But alsocTx=cTu+(1)cTvso in factcTu=cTv=cTx.

Now consider the line dened by

x(") =x+"(uv); "2R: Then (a)Ax=Au=Av=bsoAx(") =bfor all", (b)cTx(") =cTxfor all", (c)ifxi= 0 thenui=vi= 0, which impliesx(")i= 0 for all", (d)ifxi>0 thenx(0)i>0, andx(")iis continuous in".

2.6So we can increase"from zero, in a positive or a negative

direction as appropriate, until at least one extra component of x(") becomes zero. This gives an optimal solution with fewer non-zero components thanx.

Soxmust be extreme.2.7Basic solutions

Letaibe theith column ofA, so that

Ax=b()nX

i=1x iai=b:Denition 2.5 (1)A solutionxofAx=bis called abasic solutionif the vectorsfai:xi6= 0gare linearly independent. (That is, columns ofAcorresponding to non-zero variables x iare linearly independent.) (2)A basic solution satisfyingx>0is called abasic feasible solution(BFS).Note: IfAhasmrows, then at mostmcolumns can be linearly independent. So any basic solutionxhas at leastnmzero components. More later. 2.8

Theorem 2.6

xis an extreme point of

S=fx:Ax=b;x>0g

if and only ifxis aBFS.Proof. (1)Letxbe aBFS. Supposex=u+ (1)vforu;v2S,

2(0;1). To showxis extreme we need to showu=v.

LetI=fi:xi>0g. Then

(a)ifi62Ithenxi= 0, which impliesui=vi= 0.2.9(b)Au=Av=b, soA(uv) =0 =)nX i=1(uivi)ai=0 =)X i2I(uivi)ai=0sinceui=vi= 0 fori62I which impliesui=vifori2Isincefai:i2Igare linearly independent.

Henceu=v, soxis an extreme point.

2.10(2)SupposexisnotaBFS, i.e.fai:i2Igare linearly

dependent.

Then there existsu6=0withui= 0 fori62Isuch that

Au=0.

For small enough",x"uare feasible, and

x=12 (x+"u) +12 (x"u) soxis not extreme.2.11Corollary 2.7 If there is an optimal solution, then there is an optimalBFS.Proof.

This is immediate from Theorems 2.4 and 2.6.2.12

Discussion

Typically we mayassume:

n > m(more variables than constraints), Ahas rankm(its rows are linearly independent; if not, either we have a contradiction, or redundancy). Then:xis a basic solution()there is a setB f1;:::;ng of sizemsuch that xi= 0 ifi62B, fai:i2Bgare linearly independent.Proof. Simple exercise. TakeI=fi:xi6= 0gand augment it to a larger linearly independent setBif necessary.2.13Then to look for basic solutions: choosenmof thenvariables to be 0 (xi= 0 fori62B), look at remainingmcolumnsfai:i2Bg. Are they linearly independent? If so we have an invertible mmmatrix.

Solve forfxi:i2Bgto giveP

i2Bxiai=b.

So also

Ax=nX i=1x iai=nX i62B0ai+nX i2Bx iai =bas required:

This way we obtain all basic solutions (at most

n mof them).

2.14Badalgorithm:

look through all basic solutions, which are feasible? what is the value of the objective function?

We can do much better!

Simplex algorithm:

will move from oneBFSto another, improving the value of the objective function at each step. 2.15 2.16

3 The simplex algorithm (1)

The simplex algorithm works as follows.

1.Start with an initialBFS.

2.Is the currentBFSoptimal?

3.IfYES, stop.

IfNO, move to a new and improvedBFS, then return to 2. From Corollary 2.7, it is sucient to consider onlyBFSs when searching for an optimal solution.

3.1RecallP1, expressed without slack variables:

maximisex1+x2 subject tox1+ 3x269

2x1+x268

x

1;x2>0

3.2 x 1x 2x

1+ 3x2= 92x1+x2= 8ABE

DFC

3.3Rewrite:

x

1+3x2+x3= 9 (1)

2x1+x2+x4= 8 (2)

x

1+x2=f(x) (3)

Putx1;x2= 0, givingx3= 9,x4= 8,f= 0 (we're at theBFS x= (0;0;9;8)). Note: In writing the three equations as (1){(3) we are eectively expressingx3;x4;fin terms ofx1;x2. 3.4

1.Start at the initialBFSx= (0;0;9;8), vertexA, wheref= 0.

2.From (3), increasingx1orx2will increasef(x). Let's

increasex1. (a)From (1): we can increasex1to 9, if we decreasex3to 0. (b)From (2): we can increasex1to 4, if we decreasex4to 0.

Thestricterrestriction onx1is (b).

3.So (keepingx2= 0),

(a)increasex1to 4, decreasex4to 0 { using (2), this maintains equality in (2), (b)and, using (1), decreasingx3to 5 maintains equality in (1). With these changes we move to a new and improvedBFS x= (4;0;5;0),f(x) = 4, vertexD.

3.5To see if this newBFSis optimal, rewrite (1){(3) so that

each non-zero variable appears in exactly one constraint, fis in terms of variables which are zero at vertexD. Alternatively, we want to expressx1;x3;fin terms ofx2;x4.

How? Add multiples of (2) to the other equations.

3.6(1)12

(2) :52 x2+x312 x4= 5 (4) 12 (2) :x1+12 x2+12 x4= 4 (5) (3)12 (2) :12 x212 x4=f4 (6)

Nowf= 4 +12

x212 x4.

So we should increasex2to increasef.

3.71

0.We are at vertexD,x= (4;0;5;0) andf= 4.

2

0.From (6), increasingx2will increasef(increasingx4would

decreasef). (a)From (4): we can increasex2to 2, if we decreasex3to 0. (b)From (5): we can increasex2to 8, if we decreasex1to 0.

Thestricterrestriction onx2is (a).

3

0.So increasex2to 2, decreasex3to 0 (x4stays at 0, and from

(5)x1decreases to 3).

With these changes we move to theBFSx= (3;2;0;0),

vertexC. 3.8 Rewrite (4){(6) so that they correspond to vertexC: 25
(4) :x2+25 x315 x4= 2 (7) (5)15 (4) :x115 x3+35 x4= 3 (8) (6)15 (4) :15 x325 x4=f5 (9) 1

00.We are at vertexC,x= (3;2;0;0) andf= 5.

2

00.We have deducedf= 515

x325 x465.

Sox3=x4= 0 is the best we can do!

In that case we can read ox1= 3 andx2= 2.

Sox= (3;2;0;0), which hasf= 5, is optimal.

3.9Summary

At each stage:

B= `basic variables',

we expressxi,i2Bandfin terms ofxi,i62B, settingxi= 0,i62B, we can read ofandxi,i2B(gives aBFS!).

At each update:

look atfin terms ofxi,i62B, whichxi,i62B, would we like to increase? if none,STOP! otherwise, choose one and increase it as much as possible, i.e. until one variablexi,i2B, becomes 0.

3.10Summary continued

So one new variableentersB(becomes non-zero, becomes basic), another oneleavesB(becomes 0, becomes non-basic).

This gives a newBFS.

We update our expressions to correspond to the newB.

3.11Simplex algorithm

We can write equations

x

1+3x2+x3= 9 (1)

2x1+x2+x4= 8 (2)

x

1+x2=f0 (3)

as a `tableau' x

1x2x3x4

1 3 1 091

2 1 0 1821 1 0 003

This initial tableau represents theBFSx= (0;0;9;8) at which f= 0. Note the identity matrix in thex3;x4columns (rst two rows), and the zeros in the bottom row below it. 3.12

The tableau

At a given stage, the tableau has the form

(a ij)b c Tf which meansAx=b f(x) =c Txf

We start fromA=A,b=b,c=candf= 0.

Updating the tableau is calledpivoting.

3.13To update (`pivot')

1.Choose a pivot column

Choose ajsuch thatc

j>0 (corresponds to variablexj= 0 that we want to increase).

Here we can takej= 1 .

2.Choose a pivot row

Among thei's witha

ij>0, chooseito minimizeb i=a ijquotesdbs_dbs6.pdfusesText_11

[PDF] basic feasible solution linear programming example

[PDF] basic feasible solution pdf

[PDF] basic feasible solution vs feasible solution

[PDF] basic formatting in microsoft word formatting exercises

[PDF] basic french course pdf

[PDF] basic french language learning pdf

[PDF] basic french lessons for beginners pdf

[PDF] basic french premium second edition pdf

[PDF] basic french vocabulary list pdf

[PDF] basic french words with pictures

[PDF] basic german language pdf

[PDF] basic german words

[PDF] basic grammar english for beginners

[PDF] basic grammar english to hindi

[PDF] basic grammar in english