Copyright notice. Optimalisatietechnieken. Simplex-methode: principe. Lineair programmeren. x 3 optimum. x (6) A x (5) x (4) x 1

versie: 14/2/2012

© W. Philips, Universiteit Gent, 1998-2012

Copyright notice

Didactisch materiaal bij de cursus

Optimalisatietechnieken http://telin.UGent.be/~philips/optimalisatie/ Academiejaar 2011-2012

Prof. dr. ir. W. Philips [email protected] Tel: 09/264.33.85 Fax: 09/264.42.95

UNIVERSITEIT GENT Telecommunicatie en Informatieverwerking

This powerpoint presentation was developed as an educational aid to the renewed course “Optimisation Techniques” (Optimalisatietechnieken), taught at the University of Gent, Belgium as of 1998. This presentation may be used, modified and copied free of charge for non-commercial purposes by individuals and non-for-profit organisations and distributed free of charge by individuals and non-for-profit organisations to individuals and non-for-profit organisations, either in electronic form on a physical storage medium such as a CD-rom, provided that the following conditions are observed: 1. If you use this presentation as a whole or in part either in original or modified form, you should include the copyright notice “© W. Philips, Universiteit Gent, 1998” in a font size of at least 10 point on each slide; 2. You should include this slide (with the copyright conditions) once in each document (by which is meant either a computer file or a reproduction derived from such a file); 3. If you modify the presentation, you should clearly state so in the presentation; 4. You may not charge a fee for presenting or distributing the presentation, except to cover your costs pertaining to distribution. In other words, you or your organisation should not intend to make or make a profit from the activity for which you use or distribute the presentation; 5. You may not distribute the presentations electronically through a network (e.g., an HTTP or FTP server) without express permission by the author. In case the presentation is modified these requirements apply to the modified work as a whole. If identifiable sections of that work are not derived from the presentation, and can be reasonably considered independent and separate works in themselves, then these requirements do not apply to those sections when you distribute them as separate works. But when you distribute the same sections as part of a whole which is a work based on the presentation, the distribution of the whole must be on the terms of this License, whose permissions for other licensees extend to the entire whole, and thus to each and every part regardless of who wrote it. In particular note that condition 4 also applies to the modified work (i.e., you may not charge for it). “Using and distributing the presentation” means using it for any purpose, including but not limited to viewing it, presenting it to an audience in a lecture, distributing it to students or employees for self-teaching purposes, ... Use, modification, copying and distribution for commercial purposes or by commercial organisations is not covered by this licence and is not permitted without the author’s consent. A fee may be charged for such use. Disclaimer: Note that no warrantee is offered, neither for the correctness of the contents of this presentation, nor to the safety of its use. Electronic documents such as this one are inherently unsafe because they may become infected by macro viruses. The programs used to view and modify this software are also inherently unsafe and may contain bugs that might corrupt the data or the operating system on your computer. If you use this presentation, I would appreciate being notified of this by email. I would also like to be informed of any errors or omissions that you discover. Finally, if you have developed similar presentations I would be grateful if you allow me to use these in my course lectures. Prof. dr. ir. W. Philips Department of Telecommunications and Information Processing University of Gent St.-Pietersnieuwstraat 41, B9000 Gent, Belgium

E-mail: [email protected] Fax: 32-9-264.42.95 Tel: 32-9-264.33.85

02c.2

versie: 14/2/2012


Simplex-methode: principe x3

© Rardin, fig. 5.7

Kost: -x3

optimum

x(6) A

Randvoorwaarden: A-L x1, x2, x3 ≥ 0

x(5)

x(4)

Lineair programmeren B Theorie en voorbeelden

C

F

x1

x(3) x(2) D

H

G I

x2

E

x(1)

L J

x(0)

verbeterende kost

K ribben uit x(0)

02c.4

versie: 14/2/2012


versie: 14/2/2012


Overzicht

Extreme punten

Kernvraag (vermits het simplexalgoritme van het ene naar het andere extreem punt stapt) •hoe vinden we extreme punten, uitgaande van de opgegeven gelijkheden en ongelijkheden? •hoe gaan we van één extreem punt naar een ander? Om deze vraag gemakkelijker te kunnen beantwoorden •conversie van het probleem naar “standaardvorm”

E

n=3

•definitie van basisoplossingen (speciale punten, waarvan sommige extreme punten zijn) •definitie van simplexrichtingen (speciale ribben) Beschrijving van het simplexalgoritme

02c.5

versie: 14/2/2012

F

gebied van mogelijke oplossingen


E D

A, B, C

A B C

A, B F

extreem punt naburige extreme punten ribbe bepaald door A en E

n=3

Naburige extreme punten kunnen worden bepaald door stelsels actieve (on)gelijkheden, die maar in één (on)gelijkheid verschillen Het omgekeerde geldt niet: b.v. A,C,D bepaalt een extreem punt en F,C,D bepaalt een punt dat niet extreem is Ribben zijn lijnstukken tussen naburige extreme punten Elke ribbe ligt op een rechte bepaald door n-1 lineair onafhankelijke actieve ongelijkheden en/of gelijkheden Niet elk stelsel van n-1 lineair onafhankelijke actieve ongelijkheden bevat echter een ribbe (b.v. D,F) 02c.7

B

x2

extreem punt

x1

n: aantal variabelen

C Een ongelijkheid is actief in een mogelijke oplossing als ze daar als gelijkheid is voldaan (een gelijkheid is altijd actief) •b.v.: in het blauw extreem punt zijn A,B,C,D en E actief Elk extreem punt is uniek bepaald door n lineair onafhankelijke actieve ongelijkheden en/of gelijkheden (want n hypervlakken bepalen één punt in een n-dimensionale ruimte) •b.v.: het blauw punt is bepaald door A,B,C of A,B,D, of ... Niet elk stelsel van n lineair onafhankelijke actieve ongelijkheden en/of gelijkheden bepaalt echter een extreem punt •b.v.: C,D,F bepalen wel een punt maar geen extreem punt

02c.6

versie: 14/2/2012


Naburige extreme punten en ribben F

D

x3

A

Standaardvorm van LP Een LP-probleem is in standaardvorm als •geen enkele variabele xj negatief mag zijn: xj ≥ 0 •er geen andere ongelijkheden zijn n

Dus: maximaliseer (of minimaliseer) voorwaarde dat n

(S):

∑a x ij

j =1

j

= bi

∑c x

i = 1, , m en

j

j

onder de

j =1

∀j : x j ≥ 0

Elk LP-probleem kan in standaardvorm worden gebracht door toevoegen van (artificiële) reservevariabelen (slack variables) We veronderstellen nu dat het stelsel (S) meer dan 1 oplossing heeft (zoniet is het probleem triviaal), en dat de vergelijkingen lineair onafhankelijk zijn (zoniet kleine aanpassingen nodig) 02c.8

versie: 14/2/2012


versie: 14/2/2012


Standaardvorm: voorbeeld x1 ≤ 1000 x1 + x2 ≤ 1750 4 x1 + 2 x2 ≥ 4800 x1 ≥ 0 x2 willekeurig

x1 + x3 = 1000 x1 + x2 + x4 = 1750

Grafische voorstelling x3 ≥ 0 x4 ≥ 0

4 x1 + 2 x2 − x5 = 4800 x5 ≥ 0 x1 ≥ 0 x2 → x6 − x7 x6 ≥ 0 x7 ≥ 0

De waarde van een reservevariabele geeft de marge aan waarmee de corresponderende ongelijkheid is voldaan Meestal willen we de constante rechterleden positief houden; het is dan soms nodig reservevariabelen met een minteken toe te voegen Eventuele overblijvende variabelen xj waarvoor er uiteindelijk geen beperking xj≥0 aanwezig is worden overal vervangen door het verschil van 2 niet-negatieve variabelen Nadeel standaardvorm: veel meer variabelen 02c.9

versie: 14/2/2012


2000

Niet elk stel van n-m nulvariabelen bepaalt echter een extreem punt (ze bepalen b.v. een punt dat niet voldoet aan alle “niet-negatief” voorwaarden) 02c.11

A

B

toenemende winst

1000

F

Originele beperkingen: A: x1 ≤ 1000 B: x2 ≤ 1500 C: x1+x2 ≤ 1750 D: 4x1+2x2 ≤ 4800 E: x1 ≥ 0 F: x2 ≥ 0

Standaardvorm: x1+x3 = 1000 x2+x4 = 1500 C (S) x +x +x =1750 1 2 5 4x1+2x2+x6 = 4800 2000 x1 A: x3 ≥ 0 B: x4 ≥ 0 …

E

1000

De standaardvorm is 6-dimensionaal maar we kunnen nog steeds een 2-D voorstelling gebruiken: dit is dan een soort projectie 02c.10

versie: 14/2/2012

Belang van de standaardvorm Extreme punten kunnen nog steeds worden bepaald door een aantal actieve lineair onafhankelijke (on)gelijkheden, n.l. • alle m vergelijkingen van het stelsel (S), want vergelijkingen zijn overal actief (en lineair onafhankelijk) • aangevuld met voldoende actieve “niet-negatief” voorwaarden (n-m als er n variabelen zijn) Voorwaarde xj ≥ 0 actief ⇔ xj = 0 (zeer eenvoudig!) Besluit: elk extreem punt kan uniek worden bepaald door het opgeven van n-m variabelen die in dat punt nul zijn • er zijn m.a.w. geen andere punten die aan (S) voldoen, en waarin de opgegeven coördinaten (variabelen) nul zijn • het aantal op te geven nulvariabelen=het totaal aantal variabelen - het aantal vergelijkingen in (S)

D

x2

x4 ≥ 0 en (S)


Extreme punten en standaardvorm 2000

D

x2

A

1 1000

3

E

2 F

1000

extreme punten 1 x4=0, x5=0, (S)

2 x3=0, x6=0, (S)

x4 = 0, (S) B

toenemende winst



x5 = 0, (S)

geen extreme punten x3=0, x5=0, (S) 3 (wel basisoplossing)

x4=0, x2=0, (S)

geen snijpunt

02c.12

versie: 14/2/2012


versie: 14/2/2012


Basisoplossingen...

Geldige basis

Beschouw het stelsel van een probleem in standaardvorm n

∑ aij x j = bi

i = 1, h , m

j =1

Kies n-m variabelen xj Los nu het stelsel op met als bijkomende voorwaarden dat deze n-m variabelen xj nul moeten zijn

a11 a12 a13 a14 a15 a21 a22 a23 a24 a25 a31 a32 a33 a34 a35 Ab

Anb xnb

x1 x2 x3 x4 x5

b1 = b2 b3

⇔

Ab xb+Anb xnb=b ⇔ xb=Ab-1(b-Anb xnb) enkel als det(Ab) ≠ 0!

Als er een oplossing bestaat en als ze uniek is dan noemen we de oplossing een basisoplossing en dan noemen we •de variabelen die men nul stelt: niet-basisvariabelen (NB) •de andere variabelen: basisvariabelen (B)

Anb: kolommen van A corresponderend met NB-variabelen Ab: kolommen van A corresponderend met B-variabelen xb, xnb: vector van de NB-variabelen

Opmerkingen •Extreme punten zijn basisoplossingen maar niet omgekeerd •niet elk stel van n-m variabelen zijn geldige NB-variabelen

Er is een unieke oplossing voor xnb=0 ⇔ Ab is inverteerbaar ⇔ de kolommen van Ab vormen een basis ⇔ det(Ab)≠0

02c.13

versie: 14/2/2012


Basisoplossingen en extreme punten gebied van mogelijke oplossingen

n=3

F E D

x3

A B

x1

x2

extreem punt

n: aantal variabelen

C

Elk extreem punt is uniek bepaald door n lineair onafhankelijke actieve ongelijkheden en/of gelijkheden •b.v.: het blauw punt is bepaald door A,B,C of A,B,D, of ... Elk stelsel van n lineair onafhankelijke actieve ongelijkheden en/of gelijkheden bepaalt één punt; dit is een basisoplossing Niet elke basisoplossing is een extreem punt •b.v.: C,D,F bepalen een basisoplossing maar geen extreem punt; reden: deze basisoplossing ligt buiten het gebied van mogelijke oplossingen 02c.15

Nodige voorwaarde: evenveel B-variabelen als vergelijkingen

versie: 14/2/2012

02c.14


Basisoplossingen en extreme punten Een basisoplossing is niet noodzakelijk een oplossing •ze voldoen enkel aan de gelijkheden •maar niet aan alle “niet-negatief” voorwaarden Een mogelijke basisoplossing (basic feasible solution) •voldoet bovendien aan de niet-negativiteitsvoorwaarden •en is dus wel een oplossing De mogelijke basisoplossingen zijn de extreme punten Een gegeven basisoplossing kan met meer dan 1 basis corresponderen (gedegenereerdheid; zie verder)

Ax=b x≥0

Ax=b xb ≥ 0 xnb ≠ 0

mogelijke oplossingen

Ax=b Ax=b Ax=b ∃ xnb= 0: ...∃ xnb = 0: ... ∃ xnb = 0: xb ≥ 0 xb ≥ 0 xb uniek extreme punten

basisoplossingen

02c.16

versie: 14/2/2012


versie: 14/2/2012

Basissen: voorbeeld...

...Basissen: voorbeeld...

Trofeeprobleem: Maximaliseer 12 x1+9 x2 waarbij

x1

+x3

x2 +x4 x1 + x2 +x5 4 x1 +2 x2 x1, x2 , x3 , x4 , x5 , x6 ≥ 0



= 1000 = 1500 = 1750 +x6= 4800

x1

+x3

x2 +x4 x1 + x2 +x5 4 x1 +2 x2 x1 , x2 , x3 , x4 , x5 , x6 ≥ 0

= 1000 = 1500 = 1750 +x6= 4800

4 vergelijkingen, 6 onbekenden ⇒ 2 NB-variabelen


Probeer x5=x6 =0 ⇒ unieke oplossing (650,1100,350,400,0,0)

Probeer x3=x5 =0 ⇒ unieke oplossing (1000,750,0,750,0,-700)

⇒ { x5, x6 } is een geldig stel NB-variabelen en { x1 , x2 , x3 , x4 } is het bijbehorend stel B-variabelen Deze basisoplossing is ook een extreem punt want geen enkele variabele is negatief! 02c.17

versie: 14/2/2012


...Basissen: voorbeeld... +x3

+(0) x(0) +x 2 4 x1 + x(0) +x5 2 x2 4 x1 +2 2(0) x1 , x2 , x3 , x4 , x5 , x6 ≥ 0

(geen oplossing)

02c.18

versie: 14/2/2012


...Basissen: voorbeeld Indien er een lichtjes verschillend stelsel had gestaan…


x1

⇒ { x3, x5 } is een geldig stel NB-variabelen en { x1 , x2 , x4 , x6 } is het bijbehorend stel B-variabelen Deze basisoplossing is geen extreem punt!

x1

= 1000 = 1500 = 1750 +x6= 4800

+x3

+(0) x(0) +x 2 4 x1 + x(0) +x5 2 x2 4 x1 +2 2(0) x1 , x2 , x3 , x4 , x5 , x6 ≥ 0

= 1000 = 0 = 1750 +x6= 4800



NB={ x4 }; B={ x1 , x2 , x3 , x5 , x6 } (geen unieke oplossing)

NB={x2 , x4}; B={x1 , x3 , x5 , x6}

NB={x2 , x4}; B={x1 , x3 , x5 , x6}

⇒{ x2 , x4 } nog steeds geen geldig stel NB-variabelen! De waarde van de rechterleden heeft geen belang voor wat betreft de geldigheid (controleer!)

(geen oplossing)

Besluit: niet zomaar elk stel variabelen zijn NB-variabelen

02c.19

(oneindig veel oplossingen)

02c.20

versie: 14/2/2012


versie: 14/2/2012

Simplexmethode: basisprincipe Vind een extreem punt

x(0)

Ga van een extreem punt x(i+1) met een betere kost

Extreme punten en standaardvorm 2000

(zie verder)

x(i)


naar een naburig extreem punt

D

x2


x4 = 0, (S)

A

B

1 2

x(i)

(gekozen uit een •Beschouw hiervoor een ribbe uit beperkte set van zogenaamde simplexrichtingen) •indien de kost langs deze ribbe verbetert, kies dan het eindpunt van die ribbe als volgend extreem punt x(i+1); indien er geen eindpunt is dan is de optimale kost ±∞ •Zoniet, probeer een nieuwe ribbe

1000


E

Indien er geen verbeterende ribben zijn, dan is x(i) optimaal (Reden: zie verder )

x5 = 0, (S) F

1000

punt op simplexrichting 1 2 x4>0, x5=0, (S)

extreem punt 1 x4=0, x5=0, (S)

02c.21

versie: 14/2/2012


Simplex-richtingen in standaardvorm Hoe vinden we enkele ribben uit een extreem punt x ? extreem punt x: Ax=b xb ≥ 0 xnb = 0 Als we een ongelijkheid inactief laten worden dan vormen de oplossingen een rechte door x die mogelijks een ribbe bevat ⇒ een dergelijke rechte heet een simplexrichting We bereiken een punt op de ribbe door 1 component van xnb strikt groter dan 0 te maken (=1 ongelijkheid deactiveren) j-de positie Richting j: Extreem punt:

xnb =0 xb =Ab-1(b-Anb xnb) =Ab-1b xb ≥ 0

rnb(λ) =λ(0…1…0)t

λ≥0

rb(λ) =Ab-1(b-Anb rnb(λ)) λ ∈ [ 0, λmax] λmax is de grootste waarde ribbe-gedeelte van de simplexvan λ waarvoor rb(λ) ≥ 0 richting Altijd: λmax ≥ 0 want rb(0)=xb ≥ 0; meestal: λmax > 0 02c.23

02c.22

versie: 14/2/2012


Simplexrichtingen en ribben gebied van mogelijke oplossingen

F E D

A B C

R3 x3 x1

x2

extreem punt

n=3 variabelen

R1

In het blauw extreem punt zijn er 5 ribben De variabelen xa, xb, xc corresponderend met de ongelijkheden A,B en C zijn geldige NB-variabelen Ze definiëren 3 simplexrichtingen: xa ≥ 0, xb=0, xc=0 ⇒ lijnstuk bepaald door B en C ⇒ ribbe R1

xa=0, xb ≥ 0, xc=0 ⇒ punt bepaald door A en C ⇒ λmax = 0 xa=0, xb=0, xc ≥ 0 ⇒ lijnstuk bepaald door A en B ⇒ ribbe R3

⇒ de simplexrichtingen geven maar 2 van de 5 echte ribben, plus nog een gedegenereerde ribbe (met λmax = 0) 02c.24

versie: 14/2/2012


...Simplexrichtingen en ribben gebied van mogelijke oplossingen

R’1

R’3 x3

F E D

A B

x1

gebied van mogelijke oplossingen

n=3 variabelen

Andere NB-variabelen geven andere simplexrichtingen en ribben b.v. xa, xe, xd definiëren 3 andere simplexrichtingen: xa ≥ 0, xe=0, xd=0 ⇒ lijnstuk bepaald door E en D ⇒ ribbe R’1 xa=0, xe ≥ 0, xd=0 ⇒ punt bepaald door A en D ⇒ λmax = 0 xa=0, xe=0, xd ≥ 0 ⇒ lijnstuk bepaald door A en E ⇒ ribbe R’3 Besluit: als we om één of andere reden alle ribben nodig hebben dan zullen we verschillende basissen moeten beschouwen 02c.25


...Gedegenereerde extreme punten x2

A: x4 =0 B: x5 =0

x1

E

x3

A B

x1

x2

extreem punt

n=3 variabelen

C

In het blauw extreem punt zijn 5 ongelijkheden actief ⇒ in standaardvorm zijn daar 5 variabelen nul Anderzijds zijn 3 actieve ongelijkheden (b.v. A,B,C) voldoende om het extreem punt vast te leggen ⇒ in standaardvorm zijn er 3 NB-variabelen Besluit: er zijn ook nog 5 - 3 = 2 B-variabelen nul ⇒ Gedegenereerd extreem punt: extreem punt waarin naast de NB-variabelen ook een aantal B-variabelen nul zijn

02c.26

versie: 14/2/2012


Extreme punten en simplexrichtingen

0 ≤ x1 ≤ 1 0 ≤ x2 ≤ 1

gedegenereerd extreem punt x1 +x3 =1 x2 +x4 =1

x1+x2 ≤ 2

x1+x2+x5 =2

mogelijke oplossingen

F

D

C

versie: 14/2/2012


Definitie: Gedegenereerd extreem punt

extreem punt

x2

versie: 14/2/2012

Besluit: een basisoplossing x •moet volledig vastliggen door de keuze xnb= 0 •is dus uniek bepaald door de keuze van een basis Ab •de unieke xb is dan xb =Ab-1b Een extreem punt x moet bovendien mogelijk zijn: x ≥ 0 Elke simplexrichting uit zo een x is van de vorm

Probeer x4=x5 =0 ⇒ unieke oplossing (1,1,0,0,0)

•rb(λ) =Ab-1(b-Anb rnb(λ)) met rnb(λ) =λ(0…1…0)t

⇒ NB={ x4, x5 } en B={ x1, x2, x3 } Naast de NB-variabelen is ook x3 nul ⇒ Gedegenereerd extreem punt: extreem punt waarin meer ongelijkheden dan nodig actief zijn (alternatieve definitie) De NB-variabelen bepalen 2 simplexrichtingen, waarvan 1 gedegenereerde (λmax = 0) 02c.27

•het naburig extreem punt x(i+1) op die ribbe is rb(λmax) met λmax de grootste waarde van λ waarvoor rb(λ) ≥ 0 Er zijn normaal minstens evenveel ribben als simplexrichtingen Sommige simplexrichtingen geven gedegenereerde ribben Verschillende simplexrichtingen geven verschillende ribben (althans als deze ribben niet gedegenereerd zijn) 02c.28

versie: 14/2/2012


versie: 14/2/2012

Aanpassing van de basis


Opmerking

Bij λ=λmax bereiken we het eindpunt x(i+1) van de gevolgde ribbe ⇒ daar wordt een basisvariabele nul (zoniet zouden we λ kunnen verhogen)

In de les kwamen enkele slides uit deze presentatie niet aan bod; deze slides zijn bedoeld voor zelfstudie tenzij anders vermeld

Om vanuit de ribben uit x(i+1) te zoeken moeten we eerst een basis zoeken voor x(i+1) en NB- en B-variabelen De huidige keuze is niet goed want we hebben 1 NB-variabele positief gemaakt om de ribbe te volgen Kies als nieuwe NB-variabelen •de NB-variabelen die nog steeds nul zijn in x(i+1) •de (of een) B-variabele die nul werd in x(i+1)

02c.29

02c.30

versie: 14/2/2012


Bewijs... 1. Een basisoplossing die mogelijk is, is een extreem punt Bewijs: stel x is een basisoplossing ⇒ Ax=b en ∃ xnb=0: xb uniek ⇒ x ≥ 0 ⇒ xb ≥ 0 • en een mogelijke oplossing

Lineair programmeren Appendix

⇒ x ligt op een lijnstuk • maar geen extreem punt tussen twee mogelijke oplossingen y en z: x=α y+(1-α) z met 0 < α < 1 Ay=b, y ≥ 0, Az=b, z ≥ 0

y ≥ 0 en z ≥ 0 ⇒ ynb, znb ≥ 0 0 = xnb=α ynb+(1-α) znb

⇒ ynb =znb = 0

xb=Ab-1(b-Anb xnb)=Ab-1b ⇒ x b =y b ⇒ x = y yb=Ab-1(b-Anb ynb)=Ab-1b Idem voor z ⇒ x = y = z ⇒ geen lijnstuk maar een punt

02c.32

versie: 14/2/2012


...Bewijs 2. Een extreem punt is een basisoplossing Triviaal

02c.33

Copyright notice. Optimalisatietechnieken. Simplex-methode: principe. Lineair programmeren. x 3 optimum. x (6) A x (5) x (4) x 1

Recommend Documents