Transportproblemen.

© h.hofstede (h.hofstede@hogeland.nl)

       
Ook bij zogenaamde transportproblemen krijg je vaak te maken met toelaatbare gebieden.
Niet letterlijk natuurlijk...

Het gaat daarbij om goederen die vervoerd moeten worden,
Hiernaast zie je schematisch wat er aan de hand is.

Er is een aantal bronnen (B) met hoeveelheden B1, B2, B3, ... aanwezig.
Er zijn markten (M) waar de vraag gelijk is aan M1, M2, M3, ...

De goederen moeten van B naar M worden vervoerd.
We nemen aan dat er voldoende goederen zijn om alle vraag te beantwoorden (dus de B's zijn samen meer dan de M's).
Verder is bekend dat het transport van bron Bi naar markt Mj bepaalde kosten per hoeveelheid goederen met zich meebrengt.

De vraag is:  Hoe moeten de goederen naar de markten worden vervoerd als het totale transport zo goedkoop mogelijk moet?

       
Tijd voor een concreet voorbeeld.
       
Een computerwinkelketen heeft drie winkels, eentje in Groningen, eentje in Roermond en eentje in Nijmegen. De computers daarvoor moeten uit centrale magazijnen in Utrecht en Amsterdam komen.
Het magazijn in Amsterdam heeft 400 computers op voorraad en dat in Utrecht 300 computers.
De winkel in Groningen heeft 150 computers nodig, die in Roermond 350 en die in Nijmegen 200. De vervoerskosten per computer van magazijn naar winkel staan in de volgende tabel.
       
  Groningen Roermond Nijmegen
Utrecht 11 8 6
Amsterdam 12 10 9
       
Hoe kan men dit vervoersprobleem zo goedkoop mogelijk oplossen?
       
Op de eerste plaats moet je je realiseren dat alles precies "past". Er zijn in totaal 700 computers nodig en ook 700 op voorraad.
Zie de figuur hiernaast.
Stel dat er x computers van Utrecht naar Groningen gaan, en y van Utrecht naar Roermond.
Dan gaan er 300 - x - y van Utrecht naar Nijmegen, immers alles uit Utrecht moet weg.
Dan gaan er 150-x van Amsterdam naar Groningen immers Groningen moet er 150 krijgen. En op dezelfde manier gaan er  350-y van Amsterdam naar Roermond en  200 - (300 - x - y) = x + y - 100 van Amsterdam naar Nijmegen.

       
Wat zijn de beperkende voorwaarden?

Die zijn bij transportproblemen altijd erg makkelijk:
       
Alle vervoerde hoeveelheden zijn positief
       
In dit voorbeeld geeft dat de volgende zes vergelijkingen:

x,  y ≥ 0
150 - x ≥ 0
350 - y ≥ 0
300 - x - y ≥ 0
x + y - 100 ≥ 0

       
Wat is de doelstellingsfunctie?
       
Dat is uiteraard dat de totale kosten zo laag mogelijk zijn. Met de vervoerde hoeveelheden uit de figuur en de tabel met de kosten geeft dat voor de totale kosten K:
K = 11x + 8y + 6(300 - x - y) + 12(150 - x) + 10(350 - y) + 9(x + y - 100)
K = 11x + 8y + 1800 - 6x - 6y + 1800 - 12x + 3500 - 10y + 9x + 9y - 900
K = 2x + y + 8200
     
Dat geeft het toelaatbare gebied hiernaast, met daarin twee niveaulijnen; namelijk K = 8400 en K = 8500.
Daaraan kun je zien dat de goedkoopste manier van vervoer zal zijn als je kiest voor punt P (De niveaulijnen schuiven in de richting van lagere K naar linksonder)

Dat betekent dat x = 0 en y = 100.
De te vervoeren hoeveelheden zijn als in de volgende tabel:

 
  Groningen Roermond Nijmegen
Utrecht 0 100 200
Amsterdam 150 250 0
 
Het gaat K = 2 • 0 + 100 + 8200 = €8300 kosten.
       
En als de hoeveelheden niet precies "passen"?
       
In bovenstaand voorbeeld waren er precies 700 computers in voorraad en ook 700 computers nodig. Daarom waren die te vervoeren hoeveelheden makkelijk op te stellen. Je wist dat alles vervoerd zou moeten worden. Wat moet je doen als er meer computers in voorraad zijn dan besteld?

Dat is heel eenvoudig:  voeg een fictieve winkel  "Niet" toe, en doe alsof daar de extra computers heen moeten. De vervoerskosten erheen stel je uiteraard gelijk aan nul. Dat stelt dus de computers voor die in voorraad blijven.
En als de voorraad kleiner is dan de bestelling? Dan doe je gewoon alsof er een extra "Leeg" magazijn is waarin precies de ontbrekende computers staan. De vervoerskosten vanaf dit magazijn stel je gewoon allemaal gelijk aan nul.

(in deze gevallen geeft dat wel een probleem trouwens:  met nog een winkel (Niet) of magazijn (Leeg)  erbij zijn er drie variabelen nodig,  en valt het toelaatbare gebied lastig te tekenen; dat zou ruimtelijk worden!)
       
           
  OPGAVEN
           
1. Een juwelier heeft diamanten nodig voor zijn drie ateliers A1, A2 en A3. Hij bestelt die bij twee diamantgroeves, G1 en G2. Voor de ateliers heeft hij respectievelijk 400, 400 en 200 diamanten nodig. Dat komt mooi uit, want beide groeves hebben op dit moment 500 diamanten in voorraad. 

Uit veiligheidsoverwegingen wordt elke diamant apart vervoerd door een fietskoerier die in dienst van de groeves is, en  €2,- per km kost (alleen de "heenweg" hoeft betaald te worden).
De afstanden tussen de groeves en de ateliers staan in de volgende tabel.
           
 
  A1 A2 A3
G1 10 20 10
G2 10 18 20
           
  Teken een toelaatbaar gebeid en bereken daarmee de goedkoopste manier om de bestelling te verwezenlijken.
           
2. Een automerk heeft drie fabrieken in de plaatsen A, B en C. Verder zijn er twee handelaren in de plaatsen D en E. In het komende kwartaal kunnen de fabrieken respectievelijk 1000, 1500 en 1200 auto's produceren.
De vraag van de twee handelaren is respectievelijk 2300 en 1400 auto's.
De transportkosten per auto  tussen de fabrieken en de handelaren staan in de volgende tabel.
           
 
  handelaar D handelaar E
fabriek A 80 215
fabriek B 100 108
fabriek C 102 68
           
  Los het transportprobleem voor de fabrieken voor het komende kwartaal op.
Bereken minimale transportkosten.
           
3. Bij een distributiecentrum voor dagbladen is een voorraad van 600 stuks Algemeen Dagblad en 800 stuks Telegraaf aanwezig.
Er komt op dat moment een vraag van twee kiosken.
Kiosk A wil graag 500 kranten, kiosk B wil graag 700 kranten.
Het maakt de kiosken niet zoveel uit welke kranten het zijn.
De kiosken betalen de volgende bedragen voor de kranten:
           
 
  kiosk A kiosk B
Algemeen Dagblad 0,12 0,13
Telegraaf 0,15 0,15
           
  Stel een transportschema op, teken een toelaatbaar gebied en bepaal wat de maximale opbrengst voor het distributiecentrum zal zijn (Neem aan dat er geen onkosten zijn, alleen maar opbrengst).
           
  a. Stel een transportschema op, teken een toelaatbaar gebied en bepaal wat de maximale opbrengst voor het distributiecentrum zal zijn (Neem aan dat er geen onkosten zijn, alleen maar opbrengst).
         

€172,-

  b. Bereken ook de minimale opbrengst waarbij wel de kiosken de aantallen kranten krijgen waarom ze gevraagd hebben.
         

€163,-

           
4. Voor de drie noordelijke provincies vinden in Assen en Leeuwarden bijscholingscursussen plaats voor achteropgeraakte leraren. In Assen kunnen 50 mensen meedoen, in Leeuwarden 80. De deelnemers krijgen de openbaar vervoerskosten vanuit hun woonplaats naar de cursusplaats vergoed. De organiserende instantie wil deze kosten uiteraard zo laag mogelijk houden.
Uit Groningen komen 30 leraren, uit Drente 40 en uit Friesland 60.
In de volgende tabel staan de gemiddelde vervoerskosten vanaf een bepaalde provincie naar de cursusplaatsen.
           
 
  Assen Leeuwarden
Groningen €6,00 €12,00
Drente €2,00 €19,00
Friesland €18,00 €7,00
           
  Stel een transportschema op en bereken bij welk transport de kosten minimaal zijn.
           
5. Op het jaarlijkse koude buffet van de Weight Watchers staan 3 heerlijke schotels uitgestald, elk met precies één kg voedsel.  Schotel 1 bevat rauwe wortels, schotel 2 tarwekoekjes en schotel 3 heerlijke droge rijst.

De twee dames  Els en Harma lopen er likkebaardend langs.
Ze gaan samen alles opeten!!

"Ach", zegt Els, van de wortels die ik eet kom ik per 100 gram 2 gram aan, van de tarwekoekjes slechts 1 gram per 100 gram die ik eet en van rijst wordt ik maar liefst 4 gram dikker voor elke 100 gram die ik ervan eet.
"Mazzelaar", roept Harma jaloers. "Ik groei van 100 gram wortels 3 gram, en van 100 gram koekjes 4 gram en van 100 gram rijst maar liefst 6 gram!"
 
Gulzig verdelen beide vrouwen het voedsel van de drie schalen over hun borden. Na afloop zijn hun beide borden even zwaar beladen.
     
  a. Waarom is dit een transportprobleem?
           
  b. Hoe moeten de dames het voedsel verdelen als ze in totaal samen zo min mogelijk willen aankomen?
         

Els: 0, 1, 0.5
Harma 1, 0.5, 0

           
6. De  penningmeester van leerlingenvereniging Advendo moet geld overmaken. Hij heeft daarvoor een lopende rekening en een spaarrekening waar beiden €1000,- op staat. Op deze rekeningen mag je niet rood staan. Hij moet vanwege de laatste Advendo-avond een slijterij nog €500,- betalen en een supermarkt nog €800,-.
           
  a. Stel een transportschema op en teken het toelaatbare gebied.
           
  De bank rekent echter administratiekosten. De slijterij heeft een bankrekening, en overmaken van bank naar bank kost vanaf de lopende rekening 0,5% van het overgemaakte bedrag, en vanaf de spaarrekening 1%.
De supermarkt heeft een girorekening en overmaken van bank naar giro kost vanaf de lopende rekening 1% van het overgemaakte bedrag en vanaf de spaarrekening 2%.
           
  b. Stel een kostenfunctie op en bereken hoe de penningmeester de bedragen zo goedkoop mogelijk kan overmaken.
           
7. examenvraagstuk VWO Wiskunde A, 1983.
           
  Een oliemaatschappij heeft een voorraad van 200000 barrels in Koeweit, 150000 in Galveston en 100000 in Caracas. Een klant in New York heeft 300000 barrels besteld. Een tweede klant in Londen wil de overige 150000 barrels afnemen. De transportkosten in dollarcenten per barrel bedragen:
           
 

Naar

Van
New York 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 140000 barrels van Koeweit naar New York en 100000 barrels van Galveston naar New York worden getransporteerd.
Hoe groot zijn de transportkosten in dat geval?
           
  b. Bereken door middel van lineair programmeren een transportschema waarbij de transportkosten minimaal zijn.
           
  Een andere oliemaatschappij beschikt over acht depots en verkoopt haar totale voorraad aan zes klanten.
           
  c. De bedrijfseconoom van deze maatschappij moet een optimaal transportschema vaststellen. Met hoeveel beslissingsvariabelen krijgt hij te maken?
           
       

© h.hofstede (h.hofstede@hogeland.nl)