Hľadanie riešenia metódou simplex excel. Simplexná metóda riešenia úloh lineárneho programovania. Riešenie problému lineárneho programovania pomocou doplnku Hľadať riešenie

Nájsť riešenie je Doplnok Microsoftu Excel, ktorý môžete použiť na nájdenie optimálne riešenieúlohy s prihliadnutím definované užívateľom obmedzenia.

Zvážime nájdenie riešenia v (tento doplnok prešiel niekoľkými zmenami v porovnaní s predošlá verzia V .
V tomto článku sa pozrieme na:

• vytvorenie optimalizačného modelu na hárku MS EXCEL
• nastavenie Hľadanie riešenia;
• jednoduchý príklad (lineárny model).

Inštalácia Hľadajte riešenie

Tím Hľadanie riešenia je v skupine Analýza na karte Údaje.

Ak tým Hľadanie riešenia v skupine Analýza nie je k dispozícii, musíte povoliť doplnok s rovnakým názvom.
Pre to:

• Na karte Súbor vybrať tím možnosti a potom kategóriu Doplnky;
• V teréne Kontrola vyberte hodnotu Excel doplnky a stlačte tlačidlo Choď;
• V teréne Dostupné doplnky začiarknite políčko vedľa položky Hľadanie riešenia a kliknite na tlačidlo OK.

Poznámka. okno Doplnky dostupné aj na karte Vývojár. Ako povoliť túto kartu.

Po stlačení tlačidla Hľadanie riešenia v skupine analýza, otvorí sa jej dialógové okno .

Pri častom používaní Hľadanie riešenia je pohodlnejšie ho spustiť z Panela rýchly prístup a nie na karte Údaje. Ak chcete umiestniť tlačidlo na Panel, kliknite naň pravým tlačidlom myši a vyberte Pridať na panel s nástrojmi Rýchly prístup.

O modeloch

Táto časť je určená pre tých, ktorí sa ešte len zoznamujú s konceptom modelu optimalizácie.

Poradenstvo. Pred použitím Hľadanie riešenia Dôrazne odporúčame preštudovať si literatúru o riešení optimalizačných problémov a zostavovaní modelov.

Nižšie je uvedený malý vzdelávací program na túto tému.

Nadstavba Hľadanie riešenia pomáha určiť Najlepšia cesta robiť niečo:

• „Niečo“ môže zahŕňať vyčlenenie peňazí na investície, naloženie skladu, dodanie tovaru alebo inú predmetnú činnosť, pri ktorej je potrebné nájsť optimálne riešenie.
• „Najlepší spôsob“ alebo optimálne riešenie v tomto prípade znamená: maximalizácia zisku, minimalizácia nákladov, dosiahnutie najlepšia kvalita atď.

Tu je niekoľko typických príkladov problémov s optimalizáciou:

• Určte, pri ktorom je maximálny príjem z predaja vyrobených výrobkov;
• Určte pri ktorom celkové náklady náklady na dopravu by boli minimálne;
• Zistite, že celkové výrobné náklady by boli minimálne;
• Určite minimálny termín dokončenia všetkých projektových prác (kritická cesta).

Na formalizáciu danej úlohy je potrebné vytvoriť model, ktorý by odrážal základné charakteristiky predmetná oblasť(a nezahŕňa menšie podrobnosti). Upozorňujeme, že model je optimalizovaný Hľadanie riešenia iba jedným ukazovateľom(tento optimalizovaný indikátor sa nazýva cieľová funkcia).
V M.S. Model EXCEL je zbierka vzájomne prepojených vzorcov, ktoré používajú premenné ako argumenty. Tieto premenné môžu zvyčajne akceptovať iba platné hodnoty, s výhradou obmedzení špecifikovaných používateľom.
Hľadanie riešenia vyberie také hodnoty týchto premenných (s výhradou špecifikovaných obmedzení), aby cieľová funkcia bola maximálna (minimálna) alebo rovná danej číselnej hodnote.

Poznámka. V najjednoduchšom prípade možno model opísať pomocou jediného vzorca. Niektoré z týchto modelov je možné optimalizovať pomocou nástroja. Pred prvým stretnutím Hľadanie riešenia Má zmysel najprv podrobne pochopiť súvisiaci nástroj.
Hlavné rozdiely Výber parametrov od Hľadanie riešenia:

• Výber parametrov funguje len s modelmi s jednou premennou;
• nie je možné nastaviť obmedzenia na premenné;
• nie je určené maximum alebo minimum účelovej funkcie, ale jej rovnosť s určitou hodnotou;
• funguje efektívne len vtedy lineárne modely, v nelineárnom prípade nájde lokálne optimum (najbližšie k pôvodná hodnota premenná).

Príprava optimalizačného modelu v MS EXCEL

Hľadanie riešenia optimalizuje hodnotu cieľovej funkcie. Objektívna funkcia je vzorec, ktorý vracia jednu hodnotu v bunke. Výsledok vzorca by mal závisieť od premenných modelu (nie nevyhnutne priamo, ale prostredníctvom výsledku výpočtu iných vzorcov).
Modelové obmedzenia môžu byť uložené tak na rozsah variácií samotných premenných, ako aj na výsledky výpočtu iných vzorcov modelu, ktoré závisia od týchto premenných.
Všetky bunky obsahujúce modelové premenné a obmedzenia musia byť umiestnené iba na jednom hárku zošita. Zadávanie parametrov v dialógovom okne Hľadanie riešenia možné len z tohto listu.
Objektívna funkcia(bunka) sa musí nachádzať aj na tomto hárku. Medzivýpočty (vzorce) však možno umiestniť na iné listy.

Poradenstvo. Usporiadajte údaje modelu tak, aby na jednom hárku MS EXCEL bol iba jeden model. V opačnom prípade budete musieť na vykonávanie výpočtov neustále ukladať a načítavať nastavenia Hľadanie riešenia(Pozri nižšie).

Predstavme si algoritmus na prácu s Hľadanie riešenia, ktorý odporúčajú samotní vývojári (www.solver.com):

• Definujte bunky s modelovými premennými (rozhodovacie premenné);
• Vytvorte v bunke vzorec, ktorý vypočíta účelovú funkciu vášho modelu;
• Vytvorte vzorce v bunkách, ktoré vypočítajú hodnoty v porovnaní s obmedzeniami ( na ľavej strane výrazy);
• Pomocou dialógového okna Hľadanie riešenia zadajte odkazy na bunky obsahujúce premenné, na cieľovú funkciu, na vzorce pre obmedzenia a hodnoty samotných obmedzení;
• Bežať Hľadanie riešenia nájsť optimálne riešenie.

Prejdime si všetky tieto kroky na jednoduchom príklade.

Jednoduchý príklad použitia Hľadanie riešenia

Kontajner je potrebné naložiť tovarom tak, aby hmotnosť kontajnera bola maximálna. Kontajner má objem 32 metrov kubických. Položky sú uložené v škatuliach a prepravkách. Každá krabica s tovarom váži 20 kg, jej objem je 0,15 m3. Box - 80 kg a 0,5 m3, resp. Je to potrebné Celkom bolo tam minimálne 110 kontajnerov.

Tieto modely organizujeme nasledujúcim spôsobom(pozri vzorový súbor).

Premenné modelu (množstvo každého typu kontajnera) sú zvýraznené zelenou farbou.
Cieľová funkcia (celková hmotnosť všetkých krabíc a prepraviek) je vyznačená červenou farbou.
Obmedzenia modelu: minimálne množstvo nádob (>=110) a celkový objem (<=32) – синим.
Účelová funkcia sa vypočíta pomocou vzorca =SUMPRODUCT(B8:C8,B6:C6) je celková hmotnosť všetkých krabíc a prepraviek naložených do kontajnera.
Podobne vypočítame celkový objem - =SUMPRODUCT(B7:C7,B8:C8). Tento vzorec je potrebný na nastavenie limitu celkového objemu krabíc a prepraviek (<=32).
Aby sme nastavili obmedzenie modelu, vypočítame celkový počet kontajnerov =SUM(B8:C8) .
Teraz pomocou dialógového okna Hľadanie riešenia Zadajte odkazy na bunky obsahujúce premenné, cieľovú funkciu, vzorce pre obmedzenia a hodnoty samotných obmedzení (alebo odkazy na zodpovedajúce bunky).
Je jasné, že počet krabíc a prepraviek musí byť celé číslo - to je ďalšie obmedzenie modelu.

Po stlačení tlačidla Nájsť riešenie nájdu sa také počty krabíc a prepraviek, pri ktorých je ich celková hmotnosť (objektívna funkcia) maximálna a zároveň sú splnené všetky stanovené obmedzenia.

Zhrnutie

V skutočnosti je hlavným problémom pri riešení optimalizačných problémov pomocou Hľadanie riešenia Nie sú dôležité jemnosti nastavenia tohto analytického nástroja, ale správnosť zostavenia modelu adekvátneho danej úlohe. Preto sa v ďalších článkoch zameriame špeciálne na budovanie modelov, pretože „krivý“ model je často dôvodom neschopnosti nájsť riešenie pomocou Hľadanie riešenia.
Často je jednoduchšie prezrieť si niekoľko typických problémov, nájsť medzi nimi podobný a potom prispôsobiť tento model svojej úlohe.
Riešenie klasických optimalizačných problémov pomocou Hľadanie riešenia zvážil .

Riešiteľ nenašiel vhodné riešenie

Táto správa sa zobrazí, keď Hľadanie riešenia nepodarilo nájsť kombinácie premenných hodnôt, ktoré súčasne spĺňajú všetky obmedzenia.
Ak používate Simplexná metóda riešenia lineárnych úloh, potom si môžete byť istí, že v skutočnosti neexistuje žiadne riešenie.
Ak na riešenie nelineárnych problémov používate metódu, ktorá vždy začína počiatočnými hodnotami premenných, môže to tiež znamenať, že možné riešenie je ďaleko od týchto počiatočných hodnôt. Ak bežíte Hľadanie riešenia s inými počiatočnými hodnotami premenných, možno sa nájde riešenie.
Predstavme si, že pri riešení problému pomocou nelineárnej metódy boli bunky s premennými ponechané prázdne (t.j. počiatočné hodnoty sú 0) a Hľadanie riešenia nenašiel riešenie. To neznamená, že v skutočnosti neexistuje riešenie (aj keď to tak môže byť). Teraz, na základe výsledkov určitého odborného posúdenia, zadáme do buniek s premennými ďalšiu množinu hodnôt, ktorá je podľa vás blízka optimálnej (hľadanej). V tomto prípade, Hľadanie riešenia dokáže nájsť riešenie (ak nejaké skutočne existuje).

Poznámka. O vplyve nelinearity modelu na výsledky výpočtov si môžete prečítať v poslednej časti článku.

V každom prípade (lineárne alebo nelineárne), musíte najprv analyzovať model z hľadiska konzistencie obmedzení, teda podmienok, ktoré nemôžu byť splnené súčasne. Najčastejšie je to spôsobené nesprávnou voľbou pomeru (napr.<= вместо >=) alebo limitná hodnota.
Ak je napríklad vo vyššie diskutovanom príklade hodnota maximálneho objemu nastavená na 16 m3 namiesto 32 m3, potom bude toto obmedzenie v rozpore s obmedzením minimálneho počtu miest na sedenie (110), pretože minimálny počet miest zodpovedá objemu rovnajúcemu sa 16,5 m3 (110 * 0,15, kde 0,15 je objem boxu, t. j. najmenšej nádoby). Nastavením limitu maximálneho objemu na 16 m3, Hľadanie riešenia nenájde riešenie.

S limitom 17 m3 Hľadanie riešenia nájde riešenie.

Niektoré nastavenia Hľadanie riešenia

Metóda riešenia
Vyššie diskutovaný model je lineárny, t.j. účelová funkcia (M je celková hmotnosť, ktorá môže byť maximálna) je vyjadrená nasledujúcou rovnicou M=a1*x1+a2*x2, kde x1 a x2 sú modelové premenné (počet škatúľ a zásuviek), a1 a a2 sú ich váhy. V lineárnom modeli musia byť obmedzenia tiež lineárnymi funkciami premenných. V našom prípade je objemové obmedzenie V=b1*x1+b2*x2 vyjadrené aj lineárnou závislosťou. Je zrejmé, že ďalšie obmedzenie – Maximálny počet kontajnerov (n) – je tiež lineárne x1+x2 Lineárne úlohy sa zvyčajne riešia pomocou Simplexovej metódy. Výberom tejto metódy riešenia v okne Hľadanie riešenia Môžete tiež skontrolovať linearitu samotného modelu. V prípade nelineárneho modelu dostanete nasledujúcu správu:

V tomto prípade je potrebné zvoliť metódu riešenia nelineárneho problému. Príklady nelineárnych závislostí: V=b1*x1*x1; V=b1*x1^0,9; V=b1*x1*x2, kde x je premenná a V je účelová funkcia.

Tlačidlá Pridať, Upraviť, Vymazať
Tieto tlačidlá vám umožňujú pridávať, upravovať a odstraňovať obmedzenia modelu.

Tlačidlo reštart
Ak chcete odstrániť všetky nastavenia Hľadanie riešenia kliknite na tlačidlo Resetovať– dialógové okno sa vymaže.

Táto možnosť je vhodná pri použití rôznych možností obmedzenia. Pri ukladaní parametrov modelu (tlačidlo Načítať/Uložiť, potom kliknite na tlačidlo Uložiť) navrhuje sa vybrať hornú bunku rozsahu (stĺpca), v ktorej bude umiestnený: odkaz na cieľovú funkciu, odkazy na bunky s premennými, obmedzenia a parametre metód riešenia (dostupné cez tlačidlo možnosti). Pred uložením sa uistite, že tento rozsah neobsahuje údaje o modeli.
Ak chcete načítať uložené parametre, najskôr stlačte tlačidlo Načítať/Uložiť a potom v zobrazenom dialógovom okne tlačidlo Stiahnuť ▼ a potom zadajte rozsah buniek obsahujúcich predtým uložené nastavenia (nie je možné zadať iba hornú bunku). Kliknite na tlačidlo OK. Potvrďte resetovanie aktuálnych hodnôt parametrov úlohy a ich nahradenie novými.

Presnosť
Pri vytváraní modelu má výskumník na začiatku určitý odhad rozsahov variácií cieľovej funkcie a premenných. Vzhľadom na výpočty v MS EXCEL sa odporúča, aby tieto rozsahy variácií boli výrazne vyššie ako presnosť výpočtu (zvyčajne sa nastavuje od 0,001 do 0,000001). Spravidla sa údaje v modeli normalizujú tak, že rozsahy variácií cieľovej funkcie a premenných sú v rozsahu 0,1 - 100 000, samozrejme, všetko závisí od konkrétneho modelu, ale ak sa vaše premenné zmenia o viac ako 5-6 rádov, potom by ste možno mali model „zdrsniť“, napríklad pomocou logaritmickej operácie.

. Algoritmus simplexnej metódy

Príklad 5.1. Vyriešte nasledujúci problém lineárneho programovania pomocou simplexnej metódy:

Riešenie:

ja iterácia:

x3, x4, x5, x6 x1,x2. Vyjadrime základné premenné z hľadiska voľných:

Zredukujme účelovú funkciu na nasledujúci tvar:

Na základe získaného problému vytvoríme počiatočnú simplexnú tabuľku:

Tabuľka 5.3

Originálny simplexný stôl

				Hodnotiace vzťahy

Podľa definície základného riešenia sa voľné premenné rovnajú nule a hodnoty základných premenných sa rovnajú zodpovedajúcim hodnotám voľných čísel, t.j.:

3. fáza: kontrola kompatibility systému obmedzení PAP.

Pri tejto iterácii (v tabuľke 5.3) nie je identifikované znamienko nekonzistentnosti systému obmedzení (znamienko 1) (t. j. neexistuje riadok so záporným voľným číslom (okrem riadku účelovej funkcie), v ktorom by nebolo byť aspoň jeden záporný prvok (t. j. záporný koeficient pre voľnú premennú)).

Pri tejto iterácii (v tabuľke 5.3) nebolo identifikované znamienko neohraničenosti účelovej funkcie (znamienko 2) (t. j. v riadku účelovej funkcie nie je stĺpec so záporným prvkom (okrem stĺpca voľných čísel). ) v ktorom by nebol aspoň jeden pozitívny prvok) .

Keďže nájdené základné riešenie neobsahuje negatívne zložky, je prípustné.

6. fáza: kontrola optimálnosti.

Nájdené základné riešenie nie je optimálne, keďže podľa kritéria optimality (znamienko 4) by v riadku účelovej funkcie nemali byť žiadne záporné prvky (voľné číslo tohto riadku sa pri posudzovaní tohto kritéria neberie do úvahy). Preto podľa algoritmu simplexovej metódy prejdeme do fázy 8.

Keďže nájdené základné riešenie je prípustné, budeme hľadať rozlišovací stĺpec podľa nasledujúcej schémy: určíme stĺpce so zápornými prvkami v riadku účelovej funkcie (okrem stĺpca voľných čísel). Podľa tabuľky 5.3 existujú dva takéto stĺpce: stĺpec „ x1"a stĺpec" x2" Z takýchto stĺpcov sa vyberie ten, ktorý obsahuje najmenší prvok v riadku cieľovej funkcie. Ona bude tá povoľná. stĺpec " x2" obsahuje najmenší prvok (–3) v porovnaní so stĺpcom " x1

Na určenie rozlišovacej čiary nájdeme kladné odhadované pomery voľných čísel k prvkom rozlišovacieho stĺpca, pričom čiara, ktorá zodpovedá najmenšiemu kladnému hodnotiacemu pomeru, sa považuje za vyriešenú.

Tabuľka 5.4

Originálny simplexný stôl

V tabuľke 5.4 najmenší kladný hodnotiaci vzťah zodpovedá riadku „ x5“, preto bude prípustné.

Prvok umiestnený v priesečníku povoľujúceho stĺpca a povoľujúceho riadku je akceptovaný ako povoľujúci. V našom príklade je to prvok, ktorý sa nachádza na priesečníku čiary “ x5"a stĺpce" x2».

Rozlišovací prvok zobrazuje jednu bázu a jednu voľnú premennú, ktoré je potrebné vymeniť v simplexnej tabuľke, aby ste mohli prejsť na nové „vylepšené“ základné riešenie. V tomto prípade ide o premenné x5 A x2, v novej simplexnej tabuľke (tabuľka 5.5) ich prehodíme.

9.1. Transformácia rozlišovacieho prvku.

Prvok rozlíšenia v tabuľke 5.4 sa prevedie takto:

Výsledný výsledok zadáme do podobnej bunky v tabuľke 5.5.

9.2. Konverzia reťazca rozlíšenia.

Prvky rozlišovacieho riadku tabuľky 5.4 rozdelíme rozlišovacím prvkom tejto simplexnej tabuľky, výsledky sa zmestia do podobných buniek novej simplexnej tabuľky (tabuľka 5.5). Transformácie prvkov rozlišovacieho reťazca sú uvedené v tabuľke 5.5.

9.3. Konverzia stĺpca rozlíšenia.

Prvky stĺpca rozlíšenia tabuľky 5.4 vydelíme prvkom rozlíšenia tejto simplexnej tabuľky a výsledok sa vezme s opačným znamienkom. Získané výsledky zapadajú do podobných buniek novej simplexnej tabuľky (tabuľka 5.5). Transformácie prvkov rozlišovacej kolóny sú uvedené v tabuľke 5.5.

9.4. Transformácia zostávajúcich prvkov simplexnej tabuľky.

Transformácia zostávajúcich prvkov simplexnej tabuľky (t. j. prvkov nenachádzajúcich sa v rozlišovacom riadku a rozlišovacom stĺpci) sa vykonáva podľa pravidla „obdĺžnik“.

Zvážte napríklad transformáciu prvku umiestneného na priesečníku čiary " x3" a stĺpce "", podmienečne to označíme " x3" V tabuľke 5.4 mentálne nakreslíme obdĺžnik, ktorého jeden vrchol sa nachádza v bunke, ktorej hodnotu transformujeme (t. j. v bunke „ x3") a druhý (diagonálny vrchol) je v bunke s rozlišovacím prvkom. Ďalšie dva vrcholy (druhej uhlopriečky) sú jednoznačne určené. Potom transformovaná hodnota bunky " x3" sa bude rovnať predchádzajúcej hodnote tejto bunky mínus zlomok, v menovateli ktorého je rozlišovací prvok (z tabuľky 5.4) a v čitateli súčin dvoch ďalších nepoužitých vrcholov, t.j.:

« x3»: .

Hodnoty ostatných buniek sa prevedú podobne:

« x3 x1»: ;

« x4»: ;

« x4 x1»: ;

« x6»: ;

« x6 x1»: ;

«»: ;

« x1»: .

V dôsledku týchto transformácií bola získaná nová simplexná tabuľka (tabuľka 5.5).

II iterácia:

Fáza 1: zostavenie simplexnej tabuľky.

Tabuľka 5.5

Simplexný stôlII iterácií

				Odhadovaný vzťah

2. fáza: stanovenie základného roztoku.

V dôsledku simplexných transformácií sa získalo nové základné riešenie (tabuľka 5.5):

Ako vidíte, pri tomto základnom riešení je hodnota účelovej funkcie = 15, čo je väčšie ako pri predchádzajúcom základnom riešení.

Nekonzistentnosť systému obmedzení podľa znaku 1 v tabuľke 5.5 nebola zistená.

4. fáza: kontrola ohraničenosti účelovej funkcie.

Neohraničenosť účelovej funkcie v súlade s kritériom 2 v tabuľke 5.5 nie je odhalená.

5. etapa: kontrola prípustnosti nájdeného základného riešenia.

Nájdené základné riešenie podľa kritéria 4 nie je optimálne, keďže riadok účelovej funkcie simplexovej tabuľky (tabuľka 5.5) obsahuje záporný prvok: –2 (voľné číslo tohto riadku sa pri uvažovaní neberie do úvahy charakteristika). Preto prejdeme do fázy 8.

8. fáza: určenie rozlišovacieho prvku.

8.1. Definícia stĺpca rozlíšenia.

Nájdené základné riešenie je prijateľné, určíme stĺpce so zápornými prvkami v riadku účelovej funkcie (okrem stĺpca voľných čísel). Podľa tabuľky 5.5 existuje iba jeden takýto stĺpec: „ x1" Preto to akceptujeme ako povolené.

8.2. Definícia povoľovacieho reťazca.

Podľa získaných hodnôt kladných hodnotiacich vzťahov v tabuľke 5.6 je minimom vzťah zodpovedajúci riadku „ x3" Preto to akceptujeme ako povolené.

Tabuľka 5.6

Simplexný stôlII iterácií

				Odhadovaný vzťah
				3/1 = 3 – min

Fáza 9: transformácia simplexnej tabuľky.

Transformácie simplexnej tabuľky (tabuľka 5.6) sa vykonávajú rovnakým spôsobom ako v predchádzajúcej iterácii. Výsledky transformácií prvkov simplexnej tabuľky sú uvedené v tabuľke 5.7.

III iterácia

Na základe výsledkov simplexných transformácií predchádzajúcej iterácie zostavíme novú simplexnú tabuľku:

Tabuľka 5.7

Simplexný stôlIII iterácií

				Odhadovaný vzťah

2. fáza: stanovenie základného roztoku.

V dôsledku simplexných transformácií sa získalo nové základné riešenie (tabuľka 5.7):

3. fáza: kontrola zlučiteľnosti systému obmedzení.

Nekonzistentnosť systému obmedzení v súlade s kritériom 1 v tabuľke 5.7 nebola zistená.

4. fáza: kontrola ohraničenosti účelovej funkcie.

Neohraničenosť účelovej funkcie v súlade s kritériom 2 v tabuľke 5.7 nie je odhalená.

5. etapa: kontrola prípustnosti nájdeného základného riešenia.

Nájdené základné riešenie podľa kritéria 3 je prijateľné, pretože neobsahuje negatívne zložky.

6. fáza: kontrola optimálnosti nájdeného základného riešenia.

Nájdené základné riešenie v súlade s kritériom 4 nie je optimálne, pretože riadok účelovej funkcie simplexovej tabuľky (tabuľka 5.7) obsahuje záporný prvok: –3 (voľné číslo tohto riadku sa pri uvažovaní neberie do úvahy). charakteristika). Preto prejdeme do fázy 8.

8. fáza: určenie rozlišovacieho prvku.

8.1. Definícia stĺpca rozlíšenia.

Nájdené základné riešenie je prijateľné, určíme stĺpce so zápornými prvkami v riadku účelovej funkcie (okrem stĺpca voľných čísel). Podľa tabuľky 5.7 existuje iba jeden takýto stĺpec: „ x5" Preto to akceptujeme ako povolené.

8.2. Definícia povoľovacieho reťazca.

Podľa získaných hodnôt kladných hodnotiacich vzťahov v tabuľke 5.8 je minimom vzťah zodpovedajúci riadku „ x4" Preto to akceptujeme ako povolené.

Tabuľka 5.8

Simplexný stôlIII iterácií

				Odhadovaný vzťah
				5/5 = 1 – min

Fáza 9: transformácia simplexnej tabuľky.

Transformácie simplexnej tabuľky (tabuľka 5.8) sa vykonávajú rovnakým spôsobom ako v predchádzajúcej iterácii. Výsledky transformácií prvkov simplexnej tabuľky sú uvedené v tabuľke 5.9.

IV iterácia

1. etapa: konštrukcia nového simplexného stola.

Na základe výsledkov simplexných transformácií predchádzajúcej iterácie zostavíme novú simplexnú tabuľku:

Tabuľka 5.9

Simplexný stôlIV iterácií

				Odhadovaný vzťah
			–(–3/5)=3/5
			–(1/5)=–1/5
			–(9/5)=–9/5
			–(–3/5)=3/5

2. fáza: stanovenie základného roztoku.

V dôsledku simplexných transformácií sa získalo nové základné riešenie podľa tabuľky 5.9, riešenie je nasledovné:

3. fáza: kontrola zlučiteľnosti systému obmedzení.

Nekonzistentnosť systému obmedzení podľa znaku 1 v tabuľke 5.9 nebola zistená.

4. fáza: kontrola ohraničenosti účelovej funkcie.

Neohraničenosť účelovej funkcie v súlade s kritériom 2 v tabuľke 5.9 nie je odhalená.

5. etapa: kontrola prípustnosti nájdeného základného riešenia.

Nájdené základné riešenie podľa kritéria 3 je prijateľné, pretože neobsahuje negatívne zložky.

6. fáza: kontrola optimálnosti nájdeného základného riešenia.

Nájdené základné riešenie podľa znaku 4 je optimálne, keďže v riadku účelovej funkcie simplexnej tabuľky (tabuľka 5.9) nie sú žiadne negatívne prvky (voľné číslo tohto riadku sa pri posudzovaní tohto znaku neberie do úvahy) .

7. fáza: kontrola alternatívnosti riešenia.

Nájdené riešenie je jedinečné, keďže v riadku účelovej funkcie (tabuľka 5.9) nie sú žiadne nulové prvky (voľné číslo tohto riadku sa pri posudzovaní tejto charakteristiky neberie do úvahy).

odpoveď: optimálna hodnota objektívnej funkcie uvažovaného problému =24, ktorá sa dosiahne pri.

Príklad 5.2. Vyriešte vyššie uvedený problém lineárneho programovania za predpokladu, že cieľová funkcia je minimalizovaná:

Riešenie:

ja iterácia:

Fáza 1: vytvorenie počiatočnej simplexnej tabuľky.

Pôvodný problém lineárneho programovania je uvedený v štandardnej forme. Dostaňme to do kanonickej podoby zavedením ďalšej nezápornej premennej do každého z obmedzení nerovnosti, t.j.

Vo výslednej sústave rovníc berieme ako povolené (základné) premenné x3, x4, x5, x6, potom budú voľné premenné x1,x2. Vyjadrime základné premenné v termínoch voľných.

Optimalizačné modely sa používajú na nájdenie odpovedí na otázky ako:

• Ako vytvoriť rozvrh pre zamestnancov call centra tak, aby vyhovoval ich požiadavkám na dovolenku, vyvážil nadčasy a eliminoval nepretržité povinnosti?
• Ktoré príležitosti na ťažbu ropy by ste mali využiť, aby ste maximalizovali svoj príjem a zároveň mali všetky riziká pod kontrolou?
• Kedy by sa mali zadať nové objednávky v Číne a ako by sa mali doručiť, aby sa minimalizovali náklady a uspokojil očakávaný dopyt?

Stiahnite si poznámku vo formáte alebo formáte, príklady vo formáte

Cieľom optimalizácie je vždy „maximalizácia“ alebo „minimalizácia“. Najbežnejšou a dobre pochopenou formou matematickej optimalizácie je lineárne programovanie, tajný vývoj sovietskych inžinierov koncom 30. rokov 20. storočia, ktorý sa stal populárnym počas druhej svetovej vojny. Mimochodom, slovo „programovanie“ v tejto fráze je pozostatkom vojenskej terminológie tej doby a nemá nič spoločné s počítačovým programovaním.

Začnime obľúbeným príkladom ekonómov – pištole a maslo. Píše sa rok 1941, ste majiteľom francúzskej mliečnej farmy. Cez deň dojíte kravy a vyrábate maslo, v noci skladáte automaty. Vaším cieľom je maximálny zisk, aby ste vyrábali stroje čo najdlhšie. Od sprostredkovateľa z Odporu dostávate 195 peňažných jednotiek za každý stroj (aby sme neobťažovali Excel s neexistujúcimi frankami, predpokladajme, že ide o doláre). Za každý barel ropy na trhu dostanete 150 dolárov.

Podmienky a obmedzenia. Cena jedného barelu ropy je 100 USD a jeden stroj je 150 USD. Mesačný rozpočet na výrobu - 1800 dolárov. Svoje produkty skladujete v pivnici s rozlohou 21 metrov kubických. Stroj zaberá ½ m 3, barel ropy 1 ½ m 3. Koľko automatov a barelov ropy potrebujete predať za mesiac, aby ste dosiahli maximálny zisk?

Lineárny program je definovaný ako súbor riešení potrebných na optimalizáciu objektu vo svetle niektorých podmienok, pričom objekt aj podmienky sú lineárne. Môžete sčítať, odčítať a násobiť podľa konštánt, ale nemôžete použiť na riešenie nelineárne funkcie, ako je násobenie premenných (nedá sa násobiť maslom), kvadratúra alebo logické cykly, ako napríklad IF.

Znázornime rozsahy prijateľných hodnôt graficky. Po prvé, počet zbraní a ropných sudov nesmie byť záporný. Po druhé, maximum, ktoré môžete vyprodukovať, je 1800 USD/150 USD = 12 strojov alebo 1800 USD/100 USD = 18 barelov ropy (obr. 1). Všeobecný názov tohto trojuholníka je polytop– postava s plochými stranami (napríklad diamant). Po tretie, do suterénu sa zmestí maximálne 21/(½) = 42 strojov alebo 21/(1½) = 14 barelov ropy (obr. 2).

Aby sme našli ideálny pomer strojov a sudov, zavedieme do problému koncept riadky úrovne funkcií. Takáto línia v modeli optimalizácie obsahuje hodnoty, ktoré prinášajú rovnaký zisk. Hladinovú čiaru možno špecifikovať rovnicou:

(195 – 150) * N strojov + (150 – 100) * N barelov ropy = C,

kde C je konštanta.

Napríklad pri C = 450 bude čiara prechádzať súradnicami (0;10) a (9;0). Graficky je myšlienka maximalizácie zisku realizovaná posúvaním čiary úrovne rovnobežne so sebou v smere zvyšovania hodnôt pozdĺž osi X a Y (obr. 3). Je zvláštne, že pre polytop leží optimum vždy v jednom z vrcholov (alebo neexistuje žiadne jedinečné riešenie). Na tejto vlastnosti je založený algoritmus simplexnej metódy. Riešenie úlohy v Exceli začína vytvorením modelovej oblasti (obr. 4). Vzorec pre účelovú funkciu v bunke B1 = SUMPRODUCT(C4:D4;C10:D10).

Ryža. 3. Hladinová línia a funkcia pre optimalizáciu zisku: a) nejaká ľubovoľná počiatočná pozícia; b) rovná čiara v optimálnej polohe

Všetko je pripravené na stlačenie tlačidla. ÚDAJE –> Hľadanie riešenia. (Ak toto tlačidlo nevidíte, nainštalujte si doplnok Find Solution; pozrite si kapitolu 1). V okne, ktoré sa otvorí Možnosti vyhľadávania riešení nastavte zvýraznené možnosti a stlačte Nájsť riešenie.

Ryža. 5. Okno Hľadanie riešenia

Excel aktualizuje hárok a pridá doň výsledky výpočtu (obr. 6).

Čo sa stane, ak pridáte nelinearitu? Povedzme, že váš sprostredkovateľ ponúka 500 USD, ak je počet strojov za mesiac vyšší ako 5. Stačí pridať funkciu IF do bunky zisku (B1). Teraz funkcia cieľa vyzerá takto: =SUMPRODUCT(C4:D4,C10:D10)+IF(C4>5500,0). Kliknite Hľadanie riešenia. Zlyhanie, Excel hlási chybu – nie sú splnené podmienky linearity (obrázok 7).

Môžete vyskúšať evolučný algoritmus, ktorý najlepšie funguje s nelineárnymi modelmi a nemá prakticky žiadne obmedzenia na výber funkcií. Práca evolučného algoritmu v niektorých ohľadoch opakuje princípy práce biologickej evolúcie:

• generuje súbor počiatočných riešení (niečo ako genetický fond) s rôznym stupňom pravdepodobnosti;
• každé rozhodnutie má určitú úroveň spôsobilosti na prežitie;
• roztoky sa šíria krížovým prenosom, to znamená, že ich zložky sa vyberú z dvoch alebo troch existujúcich riešení a potom sa kombinujú;
• existujúce riešenia sa menia na nové;
• prebieha lokálne vyhľadávanie, počas ktorého sa generujú nové riešenia v blízkosti aktuálne najlepšieho riešenia v populácii;
• dochádza k selekcii: náhodne vybrané neúspešné kandidátske riešenia sú vyhodené z genetického fondu.

Bohužiaľ, stále existujú určité problémy s evolučným algoritmom:

• Prevádzková doba je výrazne dlhšia ako pri simplexnej metóde
• Neexistuje žiadna záruka, že nájde optimálne riešenie. Všetko, čo dokáže, je kontrolovať najlepšie riešenie v populácii, kým nevyprší čas, alebo kým sa populácia nezmení natoľko, aby pokračovala, alebo kým násilne nezastavíte Hľadanie riešenia stlačením tlačidla ESC.
• Evolučné hľadanie riešenia funguje pomerne pomaly. A ak je rozsah prijateľných hodnôt zložitý, často prisahá, dokonca ani nenájde miesto, z ktorého by mal začať.
• Ak chcete, aby evolučný algoritmus dobre fungoval v Exceli, budete musieť definovať pevné hranice pre každú rozhodovaciu premennú. Aj keď je vaše riešenie viac-menej neobmedzené, stále potrebujete obmedzenia.

Berúc do úvahy posledný bod, na vyriešenie problému so strojmi a maslom musíte pridať obmedzenie, že obe riešenia nesmú byť väčšie ako 25 (obr. 8). Po nastavení základných parametrov modelu kliknite na tlačidlo možnosti. Po asi minútovej práci evolučný algoritmus vytvoril očakávané riešenie - 6 strojov a 9 barelov ropy. Keďže je optimálne vyrobiť len tri stroje bez bonusu a bonus sa vypláca pri výrobe viac ako 5 strojov, je zrejmé, že optimálna voľba by bola 6 strojov.

Uvažujme teraz o zložitejšom príklade. Pracujete vo firme, ktorá vyrába pomarančový džús miešaním prírodných štiav rôznych odrôd (obr. 9). Aby vaša šťava spĺňala tie najnáročnejšie požiadavky:

• pomer Brix/kyslosť by mal zostať medzi 11,5–12,5;
• úroveň kyslosti by mala zostať medzi 0,75–1%;
• úroveň adstringencie by mala byť 4 alebo nižšia;
• farba by mala byť v rozmedzí 4,5–5,5.

Náčelník vám povie, že očakáva, že dopyt bude 600 000 galónov šťavy mesačne v januári a februári a 700 000 galónov v marci. Napriek tomu existuje dohoda so štátom Florida, ktorá poskytuje daňové úľavy za predpokladu, že spoločnosť nakúpi každý mesiac aspoň 40 % šťavy od farmárov, ktorí pestujú túto odrodu. Valencia. Dohoda sa musí rešpektovať.

Ryža. 9. Zoznam charakteristík na výrobu čerstvo vylisovanej pomarančovej šťavy (obrázok zväčšíte tak, že naň kliknete pravým tlačidlom myši a vyberiete Otvoriť obrázok na novej karte)

Vytvorte optimalizačný model (obr. 10). Vzorce je možné študovať na príslušnom hárku priloženého súboru Excel. Kliknite Hľadanie riešenia a zadajte parametre (obr. 11). Kliknite Nájsť riešenie.

Ryža. 11. Vyplnené okno Hľadanie riešenia pre miešaciu úlohu

Spustenie Hľadanie riešenia, zistíte optimálnu obstarávaciu cenu – 1,23 milióna dolárov (obr. 12). Upozorňujeme, že objednávka Florida Valencia spadá na spodnú hranicu podmienky. Je zrejmé, že táto dohoda nie je najlepšou voľbou, ale musíte ju prijať. Druhou najobľúbenejšou odrodou je Verna z Mexika, ktorá je sakramentsky lacná, no rovnako hrozná.

Predložíte výsledky kalkulácie svojmu šéfovi, ale on zostáva nespokojný a povie, že nechce prekročiť rozpočet 1,17 milióna dolárov. Vrátite sa k počítaču a začnete chápať, že náklady prestali byť objektívnou funkciou. Teraz je to podmienka! Aký je cieľ? Nákupné náklady môžete znížiť iba zmiernením požiadaviek na kvalitu. Rozhodnete sa ich sformulovať z hľadiska percentuálneho zníženia a vytvoríte nový model (obrázok 13).

Upozorňujeme, že bunky B26:29 a F26:F29 teraz obsahujú skôr vzorce ako konštanty. Vaším novým cieľom je minimalizovať percentuálnu degradáciu buniek G26:G29. Presnejšie povedané, chceli by ste minimalizovať maximum hodnôt v bunkách G26:G29. Ak však do bunky D2 vložíte vzorec =MAX(G26:G29), model nebude fungovať. Pripomínam, že funkcia MAX nie je lineárna. Malý trik je k dispozícii tu – k modelu môžete pridať dodatočnú podmienku: $G$26:$G$29<=$D$2 (рис. 14), а ячейку D2 оставить пустой. Т.е., ячейка D2 будет оптимизироваться не благодаря наличию в ней формулы, а последовательными циклами, запускаемыми этим дополнительным условием.

Kliknite Nájsť riešenie. Simplexový algoritmus sa pokúsi posunúť D2 bližšie k 0 ako cieľovej funkcii modelu, zatiaľ čo obmedzenia chuti a farby sa ho pokúsia zvýšiť čo najviac, aby sa získala použiteľná zmes. Kde sa zastaví hodnota D2? Najmenšia možná hodnota je maximálne percento zo štyroch znížených v rozsahu G26:G29. Vidíme (obr. 15, bunky C26:E29), že zníženie nákladov o 5 % si vyžadovalo prekročiť limity kvality vo všetkých štyroch parametroch.

Údaje ste predložili šéfovi, ktorý videl, že zníženie nákladov o 5 % nestojí za zníženie kvality šťavy, a tak súhlasil s vašou prvou možnosťou. Ale keď ste to priniesli na oddelenie zásobovania, zamestnanci boli pobúrení. Ako by sa mohli takto rozdeliť zásoby!? Dodávatelia trvajú na tom, aby ste svoje šarže zväčšili: nie viac ako 4 dodávatelia za mesiac! A sadnete si k novému modelu. Bohužiaľ nemôžete použiť funkcie IF alebo COUNT, pretože chcete zostať v lineárnom modeli. Preto sa opäť musíte uchýliť k trikom (obr. 16). Do modelu pridáte oblasť C33:E43, ktorú definujete ako binárnu (hodnoty v nej môžu byť iba 0 alebo 1), a necháte ju prázdnu. A tiež oblasť F33:H43, kde každá bunka sa rovná súčinu hodnoty z oblastí C33:E43 podľa G5:G15. K parametrom Hľadanie riešenia(obr. 17) pridáte ďalšiu podmienku $C$15:$E$15<= $F$33:$H$43 и еще одну область переменных – $C$33:$E$43.

Ako bude v tomto prípade fungovať optimalizačný algoritmus? Keď sa spustí, všetky hodnoty v oblastiach C5:E15, C33:E43 a F33:H43 sú nulové. Povedzme, že sa algoritmus pokúsi umiestniť hodnotu 240 do bunky C7. Podmienka C7 bude fungovať<= F35, которое приведет к увеличению значения в F35, которое, в свою очередь, определяется формулой F35 = C35*$G7. Поскольку G7 – константа, а С35 – бинарная переменная, последней присваивается значение 1. Условие С7 <= F35 выполнено, т.к., 240 <= 1200. Таким образом вы моделируете неудобное условие «если… то»: «если заказ сделан, то бинарная переменная включается».

Kliknite Nájsť riešenie. Všimnete si, že riešenie problému trvá dlhšie kvôli pridávaniu binárnych premenných. Ak z nejakého dôvodu Hľadanie riešenia príliš dlho pri hľadaní, môžete vždy stlačiť kláves ESC a zobraziť momentálne najlepšie nájdené riešenie.

V podstate ste už dosť pokročilý špecialista v oblasti lineárneho programovania. Ak však na to máte chuť a radi sa zaoberáte modelmi s narastajúcou zložitosťou, tu sú ďalšie dva ohromujúce príklady.

Inžinieri oznámili, že vo výrobe sa objavili nové „reduktory kyslosti“. Táto technológia je schopná neutralizovať 20% kyseliny v šťave pretekajúcej zariadením. Tým sa nielen zníži percento kyseliny, ale tiež sa zvýši Brix/index kyslosti o 25 %. Ale "reduktor" vyžaduje energiu a zásoby v cene 20 dolárov za 1 000 galónov šťavy. Nie všetky šťavy pochádzajúce od dodávateľov musia prejsť týmto procesom, ak však zásielka z objednávky prechádza cez iónomenič, musí sa spracovať celý objem. Zostavte model s iónomeničom na zníženie nákladov.

Problém s novým pravidlom je, že prirodzený spôsob modelovania je nelineárny, čo bude mať za následok pomalý optimalizačný algoritmus. Ale ako v predchádzajúcom príklade, môžete zadať binárnu premennú do oblasti C25:E35, ktorá sa „zapne“, ak je potrebné znížiť kyslosť vsádzky (obr. 18). Keďže nemôžete použiť produkt „indikátor zníženia kyslosti (binárny) * objem dávky“, vytvoríte oblasť C37:E47, ktorá bude užitočná na vyrovnanie objemov, ktoré sa majú znížiť v kyslosti, bez toho, aby ste sa priamo podieľali na vzorcoch týchto objemov. . Takže oblasti C25:E35 a C37:E47 neobsahujú vzorce. V oblasti G25:I35 sú použité vzorce =C25:E35*G5:G15 (ide o obmedzenie šarže celkovým dostupným objemom šťavy) a v oblasti K25:M35 =E5:E15-GG5:15 *(1-E25:E35). Táto podmienka bude fungovať iba vtedy, ak dávka podlieha zníženiu kyslosti.

V modeli „znižovania kyslosti“ sa zmenili aj vzorce v bunkách C16:E16 (teraz berú do úvahy náklady na zníženie kyslosti pomocou vzorca „indikátor (binárny) * objem dávky * 20 USD) a v bunkách C50:E51 (teraz berú do úvahy zvýšenie Brixovho koeficientu /kyslosti o 25 % a zníženie kyslosti o 20 % pre spracovávané šarže). V parametroch Hľadanie riešenia objavili sa nové premenné a ďalšie podmienky (obr. 19). Bohužiaľ, stlačením tlačidla Nájsť riešenie, zistíte, že doplnok Hľadanie riešenia nedokáže zvládnuť úlohu (obr. 20). Model sa stal príliš zložitým.

Ryža. 19. Možnosti Hľadanie riešenia v modeli s „reduktorom kyslosti“

Ryža. 20. Hľadanie riešenia nezvláda úlohu

Je potrebné stiahnuť a nainštalovať OpenSolver(ako to urobiť, pozri kapitolu 1). OpenSolver„vyzdvihne“ práve zadané nastavenia v okne Hľadanie riešenia. Stačí teda stlačiť tlačidlo Riešiteľ. Výsledné riešenie – 1 235 927 $ – je o viac ako 100 000 $ lepšie ako predchádzajúce minimum – 1 338 913 $.

Doteraz sme predpokladali, že dodávané produkty majú presne stanovené parametre. Je opodstatnené predpokladať, že tieto parametre podliehajú zmenám, ktoré sa vyznačujú štandardnou odchýlkou ​​(obr. 21; podrobnejšie pozri). Najznámejšie a najpoužívanejšie rozdelenie náhodnej premennej je normálne rozdelenie, inak známe ako zvonová krivka. Povedzme, že v prípade šťavy z Egypta by bol priemerný pomer Brix/kyslosť 13 a štandardná odchýlka (nazývaná aj štandardná odchýlka) by bola 0,9 (obrázok 21). V tomto príklade je 13 stredom rozdelenia pravdepodobnosti, 68 % objednávok bude v rozmedzí ±0,9 z 13 a 95 % bude v rozmedzí ±1,8 z 13.

Vaším cieľom je navrhnúť plán zmiešavania s cenou nižšou ako 1,25 milióna dolárov, ktorý najlepšie spĺňa očakávania kvality vzhľadom na variabilitu ponuky.

Na aplikáciu simulácie Monte Carlo používame strednú a štandardnú odchýlku charakteristík (ak tento názov počujete prvýkrát, odporúčam). Pri tejto metóde sa namiesto zahrnutia distribučných parametrov (priemer a smerodajná odchýlka) priamo do modelu vytvára veľké množstvo scenárov na základe tých istých distribučných parametrov.

Scenár je jednou z možných odpovedí na otázku: „Ak ide o distribúcie založené na štatistikách, ako by vyzerala konkrétna objednávka? Každý scenár obsahuje štyridsať parametrov pre desať odrôd šťavy (obr. 22). Ak chcete získať jeden takýto parameter, použite funkciu NORM.REV (viac informácií o funkcii nájdete v časti). Napríklad v bunke B33 je pomer Brix/kyslosť pre Hamlina daný =NORM.REV(RAND();H5;N5). Zadajte podobné vzorce do oblasti B33:СW76, čím sa vygeneruje 100 scenárov. Hľadanie riešenia nebude môcť s týmito vzorcami pracovať, keďže sú nelineárne, preto ich skopírujte do schránky a prilepte, ale ako hodnoty.

Cieľom je minimalizovať hodnotu v bunke D2. To znamená nájsť riešenie, ktoré najmenej zníži limity kvality pre 100 scenárov. Ako v príkladoch na obr. 13–15, bunka D2 nemá vzorec. Optimalizácia sa vykonáva nastavením parametrov v okne Hľadanie riešenia. Všetko, čo je potrebné, je umiestniť hranice kvality do všetkých scenárov, nielen do očakávaných hodnôt výkonu. Takže v pomere Brix/kyslosť pridáte výrazy B78:CW80 >= B26 a =< F26, затем проделываете то же самое с кислотностью, вяжущей составляющей вкуса и цветом (рис. 24). Нажмите Nájsť riešenie. Riešenie sa nájde pomerne rýchlo. Ak ste náhodné hodnoty vygenerovali sami a nie pomocou hodnôt v súbore na stiahnutie, vaše riešenie sa môže líšiť. Pre mojich sto scenárov to najlepšie, čo som mohol dosiahnuť, bola 133% zmena kvality.

Ryža. 24. Nastavenie Hľadanie riešenia pre model s variabilnými charakteristikami

Ak si chcete rozšíriť svoje znalosti o lineárnom programovaní, odporúčam The AIMMS optimization modeling book. Nenechajte si ujsť dve kapitoly o trikoch a tipoch – sú skutočne skvelé.

Napísané podľa knihy Johna Formana. – M.: Vydavateľstvo Alpina, 2016. – S. 129–186. Čo sa týka utajenia vývoja a 2. svetovej vojny, zdá sa, že ide o osobný názor autora knihy. Pozri Wikipedia. – Poznámka Baguzina.

Problém 1 (distribučný)

V podniku je možné vyrábať 4 druhy výrobkov na 3 samostatných vymeniteľných strojoch.

Známe:

· Výrobná úloha na výrobu rôznych druhov výrobkov v plánovanom období

• · Fond na efektívnu pracovnú dobu zariadení v plánovanom období - ;
• · Normy pre náklady na strojový čas na výrobu jednotky produkcie - ;
• · Zisk v rub. z predaja jednotky produktu vyrobenej na tom alebo onom zariadení - .

Počiatočné informácie sú zobrazené v tabuľke nasledujúceho formulára.

Tabuľka 1. Počiatočné údaje

Fond ef. otrok. čas -	Normy spotreby času za jednotku produkty - zisk na jednotku. Produkty -

Problém si vyžaduje nájsť plán distribúcie produkčnej úlohy pre výstup produktu medzi účinkujúcich

v ktorej by bola úloha splnená s maximálnym celkovým ziskom z predaja produktov.

RIEŠENIE

Vývoj ekonomického a matematického modelu.

Požadované veličiny charakterizujú objem výroby dodávateľa.

Potom matica požadovaných premenných

charakterizuje plán distribúcie výrobných úloh pre výstup produktu medzi vykonávateľov.

Objektívna funkcia

charakterizujúce celkový zisk z predaja všetkých produktov musí byť maximalizovaný.

Obmedzenia dostupnosti a využívania efektívneho pracovného času výkonných umelcov budú mať podobu systému lineárnych nerovností (2):

Tento systém obmedzení charakterizuje podmienku, že celkové vynaloženie efektívneho pracovného času každého výkonného umelca v plánovacom období na výrobu všetkých druhov výrobkov by nemalo presiahnuť časový fond. V dôsledku vyriešenia problému tak každý účinkujúci dostane svoju vlastnú úlohu na základe svojich schopností. Ak nejaká vyvažujúca premenná nadobudne hodnotu pri riešení problému, bude charakterizovať nedostatočne využitý efektívny pracovný čas toho či onoho pracovníka, ktorý sa vo výrobných podmienkach môže použiť na výrobu produktov nad rámec úlohy.

Nasledujúci blok obmedzení by mal odrážať podmienku povinného plnenia všeobecného výrobného cieľa pre výrobu produktov podľa typu a bude reprezentovaný sústavou lineárnych rovníc (3):

Podmienka pre nezáporné premenné:

Uveďme problém do kanonickej podoby, preto k nerovnostiam pridáme premenné (2) a k rovnosti (3) pridáme 4 umelé bázy. V dôsledku toho napíšeme matematický model problému v kanonickej forme:

Simplexná metóda

Vyriešme tento problém simplexnou metódou vyplnením tabuľky. Riešenie trvá niekoľko iterácií. Ukážme to.

stôl 1

Koeficienty účelovej funkcie sú uvedené v hornom riadku tabuľky; druhý riadok je názov všetkých neznámych zahrnutých v simplexných rovniciach. Prvý stĺpec vľavo obsahuje koeficienty účelovej funkcie, ktoré zodpovedajú základným neznámym obsiahnutým v pôvodnom programe (zapísané v stĺpci). Ďalší, tretí stĺpec v prvej simplexnej tabuľke je vyplnený hodnotami základných neznámych. Ďalej sú stĺpce, ktoré predstavujú vektory podmienok. Ich počet je 19. V ďalšom, prvom stĺpci za maticou podmienok sú zapísané súčty všetkých prvkov v riadkoch. Stĺpec zaznamenáva podiely z delenia prvkov konečného stĺpca B na prvky určitého stĺpca, matice podmienok. Keďže máme umelú bázu, v indexovej línii budú dva výpočty, v prvom z nich zohľadňujúce premenné a v druhom len umelá báza. Keďže máme problém s maximalizáciou, je potrebné zo základu odvodiť umelé základy. V druhom riadku indexu vyberieme najväčšie kladné skóre. Toto je náš prvý stĺpec. Hľadajme hodnotové vzťahy

A. Z týchto pomerov vyberieme najmenší, pre nás je to štvrtý riadok, pre ktorý je odhadovaný pomer rovný 1300. Vyberte riadok. Posledný stĺpec je koeficient, ktorým sa pri prepočte vynásobí každý prvok riadku. Získame ho vydelením prvkov vybraného stĺpca kľúčovým prvkom, ktorý sa nachádza na priesečníku vybraného stĺpca a riadku, pre nás je to 1. Prepočet robíme pre všetky nevybrané prvky, ktorý sa vykonáva ako nasleduje: od prepočítaného prvku odpočítame prvok kľúčového riadku, vynásobený koeficientom prepočítaného riadku: a tak ďalej pre všetky prvky. Zo základu odvodzujeme umelý základ, pričom do základu zavádzame premennú.

Posledné dva riadky sú indexové riadky, kde sa prepočítavajú hodnoty cieľovej funkcie, ako aj celý indexový riadok, keď sú všetky prvky kladné alebo nulové - problém bude vyriešený.

Ukážme to.

tabuľka 2

Vyberieme stĺpec s premennou. Nájdeme odhadované pomery, z ktorých vyberieme najmenší - to je 550. Zo základu odvodíme umelú premennú a zároveň do základu zavedieme premennú. Keď je zo základu odvodený umelý základ, príslušný stĺpec sa odstráni.

Tabuľka 3

Vyberieme stĺpec. Najmenší odhadovaný pomer, 600, sa nachádza v šiestom riadku. Zo základu odvodzujeme umelý základ, pričom do základu zavádzame premennú.

Tabuľka 4

Vyberieme stĺpec s premennou. Najnižší odhadovaný pomer 28,57 je v prvom rade. Zo základu odvodíme premennú a do základu zavedieme premennú.

Tabuľka 5

Vyberieme stĺpec s premennou. Najnižší odhadovaný pomer 407,7 je v treťom rade. Zo základu odvodíme premennú a do základu zavedieme premennú.

Tabuľka 6

Vyberieme stĺpec s premennou. Najnižší odhadovaný pomer, 344,3, sa nachádza v siedmom riadku. Zo základu odvodzujeme umelý základ, pričom do základu zavádzame premennú.

Tabuľka 7

Vyberieme stĺpec s premennou. Najmenší odhadovaný pomer, 3,273, sa nachádza v druhom rade. Zo základu odvodíme premennú a do základu zavedieme premennú.

Tabuľka 8

Vyberieme stĺpec s premennou. Najmenší odhadovaný pomer, 465, sa nachádza v siedmom riadku. Zo základu odvodíme premennú a do základu zavedieme premennú.

Tabuľka 9

Vyberieme stĺpec s premennou. Najmenší odhadovaný pomer, 109, je v treťom rade. Zo základu odvodíme premennú a do základu zavedieme premennú.

Tabuľka 10

Vyberieme stĺpec s premennou. Najmenší odhadovaný pomer, 10, je v prvom rade. Zo základu odvodíme premennú a do základu zavedieme premennú.

Tabuľka 11

Vyberieme stĺpec s premennou. Najmenší odhadovaný pomer, 147, je v druhom rade. Zo základu odvodíme premennú a do základu zavedieme premennú.

Tabuľka 12

Vyberieme stĺpec s premennou. Najmenší odhadovaný pomer, 367, je v piatom rade. Zo základu odvodíme premennú a do základu zavedieme premennú.

Tabuľka 13

Vyberieme stĺpec s premennou. Najmenší odhadovaný pomer, 128, je vo štvrtom rade. Zo základu odvodíme premennú a do základu zavedieme premennú.

Tabuľka 14

Keďže v indexovej línii nie sú žiadne negatívne odhady, získa sa optimálny plán, v ktorom objem produkcie predstavuje matica

zároveň je zisk maximálny a predstavuje 17 275,31 rubľov.

Riešenie problému pomocou Excelu

Matematický model úlohy je potrebné preniesť do ET EXCEL. Pre to:

• · Zvážte usporiadanie počiatočných údajov modelu (koeficienty cieľovej funkcie a obmedzenia) a poskytnite im jasné názvy.
• · Rezervovať nezávislé premenné matematického modelu v samostatných bunkách.
• · V jednej z buniek vytvorte vzorec, ktorý definuje účelovú funkciu.
• · Vyberte bunky a umiestnite do nich vzorce, ktoré zodpovedajú ľavým stranám obmedzení.
• · Zadajte položku ponuky „Vyhľadať riešenie“, zadajte potrebné údaje a získajte optimálne riešenie problému.
• · Analyzujte výsledné riešenie a správy.

Uvažujme o postupnosti akcií na implementáciu týchto fáz riešenia problému pomocou EXCELu.

Vytvorme si tabuľku na zadávanie počiatočných údajov.

Do vytvoreného formulára zadáme počiatočné údaje.

Koeficienty účelovej funkcie, vyjadrujúce zisk z produkcie jednotky produktu každého druhu (unit profit), sa zapisujú do buniek B6: M6.

Koeficienty obmedzenia zdrojov, ktoré určujú potrebu každého typu zdroja na produkciu jednotky výstupu, sa nachádzajú v bunkách B9:M15. Bunky P9:P15 obsahujú pravé strany obmedzení zdrojov. Bunky B3:M3 sú vyhradené pre nezávislé premenné problému - požadované objemy produkcie.

Do bunky N7 zadajte vzorec pre cieľovú funkciu pomocou príkazu vloženia funkcie SUMPRODUCT:

Obmedzenia vypĺňame aj na pravej strane.

Potom môžete začať hľadať riešenie. Ak chcete vyriešiť problémy s optimalizáciou v programe EXCEL, použite príkaz HĽADAŤ RIEŠENIE v ponuke SERVIS.

Tento príkaz pracuje s tromi hlavnými komponentmi optimalizovaného modelu zabudovaného v ET:

• · Bunka obsahujúca objektívnu funkciu problému.
• · Editovateľné bunky obsahujúce nezávislé premenné.
• · Bunky obsahujúce ľavé strany obmedzení dostupných zdrojov, ako aj jednoduché obmedzenia nezávislých premenných.

Uvažujme o postupnosti zadávania týchto komponentov.

Kurzor je v bunke N7 a príkaz SERVICE - Hľadať riešenie. Na obrazovke sa zobrazí dialógové okno.

V okne vyplňte pole Nastaviť cieľovú bunku, ktoré by malo obsahovať adresu $N$7. Ďalej nastavte tlačidlo na vyhľadanie maximálnej hodnoty. Do poľa Zmena buniek zadajte adresy požadovaných premenných $B3:$M3. Potom by ste mali zadať obmedzenia pomocou tlačidla Pridať.

Teraz, keď sú nastavené všetky obmedzenia na nájdenie optimálneho riešenia, môžeme stlačiť tlačidlo:

Po tomto získame riešenie problému.

Ak boli výpočty úspešné, po dokončení hľadania riešenia sa hodnoty vložia do tabuľky a môžete tiež určiť Typ správy - Výsledky, v dôsledku čoho môžeme získať nasledujúcu správu. pracovník čas zariadenia zisk

Riešenie v EXCEL je teda rovnaké ako pri metóde SIMPLEX, čo znamená, že uvažovaný problém bol vyriešený správne.

Odoslanie dobrej práce do databázy znalostí je jednoduché. Použite nižšie uvedený formulár

Študenti, postgraduálni študenti, mladí vedci, ktorí využívajú vedomostnú základňu pri štúdiu a práci, vám budú veľmi vďační.

Uverejnené dňa http://www.allbest.ru/

Riešenie problému pomocou Excelu a simplexnej metódy

Úloha (distribučná)

Simplexná metóda

Riešenie problému pomocou Excelu

Úloha (distribučná)

Problém 1 (distribučný)

V podniku je možné vyrábať 4 druhy výrobkov na 3 samostatných vymeniteľných strojoch.

Známe:

· Výrobná úloha na výrobu rôznych druhov výrobkov v plánovanom období

· Fond na efektívnu pracovnú dobu zariadení v plánovanom období - ;

· Normy pre náklady na strojový čas na výrobu jednotky produkcie - ;

· Zisk v rub. z predaja jednotky produktu vyrobenej na tom alebo onom zariadení - .

Počiatočné informácie sú zobrazené v tabuľke nasledujúceho formulára.

Tabuľka 1. Počiatočné údaje

Fond ef. otrok. čas -	Normy spotreby času za jednotku produkty - zisk na jednotku. Produkty -

Problém si vyžaduje nájsť plán distribúcie produkčnej úlohy pre výstup produktu medzi účinkujúcich

v ktorej by bola úloha splnená s maximálnym celkovým ziskom z predaja produktov.

RIEŠENIE

Vývoj ekonomického a matematického modelu.

Požadované veličiny charakterizujú objem výroby dodávateľa.

Potom matica požadovaných premenných

charakterizuje plán distribúcie výrobných úloh pre výstup produktu medzi vykonávateľov.

Objektívna funkcia

charakterizujúce celkový zisk z predaja všetkých produktov musí byť maximalizovaný.

Obmedzenia dostupnosti a využívania efektívneho pracovného času výkonných umelcov budú mať podobu systému lineárnych nerovností (2):

Tento systém obmedzení charakterizuje podmienku, že celkové vynaloženie efektívneho pracovného času každého výkonného umelca v plánovacom období na výrobu všetkých druhov výrobkov by nemalo presiahnuť časový fond. V dôsledku vyriešenia problému tak každý účinkujúci dostane svoju vlastnú úlohu na základe svojich schopností. Ak nejaká vyvažujúca premenná nadobudne hodnotu pri riešení problému, bude charakterizovať nedostatočne využitý efektívny pracovný čas toho či onoho pracovníka, ktorý sa vo výrobných podmienkach môže použiť na výrobu produktov nad rámec úlohy.

Nasledujúci blok obmedzení by mal odrážať podmienku povinného plnenia všeobecného výrobného cieľa pre výrobu produktov podľa typu a bude reprezentovaný sústavou lineárnych rovníc (3):

Podmienka pre nezáporné premenné:

Uveďme problém do kanonickej podoby, preto k nerovnostiam pridáme premenné (2) a k rovnosti (3) pridáme 4 umelé bázy. V dôsledku toho napíšeme matematický model problému v kanonickej forme:

Simplexná metóda

Vyriešme tento problém simplexnou metódou vyplnením tabuľky. Riešenie trvá niekoľko iterácií. Ukážme to.

stôl 1

Koeficienty účelovej funkcie sú uvedené v hornom riadku tabuľky; druhý riadok je názov všetkých neznámych zahrnutých v simplexných rovniciach. Prvý stĺpec vľavo obsahuje koeficienty účelovej funkcie, ktoré zodpovedajú základným neznámym obsiahnutým v pôvodnom programe (zapísané v stĺpci). Ďalší, tretí stĺpec v prvej simplexnej tabuľke je vyplnený hodnotami základných neznámych. Ďalej sú stĺpce, ktoré predstavujú vektory podmienok. Ich počet je 19. V ďalšom, prvom stĺpci za maticou podmienok sú zapísané súčty všetkých prvkov v riadkoch. Stĺpec zaznamenáva podiely z delenia prvkov konečného stĺpca B na prvky určitého stĺpca, matice podmienok. Keďže máme umelú bázu, v indexovej línii budú dva výpočty, v prvom z nich zohľadňujúce premenné a v druhom len umelá báza. Keďže máme problém s maximalizáciou, je potrebné zo základu odvodiť umelé základy. V druhom riadku indexu vyberieme najväčšie kladné skóre. Toto je náš prvý stĺpec. Hľadajme hodnotové vzťahy

A. Z týchto pomerov vyberieme najmenší, pre nás je to štvrtý riadok, pre ktorý je odhadovaný pomer rovný 1300. Vyberte riadok. Posledný stĺpec je koeficient, ktorým sa pri prepočte vynásobí každý prvok riadku. Získame ho vydelením prvkov vybraného stĺpca kľúčovým prvkom, ktorý sa nachádza na priesečníku vybraného stĺpca a riadku, pre nás je to 1. Prepočet robíme pre všetky nevybrané prvky, ktorý sa vykonáva ako nasleduje: od prepočítaného prvku odpočítame prvok kľúčového riadku, vynásobený koeficientom prepočítaného riadku: a tak ďalej pre všetky prvky. Zo základu odvodzujeme umelý základ, pričom do základu zavádzame premennú.

Posledné dva riadky sú indexové riadky, kde sa prepočítavajú hodnoty cieľovej funkcie, ako aj celý indexový riadok, keď sú všetky prvky kladné alebo nulové - problém bude vyriešený.

Ukážme to.

tabuľka 2

Vyberieme stĺpec s premennou. Nájdeme odhadované pomery, z ktorých vyberieme najmenší - to je 550. Zo základu odvodíme umelú premennú a zároveň do základu zavedieme premennú. Keď je zo základu odvodený umelý základ, príslušný stĺpec sa odstráni.

Tabuľka 3

Vyberieme stĺpec. Najmenší odhadovaný pomer, 600, sa nachádza v šiestom riadku. Zo základu odvodzujeme umelý základ, pričom do základu zavádzame premennú.

Tabuľka 4

Vyberieme stĺpec s premennou. Najnižší odhadovaný pomer 28,57 je v prvom rade. Zo základu odvodíme premennú a do základu zavedieme premennú.

Tabuľka 5

Vyberieme stĺpec s premennou. Najnižší odhadovaný pomer 407,7 je v treťom rade. Zo základu odvodíme premennú a do základu zavedieme premennú.

Tabuľka 6

Vyberieme stĺpec s premennou. Najnižší odhadovaný pomer, 344,3, sa nachádza v siedmom riadku. Zo základu odvodzujeme umelý základ, pričom do základu zavádzame premennú.

Tabuľka 7

Vyberieme stĺpec s premennou. Najmenší odhadovaný pomer, 3,273, sa nachádza v druhom rade. Zo základu odvodíme premennú a do základu zavedieme premennú.

Tabuľka 8

Vyberieme stĺpec s premennou. Najmenší odhadovaný pomer, 465, sa nachádza v siedmom riadku. Zo základu odvodíme premennú a do základu zavedieme premennú.

Tabuľka 9

Vyberieme stĺpec s premennou. Najmenší odhadovaný pomer, 109, je v treťom rade. Zo základu odvodíme premennú a do základu zavedieme premennú.

Tabuľka 10

Vyberieme stĺpec s premennou. Najmenší odhadovaný pomer, 10, je v prvom rade. Zo základu odvodíme premennú a do základu zavedieme premennú.

Tabuľka 11

Vyberieme stĺpec s premennou. Najmenší odhadovaný pomer, 147, je v druhom rade. Zo základu odvodíme premennú a do základu zavedieme premennú.

Tabuľka 12

Vyberieme stĺpec s premennou. Najmenší odhadovaný pomer, 367, je v piatom rade. Zo základu odvodíme premennú a do základu zavedieme premennú.

Tabuľka 13

Vyberieme stĺpec s premennou. Najmenší odhadovaný pomer, 128, je vo štvrtom rade. Zo základu odvodíme premennú a do základu zavedieme premennú.

Tabuľka 14

Keďže v indexovej línii nie sú žiadne negatívne odhady, získa sa optimálny plán, v ktorom objem produkcie predstavuje matica

zároveň je zisk maximálny a predstavuje 17 275,31 rubľov.

Riešenie problému pomocou Excel

Matematický model úlohy je potrebné preniesť do ET EXCEL. Pre to:

· Zvážte usporiadanie počiatočných údajov modelu (koeficienty cieľovej funkcie a obmedzenia) a poskytnite im jasné názvy.

· Rezervovať nezávislé premenné matematického modelu v samostatných bunkách.

· V jednej z buniek vytvorte vzorec, ktorý definuje účelovú funkciu.

· Vyberte bunky a umiestnite do nich vzorce, ktoré zodpovedajú ľavým stranám obmedzení.

· Zadajte položku ponuky „Vyhľadať riešenie“, zadajte potrebné údaje a získajte optimálne riešenie problému.

· Analyzujte výsledné riešenie a správy.

Uvažujme o postupnosti akcií na implementáciu týchto fáz riešenia problému pomocou EXCELu.

Vytvorme si tabuľku na zadávanie počiatočných údajov.

Do vytvoreného formulára zadáme počiatočné údaje.

Koeficienty účelovej funkcie, vyjadrujúce zisk z produkcie jednotky produktu každého druhu (unit profit), sa zapisujú do buniek B6: M6.

Koeficienty obmedzenia zdrojov, ktoré určujú potrebu každého typu zdroja na produkciu jednotky výstupu, sa nachádzajú v bunkách B9:M15. Bunky P9:P15 obsahujú pravé strany obmedzení zdrojov. Bunky B3:M3 sú vyhradené pre nezávislé premenné problému - požadované objemy produkcie.

Do bunky N7 zadajte vzorec pre cieľovú funkciu pomocou príkazu vloženia funkcie SUMPRODUCT:

Obmedzenia vypĺňame aj na pravej strane.

Potom môžete začať hľadať riešenie. Ak chcete vyriešiť problémy s optimalizáciou v programe EXCEL, použite príkaz HĽADAŤ RIEŠENIE v ponuke SERVIS.

Tento príkaz pracuje s tromi hlavnými komponentmi optimalizovaného modelu zabudovaného v ET:

· Bunka obsahujúca objektívnu funkciu problému.

· Editovateľné bunky obsahujúce nezávislé premenné.

· Bunky obsahujúce ľavé strany obmedzení dostupných zdrojov, ako aj jednoduché obmedzenia nezávislých premenných.

Uvažujme o postupnosti zadávania týchto komponentov.

Kurzor je v bunke N7 a príkaz SERVICE - Hľadať riešenie. Na obrazovke sa zobrazí dialógové okno.

V okne vyplňte pole Nastaviť cieľovú bunku, ktoré by malo obsahovať adresu $N$7. Ďalej nastavte tlačidlo na vyhľadanie maximálnej hodnoty. Do poľa Zmena buniek zadajte adresy požadovaných premenných $B3:$M3. Potom by ste mali zadať obmedzenia pomocou tlačidla Pridať.

Teraz, keď sú nastavené všetky obmedzenia na nájdenie optimálneho riešenia, môžeme stlačiť tlačidlo:

Po tomto získame riešenie problému.

Ak boli výpočty úspešné, po dokončení hľadania riešenia sa hodnoty vložia do tabuľky a môžete tiež určiť Typ správy - Výsledky, v dôsledku čoho môžeme získať nasledujúcu správu. pracovník čas zariadenia zisk

Riešenie v EXCEL je teda rovnaké ako pri metóde SIMPLEX, čo znamená, že uvažovaný problém bol vyriešený správne.

Uverejnené na Allbest.ru

...

Podobné dokumenty

Určenie optimálneho objemu výstupu pomocou matematickej metódy, simplexovej metódy a pomocou Excelu. Riešenie problému optimálnej alokácie investícií pomocou aplikačného programu Excel. Vypracovanie optimálnej dopravnej schémy.

kurzová práca, pridané 9.10.2012


Plánovanie zisku pri výrobe dvoch druhov palív. Zostavenie optimálneho plánu výroby na získanie maximálneho zisku z jeho predaja. Stanovenie základného plánu prepravy nákladu metódou minimálnych nákladov a pomocou Excelu.

test, pridaný 12.11.2014


Algoritmus na riešenie úloh lineárneho programovania simplexnou metódou. Konštrukcia matematického modelu úlohy lineárneho programovania. Riešenie úlohy lineárneho programovania v Exceli. Hľadanie zisku a optimálneho plánu výroby.

kurzová práca, pridané 21.03.2012


Pomocou simplexovej metódy stanovenie výrobného plánu na získanie maximálneho zisku tak, aby boli suroviny typu II úplne spotrebované. Riešenie problémov lineárneho programovania pomocou excelovskej tabuľky, vytvorenie algoritmu.

kurzová práca, pridané 30.09.2013


Štúdium matematicko-ekonomického modelu spoločnosti za účelom vývoja optimálneho riešenia pre výrobu pre získanie maximálneho zisku a minimalizáciu nákladov pomocou optimalizačných metód a programu MS Excel a balíka nástrojov Matlab.

práca, pridané 15.06.2014


Prehľad algoritmov na riešenie problémov lineárneho programovania. Vývoj algoritmu pre tabuľkovú simplexovú metódu. Zostavenie výrobného plánu, ktorý bude dosahovať maximálne zisky z predaja. Konštrukcia matematického modelu problému.

kurzová práca, pridané 21.11.2013


Stanovenie počtu a typu traktorových a automobilových tlmičov, ktoré by mala spoločnosť vyrábať, aby maximalizovala zisk. Riešenie úloh lineárneho programovania pomocou grafických a simplexových metód pomocou tabuľkového editora Excel.

kurzová práca, pridané 04.09.2013


Optimalizácia nákladov na dodávku produktov spotrebiteľom. Charakteristika dopravného problému, všeobecná forma riešenia, zovšeobecnenie; zmysluplná a matematická formulácia problému, riešenie pomocou MS Excel: výpis programu, analýza výsledkov.

kurzová práca, pridané 02.04.2011


Matematické základy optimalizácie. Vyhlásenie problému optimalizácie. Optimalizačné metódy. Riešenie úlohy klasickou simplexovou metódou. Grafická metóda. Riešenie problémov pomocou Excelu. Koeficienty objektívnej funkcie. Lineárne programovanie, metóda, problémy.

abstrakt, pridaný 21.08.2008


Stanovenie množstva nakupovaných surovín na výrobu podľa mesiacov, počas celého roka a za rok ako celok. Algoritmus potrebných akcií, prezentácia výsledkov v grafickej forme. Riešenie problému v Exceli a pomocou nástrojov VBA.