Lineair optimaliseren/programmeren
Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
- Berichten: 824
Lineair optimaliseren/programmeren
Hallo,
voor ik hier een opgave + mijn oplossing ga neerzetten, zou ik eerst even willen weten of er hier iemand is die ervaring heeft met het opstellen van lineaire optimaliseringsproblemen. Het zit namelijk zo, ik heb hier een opgave (een probleem in tekstvorm) en ik moet die in de een lineair optimaliseringsmodel gieten zodat het opgelost kan worden (oplossen zelf gebeurt softwarematig). Nu, die oplossing intypen kost bakken tijd- en typwerk. Dus ik zou eerst even willen checken of er uberhaupt iemand is die me hiermee kan helpen.
Verder weet ik ook niet of dit in het juiste (sub)forum staat, maar ik dacht hier de meeste mensen te bereiken die mij mogelijk zouden kunnen helpen.
Alvast bedankt!
Stijn
PS: lineair programmeren en lineair optimaliseren zijn twee synoniemen.
voor ik hier een opgave + mijn oplossing ga neerzetten, zou ik eerst even willen weten of er hier iemand is die ervaring heeft met het opstellen van lineaire optimaliseringsproblemen. Het zit namelijk zo, ik heb hier een opgave (een probleem in tekstvorm) en ik moet die in de een lineair optimaliseringsmodel gieten zodat het opgelost kan worden (oplossen zelf gebeurt softwarematig). Nu, die oplossing intypen kost bakken tijd- en typwerk. Dus ik zou eerst even willen checken of er uberhaupt iemand is die me hiermee kan helpen.
Verder weet ik ook niet of dit in het juiste (sub)forum staat, maar ik dacht hier de meeste mensen te bereiken die mij mogelijk zouden kunnen helpen.
Alvast bedankt!
Stijn
PS: lineair programmeren en lineair optimaliseren zijn twee synoniemen.
Be careful whose advice you buy, but be patient with those who supply it.
- Pluimdrager
- Berichten: 4.167
Re: Lineair optimaliseren/programmeren
Ik ben enigszins bekend met LP maar je zult wellicht tot vrijdag moeten wachten op antwoord.
En waarom spreek je trouwens over de oplossing in plaats van het vraagstuk?
Kun je de tekst trouwens niet scannen i.p.v intypen?Nu, die oplossing intypen kost bakken tijd- en typwerk.
En waarom spreek je trouwens over de oplossing in plaats van het vraagstuk?
Hydrogen economy is a Hype.
- Berichten: 824
Re: Lineair optimaliseren/programmeren
Ik spreek over de oplossing, omdat ik het naar mijn mening al heb 'opgelost', maar ik zou graag iemand hebben die mijn oplossing ook eens bekijkt, gewoon een second opinion zeg maar.Fred F. schreef:Ik ben enigszins bekend met LP maar je zult wellicht tot vrijdag moeten wachten op antwoord.
Kun je de tekst trouwens niet scannen i.p.v intypen?
En waarom spreek je trouwens over de oplossing in plaats van het vraagstuk?
Ik zal het straks even intypen!
Gegroet
Be careful whose advice you buy, but be patient with those who supply it.
- Berichten: 824
Re: Lineair optimaliseren/programmeren
In de bijlage zit de opdracht.
Variabelen:
De te minimaliseren functie:
Onder de randvoorwaarden:
.
.
zelfde redenering voor de andere dagen
.
.
Ik hoop dat het een beetje duidelijk is!
Variabelen:
\(x_{i,v}\)
= aantal voltijdse werknemers die beginnen te werken op dag i\(x_{i,d}\)
= aantal deeltijdse werknemers die beginnen te werken op dag i\(x_{i,dv}\)
= aantal werknemers die normaalgezien beginnen op dag i, maar opgeroepen worden om een dag vroeger te komen werken.\(x_{i,dl}\)
= aantal werknemers die normaalgezien beginnen op dag i, maar opgeroepen worden om een dag langer te werkenDe te minimaliseren functie:
\(800(x_{1,v} + ... + x_{7,v}) + 280(x_{1,d} + ... + x_{7,d}) + 144((x_{1,dv} + x_{1,dl})+ ... + (x_{7,dv} + x_{7,dl}))\)
Uitleg: 800 = 5(5 dagen) * 8(8u per dag) * 20(20euro per uur), zelfde redenering voor de andere coëfficiënten.Onder de randvoorwaarden:
\(8(x_{4,v}+...+x_{7,v} + x_{1,v} + x_{2,dv} + x_{3,dl}) + 4(x_{4,d} + ... +x_{7,v} + x_{1,d}) \geq 120\)
[MAANDAG]\(8(x_{5,v}+...+x_{7,v} + x_{1,v} + x_{2,v} + x_{3,dv} + x_{4,dl}) + 4(x_{5,d} + ... +x_{7,v} + x_{1,d} + x_{2,d}) \geq 116\)
[DINSDAG].
.
zelfde redenering voor de andere dagen
.
.
\(x_{i,dv}+x_{i,dl} \leq x_{i,v}\)
[EXTRA WERKUREN]\(x_{1,d} + ... + x_{7,d} \leq 0.3(x_{1,v} + ... + x_{7,d} + (x_{1,dv} + x_{1,dl}) + ... + (x_{7,dv} + x_{7,dl}))\)
[30% DEELTIJDS]Ik hoop dat het een beetje duidelijk is!
Be careful whose advice you buy, but be patient with those who supply it.
- Pluimdrager
- Berichten: 4.167
Re: Lineair optimaliseren/programmeren
Ik vind het een vreemd vraagstuk maar ik begrijp hoe jij de opgave interpreteert. Inderdaad zullen in de praktijk mensen gewoonlijk over het weekend heen werken en dus hun 5 (of 6) dagen in twee verschillende kalenderweken maken. Maar dan klopt een optimale LP-oplossing eigenlijk alleen als het te werken uren op maandag altijd in iedere week die 120 is (en soortgelijk verhaal voor iedere andere weekdag). Ook het feit dat mensen die gedwongen worden om 6 dagen te werken die 6e dag minder verdienen dan de andere 5 is heel vreemd. Op die manier zal een LP altijd proberen zoveel mogelijk voltijdwerkers 6 dagen i.p.v. 5 te laten werken. Ook zal het LP altijd het aantal relatief goedkope deeltijduren maximaliseren (tot die 30%). Blijkbaar heeft dit bedrijf geen vakbondsleden in dienst. Maar goed het is maar een vraagstuk....
Ik zie een typefout in de randvoorwaarde voor [MAANDAG].
In de term 4(...... x7,v .....) moet x7,d staan (en ook in vergelijkingen voor andere dagen).
Echt fout is je laatste vergelijking voor [30% DEELTIJDS].
Het dient hier te gaan om het aantal wekelijkse werkuren, niet om het aantal werkende mensen.
De regel erboven [EXTRA WERKUREN] is in feite [AANTAL WERKERS i DIE DAG EXTRA WERKT] maar dat komt in dit geval op hetzelfde neer. In feite zouden deze 7 vergelijkingen niet nodig zijn als je het aantal werkers dat 6 dagen werkt als een apart aantal zou definieren en niet includen in xi,v zoals je nu doet. De andere vergelijkingen zouden dan natuurlijk wel anders geschreven moeten worden maar in mijn ogen zou dat toch netter zijn omdat je totaal aantal vergelijkingen flink afneemt.
Bijvoorbeeld: op dag i beginnen xi,v5 voltijdmensen die 5 dagen (40 uur) zullen werken en xi,v6 voltijdmensen die 6 dagen (48 uur) zullen werken.
Ik zie een typefout in de randvoorwaarde voor [MAANDAG].
In de term 4(...... x7,v .....) moet x7,d staan (en ook in vergelijkingen voor andere dagen).
Echt fout is je laatste vergelijking voor [30% DEELTIJDS].
Het dient hier te gaan om het aantal wekelijkse werkuren, niet om het aantal werkende mensen.
De regel erboven [EXTRA WERKUREN] is in feite [AANTAL WERKERS i DIE DAG EXTRA WERKT] maar dat komt in dit geval op hetzelfde neer. In feite zouden deze 7 vergelijkingen niet nodig zijn als je het aantal werkers dat 6 dagen werkt als een apart aantal zou definieren en niet includen in xi,v zoals je nu doet. De andere vergelijkingen zouden dan natuurlijk wel anders geschreven moeten worden maar in mijn ogen zou dat toch netter zijn omdat je totaal aantal vergelijkingen flink afneemt.
Bijvoorbeeld: op dag i beginnen xi,v5 voltijdmensen die 5 dagen (40 uur) zullen werken en xi,v6 voltijdmensen die 6 dagen (48 uur) zullen werken.
Hydrogen economy is a Hype.
- Berichten: 824
Re: Lineair optimaliseren/programmeren
Eerst en vooral: bedankt voor je snelle reactie.
Die 30% vergelijking was inderdaad helemaal fout, bedankt.
Ivm met die extra werkuren:
Ik zie niet in hoe xi,v6 het aantal vergelijking zou beperken. Je moet dan toch nog steeds ingeven dat xi,v6 <= xi,v ?
Die 30% vergelijking was inderdaad helemaal fout, bedankt.
Ivm met die extra werkuren:
Ik zie niet in hoe xi,v6 het aantal vergelijking zou beperken. Je moet dan toch nog steeds ingeven dat xi,v6 <= xi,v ?
Be careful whose advice you buy, but be patient with those who supply it.
- Pluimdrager
- Berichten: 4.167
Re: Lineair optimaliseren/programmeren
Nee, want je gebruikt dan xi,v helemaal niet meer.
Je hebt dan voor voltijdwerkers alleen xi,v5 en xi,v6 , en niet xi,v , xi,dv en xi,dl.
Dat scheelt dus 7 vergelijkingen en 7 variabelen.
(in feite is xi,v5 plus xi,v6 gelijk aan jouw xi,v maar dat doet er niet toe en hoef je niet te definiëren)
Bovendien maakt het voor het LP niets uit of mensen die op dag i beginnen en 6 dagen werken, volgens jouw systeem nou eigenlijk xi+1,dv dan wel xi-1,dl heten. Het LP heeft geen voorkeur want het heeft geen invloed op de totale loonkosten per week. Het LP kan niet beslissen en geeft één van de mogelijke oplossingen hiervoor. Het gaat immers om de weekkosten, niet de dagkosten dus het doet er niet toe op precies welke dag mensen die extra 6e dag tegen een ander loon werken. Het gaat er alleen om hoeveel voltijdmensen 5 en hoeveel 6 dagen werken in één week, en wanneer ze beginnen en stoppen.
Je hebt dan voor voltijdwerkers alleen xi,v5 en xi,v6 , en niet xi,v , xi,dv en xi,dl.
Dat scheelt dus 7 vergelijkingen en 7 variabelen.
(in feite is xi,v5 plus xi,v6 gelijk aan jouw xi,v maar dat doet er niet toe en hoef je niet te definiëren)
Bovendien maakt het voor het LP niets uit of mensen die op dag i beginnen en 6 dagen werken, volgens jouw systeem nou eigenlijk xi+1,dv dan wel xi-1,dl heten. Het LP heeft geen voorkeur want het heeft geen invloed op de totale loonkosten per week. Het LP kan niet beslissen en geeft één van de mogelijke oplossingen hiervoor. Het gaat immers om de weekkosten, niet de dagkosten dus het doet er niet toe op precies welke dag mensen die extra 6e dag tegen een ander loon werken. Het gaat er alleen om hoeveel voltijdmensen 5 en hoeveel 6 dagen werken in één week, en wanneer ze beginnen en stoppen.
Hydrogen economy is a Hype.
- Berichten: 824
Re: Lineair optimaliseren/programmeren
Ah, ja.
Dus:
Minimaliseer:
.
.
Zelfde redenering andere dagen
.
.
Dus:
Minimaliseer:
\(800(x_{1,5v}+...+x_{7,5v}) + 280(x_{1,5d}+...+x_{7,5d}) + (800+144)(x_{1,6v}+...+x_{7,6v})\)
Zodanig dat:\(8(x_{4,5v}+...+x_{7,5v}+x_{3,6v}) + 4(x_{4,5d}+...+x_{7,5d}+x_{1,5d}) \geq 120\)
[MAANDAG].
.
Zelfde redenering andere dagen
.
.
\(4(x_{1,5d}+...+x_{7,5d}) \leq 0.3\cdot 8(x_{1,5v}+...+x_{7,5v}+x_{1,6v}+...+x_{7,6v})\)
Dit zou volgens mij het volledige model moeten zijn dan.Be careful whose advice you buy, but be patient with those who supply it.
- Pluimdrager
- Berichten: 4.167
Re: Lineair optimaliseren/programmeren
Nog niet helemaal.
In de [MAANDAG] vergelijking ontbreekt in 8(........) de term x1,5v en bijna alle termen voor x....,6v
en in [30% DEELTIJDS] ontbreken aan de rechterzijde na die 0,3 de termen voor de deeltijduren. Het is immers 0,3*Totaal aantal uren, niet 0,3*voltijduren.
Of je kunt aan de linkerzijde vermenigvuldigen met 0,7 want dat komt op hetzelfde neer en is toch nodig om het in het LP in te voeren (neem ik althans aan):
deeltijd =< 0,3 * (voltijd + deeltijd)
0,7 * deeltijd =< 0,3 * voltijd
0,7 * deeltijd - 0,3 * voltijd =< 0
In de [MAANDAG] vergelijking ontbreekt in 8(........) de term x1,5v en bijna alle termen voor x....,6v
en in [30% DEELTIJDS] ontbreken aan de rechterzijde na die 0,3 de termen voor de deeltijduren. Het is immers 0,3*Totaal aantal uren, niet 0,3*voltijduren.
Of je kunt aan de linkerzijde vermenigvuldigen met 0,7 want dat komt op hetzelfde neer en is toch nodig om het in het LP in te voeren (neem ik althans aan):
deeltijd =< 0,3 * (voltijd + deeltijd)
0,7 * deeltijd =< 0,3 * voltijd
0,7 * deeltijd - 0,3 * voltijd =< 0
Hydrogen economy is a Hype.
- Berichten: 824
Re: Lineair optimaliseren/programmeren
Oké, bedankt!
Ik heb het probleem ingegeven in een optimalisatie programma en kreeg dit als oplossing:
VARIABLE VALUE REDUCED COST
X15V 0.000000 1.403509
X25V 0.000000 1.403509
X35V 0.000000 1.403509
X45V 0.000000 1.403509
X55V 0.000000 1.403509
X65V 0.000000 1.403509
X75V 0.000000 1.403509
X15D 0.000000 0.000000
X25D 1.236842 0.000000
X35D 0.000000 0.000000
X45D 7.184210 0.000000
X55D 0.000000 0.000000
X65D 2.434211 0.000000
X75D 0.000000 0.000000
X16V 3.723684 0.000000
X26V 2.473684 0.000000
X36V 0.000000 0.000000
X46V 1.250000 0.000000
X56V 4.875000 0.000000
X66V 0.000000 0.000000
X76V 0.342105 0.000000
Het valt dus op dat er geen enkele voltijdse werker is die niet een extra dag moet werken, wat logisch is gezien die extra dag goedkoper is.
In de bijlage zit heel het model, zou je dat ook nog héél even kunnen checken? Zou moeten kloppen denk ik
Ik heb het probleem ingegeven in een optimalisatie programma en kreeg dit als oplossing:
VARIABLE VALUE REDUCED COST
X15V 0.000000 1.403509
X25V 0.000000 1.403509
X35V 0.000000 1.403509
X45V 0.000000 1.403509
X55V 0.000000 1.403509
X65V 0.000000 1.403509
X75V 0.000000 1.403509
X15D 0.000000 0.000000
X25D 1.236842 0.000000
X35D 0.000000 0.000000
X45D 7.184210 0.000000
X55D 0.000000 0.000000
X65D 2.434211 0.000000
X75D 0.000000 0.000000
X16V 3.723684 0.000000
X26V 2.473684 0.000000
X36V 0.000000 0.000000
X46V 1.250000 0.000000
X56V 4.875000 0.000000
X66V 0.000000 0.000000
X76V 0.342105 0.000000
Het valt dus op dat er geen enkele voltijdse werker is die niet een extra dag moet werken, wat logisch is gezien die extra dag goedkoper is.
In de bijlage zit heel het model, zou je dat ook nog héél even kunnen checken? Zou moeten kloppen denk ik
Be careful whose advice you buy, but be patient with those who supply it.
- Pluimdrager
- Berichten: 4.167
Re: Lineair optimaliseren/programmeren
Het aantal werkers zal altijd een geheel aantal moeten zijn.
Je hebt nu gebroken aantallen werkers (oftewel geheel aantal werkers maar sommigen betaald voor minder dan 8 uur per dag). Op die manier is het natuurlijk eenvoudig om exact het aantal uren te maken op iedere dag en de reduced cost dan ook precies nul want geen enkele werker hoeft betaald te worden voor uren aanwezigheid zonder dat er nog iets te doen is omdat alle werk al gedaan is voor de 8 uur om zijn.
Je alle variabelen dus specificeren als Integers, of speciale IP software gebruiken.
EDIT:
waarom gebruik je in de LINDO input overal > in plaats van >=
en < in plaats van =< ?
Je hebt nu gebroken aantallen werkers (oftewel geheel aantal werkers maar sommigen betaald voor minder dan 8 uur per dag). Op die manier is het natuurlijk eenvoudig om exact het aantal uren te maken op iedere dag en de reduced cost dan ook precies nul want geen enkele werker hoeft betaald te worden voor uren aanwezigheid zonder dat er nog iets te doen is omdat alle werk al gedaan is voor de 8 uur om zijn.
Je alle variabelen dus specificeren als Integers, of speciale IP software gebruiken.
EDIT:
waarom gebruik je in de LINDO input overal > in plaats van >=
en < in plaats van =< ?
Hydrogen economy is a Hype.
- Berichten: 824
Re: Lineair optimaliseren/programmeren
Ja, dat weet ik. Maar dit is slechts een inleidende cursus, dus niet gehele getallen mogen gewoon afgerond worden.
Verder, in lindo is > hetzelfde als >= , en < hetzelfde als <=.
Ik wil je in ieder geval hartelijk bedanken voor al je hulp!
Mvg
Stijn
EDIT:
of kan ik LINDO instellen dat hij geheeltallige oplossingen zoekt? Ben niet zo vertrouwd met het programma. Kan het in ieder geval niet meteen terugvinden, helaas.
Verder, in lindo is > hetzelfde als >= , en < hetzelfde als <=.
Ik wil je in ieder geval hartelijk bedanken voor al je hulp!
Mvg
Stijn
EDIT:
of kan ik LINDO instellen dat hij geheeltallige oplossingen zoekt? Ben niet zo vertrouwd met het programma. Kan het in ieder geval niet meteen terugvinden, helaas.
Be careful whose advice you buy, but be patient with those who supply it.
- Berichten: 824
Re: Lineair optimaliseren/programmeren
Dan nog de duaal...
Mijn oplossing zit in de bijlage. Maar wanneer ik dit duale probleem oplos in LINDO, dan verkrijg ik niet dezelfde doelfunctiewaarde als in het primale probleem. Er zit dus een fout in mijn duaal, maar waar?? Volgens mij is die helemaal in orde...
Mijn oplossing zit in de bijlage. Maar wanneer ik dit duale probleem oplos in LINDO, dan verkrijg ik niet dezelfde doelfunctiewaarde als in het primale probleem. Er zit dus een fout in mijn duaal, maar waar?? Volgens mij is die helemaal in orde...
Be careful whose advice you buy, but be patient with those who supply it.
- Pluimdrager
- Berichten: 4.167
Re: Lineair optimaliseren/programmeren
Ik denk dat in Lindo het statement GIN gebruikt wordt voor het definieren van integers die 0, 1, 2, 3, ......... kunnen aannemen.
Dat moet na het END statement. Althans zo was het in de oude DOS versie die ik vroeger wel eens gebruikte.
Om Lindo te vertellen dat de eerste n variabelen integers zijn: GIN n
Op die duaal kom ik wellicht morgen terug want ik hou er voor vandaag mee op.
Dat moet na het END statement. Althans zo was het in de oude DOS versie die ik vroeger wel eens gebruikte.
Om Lindo te vertellen dat de eerste n variabelen integers zijn: GIN n
Op die duaal kom ik wellicht morgen terug want ik hou er voor vandaag mee op.
Hydrogen economy is a Hype.
- Berichten: 824
Re: Lineair optimaliseren/programmeren
Ik heb net nog eens gekeken, maar ik vind de fout echt niet. Ik hoop dat jij me kan helpen!
Alvast bedankt!
Alvast bedankt!
Be careful whose advice you buy, but be patient with those who supply it.