Laat het gevonden worden probleem oplossing LP: . De oplossing Li zal een geheel getal zijn als
die. 
. (βi) - fractioneel deel niet-gehele optimale oplossing x i, (d i) is het fractionele deel van niet-basisvariabelen. Deze verhouding is bepalend (zie figuur). Doel van de dienst. De online rekenmachine wordt gebruikt om lineaire programmeerproblemen met gehele getallen op te lossen met behulp van de cutoff-methode. Tijdens de oplossing worden simplextabellen gebruikt. (zie voorbeeld).
Instructies. Selecteer het aantal variabelen en het aantal rijen (aantal beperkingen), klik op Volgende. De resulterende oplossing wordt opgeslagen in Word-bestand(zie een voorbeeld van een oplossing met behulp van de Gomori-methode). Bovendien wordt er een oplossingssjabloon gemaakt in Excel-indeling.
Tegelijkertijd zijn er beperkingen zoals x ik ≥ 0 hou er geen rekening mee.Soorten Gomori-algoritmen
- Gomori's eerste algoritme voor het oplossen van volledig gehele problemen.
- Gomori's tweede algoritme voor gedeeltelijk gehele lineaire programmeerproblemen.
Gomori-algoritme voor volledig gehele getallen omvat de volgende stappen:
- Het probleem van lineaire programmering wordt opgelost zonder rekening te houden met gehele getallen.
- Te midden van fractionele getallen het element met het grootste fractionele deel wordt geselecteerd en samengesteld extra beperking.
- De ongelijkheid wordt omgezet in een vergelijking door een extra niet-negatieve variabele te introduceren.
- Het resulterende probleem wordt opgelost met behulp van de dual-simplex-methode.
Voorbeeld. De Strela Research and Production Association houdt zich bezig met de vervaardiging van componenten voor militair-industriële complexe ondernemingen. Bij de vervaardiging van producten van type A en type B worden staal en non-ferrometalen gebruikt. Proces omvat tevens het bewerken van producten op draai- en freesmachines. Volgens technologische normen vereist de productie van één product van type A en één product van type B een bepaalde hoeveelheid grondstoffen en een bepaald aantal machine-uren voor verwerking op machines in de werkplaats. Technologische gegevens van het productieproces staan in de tabel.
Binnen een maand is de werkplaats van NPO Strela er beperkte middelen naar grondstoffen en naar werktijd in productiewinkels (zie tabel). De winst uit de verkoop van één product van type A is 100 roebel, en van een producteenheid van type B - 250 roebel.
| Grondstoffen | Werk in de werkplaats, machine-uur | Winst uit verkoop, wrijven. | |||
| Non-ferrometalen | Staal | Draaien werkt | Freeswerk | ||
| Product A | 10 | 25 | 41 | 90 | 100 |
| Product B | 30 | 25 | 90 | 50 | 250 |
| Bronnen | 4500 | 6250 | 14100 | 18000 | |
Vind het optimale productieplan voor NPO Strela (hoeveelheid producttype A en type B - gehele getallen) dat de grootste winst oplevert.
Oplossing.
Economisch wiskundig model taken.
x 1 - productieplan voor producten van type A, x 2 - productieplan voor producten van type B,
x 1, x 2 zijn gehele getallen.
Resourcelimieten
10x 1 + 30x 2 ≤ 4500
25x 1 + 25x 2 ≤ 6250
41x 1 + 90x 2 ≤ 14100
90x 1 + 50x 2 ≤ 18000
Objectieve functie
100x 1 + 250x 2 → max
Laten we een direct lineair programmeerprobleem oplossen met behulp van de simplexmethode. Als gevolg hiervan verkrijgen we het volgende optimale plan:
| Basis | B | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 |
| x 2 | 1450 / 11 | 0 | 1 | 41 / 330 | 0 | -1 / 33 | 0 |
| x 4 | 17500 / 11 | 0 | 0 | 245 / 66 | 1 | -50 / 33 | 0 |
| x 1 | 600 / 11 | 1 | 0 | -3 / 11 | 0 | 1 / 11 | 0 |
| x 6 | 6500 | 0 | 0 | 55 / 3 | 0 | -20 / 3 | 1 |
| F(X3) | 422500 / 11 | 0 | 0 | 125 / 33 | 0 | 50 / 33 | 0 |
x 1 = 54 6 / 11, x 2 = 131 9 / 11
F(X) = 250 131 9 / 11 + 100 54 6 / 11 = 38409 1 / 11
Het resulterende optimale plan is niet geheel getal, dus gebruiken we Gomori-methode. Het grootste fractionele deel bevindt zich in de tweede vergelijking voor de variabele x 4 (10 / 11). We creëren een extra beperking:
q 2 - q 21 x 1 - q 22 x 2 - q 23 x 3 - q 24 x 4 - q 25 x 5 - q 26 x 6 ≤0
q 2 = b 2 - = 1590 10 / 11 - 1590 = 10 / 11
q 2 1 = een 2 1 - = 0 - 0 = 0
q 2 2 = een 2 2 - = 0 - 0 = 0
q 2 3 = een 2 3 - = 3 47 / 66 - 3 = 47 / 66
q 2 4 = een 2 4 - = 1 - 1 = 0
q 2 5 = een 2 5 - = -1 17 / 33 + 2 = 16 / 33
q 2 6 = een 2 6 - = 0 - 0 = 0
10 / 11 - 47 / 66 x 3 - 16 / 33 x 5 ≤ 0
10 / 11 - 47 / 66 x 3 - 16 / 33 x 5 + x 7 = 0
Omdat dubbele simplex-methode gebruikt om het minimum van de objectieve functie te vinden, maken we de transformatie F(x) = -F(X).
| Basis | B | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 |
| x 2 | 1450 / 11 | 0 | 1 | 41 / 330 | 0 | -1 / 33 | 0 | 0 |
| x 4 | 17500 / 11 | 0 | 0 | 245 / 66 | 1 | -50 / 33 | 0 | 0 |
| x 1 | 600 / 11 | 1 | 0 | -3 / 11 | 0 | 1 / 11 | 0 | 0 |
| x 6 | 6500 | 0 | 0 | 55 / 3 | 0 | -20 / 3 | 1 | 0 |
| x 7 | -10 / 11 | 0 | 0 | -47 / 66 | 0 | -16 / 33 | 0 | 1 |
| F(X0) | -422500 / 11 | 0 | 0 | -125 / 33 | 0 | -50 / 33 | 0 | 0 |
Eerste versie van Gomori. 1. Controle van het optimaliteitscriterium. Het plan in een simplextabel is een pseudo-plan, dus we bepalen de leidende rij en kolom.
2. Definitie van een nieuwe vrije variabele. Onder de negatieve waarden van de basisvariabelen selecteren we de grootste in absolute waarde. De leidende lijn is de vijfde lijn en de variabele x 7 moet worden afgeleid van de basis.
3. Definitie van een nieuwe basisvariabele. Minimale waardeθ komt overeen met de vijfde kolom, d.w.z. de variabele x 5 moet in de basis worden ingevoerd. Op het snijpunt van de leidende rij en kolom bevindt zich een oplossend element (RE) gelijk aan (-16 / 33).
| Basis | B | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 |
| x 2 | 131 9 / 11 | 0 | 1 | 41 / 330 | 0 | -1 / 33 | 0 | 0 |
| x 4 | 1590 10 / 11 | 0 | 0 | 3 47 / 66 | 1 | -1 17 / 33 | 0 | 0 |
| x 1 | 54 6 / 11 | 1 | 0 | -3 / 11 | 0 | 1 / 11 | 0 | 0 |
| x 6 | 6500 | 0 | 0 | 18 1 / 3 | 0 | -6 2 / 3 | 1 | 0 |
| x 7 | -10 / 11 | 0 | 0 | -47 / 66 | 0 | -16 / 33 | 0 | 1 |
| F(X0) | -38409 1 / 11 | 0 | 0 | -3 26 / 33 | 0 | -1 17 / 33 | 0 | 0 |
| θ | - | - | -3 26 / 33: (-47 / 66) = 5 15 / 47 | - | -1 17 / 33: (-16 / 33) = 3 1 / 8 | - | - |
4. We herberekenen de simplextabel met behulp van de Jordano-Gauss-methode.
| Basis | B | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 |
| x 2 | 1055 / 8 | 0 | 1 | 27 / 160 | 0 | 0 | 0 | -1 / 16 |
| x 4 | 6375 / 4 | 0 | 0 | 95 / 16 | 1 | 0 | 0 | -25 / 8 |
| x 1 | 435 / 8 | 1 | 0 | -13 / 32 | 0 | 0 | 0 | 3 / 16 |
| x 6 | 13025 / 2 | 0 | 0 | 225 / 8 | 0 | 0 | 1 | -55 / 4 |
| x 5 | 15 / 8 | 0 | 0 | 47 / 32 | 0 | 1 | 0 | -33 / 16 |
| F(X0) | -153625 / 4 | 0 | 0 | -25 / 16 | 0 | 0 | 0 | -25 / 8 |
Het resulterende optimale plan bevat fractionele getallen. Met behulp van de eerste vergelijking met de variabele x2, die in het optimale plan een niet-gehele waarde kreeg met het grootste fractionele deel 7/8, creëren we een extra beperking:
q 1 - q 11 x 1 - q 12 x 2 - q 13 x 3 - q 14 x 4 - q 15 x 5 - q 16 x 6 - q 17 x 7 ≤0
q 1 = b 1 - = 131 7 / 8 - 131 = 7 / 8
q 1 3 = een 1 3 - = 27 / 160 - 0 = 27 / 160
q 1 7 = een 1 7 - = -1 / 16 + 1 = 15 / 16
Een aanvullende beperking heeft de vorm:
7 / 8 - 27 / 160 x 3 - 15 / 16 x 7 ≤ 0
Laten we de resulterende ongelijkheid omzetten in de vergelijking:
7 / 8 - 27 / 160 x 3 - 15 / 16 x 7 + x 8 = 0
waarvan we de coëfficiënten introduceren extra lijn naar het optimale simplex tafel.
| Basis | B | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | x 8 |
| x 2 | 1055 / 8 | 0 | 1 | 27 / 160 | 0 | 0 | 0 | -1 / 16 | 0 |
| x 4 | 6375 / 4 | 0 | 0 | 95 / 16 | 1 | 0 | 0 | -25 / 8 | 0 |
| x 1 | 435 / 8 | 1 | 0 | -13 / 32 | 0 | 0 | 0 | 3 / 16 | 0 |
| x 6 | 13025 / 2 | 0 | 0 | 225 / 8 | 0 | 0 | 1 | -55 / 4 | 0 |
| x 5 | 15 / 8 | 0 | 0 | 47 / 32 | 0 | 1 | 0 | -33 / 16 | 0 |
| x 8 | -7 / 8 | 0 | 0 | -27 / 160 | 0 | 0 | 0 | -15 / 16 | 1 |
| F(X0) | -153625 / 4 | 0 | 0 | -25 / 16 | 0 | 0 | 0 | -25 / 8 | 0 |
Tweede iteratie van Gomroya. 1. Controle van het optimaliteitscriterium. Het plan in een simplextabel is een pseudo-plan, dus we bepalen de leidende rij en kolom.
2. Definitie van een nieuwe vrije variabele. Van de negatieve waarden van de basisvariabelen is de grootste in absolute waarde de variabele x8. Het moet uit de basis worden afgeleid.
3. De minimumwaarde van θ komt overeen met de zevende kolom, d.w.z. de variabele x 7 moet in de basis worden ingevoerd.
| Basis | B | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | x 8 |
| x 2 | 131 7 / 8 | 0 | 1 | 27 / 160 | 0 | 0 | 0 | -1 / 16 | 0 |
| x 4 | 1593 3 / 4 | 0 | 0 | 5 15 / 16 | 1 | 0 | 0 | -3 1 / 8 | 0 |
| x 1 | 54 3 / 8 | 1 | 0 | -13 / 32 | 0 | 0 | 0 | 3 / 16 | 0 |
| x 6 | 6512 1 / 2 | 0 | 0 | 28 1 / 8 | 0 | 0 | 1 | -13 3 / 4 | 0 |
| x 5 | 1 7 / 8 | 0 | 0 | 1 15 / 32 | 0 | 1 | 0 | -2 1 / 16 | 0 |
| x 8 | -7 / 8 | 0 | 0 | -27 / 160 | 0 | 0 | 0 | -15 / 16 | 1 |
| F(X0) | -38406 1 / 4 | 0 | 0 | -1 9 / 16 | 0 | 0 | 0 | -3 1 / 8 | 0 |
| θ | - | - | -1 9 / 16: (-27 / 160) = 9 7 / 27 | - | - | - | -3 1 / 8: (-15 / 16) = 3 1 / 3 | - |
4. Voer de New Gomori-snijtransformatie uit.
| Basis | B | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | x 8 |
| x 2 | 1979 / 15 | 0 | 1 | 9 / 50 | 0 | 0 | 0 | 0 | -1 / 15 |
| x 4 | 4790 / 3 | 0 | 0 | 13 / 2 | 1 | 0 | 0 | 0 | -10 / 3 |
| x 1 | 271 / 5 | 1 | 0 | -11 / 25 | 0 | 0 | 0 | 0 | 1 / 5 |
| x 6 | 19576 / 3 | 0 | 0 | 153 / 5 | 0 | 0 | 1 | 0 | -44 / 3 |
| x 5 | 19 / 5 | 0 | 0 | 46 / 25 | 0 | 1 | 0 | 0 | -11 / 5 |
| x 7 | 14 / 15 | 0 | 0 | 9 / 50 | 0 | 0 | 0 | 1 | -16 / 15 |
| F(X0) | -115210 / 3 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | -10 / 3 |
Het optimale plan bevat fractionele getallen. Het grootste fractionele deel van de variabele is x 2 (14/15). We creëren een extra beperking: q 1 - q 11 x 1 - q 12 x 2 - q 13 x 3 - q 14 x 4 - q 15 x 5 - q 16 x 6 - q 17 x 7 - q 18 x 8 ≤0
q 1 = b 1 - = 131 14 / 15 - 131 = 14 / 15
q 1 1 = een 1 1 - = 0 - 0 = 0
q 1 2 = een 1 2 - = 1 - 1 = 0
q 1 3 = een 1 3 - = 9 / 50 - 0 = 9 / 50
q 1 4 = een 1 4 - = 0 - 0 = 0
q 1 5 = een 1 5 - = 0 - 0 = 0
q 1 6 = een 1 6 - = 0 - 0 = 0
q 1 7 = een 1 7 - = 0 - 0 = 0
q 1 8 = een 1 8 - = -1 / 15 + 1 = 14 / 15
Een aanvullende beperking heeft de vorm:
14 / 15 - 9 / 50 x 3 - 14 / 15 x 8 ≤ 0
Laten we de resulterende ongelijkheid omzetten in de vergelijking:
14 / 15 - 9 / 50 x 3 - 14 / 15 x 8 + x 9 = 0
waarvan de coëfficiënten als een extra regel in de optimale simplextabel worden ingevoerd.
| Basis | B | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | x 8 | x 9 |
| x 2 | 1979 / 15 | 0 | 1 | 9 / 50 | 0 | 0 | 0 | 0 | -1 / 15 | 0 |
| x 4 | 4790 / 3 | 0 | 0 | 13 / 2 | 1 | 0 | 0 | 0 | -10 / 3 | 0 |
| x 1 | 271 / 5 | 1 | 0 | -11 / 25 | 0 | 0 | 0 | 0 | 1 / 5 | 0 |
| x 6 | 19576 / 3 | 0 | 0 | 153 / 5 | 0 | 0 | 1 | 0 | -44 / 3 | 0 |
| x 5 | 19 / 5 | 0 | 0 | 46 / 25 | 0 | 1 | 0 | 0 | -11 / 5 | 0 |
| x 7 | 14 / 15 | 0 | 0 | 9 / 50 | 0 | 0 | 0 | 1 | -16 / 15 | 0 |
| x 9 | -14 / 15 | 0 | 0 | -9 / 50 | 0 | 0 | 0 | 0 | -14 / 15 | 1 |
| F(X0) | -115210 / 3 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | -10 / 3 | 0 |
Derde iteratie volgens de Gomori-methode. De variabele x 9 moet worden afgeleid van de basis. De minimumwaarde van θ komt overeen met de achtste kolom, d.w.z. de variabele x 8 moet in de basis worden ingevoerd.
| Basis | B | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | x 8 | x 9 |
| x 2 | 131 14 / 15 | 0 | 1 | 9 / 50 | 0 | 0 | 0 | 0 | -1 / 15 | 0 |
| x 4 | 1596 2 / 3 | 0 | 0 | 6 1 / 2 | 1 | 0 | 0 | 0 | -3 1 / 3 | 0 |
| x 1 | 54 1 / 5 | 1 | 0 | -11 / 25 | 0 | 0 | 0 | 0 | 1 / 5 | 0 |
| x 6 | 6525 1 / 3 | 0 | 0 | 30 3 / 5 | 0 | 0 | 1 | 0 | -14 2 / 3 | 0 |
| x 5 | 3 4 / 5 | 0 | 0 | 1 21 / 25 | 0 | 1 | 0 | 0 | -2 1 / 5 | 0 |
| x 7 | 14 / 15 | 0 | 0 | 9 / 50 | 0 | 0 | 0 | 1 | -1 1 / 15 | 0 |
| x 9 | -14 / 15 | 0 | 0 | -9 / 50 | 0 | 0 | 0 | 0 | -14 / 15 | 1 |
| F(X0) | -38403 1 / 3 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | -3 1 / 3 | 0 |
| θ | - | - | -1: (-9 / 50) = 5 5 / 9 | - | - | - | - | -3 1 / 3: (-14 / 15) = 3 4 / 7 | - |
4. Voer de transformatie uit.
| Basis | B | x 1 | x 2 | x 3 | x 4 | x 5 | x 6 | x 7 | x 8 | x 9 |
| x 2 | 132 | 0 | 1 | 27 / 140 | 0 | 0 | 0 | 0 | 0 | -1 / 14 |
| x 4 | 1600 | 0 | 0 | 50 / 7 | 1 | 0 | 0 | 0 | 0 | -25 / 7 |
| x 1 | 54 | 1 | 0 | -67 / 140 | 0 | 0 | 0 | 0 | 0 | 3 / 14 |
| x 6 | 6540 | 0 | 0 | 234 / 7 | 0 | 0 | 1 | 0 | 0 | -110 / 7 |
| x 5 | 6 | 0 | 0 | 317 / 140 | 0 | 1 | 0 | 0 | 0 | -33 / 14 |
| x 7 | 2 | 0 | 0 | 27 / 70 | 0 | 0 | 0 | 1 | 0 | -8 / 7 |
| x 8 | 1 | 0 | 0 | 27 / 140 | 0 | 0 | 0 | 0 | 1 | -15 / 14 |
| F(X0) | -38400 | 0 | 0 | -5 / 14 | 0 | 0 | 0 | 0 | 0 | -25 / 7 |
De oplossing bleek geheeltallig te zijn. Het optimale gehele plan kan als volgt worden geschreven: x 1 = 54, x 2 = 132. F(X) = 38400
Economische en geometrische interpretatie van het probleem integer programmeren. Een extreem probleem waarvan de variabelen alleen gehele waarden aannemen, wordt een geheeltallig programmeerprobleem genoemd.
In het wiskundige model van het gehele probleem programmering zowel de objectieve functie als de functies in het systeem van beperkingen kunnen lineair, niet-lineair en gemengd zijn. Laten we ons beperken tot het geval waarin objectieve functie en het systeem van beperkingen van het probleem is lineair.
Voorbeeld 20.
Er werd besloten om extra apparatuur te installeren in de werkplaats van de onderneming, waarvoor ruimte was toegewezen. Een onderneming kan 10.000 roebel uitgeven aan de aanschaf van apparatuur en kan twee soorten apparatuur kopen. Een set type I-apparatuur kost 1.000 roebel, en type II – 3.000 roebel.
Oplossing. Door één set type I-apparatuur aan te schaffen, kunt u de productie-output per ploegendienst met 2 eenheden verhogen, en één set type II-apparatuur met 4 eenheden. Wetende dat het installeren van één set type I-apparatuur een oppervlakte van 2 m 2 vereist, en type II-apparatuur 1 m 2 oppervlakte, bepaal een dergelijke set extra apparatuur die het mogelijk maakt de productie-output te maximaliseren
Laten we een wiskundig model van het probleem maken.
Laten we aannemen dat de onderneming x 1 sets apparatuur van type I en sets apparatuur van type II zal aanschaffen. Dan zijn de variabelen x 1 en moeten ze aan de volgende ongelijkheden voldoen:
Als de onderneming de gespecificeerde hoeveelheid apparatuur aanschaft, zal de totale productietoename zijn
Volgens hun economische inhoud zijn de variabelen x 1 en kunnen ze alleen niet-negatieve gehele waarden aannemen, d.w.z. x 1 , – gehele getallen.(73) Zo komen we tot het volgende wiskunde probleem: vinden maximale waarde lineaire functie (71) wanneer aan de voorwaarden (70), (72) en (73) is voldaan. Omdat onbekenden alleen gehele waarden kunnen aannemen, is probleem (70) – (73) een programmeerprobleem met gehele getallen. Omdat het aantal onbekenden in het probleem twee is, kan de oplossing voor dit probleem worden gevonden met behulp van de geometrische interpretatie ervan. Om dit te doen, zullen we allereerst een polygoon van oplossingen voor het probleem construeren, bestaande uit het bepalen van de maximale waarde van de lineaire functie (71) wanneer aan de voorwaarden (70) en (72) wordt voldaan (Fig. 11). Coördinaten van alle punten van de geconstrueerde oplossingspolygoon OAEVS het systeem bevredigen lineaire ongelijkheden (70) en staat niet-negativiteit variabelen (72). Tegelijkertijd voorwaarde (73), d.w.z. voorwaarde integriteit variabelen worden voldaan door de coördinaten van slechts 12 punten gemarkeerd in Fig. 11. Om het punt te vinden waarvan de coördinaten de oplossing voor het oorspronkelijke probleem bepalen, vervangt u de polygoon, met alle geldige punten met gehele coördinaten en zodanig dat de coördinaten van elk van de hoekpunten gehele getallen zijn. Dit betekent dat als we het maximale punt van functie (71) op de polygoon vinden variabelen worden voldaan door de coördinaten van slechts 12 punten gemarkeerd in Fig. 11. Om het punt te vinden waarvan de coördinaten de oplossing voor het oorspronkelijke probleem bepalen, vervangt u de polygoon, dan zullen de coördinaten van dit punt het optimale plan voor het probleem bepalen.
Om dit te doen, zullen we ook een rechte lijn construeren die door de oplossingspolygoon loopt variabelen worden voldaan door de coördinaten van slechts 12 punten gemarkeerd in Fig. 11. Om het punt te vinden waarvan de coördinaten de oplossing voor het oorspronkelijke probleem bepalen, vervangt u de polygoon(het getal 12 wordt willekeurig genomen). We verplaatsen de geconstrueerde lijn in de richting van de vector totdat deze door het laatste gemeenschappelijke punt met de gegeven veelhoek gaat. De coördinaten van dit punt bepalen het optimale plan, en de waarde van de objectieve functie daarin is het maximum.
IN in dit geval het vereiste punt is E(1; 3), waarbij de objectieffunctie de maximale waarde C aanneemt, dus de coördinaten van het punt E bepaal het optimale plan voor het probleem (70) – (73). In overeenstemming met dit plan moet de onderneming één set type 1-apparatuur en drie sets type II-apparatuur aanschaffen. Dit zal de onderneming voorzien van de bestaande beperkingen op productieruimte en fondsen maximale vergroting
productie-output gelijk aan 14 eenheden. per dienst.
Voorbeeld 21. Om het werk uit te voeren kan worden gebruikt N mechanismen. Prestatie i -de mechanisme bij het uitvoeren – J e werk is gelijk aan . Ervan uitgaande dat elk mechanisme slechts voor één taak kan worden gebruikt en elke taak slechts door één mechanisme kan worden uitgevoerd, bepaal dan de toewijzing van mechanismen aan taken die ervoor zorgen dat maximale prestaties
Oplossing.. Construeer een wiskundig model van het probleem. Laten we bij het uitvoeren een variabele x ij introduceren waarvan de waarde gelijk is aan 1 if -de mechanisme bij het uitvoeren – i-de
(74)
werk gebruikt
(75)
e-mechanisme, en anders gelijk aan 0. Vervolgens worden de voorwaarden voor het gebruik van elk mechanisme op slechts één taak uitgedrukt door de gelijkheden 
en de voorwaarden voor het uitvoeren van werk door slechts één mechanisme: gelijkheid
Het is dus de taak om dergelijke waarden van de onbekenden te bepalen
, voldoend aan stelsels van vergelijkingen (74) en (75) en voorwaarde (76), waaronder de maximale waarde van de functie wordt bereikt Laten we eens kijken naar integer-programmeerproblemen waarin zowel de objectieve functie als de functies in het systeem van beperkingen lineair zijn. In dit opzicht formuleren we het fundamentele lineaire programmeerprobleem waarbij variabelen alleen gehele waarden kunnen aannemen. Over het algemeen kan dit probleem als volgt worden geschreven: vind het maximum van de functie
onder voorwaarden
(79)
– heel (81)
Als we een oplossing vinden voor probleem (78) – (81) simplex methode, dan kan het wel of niet een geheel getal zijn (een voorbeeld waarvan de oplossing altijd een geheel getal is, is transport probleem). In het algemeen zijn er speciale methoden nodig om het optimale plan voor probleem (78) – (81) te bepalen. Momenteel zijn er verschillende van dergelijke methoden, waarvan de bekendste is Gomori-methode, die is gebaseerd op de hierboven beschreven simplexmethode.
Gomori-methode. Het vinden van een oplossing voor een geheeltallig programmeerprobleem met behulp van de Gomori-methode begint met het bepalen van het optimale plan van het probleem (78) – (80) met behulp van de simplex-methode, zonder rekening te houden (70) en staat variabelen. Zodra dit plan is gevonden, worden de componenten ervan beoordeeld. Als er geen fractionele getallen tussen de componenten voorkomen, is het gevonden plan het optimale plan voor het gehele programmeerprobleem (78) – (81). Als in het optimale plan van probleem (78) – (80) de variabele een fractionele waarde aanneemt, dan is de ongelijkheid
(82)
en een oplossing vinden voor probleem (78) – (80), (82).
In ongelijkheid (82) en – getransformeerde begingrootheden en waarvan de waarden zijn overgenomen uit de laatste simplextabel, en – fractionele delen van getallen (het fractionele deel van een bepaald getal a is het kleinste niet-negatieve getal B zodat het verschil tussen A En B er is een geheel). Als in het optimale probleemplan (78) – (80) de fractionele waarden verschillende variabelen aannemen, wordt de extra ongelijkheid (82) bepaald grootste fractie
deel.
Als in het gevonden plan van probleem (78) – (80), (82) de variabelen fractionele waarden aannemen, wordt er opnieuw één extra beperking toegevoegd en wordt het berekeningsproces herhaald. Door een eindig aantal iteraties uit te voeren, verkrijgt men óf het optimale plan voor het gehele programmeerprobleem (78) – (81), óf stelt men de onoplosbaarheid ervan vast. (70) en staat Als de eis (81) geldt alleen voor bepaalde variabelen; dergelijke problemen worden dan genoemd gedeeltelijk geheel getal. Hun oplossing wordt ook gevonden door problemen opeenvolgend op te lossen, die elk worden verkregen uit de vorige door een extra beperking te introduceren.
waar worden bepaald uit de volgende relaties:
1) voor , die niet-gehele waarden kan aannemen,
(84)
2) voor , die alleen gehele waarden kan aannemen,
(85)
Uit het bovenstaande volgt dat het proces voor het bepalen van het optimale plan voor een geheeltallig programmeerprobleem met behulp van de Gomori-methode het volgende omvat belangrijkste fasen:
1. Vind met behulp van de simplexmethode een oplossing voor probleem (78) – (80) zonder rekening te houden met de vereiste (70) en staat variabelen.
2. Creëer een extra beperking voor de variabele, die in het optimale plan van probleem (78) – (80) maximaal fractioneel waarde, en in het optimale plan moet probleem (78) – (81) een geheel getal zijn.
3. Vind met behulp van de duale methode een oplossing voor het probleem dat voortvloeit uit probleem (78) – (80) als resultaat van het toevoegen van een extra beperking.
4. Creëer indien nodig nog een extra beperking en ga door met het iteratieve proces totdat een optimaal plan voor het probleem (78) – (81) is verkregen of de onoplosbaarheid ervan is vastgesteld.
Voorbeeld 22.
Gebruik de Gomori-methode om de maximale waarde van de functie te vinden
gezien dat
(87)
– heel (89)
Oplossing. Om het optimale plan voor probleem (86) – (89) te bepalen, vinden we eerst het optimale plan voor probleem (86) – (88) (Tabel 22).
Tabel 22
|
C b |
R 0 |
|||||||
Zoals uit de tabel blijkt. 22, optimaal plan gevonden 
probleem (86) – (88) is geen optimaal plan voor probleem (86) – (89), aangezien het twee componenten zijn en niet-gehele waarden hebben. Bovendien zijn de fractionele delen van deze getallen gelijk aan elkaar. Daarom wordt voor een van deze variabelen een extra beperking gecreëerd. Laten we bijvoorbeeld een dergelijke beperking voor de variabele maken. Uit de laatste simplextabel (Tabel 22) hebben we
Aan het systeem van beperkingen van probleem (86) – (89) voegen we dus de ongelijkheid toe
of
Tabel 23
|
C b |
R 0 |
||||||||
We vinden nu de maximale waarde van functie (86) wanneer aan de voorwaarden (87), (88) en (90) wordt voldaan (Tabel 23).
Uit Tabel 23 blijkt dat het oorspronkelijke geheeltallige programmeerprobleem een optimaal plan heeft
P In dit plan is de waarde van de doelfunctie gelijk aan . Laten we een geometrische interpretatie geven van de oplossing voor het probleem. Het gebied van haalbare oplossingen voor probleem (86) – (88) is een veelhoek OABCD (Afb. 12). Vanaf afb. 12 is te zien dat de objectieffunctie op dat punt zijn maximale waarde aanneemt MET(19/2; 7/2), d.w.z. Wat X == (19/2; 7/2; 0; 0; 34) niet het optimale plan is voor probleem (86) – (89) (getallen en zijn breuken), dan wordt een extra beperking geïntroduceerd. Door dit uit te sluiten en in plaats daarvan de overeenkomstige waarden uit de vergelijkingen van het systeem van beperkingen (87) te vervangen, verkrijgen we een grenswaarde van de veelhoek Laten we een geometrische interpretatie geven van de oplossing voor het probleem. Het gebied van haalbare oplossingen voor probleem (86) – (88) is een veelhoek driehoek EFC.
Zoals blijkt uit Fig. 12 is het gebied van haalbare oplossingen voor het resulterende probleem een polygoon OABEFD. Op het punt E(9; 4) van deze veelhoek neemt de objectieve functie van dit probleem de maximale waarde aan. Sinds de coördinaten van het punt E zijn gehele getallen en onbekenden , en nemen gehele waarden aan bij het vervangen van de waarden en in vergelijking (87), dan 
is het optimale plan voor probleem (86) – (89). Dit volgt ook uit Tabel 23.
Voorbeeld 23.
Gebruik de Gomori-methode om een oplossing te vinden voor het probleem van het bepalen van de maximale waarde van een functie
onder voorwaarden
- geheel. (94)
Geef een geometrische interpretatie van de oplossing van het probleem.
Oplossing. Laten we het geformuleerde probleem als volgt herschrijven: vind de maximale waarde van de functie
onder voorwaarden
(96)
- geheel. (98)
Probleem (95) – (98) is gedeeltelijk geheel getal, omdat de variabelen niet-gehele waarden kunnen aannemen.
Met behulp van de simplexmethode vinden we de oplossing voor probleem (95) – (97) (Tabel 24).
Tabel 24
|
C b |
R 0 |
|||||||
|
C b |
R 0 |
|||||||
|
–1/3 is geen plan voor probleem (95) – (98), aangezien de variabele |
De essentie van snoeimethoden is dat het probleem eerst wordt opgelost zonder de voorwaarde van gehele getallen. Als het resulterende plan een geheel getal is, is het probleem opgelost. Anders wordt er een nieuwe beperking toegevoegd aan de taakbeperkingen met de volgende eigenschappen:
Het moet lineair zijn;
Moet het gevonden optimale niet-gehele plan afsnijden;
Mag geen enkel geheel plan afkappen.
Een extra beperking die deze eigenschappen heeft, wordt een correcte afkapwaarde genoemd.
Geometrisch elk toevoegen lineaire beperking komt overeen met het tekenen van een rechte lijn (hypervlak) die een deel ervan afsnijdt van de oplossingspolygoon (veelvlak) samen met het optimale punt met niet-gehele coördinaten, maar heeft geen invloed op de gehele punten van dit veelvlak. Als gevolg hiervan bevat het nieuwe oplossingsveelvlak alle gehele punten in het oorspronkelijke oplossingsveelvlak en dienovereenkomstig zal de optimale oplossing die met dit veelvlak wordt verkregen een geheel getal zijn (Fig. 8.1).
hoofdvariabelen *1, *2, nieuwe variabelen Xm+1, Xm+2, ..., Xm+1, oplossingen indrukken
Xt tot neo-x„optimaal
| (8.5) |
niet-gehele component. In dit geval kan worden bewezen dat de ongelijkheid
(P, ) - (a," m+\)xm+1 ■ -~(at )Xn ^ 0, (*)
gevormd door de /de vergelijking van systeem (8.5), heeft alle eigenschappen van een reguliere grenswaarde.
Om het gehele lineaire programmeringsprobleem (8.1)-(8.4) op te lossen met behulp van de Gomori-methode, wordt het volgende algoritme gebruikt:
1. Gebruik de simplexmethode om probleem (8.1)-(8.3) op te lossen zonder rekening te houden met de voorwaarde voor gehele getallen. Als alle componenten van het optimale plan geheeltallig zijn, dan is het optimaal voor het geheeltallige programmeerprobleem (8.1)-(8.4). Als het eerste probleem (8.1) -
(8.3) onoplosbaar is (dat wil zeggen dat er geen eindoptimum is of dat de voorwaarden ervan tegenstrijdig zijn), dan is het tweede probleem (8.1)-(8.4) ook onoplosbaar.
2. Als er onder de componenten van de optimale oplossing niet-gehele getallen zijn, selecteer dan de component met het grootste gehele deel en vorm met behulp van de overeenkomstige vergelijking van het systeem (8.5) de juiste grenswaarde (8.6).
3. Transformeer ongelijkheid (8.6) in een equivalente vergelijking door een extra niet-negatieve geheelvariabele te introduceren
(P() - |a/ t+1 )*t+1- ■-(a|"l )xn + xn+1 > (®*^)
en deze op te nemen in het systeem van beperkingen (8.2).
4. Los het resulterende uitgebreide probleem op met behulp van de simplexmethode. Als het gevonden optimale plan een geheel getal is,
dan is het gehele programmeerprobleem (8.1)-(8.4) opgelost. Ga anders terug naar stap 2 van het algoritme.
Als het probleem oplosbaar is in gehele getallen, zal na een eindig aantal stappen (iteraties) het optimale gehele plan worden gevonden.
Als tijdens het oplossen een vergelijking verschijnt (die de hoofdvariabele uitdrukt in termen van niet-basisvariabelen) met een niet-gehele vrije term en resterende gehele coëfficiënten, dan heeft de overeenkomstige vergelijking geen oplossing in gehele getallen. In dit geval heeft dit probleem geen optimale oplossing als geheel getal.
^ 8.1. Om graansorteerapparatuur aan te schaffen, wijst de boer 34 den toe. eenheden De apparatuur moet op een oppervlakte van maximaal 60 vierkante meter worden geplaatst. De boer kan twee soorten apparatuur bestellen: minder krachtige machines van het type A, die 3 m kosten. eenheden die een productieoppervlak van 3 m² vereisen. m (inclusief gangen) en een productiviteit van 2 ton graan per ploegendienst, en krachtigere type B-machines die 4 den kosten. eenheden met een oppervlakte van 5 vierkante meter. m en zorgt voor een productiviteit van 3 ton graan van hoge kwaliteit per ploegendienst.
Het is noodzakelijk om een optimaal plan op te stellen voor de aanschaf van apparatuur die een maximale algehele productiviteit garandeert, op voorwaarde dat de boer niet meer dan 8 machines van het type B kan aanschaffen.
Oplossing. Laten we met x\, x2 het aantal auto's van respectievelijk type A en B aangeven, met Z - algemene prestaties. Dan zal het wiskundige model van het probleem de vorm aannemen:
In afb. 8.2 OKM - gebied van haalbare oplossingen voor het probleem (8.1") - (8.3"), beperkt door rechte lijnen (1), (2), (3) en coördinaatassen; />(2/3; 8) - het punt van de optimale, maar niet-gehele oplossing voor het probleem (8.1") - (8.3"); (4) - een rechte lijn die deze niet-gehele oplossing afsnijdt; 0№М - gebied van haalbare oplossingen van het uitgebreide probleem (8.1’) - (8.3’), (8.61); M2; 7) - punt van optimale gehele oplossing.
Stap I. Hoofdvariabelen x3, x4, *5; niet-basisvariabelen X\, X2.
| x3 | = 60 - | Zh! - 5x2, |
| x4 | = 34 - | Zx) - 4x2, |
| x5 | = 8 | - *2> |
| Z = 2x) | + Zx2. |
De eerste basisoplossing X\ = (0; 0; 60; 34; 8) is toelaatbaar. Overeenkomstige lineaire functiewaarde = 0.
We vertalen de variabele XI naar de hoofdvariabelen, die is opgenomen in de uitdrukking van de lineaire functie met de grootste positieve coëfficiënt. We vinden de maximaal mogelijke waarde van de variabele xi, die door het systeem van beperkingen wordt geaccepteerd, uit de voorwaarde van het minimum van de overeenkomstige relaties:
Хг = 1ШП|т;т;Т| = 8,
die. de oplossende (gemarkeerde) vergelijking is de derde. Wanneer *2 = 8 in deze vergelijking X5 = 0, en de variabele X5 niet-basisch wordt.
Stap II. Hoofdvariabelen x2, x3, x*; niet-hoofdvariabelen Xx X5.
| { |
| (8.6) |
Door een extra geheel getalvariabele x6 > O te introduceren, verkrijgen we de vergelijking die equivalent is aan ongelijkheid (8,6")
~1*5 + Xb = °" ^8"7 ^
Vergelijking (8.7") moet worden opgenomen in het systeem van beperkingen (8.5") van het oorspronkelijke canonieke probleem, en herhaal dan het proces van het oplossen van het probleem met behulp van de simplexmethode in relatie tot het uitgebreide probleem. In dit geval wordt aanbevolen om, om het aantal stappen (iteraties) te verminderen, een extra vergelijking (8,7") in het systeem te introduceren die is verkregen bij de laatste stap van het oplossen van het probleem (zonder de voorwaarde voor gehele getallen).
IV-stap. Basisvariabelen X), *2, xs> *b‘> niet-basisvariabelen *1, *2-
X1 = z - 3*4 +
x3 = 18 + x4 +___ x5,
x6 - + ^x4 + z"x5-
De basisoplossing X4 = (y; 8; 18; 0; 0; -y) is onaanvaardbaar. (Merk op dat na het opnemen van een aanvullende vergelijking die overeenkomt met de juiste grenswaarde in het beperkingssysteem, er altijd een ongeldige basisoplossing zal worden verkregen.)
Om een acceptabele basisoplossing te verkrijgen, is het noodzakelijk om te converteren naar de hoofdvariabele, die met een positieve coëfficiënt is opgenomen in de vergelijking waarin de vrije term negatief is, d.w.z. *1 of x$ (in dit stadium beschouwen we geen lineaire functie). We vertalen naar eenvoudige, bijvoorbeeld de variabele X5.
V-stap. Hoofdvariabelen X\, X2, X3, X5; niet-basisvariabelen R], X £
Na transformaties krijgen we:
LG| = 2 - x4 + 2x6,
*2 = 7 + 2х* ~ 2Х("
x3 = 19 + -x4 + -x6,
*5 = 1 - 2х* + 2Х6’
2 = 25-|x4--|x6.
^5 =(2; 7; 19; 0; 1;0);^ = 25.
Omdat er geen hoofdvariabelen met positieve coëfficiënten zijn in de uitdrukking van een lineaire functie, is X5 de optimale oplossing.
Dus 2max = 25 optimaal gehele oplossing X* - X$ =(2; 7; 19; 0; 1; 0), d.w.z. de maximale productiviteit van 25 ton graan van hoge kwaliteit per ploegendienst kan worden verkregen door de aankoop van 2 machines van het type A en 7 machines van het type B\, terwijl de onbezette oppervlakte van het pand 19 m² zal bedragen. M, blijft contant geld van de toegewezen zijn gelijk aan 0, in de reserve voor aankoop - 1 machine van het type B (het zesde onderdeel heeft geen betekenisvolle betekenis).
Opmerking. Voor een geometrische interpretatie op het vlak Ox\Xr (zie Fig. 8.2) van de cutoff (8.6"), is het noodzakelijk om de daarin opgenomen variabelen x4 en x$ uit te drukken via de variabelen XI en x2. We verkrijgen (zie de 2e en 3e vergelijking van het systeem van beperkingen (8,5")):
y - y (34 - 3x, - 4x2) - y (8 - x2) £ 0 of x, + 2x2 £ 16.
(zie kniplijn (4) in Afb. 8.2)>
^ 8.2. Er zijn er genoeg groot aantal boomstammen van 3 m lang. Boomstammen moeten in twee soorten stukken hout worden gesneden: 1,2 m lang en 0,9 m lang, en er moeten minstens 50 stukken van elk type worden verkregen. en 81 st. respectievelijk. Elke boomstam kan op verschillende manieren in de aangegeven stukken worden gezaagd: 1) in 2 stukken van elk 1,2 m; 2) voor 1 stuk van elk 1,2 m en 2 stuks van elk 0,9 m; 3) voor 3 stukken van elk 0,9 m. Zoek het aantal houtblokken,
gezaagd volgens elke methode, zodat elk soort werkstuk kan worden verkregen uit het kleinste aantal houtblokken.
Oplossing. Laten we met х\, хі, хм het aantal houtblokken aangeven dat dienovereenkomstig op 1, 2 en 3 manieren is gesneden. Hieruit kun je 2хі + *2 blanco's van elk 1,2 m en 2l\ + 3x2 blanco's van elk 0,9 m krijgen. we geven het totale aantal logs aan met I. Dan zal het wiskundige model van het probleem de vorm aannemen:
I 2х, + x2 - x4 = 50, , niet hoger dan dit.
Onder fractioneel deel
een aantal A betekent het kleinste niet-negatieve getal 
zodanig dat het verschil tussen en A Er is [ A] – geheel getal van het getal).
Voor de geselecteerde basisvariabele 
met het grootste fractionele deel
zoek het fractionele deel 
deze variabele en de fractionele delen van alle coëfficiënten voor de variabelen mechanismen. Prestatie e lijn van het systeem van beperkingen 
(productielijn).
Laten we aanduiden 
En 
hele delen van getallen 
En 
. Fractionele waarden 
En 
(
) worden als volgt gedefinieerd
Om dit te doen, wordt een vergelijking opgeschreven uit de genererende rij van de simplextabel, ervan uitgaande dat de eerste M variabelen zijn essentieel voor een bepaald optimaal plan
of 
We verplaatsen alle gehele delen van de coëfficiënten in de ene richting en laten alle fractionele delen in de andere richting:
Omdat 
<1,
то заменяя в правой части 
, verkrijgen we de strikte ongelijkheid
Omdat de linkerkant van de ongelijkheid gehele waarden moet aannemen, kan de noodzakelijke voorwaarde voor de integriteit ervan alleen in de volgende vorm worden geschreven:
De ongelijkheid wordt omgezet in een vergelijking door een extra niet-negatieve variabele te introduceren en opgenomen in de optimale simplextabel.
We lossen het probleem op met behulp van de dual-simplex-methode. Als het nieuwe optimale plan voor het uitgebreide probleem een geheel getal is, is het probleem opgelost. Als de oplossing een niet-geheel getal is, moet u het algoritme van de Gomori-methode herhalen totdat een geheeltallige oplossing is verkregen.
Voorbeeld.
Gebruik de Gomori-methode om een oplossing te vinden voor een programmeerprobleem met gehele getallen, bestaande uit het bepalen van de maximale waarde van een functie 
gezien dat
Oplossing. Ongelijkheden nivelleren met behulp van hulpvariabelen X 3 , X 4 verkrijgen we het lineaire programmeerprobleem in canonieke vorm:
We lossen het lineaire programmeerprobleem op met behulp van de simplexmethode, waarbij we een stapsgewijze overgang van de ene basis naar de andere gebruiken. De voortgang bij het oplossen van het probleem en de daaruit voortvloeiende optimale oplossing worden in de tabellen weergegeven.
|
(Afb. 12). B |
(Afb. 12). 2 =11 | |||||
|
| ||||||
|
∆ -de mechanisme bij het uitvoeren =Z -de mechanisme bij het uitvoeren -MET -de mechanisme bij het uitvoeren | ||||||
|
(Afb. 12). B |
(Afb. 12). 2 =11 | |||||
|
| ||||||
|
|
|
| ||||
|
∆ -de mechanisme bij het uitvoeren =Z -de mechanisme bij het uitvoeren -MET -de mechanisme bij het uitvoeren |
|
|
| |||
In het gevonden optimale plan de waarde van de variabele X 2 is gelijk aan een breukgetal. We vinden het fractionele deel ervan en de fractionele delen van alle elementen van de lijn die de variabele bevat X 2, namelijk:
Nu stellen we de Gomori-ongelijkheid samen voor de gevonden waarden van de fractionele delen:
.
X 5 verplaatsen we de vrije term van de vergelijking naar de rechterkant en krijgen we een nieuwe beperking:
.
We voegen een rij met een nieuwe beperking en een kolom met een nieuwe variabele toe aan de simplextabel en gaan door met het oplossen van het probleem met behulp van de dual simplex-methode, aangezien het pseudoplan nu in de tabel is geschreven.
|
| |||||||
|
|
|
| |||||
|
|
|
| |||||
|
∆ -de mechanisme bij het uitvoeren =Z -de mechanisme bij het uitvoeren –(Afb. 12). -de mechanisme bij het uitvoeren |
|
|
| ||||
|
(Afb. 12). B |
(Afb. 12). 2 =11 | ||||||
|
|
|
|
|||||
|
|
|
||||||
|
∆ -de mechanisme bij het uitvoeren =Z -de mechanisme bij het uitvoeren –(Afb. 12). -de mechanisme bij het uitvoeren |
|
|
|||||
De resulterende optimale oplossing voor het uitgebreide probleem bevat een niet-gehele waarde van de variabele X 1, dus we vinden voor deze regel de breukdelen van alle niet-gehele getallen, namelijk:
en de nieuwe Gomory-ongelijkheid heeft de vorm: 
We egaliseren de ongelijkheid van Gomori met behulp van een nieuwe hulpvariabele X 6 verplaatsen we de vrije term van de vergelijking naar de rechterkant en krijgen we een nieuwe beperking: 
.
We voegen het toe aan het probleem dat wordt opgelost, stemmen het af met behulp van een hulpvariabele en lossen het uitgebreide probleem op
|
(Afb. 12). B |
(Afb. 12). 2 =11 | |||||||
|
|
|
| ||||||
|
|
| |||||||
|
|
|
| ||||||
|
∆ -de mechanisme bij het uitvoeren =Z -de mechanisme bij het uitvoeren –(Afb. 12). -de mechanisme bij het uitvoeren |
|
| ||||||
|
(Afb. 12). B |
(Afb. 12). 2 =11 | |||||||
|
∆ -de mechanisme bij het uitvoeren =Z -de mechanisme bij het uitvoeren –(Afb. 12). -de mechanisme bij het uitvoeren | ||||||||
Zo is de optimale oplossing voor het gehele programmeerprobleem gevonden: Z maximaal=11 op 
.
Opmerkingen :
Als tijdens het oplossingsproces een vergelijking met een niet-gehele component in de simplextabel verschijnt 
en gehele coëfficiënten in de overeenkomstige regel van het systeem van beperkingen 
, dan heeft dit probleem geen geheeltallige oplossing.
De methode is gebaseerd op de simplexmethode, die wordt gebruikt om de optimale oplossing te vinden zonder rekening te houden met gehele getallen. Als het resulterende plan ten minste één fractionele component bevat, wordt een extra beperking opgelegd en worden de berekeningen opnieuw voortgezet met behulp van de simplexmethode.
Het proces gaat door totdat alle componenten van het plan geheeltallig zijn, of totdat wordt aangetoond dat het probleem geen geheeltallige oplossing heeft.
Laat X* = (x1, x2, …, xm, …, xn) het optimale plan zijn dat wordt gevonden met behulp van de simplexmethode, waarbij de basis de vectoren A1, A2,…, Am zijn. Laat xi een gebroken getal zijn (het getal in kolom B in de i-de rij). Dan is het mogelijk dat in de i-de regel:
1. alle xij zijn gehele getallen, dit betekent dat het probleem geen geheeltallige oplossing heeft
2. sommige xij zijn fractioneel
Laat [xi] en [xij] gehele delen zijn van de getallen xi en хij, en (xi) en (хij) gebroken delen.
Laten we qi = (хi) en qij = (хij) aanduiden en de verschillen samenstellen.
(qi1Х1+ qi1Х2+…+ qi1Хn)- qi ≥0
Laten we de ongelijkheid omzetten in een vergelijking door deze te vermenigvuldigen met (-1) en een nieuwe variabele Xn+1 toe te voegen en een nieuwe rij toe te voegen aan de simplextabel (en dus een kolom). We lossen verder op met behulp van de dual simplex-methode; als het gevonden plan geen geheel getal is, herhalen we het proces van het toevoegen van een nieuwe variabele, rij en kolom aan de simplextabel.
Als het optimale plan meerdere niet-gehele componenten bevat, creëren we een extra beperking voor de maximale qi.
De informatie waarin u geïnteresseerd bent, kunt u ook vinden in de wetenschappelijke zoekmachine Otvety.Online. Gebruik het zoekformulier:
Meer over onderwerp 47 Gomori-methode: hoofdideeën en korte beschrijving van het algoritme. De economische betekenis van het introduceren van een extra beperking:
- 25. Economische managementmethoden, hun beoogde doel. Typen en belangrijkste inhoud van methoden voor economische beïnvloeding. Korte beschrijving en kenmerken van de toepassing van economische methoden
