1. Premeňte nerovnosti na rovnosť
2. Nájdite počiatočné prípustné základné riešenie
3. Na základe podmienky optimality sa určí vstupná premenná. Ak neexistujú žiadne vstupné premenné, proces je ukončený.
4. Na základe podmienky prípustnosti vyberte vylúčenú premennú
5. Vypočítajte prvky novej vodiacej čiary
nová vedúca línia = aktuálna linka/ vedúci prvok
6. Vypočítajte prvky zostávajúcich čiar vrátane čiary z
nový riadok = aktuálny riadok - jeho koeficienty v poprednom stĺpci * nový vodiaci riadok
Prejdite na krok 3.
Pre pohodlie zaznamenávania iteračného procesu zapisujeme všetky hodnoty do Simplexovej tabuľky.
2. Príklad riešenia problému lp pomocou balíka ms excel
Pri mnohých optimalizačných problémoch je vhodné použiť model lineárneho programovania. Podstatou problému je sformulovať systém nerovníc, ktoré popisujú zodpovedajúce obmedzenia problému a nastaviť optimalizačnú funkciu.
Na nájdenie riešenia v takýchto modeloch môžete použiť nástroj MS EXCEL - HĽADAŤ RIEŠENIE.
Pozrime sa, ako vytvoriť model lineárneho programovania a nájsť jeho riešenie pomocou príkladu.
2.1. Formulácia problému
Na troch strojoch sa spracovávajú diely dvoch typov (A a B) a každý diel sa spracováva na všetkých strojoch. Poznáme dobu spracovania dielov na každom stroji, dobu prevádzky strojov počas jedného výrobného cyklu a zisk z predaja jedného dielu z každého druhu (údaje v tabuľke). Zostavte plán výroby, ktorý poskytuje najvyšší zisk.
2.2. Zostavenie matematického modelu
Označme x 1 a x 2 počet jednotiek častí typu A a B, ktoré sú plánované na uvoľnenie. Potom je čas spracovania x 1 dielov typu A na prvom stroji 1 * x 1; x 2 diely typu B, respektíve 2 * x 2. Celková doba prevádzky stroja I na výrobu plánovaného počtu dielov je x 1 + 2 * x 2, je obmedzená na 16 hodín prevádzky tohto stroja počas jedného výrobného cyklu. Preto musí byť splnená nerovnosť:
x 1 + 2 * x 2<=16;
Podobne pre stroje II a III získame nerovnosti, resp.
x 1 + x 2<=10;
3 * x 1 + x 2<=24;
Okrem toho v zmysle definície zadaných hodnôt x 1 a x 2 musia byť splnené tieto podmienky: x 1 > = 0; x2> = 0;
Takto získame systém nerovností nazývaný systém obmedzení pre problém:
Akékoľvek riešenie (x 1; x 2) systému obmedzení sa nazýva plán výroby alebo plán realizovateľných problémov.
Zisk z predaja x 1 kusov dielov typu A je 4. x 1 a zisk z predaja x 2 kusov dielov typu B je 2 x 2. Celkový zisk z predaja výrobkov uvoľnených podľa plánu (x 1; x 2) sa rovná:
F(NS 1 ; NS 2 ) = 4x 1 + 2x 2 (tisíc rubľov).
Lineárna funkcia F(NS 1 ; NS 2 ) sa nazýva objektívna funkcia problému.
Podľa stavu problému je potrebné nájsť taký plán (x 1; x 2), pri ktorom by bol zisk maximálny.
Matematický model problému bol teda zostavený ako problém lineárneho programovania:
F(NS 1 ; NS 2 ) = 4x 1 + 2x 2 → max
Odoslanie dobrej práce do databázy znalostí je jednoduché. Použite nižšie uvedený formulár
Študenti, postgraduálni študenti, mladí vedci, ktorí pri štúdiu a práci využívajú vedomostnú základňu, 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 (distribúcia)
Simplexná metóda
Riešenie problému pomocou Excelu
Úloha (distribúcia)
Úloha 1 (distribúcia)
V podniku je možné vyrábať 4 druhy výrobkov na 3 samostatných vymeniteľných strojoch.
Známe:
Výrobné zadanie na uvoľnenie rôznych typov produktov v plánovacom období
· Fond efektívnej pracovnej doby zariadení v plánovanom období -;
· Miery vynaloženia strojového času na výrobu jednotky produkcie -;
· Zisk v rubľoch. z predaja výrobnej jednotky vyrobenej na konkrétnom zariadení -.
Počiatočné informácie sú zobrazené v tabuľke v nasledujúcom formulári.
Tabuľka 1. Počiatočné údaje
|
Fond ef. otrok. čas. - |
Nákladové sadzby času. za jednotku produkty - zisk na jednotku. Produkty - |
||||
V úlohe musíte nájsť plán distribúcie produkčnej úlohy na vydanie produktov medzi účinkujúcimi
pri ktorej by bola úloha splnená s maximálnym celkovým ziskom z predaja produktov.
RIEŠENIE
Vývoj ekonomického a matematického modelu.
Hľadané premenné - charakterizujú objem produkcie m interpreta.
Potom matica požadovaných premenných
charakterizuje plán rozdelenia výrobnej úlohy na výrobu produktov medzi účinkujúcich.
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é náklady na efektívny pracovný čas každého výkonného umelca v plánovacom období na vydanie všetkých druhov produktov by nemali presiahnuť časový fond. V dôsledku vyriešenia problému teda každý účinkujúci dostane svoju úlohu na základe svojich schopností. Ak pri riešení problému nadobudne hodnotu niektorá bilančná veličina, bude to charakterizovať nevyužitý efektívny pracovný čas toho či onoho realizátora, ktorý môže byť vo výrobných podmienkach využitý na uvoľnenie produktov nad rámec úlohy.
Ďalší blok obmedzení by mal odzrkadľovať podmienku povinného plnenia všeobecnej výrobnej úlohy pre výstup výrobkov podľa typu a bude reprezentovaný sústavou lineárnych rovníc (3):
Podmienka nezápornosti premenných:
Zredukujme problém na kanonickú formu, preto k nerovnosti (2) pridáme premenné a k rovnosti (3) pridáme 4 umelé bázy. Výsledkom je, že zapíšeme matematický model problému v kanonickom tvare:
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
V najvrchnejšom riadku tabuľky sú zadané koeficienty účelovej funkcie, v druhom riadku sú názvy všetkých neznámych zahrnutých v simplexných rovniciach. V prvom stĺpci vľavo sú zapísané koeficienty účelovej funkcie, ktoré zodpovedajú základným neznámym obsiahnutým v pôvodnom programe (zapísané v stĺpci). Ďalší, tretí v rade 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 stĺpci, prvom za maticou podmienok, sú v riadkoch zapísané súčty všetkých prvkov. Stĺpec obsahuje kvocienty z delenia prvkov konečného stĺpca B na prvky určitého stĺpca, maticu podmienok. Keďže máme umelú bázu, v indexovej línii budú dva výpočty, v prvom s prihliadnutím na 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 indexovom riadku vyberte najvyššiu kladnú značku. Máme - toto je prvý stĺpec. Nájdenie hodnotového vzťahu
a Z týchto vzťahov vyberieme najmenší, máme ho štvrtý riadok, preňho je odhadovaný pomer 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čítajte prvok kľúčového riadku od prvku, ktorý sa prepočítava, vynásobený faktorom prepočítaného riadka: a tak sú 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 sa vyrieši.
Ukážme to.
tabuľka 2
Vyberieme stĺpec s premennou. Nájdeme odhadované vzťahy, z ktorých vyberieme najmenší - to je 550. Zo základu odvodíme umelú premennú, pričom premennú vložíme do základu. Keď sa zo základu odvodí umelý základ, odstránime príslušný stĺpec.
Tabuľka 3
Vyberieme stĺpec. Najmenší odhadovaný pomer, 600, je v šiestom rade. Zo základu odvodzujeme umelý základ, pričom do základu zavádzame premennú.
Tabuľka 4
Vyberieme stĺpec s premennou. Najmenší odhadovaný pomer 28,57 je v prvom rade. Premennú odvodzujeme zo základu, pričom premennú zavádzame do základu.
Tabuľka 5
Vyberieme stĺpec s premennou. Najmenší odhadovaný pomer 407,7 je v treťom rade. Premennú odvodzujeme zo základu, pričom premennú zavádzame do základu.
Tabuľka 6
Vyberieme stĺpec s premennou. Najmenší odhadovaný pomer 344,3 je v siedmom rade. 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 je v druhom rade. Premennú odvodzujeme zo základu, pričom premennú zavádzame do základu.
Tabuľka 8
Vyberieme stĺpec s premennou. Najmenší odhadovaný pomer, 465, je v siedmom rade. Premennú odvodzujeme zo základu, pričom premennú zavádzame do základu.
Tabuľka 9
Vyberieme stĺpec s premennou. Najmenší odhadovaný pomer, 109, je v treťom rade. Premennú odvodzujeme zo základu, pričom premennú zavádzame do základu.
Tabuľka 10
Vyberieme stĺpec s premennou. Najmenší odhadovaný pomer, 10, je v prvom rade. Premennú odvodzujeme zo základu, pričom premennú zavádzame do základu.
Tabuľka 11
Vyberieme stĺpec s premennou. Najmenší odhadovaný pomer, 147, je v druhom rade. Premennú odvodzujeme zo základu, pričom premennú zavádzame do základu.
Tabuľka 12
Vyberieme stĺpec s premennou. Najmenší odhadovaný pomer, 367, je v piatom rade. Premennú odvodzujeme zo základu, pričom premennú zavádzame do základu.
Tabuľka 13
Vyberieme stĺpec s premennou. Najmenší odhadovaný pomer, 128, je vo štvrtom riadku. Premennú odvodzujeme zo základu, pričom premennú zavádzame do základu.
Tabuľka 14
Keďže v indexovej línii nie sú žiadne negatívne hodnotenia, získa sa optimálny plán, pre ktorý objem výroby predstavuje matica
maximálny zisk je 17 275,31 rubľov.
Riešenie problému s Excel
Matematický model úlohy je potrebné preniesť do ET EXCEL. Pre to:
· Premyslite si organizáciu počiatočných údajov modelu (koeficienty objektívnych funkcií a obmedzenia) a poskytnite 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 prijaté riešenie a správy.
Uvažujme o postupnosti akcií na implementáciu týchto fáz riešenia problému pomocou EXCELu.
Vytvorme tabuľku na zadávanie počiatočných údajov.
Do vytvoreného formulára zadáme počiatočné údaje.
Koeficienty objektívnej funkcie vyjadrujúce zisk z produkcie jednotky produkcie každého druhu (unit profit) sa zapisujú do buniek B6: M6.
Koeficienty obmedzenia zdrojov, ktoré určujú potrebu každého z typov zdrojov na výrobu jednotky výstupu, sa nachádzajú v bunkách B9: M15. Bunky P9: P15 obsahujú pravú stranu limitov zdrojov. Bunky B3: M3 sú vyhradené pre nezávislé premenné problému - požadovaný objem produkcie.
Do bunky N7 zadajte vzorec pre funkciu Object použitím príkazu na vloženie funkcie SUMPRODUCT:
A tiež vyplniť obmedzenia na pravej strane.
Potom môžete začať hľadať riešenie. Na vyriešenie problémov s optimalizáciou v programe EXCEL sa používa príkaz HĽADAŤ RIEŠENIE v ponuke SERVIS.
Tento tím pracuje s tromi hlavnými komponentmi optimalizovateľného modelu zabudovaného v ET:
· Bunka obsahujúca účelovú funkciu úlohy.
· Upraviteľ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 vstupu týchto komponentov.
Kurzor je v bunke N7 a príkaz SERVIS - Vyhľ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 hľadaný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:
Potom dostaneme 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ť ďalšiu správu. pracovný čas zariadenia zisk
Riešenie v EXCEL je teda rovnaké ako v metóde SIMPLEX, čo znamená, že uvažovaný problém je vyriešený správne.
Uverejnené na Allbest.ru
...Podobné dokumenty
Stanovenie optimálneho objemu produktov matematickou metódou, simplexovou metódou a pomocou Excelu. Riešenie problému optimálneho rozloženia investícií pomocou aplikačného programu Excel. Vypracovanie optimálnej dopravnej schémy.
semestrálna práca, pridaná 9.10.2012
Plánovanie zisku pri výrobe dvoch druhov paliva. Zostavenie optimálneho plánu výroby pre získanie maximálneho zisku z jeho predaja. Stanovenie základného plánu prepravy tovaru metódou minimálnych nákladov a pomocou Excelu.
test, pridaný 12.11.2014
Algoritmus na riešenie úloh lineárneho programovania simplexovou 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.
semestrálna práca pridaná 21.03.2012
Stanovenie pomocou simplexovej metódy výrobného plánu na dosiahnutie maximálneho zisku tak, aby boli suroviny typu II plne spotrebované. Riešenie úloh lineárneho programovania pomocou tabuľkového procesora Excel, zostavenie algoritmu.
semestrálna práca pridaná 30.09.2013
Štúdium matematicko-ekonomického modelu spoločnosti s cieľom vyvinúť optimálne riešenie výroby produktov pre maximalizáciu zisku a minimalizáciu nákladov pomocou optimalizačných metód a programu MS Excel a sady nástrojov Matlab.
práca, pridané 15.06.2014
Prehľad algoritmov pre metódy riešenia problémov lineárneho programovania. Vývoj algoritmu pre tabuľkovú simplexovú metódu. Zostavenie výrobného plánu, v ktorom bude dosiahnutý maximálny zisk z predaja. Zostavenie matematického modelu problému.
ročníková práca, pridaná 21.11.2013
Stanovenie počtu a typu traktorových a automobilových tlmičov výfuku, ktoré by mala spoločnosť vyrábať za účelom maximalizácie zisku. Riešenie úlohy lineárneho programovania grafickou a simplexnou metódou pomocou tabuľkového editora Excel.
semestrálna práca pridaná dňa 04.09.2013
Optimalizácia nákladov na dodávku produktov spotrebiteľom. Opis dopravného problému, všeobecný pohľad na riešenie, zovšeobecnenie; zmysluplná a matematická formulácia problému, riešenie pomocou MS Excel: výpis programu, analýza výsledkov.
ročníková práca, pridaná 02.04.2011
Matematické základy optimalizácie. Vyhlásenie problému optimalizácie. Metódy optimalizácie. 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, úlohy.
abstrakt pridaný dňa 21.08.2008
Stanovenie množstva nakúpených surovín na výdaj výrobkov 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 tabuľkovom procesore Excel a používanie nástrojov VBA.
Na riešenie problémov lineárneho programovania simplexná metóda v prostredí MS Excel sa bunky plnia zdrojovými údajmi v režime čísel a vzorcov matematického modelu.
MS Excel umožňuje získať optimálne riešenie bez obmedzenia dimenzie sústavy nerovností účelovej funkcie.
Vyriešme problematiku vyrábaných produktov simplexnou metódou pomocou doplnku „Hľadať riešenie“ v MS Excel.
1. Vyplňte tabuľku Excel v číselnom režime (obr. 1)
2. Vyplňte tabuľku Excel v režime vzorcov (obr. 2)
Obr. 1 Tabuľka v číselnom režime
Obr. 1 Tabuľka v režime vzorca
Tu: B9: C9 - výsledok (optimálny počet produktov každého typu);
В6: С6 - koeficienty účelovej funkcie;
B10 je hodnota účelovej funkcie;
В3: С5 - koeficienty obmedzení;
D12: D14 - pravá strana obmedzení;
B12: B14 sú vypočítané (skutočné) hodnoty ľavej strany obmedzení.
Vyriešme problém pomocou príkazu Údaje / Hľadať riešenie. Na obrazovke sa zobrazí dialógové okno Nájsť riešenie.
V poli Nastaviť funkciu cieľa sa zobrazí odkaz na aktívnu bunku, t.j. na B10. Navyše, toto prepojenie je absolútne. V časti Equal nastavte prepínač na maximálnu (minimálnu) hodnotu v závislosti od funkcie cieľa. Obmedzenia sa nastavujú pomocou tlačidla Pridať, ktoré vyvolá dialógové okno Pridať obmedzenie na ich zadanie.
Vo vstupnom poli Odkaz na bunku: označuje adresu bunky obsahujúcej vzorec na ľavej strane obmedzenia. Potom sa zo zoznamu vyberie znamienko pomeru. Pole Obmedzenie obsahuje adresu bunky obsahujúcej pravú stranu obmedzenia. Kliknite na tlačidlo Pridať a opakujte až do ďalšieho obmedzenia. Po zadaní všetkých obmedzení kliknite na tlačidlo OK.
Keďže všetky premenné nesú podmienky nezápornosti, ich pozitivita sa nastavuje pomocou tlačidla Parametre v dialógovom okne Nájsť riešenie. Po kliknutí naň sa zobrazí okno Možnosti vyhľadávania riešení.
Začiarknite políčko Urobiť premenné bez obmedzení nezáporné a vyberte Metóda riešenia Hľadať riešenia lineárnych problémov pomocou simplexnej metódy. Kliknite na tlačidlo Nájsť riešenie.
Excel zobrazí okno s výsledkami vyhľadávania riešení so správou, že sa našlo riešenie alebo že nemôže nájsť vhodné riešenie.
Ak sú výpočty úspešné, Excel zobrazí nasledujúce súhrnné okno. Môžu byť ponechané alebo zlikvidované. Okrem toho môžete získať jeden z troch typov prehľadov (Výsledky , Udržateľnosť , Limity), čo vám umožní lepšie pochopiť získané výsledky vrátane hodnotenia ich spoľahlivosti.
Po nájdenom riešení sa v bunkách B9: C9 objaví optimálny počet produktov každého typu.
Pri ukladaní zostavy zvoľte - Správa o výsledkoch (obr. 3).
Zo správy je zrejmé, že zdroj 1 nie je plne využitý na 150 kg a zdroj 2 a 3 je plne využitý.
Výsledkom bol optimálny plán, v ktorom sa musia vyrobiť výrobky 1. typu v množstve 58 ks a výrobky 2. typu v množstve 42 ks. Zároveň je zisk z ich predaja maximálny a predstavuje 4660 tisíc rubľov.
Obr. 3 Správa o výsledkoch
1. Osobné a vysokorýchlostné vlaky, pozostávajúce z vyhradeného miesta na sedenie, oddielových a mäkkých vozňov, odchádzajú denne zo zriaďovacej stanice. Počet miest vo vozni s vyhradeným sedadlom je 54, v oddielovom vozni - 36, v mäkkom vozni - 18. V tabuľke je uvedené zloženie jednotlivých typov vlakov a počet vozňov rôznych typov, ktoré sú vo vozovom parku k dispozícii. Určte počet rýchlych a osobných vlakov, ktoré musia byť denne zostavené, aby sa maximalizoval počet prepravených cestujúcich.
Riešenie dopravných problémov
Prepravné úlohy sú úlohy stanovenia optimálneho plánu prepravy tovaru z daných východiskových miest do daných odberných miest.
| b 1 | b 2 | … | b k | … | b g | |
| 1 | } Súvisiace články Najnovšie články
Voľba redaktora
|
Pomer strán 1440 x 900
Rozlíšenia obrazovky monitora
Kedy potrebujem aktualizovať firmvér
Ako premeniť smartfón s Androidom na bezpečnostnú kameru
Ako vyzerá čínska klávesnica (história a fotografie)