Lineair optimaliseren/programmeren

Moderators: dirkwb, Xilvo

Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
Gebruikersavatar
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.
Be careful whose advice you buy, but be patient with those who supply it.

Gebruikersavatar
Pluimdrager
Berichten: 4.168

Re: Lineair optimaliseren/programmeren

Ik ben enigszins bekend met LP maar je zult wellicht tot vrijdag moeten wachten op antwoord.
Nu, die oplossing intypen kost bakken tijd- en typwerk.
Kun je de tekst trouwens niet scannen i.p.v intypen?

En waarom spreek je trouwens over de oplossing in plaats van het vraagstuk?
Hydrogen economy is a Hype.

Gebruikersavatar
Berichten: 824

Re: Lineair optimaliseren/programmeren

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 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.

Ik zal het straks even intypen!

Gegroet
Be careful whose advice you buy, but be patient with those who supply it.

Gebruikersavatar
Berichten: 824

Re: Lineair optimaliseren/programmeren

In de bijlage zit de opdracht.

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 werken

De 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.

Gebruikersavatar
Pluimdrager
Berichten: 4.168

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.
Hydrogen economy is a Hype.

Gebruikersavatar
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 ?
Be careful whose advice you buy, but be patient with those who supply it.

Gebruikersavatar
Pluimdrager
Berichten: 4.168

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.
Hydrogen economy is a Hype.

Gebruikersavatar
Berichten: 824

Re: Lineair optimaliseren/programmeren

Ah, ja.

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.

Gebruikersavatar
Pluimdrager
Berichten: 4.168

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
Hydrogen economy is a Hype.

Gebruikersavatar
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
Be careful whose advice you buy, but be patient with those who supply it.

Gebruikersavatar
Pluimdrager
Berichten: 4.168

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 =< ?
Hydrogen economy is a Hype.

Gebruikersavatar
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.
Be careful whose advice you buy, but be patient with those who supply it.

Gebruikersavatar
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...
Be careful whose advice you buy, but be patient with those who supply it.

Gebruikersavatar
Pluimdrager
Berichten: 4.168

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.
Hydrogen economy is a Hype.

Gebruikersavatar
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!
Be careful whose advice you buy, but be patient with those who supply it.

Reageer