Simplexová metóda je univerzálna. S jeho pomocou je možné vyriešiť akýkoľvek problém lineárneho programovania. Vďaka svojej univerzálnosti však nie je zbavený niektorých nevýhod. V niektorých prípadoch je na riešenie úloh lineárneho programovania vhodnejšia takzvaná duálna metóda. Táto metóda je založená na teórii duality, jednej z najdôležitejších zložiek všeobecnej teórie lineárneho programovania.

Teória duality sa používa na vývoj metód na riešenie mnohých prakticky dôležitých tried lineárnych optimalizačných problémov: problémy transportného typu, lineárne celočíselné problémy atď. Pozrime sa na hlavné ustanovenia tejto teórie.

Každý problém lineárneho programovania zodpovedá inému problému, v určitom zmysle jeho opaku. Ak sa prvý problém nazýva priamy, potom sa opak nazýva duálny. Keďže duálny problém k duálnemu problému je pôvodný priamy problém, nezáleží na tom, ktorý problém sa nazýva priamy a ktorý duálny. Preto sa priame a duálne problémy nazývajú duálne párové problémy.

Duálny problém je formulovaný priamo z priameho použitia určité pravidlá. Keďže priame problémy môžu mať obmedzenia vo forme nerovností typu, typu alebo vo forme rovnosti, pravidlá na získanie duálnych problémov pre ne sa ukazujú byť odlišné.

Existujú symetrické, asymetrické a zmiešané duálne problémy. V symetrických problémoch majú obmedzenia priameho problému tvar . V obmedzeniach asymetrického problému používajú obmedzenia priameho problému znamienka. V zmiešaných problémoch sa používajú oba typy vzťahov „menší alebo rovný“ a „rovná sa“. V asymetrických a zmiešaných problémoch sa na novozavedené premenné nekladie požiadavka ich nezápornosti.

Výpočty založené na vzťahoch duality začínajú redukciou priamych a duálnych problémov na štandardnú formu. Preto sa môžeme obmedziť na formuláciu pravidiel na vytvorenie problému, ktorý je duálny voči štandardnému problému lineárneho programovania. Pravidlá pre získanie duálneho problému pre iné typy problémov LP možno získať z týchto pravidiel.

Napíšme problém LP v štandardnom tvare:

,

,

i = 1,..., m; j=1,..,n.

Nazvime tento problém priamo. Potom bude úloha vo vzťahu k nej dvojaká:

,

i = 1,..., m; j=1,..,n.

Po analýze úloh môžeme vyvodiť tieto závery:

1. Každé obmedzenie priameho problému zodpovedá premennej duálneho problému.

2. Každá premenná priameho problému zodpovedá obmedzeniu duálneho problému.

3. Koeficienty pre ľubovoľnú premennú v obmedzeniach priameho problému sa stanú obmedzujúcimi koeficientmi pre duálny problém zodpovedajúci tejto premennej a pravá strana vygenerovaného obmedzenia sa rovná koeficientu pre túto premennú vo vyjadrení účelovej funkcie.

4. Typ extrému duálneho problému je opačný ako typ extrému priameho problému;

5. Vektory B a C v priamych a duálnych úlohách menia miesta;

6. Matica A duálny problém sa získa transpozíciou matice A priama úloha;

7. Všetky obmedzenia duálneho problému majú tvar pre maximalizačný problém a tvar pre lineárny tvarový minimalizačný problém.

V prípade symetrického duálneho problému:

V prípade asymetrického problému:

Dvojitý problém má tvar:

Zmiešané problémy obsahujú obmedzenia vo forme rovnosti a nerovností. Pri skladaní duálnej úlohy je potrebné použiť prechodové pravidlá pre symetrické a asymetrické úlohy.

Nižšie uvedené príklady slúžia na ilustráciu pravidiel na získanie duálnych problémov.

Príklad Je daný problém lineárneho programovania (naľavo od každého obmedzenia je s ním spojená duálna premenná). Táto úloha odkazuje na asymetrické.

,

Sformulujme pre tento problém dvojitý problém. Účelová funkcia duálnej úlohy je lineárna forma získaná ako súčin vektora b=(10,20,60,80) vektorom premenných duálnej úlohy Y =( ). Navyše, keďže v priamom probléme je účelová funkcia maximalizovaná, v duálnom probléme je minimalizovaná. Berúc do úvahy vyjadrené pripomienky, získavame

Ľavá strana prvého obmedzenia duálneho problému je súčinom vektora systému obmedzení priameho problému spojeného s premennou , a vektora premenných duálneho problému. Pravá strana tohto obmedzenia sa rovná koeficientu premennej , v objektívnej funkcii priameho problému.

A keďže, navyše, priamym problémom je problém nájsť maximum, prvé obmedzenie má tvar:

Podobne získame druhé obmedzenie duálneho problému: . Absencia premennej v tomto obmedzení je spôsobená tým, že v druhom obmedzení priameho problému neexistuje žiadna premenná.

Premenná spojená s treťou premennou duálneho problému sa vyskytuje iba v prvom obmedzení priameho problému. Z tohto dôvodu dostaneme tretie obmedzenie . Analogicky dostaneme štvrté, piate a šieste obmedzenie: .

Teda aj napriek tomu, že podmienka nezápornosti nebola špecificky kladená na premenné duálneho problému, napriek tomu sa ukázalo, že je splnená pre všetky.

Príklad Vzhľadom na problém lineárneho programovania v neštandardná forma

,

,

,

Neobmedzené v znamení .

Napíšme tento problém v štandardnej forme. Aby sme to urobili, urobme zmenu premenných , zaveďme redundantnú premennú do druhého obmedzenia a dodatočnú premennú do tretieho. Dostaneme

,

.

Sformulujme duálny problém. Keďže v priamom probléme je účelová funkcia minimalizovaná, má účelová funkcia duálneho problému tvar .

Z rovnakého dôvodu sú prvé, druhé a tretie obmedzenie duálneho problému spojené s premennými sa píšu takto:

,

Keďže premenná sa vyskytuje iba v druhej a premenná iba v tretej rovnici priameho problému, súvisiace obmedzenia duálneho problému sú:

.

Z troch premenných duálneho problému sa teda jedna ukázala ako neobmedzená v znamienkach.

Pomocou teorémov duality, keď poznáte riešenie jedného z problémov, môžete nájsť optimálne riešenie druhého bez toho, aby ste ho riešili.

Uvažujme o zmiešanom probléme.

Dvojitý problém bude mať tvar:

Ak použijeme kanonickú formu problému lineárneho programovania, potom máme do činenia s problémom asymetrického lineárneho programovania.

Kanonická forma problému je:

Dvojitý problém bude vyzerať takto:

Veta 1. Pre akúkoľvek dvojicu realizovateľných riešení priameho a duálneho problému hodnota cieľovej funkcie v úlohe maximalizácie nepresahuje hodnotu cieľovej funkcie v úlohe minimalizácie.

Praktická hodnota tejto vety je nasledovná. V praxi je niekedy lepšie získať riešenie blízko optima, ale v krátkom čase, ako získať optimálne riešenie, ale za podstatne dlhší čas. V tomto prípade môže posledná nerovnosť slúžiť ako odhad blízkosti riešenia získaného pri ďalšej iterácii k optimu.

Veta 2. Ak má jeden z duálnych problémov optimálne riešenie, potom aj druhý má optimálne riešenie a hodnoty cieľových funkcií pre obe riešenia sa zhodujú. Ak má jeden z duálnych problémov neobmedzenú objektívnu funkciu, potom je druhý neriešiteľný, to znamená, že nemá žiadne realizovateľné riešenia.

Veta. Aby boli prípustné riešenia optimálne, je potrebné a postačujúce, aby vyhovovali sústave rovníc

.

Táto veta znamená, že jedna z premenných akéhokoľvek problému je striktne väčšia ako nula, potom je zodpovedajúce obmedzenie v druhom duálnom probléme splnené ako prísna rovnosť a naopak, ak je pri optimálnom riešení akékoľvek obmedzenie splnené ako prísna nerovnosť. , potom zodpovedajúca premenná v optimálnom riešení je nula.

Príklad Poďme vyriešiť symetrický problém. Nech má pôvodný problém formu

Ak problém vyriešime graficky, dostaneme

Vytvorme pre to dvojitý problém

Takže cieľové funkcie v optimálnom bode sú rovnaké

Keďže premenné
, potom zodpovedajúce obmedzenia v duálnom probléme obsahujú znamienko rovnosti. Tieto obmedzenia majú formu

Dosaďte hodnoty do obmedzení . Dostaneme

.

V tomto systéme je prísna len prvá nerovnosť. teda . Ďalšie hodnoty premenných nájdeme zo sústavy rovníc

.

Výsledkom riešenia tohto systému lineárnych algebraických rovníc získame

Vyriešme ten istý problém, ale za predpokladu, že riešenie je známe

Keďže druhá a tretia premenná sú striktne väčšie ako nula, zodpovedajúce obmedzenie je splnené ako prísna rovnosť.

.

Rozhodovanie tento systém rovnice, dostaneme

Ak sa pôvodná úloha rieši simplexovou metódou a koeficienty sa získajú vo výslednej účelovej funkcii - matici - riadku koeficientov, potom riešenie duálnej úlohy možno nájsť pomocou vzorca kde je matica koeficientov pre základné premenné účelovej funkcie pri optimálnom riešení pôvodného problému.

Uvažujme o ekonomickej interpretácii duálneho problému.

Veta. Hodnoty premenných v optimálnom riešení duálneho problému predstavujú odhady vplyvu voľných členov obmedzení pôvodného problému na optimálnu hodnotu jeho účelovej funkcie. Pretože

Potom duálne premenné ukazujú, ako sa cieľová funkcia zmení, keď sa zdroj zmení o jednu

Stručná teória

Vyplníme simplexnú tabuľku 0. iterácie.

BP Simplexné
vzťah		 8 6 4 0 0 0 0 520 16 18 9 1 0 0 65/2 0 140 7 7 2 0 1 0 20 0 810 9 2 1 0 0 1 90 0 -8 -6 -4 0 0 0

Keďže úlohu riešime na maximum, prítomnosť záporných čísel v indexovom riadku pri riešení úlohy na maximum naznačuje, že sme nedosiahli optimálne riešenie a je potrebné prejsť z tabuľky 0. iterácie. do ďalšieho.

Pokračujeme k ďalšej iterácii takto:

Vedúci stĺpec zodpovedá .

Kľúčový riadok je určený minimálnym pomerom voľných výrazov a členov vedúceho stĺpca (jednoduché vzťahy):

Na priesečníku kľúčového stĺpca a kľúčového radu nájdeme povoľovací prvok, teda 7.

Teraz začneme zostavovať 1. iteráciu. Namiesto jednotkového vektora zavedieme vektor .

IN nový stôl namiesto povoľovacieho prvku napíšeme 1, všetky ostatné prvky kľúčového stĺpca sú nuly. Prvky reťazca kľúčov sú rozdelené na prvok enable. Všetky ostatné prvky tabuľky sa vypočítajú pomocou pravidla obdĺžnika.

Dostaneme tabuľku 1. iterácie:

BP Simplexné
vzťah		 8 6 4 0 0 0 0 200 0 2 31/7 1 -16/7 0 1400/31 8 20 1 1 2/7 0 1/7 0 70 0 630 0 -7 -11/7 0 -9/7 1 - 160 0 2 -12/7 0 8/7 0

Kľúčový stĺpec pre 1. iteráciu zodpovedá .

Nájdeme kľúčový riadok, na ktorý definujeme:

Na priesečníku kľúčového stĺpca a kľúčového radu nájdeme povoľovací prvok, t.j. 31/7.

Vektor sa odvodí od bázy a vektor sa zavedie.

Dostaneme tabuľku 2. iterácie:

BP Simplexné
vzťah		 8 6 4 0 0 0 4 1400/31 0 14/31 1 7/31 -16/31 0 8 220/31 1 27/31 0 -2/31 9/31 0 0 21730/31 0 -195/31 0 11/31 -65/31 1 7360/31 0 86/31 0 12/31 8/31 0

V riadku indexu sú všetky členy nezáporné, takže sa získa nasledujúce riešenie problému lineárneho programovania (vypíšeme ho zo stĺpca voľných členov):

Preto je potrebné predať 7,1 tisíc rubľov. tovar 1. druhu a 45,2 tisíc rubľov. tovar 3. druhu. Nie je výhodné predávať výrobok 2. typu. V tomto prípade bude zisk maximálny a bude 237,4 tisíc rubľov. Ak sa zrealizuje optimálny plán, zostávajúci zdroj 3. typu bude 701 jednotiek.

Problémy duálneho lineárneho programovania.

Každý problém lineárneho programovania má zodpovedajúci duálny problém.

Algoritmus na zostavenie duálneho problému.

Príklad 1

Zostavte dvojitý problém

1. Všetky nerovnosti systému obmedzení pôvodného problému privádzame do jedného významu

2. Zostavte rozšírenú maticu

3. Transponujte maticu

4. Formulujte duálny problém

Pôvodný (priamy) problém

Dvojitý problém

Problém lineárneho programovania možno považovať za model alokácie obmedzených zdrojov, v ktorom objektívna funkcia predstavujúca zisk alebo príjem z výrobnej činnosti podlieha maximalizácii. Ak vezmeme do úvahy problém lineárneho programovania z tohto hľadiska, zodpovedajúci duálny problém dostane zaujímavú ekonomickú interpretáciu.

premenlivý pri i duálny problém predstavuje náklady na jednotku zdroja i. V literatúre operačného výskumu premenné pri i duálny problém sa často nazýva duálne ceny . Okrem toho sa niekedy nazývajú tieňové ceny A simplexné multiplikátory .

Podobne pre každú dvojicu prípustných riešení priameho a dvojitého problému je nerovnosť f < z možno interpretovať nasledovne:

príjem< Общая стоимость ресурсов

Tento vzťah ukazuje, že pokiaľ sú celkové príjmy zo všetkých druhov činností striktne nižšie ako celkové náklady na všetky použité zdroje, riešenie priameho aj duálneho problému nemôže byť optimálne. Optimum (maximálny príjem) je možné dosiahnuť len vtedy, keď sú všetky spotrebované zdroje plne využité.

Veľký praktický záujem má ekonomická interpretácia druhej vety o dualite, ako aj jej dôsledky na komplementárnu nerigiditu.

1. Ak je celkové hodnotenie i-tého zdroja kladné

potom je tento zdroj plne využitý v súlade s optimálnym plánom x*

2. Ak i-tý zdroj nie je plne využitý

potom je jeho optimálny odhad nula a i-té obmedzenie nehmotný.

3. Ak v súlade s optimálnym plánom x* j-tych produktov vyrobené

potom je táto výroba efektívna, keďže cena jednotky j-tého produktu

rovná nákladom na jeho výrobu v jednotkách

4. Ak výroba j-tých produktov nerentabilné (znížené náklady sú nenulové

potom sa v súlade s optimálnym plánom tento produkt nevyrába

Duálne odhady teda súvisia s optimálnym návrhom priameho problému. Akákoľvek zmena počiatočných údajov priameho problému ovplyvňuje jeho optimálny plán a systém duálnych odhadov. Duálne hodnotenia zase slúžia ako nástroj na analýzu a prijímanie správnych rozhodnutí v meniacich sa obchodných situáciách.

Uvádzajú sa pravidlá pre tvorbu duálnych úloh. Zvažujú sa symetrické, asymetrické a zmiešané páry. Analyzované sú príklady skladania duálnych úloh.

Obsah

Úlohy duálneho alebo konjugovaného lineárneho programovania majú tú vlastnosť, že riešením jedného z problémov je možné získať riešenie iného problému. Tu sa pozrieme na pravidlá skladania duálnych úloh.

Symetrický duálny problém

Zvážte problém lineárneho programovania s nezápornými premennými a nerovnosťami systému obmedzení nasledujúceho tvaru:
(1.1) ;
(1.2)
Sú tu nejaké čísla. Všetky riadky systému (1.2) sú podpísané nerovnosti.


(2.1) ;
(2.2)
Tu sú všetky riadky systému (2.2) označené nerovnosťami. Matica koeficientov systému obmedzení (2.2) je transponovaná matica systému (1.2). Obsahuje riadky a stĺpce. Duálny problém má premenné. Všetky premenné sú nezáporné.

Pôvodný problém (1) sa často nazýva priamy problém a problém (2) sa nazýva duálny problém. Ak vezmeme problém (2) ako počiatočný, potom problém (2) bude priamym problémom a problém (1) bude duálny. Problémy (1) a (2) sa nazývajú symetrické duálne problémy.

Symetrický duálny problém teda môže byť zostavený len vtedy, ak sú všetky premenné pôvodného problému nezáporné a systém obmedzení neobsahuje rovnosti. Ak sa hľadá maximum účelovej funkcie, potom je potrebné previesť nerovnosti do tvaru . Ak sa hľadá minimum, potom je potrebné previesť nerovnosti do tvaru . Ak chcete zmeniť znamienko, musíte vynásobiť obe strany nerovnosti -1 .

Príklad skladania symetrického duálneho problému


;

Pôvodný problém je problém nájsť minimum. Preto všetky nerovnosti musia mať znaky. Prvá a tretia nerovnosť obsahujú znamienko. Vynásobme ich -1 :




Transponujme túto maticu. To znamená, že prvý riadok napíšeme ako prvý stĺpec, druhý riadok napíšeme ako druhý stĺpec a tretí riadok napíšeme ako tretí stĺpec.

Dvojitý problém má tvar:
;

;

Asymetrický duálny problém

Maximálna výzva

Zvážte problém kanonického maximálneho lineárneho programovania s nezápornými premennými a rovnosťami systému obmedzení:
(3.1) ;
(3.2)
Sú tu nejaké čísla. Všetky riadky systému (3.2) sú rovnaké. Všetky premenné sú nezáporné.

Dvojitý problém má tvar:
(4.1) ;
(4.2)
Tu sú všetky riadky systému (4.2) označené nerovnosťami. Matica koeficientov systému obmedzení (4.2) je transponovanou maticou systému (3.2). Duálny problém má premenné. Premenné môžu byť pozitívne alebo negatívne.

Rozdiel medzi asymetrickou dvojicou úloh (3) a (4) od symetrickej dvojice (1) a (2) je v tom, že systém obmedzení (3.2) obsahuje iba rovnosti a v systéme (4.2) nie sú žiadne podmienky pre nezápornosť premenných.

Minimálna úloha

Teraz zvážte problém kanonického minima lineárneho programovania:
(5.1) ;
(5.2)

Dvojitý problém má tvar:
(6.1) ;
(6.2)

Systém obmedzení (6.2) sa líši od (4.2) tým, že nerovnosti majú znamienka.

Vzťah k symetrickému páru duálnych problémov

Ukážme, že asymetrickú dvojicu úloh (3)-(4) možno získať zo symetrickej dvojice (1)-(2).

Takže máme priamy problém s objektívnou funkciou
(3.1)
a systém obmedzení
(3.2)
Každá rovnosť môže byť reprezentovaná dvoma nerovnosťami:

Nerovnosti so znamienkami násobíme podľa -1 :

Systém obmedzení má nerovnosti.

Pomocou vzorcov (1)-(2) dostaneme dvojitý problém:
;


duálny problém má nezáporné premenné:
.
Je ľahké vidieť, že tieto premenné vstupujú do problému vo forme rozdielov
.

Urobme náhrady
.
Od a , premenné môžu byť kladné alebo záporné.

A dostávame duálny problém (4):
(4.1) ;
(4.2)

Ak vezmeme (4) ako počiatočný problém, potom vykonaním všetkých akcií v opačnom poradí dostaneme duálny problém (3).

Použitím rovnakej metódy je možné získať duálny problém (6) z problému (5) a duálny problém (5) z problému (6).

Zmiešaný problém

Teraz uvažujme o zmiešanom probléme.

Majme priamy problém (1) pre maximum, v systéme obmedzení, ktorého tý riadok je rovnosť. Potom má duálny problém tvar (2) s jednou výnimkou - premenná môže byť kladná alebo záporná. To znamená, že neexistuje žiadne obmedzenie.

To isté sa stane, ak máme priamy problém (2) pre minimum, v systéme obmedzení, ktorého je tý riadok rovnosťou. Duálny problém má tvar (1) s jednou výnimkou - premenná môže byť ľubovoľného znamienka.

Teraz majme priamy problém (1) pre maximum, ale neexistuje žiadne obmedzenie. To znamená, že premenná môže byť kladná alebo záporná. Potom má duálny problém tvar (2) s jednou výnimkou - tý riadok systému obmedzení je rovnosť.

A nakoniec, majme priamy problém (2) pre minimum, ale neexistuje žiadne obmedzenie . Potom má duálny problém tvar (1) s jednou výnimkou - tý riadok systému obmedzení je rovnosť.

To všetko nám umožňuje formulovať pravidlá pre skladanie duálnych problémov.

Pravidlá pre skladanie duálnych úloh

1. Pre pôvodný maximálny problém zredukujeme všetky nerovnosti systému obmedzení do tvaru:
.
Pre pôvodný minimálny problém zredukujeme všetky nerovnosti do tvaru:
.
Ak potrebujete zmeniť znamienko, vynásobte obe strany nerovností -1 .
2. Duálny problém skladáme rovnakým spôsobom ako pri symetrickej dvojici problémov.
3. Ak je v pôvodnej úlohe tý riadok systému obmedzení rovnosť, tak podmienku nezápornosti tej premennej duálnej úlohy preškrtneme.
4. Ak v pôvodnej úlohe neexistuje podmienka nezápornosti pre tú premennú , potom v druhom riadku duálnej úlohy zmeníme znamienko nerovnosti na znamienko rovnosti.

Príklad skladania zmiešaného duálneho problému

Vzhľadom na problém lineárneho programovania:
;

Vytvorte dvojitý problém.

Účelová funkcia má voľný člen 5. Aby sme ju dostali do tvaru (2.1), zavedieme premennú a pridáme rovnosť . Potom bude mať problém podobu:

;

Tento problém je problém nájsť minimum. Preto všetky nerovnosti musia mať znaky. Tretia nerovnosť obsahuje znamienko. Preto to vynásobme -1 :

Prepíšme systém obmedzení, pričom explicitne uvedieme koeficienty premenných:

Koeficientová matica systému obmedzení má tvar:

Transponujme túto maticu. To znamená, že prvý riadok napíšeme ako prvý stĺpec, druhý riadok napíšeme ako druhý stĺpec atď.

Vytvorme duálny problém ako pre symetrický pár.
;

Keďže v pôvodnej úlohe sú 1., 2. a 4. riadok systému obmedzení rovnosti, potom v duálnej úlohe môžu mať premenné , a ľubovoľné znamienko. Jediná nezáporná premenná je . Preto podmienky nezápornosti premenných majú tvar:
.

Keďže v pôvodnej úlohe môžu mať premenné a ľubovoľné znamienka, 3. a 4. riadok systému obmedzení duálnej úlohy sú rovnosti.

Duálny problém má teda tvar:
;

Zo štvrtej rovnice. Nahraďte premennú jej hodnotou a vynásobte tretí riadok -1 .

Je potrebné poznamenať, že metódy riešenia problémov lineárneho programovania zahŕňajú nie na ekonomiku, ale na matematiku a výpočtovú techniku. Zároveň musí ekonóm poskytnúť čo najpohodlnejšie podmienky pre dialóg s príslušným softvérom. Takéto podmienky môžu poskytnúť iba dynamicky sa rozvíjajúce a interaktívne vývojové prostredia, ktoré majú vo svojom arzenáli súbor knižníc nevyhnutných na riešenie takýchto problémov. Jedným z nich je vývojové prostredie softvér je určite Python.

Formulácia problému

Publikácie zvažovali riešenia problémov priamej optimalizácie pomocou metódy lineárneho programovania a navrhli rozumný výber riešiteľa scipy. optimalizovať.

Je však známe, že každý problém lineárneho programovania zodpovedá takzvanému rozlišovanému (duálnemu) problému. V ňom sa oproti priamej úlohe riadky menia na stĺpce, nerovnosti menia znamienko, namiesto maxima sa hľadá minimum (alebo naopak, namiesto minima sa hľadá maximum). Úloha duálna k duálnej je samotná pôvodná úloha.

Riešenie duálneho problému je veľmi dôležité pre analýzu využívania zdrojov. V tejto publikácii bude dokázané, že optimálne hodnoty cieľových funkcií v pôvodnom a duálnom probléme sa zhodujú (t. j. maximum v pôvodnom probléme sa zhoduje s minimom v duálnom probléme).

Optimálne hodnoty materiálových a mzdových nákladov sa budú posudzovať podľa ich príspevku k objektívnej funkcii. Výsledkom budú „objektívne stanovené odhady“ surovín a práce, ktoré sa nezhodujú s trhovými cenami.

Riešenie priameho problému optimálneho výrobného programu

Berúc do úvahy vysoký stupeň matematický tréning Pre veľkú väčšinu používateľov tohto zdroja nebudem uvádzať bilančné rovnice s hornými a dolnými obmedzeniami a zavádzaním ďalších premenných na prechod k rovnosti. Preto okamžite uvediem označenia premenných použitých v riešení:
N – počet druhov vyrobených výrobkov;
m – počet druhov použitých surovín;
b_ub - vektor dostupných zdrojov dimenzie m;
A_ub je matica rozmeru m×N, ktorej každý prvok je spotrebou zdroja typu i na výrobu jednotky produktu typu j;
c je vektor zisku z produkcie jednotky každého druhu produktu;
x – požadované objemy vyrobených produktov každého druhu (optimálny plán výroby) zabezpečujúci maximálny zisk.

Cieľová funkcia
maxF(x)=c×x

Obmedzenia
A×x≤b

Číselné hodnoty premenných:
N=5; m=4; b_ub = ; A_ub = [, , ,]; c = .

Úlohy
1. Nájdite x, aby ste zabezpečili maximálny zisk
2. Nájdite zdroje použité pri vykonávaní kroku 1
3. Pri vykonávaní kroku 1 nájdite zvyšné zdroje (ak nejaké existujú).


Na určenie maxima (štandardne sa určuje minimum, musia byť zapísané koeficienty účelovej funkcie negatívny znak c = [-25, -35,-25,-40,-30] a ignorujte znamienko mínus pred ziskom.

Zápisy používané na zobrazenie výsledkov:
X– pole premenných hodnôt, ktoré poskytujú minimum (maximum) cieľovej funkcie;
ochabnutý– hodnoty dodatočných premenných. Každá premenná zodpovedá obmedzeniu nerovnosti. Premenná hodnota nula znamená, že príslušné obmedzenie je aktívne;
úspech– Pravda, ak sa funkcii podarilo nájsť optimálne riešenie;
postavenie- stav rozhodnutia:
0 – hľadanie optimálneho riešenia bolo úspešne ukončené;
1 – bol dosiahnutý limit počtu iterácií;
2 – problém nemá riešenia;
3 – účelová funkcia nie je obmedzená.
nit– počet vykonaných iterácií.

Výpis riešenia problému priamej optimalizácie

#!/usr/bin/python # -*- kódovanie: utf-8 -*- import scipy zo scipy.optimize import linprog # načítanie knižnice LP c = [-25, -35,-25,-40,-30] # zoznam koeficientov cieľovej funkcie b_ub = # zoznam objemov zdrojov A_ub = [, # matica konkrétnych hodnôt zdrojov​, , ] d=linprog(c, A_ub, b_ub) # hľadanie riešenia pre kľúč,val v d.items(): print(key ,val) # výstup riešenia if key=="x": q=#použité zdroje print("A_ub*x",q) q1= scipy.array(b_ub)-scipy.array (q) #remaining resources print(" b_ub-A_ub*x", q1)


Výsledky riešenia problému
hnida 3
stav 0

úspech Pravda
x [ 0,0, 18,18181818 22,72727273 150. ]
A_ub*x
b_ub-A_ub*x [0. 0. 0. 90.90909091]
zábava -5863,63636364
uvoľnenosť [0. 0. 0. 90,90909091]

závery

  1. Bol nájdený optimálny plán pre typy produktov
  2. Zistilo sa skutočné využitie zdrojov
  3. Našiel sa zvyšok nevyužitého štvrtého typu zdroja [ 0,0 0,0 0,0 90,909]
  4. Výpočty podľa kroku 3 nie sú potrebné, pretože rovnaký výsledok sa zobrazí v premennej „slack“.

Riešenie duálneho problému na optimálnom výrobnom programe

Štvrtý typ zdroja v priamej úlohe nie je plne využitý. Potom sa hodnota tohto zdroja pre podnik ukáže byť nižšia v porovnaní so zdrojmi, ktoré obmedzujú produkciu, a podnik je ochotný zaplatiť vyššiu cenu za získanie zdrojov, ktoré zvyšujú zisky.

Predstavme si nový účel pre požadovanú premennú x ako nejakú „tieňovú“ cenu, ktorá určuje hodnotu daného zdroja vo vzťahu k zisku z predaja vyrobených produktov.

C – vektor dostupných zdrojov;
b_ub je vektor zisku z produkcie jednotky každého typu produktu;
A_ub_T – transponovaná matica A_ub.

Cieľová funkcia
minF(x)=cxx

Obmedzenia
A_ub_T ×x≥ b_ub

Číselné hodnoty a vzťahy pre premenné:
c =; A_ub_T transponovať (A_ub); b_ub = .

Úloha:
Nájdite x označujúce hodnotu pre výrobcu každého typu zdroja.

Vlastnosti riešenia s knižnicou scipy. optimalizovať
Na nahradenie obmedzení zhora obmedzeniami zdola je potrebné vynásobiť obe časti obmedzenia mínusom jedna – A_ub_T ×x≥ b_ub... Za týmto účelom zapíšte pôvodné údaje v tvare: b_ub = [-25, -35,-25,-40,-30]; A_ub_T =- scipy.transpose(A_ub).

Výpis riešenia problému duálnej optimalizácie

#!/usr/bin/python # -*- kódovanie: utf-8 -*- import scipy zo scipy.optimize import linprog A_ub = [, , , ] c= b_ub = [-25, -35,-25,- 40,-30] A_ub_T =-scipy.transpose(A_ub) d=linprog(c, A_ub_T, b_ub) pre kľúč,hodnota v d.items(): print(kľúč,hodnota)


Výsledky riešenia problému
hnida 7
správa Optimalizácia bola úspešne ukončená.
zábavné 5863,63636364
x [ 2,27272727 1,81818182 6,36363636 0. ]
uvoľnenie [5,45454545 2,27272727 0. 0. 0. ]
stav 0
úspech Pravda

závery

Tretí typ zdroja má preto pre výrobcu najväčšiu hodnotu tento typ najprv treba nakúpiť zdroje, potom prvý a druhý typ. Štvrtý typ zdroja má pre výrobcu nulovú hodnotu a kupuje sa ako posledný.

Výsledky porovnania priamych a duálnych problémov

  1. Dvojitý problém rozširuje možnosti produktového plánovania, ale pomocou scipy. optimalizácia je riešená v dvojnásobnom počte priamych iterácií.
  2. Premenná slack zobrazuje informácie o aktivite obmedzení vo forme nerovností, ktoré je možné použiť napríklad na analýzu bilancií surovín.
  3. Priamy problém je problém maximalizácie a duálny problém je problém minimalizácie a naopak.
  4. Koeficienty účelovej funkcie v priamom probléme sú obmedzeniami v duálnom probléme.
  5. Obmedzenia v priamom probléme sa stávajú koeficientmi účelovej funkcie v duálnom.
  6. Znaky nerovností v obmedzeniach sú obrátené.
  7. Matica systému rovnosti je transponovaná.
Odkazy