Rezolvarea unei probleme de programare liniară folosind metoda grafică, metoda simplex și prin sarcina „căutare soluție” în Excel. kg de materii prime de primul tip, a. Rezolvarea problemei folosind Excel și metoda simplex

1. Transformă inegalitățile în egalități

2. Găsiți soluția de bază fezabilă inițială

3. Pe baza condiției de optimitate se determină variabila de intrare. Dacă nu există variabile de intrare, atunci procesul este finalizat.

4. Pe baza condiției de admisibilitate, selectați variabila exclusă

5. Calculați elementele noului rând de început

noua linie de conducere = linia curentă/element de conducere

6. Calculați elementele rândurilor rămase, inclusiv șirul z

rând nou = rând curent - coeficienții săi în coloana de început * rând de început nou

Să trecem la pasul 3.

Pentru confortul înregistrării procesului iterativ, scriem toate valorile într-un tabel Simplex.

2. Un exemplu de rezolvare a problemei lp folosind pachetul ms excel

Pentru multe probleme de optimizare, este convenabil să folosiți un model de programare liniară. Esența problemei este de a compila un sistem de inegalități care descrie constrângerile corespunzătoare problemei și specifică funcția de optimizare.

Pentru a găsi o soluție la astfel de modele, puteți folosi instrumentul MS EXCEL - CĂUTARE SOLUȚIE.

Să ne uităm la cum să creăm un model de programare liniară și să găsim soluția acestuia folosind un exemplu.

2.1. Enunțarea problemei

Două tipuri de piese (A și B) sunt prelucrate pe trei mașini, iar fiecare piesă este prelucrată pe toate mașinile. Cunoaștem timpul de procesare a pieselor pe fiecare mașină, timpul de funcționare al mașinilor pe parcursul unui ciclu de producție și profitul din vânzarea unei piese din fiecare tip (date din tabel). Întocmește un plan de producție care oferă cel mai mare profit.

2.2. Construirea unui model matematic

Să notăm cu x 1 și x 2 numărul de unități de piese de tipurile A și B planificate pentru producție. Atunci timpul de procesare x 1 al pieselor de tip A la prima mașină este 1 * x 1; x 2 părți de tip B, respectiv 2 * x 2. Timpul total de funcționare al mașinii I pentru producția numărului planificat de piese este egal cu x 1 + 2 * x 2, este limitat la 16 ore de funcționare a acestei mașini în timpul unui ciclu de producție. Prin urmare, inegalitatea trebuie satisfăcută:

x 1 +2*x 2<=16;

În mod similar, pentru mașinile II și III obținem următoarele inegalități, respectiv:

x 1 + x 2<=10;

3*x 1 + x 2<=24;

În plus, în sensul definiției valorilor introduse x 1 și x 2, trebuie îndeplinite următoarele condiții: x 1 >=0;

Astfel, obținem un sistem de inegalități numit sistem de constrângeri probleme:

Orice soluție (x 1; x 2) a unui sistem de constrângeri se numește plan de producție sau plan admisibil pentru problemă.

Profitul din vânzarea x 1 unități de piese de tip A este egal cu 4. x 1, iar profitul din vânzarea a x 2 unități de piese de tip B este egal cu 2x 2. Profitul total din vânzarea produselor produse conform planului (x 1; x 2) este egal cu:

F(X 1 ; X 2 )=4x 1 +2x 2 (mii de ruble).

Funcția liniară F(X 1 ; X 2 ) numit funcția țintă sarcini.

În funcție de condițiile problemei, se cere găsirea unui plan (x 1; x 2) la care profitul să fie maxim.

Astfel, a fost construit un model matematic al problemei ca problemă de programare liniară:

F(X 1 ; X 2 )=4x 1 +2x 2 → max

Modelele de optimizare sunt folosite pentru a găsi răspunsuri la întrebări precum:

• Cum să creați un program pentru angajații centrului de apel, astfel încât să satisfacă cererile lor de concediu, să echilibreze orele suplimentare și să elimine sarcina non-stop?
• Ce oportunități de foraj petrolier ar trebui să utilizați pentru a vă maximiza veniturile, ținând în același timp toate riscurile sub control?
• Când ar trebui plasate noi comenzi în China și cum ar trebui să fie livrate pentru a minimiza costurile și pentru a satisface cererea așteptată?

Descărcați nota în sau format, exemple în format

Scopul optimizării este întotdeauna „maximizarea” sau „minimizarea”. Cea mai comună și mai bine înțeleasă formă de optimizare matematică este programarea liniară, o dezvoltare secretă a inginerilor sovietici la sfârșitul anilor 1930, care a devenit populară în timpul celui de-al Doilea Război Mondial. Apropo, cuvântul „programare” din această expresie este o relicvă a terminologiei militare din acea vreme și nu are nimic de-a face cu programarea computerelor.

Să începem cu exemplul preferat al economiștilor - arme și unt. Anul este 1941, sunteți proprietarul unei ferme franceze de lactate. Ziua mulgi vacile si produci unt, noaptea asamblezi automate. Scopul dvs. este profitul maxim pentru a produce mașini cât mai mult timp posibil. De la intermediarul de la Rezistență primești 195 de unități monetare pentru fiecare aparat (pentru a nu deranja Excel cu franci inexistenți, să presupunem că aceștia sunt dolari). Pentru fiecare baril de petrol de pe piață ești plătit cu 150 USD.

Condiții și restricții. Costul unui baril de petrol este de 100 USD, iar o mașină este de 150 USD. Bugetul lunar de producție - 1800 USD. Vă depozitați produsele într-un subsol de 21 de metri cubi. Mașina ocupă ½ m 3, un baril de ulei de 1½ m 3. Câte automate și barili de petrol trebuie să vinzi într-o lună pentru a obține profitul maxim?

Un program liniar este definit ca un set de soluții necesare pentru a optimiza un obiect în lumina unor condiții, în care atât obiectul, cât și condițiile sunt liniare. Puteți adăuga, scădea, înmulți prin constante, dar nu puteți utiliza funcții neliniare pentru a rezolva, cum ar fi înmulțirea variabilelor (nu puteți înmulți prin unt), pătrarea sau bucle logice, cum ar fi IF.

Să ne imaginăm zonele valori acceptabile grafic. În primul rând, numărul de pistoale și butoaie de petrol trebuie să fie nenegativ. În al doilea rând, maximul pe care îl puteți produce este de 1800 USD/150 USD = 12 mașini sau 1800 USD/100 USD = 18 barili de petrol (Fig. 1). Denumirea generală a acestui triunghi este politop– o figură cu laturile plate (de exemplu, un diamant). În al treilea rând, subsolul poate găzdui nu mai mult de 21/(½) = 42 de mașini sau 21/(1½) = 14 barili de petrol (Fig. 2).

Pentru a găsi raportul ideal de mașini și butoaie, introducem conceptul în problemă linii de nivel de funcție. O astfel de linie în modelul de optimizare include valori care aduc același profit. Linia de nivel poate fi specificată prin ecuația:

(195 – 150) * N mașini + (150 – 100) * N barili de petrol = C,

unde C este o constantă.

De exemplu, cu C = 450, linia va trece prin coordonatele (0;10) și (9;0). Grafic, ideea de maximizare a profitului se realizează prin deplasarea liniei de nivel paralel cu ea însăși în direcția creșterii valorilor de-a lungul axelor X și Y (Fig. 3). Este curios că pentru un politop optimul se află întotdeauna la unul dintre vârfuri (sau nu există deloc o soluție unică). Algoritmul metodei simplex se bazează pe această proprietate. Rezolvarea problemei în Excel începe cu crearea unei zone de model (Fig. 4). Formula pentru funcția obiectiv din celula B1 =SUMPRODUCT(C4:D4;C10:D10).

Orez. 3. Linie de nivel și funcție pentru optimizarea profitului: a) o poziție inițială arbitrară; b) linie de nivel în poziție optimă

Sunteți gata să apăsați butonul. DATE –> Găsirea unei soluții. (Dacă nu vedeți acest buton, instalați programul de completare Find Solution; consultați Capitolul 1). În fereastra care se deschide Opțiuni de căutare a soluției setați opțiunile evidențiate și apăsați Găsiți o soluție.

Orez. 5. Fereastra Găsirea unei soluții

Excel va actualiza foaia și va adăuga rezultatele calculului la ea (Fig. 6).

Ce se întâmplă dacă adăugați neliniaritate? Să presupunem că intermediarul dvs. oferă 500 USD dacă numărul de mașini pe lună este mai mare de 5. Doar adăugați o funcție IF la celula de profit (B1). Acum funcția obiectiv arată astfel: =SUMPRODUCT(C4:D4,C10:D10)+IF(C4>5,500,0). Clic Găsirea unei soluții. Eșec, Excel raportează o eroare - condițiile de liniaritate nu sunt îndeplinite (Figura 7).

Puteți încerca algoritmul evolutiv, care funcționează cel mai bine cu modele neliniare și practic nu are restricții în alegerea funcțiilor. Lucrarea algoritmului evolutiv repetă în anumite moduri principiile muncii evoluției biologice:

• generează un pool de soluții inițiale (ceva ca un pool genetic) de diferite grade de probabilitate;
• fiecare decizie are un anumit nivel de aptitudine pentru supraviețuire;
• soluțiile sunt înmulțite prin transfer încrucișat, adică componentele lor sunt selectate dintre două sau trei solutii existenteși apoi combinate;
• soluțiile existente se transformă în altele noi;
• are loc căutare locală, timp în care se generează soluții noi în apropierea celei mai bune în acest moment decizii într-o populație;
• are loc selecția: soluțiile candidate nereușite alese aleatoriu sunt aruncate din fondul genetic.

Din păcate, există încă unele probleme cu algoritmul evolutiv:

• Timpul de operare este semnificativ mai lung decât în ​​cazul metodei simplex
• Nu există nicio garanție că va găsi solutie optima. Tot ce poate face este să controleze cea mai buna solutieîn populație până la expirarea timpului sau la schimbarea populației în într-o măsură suficientă pentru a continua sau nu opriți forțat „Căutați o soluție” apăsând butonul ESC.
• Căutarea evolutivă a unei soluții funcționează destul de lent. Și dacă gama de valori acceptabile este complexă, deseori înjură, negăsind nici măcar un loc de unde să plece.
• Dacă doriți ca algoritmul evolutiv să funcționeze bine în Excel, va trebui să definiți limite dure pentru fiecare variabilă de decizie. Chiar dacă soluția dvs. este mai mult sau mai puțin nerestricționată, aveți totuși nevoie de restricții.

Ținând cont de ultimul punct, pentru a rezolva problema cu mașinile și untul trebuie să adăugați o constrângere ca ambele soluții să nu fie mai mari de 25 (Fig. 8). După setarea parametrilor de bază ai modelului, faceți clic pe butonul Opțiuni. După ce a lucrat aproximativ un minut, algoritmul evolutiv a produs soluția așteptată - 6 mașini și 9 barili de petrol. Deoarece este optim să faci doar trei utilaje fără bonus, iar bonusul se plătește atunci când sunt produse mai mult de 5 utilaje, este evident că alegerea optimă ar fi 6 utilaje.

Să luăm acum în considerare mai multe exemplu complex. Lucrezi pentru o companie care produce suc de portocale amestecând sucuri naturale de diferite soiuri (Fig. 9). Pentru a vă asigura că sucul dumneavoastră îndeplinește cele mai sofisticate cerințe:

• raportul Brix/aciditate ar trebui să rămână între 11,5–12,5;
• nivelul de aciditate ar trebui să rămână între 0,75–1%;
• nivelul de astringență ar trebui să fie de 4 sau mai mic;
• culoarea ar trebui să fie între 4,5–5,5.

Șeful vă spune că se așteaptă ca cererea să fie de 600.000 de galoane de suc pe lună pentru ianuarie și februarie și de 700.000 de galoane pentru martie. Și totuși, există un acord cu statul Florida care oferă scutiri de taxe cu condiția ca compania să cumpere cel puțin 40% din suc în fiecare lună de la fermierii care cultivă soiul Valencia. Acordul trebuie respectat.

Orez. 9. Lista de caracteristici pentru producerea sucului de portocale proaspăt stors (pentru a mări imaginea, faceți clic pe ea clic dreapta mouse-ul și selectați Deschide imaginea într-o filă nouă)

Crea model de optimizare(Fig. 10). Formulele pot fi studiate pe foaia corespunzătoare a fișierului Excel atașat. Clic Găsirea unei soluții, și introduceți parametrii (Fig. 11). Clic Găsiți o soluție.

Orez. 11. Fereastra umplută Găsirea unei soluții pentru sarcina de amestecare

Lansare Găsirea unei soluții, găsești cost optim achiziții - 1,23 milioane USD (Fig. 12). Vă rugăm să rețineți că comenzile Florida Valencia sunt procesate prin limita inferioară conditii. Evident, această afacere nu este cea mai buna varianta, dar trebuie să te împaci cu asta. Al doilea cel mai popular soi este Verna din Mexic, care este al naibii de ieftin, dar la fel de groaznic.

Prezinți rezultatele calculului șefului tău, dar acesta rămâne nemulțumit și spune că nu vrea să treacă peste bugetul de 1,17 milioane de dolari Te întorci la computer și începi să înțelegi că costul a încetat să mai fie o funcție obiectivă. Acum aceasta este o condiție! Care este scopul? Puteți reduce costurile de achiziție doar prin relaxarea cerințelor de calitate. Decizi să le formulezi în termeni de reducere procentuală și faci model nou(Fig. 13).

Vă rugăm să rețineți că celulele B26:29 și F26:F29 conțin acum mai degrabă formule decât constante. Noul tău obiectiv este de a minimiza degradarea procentuală în celulele G26:G29. Mai precis, ați dori să minimizați maximul valorilor din celulele G26:G29. Cu toate acestea, dacă puneți formula =MAX(G26:G29) în celula D2, modelul nu va funcționa. Permiteți-mi să vă reamintesc că funcția MAX nu este liniară. Un mic truc este disponibil aici - puteți intra condiție suplimentară la model: $G$26:$G$29<=$D$2 (рис. 14), а ячейку D2 оставить пустой. Т.е., ячейка D2 будет оптимизироваться не благодаря наличию в ней формулы, а последовательными циклами, запускаемыми этим дополнительным условием.

Clic Găsiți o soluție. Algoritmul simplex va încerca să împingă D2 mai aproape de 0 ca funcție obiectiv a modelului, în timp ce constrângerile de aromă și culoare vor încerca să-l mărească cât mai mult posibil pentru a obține un amestec funcțional. Unde se oprește valoarea lui D2? Cea mai mică valoare posibilă este procentul maxim de patru redus în intervalul G26:G29. Vedem (Fig. 15, celulele C26:E29) că reducerea costurilor cu 5% a necesitat depășirea limitelor de calitate în toți cei patru parametri.

I-ai prezentat datele șefului, care a văzut că reducerea costurilor cu 5% nu merită să reducă calitatea sucului, așa că a fost de acord cu prima ta variantă. Dar când ai adus-o la departamentul de aprovizionare, angajații au fost revoltați. Cum ar putea fi împărțite proviziile așa!? Furnizorii insistă să vă măriți loturile: nu mai mult de 4 furnizori pe lună! Și te așezi la noul model. Din păcate, nu puteți utiliza funcțiile IF sau COUNT deoarece doriți să rămâneți în modelul liniar. Prin urmare, trebuie să recurgeți din nou la trucuri (Fig. 16). Adăugați regiunea C33:E43 la model, pe care o definiți ca binar (valorile din acesta pot fi doar 0 sau 1) și o lăsați goală. Și, de asemenea, zona F33:H43, unde fiecare celulă este egală cu produsul valorii din zonele C33:E43 cu G5:G15. La parametri Găsirea unei soluții(Fig. 17) adăugați o altă condiție $C$15:$E$15<= $F$33:$H$43 и еще одну область переменных – $C$33:$E$43.

Cum va funcționa algoritmul de optimizare în acest caz? Când începe, toate valorile din zonele C5:E15, C33:E43 și F33:H43 sunt zero. Să presupunem că algoritmul încearcă să plaseze valoarea 240 în celula C7. Condiția C7 va funcționa<= F35, которое приведет к увеличению значения в F35, которое, в свою очередь, определяется формулой F35 = C35*$G7. Поскольку G7 – константа, а С35 – бинарная переменная, последней присваивается значение 1. Условие С7 <= F35 выполнено, т.к., 240 <= 1200. Таким образом вы моделируете неудобное условие «если… то»: «если заказ сделан, то бинарная переменная включается».

Clic Găsiți o soluție. Veți observa că problema durează mai mult să se rezolve din cauza adunării variabilelor binare. Dacă dintr-un motiv oarecare Găsirea unei soluții prea mult timp în căutarea dvs., puteți apăsa oricând ESC și puteți vedea cea mai bună soluție găsită în acest moment.

Practic, ești deja un specialist destul de avansat în domeniul programării liniare. Dar, dacă ai un gust pentru asta și îți place să te ocupi de modele de complexitate crescândă, iată încă două exemple uimitoare.

Inginerii au raportat că au apărut noi „reductori de aciditate” în producție. Această tehnologie este capabilă să neutralizeze 20% din acidul din sucul care curge prin dispozitiv. Acest lucru nu numai că reduce procentul de acid, dar crește și indicele Brix/aciditate cu 25%. Dar „reductorul” necesită energie și consumabile care costă 20 de dolari la 1.000 de galoane de suc. Nu toate sucurile provenite de la furnizori trebuie supuse acestui proces, cu toate acestea, dacă o expediție dintr-o comandă este efectuată printr-un schimbător de ioni, întregul volum trebuie procesat. Construiți un model care implică un schimbător de ioni pentru a reduce costurile.

Problema cu noua regulă este că modalitatea naturală de modelare a acesteia este neliniară, ceea ce va duce la un algoritm de optimizare lent. Dar, ca și în exemplul anterior, puteți introduce o variabilă binară în zona C25:E35, care ar fi „activată” dacă este necesar să se reducă aciditatea lotului (Fig. 18). Deoarece nu puteți utiliza produsul „indicator de reducere a acidității (binar) * volum lot”, creați zona C37:E47, care vă va fi utilă pentru egalizarea volumelor care trebuie reduse în aciditate, fără a participa direct la formulele acestor volumele în sine. Deci, zonele C25:E35 și C37:E47 nu conțin formule. În zona G25:I35 se folosesc formulele =C25:E35*G5:G15 (aceasta este limitarea lotului prin volumul total disponibil de suc), iar în zona K25:M35 =E5:E15-GG5:15 *(1-E25:E35). Această condiție va funcționa numai dacă lotul este supus reducerii acidității.

De asemenea, în modelul „reductor de aciditate”, formulele din celulele C16:E16 au fost modificate (acum iau în considerare costul reducerii acidității folosind formula „indicator (binar) * volum lot * 20 USD) și în celulele C50:E51 (acum iau in calcul cresterea coeficientului Brix/aciditate cu 25% si reducerea aciditatii cu 20% pentru loturile procesate). În parametri Găsirea unei soluții au apărut noi variabile şi condiţii suplimentare (Fig. 19). Din păcate, apăsând butonul Găsiți o soluție, veți afla că suplimentul Găsirea unei soluții nu poate face față sarcinii (Fig. 20). Modelul a devenit prea complex.

Orez. 19. Opțiuni Găsirea unei soluțiiîn modelul cu „reductor de aciditate”

Orez. 20. Găsirea unei soluții nu face față sarcinii

Trebuie să descărcați și să instalați OpenSolver(cum se face acest lucru, vezi capitolul 1). OpenSolver va „prelua” setările tocmai introduse în fereastră Găsirea unei soluții. Deci doar apăsați butonul Rezolvator. Soluția rezultată – 1.235.927 USD – este cu peste 100.000 USD mai bună decât minimul anterior – 1.338.913 USD.

Pana acum am presupus ca produsele furnizate aveau exact parametrii specificati. Este rezonabil să presupunem că acești parametri sunt supuși variațiilor, caracterizate prin abaterea standard (Fig. 21; vezi pentru mai multe detalii). Cea mai cunoscută și utilizată distribuție a unei variabile aleatoare este distribuția normală, altfel cunoscută sub numele de curba clopot. Să spunem, în cazul sucului din Egipt, raportul mediu Brix/aciditate ar fi 13, iar abaterea standard (numită și abatere standard) ar fi 0,9 (Figura 21). În acest exemplu, 13 este centrul distribuției de probabilitate, 68% dintre comenzi vor fi în ±0,9 din 13 și 95% vor fi în ±1,8 din 13.

Scopul dvs. este de a propune un plan de amestecare care costă mai puțin de 1,25 milioane USD care să răspundă cel mai bine așteptărilor de calitate, în lumina variabilității ofertei.

Folosim media și abaterea standard a caracteristicilor pentru a aplica simularea Monte Carlo (dacă ați auzit acest nume pentru prima dată, vă recomand). În această metodă, în loc să includă parametrii de distribuție (media și abaterea standard) direct în model, un număr mare de scenarii sunt create pe baza acelor parametri de distribuție.

Un scenariu este un răspuns posibil la întrebarea: „Dacă acestea sunt distribuții bazate pe statistici, cum ar arăta o anumită comandă?” Fiecare scenariu include patruzeci de parametri pentru zece soiuri de suc (Fig. 22). Pentru a obține un astfel de parametru, utilizați funcția NORM.REV (pentru mai multe informații despre funcție, consultați). De exemplu, în celula B33, raportul Brix/aciditate pentru Hamlin este dat de =NORM.REV(RAND();H5;N5). Introduceți formule similare în zona B33:СW76, generând 100 de scenarii. Găsirea unei soluții nu va putea lucra cu aceste formule, deoarece sunt neliniare, așa că copiați-le în clipboard și lipiți-le, ci ca valori.

Scopul este de a minimiza valoarea din celula D2. Adică, găsiți o soluție care să reducă cel puțin limitele de calitate pentru 100 de scenarii. Ca și în exemplele din fig. 13–15, celula D2 nu are o formulă. Optimizarea se realizează prin setarea parametrilor în fereastră Găsirea unei soluții. Tot ce este necesar este să plasăm limite de calitate în toate scenariile, nu doar valorile de performanță așteptate. Deci, în raportul Brix/aciditate adăugați termenii B78:CW80 >= B26 și =< F26, затем проделываете то же самое с кислотностью, вяжущей составляющей вкуса и цветом (рис. 24). Нажмите Găsiți o soluție. Soluția va fi găsită destul de repede. Dacă ați generat singur valorile aleatoare în loc să le utilizați pe cele din fișierul de descărcare, soluția dvs. poate varia. Pentru suta de scenarii ale mele, cel mai bun lucru pe care l-am putut obține a fost o schimbare de 133% a calității.

Orez. 24. Configurare Găsirea unei soluții pentru un model cu caracteristici variabile

Dacă doriți să vă extindeți cunoștințele de programare liniară, vă recomand cartea de modelare a optimizarii AIMMS. Nu rata cele două capitole despre trucuri și sfaturi - sunt cu adevărat geniale.

Scrisă pe baza cărții lui John Foreman. – M.: Editura Alpina, 2016. – P. 129–186. În ceea ce privește secretul dezvoltării și al Doilea Război Mondial, aceasta pare a fi părerea personală a autorului cărții. Vezi Wikipedia. – Nota Baguzina.

Problema 1 (distributivă)

La întreprindere, 4 tipuri de produse pot fi produse pe 3 mașini interschimbabile separate.

Cunoscut:

· Sarcina de producție pentru producerea diferitelor tipuri de produse în perioada planificată

• · Fond pentru timpul de lucru efectiv al echipamentelor în perioada planificată - ;
• · Standarde pentru costul timpului mașinii pentru producerea unei unități de producție - ;
• · Profit in rub. din vânzarea unei unităţi de produs produsă pe cutare sau cutare echipament - .

Informațiile inițiale sunt afișate în tabelul din formularul următor.

Tabelul 1. Date inițiale

Problema necesită găsirea unui plan pentru distribuirea unei sarcini de producție pentru producția de produs între performeri

în care sarcina ar fi finalizată cu profitul total maxim din vânzările de produse.

SOLUŢIE

Dezvoltarea unui model economic și matematic.

Variabilele cerute caracterizează volumul producției de către antreprenor.

Apoi matricea variabilelor cerute

caracterizează planul de repartizare a sarcinii de producție pentru producția de produs între executanți.

Funcția obiectivă

caracterizarea profitului total din vânzarea tuturor produselor trebuie maximizată.

Restricțiile privind disponibilitatea și utilizarea timpului de lucru efectiv al artiștilor executanți vor lua forma unui sistem de inegalități liniare (2):

Acest sistem de restricții caracterizează condiția ca cheltuiala totală a timpului de lucru efectiv de către fiecare executant în perioada planificată pentru producerea tuturor tipurilor de produse să nu depășească fondul de timp. Astfel, ca urmare a rezolvării problemei, fiecare executant își va primi propria sarcină, în funcție de capacitățile sale. Dacă o variabilă de echilibrare capătă o valoare în rezolvarea unei probleme, ea va caracteriza timpul de lucru efectiv subutilizat al unuia sau altuia executant, care în condiții de producție poate fi folosit pentru a produce produse peste sarcină.

Următorul bloc de restricții ar trebui să reflecte condiția îndeplinirii obligatorii a obiectivului general de producție pentru producția de produse după tip și va fi reprezentat de un sistem de ecuații liniare (3):

Condiție pentru variabile nenegative:

Să aducem problema în formă canonică, pentru aceasta adăugăm variabile la inegalități (2), și adăugăm 4 baze artificiale la egalități (3). Ca rezultat, scriem modelul matematic al problemei în formă canonică:

Metoda simplex

Să rezolvăm această problemă folosind metoda simplex completând tabelul. Soluția necesită mai multe iterații. Să o arătăm.

Tabelul 1

Coeficienții funcției obiectiv sunt introduși în linia de sus a tabelului, a doua linie este numele tuturor necunoscutelor incluse în ecuațiile simplex. Prima coloană din stânga conține coeficienții funcției obiectiv, care corespund necunoscutelor de bază incluse în programul original (scrise în coloană). Următoarea, a treia coloană din primul tabel simplex este completată cu valorile necunoscutelor de bază. Urmează coloanele care reprezintă vectorii de condiție. Numărul lor este 19. În următoarea, prima coloană după matricea condițiilor, sunt scrise sumele tuturor elementelor din rânduri. Coloana înregistrează coeficientii de la împărțirea elementelor coloanei finale B în elementele unei anumite coloane, o matrice de condiții. Deoarece avem o bază artificială, în linia indexului vor fi două calcule, în primul dintre ele, ținând cont de variabile, iar în al doilea doar baza artificială. Deoarece avem o problemă de maximizare, este necesar să derivăm baze artificiale din bază. În a doua linie de index selectăm cel mai mare scor pozitiv. Aceasta este prima noastră coloană. Să găsim relații de valoare

Şi. Din aceste rapoarte îl selectăm pe cel mai mic, pentru noi acesta este al patrulea rând, pentru care raportul estimat este egal cu 1300. Selectați rândul. Ultima coloană este coeficientul cu care fiecare element al rândului este înmulțit în timpul recalculării. Se obține prin împărțirea elementelor coloanei selectate la elementul cheie, care se află la intersecția coloanei selectate și a rândului, pentru noi este 1. Facem recalcularea pentru toate elementele neselectate, care se efectuează ca urmează: din elementul recalculat scădem elementul rând cheie, înmulțit cu coeficientul rândului recalculat: și așa mai departe pentru toate elementele. Din bază derivăm o bază artificială, introducând în același timp o variabilă în bază.

Ultimele două linii sunt linii index în care sunt recalculate valorile funcției obiectiv, precum și întreaga linie index, când toate elementele sunt pozitive sau zero - problema va fi rezolvată.

Să o arătăm.

Tabelul 2

Să selectăm coloana cu variabila. Găsim rapoartele estimate, din care selectăm cel mai mic - acesta este 550. Deducem o variabilă artificială din bază și, în același timp, introducem o variabilă în bază. Când o bază artificială este derivată din bază, coloana corespunzătoare este eliminată.

Tabelul 3

Să selectăm coloana. Cel mai mic raport estimat, 600, se găsește în al șaselea rând. Din bază derivăm o bază artificială, introducând o variabilă în bază.

Tabelul 4

Să selectăm coloana cu variabila. Cel mai mic raport estimat, 28,57, se află în primul rând. Deducem o variabilă din bază și introducem o variabilă în bază.

Tabelul 5

Să selectăm coloana cu variabila. Cel mai mic raport estimat, 407,7, se află în al treilea rând. Deducem o variabilă din bază și introducem o variabilă în bază.

Tabelul 6

Să selectăm coloana cu variabila. Cel mai mic raport estimat, 344,3, se găsește în al șaptelea rând. Din bază derivăm o bază artificială, introducând în același timp o variabilă în bază.

Tabelul 7

Să selectăm coloana cu variabila. Cel mai mic raport estimat, 3,273, se găsește în al doilea rând. Deducem o variabilă din bază și introducem o variabilă în bază.

Tabelul 8

Să selectăm coloana cu variabila. Cel mai mic raport estimat, 465, se găsește în al șaptelea rând. Deducem o variabilă din bază și introducem o variabilă în bază.

Tabelul 9

Să selectăm coloana cu variabila. Cel mai mic raport estimat, 109, se află în al treilea rând. Deducem o variabilă din bază și introducem o variabilă în bază.

Tabelul 10

Să selectăm coloana cu variabila. Cel mai mic raport estimat, 10, se află în primul rând. Deducem o variabilă din bază și introducem o variabilă în bază.

Tabelul 11

Să selectăm coloana cu variabila. Cel mai mic raport estimat, 147, se află în al doilea rând. Deducem o variabilă din bază și introducem o variabilă în bază.

Tabelul 12

Să selectăm coloana cu variabila. Cel mai mic raport estimat, 367, se află în al cincilea rând. Deducem o variabilă din bază și introducem o variabilă în bază.

Tabelul 13

Să selectăm coloana cu variabila. Cel mai mic raport estimat, 128, se află în al patrulea rând. Deducem o variabilă din bază și introducem o variabilă în bază.

Tabelul 14

Deoarece nu există estimări negative în linia indicelui, se obține un plan optim în care volumul producției este reprezentat de matrice

în același timp, profitul este maxim și se ridică la 17.275,31 ruble.

Rezolvarea unei probleme folosind Excel

Modelul matematic al problemei trebuie transferat la ET EXCEL. Pentru a face acest lucru:

• · Luați în considerare organizarea datelor inițiale ale modelului (coeficienți ai funcției obiective și restricții), oferindu-le denumiri clare.
• · Rezervați variabilele independente ale modelului matematic în celule separate.
• · Într-una dintre celule, creați o formulă care definește funcția obiectiv.
• · Selectați celule și plasați în ele formule care corespund părților din stânga constrângerilor.
• · Introduceți elementul de meniu „Căutare soluție”, introduceți datele necesare și obțineți soluția optimă a problemei.
• · Analizați soluția rezultată și rapoarte.

Să luăm în considerare succesiunea de acțiuni pentru implementarea acestor etape de rezolvare a unei probleme folosind EXCEL.

Să creăm un tabel pentru introducerea datelor inițiale.

Vom introduce datele inițiale în formularul creat.

Coeficienții funcției obiectiv, care exprimă profitul din producerea unei unități de produs de fiecare tip (profit unitar), se scriu în celulele B6: M6.

Coeficienții de constrângere a resurselor care determină necesitatea fiecărui tip de resursă de a produce o unitate de ieșire sunt localizați în celulele B9:M15. Celulele P9:P15 conțin partea dreaptă a restricțiilor de resurse. Celulele B3:M3 sunt rezervate variabilelor independente ale problemei - volumele necesare de producție.

În celula N7, introduceți formula funcției obiectiv utilizând comanda de inserare a funcției SUMPRODUCT:

De asemenea, completăm restricțiile din partea dreaptă.

După aceasta, puteți începe să căutați o soluție. Pentru a rezolva problemele de optimizare în EXCEL, utilizați comanda CĂUTARE SOLUȚIE din meniul SERVICE.

Această comandă operează cu trei componente principale ale modelului optimizat construit în ET:

• · O celulă care conține funcția obiectivă a problemei.
• · Celule editabile care conțin variabile independente.
• · Celule care conțin partea stângă a restricțiilor asupra resurselor disponibile, precum și restricții simple asupra variabilelor independente.

Să luăm în considerare succesiunea de introducere a acestor componente.

Cursorul se află în celula N7 și comanda SERVICE - Căutați o soluție. Pe ecran va apărea o casetă de dialog.

În fereastră, completați câmpul Setați celula țintă, care ar trebui să conțină adresa $N$7. Apoi, setați butonul pentru a căuta valoarea maximă. În câmpul Modificare celule, introduceți adresele variabilelor dorite $B3:$M3. Apoi ar trebui să introduceți restricții folosind butonul Adăugare.

Acum că au fost setate toate restricțiile pentru găsirea soluției optime, putem apăsa butonul:

După aceasta vom obține o soluție la problemă.

Dacă calculele au avut succes, după finalizarea căutării unei soluții, valorile vor fi inserate în tabel și puteți specifica și Tipul de raport - Rezultate, în urma căruia putem obține următorul raport. lucrător timp echipament profit

În consecință, soluția în EXCEL este aceeași cu metoda SIMPLEX, ceea ce înseamnă că problema luată în considerare a fost rezolvată corect.

Rezolvarea ZLP folosind metoda simplex folosind tabele EXCEL

Lăsați ZLP-ul original să fie redus la forma canonică, iar sistemul său de restricții să aibă o formă preferată. De exemplu, pentru „Problema privind utilizarea materiilor prime” modelul matematic de tipul corespunzător va fi următorul:

Primul tabel simplex din foaia de lucru EXCEL va arăta ca (Fig. 10):

Presupunând că studentul este familiarizat cu algoritmul metodei simplex tabulare, vom descrie principalele etape ale implementării acesteia folosind tabelele EXCEL.

Etapa 1. Selectați coloana și rândul de activare și evidențiați elementul de activare (vezi Fig. 11).

Etapa 2. Înlocuiți coloanele „Base” și „Cb” în noul tabel conform regulilor de completare a acestora.

Elementele liniei de autorizare sunt împărțite în elementul de autorizare și sunt scrise în rândul corespunzător numărului noului tabel:

, la i = r. (*)

Toate celelalte elemente ale noului tabel sunt calculate folosind formulele:

, la i ≠ r (**)

unde este un element al noului tabel simplex, o ij , - elementul tabelului simplex anterior, o rk- element de autorizare, o ik- elementul coloanei de rezoluție, o rj- elementul șirului de activare.

Nota . Pentru a folosi capacitatea EXCEL de a copia formule cu modificarea adreselor celulelor incluse în acestea, este recomandabil să programați formule (*) și (**) numai pentru celulele coloanei „B”, dând adrese absolute celulelor care nu se schimba. Datele formulei sunt apoi copiate în toate celulele rămase din fiecare rând al noului tabel.

Etapa 4. Elementele ultimului rând al noului tabel sunt completate fie folosind formule (**), fie conform regulii de completare a acestui rând.

Rezultatele calculelor din tabelele EXCEL pentru exemplul nostru sunt prezentate în Fig. 11, iar formulele utilizate în aceste calcule sunt prezentate în Fig. 12.

Akulich I.L. Programare matematică în exemple și probleme: Proc. manual pentru studenți la economie.

specialist. universități - M.: Mai sus. şcoală, 1986.-319 p., ill.

Sakovich V.A. Cercetare operațională (metode și modele deterministe): un ghid de referință.

- Mn.: Mai sus. scoala, 1984.-256p.

Taha H. Introducere în cercetarea operațională: în 2 cărți. Cartea 1. Pe. din engleză – M.: Mir, 1985.-479 p., ill.