Lineair programmeren

Opgave 7

De doelfunctie `W = 16x_1 + 20x_2` heeft een aantal randvoorwaarden. Met behulp van de simplexmethode is het maximum van `W` bepaald.

Het laatste simplextableau is:

`x_1`	`x_2`	`s_1`	`s_2`	`s_3`
`0`	`1`	`0,125`	`text(-)0,75`	`0`	`31,25`
`1`	`0`	`text(-)0,125`	`1,75`	`0`	`18,75`
`0`	`0`	`1`	`text(-)20`	`1`	`150`
`0`	`0`	`text(-)0,5`	`text(-)13`	`0`	`text(-)925`

a

Hoeveel spelingsvariabelen zijn er gebruikt?

b

Leg uit waarom dit de eindsituatie is.

c

Hoe groot is de maximale waarde van `W` en hoe groot zijn dan de waarden van `x_1` en `x_2` ?

Opgave 8

Maximaliseer `W = x_1 + x_2` onder de randvoorwaarden:

`x_1 ge 0`
`x_1 + 2x_2 le 160`
`0 le x_2 le 60`
`4x_1 + x_2 le 400`

Maak gebruik van simplextableaus. Rond af op twee decimalen.

Opgave 9

Een aantal Europese luchtvaartmaatschappijen heeft standaardafmetingen voor containers voor goederenvervoer ingevoerd. Die containers passen in alle vliegtuigen van deze maatschappijen; één container per vliegtuig. Lege containers terugvliegen naar hun thuishaven is duur, zodat deze maatschappijen hebben besloten om die containers onder te brengen in een gemeenschappelijk fonds, een zogenaamde "pool" . Elk van de aangesloten maatschappijen mag alle op haar thuishaven aanwezige containers uit deze pool gebruiken voor vervoer naar een of meer luchthavens die bij de pool zijn aangesloten. Daardoor kan het gebeuren dat er op zeker moment op bepaalde luchthavens een overschot aan containers is en een tekort op andere. Tegen zo gering mogelijke kosten moet van tijd tot tijd een herverdeling plaatsvinden.

Op een bepaald moment doen zich deze overschotten en tekorten voor:

overschot		tekort
Athene	400	Amsterdam	500
Berlijn	300	Dublin	300
Londen	680	Lissabon	780
Rome	200

In de afstandstabel zijn enkele onderlinge afstanden in kilometer van deelnemende luchthavens weergegeven.

	Amsterdam	Dublin	Lissabon
Athene	2700	3300	4000
Berlijn	700	1500	2900
Londen	200	400	2000
Rome	1800	2100	2600

Het is de bedoeling om het totaal aantal vliegkilometers zo klein mogelijk te houden.

a

Waarom zijn niet alle onderlinge afstanden in de afstandstabel opgenomen?

b

Maak een transportschema. Hoeveel beslissingsvariabelen zijn er?

c

Noteer alle randvoorwaarden en de doelfunctie.

d

Om hoeveel spelingsvariabelen gaat het als je de simplexmethode gebruikt?

e

Los het probleem op met de simplexmethode die in de Excel Oplosser is ingebouwd.

Opgave 10

De firma Splinter maakt prima houtvrij papier met een machine die rollen van `2` meter breedte produceert. De productiekosten zijn € 60,00 per rol. Deze rollen kunnen in de breedte worden versneden tot rollen van kleinere breedte. Er is vraag naar rollen van `60` centimeter, `90` centimeter en `120` centimeter. Per dag kunnen hiervan hoogstens respectievelijk `9` , `10` en `6` rollen op de markt worden afgezet tegen € 30,00, € 40,00 en € 50,00 per rol. Snijresten zijn onverkoopbaar.

Bereken met de hand hoeveel rollen van `2` meter per dag moeten worden geproduceerd en op welke wijze deze moeten worden versneden om de winst te maximaliseren.

(naar: Pythagoras (wiskundetijdschrift voor jongeren))

Opgave 11

Een raffinaderij gebruikt `3` soorten grondstoffen, A, B en C en produceert `3` eindproducten X, Y en Z. Grondstof A kost `6` euro/ton, grondstof B `8` euro/ton en grondstof C `9` euro/ton.

Er worden 4 productieprocessen uitgevoerd:

proces	grondstoffen	eindproducten
1	1 ton A 3 ton B	2 ton X 1 ton Y 1 ton Z
2	1 ton A 2 ton C	3 ton Z
3	2 ton B	1 ton Y 1 ton Z
4	1 ton B 1 ton C	2 ton X

De productiekosten zijn bij deze productieprocessen per ton grondstof achtereenvolgens `14,5` ; `5` ; `13` en `3,5` euro. Elke productieperiode worden deze vier processen uitgevoerd en daarbij zijn de vaste kosten `400` euro. De maximale capaciteit per periode is `20` ton van grondstof A, `40` ton van grondstof B en `30` ton van grondstof C en voor de processen 2 en 4 samen maximaal `40` ton aan grondstoffen.

Het gaat om de maximaal haalbare winst per productieperiode. De verkoopprijzen per ton zijn voor X, Y en Z respectievelijk `26` , `28` en `32` euro.

a

Om welke beslissingsvariabelen gaat het hier?

b

Geef een formule voor de winst `W` .

c

Schrijf alle randvoorwaarden op.

d

Om hoeveel spelingsvariabelen gaat het als je de simplexmethode gaat gebruiken?

e

Los het probleem op met de simplexmethode die in de Excel Oplosser is ingebouwd.

Verwerken