Springen naar inhoud

Groentenfamilies in operationeel onderzoek: hoe?!


  • Log in om te kunnen reageren

#1

Rpraa

    Rpraa


  • 0 - 25 berichten
  • 6 berichten
  • Gebruiker

Geplaatst op 22 oktober 2012 - 08:16

Dag iedereen.
Even voorstellen. Ik ben een student HIR (1e master). Dit jaar hebben wij een plichtvak toepassingen van operationeel onderzoek. Daarvoor moeten we een case uitwerken. Optimalisatie moet gebeuren met een programma als Cplex, Lingo... Daarnaast moet ook een algoritme worden ontwikkeld om tot een oplossing te komen.

Korte opgave van het probleem:

The resulting problem is the following. You are given a number of patches; each patch has a given size. Further, you have a set of vegetables, for each vegetable you know the family it belongs to and the amount you want to grow. For each combination of patch and vegetable you are given a score, representing the suitability of the patch for the vegetable. This score depends on what has grown on the patch the previous year, the amount of sunshine, etc. The goal is to assign the vegetables to the patches, such that only vegetables of the same family are together on a patch and such that the total suitability is maximized.
Volledige opgave --> zie bijlage Bijlage  TvOO-case3eocfarm.docx   19,58K   48 maal gedownload

Nu mijn vraag; er moet dus afgedwongen worden dat wanneer een groente van een familie wordt geteeld op 1 van de patches, er geen groente van een andere familie op deze patch kan worden geteeld.

We wijzen dus een groente toe aan een patch. Daarenboven weten we de familie waartoe deze groente behoort. Nu moeten we afdwingen dat enkel deze familie aan de geselecteerde patch kan worden toegewezen.

Hoe zouden jullie dit in variabelen gieten en een logische beperking opstellen voor dit 'familieprobleem'?

In ieder geval, dank bij voorbaat.

Veranderd door Rpraa, 22 oktober 2012 - 08:27


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

#2

Rpraa

    Rpraa


  • 0 - 25 berichten
  • 6 berichten
  • Gebruiker

Geplaatst op 23 oktober 2012 - 16:23

Programmeren gebeurt in Lingo, Cplex of dergerlijk optimalisatieprogramma...

#3

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 28 oktober 2012 - 14:01

We wijzen dus een groente toe aan een patch. Daarenboven weten we de familie waartoe deze groente behoort. Nu moeten we afdwingen dat enkel deze familie aan de geselecteerde patch kan worden toegewezen.

Als ik naar je volledige opgave kijk, dan valt het mij op dat de 'scores' groente-patch, dezelfde zijn voor groenten van dezelfde familie. Ook de voorbeeld oplossing met score 52 kijkt niet naar de individuele groenten, maar naar de families.

Ik zou dus beginnen met het probleem te reduceren naar het toewijzen van patches aan families.

Wat wil je maximaliseren? de totale score
Wat zijn de constraints? elke familie groenten heeft een minimale oppervlakte nodig

#4

Rpraa

    Rpraa


  • 0 - 25 berichten
  • 6 berichten
  • Gebruiker

Geplaatst op 28 oktober 2012 - 14:16

Xenion, eerst en vooral bedankt voor je antwoord.

Het klopt inderdaad dat in de opgave de 2 verschillende groenten van een familie dezelfde score hebben indien ze aan een patch worden toegewezen. Echter, dit probleem moet worden toegepast op een grotere case met 180 groenten, 24 families en 220 patches (zie bijlage voor de grote dataset). Daar is het echter niet het geval dat deze 'familiescores' dezelfde zijn, dus de case kan helaas niet gereduceerd worden.

Ook prof en assistent vonden de opgave blijkbaar onduidelijk en maakten een nieuwe mededeling:

Er is een fout geslopen in het voorbeeld in de opgave bij het berekenen van de doelfunctiewaarde. Het is niet voldoende om de patches aan families toe te wijzen, je moet ook specifieren welke hoeveelheid van welke groente je aan elke patch toewijst. Voor de oplossing in het voorbeeld kan dat dan als volgt: 1 2 3 4 5 6 7 8 9 10 white cabbage 120 carrots 150 200 broccoli 210 green salad 110 200 onion 200 200 spinach 150 140
De doelfunctiewaarde is 5070 (de 52 in de opgave mag je vergeten). Let op, dit hoeft niet de optimale oplossing te zijn voor het voorbeeld, het is een toelaatbare oplossing.


Na groepsbijeenkomst zijn we er nog altijd niet uitgeraakt hoe we zouden afdwingen dat op 1 patch slechts 1 enkele groentenfamilie kan worden geteeld.

Nogmaals bedankt voor je antwoord en hopelijk ben je iets met de verduidelijking van de case om ons op de goede weg te helpen!

Bijgevoegde Bestanden

Veranderd door Rpraa, 28 oktober 2012 - 14:17


#5

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 28 oktober 2012 - 15:06

Goh, ik heb zelf nooit zo'n probleem opgelost, dus ik weet niet wat er allemaal mogelijk is, maar zou het evt als volgt kunnen?

Aan elke patch wil je zeggen hoeveel van elke groente erop komt.
Je kan dan een rij opstellen: A1j, A2j, ..., ANj. Waarbij elke Aij een aantal m² van groente i op patch j voorstelt.
Als een groente i niet voorkomt op die patch j, dan is de bijhorende Aij = 0.

Je kostfunctie wordt dan de som over alle patches en groenten waar je die Aij met de bijhorende score vermenigvuldigt.
LaTeX

De eerste constaint is dat LaTeX
De 2de constraint zal iets worden van LaTeX
Waarbij AantalFamilies dan een zelf geschreven functie is die op basis van de niet nulle Aij kan tellen hoeveel verschillende families er op een patch j zijn.

De andere constraints zijn dan dat je genoeg van elke groente hebt.
LaTeX

Kan je het op deze manier uitdrukken in zo'n optimalisatie programma?

#6

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 28 oktober 2012 - 15:40

Of misschien beter:

Ik ga even terug naar de kleine opgave.

Wijs toch aan elke patch een familie toe. Dit doe je door membership variabelen F1,F2,F3 (cabbage, carrot, leaves) in te vullen met de beperking LaTeX (een Fi kan gelijk zijn aan 1, de andere twee zijn 0, of alledrie gelijk aan 0)

Voor 1 patch wil je zeggen hoeveel m² er voor elke groente toegewezen wordt. Dat komt neer op het kiezen van A1,A2,...,A6. (white cabbage, carrots, ... spinach)

De beperking dat de som van A1 over alle patches gelijk is aan 120m² (white cabbage), etc.
En de beperking dat LaTeX

Je wil de opbrengst over alle patches maximaliseren, dus de som over alle patches van:
A1*S1 + ... + A6*S6 met Si de score voor groente i op de patch.

Je kan hier die familievariabelen insteken omdat je weet welke groente tot welke familie hoort.
In dit voorbeeld:
F1*A1*S1 + F2*A2*S2 + F1*A3*S3 + F3*A4*S4 + F2*A5*S5 + F3*A6*S6

De solver zal normaal gezien geen Ai gaan toewijzen als de familievariabele van die groente op een patch gelijk is aan 0, omdat dat de opbrengst niet groter maakt.

#7

Rpraa

    Rpraa


  • 0 - 25 berichten
  • 6 berichten
  • Gebruiker

Geplaatst op 30 oktober 2012 - 12:25

Merci voor het antwoord Xenion. We hebben vamiddag groepsbijeenkomst en zal het daar even voorleggen. Ik houd je op de hoogte of we jouw werkwijze op het grote probleem kunnen implementeren.

Bedankt voor de moeite.

#8

Xenion

    Xenion


  • >1k berichten
  • 2606 berichten
  • Moderator

Geplaatst op 30 oktober 2012 - 23:52

Als je een andere oplossing vindt, mag je die hier ook steeds posten. Ik ben wel benieuwd hoe je het uiteindelijk oplost krijgt. Zoals eerder gezegd heb ik zelf geen operationeel onderzoek gehad. Ik denk zelf eerder aan AI technieken :)





0 gebruiker(s) lezen dit onderwerp

0 leden, 0 bezoekers, 0 anonieme gebruikers

Ook adverteren op onze website? Lees hier meer!

Gesponsorde vacatures

Vacatures