-ocr page 1-



		I.INIEAIR PRCGRAMMISMiN

-ocr page 2-



		I.INIEAIR PROGRAMMERS

-ocr page 3-



			s

Tiberdreef 4 - 3561 GG Utrecht

		LINEAIR PROGRAMMEREN

	Een produktie ten behoeve van de experimenten in het kader van de Herverkaveling Eindexamenprogramma's Wiskunde 1 en 2 V.W.O. Samenstelling: Jan de Lange Jzn Martin Kindt Vormgeving: Ellen Hanepen © 1983; 2e herziene versie Utrecht, november 1983.

-ocr page 4-



		INHOUDSOPGAVE 1. BIER OF ALE pag. 1 2. TARWE OF BOERENKOOL 5 3. TRANSPORTPROBLEMEN 11 4. LINEAIR PROGRAMMEREN 15 5. RANDEN WANDELEN 21 6. SPELINGSVARIABELEN 25 7. KANONIEKE VORM 31 8. VEGEN 35 9. SIMPLEX METHODE (I) 43 10. SIMPLEX METHODE (II) 51 11. SIMPLEX MET DE COMPUTER 57 12. GEMENGDE OPGAVEN 65 SAMENVATIING 72

-ocr page 5-



		1

	I
	I
BIER OF ALE Een bierbrouwer maakt twee soorten bier: 'Bier' en 'Ale'. De laatste soort is met name populair in Groot Brittannie en de Verenigde Staten. Het verschil in bereiding zal nog ter sprake komen. Voor beide soorten heeft hij de grondstoffen mais, hop en gerst nodig. De gerst wordt eerst geweekt; vervolgens laat men de gerst in een kelder tot kiemen komen. Daarna wordt het gedroogd. Dan heb je geAAtmout. Deze mout wordt samen met de mais en hop tot bier en ale verwerkt. Om een vat bier te maken heeft de brouwer nodig: 15 pond mais, 1 ons hop en 20 pond mout. '5 pond mm* ' °ws Hof J \v^ J BIER Om een vat ale te produceren heeft hij nodig: 5 pond mais, 1 ons hop en 35 pond mout.

5 PONT>M«"^i& ¹ ou,of *^? Powb wO<Jf / J ALE De winst op een vat bier bedraagt / 25,�; op een vat ale / 15,�.

-ocr page 6-

Het lijkt nogal verleidelijk voor de bierbrouwer om alleen bier te gaan
brouwen. Er is echter een probleem. Op korte termijn kan hij slechts be-
schikken over: 480 pond mais, 40 ons hop en 1190 pond mout.

» 1. Stel dat de brouwer LLVti,luAXznd bier maakt. Hoeveel vaten kan hij
dan produceren en hoeveel winst maakt hij dan?

» 2. Hoeveel houdt hij aan grondstoffen over?

» 3. Denk je dat het mogelijk is om meer winst te maken? Verklaar!

Deze laatste vraag is een nader onderzoek waard.

Bij welke combinatie van twee biersoorten maakt de brouwer de meeste

winst?

GERSTMOUT
iJ 90 pond

/ 25,-- WINST

i 15,-- WINST

WEIKE COMBINATIE GEEFT
MAXIMALE WINST?

Het probleem van de bierbrouwer in beeld gebracht.

-ocr page 7-

Het plaatje van de vorige bladzijde is in feite al bijna een (gerichte)

M ^^
15\

Bij deze graaf hoort de volgende ma&vlx:

A B


M	5	15
H	1	1
G	35	20

» 4. Hoeveel van elke grondstof wordt gebruikt bij produktie van 10
vaten ale en 20 vaten bier? (Bereken met matrixprodukt!)
Wat is de winst in dit geval?

» 5. De winst W is een functie van het aantal geproduceerde vaten ale
(=0.) en het aantal vaten bier (= fa) .
Wat is de formule voor W?

» 6. Teken niveaulijnen (iso-winst-lijnen) in een 0 , stelsel. (Neem
aan dat er onbeperkte voorraden grondstoffen zijn).

» 7. Hoe groot is het grondstoffengebruik van ieder van de drie grond-
stoffen bij produktie van a vaten ale en fa vaten bier? (Bereken
met bovenstaande matrix).

» 8. Bij opgave » 7 bleek hoeveel mais er voor de produktie van a vaten
ale en b vaten bier nodig is.
Verklaar waarom geldt: 5a+ 15fa i 480.

» 9. Teken de grafiek van 5a+ 15fa=480 in een 0 stelsel.

Arceer daarna het gebied waarvoor YiLeX geldt: 5a+ 15fa i 480.

-ocr page 8-



		4

Uit de voorgaande twee opgaven blijkt hoe de totale hoeveelheid mais een beperkende voorwaarde is. Maar ook de hop en de gerst leveren beperkende voorwaarden. » 10. Stel, op dezelfde wijze als bij de opgaven s> 8 en »9 gedaan is, de beperkende voorwaarden op als gevolg van de aanwezige voorraad hop. Teken de resultaten in de grafiek van opgave » 9. » 11. Dezelfde opdracht voor de beperkende voorwaarden tengevolge van de aanwezige voorraad gerst. > 12. Bij welke produktiehoeveelheden worden alle voorraden hop en gerst- mout opgebruikt? Los dit op met de grafiek van opgave » 9 tot en met opgave » 11. Hoe kun je het zonder grafiek oplossen? Hoeveel mais is er in dit geval nog over? Door de (drie) beperkende voorwaarden is nog maar een klein gebied met mogelijkheden overgebleven, zoals uit de grafiek blijkt. » 13. Ligt het binnen de mogelijkheden van de brouwer om 6 vaten ale en 13 vaten bier te maken? Zo ja, hoe groot is de winst dan? » 14. Teken (de grenzen van) het beperkende gebied in de grafiek met iso- winst-lijnen. (Opgave »6). Concludeer aan de hand van deze grafiek wat de produktiemethode is die de meeste winst oplevert. > 15. Van welke grondstof is hoeveel over? Hoe kun je dat aan de grafiek zien?

	Problemen zoals dit bierbrouwersprobleem komen nogal eens voor. Alleen meestal veel ingewikkelder. Maar de opzet is steeds hetzelfde: je zoekt naar een maximum (of minimum) van een functie op een begrensd gebied, waarbij het gaat om lineaire functies (bij het bier: W = 15a+25b) op een gebied dat begrensd wordt door rechte lijnen. In zo'n geval spreken we van LajizoaJiq. VftjOQtuvmmUiing. Bij programmering wordt dan gedacht aan plan- ning. Als je de functie waar het om gaat en de vergelijkingen van de randen van het gebied eenmaal hebt gevonden, is het probleem vaak snel opgelost. Maar juist dat 'mathematiseren' is nogal lastig.

-ocr page 9-

Een boer heeft een flink stuk land waarop hij tarwe en boerenkool wil
verbouwen. De twee variabelen zijn:

t : het aantal te verbouwen hectare tarwe;

b : het aantal te verbouwen hectare boerenkool.

De beperkende voorwaarden in matrixvorm zijn:


	tarwe	boerenkool	(maximaal) beschikbaar
aantal werkdagen per hectare	2	1	10
kosten landarbeider per hectare in guldens	35	30	210
kosten kunstmest per hectare in guldens	15	20	120

-ocr page 10-



		6

	» 16. Schrijf deze drie beperkingen op als vergelijkingen met variabelen � en b. (Zie opgave » 9). » 17. Teken het gebied waarvoor de beperkingen van opgave » 16 gelden. (Neem de �~a.s horizontaal). Bereken de coordinaten van de hoek- punten. » 18. Het totaal aantal hectaren dat beplant kan worden is een functie van � en b. Welke functie? Moeten � en b gehele getallen zijn? > 19. Wat is het Qftoo�i>�z gebied dat kan worden beplant? Teken iso-opper- vlakte-lijnen. > 20. De winst per hectare tarwe is / 40,�. De winst per hectare boerenkool is / 30,�. Hoe maakt de boer maximaZt winst?

HEER BOMMEL Heer Bommel voelt zich wat slapjes en raadpleegt daarom de alom bekende dr. Zielknijper. Deze constateert eenvoudig een tekort aan kalk en ijzer en schrijft heer Bommel miyH>te.yi6 50 mg kalk en min&t&nA 8 mg ijzer per dag voor. Aangekomen bij de Rommeldamse apotheek blijkt dat Bommel de keus heeft uit twee soorten pil- len: - merk A, bevattend 5 mg kalk en 2 mg ijzer; - merk B, bevattend 10 mg kalk en 1 mg ijzer. Omdat heer Bommel een uitgesproken hekel heeft aan het slikken van pillen, wil hij met zo weinig mogelijk volstaan. Hij slaat aan het rekenen, maar het probleem wordt hem al gauw te mach- tig. Gelukkig is daar Tom Poes die met behulp van de algebra en heer Bommel's ruitjesjas, het probleem vlotweg oplost. Hij stelt: <X: het aantal pillen A; b: het aantal pillen B.

-ocr page 11-

»21. Hoeveel pillen moet heer Bommel mi.yu.maal. slikken?

Hint: Bepaal eerst de beperkende voorwaarde die voortvloeit uit
de eis dat heer Bommel genoeg kalk krijgt. Daarna die voor
ijzer. Teken tenslotte het beperkende gebied met daarop die
iso-aantal-pillen-lijnen.


TERUGKIJKEND:
Het	doel van de bierbrouwer was zoveel mog			elijk winst maken	. Due	i zocht
hij	naar het maximum van <	ie dozJL^untiXI (van twee variabelen):
	W = 15a + 25b
op	sen door rechte lijnen	begrensd	gebied.	Dat gebeurt door	het	tekenen
van	hoogtelijnen (iso-winstlijnen)		i
Het	doel van de boer was (	3m zoveel	mogelij	k winst te maken.	Dus	zoekt
hij	naar het maximum van	de dozlfaunctie. (		van twee variabelen):
	W = 40-t + 30b
op	sen door rechte lijnen	begrensd	gebied.	Ook hier via iso-	-wins	tlijnen.
Het	doel van heer Bommel was om zo		weinig	mogelijk pillen te slikken.
Dus	zoekt hij naar het minimum van		de dooJL^uncXlz (van twee		vari	abelen):
	D = a + b
op	een door rechte lijnen	begrensd	gebied.	Dat gebeurt met :	Lso-aantal-
pillen-lijnen.

WERKWEEK

De hoogste klassen van een school in Haarlem gaan op werkweek. De reis
zal gemaakt worden met huurbusjes. Er zijn twee soorten beschikbaar: VW
en Ford Transit. In totaal gaan er 72 personen mee en 48 dozen bagage.
In een VW-bus kunnen 6 personen en 6 dozen, in een Transit 8 personen en
4 dozen. De busjes kosten / 80,� per dag per bus.

» 22. Hoeveel busjes moeten er van iedere soort gehuurd worden om zo
goedkoop mogelijk uit te zijn?
Wat zijn de kosten in dat geval?

-ocr page 12-

BOEKENREKJES

Een bedrijf maakt metalen boekenrekjes. Voor ieder rekje zijn drie ma-
chines nodig. Er zijn twee uitvoeringen van de rekjes: normaal en abnor-
maal (mooi).

De normale rekjes worden in 5,6 uur gemaakt:

2,0 uur door machine I; 1,2 uur door machine II; 2,4 uur door machine III,

Dezelfde machines worden ook gebruikt voor de mooie rekjes:

2,0 uur door machine I; 2,4 uur door machine II; 0,8 uur door machine III,

De machines draaien (ieder) maximaal 48 uur per week. De winst per nor-
maal rekje is / 2,40; de winst op een abnormaal rekje is / 4,80.

» 23. Hoeveel rekjes van iedere soort zou de fabrikant moeten maken als
hij maximale winst zou willen maken?
Is er meer dan een oplossing?

VITAMINEN

Vitaminen heb je nodig, omdat het lichaam ze niet of niet voldoende pro-
duceert. Met elk vitamine^tefcoA^C heb je kans op het optreden van kwalen
en stoornissen. De bekendste zijn scheurbuik (tekort aan vit. C); rachi-
tis, een vervorming van de wervelkolom (vit. D); beri-beri, een tropi-
sche ziekte (vit. B) en een bepaald soort ernstige hoornvliesontsteking
(vit. A). Het mag dus niet al te verbazend worden genoemd dat er nogal
wat vitaminedrankjes en -pillen op de markt zijn.

Een bepaald vitamine-extract V kost 30 cent per gram.
Een ander vitamine-extract W kost 150 cent per gram.

De samenstelling per gram is:


vitamine	A	B	C	D	E
vitamine- extract	12	1	20	1	2
vitamine- extract	6	10	30	3	2

(de hoeveelheden in inter-
nationale eenheden).

-ocr page 13-

Een farmaceutisch bedrijf wil door u gram V en W gram W te mengen een
nieuw extract maken, zo dat (u + w)) gram van dat mengsel mi.Yll>tQ,Yl�> bevat:


vitamine	A	B	C	D	E
vitamine- extract "V + W"	84	70	240	30	15

» 24. In welke verhouding moeten de extracten V en W gemengd worden, zo
dat de kosten van "V + W" miviimaaJL zullen zijn?

PARFUM

Een persoon die parfums samenstelt heet een parfumeur, of iets theatra-
ler: een parfumcomponist.

Op de foto zie je zo'n parfumcomponist achter z'n werktafel zitten, die
geheel in stijl, een parfumorgel wordt genoemd.

De parfumeur heeft de hand kunnen leggen op enkele exclusieve "essences'
waar hij twee perfecte parfums van wil maken.

Hij heeft 300 ml van essence CL; 350 ml van essence b en 200 ml van es-
sence C.

De parfums die hij wil maken heeft hij in een creatieve bui "Moonlight"
en "Daydream" genoemd.

-ocr page 14-

De samenstelling is:


	a	fa	c
Moonlight	5	5	2
Daydream	2	7	5

(de hoeveelheden in milliliters)

Op een flesje "Moonlight" maakt hij een winst van / 40,� en op een
flesje "Daydream" / 50,�.

» 25. Hoeveel moet hij van ieder maken voor de maximale winst?

RADIO OF T.V.

Een fabrikant wil een deel van z'n budget besteden aan reclame op radio
of t.v. Hij wil een aantal minuten op de radio (x) en een aantal minuten
op t.v. (t).
Er zijn nogal wat randvoorwaarden:

- hij wil minstens 30 seconden radio;

- hij wil minstens 3 minuten t.v.;

- de radio kost / 1.000,� per minuut, de t.v. / 4.000,�;

- het totaal te besteden bedrag is maximaal / 20.000,�;

- hij wil minstens tweemaal zoveel tijd op t.v. als op de radio.

»26. Schrijf de beperkingen op als vergelijkingen en/of ongelijkheden

en teken het gebied (de grafiek) dat ontstaat als deze beperkingen
gelden.

s>27. De uitgezonden spots moeten veelvouden van 30 sec. zijn. Wat is
het QSiOOtAte, aantal minuten dat kan worden uitgezonden?

» 28. Het budget wordt later verlaagd met 20%.
Wat zijn nu de mogelijkheden?

-ocr page 15-



			11

	3
	3	TRANSPORTPROBLEMEN
		TRANSPORTPROBLEMEN

Een fabriek die o.a. diepvrieskasten maakt heeft twee voorraadhallen. Een in Leiden en de ander in Arnhem. Van een bepaald type diepvriezer staan er in Leiden vijf en in Arnhem vier. Die moeten allemaal op korte termi jn bezorgd worden in Leeuwarden (drie), in Amersfoort (vier) en in Breda (twee). De transportkosten per vriezer zijn natuurlijk afhankelijk van de afstanden van de voorraadhallen tot de te bezoeken plaatsen. In de volgende graaf staan de transportkosten per kist langs de wegen (in guldens):

-ocr page 16-

De vraag is nu hoe het bedrijf zo goedkoop mogelijk uit is: hoeveel uit

Leiden moeten er naar Leeuwarden, naar Amersfoort, enz.?

Dit lijkt een heel ander probleem dan het voorgaande, maar dat valt wel

mee.

De eerste vraag is: wat is de (doel)functie, ofwel: wat zijn de VCUiMl-

boJLwl

Voordat we die proberen te beantwoorden, gaan we het probleem eerst wat

verkennen met grafen en matrices:

Lw NAAR

Lw Af Br ,
2 1

VAN

� � � � � �

Hier zie je (een gedeelte van) een mogelijkheid:
twee Leidse vriezers naar Leeuwarden;
een Leidse vriezer naar Amersfoort.

»29. Laat zien dat je nu de getallen bij de andere pij len 66k weet.

Maak de matrix ernaast af; maak ook een transportkostenmatrix (ook
2x3) en bepaal de totale kosten.

»30. Bepaal op analoge wij ze een andere oplossing.

»31. Doe hetzelfde als je weet dat er <X vriezers van L naar Lw gaan;
en b naar Af. Laat zien dat voor de totale kosten K geldt:
K = 15a+ 20b + 235

-ocr page 17-



		13

Nu is het niet zo raoeilijk meer met lineair programmeren het probleem op te lossen. Als variabelen kiezen we a en fa uit de graaf van opgave » 30. Aangezien er zes wegen in de graaf staan, krijgen we zes beperken- de voorwaarden. » 32. Welke zes zijn dat? >33. Teken het toegestane gebied dat door deze zes beperkingen wordt gevormd. (a-as horizontaal). *■ 34. Hoeveel mogelijke oplossingen zijn er? »35. Bij opgave » 31 had je al een formule voor de totale kosten, uit- gedrukt in a en fa. Teken iso-kostenlijnen in de grafiek en bepaal de oplossing met de laagste kosten. TARWETRANSPORT

	Het middenwesten van de Verenigde Staten vormt de graanschuur van de V.S. en van een groot deel van de wereld daarbuiten. Een tarwegroothandelaar heeft pakhuizen in Omaha en Chicago. In het eerste pakhuis heeft hij 50 vrachtwagenladingen tarwe, in het tweede 40.

-ocr page 18-

Hij heeft 20 wagenladingen verkocht naar Denver, 36 naar Miami en 34

naar New York.

De transportkosten per wagenlading zijn:

NAAR

VAN

» 36. Zoek de plaatsen op de kaart op. Maak een gerichte graaf (zoals
voor opgave » 29) bij de situatie dat de handelaar vanuit Omaha
10 ladingen naar Denver en 20 naar Miami verstuurt.

» 37. Doe hetzelfde als je weet dat er X ladingen van Omaha naar Denver
en y naar Miami (ook uit Omaha) worden verstuurd.

»38. Bepaal nu de oplossing die voor de handelaar het goedkoopste is.

Transportproblemen, zoals in de twee voorbeelden, kunnen dus met lineair
programmeren opgelost worden.

Het is zaak goed op de gevolgde oplossingsmethode te letten, daar deze
aanvankelijk sterk afwijkt van die bij de 'normale' lineaire programme-
rings problemen.

-ocr page 19-



			15

	4
		LINEAIR PROGRAMMEREN


Lineair programmeren is: het zoeken naar een minimum of maximum van een lineaire (eerstegraads) functie: i[x,y) = ax + by + a op een bepaald gebied, dat gevormd wordt door enkele lineaire vergelij- kingen of lineaire ongelijkheden. Niveaulijnen van fa[x,y) = CLX + by + c kunnen daarbij een rol spelen. De functie f$(x,t/) = ax + by + c heet doelfiunctLz of doelAteZLLng-i>{_lu.nc- tiz. Het gebied waarop de doelstellingsfunctie geminimaliseerd of gemaximali seerd moet worden, heet het tooAaixthaXt Qoh-izd. In feite is dit gebied het domein van de doelstellingsfunctie.

-ocr page 20-

Het voorgaande is een enge beperking van het lineair programmeren, want
in werkelijkheid zal de doelstellingsfunctie niet een functie van tWZZ
variabelen zijn, maar eerder van t<izn�aZlzn variabelen of zelfs nog veel
meer. Maar laten we eerst eens kijken naar een doelstellingsfunctie van
&KLZ variabelen. Je kunt dan de methode met de niveaulijnen nog wel toe-
passen (in zeer eenvoudige gevallen), maar zelfs dan wordt de zaak gecom-
pliceerd, zoals blijkt uit dit voorbeeld:

We beperken ons tot de wiskundige kant van de zaak.

De te max.imaXu>zh.zn dozt^unctiz (winst) is:

W = 50x + 200(/+ 300z.
Het tozlaixtbaJiz gzbizd wordt gegeven door:

�x + y + z S 13

y+ 2z < 18

X < 15

y �10

z < 8

en X > 0; y± 0; Z ^ 0.

Omdat we nu een doelfunctie van drie variabelen hebben, is het toelaat-
bare gebied niet een vlakdeel maar een deel van de ruimte:


		8
B		L _ _____ _ /		Y
B			10
	X/ __*
/	(5
*/

-ocr page 21-

» 39. Er zijn acht beperkende voorwaarden. Het toelaatbare gebied heeft
ook acht grensvlakken.
Geef aan welk grensvlak bij welke beperkende voorwaarde hoort.

In plaats van niveau�x.jn�ft bij een doelfunctie van twee variabelen zijn
er nu niveauvlakkm. Zo levert een winst(niveau) van / 2.000,�:

2000 = 50x + 200t/+ 300z

het volgende ■LiotMi.nstvlak op:


²		t

*r (*
*1 t*		X \.
*/ /*		,■■■'■' ^ \^
*/ /*		X ^
/ *
*i t*
*1 f*		■v /
		"^/	i� Y
			k� i
	L V /	** * is
	\V	-"^-^^

/
X

Andere isowinstvlakken zijn hiermee evenwijdig:

-ocr page 22-



		18

	» 40. Kun je aan de hand van deze isowinstvlakken al een voorspelling doen over de maximale winst? Erg duidelijk is een dergelijke tekening niet. En als er raeer dan drie variabelen in het spel zijn gaat deze grafische methode helemaal niet meer. » 41. Waarom? Er is echter een andere raethode die ons in dat geval uit de brand kan helpen. Bij deze methode loop je als het ware over de randen van het toegestane gebied, en wel steeds van het hoekpunt waar je bent naar een hoekpunt dat 'hoger' ligt. Dus naar een punt waar de winst hoger is, Bekijken we nog eens het toegestane gebied:

We kunnen de wandeling beginnen in het punt (0,0,0). De winst is daar: W(0,0,0) - 0 Vandaar gaan we wandelen over de rand naar een 'hoger' punt, We proberen (15,0,0) (= A).

-ocr page 23-

»42. Bereken de winst in A. Maak een tabel als volgt:


	punt	winst
	0,0,0	0
	15,0,0

Wandel vanuit A naar B of naar C. Bereken de coordinaten van het
door jou uitgekozen punt en bereken daar de winst. Vul deze in de
tabel in.

» 43. Zet je wandeling over de randen voort, net zo lang tot je in het
punt bent aangekomen dat het hoogste lijkt te liggen. Vul de ge-
vonden waarden steeds in de tabel in.

Vergelijk je antwoorden steeds met de tekening waarin de isowinst-
vlakken waren getekend.

» 44. Welk voordeel heeft het om op deze manier van een punt naar een

'naastgelegen' hoger punt te lopen tot je 'boven' bent, ten opzich
te van het berekenen van de winstwaarde in attd hoekpunten en dan
de grootste te nemen?


	RC.100)
q(isoo)
		\«(i9oo)
/ ywasoo) \ //		\/. , ) C (iooo\ �Yj«ioo) / 1
A(.oo.) / ife^T"		\/. , ) C (iooo\ �Yj«ioo) / 1
S(iooo) C(IOOO)		DOooo)

Een wat ingewikkelder gebied, met bij alle zichtbare hoekpunten de func-
tiewaarde van de doelfunctie. Met enige fantasie zijn er twee bergen in
te herkennen met daartussen een zadelpunt.

-ocr page 24-



			20

	»45. Begin de wandeling in B. Ga vandaar naar een naastgelegen hoekpunt met een hoQ2A.il functiewaarde. Maak weer een tabel als bij opgave »42. Wat wordt zo het hoogste punt? Wat vind je van de randenwan- delmethode in dit geval? De randenwandelmethode levert bij zo'n gebied met meerdere toppen geen goede oplossing. Wel als we te maken hebben met een 'alleenstaande' berg:

Gelukkig hebben toelaatbare gebieden bij lineair programmeren altijd een 'eenzame berg'-vorm. Over de achtergronden daarvan zullen we het niet hebben, maar het is wel snel te zien wanneer een gebied een 'eenzame berg¹ is. Neem je namelijk in bovenstaande tekening twee willekeurige punten op de berg (b.v. G en 0), dan loopt de verbindingslijn dooh. de berg (een tunnel) » 46. Laat zien dat in de tekening van de dubbolberg (minstens) een paar punten te vinden zijn, waarvan de verbindingslijn niet dodh. de ber- gen lopen (tunnel) maar biuXen het gebied ('kabelbaan').

		Men zegt wel dat de 'eenzame berg' convex is en de dubbelberg niet. Toelaatbare gebieden bij lineaire programmering zijn altijd convex. Als gevolg daarvan kunnen we de randenwandelmethode gebruiken.

-ocr page 25-



				21

		5
		5	RANDEN WANDELEN
			RANDEN WANDELEN

	MEDICIJNEN

Een farmaceutisch bedrijf moet binnen een tijdsbestek van 190 uur grote hoeveelheden van drie medicijnen maken (1), die we even U, V en W noe- men. 1000 flesjes U maken kost 3 uur; 1000 flesjes V maken kost 2 uur; 1000 flesjes W maken kost 4 uur. Hij kan niet meer dan 30.000 flesjes U, (2) 40.000 flesjes V, (3) en 20.000 flesjes W maken. (4) Het aantal duizendtallen te maken flesjes U noemen we U; het aantal dui- zendtallen flesjes V noemen we v en van W maken we er W duizend.

-ocr page 26-



		22

	»47. Laat zien dat de beperkende voorwaarden (2), (3) en (4) een toe- laatbaar gebied in de vorm van een blok opleveren. Teken het. » 48. Laat zien dat de beperkende voorwaarde (1) een vlak oplevert. Te- ken dit in dezelfde tekening en bepaal het toelaatbare gebied als je alle vier beperkende voorwaarden bekijkt. Per duizend flesjes U maakt de fabriek / 24,� winst. Voor V en W liggen die getallen als volgt: / 35,� en / 18,�. s>49. Bepaal de doelfunctie, in dit geval de winstfunctie. » 50. Probeer via de randenwandelmethode (te beginnen in (0,0,0) de ma- ximale winst te vinden.

BISTRO Een bistrohouder koopt vlees van drie leveranciers. Slager A kan hem maximaal 30 kg leveren; slager B kan hem maximaal 50 kg leveren; slager C kan hem onbeperkt leveren. De bistro-eigenaar bestelt a kg bij A; 6 kg bij B en c kg bij C. »51. Aan welke voorwaarden moeten a, b en c voldoen? Teken dit gebied in een driedimensionaal stelsel. De eigenaar wil niet meer dan 120 kg bestellen. » 52. Schets het toelaatbare gebied in het driedimensionaal stelsel van opgave » 51. De bistro-eigenaar maakt op het vlees van A / 25,� winst per kilo. Op het vlees van B / 20,� en op dat van C / 15,�. »53. Zonder verdere berekening kun je al zeggen wat het handigst is voor de bistroeigenaar. Wat?

-ocr page 27-



			23

		Om in te zien hoe de randenwandelmethode werkt, proberen we dit antwoord ook op deze manier te vinden: » 54. Bepaal de doelfunctie, in dit geval de winstfunctie. » 55. Probeer via de randenwandelmethode (te beginnen in (0,0,0)) de maximale winst te vinden. Deze randenwandelmethode laat zich ook toepassen in gevallen waarbij er meeA dan drie variabelen zijn. Alleen het tekenen gaat dan niet meer. De randenwandelmethode staat bekend onder de naam: SIMPLEXmethode. De sim- plexmethode kan met behulp van de computer ook worden gebruikt in lineaire programmeringsproblemen met hondoAdtin variabelen. Maar in eenvoudiger gevallen is ook een oplossing zonder computer mogelijk, maar dat vereist wat meer wiskundevoorkennis.

-ocr page 28-



		24

-ocr page 29-



				25

		6
		6	SPELINGSVARIABELEN
			SPELINGSVARIABELEN

	Even terug naar opgave »23: BOEKENREKJES. Een ba.dHA.Jl maakt metaZcn bocke.nn.ekjeA. \Jooh. tcdeA n.ekjz z-ijn dnte. ma- china, nodtg. En ztjn twze. iU.tvoeAx.natn van de. n.e.kjeA: nohmaat e.n abnon- maat [moot). Ve. nonmate. n.zkjeJ> iMon.de.n tn 5,6 uuA gemaakt: 2,0 uuA doon. machine. I; 1,2 uua doon. machine. II; 2,4 uun. doon. machine III. VtzeZfade. machines wondzn ook gcbnutkt voon. de. moote. n.e.kje&: 2,0 uuA doon. machine. I; 2,4 uuA doon. machine. II; 0,8 uuA doon. machine. III. Ve. machines dxaaten [tedex] maxtmaal 4$ uua peA we.e.k. Ve. uitn6t peA nonmaat n.e.kje. t& f 2,40. Ve. wtnAt op een abnonmaal n.e.kje. ti, f 4,SO. » Hoe.ve.eX. n.ekjeA van tedeAe. i>oont zou de. fiabnlkant moeXen maken att> hij maxtmale. wtmt zou Mitten maken? 1-6 eA meeA dan een oploA&tng?

De doelstellingsfunctie is: W = 2,40x + 4,80t/ met X: het aantal normale rekjes; y: het aantal abnorraale rekjes.

-ocr page 30-

Het toelaatbare gebied is:

2,Ox + 2,0y i 48 (machine I)

1,2x + 2,Ay � 48 (machine II)

2,4X + 0,8y i 48 (machine III)

Dit geeft het volgende toelaatbare gebied:

\-5

?fty

-S*+-

_s 10 15 20 25 30 35 40 45 X-as

Bij opgave » 23 losten we dit probleem op met niveaulijnen van de doel-
functie:

W = 2,40x + 4,80t/.
Nu gaan we kijken wat de randenwandelmethode hier oplevert:

»56. Begin in (0,0) en wandel naar het hoogste punt of de hoogste pun-
ten.
Maak een tabel:


	Punt	Winst
	(0,0) � � �	� � �

-ocr page 31-

Bij deze methode ga je er - terecht - vanuit dat het maximum in een
hoekpunt of op de rand bereikt wordt. We hoeven dus niet het hele toe^-laatbare gebied te inspecteren, maar alleen de randen.
Het inspecteren van die hoekpunten wordt bij meer variabelen en meer
beperkingen een verschrikkelijke hoeveelheid werk. Gelukkig kunnen we
gebruik maken van de computer. Dan moeten we echter de wiskundige for-
mulering van het probleem wat anders noteren. Ogenschijnlijk zelfs veel
ingewikkelder.

We hebben:


Maxima]		iseer:	W	= 2,40x +			4,	80y
op	het	toelaatbare	gebied:
			2	,0x +	2,	oy	Vii	48
			1	,2x +	2,	4y	VII	48
			2:	,4x +	o,	8y	VII	48

Nu kan door een list 2,0X + 2,0y S 48
geschreven worden als:

2,Ox + 2,0y + A. = 48

»57. Verklaar de list.

ft wordt een 4peiU.ttg4vaAxa.beZe. genoemd. Waarom?

Op dezelfde wijze kun je

1,2x + 2,4t/ i 48

herschrijven als:

1,2X + 2,4t/ + -4 = 48.

» 58. Pas de list ook toe op de derde beperkende voorwaarde. Noem de
derde spelingsvariabele t.

-ocr page 32-

Het probleem kan nu opnieuw geformuleerd worden:

Maximaliseer: W = 2,40x + 4,80y

waarbij X en if, evenals de spelingsvariabelen 1_t -6 en t (allemaal

SO) oplossingen moeten zijn van het stelsel lineaire vergelijkin-

gen:

2,OX + 2, Of/ + h. =48 (machine I)

1,2x + 2,4(/ + -4 =48 (machine II)

2,4X + 0,8i/ + t = 48 (machine III)

We noemen dit de kanon-Lzkd vorm van een lineair programmeringsprobleeni.
X en (/ worden de bQJ,ZJJ,i>i.YiQt>V0LKA.abdL<>.n genoemd.

» 59. Waarom?

Van groot belang bij het opstellen van de kanonieke vorm is de AtAiictuuA
van de manier van opschrijven. Die structuur is bij het voorbeeld als
volgt:

2_f0x

2,0y

- 48

1,2x

2,4y

- 48

2,4X

0,8y

- 48

,8te

> 1 beperkende voorwaarde

> 2 beperkende voorwaarde

-> 3 beperkende voorwaarde


Qi	11
J3	j3	01	91
0)	a)	l-t	r-4	(1
-r4	■^1	1)	«	l-<
U	14	J3	J3	01
03	H	nl	01	J3
>	>	�rA	�H	a
0)	09	}4	M	�H
00	00	CO	«	M
(3	c	>	>	m
■�-4	�r^	01	■	>
a	HI	00	00	01
«	■	C	C	00
�-i	�H	�H	�**	c
^	r*	r-l	f-<	�-I
■	a>	01	11	1-1
01	41	a.	a	01
XI	X3	01	01	o. 01
01	V	01	ii
u	-o	vi	�o	01
■	01	01	01	T)
l*	■	U	ii	u
11	s	�	»	01
�J	C	11	u	Tl
V -				■

toCaal vijf kolomnen

-ocr page 33-

Wat betekent dit nu allemaal? En met name, wat is de betekenis van de
list die ons de spelingsvariabelen 1, & en t opleverde?


Y-as ⁱ⁰ 20' 15	\	\ "NO¹	\ \ \ \ c	> \ \
	\			> \ \
10-
5	i^::':^::^::^::^::^::^;:^::^::^::^:>			»8 " ■ *�:■:■:::::■■:-:-:.:■:■:.> v^f'**
5	"'			.W:�:�:�>:\ V .
				\ A ^
		».v,v......	;■�:■;�;■:■,	"■�% ■■■■"■■■■■■■■■; Vi» <

0 5 10 '5 20 25 30 35 40 45 X-as

Wat is er aan de hand als /i=0? Dan is er geen speling op machine I en

dus geldt:

2,OX + 2,0t/ = 48.

Dat is precies de grenslijn van het gebied bepaald door machine I.

»60. Verklaar waarom de andere grenslijnen ook op zo'n manier zijn voor
te stellen. Zet bij iedere grenslijn de juiste voorwaarde.

Bij de randenwandelmethode wandel je van hoekpunt naar hoekpunt.
Stel dat we beginnen in 0 (dus: X. = 0; (/= 0).

Als we X = 0, t/ = 0 invullen in de kanonieke vorm, krijg je:

0 + 0 + K = 48

0 + 0 + -6 =48
0+0 + t = 48

en de winst is 0 + 0 = 0.

-ocr page 34-



		30

	Er wordt dus niets geproduceerd en geen winst gemaakt. De oplossing van het stelsel is (0,0,48,48,48). »61. Wat betekent het dat ^ = 48? We wandelen vanuit 0 naar A. »62. Waarom geldt in A dat t/=0; t-01 » 63. Vul deze waarden in de kanonieke vorm in en los het stelsel op. Bepaal de winst. » 64. Doe hetzelfde (als bij de opgaven » 62 en » 63) voor B. » 65. Ook voor C en D. Het is overduidelijk dat deze methode erg veel tijd en moeite kost. Echter, deze manier kan men ook toepassen voor een wiLte,keuiAA.g aantal beslissingsvariabelen en een WAJLtzkuVhiQ aantal spelingsvariabelen.

SAMENGEVAT: Er moest een (lineaire) doelfunctie van -twee variabelen gemaximaliseerd worden. Het tQQJUwXboJiz gebied voldeed aan dxLz (lineaire) ongelijkheden. Door introductie van dxiz spelingsvariabelen werden dit vergelijkingen. In totaal kreeg je dan V4.j� variabelen. Om een hoekpunt (en dus een oplossing) te vinden moeten (minstens) tiMQ.2. variabelen nul zijn. We zoeken net zo lang tot we het hoogste punt gevonden hebben.

-ocr page 35-



		31

	KANONIEKE VORM

Als er erg veel variabelen in het spel zijn, kan het alfabet tekort schieten. Stel dat er een probleem is met 15 beslissingsvariabelen en 21 spelingsvariabelen, dan gaat het mooi mis met X, y, ... en ti, i>, �, ... Daarom zullen we beslissingsvariabelen vaak: en de spelingsvariabelen: ^1, 42, -4 ₃ , .... noemen. » 66. Schrijf in de kanonieke vorm (denk daarbij aan de goede structuur!) Maximaliseer: 3Xi + 2X2 met: 4Xi + X₂ i 200 *Xi + x₂* � 80 ^Xi + x₂ i 60 »67. Schrijf in de kanonieke vorm: Maximaliseer: 3Xi - 2X₂ + 5x₃met: 6X1 + 2x₂ + 3x₃ ^ 6 -2x₂ + X₃ ^3 x₃ - 5Xi ^ 2 »68. Schrijf het bier/ale-probleem uit het eerste hoofdstuk in de kano- nieke vorm en los het probleem op met de in hoofdstuk 6 geschetste methode.

-ocr page 36-



			32

		Een fabriek van elektronische apparatuur maakt twee soorten produkten: A en B. De eindmontage van A vergt 4 uur. De eindmontage van B vergt 2 uur. De eindcontrole van A kost 2 uur. De eindcontrole van B kost 5 uur. Voor de montage zijn twee werknemers beschikbaar en voor de eindcontrole drie. Een werknemer werkt 8 uur per dag. De winst op A bedraagt / 20,� en op B / 30,�. » 69. Schrijf dit probleem - waarbij het gaat om de maximale winst - in de kanonieke vorm. » 70. Teken het toelaatbare gebied en geef daarin aan welke twee voor- waarden in ieder hoekpunt gelden (als bij opgave ^62). 3> 71. Vul die waarden uit opgave s>70 in de kanonieke vorm in. Waarom krijg je steeds twee vergelijkingen met twee onbekenden? Is zo'n stelsel in principe op te lossen? Hoofdstuk 4 begon met het voorbeeld: Te maximaliseren: W = 50x + 200(/ + 300z. Toelaatbare gebied: �x + *y + z* � 13 *y +* 2z < 18 x < 15 y �10 z i 8 »72. Hoeveel beslissingsvariabelen zijn hier? »73. Hoeveel spelingsvariabelen zijn er? » 74. Schrijf dit voorbeeld in de kanonieke vorm. (Gebruik Xi, .... voor beslissingsvariabelen en ii, .... voor spelingsvariabelen).

-ocr page 37-

»75. Verklaar waarom voor hoekpunt B van de figuur op biz. 16 geldt:
X₂ = 0
4i = 0

Waarom dhA.Z voorwaarden?

4₃ = 0

» 76. Waarom hou je een stelsel van vijf vergelijkingen over met vijf

onbekenden als je de voorwaarde van B invult in de kanonieke vorm?
Is zo'n stelsel op te lossen?

Misschien wordt nu duidelijk waarom deze methode 'altijd' werkt.

Als je 150 beslissingsvariabelen hebt en 250 spelingsvariabelen, krijg

je in principe een systeem van 250 vergelijkingen met 400 onbekenden.

De structuur van de kanonieke vorm ziet er dus als volgt uit:

250

^250,

250 kolommen

150 kolommen

400 kolommen

Maar voor ieder 'hoekpunt' geldt dat er 150 variabelen gelijk aan nul
zijn. Vul je dat in de kanonieke vorm in, dan blijft er een systeem over
van 250 vergelijkingen met 250 onbekenden. En dat is in principe oplos-
baar. Zeker met de computer.

In het volgende hoofdstuk zullen we zien hoe je een systeem van b.v.
zes vergelijkingen met zes onbekenden oplost.

-ocr page 38-



				34

		Op deze faoto, die. ook op dd voonkant van (Lit bodkjd 6taat, zijn doon. ddn thJXQjtoh voidn in dn gfiond geXAokken. In hdavdlacktig tdVidin zo- ati> hi.dK., zi,jn deze tijndn in fiditd ni.dt6 anddKi> dan hoogtdtijndn. Ovdftigjinis: L.P. wh.dt nogat ddni, gdbmUkt in de tandbouw.

-ocr page 39-



			35

	8
	8	VEGEN
		VEGEN

In dit hoofdstuk wordt bekeken hoe een stelsel van n vergelijkingen met n onbekenden kan worden opgelost. Het eenvoudigste geval is n = 2; dus twee vergelijkingen met twee onbe- kenden: 3x + by = 11 *x - y =* 1 Een manier van oplossen gaat als volgt: vermenigvuldig de tweede vergelijking met 3 en trek die van de eerste vergelijking af: \| 3X + 5y = 11 < 3x - 3y = 3 _ . 0-x + 8y = 8 De eerste vergelijking van het stelsel wordt nu door dit resultaat ver- vangen: O'X *+ 8y = 8* x - y = 1 waaruit gemakkelijk volgt: y = 1 X = 2 ofwel: (x,y) = (2,1) »77. Los zelf het volgende stelsel op: 3a + 5b = 11 a - b = 1

-ocr page 40-

Zoals te verwachten, was er geen 'echt' verschil tussen:
3x + by = 11 | 3a + 5b = 11

y = 1 a - b =

Van belang zijn eigenlijk alleen de coefficienten en de plaats daarvan!


3X	+	by	=	11
3X	+	by	=	11
1x	-	\y	=	1
1x	-	\y	=	1

eerste vergelijking
tweede vergelijking

In matrixnotatie:

-1

1 1

-V eerste vergelijking
_^. tweede vergelijking

^ 78. Verklaar dat beide vergelijkingen van hierboven in matrixnotatie
als volgt opgelost (kunnen) worden.

Schrijf daartoe iedere matrix weer in de vorm van een stelsel ver-
gelijkingen.

3 5

1 -1

0 8

, 1 -1

0 1

i 1 -1

0 1

1 0

wordt:

1 /

wordt:

» 79. Stel dat iemand een systeem van vier vergelijkingen met vier on-
bekenden heeft teruggebracht tot:

-ocr page 41-

Breng deze matrixnotatie terug tot een stelsel van vier vergelij-

kingen met vier onbekenden.

Geef de oplossing van het stelsel.

» 80. Schrijf het stelsel:

- 2X₄ =

Xi - X₂2x₂

Xi + X₂ + X₃

Xi + X₂ + 2X₃ + Xi*

in matrixvorm.

»81. Schrijf het stelsel:

Xi + 2X₂

x₃ + 2x₄

X₂ ^- Xij

x₃ + 2xi

4
6
1
3

in matrixvorm.

»82. Schrijf het stelsel:

Xi - 3 = x.₂ + 2X4

X3 + X4 = 4 - 2x₂

Xi + x₃ = 6 - x₂

x₄ + x₂ + Xi = 6 - 2x₃

in matrixvorm.

0m te laten zien hoe het oplossen van een stelsel van drie vergelijkin-
gen met drie onbekenden gaat in matrixnotatie en in de vergelijkingen-
notatie, het volgende voorbeeld:

Xi + X₂ + X3 = 6

2Xi - 3x₂ + X₃ = 1

Xi - x₂ + X₃ = 2

-ocr page 42-

We gaan de Xi eJLLmLnQAzn uit de tweede vergelijking door de eerste
er twee keer af te trekken.
We krijgen dan:

6
-11

/ ¹ ¹

0 -5
\ 1 -1

Xi + X₂ + X₃ = 6

0 - 5x₂ " x₃ = -11

Xi - X₂ + X₃ = 2

We gaan de Xi elimineren uit de derde vergelijking door de eerste
er af te trekken.
We krijgen dan:


1¹	1	1	6
0	-5	-1	-11
\ o	-2	0	- 4

Xi + x₂ + x₃ = 6
0 - 5x₂ - x₃ = -11
0 - 2x₂ + 0 = - 4

De derde vergelijking kan anders geschreven worden:


1	1	1	6 \
0	-5	-1	-11
0	1	0	2 /

Xi + X₂ + X₃ = 6
0 - 5x₂ - X₃ = -11
0 + X₂ + 0 = 2

De oplossing X₂ = 2 is nu zowel links als rechts af te lezen.
Maar we gaan verder met elimineren.

^83. Verklaar de volgende stappen:

Xi + 0 + X₃ = 4

0 + 0 - X₃ = -1 of

0 + X₂ + 0 = 2

en tenslotte:

Xi + 0 + 0 = 3

0 + 0 + X₃ = 1 of

0 + X₂ + 0 = 2

dus: (Xi, x₂, X₃) = (3,2,1).


I ¹	0	1	4 '
0	0	-1	-1
1 0	1	0	2 1

I 1

\ o

0 0

0 1

1 0

De stelsels die bij de opgaven » 80 en » 82 staan zijn dezelfde zoals
blijkt uit hun matrixvorm. De oplossing van opgave > 79 is tevens oplos-
sing van » 80 en » 82.

-ocr page 43-

» 84. Hoe kun je dat controleren?

De vraag is nu hoe je van de matrixvorm van opgave > 80 (82) naar die

van » 79 kunt komen.

Dat gaan we nu in detail bekijken.

Dus hoe kom je van:

naar:

We beginnen met:

We gaan nu proberen in de linker vier kolommen steeds een 1 en drie nul-
len te krijgen. En die enen moeten ieder in een andere rij staan.
We laten eerst het oog vallen op de 1 links boven. Die mag blijven:

3
4
6
6

Met deze MJ op de 'vierde etage' gaan we de linkerkolom (schoorsteen)
schoon vegen. Dat wil zeggen: alle getallen nuZ maken. Dus de linkerko-
lom moet 7.6 worden:

� � � � �

� � � �

Op de derde etage valt niets te vegen, die is al schoon. (Er is al een
nul) .

-ocr page 44-

De 1 op de tweede etage 'vegen' we door de vierde etage van de tweede
af te trekken.
Je krijgt dan:

4
3

\J -1 0-2
0 2 11
0 2 12
112 1

Van de linker schoorsteen moet nu alleen nog de eerste etage worden ge-
veegd. Ook weer door er de vierde etage vanaf te trekken:

Zo. Daarmee is de linker schoorsteen geveegd,

Nu een andere. In de derde kolom staat een 1 op de derde etage. Laten
we daarmee de derde schoorsteen schoonvegen:


			-1 2 2	0 -2 0 < 1 2
			2	2 3
» 85. c	i. Verklaar d	e vo	lgende stap
		/ ¹0 0	-1 2 2	0 -2 o « 1 2
	.	\ o	2	2 3
		/ ¹0	-1 2 0	0 -2 0 ' 0 1
		o	-2	0 1

³\

4
3
3

3
4

-1
-5

Nu is ook de derde schoorsteen geveegd.

-ocr page 45-

De volgende kolom die zich leent om geveegd te worden is de vierde, want
daar zitten al twee bruikbare enen in.

»85. b. Er staan dfiL<L enen in de vierde kolom.
Waarom zijn er maar twee bruikbaar?

» 85. c. Verklaar:


	0 -2	3 \
	1 1	4 1
	0 ©	-1
	0 1	-5 /


	1 1	-1
	0	2
	0	0
	\ o	-2
	r 0	-1 2
	0	0
	0	-2


	0 0	1 \
	1 0	5 1
	o 0	-1
	0 0	-4 /

wordt:

Tenslotte vegen we de nog overgebleven vuile schoorsteen, namelijk de
tweede.

»85. d. Verklaar waarom de (-2J moet blijven (in die tweede kolom) en
laat zien dat we uiteindelijk krijgen:


/ 1 0 0	0	3
0 0 1	0	1
0 0 0 \ o 0 o	1 0	-1 2

Hiermee zijn we terug bij opgave » 79 en is het probleem opgelost.

Dit principe - de schoorsteenveegmethode - is ook in moeilijker gevallen

bruikbaar.

»86. Los op (met de veegmethode):

2Xi - X₃ = "4

- Xi + 2X2 =3

3x₂ + 2x₃ = 7

-ocr page 46-

4 2

Xi + 2X2 + 3x₃ = 15
3xi + 2x₂ + x₃ = 13
2xi + x₂ + x₃ = 9

> 87. Los op:

> 88. Los op:

2Xi

8
9

x₃ + x₄ =

Xi + 2x₂ + 3x₄

Xi + 3X₃ + 2X4

2xi + x₂ + 5x₃ + 2x₄

» 89. Los op:

Xi + 2X₂ - X₃ + X4 =

-1

+ 2x₄ =

2x_:

x₂

Xi - X₂ + 2X3 - Xi* =
Xi + 3X₂ + X₃ - 2X4 =

-ocr page 47-



					43

		9
		9
	SIMPLEX METHODE (I) De Simplex- of Randenwandelmethode wordt in dit hoofdstuk gebruikt bij het opstellen van het ale- en/of bierprobleem uit hoofdstuk 1. Daarbij passen we de veegmethode toe uit het vorige hoofdstuk. DE EERSTE STAP De eerste stap is het opstellen van de do eZ&unctie. en de faepe/tfeende voosiwcuvidzn. In het eerste hoofdstuk werd dit stap voor stap gedaan met het volgende resultaat: VoeZ^unctit: W = 15Xi + 25x₂ BepeAfeende voohwaaAden:

				(mais) (hop) (gerstmout)
			5xi + 15x₂ S 480 *Xi + x.2 i* 40 35Xi + 20x₂ � 1190


DE TWEEDE STAP De tweede stap is het invoeren van i>pztinQis\ja>ujxbilttn. Het probleem kan dan in de kanonieke vorm geschreven worden: 5Xi + 15X₂ + i>i = 480 Xi + X₂ + -4₂ = 40 35Xi + 20x₂ +4₃= 1190 15Xi + 25X₂ = W

-ocr page 48-

DE DERDE STAP

De kanonieke vorm wordt nu in matAAXno&uLLfL geschreven:


5	15	1	0	0	480
1	1	0	1	0	40
35	20	0	0	1	1190
15	25	0	0	0	W

Dit wordt het SIMPLEX-TABLEAU genoemd.

Een eerste oplossing is direct uit het tableau af te lezen:
Xi =0, X₂ = 0, 4i = 480, 4₂ = 40, 4₃ = 1190.

> 90. Verklaar deze oplossing in termen van het ale-/bierprobleem.
Hoe groot is de winst?

Omdat er maar tuozn bQJ>LLi>i><LnQi>va.ici&bele.Ti zijn is de oplossing grafisch
weer te geven:

De eerste basisoplossing is dus:

Xi =0, X₂ = 0, &\ = 480, 4₂ = 40, -4₃ = 1190
ofwel: (0, 0, 480, 40, 1190).

-ocr page 49-



			45

DE VIERDE STAP We gaan nu wandelen vanuit het eerste hoekpunt (vanuit de eerste ba- sisoplossing). De vraag is: Welke kant op? Het slimste is om in die richting te wandelen die de snelste toename in de winst geeft. (We willen zo steil mogelijk klimmen). De winstfunctie is: W = 15Xi + 25X2. »91. Welke variabele moeten we vermeerderen om zo snel mogelijk te stij- gen: Xi of X2? We zitten in de eerste basisoplossing Xi = 0, X2 = 0. Uit het antwoord op opgave » 91 volgt dat we moeten gaan wandelen langs de rand Xi = 0. (Grafiek!). Nu kan Xi = 0 in principe snijden met 61 = 0 met 62 =0 en me t i> 3 = 0 »92. Welk van de drie snijpunten moeten we hebben: Xi = 0, 61 = 0 of Xi = 0, 4₂ = 0 of Xi = 0, 4₃ = 0? Uit de antwoorden van opgave > 90 en »91 volgt dat het verstandig is om:

	6 <5)
	6 <5)	X2 groter te laten worden, omdat de CoiL^-lditLnt van X2 (-in de dooZfaunctlo.) het QUootbt is; te wandelen naar het hoekpunt dat het dLLck�&�. b-Lj ligt om er zeker van te zijn dat we nog in het toelaatbare gebied zitten. (In dit geval Xi =0, 4i =0).

-ocr page 50-

DE VIJFDE STAP

In deze vijfde stap wandelen we van de eerste basisoplossing naar de
volgende.


5	15	1	0	0	480
1	1	0	1	0	40
35	20	0	0	1	1190
15	25	0	0	0	W

We hadden:

Een oplossing: (0,0,480,40,1190); Winst: 0.

1 ) geeft de grootste coefficient van de doelfunctie aan.
Ora X2 direct uit de matrix te kunnen aflezen, gaan we de X2 -kolom
vegen.

Omdat die kolom geveegd moet worden, gaan we er eerst allemaal enen
van maken:


1 3	0	1 15	0	0	32
1	1	0	1	0	40
1¹¹ 4	1	0	0	1 2 0	59,5
15	25	0	0	0	W

> 93. Waar vind je de getallen 32, 40 en 59,5 in de grafiek terug?

Hoe kun je aan het bovenstaande tableau zien dat Xi =0; <6i = 0
het meest nabije snijpunt oplevert?

Omdat we naar het meest nabije snijpunt moeten, is nu niet alleen de
vegerij (fO)> maar 00k welk element Mj mag blijven ( *\2j) bekend.

-ocr page 51-



			47

		Vegen levert dan: � © Ts 0 0 32 f 0 -& 1 0 8 ¹IT 0 -^ 0 Jj 27,5 6 f 0 - f§ 0 0 W- 800 De schone kolommen (de tweede, vierde en vijfde) brengen we in de een- heidsmatrixvorm, zodat een oplossing direct is af te lezen. Daartoe wordt de derde rij vermenigvuldigd met 20. I © IT 0 0 32 f 0 -^ 1 0 8 ^ 0 - \| 0 1 550 6§ 0 - \| 0 0 W- 800 » 94. Een oplossing van dit stelsel is nu: (0, 32, 0, 8, 550). Verklaar! ^95. Verklaar ieder der coordinaten van de oplossing binnen het kader van het bier-/aleprobleem. » 96. Hoe groot is de winst? Waar vind je die in het tableau? »97. Wijs de oplossing aan in de grafiek van biz.44. Deze oplossing wordt een tltiMldz basisoplossing genoemd. DE ZESDE STAP Vanuit het hoekpunt Xi ■ 0, &\ - 0 moeten we verder wandelen naar een hoger gelegen punt. We moeten i>\ = 0 laten snijden met 42 = 0 of 4₃ = 0 of 6₂ = 0 We gaan op precies dezelfde wijze te werk als bij de vijfde stap:

-ocr page 52-

We hadden:


t	0	h	0	0	32
1 3	0	-h	1	0	8
8_5 3	0	_ 1 3	0	1	550
of	0	_ 5 3	0	0	W-800

We hebben geen keuze in veegkolom, want alleen verandering in Xi le-
vert vermeerdering op.

>> 98. Verklaar dit en de stappen naar de volgende tableaus:


0	3	3 1 0	_3_ 2	0	84
0	0	1 " TV	3 2	0	12
0	0	9 170	3 2	3 8 5	126 1 7
0	0	-1	-10	0	W-880

wordt:


0	1	1 0	1 2	0	28
1	0	l 1 0	1 2	0	12
0	0	3 2	_ 8 5 2	1	210
0	0	-1	-10	0	W- 880

wordt:

» 99. We lezen direct een oplossing uit dit tableau af. Welke'

» 100. Uit de laatste regel van het tableau volgt onmiddellijk dat

W-880 i 0 is. Dus de maximaZz winst is / 880, �. Verklaar dit,

-ocr page 53-

SAMENVATTING

Opstellen simplextableau.
Oplossing: (0,0,480,40,1190).
Winst: 0.

We maken van de Mj kolom enen, deze
moet daarna geveegd worden. (x₂ toe-
neraen laat de winst het snelst groe-
ien) .

Uit "*\2J volgt dat dit het meest nabije
snijpunt oplevert: Xi=0, 6i ■ 0.


5	15	1	0	0	480
1	1	0	1	0	40
35	20	0	0	1	1190
15	25	0	0	0	w


1 3 1	1 0	0 1	0 0	32 40
1*	1 0	0	2 0	59,5
15	25 0	0	0	W

-©


1 3	0	1 5	0	0	32
? 3	0	"A	1	0	8
1A	0	"A	0	Ju 20	27,5
6*	0	1 *	0	0	W- 800

Door vegen met (l ) ontstaat dit ta-
bleau. De schone kolommen nu nog zo

'fatsoeneren' dat alleen nullen en een

1 erin staan.

(Eenheidsmatrix).

Oplossing: (0,32,0,8,550).
Winst: 800.

of bepaalt veegkolom. Daar maken we
eerst weer enen van.

(De afstandsvoorwaarde) geeft aan welk
element 1 blijft in die kolom.

Vegen levert dit resultaat op.

Nu de schone kolommen nog 'mooi' maken.

(Eenheidsmatrix).

Oplossing: (12,28,0,0,210).

Winst: 880.

Dus:

12 vaten ale; 210 pond mout over.

28 vaten bier.

Winst: 880 gulden.


0 3	A	_1 2	0	84
0 °	1 TTJ	3 2	0	12
0 0	9	_i	-2-	m
0 0	1 70	2	S 5	17
0 0	-1	-10	0	W- 880


0	1	A	_ 1 2	0	28
1	0	-A	i 2	0	12
0	0	§	2	1	210
0	0	-1	-10	0	W- 880

-ocr page 54-



		50

-ocr page 55-



			51

	1
		SIMPLEX METHODE (II)


Uit het voorgaande hoofdstuk blijkt dat de simplexmethode uit de volgen- de stappen bestaat: 1. Stel de doelfunctie. en bzpeAkundz voommandm op. 2. Voer &pzJting&VO/uabe�zn in. (Kanonieke vorm). 3. Maak het Aimple.X-table/LU; vind eerste basisoplossing. 4. Ga op zoek naar tweede basisoplossing: a. Veeg de kolom met de gtiootitd coH^-LdLzYVt in de do eZ&tinctiz. Maak eerst de elementen gelijk aan 1 in die kolom. b. Kijk daarna naar de constantes rechts van de streep. De kZeinAte. constants, (kleinste afstand) bepaalt welk element in de veegkolom de 1 is. c. Bepaal na het vegen een tweede basisoplossing. 5. Herhaal stap 4 totdat alle coefficienten van de doelfunctie negatief zijn. Dan ben je op het hoogste punt.

-ocr page 56-

3> 101. Los het boekenrekjesprobleem (opgave » 23) op met de simplexme-
thode. Controleer de oplossingen aan de hand van de grafiek van
opgave *■ 23.

» 102. Een hondebroodfabriek maakt twee soorten hondebrood: A en B.
Voor een doos A gebruikt men 2 pond vlees en 1 pond meel.
Voor de wat mindere soort B gebruikt men voor een doos 4 pond
vlees en 5 pond meel.

Per dag kan maximaal 80 pond vlees en 70 pond meel worden ver-
werkt.

De winst op 1 doos A is / 3,�.
De winst op 1 doos B is / 10,�.

Hoeveel dozen van iedere soort zal de fabriek maximale winst op-
leveren? (Gebruik de simplexmethode).

» 103. Een fabrikant maakt glazen asbakken. Hele degelijke die / 5,�
kosten om te maken en waarvoor de transportkosten / 0,20 zijn
(per stuk).

Verder goedkope reclameasbakjes: produktiekosten / 2,�, maar
/ 0,40 om te verzenden.

De totale produktiekosten mogen de / 3.000,� niet te bovengaan.
De verzendkosten moeten onder de / 160,� blijven.
Hoeveel van iedere soort zal de fabrikant maken als zijn winst
op de mooie asbak / 2,40 en op de reclameasbak / 2,� is?

Hoofdstuk 5 begon met het medicijnenprobleem (de opgaven » 47, » 48,

s> 49 en > 50). Bij het oplossen van dit probleem doet fich nog een klei-

ne complicatie voor:

Het tableau is:


1	0	0	1	0	0	0	30
0	1	0	0	1	0	0	40
0	0	I	0	0	1	0	20
3	2	4	0	0	0	1	190
24	35	18	0	0	0	0	W

Oplossing: (0, 0, 0, 30, 40, 20, 190); W = 0.

-ocr page 57-



		53

	» 104. Controleer dit tableau. Het is snel duidelijk dat de te vegen kolom de tweede is. Daar zouden we dus van alle elementen een 1 moeten maken. Er staan echter al tlXKLZ nutttn in. Daar blijven we vanaf. Die twee nullen komen nooiX, in aan- merking om als veegelement op te treden. Het waarom blijkt uit de teke- ning van het toelaatbare gebied:

We zitten in (0,0,0). Xz moet verhoogd worden. We reizen dus langs de X2^_as. Dus Xi=0; X3 =0. Dan kunnen we in principe snijden met een hele serie vlakken, te weten: 61 = 0 -62 = 0 4₃ = 0 4₄ = 0 maar uit de tekening blijkt dat snijden met 41 = 0 en 4 3 = 0 0n.m0g2lA.jk is, omdat deze e.\)<Lnu)-Ljdi.Q zijn met X2^_as!

-ocr page 58-

De twee nullen in de veegrij geven aan dat er geen snijpunt is (met 4i=0
en 43=0). Dus leveren ze zeker geen meest nabij snijpunt op. We kunnen
dus slechts kiezen uit de twee andere elementen:


1	0	0	1	0	0	0	30
0	1	0	0	1	0	0	40
0	0	1	0	0	1	0	20
3	2	4	0	0	0	1	190
24	35	18	0	0	0	0	W

(komt niet in
aanmerking)


1	0 0	I	0	0	0	30
0	0 o	0	1	0	0	40
0	0 1	0	0	1	0	20
3 2	1 2	0	0	0	1 2	95
24	35 18	0	0	0	0	w

wordt:

2 ) (meest na-

bije snijpunt)

» 105. Los het probleem zelf verder op.

» 106. Los het probleem waarmee hoofdstuk 4 begint op met de simplex-

methode. Controleer de basisoplossing aan de hand van de grafiek
in dat hoofdstuk.

» 107. Doe hetzelfde met het bistroprobleem uit hoofdstuk 5.

-ocr page 59-

» 108. Een fabrikant maakt twee soorten stof (A en B), waarbij hij ge-
bruik maakt van drie soorten wol van verschillende kleur:


soort wol	beschikbare hoeveel- heid wol	nodig voor produktie van een rol van soort
soort wol	beschikbare hoeveel- heid wol	A	B
rood	1400 kg	4 kg	4 kg
groen	1800 kg	6 kg	3 kg
geel	1800 kg	2 kg	6 kg

Winst per rol A: / 120,�.

Winst per rol B: / 80,�.

Hoeveel rollen A en B zal hij maken om maximale winst te maken?

(Gebruik de simplexmethode).

-ocr page 60-



	56

		.

�

-ocr page 61-

SIMPLEX MET DE COMPUTER

Als het aantal variabelen groot wordt ligt het voor de hand de computer
in te schakelen. De hele Simplex-methode is tenslotte het slaafs toepas-
sen van enkele rekenregels en daar zijn computers buitengewoon geschikt
voor. Bovendien gaat het razend snel, zelfs bij een geval met zeer veel
variabelen. Het probleem is dan ook vaak niet zozeer het rekenwerk, maar
het opstellen van de doelfunctie en het vinden van de beperkende voor-
waarden.

Afhankelijk van het programma dat in de computer zit, kan de invoer b.v.
bestaan uit:


MJ de coefficienten van de beper-	(2J de coefficienten van de
kende voorwaarden.	kanonieke vorm.
Xi i 10	Xi + + -61	10
*x.₂ <* 8	X₂ +4₂	8
Xi+ 2x₂ � 18	Xi+ 3x₂ +i>₃	18
Xi+ x₂ i 13	Xi + X₂ + 6n =	13
200Xi + 300x₂ = W	200Xi+300x₂	W
wordt als computer-invoer:	wordt als computer-invoer:
1, 0, 10	1, 0, 1 0 0 0 10
0, 1, 8	0, 1, 0 1 0 0 8
1, 2, 18	1, 2, 0 0 1 0 18
1, 1, 13	1, 1, 0 0 0 1 13
200, 300.	200, 300.

-ocr page 62-



		58

	Hieronder zie je de invoer op de eerste manier. Eerst vraagt de computer het aantal beslissingsvariabelen. Daarna om het aantal beperkingen. 1000> aantal beslissingsvariabelen: 10 1010> aantal restncties: 15 1020> 20,28,28,10,45,39,28,56,18,34,3400 1030> 45,67,23,45,87,34,12,65,34,56,4567 10 4 0 > 23,56,98,67,34,28.67,88,44,56,4599 1050> 34,25,16,78,88,45,76,34.23,89,7777 1060> 54,65,29,82,46,78,25,90,45.22.8632 1070> 55,77,123.56,88,45,34,34,66,77,8888 1080> 22,55,66,987,4 5,23,78,80,90,45.45370 1090> 54,66,29,56,74,89,34,88,27,65,3490 1100> 90,6,30,5.4,90,34,54,76,3000,123000 1110> 11,22,33,88,45,35,76,87,80.60,4500 1120> 34,56,98,12,67,40.87,98,50,60,70000 1130> 34,56,6,7,30,87.90,45.44.44,99880 11 4 0 > 55,22,99,45,45,45,67,9.34,45,8700 1150> 4,5,6,7,8,3,5,7,3.6,800 1160/ 33,60,20,80,60.50,55.66,9,5,7600 1170 > 30,30,4 3,56.23,5.7.3,8,34

» 109. Schrijf regel 1020 in vergelijking-vorm. » 110. Wat betekent regel 1170? De output van dit probleem zie je hiernaast op de volgende bladzijde. De winst in het eerste punt is 2574,2. Deze ontstaat als Xu =46,0. Dat klopt, want de winst is dan 56 � 46,0 = 2576 (afrondingsfouten). Na een eerste wandeling komt de computer terecht in een punt waar de winst 3211,9 is. » 111. Hoe komt deze winst tot stand? » 112. Toon op dezelfde wijze aan hoe de winst tot stand komt in de ho- gere punten.

-ocr page 63-

h�?t simplextableau ziet er zo uiti


19.8	27.4	27.3	0.0	44	5	38.8	27	2	55	2	17	1	33	5	2940	3
44.0	64.5	20.0	0.0	84	.9	33. 0	8	4	6 1	.4	29	9	53	9	2498	5
21.5	52.3	93.5	0.0	30	9	26.4	61	7	er	6	37	9	52	9	1519	2
32. 3	20.7	10. B	0.0	3 4	.4	43.2	69	8	27	.7	15	9	83	4	4191	5
52. 2	60.4	23. 5	0.0	42	3	76. 1	10	5	83	4	37	5	10	3	4862	7
53.8	73.9	1 19.3	0.0	85	4	43.7	29	6	29	5	60	9	74	4	6313	8
0. 0	0. 1	0. 1	1.0	0	0	0. 0	0	1	0	1	0	1	0	0	46	0
52.8	62.9	25 3	0.0	71	4	87.7	29	6	83	5	21	9	62	4	915	8
89.9	5.7	29.7	0.0	3	8	B9.9	33	6	53	6	75	5	2999	8	122770	2
9.0	17. 1	27. 1	0.0	41	0	32.9	69	0	7 a	9	72	0	56	0	454	9
33. 7	55.3	97.2	0.0	66	5	39.7	86	1	97	0	4B	9	59	5	6944B	4
33.8	55. 6	5.5	0. 0	29	7	86.8	89	4	44	4	43	4	43	7	99558	2
54. 0	19.5	96.0	ii. 0	42	9	44.0	63	4	5	4	29	9	42	9	6631	5
3.8	4.6	5.5	0. 0	7	7	2.8	4	4	6	4	2	4	3	7	478	2
31 .2	55. 5	14.7	0.0	56	4	4B. 1	48	7	59	5	1	7	1	4	3922	6
28.8	26.9	39.3	0.0	20	4	3.7	2	6	-1	5	2	9	31	4	-2574	2
de waarde van d		e doelfunctie		1 5	2z	74. IB
net 5imp	extabl	eau ziet	er :o	uit
13.5	12.2	o.o	0. 0	35.	5	31.0	9	2	31	1	6	0	IB	1	2496	3
39.4	53.3	0.0	0.0	78	3	27.3	-4	7	43	7	21	B	42.	6	2173	7
i.i. 2	0.6	1.0	' i. 0	0.	3	0.3	0.	7	0	9	0.	4	ii	6	16.	2
29.8	14.6	0.0	O.o	80	9	40. 1	62	7	IB	2	11	5	79.	T	4016	3
46.8	47.3	0.0	0.0	34	5	69.4	3.	0	62	6	2B.	0	4.	9	4480	6
26.3	7.2	o.o	0.0	46	0	10.0	-49	1	-75	8	12	6	6	9	4376	6
0.0	0.0	0. 0	1.0	o.	0	0. 0	0.	0	0.	0	0.	1	0.	0	44.	9
46.9	48.8	0.0	0. 0	63	t	80.6	12	9	61	2	1 1	7	48.	1	505	b
83. 1	-10.9	o.o	0.0	-6.	0	B1.5	14	0	27.	4	63.	5	2983.	o	1222BB.	3
2.8	1.9	0.0	0. 0	^2	0	25.3	51	2	55	9	61	0	40	6	14	4
11.4	1.0	0. 0	0. 0	34	3	12.2	21.	9	11.	2	9.	5	4.	4	67869.	5
32.6	52.5	0.0	0.0	27	9	85.3	85	B	39	5	41	1	41..	5	99468.	4
31.9	-34.2	0.0	0.0	11.	2	16.8	0.	1	-79.	4	-9.	0	-11.	4	5072.	1
2.6	1.5	o.o	0. 0	5	9	1.3	0.	8	1.	5	0.	1	2.	5	388.	4
27.8	47.4	0.0	0.0	51	5	44. O	39.	0	46	6	-4.	2	-6.	9	36B4.	6
19.7	4.9	0.0	0.0	7	5	-7.4	-23	3	-36	2	-13.	0	9	2	-3211	9

de riaarde van de doel f unct i e i s 3211. 86

net si mpl e>; tabl eau z i et er zo uiti


0	0	2	8	0	o	0	0	-118	6	-90	7	-237	1	-238	2	-2B7	6	-177	5	2427	1
0	0	26	0	0	0	u	0	-371	7	-328	1	-723	B	-742	5	-835	6	-528	6	1971	6
0	II	0	4	1	0	0	0	_2	3	-1	8	-3	5	-3	7	-4	6	-2	B	15	1
0	0	-6	0	0	0	0	0	-259	3	-228	5	-480	8	-576	1	-636	5	-352	5	3863	6
0	0	14	9	0	0	0	0	-499	7	-352	4	-B50	5	-870	5	-989	6	-673	1	4240	7
0	0	-11	0	0	0	0	0	-254	7	-227	5	-529	6	-601	2	-560	3	-374	B	4241	5
0	II	0	0	0	o	1	0	�0	1	-0	1	-0	1	-0	1	-0	1	-0	1	44	B
0	o	16	2	0	o	0	0	-473	1	-342	9	-843	9	-875	6-	-1009	8	-632	5	264	7
0	0	-68	4	0	0	0	0	-954	9	-667	B-	1502	0-	1630	1-	1744	0	1778	6	121862	2
1	0	0	7	0	0	0	0	11	4	9	0	18	3	20	0	21	8	14	5	5	1
0	0	-6	9	0	0	0	0	-95	7	-90.	4	-185	B	-215	9	-23B	1	-160	6	67811	1
0	0	30	0	0	0	0	0	-344	2	-208	6	-508	7	-610	4	-667	7	-431	7	99301	3
1'	0	-56	3	0.	0	0.	0	-353.	5	-271.	2	-582.	5	-716.	4	-703.	6	-474.	2	4908	4
0	0	-0	3	0	0	0	0	-23	5	-21	9	-46	1	-49	0	-55	8	-34	7	375	2
0	IJ	2B	1	0	0	0	0	-266	6	-207.	2	-469	2	-509.	1	-610	2	-410	7	3541	B
0	0	-8	7	0	0	1.1	0	-217	8	-185	3	-383	3	-429	8	-442	2	-276	8	-3313	0

de waarde van de doel -f unct i e i s 2
het simplextableau ziet er zo uit:


0. 0	-1.1	0. 0	0.0	-4	.8	-8.2	-34.0	-27	5	44	6	-25.4	2363	4
0.0	12.3	O.O	0.0	26	.7	-39.3	-13.2	� 5	2	14	B	4.0	1748	7
0.0	0. 3	1.0	0.0	1	3	0.8	2.8	2	9	3	0	2.0	13	1
0.0	-16.5	0. 0	0.0	46	.6	-6.8	64.8	-10	0	16	5	56.5	3692	4
0.0	-1.4	0.0	0.0	-26	6	-9.5	-6.6	5	0	20	2	-40.6	3976	0
0.0	-16. 1	0.0	0.0	-105	.3	-119.2	-263.1	-324	7	-241	4	-175.0	4157	9
0.0	0.0	i.i . 0	1.0	-0	1	-0. 1	-0. 1	-0	1	-0	1	-0. 1	44	8
0.0	3. 5	0.0	0. 0	-103	2	-74. a	-184.0	-190	9	-220	2	-137.9	57	7
0.0	-97.7	0. 0	0.0	-101	1	-49.0	20.7	-50	2	78	3	2919.9	121384	4
1.0	1. 1	0. 0	0.0	0	B	1.3	-0.8	0	2	-1	0	0.2	11	1
0.0	-7.4	0.0	0. 0	-81	5	-80. 1	-160.4	-189	5	-207	7	-141.5	67803	1
0.0	18.2	o.o	0.0	-2	.7	39.0	100. 4	21	6	61	3	24.8	99110	2
11.11	-64.3	0. 0	0.0	-118	7	-101.0	-163.7	-281	9	-202	5	-160.4	4777	0
0.0	-1.0	0. 0	IJ. 0	_2	2	-6.5	-8. 1	-10	3	-io	3	-6.2	363	2
0.0	18.4	0.0	0.0	14	4	-3.5	32.0	1 1	0	-10	4	-35.0	3384	5
0.0	-14.5	0.0	0.0	-50	6	-64.2	-85. 1	-120	4	85	4	-53.2	-3406	6
laarde van de		doelfunct i e		1 S	3406.60
5i mp	e>: tabl eau ziet		er zc	uit
0.0	-2. 1	0. 0	0.0	26	1	14.2	21.0	2V	6	21	3	15.9	2346	2
0.0	12.4	0.0	0.0	25	9	-40.0	-14.7	-6	7	13	0	2.9	1749	1
0.0	0.3	1.0	0.0	-0	2	-0.3	0. 2	0	2	-0	1	0.0	13	9
0.0	-15.6	0. 0	0.0	21	2	-25.2	19.4	-57	1	-37	9	22.5	3706	6
0.0	-0.9	0.0	0.0	-40.	0	-19.3	-30.7	-19.	9	-8.	5	-58.6	3983.	6
0.0	-20.9	0.0	0.0	32	2	-19.3	-17.8	-70	2	52	1	8.8	4081	0
0.0	0.0	0.0	1.0	0.	5	0.3	0.8	0.	8	1	0	0.6	44	6
O.O	14.4	0.0	0.0	-420	5	-304.7	-749.9	-778	t	-B97	4	-562.1	235	3
u. 0	-9B.4	0.0	0.0	-82	2	-35.3	54.5	-15	1	118	7	2945.2	121373	8
1.11	1. 1	0.0	0.0	1	0	1.5	-0.3	0.	7	-0	3	0.6	11	0
0.0	-11.8	0. 0	0.0	47	5	13.3	69.6	49.	1	67	5	30. 8	67731.	0
0.0	18.3	0.0	0.0	-b	0	36.6	94.5	15	3	54	2	20.4	99112	1
o.o	-68.0	0.0	0.0	-10.	6	-22.7	29.0	-81.	9	2B	1	-15.9	4716.	6
0.0	-1. 1	0.0	0.0	2	0	-3.4	-0.6	_2	6	-1	4	-0.6	360	9
0.0	19. 1	0. 0	0.0	-6.	0	-18.3	-4.4	-26.	8	�53.	9	-62.3	3395.	9
0.0	-15.4	0.0	0.0	-24	1	-44.9	-37.8	-71.	3	-2B	8	-17.8	-3421	4

de waarde van de doelfunctie is 3421.43

de opt i male oplossi ng is nu gevonden

-ocr page 64-

Op biz. 33 werd gesproken van een geval met 150 beslissingsvariabelen
en 250 spelingsvariabelen. Dat is nog niet erg veel. Bij het ontwerpen
van een olieraffinaderij gaat het om tienduizenden variabelen.

Het simplex-tableau voor een geval met 150 beslissingsvariabelen en 250
spelingsvariabelen zal er zd uitzien:


^xl	^x2		'"^X15C
«	�	�	�
■	�	■	�
� � � � t	� � � �	� � � � �	� � � � �
�	�	�	�

250

'250

■ �

» 113. Wat komt er in de matrix met het vraagteken te staan?

» 114. Hoe vind je een eerste basisoplossing?

Hoeveel variabelen moeten er nul zijn in een 'hoekpunt'?

Los de volgende problemen op met behulp van de computer; vergelijk de
output met je simplex-tableaus.

» 115. Het ale-/bierprobleem uit hoofdstuk 1.

» 116. Het probleem uit hoofdstuk 4.

» 117. Het bistroprobleem uit hoofdstuk 5.

» 118. Het medicijnenprobleem eveneens uit hoofdstuk 5,

-ocr page 65-

» 119. Een fabrikant maakt artikelen A en B.
De fabricage gebeurt in twee fasen:

- de hoofdbewerking in werkplaats I;

- de nabewerking, die voor beide produkten plaats kan vinden in
zowel werkplaats II als werkplaats III.

In werkplaats II is de mogelijkheid tot overwerk schematisch:

hoofdbewerking
werkplaats I;
capaciteit:
1000 uur

nabewerking
werkplaats III;
capaciteit:

1100 uur

nabewerking
werkplaats II;
capaciteit:

850 uur

nabewerking
werkplaats II
(OVERWERK);
capaciteit:
250 uur

I + II OVERWERK

KLAAR

Er zijn dus drie manieren om ieder produkt te maken.

Verder is gegeven:


werkplaats	bewerkingstijd per eenheid
werkplaats	A	B
I	0,8	0,5
II	0,4	0,5
III	0,5	0,6

(in uren)


produktie methode	winst op een eenheid
produktie methode	A	B
I + III	13	7
I + II	15	10
I + II OVERWERK	10	8

(in guldens)

-ocr page 66-

Bepaal bij welke produktie via welke methode er maximale winst
is. (Hint: er zijn 6 beslissingsvariabelen en 4 spelingsvariabe-
len).

» 120. Een schoenenfabrikant heeft een produktielijn waarop zes 'hande-
lingen' worden verricht en er worden acht produkten gemaakt.
Die acht produkten zijn N(ette schoenen), W(andelschoenen),
S(portschoenen) en L(aarzen). En van ieder een d(ames) en h(eren)
model.

Welke schoen op welke manier door de produktielijn gaat, zie je
in het volgende schema:

snijden

\, ,,

sierstiksel
capaciteit:

2400

uren.

N ^ir VL

in elkaar
zetten fase 1
capaciteit:
12000
uren

in elkaar
zetten fase 2
capaciteit:
12000 uren

in elkaar
zetten fase 2
capaciteit:
24000 uren

afwerking

-ocr page 67-

Voor de eerste en laatste fase van de produktie gelden geen beperkingen.
Wei voor de overige vier fasen, zoals uit het schema op de vorige blad-
zijde blijkt.

Produktietijden (in uren per partij schoenen):


Produkt	^Nh	^Nd	^Lh	^Ld	^Wh	^Wd	^Sh	^Sd
sierstiksel	5	6	4	4	-	-	-	-
1e fase	15	20	12	15	15	15	10	12
2e fase in I	30	20	-	-	20	30	-	-
2e fase in II	-	-	60	60	-	-	50	80


Winst per
partij in	250	250	200	200	250	300	200	250
guldens

Bepaal de produktiehoeveelheden voor maximale winst.

-ocr page 68-



				64

		B-Lj hojt ontiMQjvpzn van oLieAa^i.nadoxijzn kA.jkt men nieX op van L.P. ptwbtojnm met ti.dnduuiz<indm vaKiaboZin.

-ocr page 69-



		65

	GEMENGDE OPGAVEN

^ 121. a. Een jeneverstokerij produceert zowel jonge- als oude jenever. Gezien de aangevoerde hoeveelheid graan, kan er totaal hoog- stens 10 ton (1 ton = 1000 liter) jenever geproduceerd worden. Daarvan mag hoogstens 5 ton jonge jenever zijn wegens een te- kort aan etiketten. In het bedrijf werken 48 mensen. Voor het maken van 1 ton jonge jenever is 4 man nodig, voor 1 ton oude jenever 5 man. Wegens groot onderhoud zijn er hoogstens 240 alcoholstampers beschikbaar. Daarbij moet je weten dat men voor 1 ton jonge jenever 30 alcoholstampers gebruikt worden en voor 1 ton oude jenever 20. Stel de beperkende voorwaarden op en teken het toegestane ge- bied. De winst op 1 ton jonge jenever is / 4.000,� en op 1 ton oude jenever / 3.000,�. Teken de iso-winst-lijnen en bereken de maximale winst. b. De in opgave a. genoemde stokerij staat in Schiedam. Het zuster- bedrijf staat in Utrecht. In Schiedam ligt 10 ton jenever in voorraad en in Utrecht 8 ton. De Heer A. in Den Haag bestelt 8 ton. B. te Soest wenst 4 ton en C. te Haarlem wil zijn voorraad met 6 ton aanvullen.

-ocr page 70-

De verkoopleider van het jeneverconcern heeft als transport-
kosten-matrix (in guldens per ton):

NAAR

Haarlem
90
120

Den Haag Soest

Schiedam / 30 50

VAN

Utrecht 1 20 100

Stel uit Schiedam gaat X ton naar Den Haag en y ton naar Soest.

Maak een gerichte graaf.

Stel de beperkende voorwaarden op en teken het toegestane ge-

bied.

Bereken de totale transportkosten (in X en (/) .

Bepaal de minimale transportkosten.

» 122. In een kleine milkbar heeft men op zekere dag de beschikking over
24 liter melk, 21 liter ijs en 9 liter siroop.
Er worden twee soorten milkshakes verkocht:

'Alaska', samengesteld uit 2 dl melk, 3 dl ijs en 1 dl siroop.

'Little Prince', samengesteld uit 2 dl melk, 1 dl ijs en f dl

siroop.
Een 'Alaska' kost / 3,� en een 'Little Prince' / 2,�.

a. Bij welke verkochte aantallen milkshakes van elke soort is er
op die dag een maximale opbrengst?

De eigenaar koopt de melk voor / 1,� per liter, het ijs voor
/ 3,� per liter en de siroop eveneens voor / 3,� per liter in.

b. Bij welke verkochte aantallen milkshakes is de winst maximaal?

c. De eigenaar verandert zijn prijzen zodanig dat de winst maxi-
maal is bij de verkoop van 20 'Alaska's' en 100 'Little Prince's'.
De totale prijs van een 'Alaska' en een 'Little Prince' blijft
hetzelfde. Welke prijzen rekent hij nu?

-ocr page 71-



			67

		» 123. Een bedrijf in Hongkong heeft zich toegelegd op het fabriceren van Amerikaanse hardloopschoenen. Aanvankelijk maakt men twee modellen: Runner en Lady T. Het vervaardigen van 10 paar Runner kost 3 uur, terwijl men slechts 2 uur nodig heeft voor het maken van 10 paar Lady T. Vanwege de beperkte machinecapaciteit kan er per week hoogstens 300 paar Runner en 400 paar Lady T. geproduceerd wor- den. In totaal kan er per week niet meer dan 140 uur geproduceerd worden. Op 10 paar Runner wordt $60,- en op 10 paar Lady T. $50,- winst gemaakt. a. Stel de beperkende voorwaarden op, teken het toegestane gebied en vind m.b.v. iso-winst-lijnen de produktie waarbij maximale winst wordt geboekt. b. Runner blijkt goed in de markt te liggen en de winst per 10 paar stijgt. (De winst op Lady T. blijft hetzelfde.). Vanaf welke winst op Runner doet de fabrikant er goed aan zijn produktieverdeling te veranderen? De capaciteit van het bedrijf wordt uitgebreid zodat ook nog een derde type schoenen kan worden gemaakt: de Super A. Maximaal kan er 400 paar van dit nieuwe type gemaakt worden. Voor het vervaar- digen van 10 paar Super A is 2� uur nodig en de winst op Super A bedraagt $40,- (per 10 paar). Het totale aantal produktie-uren per week wordt met 70 uitgebreid (en wordt dus 210). c. Stel de beperkende voorwaarden op voor de nieuwe situatie en teken het toegestane gebied in een driedimensionaal assenstel- sel. d. Bepaal de maximale winst m.b.v. de randenwandelmethode (de winst op Runner is nu weer $60,- per 10 paar). Begin in de oorsprong: (0,0,0). » 124. In hoofdstuk 3 staat een transportprobleem: er zijn twee pakhui- zen en drie plaatsen waar het graan naar toe moet. lets lastiger is het volgende probleem: drie pakhuizen en twee plaatsen waar afgeleverd moet worden.

-ocr page 72-

De graaf is als volgt:

A1.5U;

P(60)

B(40)

Q(50)

rr?n1

plaaXi ptaaXi

ImeX voohAxuxd) (»ie^ geuie.ru>�e.

hoe.ve.zZhzid]

Wat zijn de minimale transportkosten in dit geval?
Hoeveel wordt er uit ieder pakhuis verscheept?

» 125. Een bierbrouwerij levert per week 11500 liter bier af in pijp-
jes, euroflessen en blikjes.

De inhoud van een blik en van een pijpje is 3 en de inhoud van
een eurofles is j liter.

Per week zijn er 1000 kratten en 23000 flessen beschikbaar. In
een krat gaan 24 pijpjes of 20 euroflessen.

De blikjes bier worden in dozen verpakt; in elke doos gaan 24 blik-
jes. In verband met een export-opdracht moeten er elke week mins-
tens 6000 blikjes bier afgeleverd worden.

De winst op een krat pijpjes is / 1,11 en op een krat euroflessen
/ 1,35. Aan een doos blikjes wordt / 1,� verdiend.
Bij welke hoeveelheid kratten pijpjes, kratten euroflessen en do-
zen blikjes incasseert de brouwer maxiraale winst?

» 126. Een oliemaatschappij heeft een voorraad van 200.000 barrels in
Koeweit. 150.000 in Galveston en 100.000 in Caracas.
Een klant in New York heeft 300.000 barrels besteld.
Een tweede klant in Londen wil de overige 150.000 barrels afnemen.

-ocr page 73-

De transportkosten in dollarcenten per barrel bedragen:


"^-\Naar Van^""^-\^	New Yc	rk	Londen
Koeweit	38		35
Galveston	10		22
Caracas	18		25

a. Maak een schema voor het transport van de totale voorraad van
de oliemaatschappij in het geval er 140.000 barrels van Koeweit
naar New York en 100.000 barrels van Galveston naar New York
worden getransporteerd.

Hoe groot zijn de transportkosten in dat geval?

b. Bereken door middel van lineair programmeren een transport-
schema waarbij de transportkosten minimaal zijn.

Een andere oliemaatschappij beschikt over acht depots en ver-
koopt haar totale voorraad aan zes klanten.

c. De bedrijfseconoom van deze maatschappij moet een optimaal
transportschema vaststellen.

Met hoeveel beslissingsvariabelen krijgt hij te maken?

» 127. Een bedrijf maakt vier modellen vliegtuigjes. Er worden twee uit-
voeringen van een sportvliegtuig gemaakt: de Super en de Economy.
Daarnaast worden er twee versies gemaakt van een zweefvliegtuig:
een echt zweefvliegtuig: de Zwever, en een met hulpmotor: de
Motorzwever.

Het schema voor de produktie staat op deze bladzijde. Daaruit
blijkt o.a. dat er naast het onderdelenmagazijn vijf produktie-
hallen zijn die alien een maximale capaciteit hebben.
Zo heeft hal I een produktiecapaciteit van 10.000 uur.
De produktietijden per model per hal staan ook in het schema ver-
meld: bijv. het in elkaar zetten van een 'Super' in hal I duurt
50 uur en het in elkaar zetten van een 'Economy' 40 uur.
Tenslotte is ook de winst af te lezen uit het schema: bij de
'verkoop' blijkt de winst op een 'Super' / 6.000,� te bedragen.

-ocr page 74-

///

ONDERDEIEN

G��N tePtRKINCCN

SO 1 dL. [40

MA /. /O. OOO UUR.

40J .SlT ~M

MOTOR TIT

lNBOUWENXLL

am*. 98oouvfL


		^US^
	<^	^^p^⁵⁷
	/Vl4)f.	22 5"0 t/y/?

SUPER

UITVOERING

AFWERKING

5\r yE \'MZ \fZ

W 4

VERKOOP

GE~t~N BCPCRKIHCEN

VERK1ARING


	su�^^		� W EeteVenti vinst per
	I 50 \| fietekent: er is in dexe fase een produkciecijd van 50 our voor het toeltel SUPER.		� W EeteVenti vinst per
			f. vliegtuig f/i v«n het L^J model SUPER ia / 6.000,--.

a. Stel een simplex-tableau op voor de berekening van de maximale
winst. (Je hoeft de berekening zelf niet uit te voeren).

-ocr page 75-



		71

	De berekening wordt door de computer uitgevoerd. De laatste drie tableaus die de computer levert, zien er als volgt uit: (1e kolom: Super; 2e kolom: Economy; 3e kolom: Motorzwever; 4e kolom: Zwever). HEI blKKLtXIMJLtflU ZIEI ER 20 UI I I O.OO 1.00 0.00 0.00 0.0J 0.00 0.00 -O.OB O.OO 62.10 0.00 0.00 0.00 25.00 1.65 1.00-1.50-1.50 O.OO i425.00 O.JO 0.00 1.00 0.00 -0.06 0.00 0.05 0.05 O.OO t.2.50 i.oo o.oo o.oo o.oo o.oo 0.00 o.oo 0.0/ 0.00 150.00 0.00 0.00 0.00 2.00 0.04 0.00 -0.15 -0.20 1.00 480.00 0.00 0.00 0.00 J.00 0.08 0.00 -0.1? -0.1/ 0.00 -MOy.JB Lit UAAKBE VAN DE DUELTUNUUE IS M0?.48 HEI SiflPLEX I rtbLEftU Zlfcl EK 2.U Ull: 0.00 1.00 0.00 0.00 O.0J 0.00 0.00 -0.08 0.00 62.50 0.00 0.00 0.00 1.00 0.0/ 0.04 -0.06 -0.06 0.00 li/.OO 0.00 0.00 1.00 0.00 -0.06 0.00 0.05 0.05 0.00 52.50 1.00 0.00 0.00 0.00 0.00 0.00 0.00 0.0/ O.OO 150.00 0.00 0.00 0.00 0.00 -0.0? -0.08 -0.0J -0.08 l.OO 206.00 O.OO 0.00 O.OO 0.00 -0.12 -0.12 0.00 0.00 O.OO -1820.J8 LIE WflftKUE VAN DE DUELFUNCIIE IS 1820.48 HEI SIW-'LEX TABLEAU MET ER 20 UIT: O.OO 1.00 1.6/ 0.00 -0.0/ 0.00 0.08 0.00 0.00 150.00 O.OO 0.00 1.20 1.00 0.00 0.04 0.00 0.00 O.OO 200.00 0.00 0.00 20.00 0.00-1.10 0.00 1.00 1.00 O.OO 1050.00 1.00 0.00 -1.J3 0.00 0.0/ 0.00 -0.0/ 0.00 0.00 bO.OO 0.00 0.00 1.60 0.00 -0.18 -0.08 0.05 0.00 1.00 :2?0.00 0.00 0.00 -0.18 0.00 -0.11 -0.12 -0.02 0.00 O.OO -1840.00 OE WAAKUE VAN LIE DUELFUNI'IIE IS 1840.00 LIE UPIINALE UPLUSSlNti IS NU LitVUNLIEN

Aan de hand van deze tableaus moeten de directeuren een beslis- sing nemen over de te produceren aantallen toestellen. De ene directeur (A) wil per se het produktieschema uitvoeren dat tot maximale winst leidt. De andere directeur (B) oppert de mogelijkheid om te produceren volgens het middelste tableau: de winst is wat minder, maar aJLl.2, V-LQA. modellen worden geproduceerd. b. Bepaal aan de hand van de simplex-tableaus hoeveel stuks er van ieder model gemaakt moeten worden, als directeur (A) zijn zin krijgt en hoeveel als directeur (B) zijn zin krijgt. c. Bepaal bij ieder van de onder b. genoemde produktiemogelijkhe- den de Q<uni,dd<itdz winst per vliegtuig.

-ocr page 76-



			72

		SAMENVATTING In hoo^ditak 1 wordt kennisgemaakt met een lineair programmeringspro- bleem. Het mathematiseren vindt in kleine stapjes plaats. Het probleem werd grafisch, met niveaulijnen opgelost. In koo^d&tuk 1 volgden meer dergelijke problemen, waarbij het steeds ging om het maximaliseren of minimaliseren van een doelfunctie op een toelaatbaar gebied. In hoofidAtuk 3 zagen we een iets andere soort lineaire programmerings- problemen: transportproblemen. In de eerste drie hoofdstukken betrof het uitsluitend problemen met tw&2. beslissingsvariabelen. Deze zijn grafisch met niveaulijnen op te lossen. In hoo^d&tuk 4 worden enkele - zorgvuldig uitgekozen - voorbeelden be- studeerd in drie variabelen, waarbij snel blijkt dat wivncuivtakkzn nau- welijks een oplossing bieden. Als alternatief bestuderen we de waarde van de doelfunctie in een hoekpunt en wandelen naar een hoger hoekpunt tot we niet hoger kunnen. Dit is dan het maximum, omdat een toelaatbaar gebied altijd convex is. In hoo^di>tuk 5 oefenen we dit randenwandelen in twee voorbeelden. In hoo&dAtuk 6 worden de voorbereidingen getroffen om tot een profes- sionelere randenwandelmethode, de simplexmethode, te komen. Het toelaat- bare gebied wordt niet geschreven als een aantal ongelijkheden, maar als een aantal vergelijkingen. Die zijn immers gemakkelijker oplosbaar. We gebruiken daarbij ipeZing^vaAlabzlzn. In hoofadAtuk 7 wordt geoefend met de begrippen kanonieke vorm, beslis- singsvariabelen en spelingsvariabelen. Verder werd duidelijk dat, als er 150 beslissingsvariabelen en 250 spelingsvariabelen zijn, we een sys- teem van 250 vergelijkingen met 400 onbekenden krijgen. In ieder hoekpunt geldt dat er 150 variabelen gelijk aan nul zijn. Vul je dat in de kano-

-ocr page 77-



			73

		nieke vorm in, dan blijft er een systeem van 250 vergelijkingen met 250 onbekenden over. In koofad-btilk S zien we een methode waarmee je een stelsel van 250 verge- lijkingen met 250 onbekenden (in principe) op kunt lossen. (Veegmethode). In hoo^dbtuk 9 wordt de &A.mpZe.xme.thod<L aan de hand van een gedetailleerd voorbeeld uitgelegd. Hoe dat gaat vind je samengevat op de eerste blad- zijde van hoo^ditak 10. Verder tref je daar nog enige problemen aan, die met de simplexmethode opgelost kunnen worden. In hoofid&tuk J/ wordt tenslotte ingegaan op de manier waarop de computer ons al het rekenwerk uit handen kan nemen. In hoo{)d&�-uk 7 2 zijn een aantal gemengde opgaven opgenomen.

(de hoeveelheden

in dollars).