Springen naar inhoud

Lineair programmeren.


  • Log in om te kunnen reageren

#1

thrm

    thrm


  • >25 berichten
  • 26 berichten
  • Gebruiker

Geplaatst op 18 december 2008 - 14:13

Ik heb de volgende opgave:

McRonald maakt voor een zusterbedrijf elke week twee soorten steak sauzen: Spicy Gonzales en
Cool Gringo. Elk van de sauzen wordt gemaakt door het mengen van twee ingrediÄenten, die we
A en B noemen. Hoewel een zekere mate van vrijheid is toegestaan bij het maken van de sauzen,
moet voldaan worden aan de volgende eisen:
1. Cool Gringo mag niet voor meer dan 75% bestaan uit ingrediÄent A;
2. Spicy Gonzales moet voor tenminste 25% uit ingrediÄent A en voor tenminste 50% uit
ingrediÄent B bestaan;
3. Per week kunnen ten hoogste 40 liter van ingrediÄent A en ten hoogste 30 liter van ingrediÄent
B worden ingekocht.
McRonald kan tegen een prijs van 7 euro per liter Spicy Gonzales en tegen een prijs van 6 euro
per liter Cool Gringo de sauzen verkopen, terwijl de ingrediÄenten A en B resp. 3 en 4 euro per
liter kosten. McRonald wil zijn winst maximaliseren.
Stel hiervoor een lineair programmeringsprobleem op en los dit op.


en ik wil dit in een stelsel zetten zoals in de volgende voorbeeldopgave:

Een bedrijf produceert 4 producten: A, B, C en D. Ieder product vereist, per eenheid die wordt
geproduceerd, een gegeven aantal uren werk op 3 machines en eveneens een bepaalde gegeven
hoeveelheid grondstof (in kg). De 3 machines zijn 400, 500 resp. 300 uur beschikbaar, en er is
150 kg grondstof aanwezig. Ieder product levert per eenheid een bepaalde winst op (in euro's).
De gegevens van dit probleem staan in onderstaande tabel.
A B C D beschikbaar
machine 1 1.0 1.0 0.5 0.5 400
machine 2 0.5 0.7 0.8 0.5 500
machine 3 0.3 0.2 0.5 0.3 300
grondstof 0.2 0.3 0.2 0.2 150
winst 5 12 6 7
Hieruit is bijvoorbeeld af te leiden dat de productie van ¶e¶en eenheid van product B 1 uur op
machine 1, 0.7 uur op machine 2 en 0.2 uur op machine 3 nodig heeft, 0.3 kg grondstof vereist en
12 euro aan winst oplevert.


Het lukt me echter niet. Help ? :D

Dit forum kan gratis blijven vanwege banners als deze. Door te registeren zal de onderstaande banner overigens verdwijnen.

#2

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 18 december 2008 - 16:29

Ik meen dit te kunnen oplossen met 6 variablen. Laat eens zien wat je zou kunnen vinden.
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

#3

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 18 december 2008 - 17:05

Is er ook iets gegeven over de minimale hoeveelheid saus die van elke soort wekelijks moet worden geproduceerd? Ik kom namelijk uit dat er enkel Spicy Gonzales moet worden geproduceerd.

EDIT: met mijn oplossingsmethode vindt de computer geen aparte oplossing. (Telkens een andere)
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

#4

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 18 december 2008 - 17:41

Ik ga toch even zelf mijn oplossing geven dan kan ik mogelijk wat bijleren.

x1 aantal l A per week
x2 aantal l B per week
x3 aantal l A in Spicy Gonzales
x4 aantal l B in Spicy Gonzales
x5 aantal l A in Cool Gringo
x6 aantal l B in Cool Gringo

Constraint:
x3+x5<x1
x4+x6<x2
x5/(x5+x6)<0,75
x3/(x3+x4)>0,25
x4(x3+x4)>0,5

x1<40
x2<30

De te maximaliseren functie:
7(x3+x4)+6(x5+x6)-3(x3+x5)-2(x4+x6) = 4 x3 + 3 x4 + 3 x5 + 2 x6

Dit zou moeten werken. Ik maakte een foutje bij het invoeren in de computer.
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

#5

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 18 december 2008 - 18:48

Ik meen dit te kunnen oplossen met 6 variablen.

Dan heb je er twee te veel.

#6

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 19 december 2008 - 11:18

:D ik had het kunnen weten. Ik kom op een maximale winst van 230€. Met x={40,30,25,25,15,5}

In GNU octave:
Verborgen inhoud
c=[0;0;4;3;3;2];
a=[-1,0,1,0,1,0;
0,-1,0,1,0,1;
0,0,0,0,0.25,-0.75;
0,0,0.75,-0.25,0,0;
0,0,-0.5,0.5,0,0];
b=[0;0;0;0;0];
ctype="UUULL";
[xopt, fmax, status, extra] = glpk (c, a, b, [], [40,30,40,30,40,30], ctype,"CCCCCC",-1)
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

#7

Fred F.

    Fred F.


  • >1k berichten
  • 4168 berichten
  • Pluimdrager

Geplaatst op 19 december 2008 - 19:36

McRonald maakt voor een zusterbedrijf elke week twee soorten steak sauzen: Spicy Gonzales en
Cool Gringo. Elk van de sauzen wordt gemaakt door het mengen van twee ingrediÄenten, die we
A en B noemen. Hoewel een zekere mate van vrijheid is toegestaan bij het maken van de sauzen,
moet voldaan worden aan de volgende eisen:
1. Cool Gringo mag niet voor meer dan 75% bestaan uit ingrediÄent A;
2. Spicy Gonzales moet voor tenminste 25% uit ingrediÄent A en voor tenminste 50% uit
ingrediÄent B bestaan;
3. Per week kunnen ten hoogste 40 liter van ingrediÄent A en ten hoogste 30 liter van ingrediÄent
B worden ingekocht.
McRonald kan tegen een prijs van 7 euro per liter Spicy Gonzales en tegen een prijs van 6 euro
per liter Cool Gringo de sauzen verkopen, terwijl de ingrediÄenten A en B resp. 3 en 4 euro per
liter kosten. McRonald wil zijn winst maximaliseren.
Stel hiervoor een lineair programmeringsprobleem op en los dit op.

De juiste Linear Programming formulering van dit probleem is:

Variabelen:
A = aantal liters ingekochte A per week
B = aantal liters ingekochte B per week
C = aantal liters verkochte Cool gringo per week
S = aantal liters verkochte Spicy gonzales per week

Beperkingen:
A :D 40
B :P 30
A - 0,75C :D 0
0,25S - A :P 0
0,5S - B :P 0
C + S - A - B :D 0

Doelfunctie:
Maximaliseer: 7S + 6C - 3A - 4B

en ik wil dit in een stelsel zetten zoals in de volgende voorbeeldopgave:
.........
.......
Het lukt me echter niet. Help ?

Ik weet niet wat je hiermee bedoelt.
Het tweede probleem is toch anders van struktuur dan het eerste.
Hydrogen economy is a Hype.

#8

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 19 december 2008 - 19:48

@Fred F. : Kom jij hetzelfde uit. (Wss wel hoor :D )
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

#9

Fred F.

    Fred F.


  • >1k berichten
  • 4168 berichten
  • Pluimdrager

Geplaatst op 19 december 2008 - 20:13

Ik heb nu geen LP bij de hand dus ik weet de juiste antwoorden niet. Ik vermoed echter dat dit een huiswerkvraagstuk is dus daarom geef ik voor de topicstarter de juiste formulering in lineaire vergelijkingen zoals die in een LP ingevoerd worden. En zoals EvilBro al voorspelde zijn er inderdaad maar 4 variabelen nodig.
Hydrogen economy is a Hype.

#10

Fred F.

    Fred F.


  • >1k berichten
  • 4168 berichten
  • Pluimdrager

Geplaatst op 19 december 2008 - 23:25

Ik heb eerder een fout gemaakt in de formulering van enkele beperkingen.
A kan maximaal voor 75 % in C en maximaal voor 50 % in S voorkomen, dus A :P 0,75C + 0,50S
B kan maximaal voor 100 % in C en maximaal voor 75 % in S voorkomen, dus B :P C + 0,75S

Voor alle duidelijkheid hier de volledige gecorrigeerde LP formulering:

Variabelen:
A = aantal liters ingekochte A per week
B = aantal liters ingekochte B per week
C = aantal liters verkochte Cool gringo per week
S = aantal liters verkochte Spicy gonzales per week

Beperkingen:
A :D 40
B :P 30
A - 0,75C - 0,50S :P 0
B - C - 0,75S :D 0
C + S - A - B :D 0

Doelfunctie:
Maximaliseer: 7S + 6C - 3A - 4B

Als ik dit in een LP run dan krijg ik:
A = 40
B = 30
C = 20
S = 50
Winst = 230 Euro

Dit is hetzelfde als jhnbk vond op zijn manier.
Hydrogen economy is a Hype.

#11

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 20 december 2008 - 09:37

Ik vermoed echter dat dit een huiswerkvraagstuk is dus daarom geef ik voor de topicstarter de juiste formulering in lineaire vergelijkingen zoals die in een LP ingevoerd worden.

Ik heb daar nooit lessen over gehad helaas.
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.

#12

EvilBro

    EvilBro


  • >5k berichten
  • 6703 berichten
  • VIP

Geplaatst op 20 december 2008 - 12:13

Ik heb daar nooit lessen over gehad helaas.

Wat bedoeld wordt is dat de volgende conditie gewoon even omgeschreven moet worden naar een equivalent dat wel past in lineair programmeren.
LaTeX
Anders krijg je het niet lekker in je matrix. :D

Ik vind trouwens de methode van Fref F. moeilijk te volgen. Hetgeen ik moeilijk vind is de link te leggen tussen de beperkingen en zijn formules die deze beperkingen beschrijven. Ik zeg overigens niet dat de methode fout is (ik kan de fout, als die er in zit, niet vinden).

#13

Fred F.

    Fred F.


  • >1k berichten
  • 4168 berichten
  • Pluimdrager

Geplaatst op 20 december 2008 - 12:28

Ik vind trouwens de methode van Fred F. moeilijk te volgen. Hetgeen ik moeilijk vind is de link te leggen tussen de beperkingen en zijn formules die deze beperkingen beschrijven.

Daarom schreef ik al eerst voor de duidelijkheid:

A kan maximaal voor 75 % in C en maximaal voor 50 % in S voorkomen, dus A :P 0,75C + 0,50S
B kan maximaal voor 100 % in C en maximaal voor 75 % in S voorkomen, dus B :D C + 0,75S

Met andere woorden: de eerste is de volumebalans voor alle A en de tweede is de volumebalans voor alle B.
De laatste beperking C + S - A - B :D 0 is de totale volumebalans: er kan nooit meer C + S gemaakt worden dan er A + B is. Deze is nodig omdat het model anders unbounded zou zijn. Omdat jhnbk met 6 i.p.v. 4 variabelen werkt, en daardoor met meer beperkingen, heeft hij die niet nodig.
Hydrogen economy is a Hype.

#14

jhnbk

    jhnbk


  • >5k berichten
  • 6905 berichten
  • VIP

Geplaatst op 24 december 2008 - 09:59

Wat bedoeld wordt is dat de volgende conditie gewoon even omgeschreven moet worden naar een equivalent dat wel past in lineair programmeren.
LaTeX


Anders krijg je het niet lekker in je matrix. :D

In mijzelf had ik dat wel even gedaan :P (Kijk maar naar mijn octave input) en ging er van uit dat de topicstarter dat wel zou weten.

Ik bedoelde dat ik LP probleempjes eens op mijzelf heb bestudeerd uit interesse.
Het vel van de beer kunnen verkopen vraagt moeite tenzij deze dood voor je neervalt. Die kans is echter klein dus moeten we zelf moeite doen.





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures