Lineaire optimalisatie samenvatting - 18/20 eerste zit HIR(B)

SIMPLEX


Oplossingsmethode:

1. In standaardvorm zetten
 Voorwaarden standaardvorm:
- Maximaliseren van doelfunctie
- ≤ Beperkingen
- Variabelen ≥ 0
2. Voor elke beperking een Slack variabele toevoegen (≤ wordt =)
 Slack = rechterlid - linkerlid
3. Startoplossing zoeken: z = 0
4. Startoplossing verbeteren tot optimale oplossing gevonden
 Variabelen van de doelfunctie in de basis brengen (inkomende variabele), basisvariabele uit
de basis brengen (uitgaande variabele)
 Maximale stijging inkomende variabele bepalen
 Nieuw model opstellen + bijhorende waarde variabelen weergeven



Wanneer optimale oplossing gevonden?

1. Alle doelfunctievariabelen hebben een negatieve coëfficiënt
2. Er zijn geen niet-basisvariabelen met coëfficiënt 0 in de doelfunctie
 Indien wel: breng niet-basisvariabele met coëfficiënt 0 in de basis
- Als dit leidt tot een andere niet-basisvariabele met coëfficiënt 0 in de doelfunctie: x
optimale basisoplossingen en oneindig aantal optimale oplossingen kunnen beschreven
worden a.d.h.v. een convexe lineaire combinatie


Problemen die zich kunnen voordoen:

1. Begin (initialisatie): oorspronkelijk probleem heeft ontoelaatbare oorsprong

Ontoelaatbare oorsprong als in standaardvorm geldt: … ≤- …

Oplossing: twee-fasen simplex

 Er wordt een hulpprobleem opgesteld, als toelaatbare oplossing van het hulpprobleem x 0 = 0
kan geconcludeerd worden dat het oorspronkelijk probleem een toelaatbare oplossing heeft

Hulpprobleem: min x0 of max -x0
-x0 toevoegen bij alle linkerleden van de beperkingen

, Oplossingsmethode hulpprobleem:

i. Slack variabelen toevoegen
ii. Dictionaire toelaatbaar maken: x0 in basis brengen
iii. Hulpprobleem oplossen a.d.h.v. simplex
iv. Indien optimale waarde hulpprobleem x0 = 0 : geef waardes oorspronkelijke variabele (excl.
Slack variabelen) weer die toelaatbare oplossing vormen voor oorspronkelijk probleem
v. Stel startdictionnair op van oorspronkelijk probleem:
- Kopieer rijen, negeer alle termen met x0
- Druk oorspronkelijke doelfunctie uit in termen van niet-basis variabelen
vi. Startdictionnair oorspronkelijk probleem oplossen a.d.h.v. simplex




 Mogelijkheden die zich kunnen voordoen nadat hulpprobleem opgelost is:
- X0 is niet-basis variabele (z = 0): startdictionnair oorspronkelijk probleem kan opgelost
worden
- X0 is basisvariabele en z ≠0: kan geconcludeerd worden dat er geen toelaatbare oplossing
bestaat voor oorspronkelijk probleem
- X0 is basisvariabele en z = 0: onmogelijk resultaat om te bekomen indien x 0 als uitgaande
variabele wordt gekozen wanneer de mogelijkheid zich voordoet




2. Midden (iteratie)
 Onbegrensd: bij het zoeken van uitgaande variabele kan geen variabele gevonden worden die
een bovengrens geeft aan de stijging van de uitgaande variabele

Oplossing: uitgaande variabele = t, bij optimale oplossing worden basisvariabelen in functie
van t geschreven

 Ontaard/gedegenereerd: basisoplossing waarbij tenminste één basisvariabele de waarde 0
heeft



3. Einde

Om oneindige lus (cycling/cycelt) te voorkomen wordt consistent gekozen voor de variabele met de
kleinste index als inkomende/uitgaande variabele indien er meerdere keuzes zijn