Programmeren met gemengde gehele getallen: een eenvoudige zelfstudie (2023)

In een eerder artikel (Lineair programmeren in Python: een eenvoudige zelfstudie) Ik behandelde lineaire programmering waarbij we een probleem met de fabrieksproductie oplosten door een reeks lineaire beperkingen te definiëren en de variabelen waren continu. Maar wat gebeurt er als de variabelen niet continu zijn? Wat moeten we doen als we beslissingsvariabelen willen introduceren? Dit is waar Mixed Integer Programming om de hoek komt kijken.

We zullen gebruikenPulpverder in deze tutorial als je er een installatiehandleiding voor wilt, kun je het vorige artikel bekijken voor het instellen en definiëren van de basisfunctionaliteit. Laten we eerst nog eens naar de probleemstelling kijken, een beetje aangepast om te zien waar Mixed Integer Programming nuttig kan zijn.

Stel je voor dat je werkt voor een bedrijf dat computers bouwt. Een computer is een vrij complex product en er zijn verschillende fabrieken die ze assembleren waarvoor het bedrijf een bepaald bedrag per eenheid betaalt. De kosten van dit computermodel op de markt zijn vastgesteld op 500 $, verschillende fabrieken assembleren de computers met verschillende snelheden en kosten. Fabriekf0produceert 2000 per dag tegen 450 $ per eenheid, fabriekf11500 per dag voor 420 $ per eenheid enf21000 per dag voor 400 $ per eenheid. We hebben 1 maand de tijd om 80.000 eenheden te assembleren onder de voorwaarde dat geen enkele fabriek meer dan het dubbele aantal eenheden mag produceren dan welke andere fabriek dan ook.Slechts twee fabrieken kunnen tegelijkertijd werken.De vraag is,wat is de optimale productieverdeling tussen de fabriekenzodanig dat wijmaximaliseren de winstverkregen door de computers onder die beperkingen te verkopen?

Let op de extra beperking "Slechts twee fabrieken kunnen tegelijkertijd werken”. Dit kan niet worden opgelost met klassieke lineaire programmering, omdat we moeten beslissen welke 2 fabrieken op een bepaalde dag werken. Er zijn echter meerdere manieren om dit probleem op te lossen, ik heb gekozen voor een misschien intuïtieve benadering om het beter te begrijpen.

Dus we weten dat we 30 dagen hebben om al die eenheden samen te stellen, hoe kunnen we onze beperkingen definiëren? Nou, het is vrij eenvoudig. We kunnen 3 binaire variabelen voor elke dag definiëren (1 variabele per fabriek) en de beperking instellen dat ze niet meer dan 2 mogen optellen. Binaire variabelen zijn in feite gehele variabelen die beperkt zijn tot tussen 0 en 1, inclusief. Uiteindelijk ziet ons mixed integer-programma er zo simpel uit als dit:

Als je je nu afvraagt ​​waarom het lijkt op een lineair programma, dan heb je het punt begrepen, het enige verschil is dat we integer-variabelen introduceren. We kunnen de probleemdefinitie bekijken om het een beetje beter te begrijpen. Kortom, we kunnen zien dat het resulterende doel logisch is gecombineerd met al die variabelen die we in de bovenstaande for-lus hebben samengevat. En ook alle integer-beperkingen.

computermontage:
MAXIMALISEREN
-450*f0eachDay_0 + -450*f0eachDay_1 + -450*f0eachDay_10 + -450*f0eachDay_11 + -450*f0eachDay_12 + -450*f0eachDay_13 + -450*f0eachDay_14 + -450*f0eachDay_15 + -450*f0eachDay_1 6 + -450*f0eachDay_17 + -450*f0eachDay_18 + -450*f0eachDay_19 + -450*f0eachDay_2 + -450*f0eachDay_20 + -450*f0eachDay_21 + -450*f0eachDay_22 + -450*f0eachDay_23 + -450*f0eachDay_3 + -450*f0eachDay_4 + -450*f0eachDay_5 + -450*f0eachDay_6 + -450*f0eachDay_7 + -450*f0eachDay_8 + -450*f0eachDay_9 + -420*f1eachDay_0 + -420*f1eachDay_1 + -420*f1eachDay_10 + -420*f1eachDay_11 + -420*f1eachDay_12 + -4 20*f1eachDag_13 + -420*f1eachDag_14 + -420*f1eachDag_15 + -420*f1eachDag_16 + -420*f1eachDag_17 + -420*f1eachDag_18 + -420*f1eachDag_19 + -420*f1eachDag_2 + -420*f1eachDag_20 + -420*f1eachDag_ 21 + -420*f1eachDag_22 + -420*f1eachDag_23 + -420*f1eachDag_3 + -420*f1eachDag_4 + -420*f1eachDag_5 + -420*f1eachDag_6 + -420*f1eachDag_7 + -420*f1eachDag_8 + -420*f1eachDag_9 + -400*f2eachDag_0 + -400 *f2eachDag_1 + -400*f2eachDay_10 + -400*f2eachDay_11 + -400*f2eachDay_12 + -400*f2eachDay_13 + -400*f2eachDay_14 + -400*f2eachDay_15 + -400*f2eachDay_16 + -400*f2eachDay_17 + -400*f2eachDay _18 + -400*f2eachDay_19 + -400*f2eachDag_2 + -400*f2eachDag_20 + -400*f2eachDag_21 + -400*f2eachDag_22 + -400*f2eachDag_23 + -400*f2eachDag_3 + -400*f2eachDag_4 + -400*f2eachDag_5 + -400*f2eachDag_6 + - 400*f2eachDag_7 + -400*f2elkeDag_8 + -400*f2elkeDag_9 + 0
ONDERWORPEN AAN
_C1: f0eachDay_0 + f1eachDay_0 + f2eachDay_0 <= 2
_C2: f0eachDag_1 + f1eachDag_1 + f2eachDag_1 <= 2
_C3: f0eachDag_2 + f1eachDag_2 + f2eachDag_2 <= 2
_C4: f0eachDag_3 + f1eachDag_3 + f2eachDag_3 <= 2
_C5: f0eachDag_4 + f1eachDag_4 + f2eachDag_4 <= 2
_C6: f0eachDag_5 + f1eachDag_5 + f2eachDag_5 <= 2
_C7: f0eachDag_6 + f1eachDag_6 + f2eachDag_6 <= 2
_C8: f0eachDag_7 + f1eachDag_7 + f2eachDag_7 <= 2
_C9: f0eachDag_8 + f1eachDag_8 + f2eachDag_8 <= 2
_C10: f0eachDag_9 + f1eachDag_9 + f2eachDag_9 <= 2
_C11: f0eachDay_10 + f1eachDay_10 + f2eachDay_10 <= 2
_C12: f0eachDag_11 + f1eachDag_11 + f2eachDag_11 <= 2
_C13: f0eachDag_12 + f1eachDag_12 + f2eachDag_12 <= 2
_C14: f0eachDag_13 + f1eachDag_13 + f2eachDag_13 <= 2
_C15: f0eachDay_14 + f1eachDay_14 + f2eachDay_14 <= ​​​​2
_C16: f0eachDag_15 + f1eachDag_15 + f2eachDag_15 <= 2
_C17: f0eachDag_16 + f1eachDag_16 + f2eachDag_16 <= 2
_C18: f0eachDag_17 + f1eachDag_17 + f2eachDag_17 <= 2
_C19: f0eachDag_18 + f1eachDag_18 + f2eachDag_18 <= 2
_C20: f0eachDag_19 + f1eachDag_19 + f2eachDag_19 <= 2
_C21: f0elkeDag_20 + f1eachDag_20 + f2elkeDag_20 <= 2
_C22: f0eachDag_21 + f1eachDag_21 + f2eachDag_21 <= 2
_C23: f0eachDag_22 + f1eachDag_22 + f2eachDag_22 <= 2
_C24: f0eachDag_23 + f1eachDag_23 + f2eachDag_23 <= 2
_C25: 2000 f0eachDay_0 + 2000 f0eachDay_1 + 2000 f0eachDay_10
+ 2000 f0elkedag_11 + 2000 f0elkedag_12 + 2000 f0elkedag_13
+ 2000 f0elkedag_14 + 2000 f0elkedag_15 + 2000 f0elkedag_16
+ 2000 f0elkedag_17 + 2000 f0elkedag_18 + 2000 f0elkedag_19
+ 2000 f0elkeDag_2 + 2000 f0elkeDag_20 + 2000 f0elkeDag_21
+ 2000 f0elkeDag_22 + 2000 f0elkeDag_23 + 2000 f0elkeDag_3 + 2000 f0elkeDag_4
+ 2000 f0eachDay_5 + 2000 f0eachDay_6 + 2000 f0eachDay_7 + 2000 f0eachDay_8
+ 2000 f0eachDay_9 + 1500 f1eachDay_0 + 1500 f1eachDay_1 + 1500 f1eachDay_10
+ 1500 f1elkeDag_11 + 1500 f1elkeDag_12 + 1500 f1elkeDag_13
+ 1500 f1elkeDag_14 + 1500 f1elkeDag_15 + 1500 f1elkeDag_16
+ 1500 f1elkeDag_17 + 1500 f1elkeDag_18 + 1500 f1elkeDag_19
+ 1500 f1elkeDag_2 + 1500 f1elkeDag_20 + 1500 f1elkeDag_21
+ 1500 f1elkeDag_22 + 1500 f1elkeDag_23 + 1500 f1elkeDag_3 + 1500 f1elkeDag_4
+ 1500 f1eachDag_5 + 1500 f1eachDag_6 + 1500 f1eachDag_7 + 1500 f1eachDag_8
+ 1500 f1eachDay_9 + 1000 f2eachDay_0 + 1000 f2eachDay_1 + 1000 f2eachDay_10
+ 1000 f2eachDay_11 + 1000 f2eachDay_12 + 1000 f2eachDay_13
+ 1000 f2eachDay_14 + 1000 f2eachDay_15 + 1000 f2eachDay_16
+ 1000 f2eachDay_17 + 1000 f2eachDay_18 + 1000 f2eachDay_19
+ 1000 f2elkeDag_2 + 1000 f2elkeDag_20 + 1000 f2elkeDag_21
+ 1000 f2elkeDag_22 + 1000 f2elkeDag_23 + 1000 f2elkeDag_3 + 1000 f2elkeDag_4
+ 1000 f2elkeDag_5 + 1000 f2elkeDag_6 + 1000 f2elkeDag_7 + 1000 f2elkeDag_8
+ 1000 f2eachDay_9 >= 80000
VARIABELEN
0 <= f0eachDay_0 <= 1 geheel getal
0 <= f0eachDay_1 <= 1 geheel getal
0 <= f0eachDay_10 <= 1 geheel getal
0 <= f0eachDay_11 <= 1 geheel getal
0 <= f0eachDay_12 <= 1 geheel getal
0 <= f0eachDay_13 <= 1 geheel getal
0 <= f0eachDay_14 <= ​​1 geheel getal
0 <= f0eachDay_15 <= 1 geheel getal
0 <= f0eachDay_16 <= 1 geheel getal
0 <= f0eachDay_17 <= 1 geheel getal
0 <= f0eachDay_18 <= 1 geheel getal
0 <= f0eachDay_19 <= 1 geheel getal
0 <= f0eachDay_2 <= 1 geheel getal
0 <= f0eachDay_20 <= 1 geheel getal
0 <= f0eachDay_21 <= 1 geheel getal
0 <= f0eachDay_22 <= 1 geheel getal
0 <= f0eachDay_23 <= 1 geheel getal
0 <= f0eachDay_3 <= 1 geheel getal
0 <= f0eachDay_4 <= 1 geheel getal
0 <= f0eachDay_5 <= 1 geheel getal
0 <= f0eachDay_6 <= 1 geheel getal
0 <= f0eachDay_7 <= 1 geheel getal
0 <= f0eachDay_8 <= 1 geheel getal
0 <= f0eachDay_9 <= 1 geheel getal
0 <= f1eachDay_0 <= 1 geheel getal
0 <= f1eachDay_1 <= 1 geheel getal
0 <= f1eachDay_10 <= 1 geheel getal
0 <= f1eachDay_11 <= 1 geheel getal
0 <= f1eachDay_12 <= 1 geheel getal
0 <= f1eachDay_13 <= 1 geheel getal
0 <= f1eachDay_14 <= ​​1 geheel getal
0 <= f1eachDay_15 <= 1 geheel getal
0 <= f1eachDay_16 <= 1 geheel getal
0 <= f1eachDay_17 <= 1 geheel getal
0 <= f1eachDay_18 <= 1 geheel getal
0 <= f1eachDay_19 <= 1 geheel getal
0 <= f1eachDay_2 <= 1 geheel getal
0 <= f1eachDay_20 <= 1 geheel getal
0 <= f1eachDay_21 <= 1 geheel getal
0 <= f1eachDay_22 <= 1 geheel getal
0 <= f1eachDay_23 <= 1 geheel getal
0 <= f1eachDay_3 <= 1 geheel getal
0 <= f1eachDay_4 <= 1 geheel getal
0 <= f1eachDay_5 <= 1 geheel getal
0 <= f1eachDay_6 <= 1 geheel getal
0 <= f1eachDay_7 <= 1 geheel getal
0 <= f1eachDay_8 <= 1 geheel getal
0 <= f1eachDay_9 <= 1 geheel getal
0 <= f2eachDay_0 <= 1 geheel getal
0 <= f2eachDay_1 <= 1 geheel getal
0 <= f2eachDay_10 <= 1 geheel getal
0 <= f2eachDay_11 <= 1 geheel getal
0 <= f2eachDay_12 <= 1 geheel getal
0 <= f2eachDay_13 <= 1 geheel getal
0 <= f2eachDay_14 <= ​​1 geheel getal
0 <= f2eachDay_15 <= 1 geheel getal
0 <= f2eachDay_16 <= 1 geheel getal
0 <= f2eachDay_17 <= 1 geheel getal
0 <= f2eachDay_18 <= 1 geheel getal
0 <= f2eachDay_19 <= 1 geheel getal
0 <= f2eachDay_2 <= 1 geheel getal
0 <= f2eachDay_20 <= 1 geheel getal
0 <= f2eachDay_21 <= 1 geheel getal
0 <= f2eachDay_22 <= 1 geheel getal
0 <= f2eachDay_23 <= 1 geheel getal
0 <= f2eachDay_3 <= 1 geheel getal
0 <= f2eachDay_4 <= 1 geheel getal
0 <= f2eachDay_5 <= 1 geheel getal
0 <= f2eachDay_6 <= 1 geheel getal
0 <= f2eachDay_7 <= 1 geheel getal
0 <= f2eachDay_8 <= 1 geheel getal
0 <= f2eachDay_9 <= 1 geheel getal

Nu is het duidelijk dat programma's met gemengde gehele getallen behoorlijk groot kunnen worden vanwege de beslissingsvariabelen. Het introduceren van gehele variabelen en beperkingen introduceert ook niet-lineariteit in het optimalisatieprobleem, waardoor het probleem veel moeilijker op te lossen is. In feite, voor een gemengd integer programma van behoorlijke omvang, groeit de oplossingstijd exponentieel met het aantal integer variabelen! Stel je voor dat je dat hebtNbinaire variabelen, hoeveel configuraties bestaan ​​er voor die binaire variabelen? Goed,2^nconfiguraties. Daarom is mixed integer programming nog steeds een actief onderzoeksgebied. De toepassingen van dergelijke programma's zijn enorm, zoals bij combinatorische optimalisatie of bij elk probleem waarvoor besluitvorming vereist is.

Ik hoop dat dit artikel het programmeren van gemengde gehele getallen op een korte en ongecompliceerde manier een beetje heeft gedemystificeerd, zodat het nuttig voor je kan zijn. Blijf optimaliseren!