Groentenfamilies in operationeel onderzoek: hoe?!

[Rpraa]

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

TvOO-case3eocfarm

(19.58 KiB) 218 keer gedownload

[/u][/i][/size][/color]



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.

[Rpraa]

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

[Xenion]

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

[Rpraa]

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!

[Xenion]

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.

\(\sum_{j \in patches}\sum_{i \in vegetables}A_{ij}\cdot S_{ij}\)

De eerste constaint is dat

\(\sum A_{ij} \leq Opp_{patch j}\)

De 2de constraint zal iets worden van

\(AantalFamilies(patch) \leq 1\)

[/color]

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.

\(\sum_{j \in patches}A_{ij} = gewenste waarde van groente_i\)

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

[Xenion]

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

\(\sum Fi \leq 1\)

(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

\(\sum A_i \leq Opp_{patch}\)

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.

[Rpraa]

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.

[Xenion]

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