Ce studiază programarea liniară? Metode neconvenționale
Programarea liniară reprezintă metode de rezolvare a unei anumite clase de probleme de găsire a valorilor extreme (verificare sau min). Ele se bazează pe soluția sistemului ecuații liniare, când dependența este strict funcțională. În model programare liniară se disting trei componente: functia tinta (maximizata sau minimizata), sistemul de restrictii si conditia de nenegativitate a variabilelor. Aparatul matematic al programarii liniare este folosit pentru rezolvarea problemelor economice, tehnice, militare etc.
În problemele de planificare optimă economică, soluția funcţie obiectivă se rezumă la găsirea maximului, de exemplu, a profitului, a volumului producției, a productivității muncii sau a minimului costurilor curente, a investițiilor de capital, a timpului de finalizare a lucrărilor etc.
În același timp, trebuie menționat că nu orice problemă de planificare optimă poate fi formulată și rezolvată în cadrul programării liniare. Pentru a face acest lucru, trebuie îndeplinite patru condiții de bază.
- 1. Problema trebuie să fie clar formulată și cuantificată criteriul de optimitate, ceea ce nu este atât de ușor de realizat în practică. Performanța unei întreprinderi este judecată cel mai adesea după o serie de indicatori: volumul producției, gama și calitatea produselor, rentabilitatea producției etc. Alegerea unui criteriu poate fi departe de cea mai bună din punctul de vedere al altuia și invers. .
- 2. Important parte integrantă Problemele de programare liniară sunt restrictii, legate de resursele disponibile, nevoi sau alți factori. Într-o economie reală nu este întotdeauna posibil să se ia în considerare și interacțiunea cantitate mare factori, prin urmare este compilat un model simplificat care ar reflecta mai îndeaproape natura reală.
- 3. Programarea liniară presupune o alegere a opțiunilor și este aplicabilă numai atunci când condițiile specifice problemei economice determină acest lucru libertatea de alegere.
- 4. Modelul trebuie să conţină numai ecuații liniare sau inegalități, aceste. toate variabilele problemei trebuie să fie la prima putere. Dependențe economice reale nu sunt întotdeauna liniare.
Ținând cont de condițiile relevante și aproximând situația economică pentru rezolvarea problemelor de programare liniară, este de asemenea necesar să se țină cont de faptul că impunerea asupra variabile restricțiile prea stricte pot duce la inconsecvența întregului sistem de condiții inițiale ale problemei.
Pe baza naturii problemelor rezolvate, metodele de programare liniară pot fi împărțite în două grupe.
- 1.Metode universale. Cu ajutorul lor, orice problemă de programare liniară poate fi rezolvată. Cel mai comun este metoda simplex, propus de J. Danzig, metoda de rezolvare a multiplicatorilor, dezvoltat de academicianul L.V Kantorovich în 1939, cu aproximativ 10 ani înainte de apariția sa în străinătate.
- 2. Metode speciale. Aceste metode sunt mai simple decât cele universale, dar nu sunt aplicabile pentru toate sarcinile. Acestea includ metoda de distributie a rezolva problema de transport, metoda termenului de rezolvare A. L. Lurie, metodă anuități diferențiale O. L. Brudno, metoda maghiară.
Un grup special de metode de programare liniară include metode aproximative, care se deosebesc de celelalte prin faptul că nu garantează o soluție strict optimă a problemei, dar sunt simple și bine adaptate calculelor manuale. Acestea includ metoda indexului, Metoda de aproximare Vogel etc.
Metoda simplex. Pentru a înțelege mai bine ideea metodei simplex, luați în considerare rezolvarea problemei de optimizare a utilizării resurselor pentru a obține un profit maxim.
Exemplul 2.21
Există o producție auxiliară care utilizează materiale rămase din producția principală. Pe această producție s-a lansat producția de uși de diverse sortimente: cu utilizarea sticlei (gama LAN) și fără ea (gama DV). Vânzările acestor produse sunt asigurate, i.e. produsele pot fi produse în orice raport, dar există o limitare a numărului de locuri de muncă în atelier și a resurselor de materiale de bază. Sarcina este de a planifica atelierul o producție lunară care să ofere cel mai mare profit posibil.
Sarcina nu stabilește condiții pentru utilizarea obligatorie a întregului volum de resurse. Este necesar ca consumul de timp de lucru să nu depășească limitele specificate.
Să luăm în considerare program 1, care presupune producerea doar a ușilor din gama DV, fără a folosi sticlă pentru realizarea acestora.
Dacă lansați doar TV, folosind toate resursele disponibile, atunci acestea vor fi suficiente pentru a lansa:
- - dupa timpul de lucru: 520/9,2 = 56 (bucati);
- - lemn: 24/0,3 = 80 (buc.).
Prin urmare, toate resursele sunt suficiente pentru a produce doar 56 de uși.
Profitul din această emisiune va fi de 168.000 de ruble. (56 3000).
Program 2 presupune producerea numai a ușilor din gama LAN. ÎN în acest caz, vor exista suficiente resurse pentru a elibera:
- - dar timp de lucru: 520/4 = 130 (bucati);
- - lemn: 24/0,6 = 40 (bucati);
- - sticla: 40/2 = 20 (buc.).
În mod optim, este posibil să se producă doar 20 de uși LAN, care este limitată de prezența sticlei. Acest lucru va lua 12 m de lemn din partea rămasă este posibil să producă încă 40 de bucăți. uși din gama DV. Pentru productie 20 buc. ICE și 40 buc. DV va fi cheltuită 448 de ore-om.
Profitul va fi de 160 de mii de ruble. (20 -2 + 40-3). Deci primul program este de preferat. Există și alte opțiuni.
Limitările acestei sarcini sunt:
Să desenăm o linie dreaptă pe grafic L u corespunzătoare primei inegalități: 
A doua inegalitate corespunde dreptei b 2:
A treia inegalitate din grafic corespunde unei drepte paralele cu axa absciselor L 3:
Deoarece planul de lansare trebuie să se bazeze pe toate cele cinci constrângeri ale problemei, zona soluțiilor fezabile în acest caz va fi un poligon umbrit.
Valoarea maximă a funcției obiectiv găsită în calculele anterioare va corespunde punctelor dreptei:
Poligonul limitează aria soluțiilor fezabile ale problemei. Din masa de soluții, trebuie să o alegeți pe cea în care valoarea profitului este maximă. În cazul nostru, ego-ul va fi punctul de intersecție al liniilor L (Şi 1 2 .
În continuare, sistemul de ecuații liniare este rezolvat: 
Rezolvând sistemul, obținem: 
deci profitul este:
Dacă linia dreaptă corespunzătoare funcției obiectiv (în metoda grafică) trece prin vârful poligonului, atunci problema are o singură opțiune optimă. Dacă coincide cu latura poligonului, atunci problema are multe soluții.
Soluția optimă trebuie să treacă fie printr-un vârf, fie printr-o latură a poligonului. Prin urmare, unul dintre vârfuri corespunde soluției optime, dar nu se știe la început care dintre ele.
Metoda grafică este simplă și vizuală, dar aplicarea ei este limitată.
Cu trei variabile, ar fi necesar să construim un poliedru într-un sistem de coordonate multidimensional. Cu patru sau mai multe variabile imagine grafică imposibil. Dar este posibil să ne imaginăm spațiul multidimensional în mod abstract. Dacă starea problemei este consecventă, atunci regiunea valori acceptabile(ODZ) formează un poligon convex în spațiul i-dimensional.
În acest caz, soluția optimă, dacă există, se realizează neapărat la un vârf al poliedrului (eventual la mai mult de unul).
Astfel, pentru a găsi o soluție la o problemă de programare liniară, este suficient să enumerăm opțiunile corespunzătoare vârfurilor poliedrului. Acestea se numesc planuri de referință. Cu toate acestea, în sarcini complexe pot fi prea multe dintre ele și determinarea planurilor de referință va necesita o cantitate imensă de calcule.
Metoda simplex vă permite să efectuați o căutare ordonată a vârfurilor unui poliedru.
Să ne uităm la succesiunea de calcule folosind metoda simplex folosind un exemplu.
Exemplul 2.23
Întreprinderea are trei grupe de echipamente (I, II, III), pe care sunt fabricate patru tipuri de produse (A, B, C, D). Toate produsele au vânzări nelimitate și, prin urmare, întreprinderea poate planifica un program de sortiment în intervalul dat.
Se aplică următoarele restricții:
- - disponibilitatea echipamentelor de bază;
- - standarde de timp pentru prelucrarea fiecărui tip de produs pe echipamentele fiecărei grupe;
- - suma profitului primit de întreprindere pe unitate dintr-un anumit tip de produs.
Trebuie să obțineți profit maxim.
Problema pe care o căutați: X (- ed. O; X 2 - ed. B; X 3 - ed. ÎN; X 4 - ed. G.
Profit maxim:
Restrictii:
Pentru a rezolva problema metoda simplex Transformăm toate inegalitățile în egalități. Pentru a face acest lucru, introducem trei variabile suplimentare nenegative în problemă: X 5 , x 6, x 7 și adăugați-le în partea stângă a inegalității:
În sensul lor economic, variabilele suplimentare nu sunt altceva decât timpul de funcționare neutilizat al echipamentelor specifice. Pentru a rezolva probleme folosind metoda simplex, sunt compilate tabele simplex speciale.
In cel mai mult linia de sus se înregistrează coeficienţii funcţiei obiectiv. Variabilele suplimentare corespund coeficienților zero. Echipamentele nefolosite nu generează profit. Aceiași indicatori zero sunt în coloană CU față de fiecare variabilă suplimentară.
În completarea liniei Zj - Cj au propriile lor caracteristici. În considerare Zj pentru fiecare coloană. Se obține ca sumă a produselor valorilor coloanei CU prin coeficienții coloanei corespunzători j. Deoarece în versiunea originală în coloană CU sunt 0, apoi valoarea Zj pentru toate coloanele este 0, iar valoarea Zj - Cj= -Cj. Prin urmare, în versiunea inițială, coeficienții funcției obiectiv sunt stabiliți aici cu semnul opus. Toate variabilele principale sunt setate la 0 și nu sunt incluse în baza problemei noastre. Variabilele suplimentare sunt egale cu valorile limită conform ecuațiilor originale. Aceasta înseamnă că nu se produce nimic, nu se utilizează resurse, iar valoarea funcției obiectiv este 0 (fără profit).
Rezolvarea problemei constă în introducerea secvenţială a principalelor variabile în plan până la obţinerea soluţiei optime. În acest caz, la fiecare etapă a calculului puteți introduce o singură variabilă. În acest caz, o altă variabilă este eliminată din bază, deoarece cu trei restricții nu pot exista mai mult de trei variabile în bază.
Întrucât problema este rezolvată de max profit, trebuie să începeți cu cel mai profitabil produs. În cazul nostru, aceasta este ed. D. Introdus în bază x 4. Să stabilim cum poate fi avută în vedere publicarea publicației. D. Depinde de cantitatea de resurse și de standardele de cost. Echipamentele din grupa I pot procesa 3000 de articole. (24.000/8), grupa II nu este implicată în producția de G, iar grupa III poate fi utilizată pentru procesarea a 30.000 de articole. Acceptăm cea mai mică dintre valori (3000 ed.), în tabelul din coloana „bază” X 4 pus la loc X 5 (echipamentul grupului I este egal cu zero, deoarece este complet utilizat). Numărul 8 la intersecție x AŞi X 5 numit element de ghidare sau general, cheie, permisiv.
Linia X 4 V masa noua obţinut prin împărţirea şirului de variabile de ieşire X 5 din tabelul precedent pe elementul de ghidare. În coloană CU Se introduce 0,8 - suma profitului pe unitatea de publicare. D. După aceasta, coloana „plan” este recalculată. Despre echipamentul grupei II ed. G nu este procesat, iar în noua versiune fondul de timp rămâne neschimbat (12.000 de minute).
Fondul de timp al echipamentelor grupei III se va reduce cu 3000 de minute (1 minut x x 3000 de piese), prin urmare 27.000 de minute rămân neutilizate. Următorul număr din coloana „plan” este de 2400 de ruble. (0,8 3000) - profit la această opțiune. După coloana „plan”, toate celelalte coloane sunt recalculate tabel simplex, cu excepția șirului de variabile de intrare. În același timp, trebuie avut în vedere că în coloanele tuturor variabilelor incluse în bază, la intersecția rândurilor și coloanelor cu același nume, există întotdeauna o unitate, iar elementele rămase ale coloanei sunt egale. la zero.
Prin urmare, puteți completa imediat coloanele x 4, x 6Şi x 7. Este recomandabil să recalculați conform „regula triunghiului”. Pentru a calcula orice coeficient în noua versiune, trebuie să găsiți trei numere în tabelul simplex: numărul care stă în locul acestui coeficient în versiunea anterioară;
- - un număr în aceeași linie a opțiunii precedente, dar în coloana variabilei de intrare;
- - un număr care se află în noua versiune în aceeași coloană cu coeficientul dorit, dar în rândul variabilei nou introduse (elementele acestui rând au fost deja calculate anterior).
Cele trei numere din tabel formează un triunghi dreptunghic. Pentru a determina coeficientul necesar, este necesar să se scadă produsul celorlalte două unghiuri din numărul situat la vârful unghiului drept.
De exemplu, pentru column.gr
Hai sa facem calculul:
pentru coeficientul pe linie 
pentru factor de linie x 7: 
Indicator de linie Zj - Cj poate fi calculată în două moduri:
a) conform formulei
b) conform regulii „triunghiului”:
Efectuăm calcule în mod similar pentru alte coloane ale noii versiuni a tabelului simplex.
Acum trebuie să aflăm dacă a doua opțiune este optimă sau poate fi îmbunătățită. Pentru a face acest lucru, uitați-vă la linie Zj - Cj. Dacă conține numere negative, atunci opțiunea poate fi îmbunătățită.
Cu 0,3 frecții. pentru fiecare unitate introdusă de produs, profitul va crește atunci când este introdus în numerele de bază! (ed. A) și cu 0,1 rub. la introducerea numerelor 3 (ed. B). Aceste cifre pot părea să contrazică datele originale: conform cărora ed. Și aduce 0,4 ruble. profit, B - 0,5 rub. Dar ideea este că în această etapă sarcină, introducerea acestor produse în plan va înlocui un anumit număr de produse introduse anterior. D, pentru a elibera echipamentele Grupului I pentru producția lor.
În etapa următoare este mai potrivit să se introducă X ((ed. A), întrucât corespunde celui mai mare valoare absolută număr negativ. Similar cu opțiunea anterioară, vom seta câte ed. Sau poate fi inclus în plan, ținând cont de faptul că acesta conține deja lansarea unei publicații. D. Pentru aceasta, împărțim numerele din coloana „plan” la coeficienții corespunzători (numai pozitivi) din coloana variabilei de intrare X ( iar din coeficientii obtinuti se selecteaza cel mai mic:
Rezultă că în noua optiune nu pot fi introduse în calcul mai mult de 4000 ed. Și, deoarece factorul limitator este echipamentul din grupa II. Prin urmare, variabila X ( va înlocui variabila din bază secolul x
La intersecția unei coloane x xși șiruri x 6 găsim și evidențiem elementul ghid - 3. În continuare, calculăm șirul variabilei introduse împărțind elementele șirului x 6 a versiunii anterioare pe elementul de ghidare. Apoi calculăm coloana „plan”:
Profitul cu noua opțiune va fi:
Conform regulii descrise, completați următoarele coloane. Privind prin linie Zj - Cj vedem că conține doar zerouri și elemente pozitive, ceea ce înseamnă că opțiunea 3 este soluția optimă și nu poate fi îmbunătățită. Include doar două tipuri de produse din patru. Variabilă x 3 corespunde cu ultima linie 0. Aceasta înseamnă că introducerea în plan într-o etapă ulterioară x 3 nu va crește profiturile, dar nici nu le va reduce, iar rezultatul rezultat va fi și el optim. Împărțirea numerelor din coloana „plan” la coeficienții coloanei x 3 iar alegand minimul dintre rezultatele obtinute, determinam ca aceasta variabila sa fie introdusa in baza in locul variabilei^. Ca urmare a transformărilor ulterioare, obținem un nou plan optim, care prevede lansarea a 2182 de ediții. O (X ()și 5455 ed. B (.g 3). Să găsim câteva opțiuni optime pentru a ne rezolva problema. Opţiune/: 50% din primul program și 50% din al doilea program:
Opțiunea II: 80% din primul program și 20% din al doilea program:
Aceste opțiuni oferă, de asemenea, un profit de 3.600 RUB.
Prezența mai multor planuri efective practic egale face posibilă determinarea unui număr de opțiuni intermediare, care în problemele economice oferă caracteristici suplimentare pentru analiza și selecția calitativă a celor mai acceptabile dintre ele.
La rezolvarea problemelor folosind metoda simplex, pot apărea cazuri de „degenerare”. La T restricții, un plan nedegenerat conține întotdeauna T variabile pozitive, iar restul p - t variabilele problemei nu sunt incluse în bază și sunt egale cu zero. Cu toate acestea, este posibil ca una sau mai multe dintre variabilele incluse în bază să fie egale cu zero, adică. prezența unuia sau mai multor zerouri în coloana „plan” a unui tabel simplex. Acest plan se numește degenera. Cu un plan degenerat, prezența numere negativeîn linie Zj - Cj nu înseamnă că următoarea opțiune va oferi o creștere a valorii funcției obiectiv. Poate rămâne neschimbat și în timpul nu numai unuia, ci și mai multor etape succesive. Asta se întâmplă buclă, care împiedică calculele ulterioare și nu poate fi depășită decât cu ajutorul unor tehnici speciale.
În prezent, la rezolvarea problemelor de optimizare, acestea sunt utilizate pe scară largă. calculatoare personale. În acest caz, sistemul este utilizat foi de calcul „Microsoft Excel».
Pentru a rezolva probleme de optimizare în MS Excel utilizați programul de completare Căutare soluție, care este apelat din elementul din meniul principal „Instrumente”.
Dacă în versiune Excela instalat pe computer, acest subelement din meniul „Serviciu” lipsește, trebuie să apelați elementul de meniu „Suplimente” și în lista propusă module suplimentare selectați „Căutați o soluție”.
Să ne uităm la exemplul de utilizare a acestui add-in, folosindu-l pentru a rezolva problema planificării producției.
Exemplul 2.24
Compania produce produse A, B, C, D din trei tipuri de resurse. Modelul matematic are următoarea vedere: verifica/(X) = 7,5i* 1 +3x 2+ 6dg 3 + 12.g 4 (funcția obiectivă - costul total al producției).
Restricțiile privind rezervele de resurse și nenegativitatea variabilelor sunt următoarele:
Să creăm un șablon în editor Excela.
Acum hai să-l punem această sarcină informatii numerice.
În celulele goale selectate (valorile funcției obiectiv și părțile stângi ale inegalităților) este necesar să introduceți formule care să afișeze conexiunile și relațiile dintre numere pe desktop.
Celulele C 4 - Fa sunt numite în Excela variabile (în modelul nostru acestea sunt variabile necunoscute). Căutarea unei soluții la schimbarea acestora va găsi valoare optimă funcția țintă. Valorile introduse inițial în aceste celule sunt de obicei zerouri (celulele necompletate sunt tratate implicit ca conținând valori zero).
Acum trebuie să introduceți formulele. În nostru model matematic funcția obiectiv este produsul dintre vectorul coeficienților și vectorul necunoscutelor. Într-adevăr, expresia poate fi luată în considerare
ca produsul vectorului (7, 5, 3, b, 12) de vectorul (.r, X 2, i-*, x A).
ÎN Excela Există o funcție SUMPRODUCT care vă permite să găsiți produsul scalar al vectorilor. Această funcție trebuie să apelați celula #5 și să setați adresele celulelor care conțin coeficienții ecuațiilor (în acest caz, C5) ca vectori care trebuie înmulțiți: F5), și celulele în care vor fi plasate valorile ca urmare a soluției x și x 2, x 3, x 4(celule SA : FA).
Fiecare parte stângă a constrângerii este, de asemenea, un produs a doi vectori: rândul corespunzător al matricei de cost și un vector de necunoscute. Expresie 2x + x 2+ 0Dg 3 + 4x l(pentru prima constrângere 2x, + x 2 + 0,5x 3 + 4 x 4 2400) va fi considerat produsul dintre un vector de coeficienți (2,1,0,5,4) și un vector de variabile (x și x 2, x 3, x 4).
În celula rezervată formulei din stânga primei constrângeri ((79), numim funcția SUMPRODUCT. Ca adrese ale vectorilor înmulțiți, introducem adresa rândului de coeficienți C9: /0 și adresa a valorilor variabilelor C4: FA.
În cele patru celule rămase ale coloanei " Partea stângă„Introducem formule similare folosind rândul corespunzător al matricei costurilor. Un fragment de ecran cu formulele introduse arată astfel.
Până la apelarea serviciului „Căutare soluție”, formulele pentru părțile din stânga constrângerilor și formula pentru valoarea funcției obiectiv trebuie să fie introduse pe desktop cu problema.
În meniul „Serviciu”, selectați „Căutați o soluție”. În fereastra care apare, introduceți următoarele informații:
- a) setați adresa celulei pentru valoarea funcției țintă #5 ca celulă țintă;
- b) setați „caseta” la opțiunea „valoare maximă”, întrucât în acest caz funcția obiectivă a venitului este supusă maximizării;
- c) ca celule schimbătoare se introduce adresa liniei de valori ale variabilelor C4: F4;
- d) în dreapta ferestrei destinate introducerii restricțiilor, faceți clic pe butonul „Adăugați”, va apărea un formular de introducere a restricțiilor;
e) în partea stângă a formularului „Cell Link”, introduceți adresa formulei pentru partea stângă a primei constrângeri G 9, este selectat semnul de inegalitate necesar (în cazul nostru, 
f) toate constrângerile sarcinii sunt introduse în același mod, după care se apasă butonul „OK”.
Fereastra „Căutare soluție” cu informațiile introduse arată astfel.
Apoi, trebuie să faceți clic pe butonul „Opțiuni”, bifați „casetele de selectare” Model liniar" și "Valori nenegative", deoarece în acest caz problema se referă la programarea liniară, iar constrângerea necesită valori nenegative.
Apoi faceți clic pe „OK”, „Run”, după care apare fereastra cu rezultatul soluției.
Dacă, în urma tuturor acțiunilor, primiți o fereastră cu mesajul „Soluție găsită”, atunci vi se oferă posibilitatea de a primi trei tipuri de rapoarte, care sunt utile atunci când analizați modelul pentru sensibilitate. ÎN în acest exemplu Doar salvați soluția găsită făcând clic pe „OK”. Ca urmare, s-a obținut o soluție la problemă.
Dacă, în urma rezolvării problemei, apare o fereastră cu un mesaj despre imposibilitatea de a găsi o soluție, aceasta înseamnă că a fost făcută o eroare în formularea problemei (formulele pentru constrângeri nu au fost completate, „steagul” , maximizarea (minimizarea), etc. nu a fost setată corect).
În fereastra „Căutare soluție” există un buton „Opțiuni”.
Bifați caseta de selectare „Afișați rezultatele iterației” și faceți clic pe „OK”.
Apoi faceți clic pe butonul „Run”.
MS Excel va afișa următoarea fereastră.
Fișa de lucru va afișa rezultatele primei iterații.
După aceea, faceți clic pe butonul „Continuare”, rezultatele celei de-a doua iterații sunt afișate pe foaia de lucru.
Faceți clic din nou pe butonul „Continuați” și foaia de lucru afișează rezultatele celei de-a treia iterații.
Data viitoare când faceți clic pe butonul „Continuare”, programul afișează fereastra „Rezultatele căutării soluției”, unde trebuie să salvați soluția găsită și să selectați tipul de raport.
ÎN această secțiune formatul general pentru rezolvarea problemelor de optimizare în Excela. In functie de modelele economice se fac modificari corespunzatoare.
Rapoartele arată așa.
1. Raportați rezultatele.
2. Raport de sustenabilitate.
3. Raport asupra limitelor.
Luați în considerare acum un exemplu în care modelul matematic are aceeași formă, dar constrângerile au semne diferite.
Exemplul 2.25
L. Să presupunem că modelul matematic este următorul: Are următoarele restricții: 
Raport de sustenabilitate.
B. Să presupunem acum că modelul matematic are alte restricții:
În acest caz, avem următoarele rezultate din rapoarte.
Raport de sustenabilitate.
- Pentru a rezolva aceeași problemă, vom folosi una dintre metodele de programare liniară - grafică. Exemplul 2.22 Să introducem următoarea notație: x( - numărul necesar de uși DV, x2 - numărul necesar de uși ICE.
Programarea liniară a apărut ca o ramură separată a matematicii aplicate în anii 40 și 50. secolul XX grație muncii omului de știință sovietic, laureatul Premiului Nobel L.V. Kantorovich. În 1939, a publicat lucrarea „Metode matematice de organizare și planificare a producției”, în care a folosit matematica pentru a rezolva obiective economice O cel mai bun download mașini, tăierea materialelor la cel mai mic cost, distribuirea mărfurilor pe mai multe moduri de transport și altele, propunând metoda de rezolvare a multiplicatorilor 8.
L.V. Kantorovich a fost primul care a formulat concepte economice și matematice atât de utilizate pe scară largă precum planul optim, alocarea optimă a resurselor, evaluări determinate obiectiv, indicând numeroase domenii ale economiei în care pot fi aplicate.
Conceptul de programare liniară a fost introdus de matematicianul american D. Dantzig, care în 1949 a propus un algoritm pentru rezolvarea problemei de programare liniară, numit „metoda simplex”.
Programarea matematică, care include programarea liniară, este în prezent unul dintre domeniile cercetării operaționale. În funcție de tipul de probleme care se rezolvă, se distinge domenii precum programarea liniară, neliniară, discretă, dinamică etc. Termenul de „programare” a fost introdus datorită faptului că variabilele necunoscute care se află în proces de rezolvare a unei probleme determină de obicei un program sau un plan de funcționare a unei entități economice.
În analiza matematică clasică se studiază formularea generală a problemei determinării unui extremum condiționat. Cu toate acestea, în legătură cu dezvoltarea producției industriale, transporturilor, agriculturii și sectorului bancar, rezultatele tradiționale ale analizei matematice nu au fost suficiente. Nevoile practicii și dezvoltarea tehnologiei informatice au condus la necesitatea de a determina soluții optime la analiza sistemelor economice complexe.
Instrumentul principal pentru rezolvarea unor astfel de probleme este modelarea matematică. În acest caz, se construiește mai întâi un model simplu, apoi se efectuează cercetarea acestuia, făcând posibilă înțelegerea care dintre proprietățile integratoare ale obiectului nu sunt surprinse de schema formală, după care, prin complicarea modelului, o mai mare adecvare a acestuia. la realitate este asigurată. În multe cazuri, prima aproximare a realității este un model în care toate dependențele dintre variabilele care caracterizează starea obiectului sunt liniare. Practica arată că un număr suficient de procese economice sunt descrise destul de complet prin modele liniare. În consecință, programarea liniară ca un aparat care permite găsirea unui extremum condiționat pe o mulțime definită de ecuații liniare și inegalități joacă un rol important în analiza acestor procese.
Programarea liniară a primit o dezvoltare pe scară largă datorită faptului că s-a stabilit că o serie de probleme de planificare și control pot fi formulate sub forma unor probleme de programare liniară, pentru rezolvarea cărora există metode eficiente. Potrivit experților, aproximativ 80–85% din toate problemele de optimizare rezolvate în practică sunt probleme de programare liniară.
Aparatul matematic creat în combinație cu programe de calculator care efectuează calcule intensive în muncă face posibilă utilizarea pe scară largă a modelelor de programare liniară în știința și practica economică.
Definiția 1 9 . Programarea liniară (LP) este un domeniu al programării matematice, care este o ramură a matematicii care studiază metode de găsire a valorilor extreme (mai mari și mai mici) ale unei funcții liniare a unui număr finit de variabile, ale căror necunoscute sunt supuse constrângeri liniare.
Această funcție liniară se numește funcție țintă, iar constrângerile, care reprezintă relații cantitative între variabile care exprimă condițiile și cerințele problemei economice și sunt scrise matematic sub formă de ecuații sau inegalități, se numesc sistem de constrângeri.
O gamă largă de probleme de planificare a proceselor economice se reduce la probleme de programare liniară, unde se pune sarcina de a găsi cea mai bună soluție (optimă).
O problemă generală de programare liniară (GLP) este să găsești valoarea extremă (maximum sau minim) a unei funcții liniare, numită obiectivul 10:
din n variabile x 1 , x 2 , …, X n cu restricții funcționale impuse:
(3.2)
și restricții directe (cerința de non-negativitate a variabilelor)
, (3.3)
Unde o ij , b i , c j– date constante de valori.
În sistemul de restricții (3.2), semnele „mai mic sau egal cu”, „egal cu” și „mai mare sau egal cu” pot apărea simultan.
ZLP într-o formă mai concisă are forma:
,
cu restrictii:
;
.
Vector` X = (x 1 , x 2 , …, X n) ale căror componente satisfac constrângerile funcţionale şi directe ale problemei se numesc plan(sau solutie acceptabila) ZLP.
Toate soluțiile fezabile se formează domeniul definirii probleme de programare liniară, sau regiune a soluțiilor fezabile (ODR). O soluție fezabilă care oferă maximum sau minim al funcției obiectiv f(`X), se numește planul optim al problemei și se notează f(`X * ), Unde ` X * =(x 1 * , x 2 * , …, X n * ).
O altă formă de înregistrare a PPP:
,
Unde f(`X * ) este valoarea maximă (minimă). f(CU, X), preluat toate soluțiile incluse în set solutii posibile X .
Definiția 2 11 . Expresia matematică a funcției obiectiv și a constrângerilor acesteia se numește model matematic al unei probleme economice.
Pentru a compila un model matematic aveți nevoie de:
1) identificarea variabilelor;
2) creați o funcție obiectivă pe baza scopului problemei;
3) notează un sistem de restricții, ținând cont de indicatorii din enunțul problemei și de modelele lor cantitative.
Metodele de programare liniară sunt folosite pentru a rezolva multe probleme extreme care sunt adesea tratate în economie. Rezolvarea unor astfel de probleme se reduce la găsirea valorilor extreme (maximum și minim) ale unor funcții de mărimi variabile.
Programarea liniară se bazează pe rezolvarea unui sistem de ecuații liniare (cu transformare în ecuații și inegalități), când relația dintre fenomenele studiate este strict funcțională. Se caracterizează prin expresia matematică a variabilelor, ordine anume, succesiune de calcule (algoritm), analiza logica. Poate fi utilizat numai în cazurile în care variabilele și factorii studiati au certitudine matematică și limitări cantitative, când, ca urmare a unei succesiuni cunoscute de calcule, factorii sunt interschimbabili, când logica din calcule, logica matematică se combină cu o înţelegere logică a esenţei fenomenului studiat.
Folosind această metodă în producția industrială, de exemplu, cea optimă performanța generală mașini, unități, linii de producție (cu o gamă dată de produse și alte valori date), se rezolvă problema tăierii raționale a materialelor (cu randament optim al pieselor de prelucrat). ÎN agricultură este folosit pentru a determina costul minim al rațiilor de furaje pentru o anumită cantitate de furaj (după tip și nutrienți conținuti în acestea). Problema amestecului poate găsi aplicație și în producția de turnătorie (compoziția încărcăturii metalurgice). Aceeași metodă este folosită pentru a rezolva problema transporturilor, problema atașării raționale a întreprinderilor de consum de întreprinderile producătoare.
Toate problemele economice rezolvate prin programarea liniară se disting prin soluții alternative și anumite condiții limitative. A rezolva o astfel de problemă înseamnă a alege cel mai bun, Optimal, dintre toate opțiunile (alternative) admisibile posibile. Importanța și valoarea utilizării metodei de programare liniară în economie este că opțiunea optimă este selectată dintr-un număr foarte semnificativ opțiuni alternative. Este aproape imposibil să rezolvi astfel de probleme folosind alte metode.
Ca exemplu, luați în considerare rezolvarea problemei utilizării raționale a timpului de funcționare a echipamentelor de producție.
În conformitate cu planul operațional, secția de șlefuire a produs 500 de inele pentru rulmenți de tip A, 300 de inele pentru rulmenți de tip B și 450 de inele pentru rulmenți de tip B, în prima săptămână a lunii decembrie. Toate inelele au fost șlefuite pe două mașini interschimbabile performanță diferită. Timpul mașinii pentru fiecare mașină este de 5000 de minute. Complexitatea operațiunilor (în minute pe inel) în fabricarea diferitelor inele este caracterizată de următoarele date (Tabelul 6.5).
Tabelul 6.5
Este necesar să se determine opțiunea optimă pentru distribuirea operațiunilor între mașini și timpul care ar fi petrecut cu această opțiune optimă. Să finalizăm sarcina folosind metoda simplex.
Pentru a compila un model matematic al acestei probleme, introducem următoarele simboluri: jc, x2, xъ, - respectiv, numărul de inele pentru rulmenți de tipurile L, B, V, produse pe mașina I; x4, x5, x6 - respectiv, numărul de inele pentru rulmenți de tipurile A, B, C, produse pe mașina II.
Forma liniară care reflectă criteriul de optimitate va arăta astfel:
min a(x) = 4x,-f 10x2-f 10x3-f 6x4-f 8x5+20x6 cu restricții
4х, -f 10х2 -f 10;t3 lt; 5000
6x4 -f 8x5 -f 20x6 ~lt; 5000
x, = 500
x2 + x5 = 300
x3 + x6 = 450
Xj^0,j=l, ..., 6
Să transformăm condiția problemei prin introducerea de variabile suplimentare (auxiliare) și fictive. Să scriem condiția astfel:
spike lt;x(x) = 4dg, + 10x2+ 10x3 + 6x4 + 8x5 + 20x6+
+ Mx9 + Mx(0+Mx(,
Un sistem de ecuații care reflectă condițiile restrictive ale timpului computerului și cantitatea de produse produse:
4x, + l(bc2 + 10x3 +x1 = 5000
6x4 + 8x5 + 20x6 + xs = 5000
Xj + x4 + x9 = 500
x2 + x5 + x10 = 300
XJ +X6 + *!1 = 450
-*,^0,7=1, ..., 11
Soluția la această problemă este prezentată în tabel. 6.6. Opțiunea optimă a fost obținută în a șaptea etapă (iterație). Dacă mașina I a produs 125 inele lagăre de tip A, 450 inele lagăr de tip B și mașina II a produs 375 inele lagăr de tip A și 300 inele lagăr de tip B, atunci cu o astfel de încărcătură de echipament ar fi 350 de minute de timp de mașină. eliberat pentru mașina II. Timpul total petrecut pe varianta optima s-ar ridica la 9650 de minute, în timp ce 10.000 de minute de timp pe calculator au fost de fapt cheltuite.
O problemă foarte tipică rezolvată folosind programarea liniară este problema transportului. Semnificația sa este de a minimiza cifra de afaceri de marfă atunci când se livrează bunuri de larg consum de la producător la consumator, de la depozitele și bazele angro până la punctele de vânzare cu amănuntul. Poate fi rezolvată folosind metoda simplex sau metoda distribuției.
Soluția problemei transportului prin metoda distribuției a fost dată în cea de-a treia ediție a manualului „Teoria analizei economice” („Finanțe și statistică”, 1996).
Rezolvarea problemei utilizării raționale a mașinilor-unelte folosind metoda simplex
| Bază | Cu | Ro | 4 | 10 | 10 | 6 | 8 | 20 | 0 | 0 | m | m | m |
| L | Rg | R | L | R ъ | | Pi | P8 | p* | L 0 | L, |
|||
| L | 0 | 5000 | 4 | 10 | 0 | 0 | 0 | 0 | і | 0 | 0 | 0 | 0 |
| R, | 0 | 5000 | 0 | 0 | 0 | 6 | 8 | 20 | 0 | 1 | 0 | 0 | 0 |
| L | m | 500 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| L 0 | m | 300 | w | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| L. | m | 450 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| Zj-Cj | | 1250M | M-4 | M-10 | M-10 | M-6 | M-8 | M-20 | 0 | 0 | 0 | 0 | 0 |
| Pi | 0 | 3000 | 0 | 10 | 10 | -4 | 0 | 0 | 0 | 0 | -4 | 0 | 0 |
| p* | 0 | 5000 | 0 | 0 | 0 | 6 | 8 | 20 | 1 | 1 | 0 | 0 | 0 |
| Ro | 4 | 500 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| Iată | m | 300 | 0 | 1 | 0 | 0 | w | 0 | 0 | 0 | 0 | 1 | 0 |
| L. | m | 450 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| zr-9 | | 750L/+2000 | 0 | M-10 | M-10 | -2 | M-8 | DESPRE 2 | 0 | 0 | -M + 4 | 0 | 0 |
| Bază | CU | P0 | 4 | Pi | 10 | 6 | 8 | 20 | 0 | 0 | m | m | M |
| | | Pi | 10 | ^3 | l | P5 | p6 | Pi | p« | p9 | Pi 0 | RC |
|
| Pi | 0 | 3000 | 0 | 10 | 10 | -4 | 0 | 0 | 1 | 0 | -4 | 0 | 0 |
| P* | 0 | 2600 | 0 | -8 | 0 | 6 | 0 | 20 | 0 | 1 | 0 | -8 | 0 |
| Pi | 4 | 500 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| P5 | 8 | 300 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| RP | M | 450 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
| Zj-Cj | | 450L/+4400 | 0 | -2 | M-10 | -2 | 0 | M-20 | 0 | 0 | -M+4 | -M+8 | 0 |
| R | 10 | 300 | 0 | 1 | 1 | 4 10 | 0 | 0 | 1 10 | 0 | 4 10 | 0 | 0 |
| P% | 0 | 2600 | 0 | -8 | 0 | 6 | 0 | 20 | 0 | 1 | 0 | -8 | 0 |
| Pi | 4 | 500 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| P5 | 8 | 300 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
| RC | M | 150 | 0 | -1 | 0 | j4_ 10 | 0 | 1 | _J_ 10 | 0 | 4 10 | 0 | 1 |
| zrCj | | 150L/+7400 | 0 | -M+S | 0 | - M-6 10 | 0 | M-20 | - ~M+110 | 0 | -±m 10 | - Af+8" | 0 |
| Bază | Cu | L, | 4 | 10 | 10 | 6 | 8 | 20 | 0 | 0 | M | M | m |
||
| L | Rg | L | l | PS | p6 | Pi | pamp; | P9 | Iată | l. |
|||||
| L | 10 | 300 | 0 | 1 | 1 | 4 | 0 | 0 | 1 | | 0 | | 4 | 0 | 0 |
| | | | | | | “10 | | | Că | | | | “ 10 | | |
| p6 | 20 | 130 | 0 | 4 | 0 | 3 | 0 | 1 | 0 | | 1 | | 0 | 4 | 0 |
| | | | | ~Ї0 | | 10 | | | | | 20 | | | 10 | |
| l | 4 | 500 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | | 0 | | 1 | 0 | 0 |
| PS | 8 | 300 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | | 0 | | 0 | 1 | 0 |
| R\\ | M | 20 | 0 | 6 | 0 | 1 | 0 | 0 | 1 | | 1 | | 4 | 4 | 1 |
| | | | | 10 | | ~10 | | | Că | | 20 | Că | 10 | |
|
| Zj-Cj | | 20M+10000 | 0 | | 0 | -m | 0 | 0 | m+\ | | -m+\ | --M | -*M | 0 |
|
| | | | | 10 | | 10 | | | 10 | 20 | | 10 | 10 | |
|
| l | 10 | 380 | 0 | 14 | 1 | 0 | 0 | 0 | 3 | | 2 | | 12 | 0 | 0 |
| | | | | 10 | | | | | 10 | | 10 | 10 | | |
|
| p% | 20 | 70 | 0 | 14 | 0 | 0 | 0 | 1 | 3 | | 2 | | 12 | 16 | -3 |
| | | | | 10 | | | | | 10 | | 10 | | 10 | 10 | |
| L | 4 | 300 | 1 | 6 | 0 | 0 | 0 | 0 | 1 | | 1 | | -3 | | -10 |
| | | | | | | | | | | | 2 | | | | |
| p5 | 8 | 300 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | | 0 | | 0 | 1 | 0 |
| P4 | 6 | 200 | 0 | -6 | 0 | 1 | 0 | 0 | -1 | | 1 | | 4 | 4 | 10 |
| | | | | | | | | | | | ’ 2 | | | | |
| Z.-Ci | | 10000 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | -M | -M | -m |
||
| Bază | | Lgt; | 4 | 10 | 10 | 6 | 8 | 20 | 0 | 0 | m | m | l/ |
| O | L | Rg | ръ | P* | P5 | P6 | L | Pamp; | p9 | L 0 | l. |
||
| Rg | 10 | 450 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | | | |
| P% | 0 | 350 | 0 | 7 | 0 | 0 | 0 | 5 | 3 5 | 1 | | | |
| L | 4 | 125 | 1 | 5 2 | 0 | 0 | 0 | 5 2 | 1 4 | 0 | | | |
| PS | 8 | 300 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | | | |
| P4 | 6 | 375 | 0 | 5 2 | 0 | 1 | 0 | 5 2 | 1 4 | 0 | | | |
| Zj-Cj | | 9650 | 0 | -7 | 0 | 0 | 0 | -5 | 1 2 | 0 | | | |
Programare liniară
Programare liniară- o disciplină matematică dedicată teoriei și metodelor de rezolvare a problemelor extreme pe mulțimi de spațiu vectorial -dimensional definite prin sisteme de ecuații liniare și inegalități.
Programarea liniară este un caz special de programare convexă, care la rândul său este un caz special de programare matematică. În același timp, stă la baza mai multor metode de rezolvare a problemelor de programare cu numere întregi și neliniare. O generalizare a programării liniare este programarea liniară fracțională.
Multe proprietăți ale problemelor de programare liniară pot fi, de asemenea, interpretate ca proprietăți ale poliedrelor și astfel formulate și dovedite geometric.
Poveste
Metoda punctului interior a fost menționată pentru prima dată de I. I. Dikin în 1967.
Sarcini
Problema principală (standard) de programare liniară se numește problema găsirii minimului unei funcții obiectiv liniare ( formă liniară) de forma:
in conditii
, .Problema programarii liniare va avea vedere canonică , dacă în problema principală în locul primului sistem de inegalități există un sistem de ecuații:
,Problema principală poate fi redusă la canonică prin introducerea unor variabile suplimentare.
Problemele de programare liniară de cea mai generală formă (probleme cu constrângeri mixte: egalități și inegalități, prezența variabilelor libere de constrângeri) pot fi reduse la unele echivalente (având același set de soluții) prin înlocuirea variabilelor și înlocuirea egalităților cu o pereche de inegalităților.
Este ușor de observat că problema găsirii maximului poate fi înlocuită cu sarcina găsirii minimului luând coeficienți cu semnul opus.
Exemple de probleme
Potrivire maximă
Luați în considerare problema de potrivire maximă într-un grafic bipartit: există mai mulți băieți și fete, iar pentru fiecare băiat și fată se știe dacă sunt atractivi unul pentru celălalt. Trebuie să ne căsătorim cu un număr maxim de cupluri cu simpatie reciprocă.
Să introducem variabile care corespund perechii dintre -băiat și -fată și să satisfacem restricțiile:
cu funcţie obiectivă. Se poate arăta că printre soluțiile optime la această problemă există una întreagă. Variabilele egale cu 1 vor corespunde cuplurilor care ar trebui să fie căsătorite.
Debit maxim
Să existe un grafic (cu muchii orientate), în care pentru fiecare muchie să fie debitului. Și sunt date două vârfuri: dren și sursă. Este necesar să se indice pentru fiecare margine cât lichid va curge prin ea (nu mai mult decât capacitatea sa) astfel încât să se maximizeze debitul total de la sursă la scurgere (lichidul nu poate apărea sau dispărea la toate vârfurile cu excepția scurgerii și sursei).
Să luăm ca variabile cantitatea de lichid care curge prin coastă. Apoi
,unde este capacitatea acelei margini. Aceste inegalități trebuie să fie completate de egalitatea cantității de fluid care intra și care iese pentru fiecare vârf, cu excepția scurgerii și sursei. Ca o funcție, este firesc să se ia diferența dintre cantitatea de fluid care iese și care intra la sursă.
O generalizare a problemei anterioare este fluxul maxim al costului minim. În această problemă, sunt date costurile pentru fiecare margine și trebuie să selectați debitul cu costul minim dintre fluxurile maxime. Această problemă se rezumă la două probleme de programare liniară: mai întâi trebuie să rezolvați problema debitului maxim, apoi să adăugați la această problemă constrângerea , unde este valoarea debitului maxim și să rezolvați problema cu caracteristică nouă- costul fluxului.
Aceste probleme pot fi rezolvate mai repede decât algoritmi generali rezolvarea problemelor de programare liniara datorita structurii speciale a ecuatiilor si inegalitatilor.
Sarcina de transport
Există o anumită marfă omogenă care trebuie transferată de la depozite la fabrici. Pentru fiecare depozit se știe câtă marfă conține, iar pentru fiecare fabrică este cunoscută cererea de marfă. Costul transportului este proporțional cu distanța de la depozit la fabrică (se cunosc toate distanțele de la al-lea depozit la a--a fabrică). Este necesar să compuneți cel mai mult plan ieftin transport.
Variabilele decisive în acest caz sunt cantitățile de marfă transportate de la al-lea depozit la a-lea fabrică. Acestea îndeplinesc restricțiile:
Funcția obiectiv are forma: , care trebuie minimizată.
Joc cu sumă zero
Există o matrice de dimensiuni. Primul jucător alege un număr de la 1 la , al doilea - de la 1 la . Apoi verifică numerele și primul jucător primește puncte, iar al doilea jucător primește puncte (numărul ales de primul jucător primește al doilea). Trebuie să găsim strategia optimă pentru primul jucător.
Să presupunem că într-o strategie optimă, de exemplu, primul jucător trebuie să aleagă un număr cu probabilitate . Atunci strategia optimă este o soluție la următoarea problemă de programare liniară:
, , (),în care funcția trebuie maximizată. Valoare în solutie optima va fi așteptarea matematică a primului jucător în cel mai rău caz.
Algoritmi de rezolvare
Cel mai faimos și utilizat pe scară largă în practică pentru a rezolva sarcină comună Programarea liniară (LP) este o metodă simplex. În ciuda faptului că metoda simplex este un algoritm destul de eficient care a arătat rezultate bune atunci când decide probleme aplicate LP, este un algoritm cu complexitate exponențială. Motivul pentru aceasta este natura combinatorie a metodei simplex, care enumeră secvenţial vârfurile poliedrului de soluţii fezabile atunci când se caută soluţia optimă.
Primul algoritm polinom, metoda elipsoidului, a fost propus în 1979 de matematicianul sovietic L. Khachiyan, rezolvând astfel problema pentru o lungă perioadă de timp rămas nerezolvată. Metoda elipsoidală are o natură complet diferită, necombinatorie decât metoda simplex. Cu toate acestea, din punct de vedere computațional, această metodă s-a dovedit a fi nepromițătoare. Cu toate acestea, însuși faptul complexității polinomiale a problemelor a condus la crearea unei clase întregi algoritmi eficienti LP - metode de punct interior, primul dintre care a fost algoritmul lui N. Karmarkar propus în 1984. Algoritmii de acest tip folosesc o interpretare continuă a problemei LP, când în loc să enumere vârfurile poliedrului pentru soluții la problema LP, se efectuează o căutare de-a lungul traiectoriilor în spațiul variabilelor problemei care nu trec prin vârfurile lui. poliedrul. Metoda punctului interior, care, spre deosebire de metoda simplex, traversează puncte din interiorul regiunii fezabile, utilizează metode de programare neliniară cu barieră logartică dezvoltate în anii 1960 de Fiacco și McCormick.
Vezi de asemenea
- Metodă grafică pentru rezolvarea unei probleme de programare liniară
Note
Literatură
- Thomas H. Corman și colab. Capitolul 29. Programarea liniara // Algoritmi: constructie si analiza = INTRODUCERE IN ALGORITMI. - Ed. a 2-a. - M.: „Williams”, 2006. - P. 1296. - ISBN 5-8459-0857-4
- Akulich I.L. Capitolul 1. Probleme de programare liniară, Capitolul 2. Probleme speciale de programare liniară // Programarea matematică în exemple și probleme. - M.: facultate, 1986. - 319 p. - ISBN 5-06-002663-9
- Karmanov V. G. Programare matematică. - editia a 3-a. - M.: Nauka, 1986. - 288 p.
- Danzig George Bernard „Amintiri despre începutul programării liniare”
Legături
- - Pachet de optimizare gratuit conceput pentru a rezolva probleme de programare liniare, întregi și obiective.
- Vershik A. M. „Despre L. V. Kantorovich și programarea liniară”
- Bolshakova I. V., Kuralenko M. V. „Programare liniară. Manual educațional și metodologic pentru test.”
- Barsov A. S. „Ce este programarea liniară”, Prelegeri populare despre matematică, Gostekhizdat, 1959.
- M. N. Vyalyi Inegalități liniare și combinatorie. - MCNMO, 2003.
Fundația Wikimedia.
- 2010.
- Salten, Felix
Glagow, Martina
Vedeți ce este „programarea liniară” în alte dicționare: programare liniară - - programare liniară O zonă de programare matematică dedicată teoriei și metodelor de rezolvare a problemelor extreme caracterizate prin dependență liniară intre……
Programare liniară
Programare liniară- un domeniu de programare matematică consacrat teoriei și metodelor de rezolvare a problemelor extreme caracterizate printr-o relație liniară între variabile. În chiar vedere generală problema L.p se poate scrie asa. Dana...... Dicţionar economico-matematic
Dacă o problemă de programare liniară are doar două variabile, atunci poate fi rezolvată metoda grafica.
Luați în considerare o problemă de programare liniară cu două variabile și:
(1.1)
;
(1.2)
Aici, există numere arbitrare. Sarcina poate fi fie găsirea maximului (max), fie găsirea minimului (min). Sistemul de restricții poate conține atât semne, cât și semne.
Construirea domeniului soluțiilor fezabile
Metoda grafică de rezolvare a problemei (1) este următoarea.
Mai întâi, desenăm axele de coordonate și selectăm scara. Fiecare dintre inegalitățile sistemului de constrângeri (1.2) definește un semiplan mărginit de dreapta corespunzătoare.
Deci, prima inegalitate
(1.2.1)
definește un semiplan mărginit de o dreaptă.
Pe o parte a acestei linii drepte și pe cealaltă parte.
Pe linie foarte dreaptă.
Pentru a afla de ce parte are loc inegalitatea (1.2.1), alegem un punct arbitrar care nu se află pe linie. În continuare, înlocuim coordonatele acestui punct în (1.2.1). Dacă inegalitatea este valabilă, atunci semiplanul conține punctul selectat. Dacă inegalitatea nu este valabilă, atunci semiplanul este situat pe cealaltă parte (nu conține punctul selectat). Umbriți semiplanul pentru care este valabilă inegalitatea (1.2.1).
(2)
Apoi, selectați un punct arbitrar care nu aparține niciuna dintre aceste linii. Înlocuiți coordonatele acestui punct în sistemul de inegalități (1.2). Dacă toate inegalitățile sunt satisfăcute, atunci regiunea soluțiilor fezabile este limitată de liniile drepte construite și include punctul selectat. Umbrim regiunea soluțiilor fezabile de-a lungul limitelor liniilor, astfel încât să includă punctul selectat.
Dacă cel puțin o inegalitate nu este satisfăcută, atunci alegeți un alt punct. Și așa mai departe până când se găsește un punct ale cărui coordonate satisfac sistemul (1.2).
Găsirea extremului funcției obiectiv
Deci, avem o regiune umbrită de soluții fezabile (ADA). Este limitată de o linie întreruptă formată din segmente și raze aparținând liniilor drepte construite (2). ODS este întotdeauna un set convex. Poate fi fie o mulțime mărginită, fie nemărginită de-a lungul unor direcții.
Acum putem căuta extremul funcției obiectiv
(1.1)
.
Pentru a face acest lucru, alegeți orice număr și construiți o linie dreaptă
(3)
.
Pentru comoditatea unei prezentări ulterioare, presupunem că această linie dreaptă trece prin ODR. Pe această linie funcția obiectiv este constantă și egală cu .
.
o astfel de linie dreaptă se numește linie de nivel de funcție.
.
Această linie dreaptă împarte planul în două semiplane. Pe un semiplan
Pe alt semiplan
Adică pe o parte a dreptei (3) funcția obiectiv crește. Și cu cât deplasăm punctul mai departe de linia dreaptă (3), cu atât valoarea va fi mai mare.
Să luăm în considerare cazul în care linia extremă paralelă cu o dreaptă arbitrară de forma (3) trece printr-un vârf al poligonului ODR. Din grafic determinăm coordonatele acestui vârf. Apoi valoarea maximă (minimă) a funcției obiectiv este determinată de formula:
.
Soluția problemei este
.
Poate exista și un caz când linia dreaptă este paralelă cu una dintre fețele ODR. Apoi linia dreaptă trece prin două vârfuri ale poligonului ODR. Determinăm coordonatele acestor vârfuri. Pentru a determina valoarea maximă (minimă) a funcției obiectiv, puteți utiliza coordonatele oricăruia dintre aceste vârfuri:
.
Problema are nenumărate soluții. Soluția este orice punct situat pe segmentul dintre punctele și , inclusiv punctele și ei înșiși.
Un exemplu de rezolvare a unei probleme de programare liniară folosind metoda grafică
Stare problematica
Compania produce rochii de două modele A și B. Se folosesc trei tipuri de țesături. Pentru a realiza o rochie de model A, sunt necesari 2 m de țesătură de primul tip, 1 m de țesătură de al doilea tip, 2 m de țesătură de al treilea tip. Pentru a realiza o rochie de model B, sunt necesari 3 m de țesătură de primul tip, 1 m de țesătură de al doilea tip, 2 m de țesătură de al treilea tip. Stocurile de țesătură de primul tip sunt de 21 m, de al doilea tip - 10 m, de al treilea tip - 16 m Eliberarea unui produs de tip A aduce un venit de 400 de den. unități, un produs tip B - 300 den. unitati
Întocmește un plan de producție care să ofere companiei cele mai mari venituri. Rezolvați problema grafic.
Soluţie
Fie variabilele și notăm numărul de rochii produse, modelele A și respectiv B. Atunci cantitatea de material textil de primul tip consumata va fi:
(m)
Cantitatea de țesătură de al doilea tip consumată va fi:
(m)
Cantitatea de material de al treilea tip consumată va fi:
(m)
Întrucât numărul de rochii produse nu poate fi negativ, atunci
Și .
Veniturile din rochiile produse vor fi:
(unități den.)
Atunci modelul economico-matematic al problemei are forma:
O rezolvam grafic.
Desenăm axele de coordonate și .
Construim o linie dreaptă.
La .
La .
Desenați o linie dreaptă prin punctele (0; 7) și (10.5; 0).
Construim o linie dreaptă.
La .
La .
Desenați o linie dreaptă prin punctele (0; 10) și (10; 0).
Construim o linie dreaptă.
La .
La .
Desenați o linie dreaptă prin punctele (0; 8) și (8; 0).
Umbrim zona astfel încât punctul (2; 2) să cadă în partea umbrită. Obținem patrulaterul OABC.
(A1.1) .
La .
La .
Desenați o linie dreaptă prin punctele (0; 4) și (3; 0).
Mai observăm că, deoarece coeficienții și ai funcției obiectiv sunt pozitivi (400 și 300), ea crește pe măsură ce și crește.
.
Desenăm o dreaptă paralelă cu dreapta (A1.1), cât mai departe posibil de aceasta în direcția creșterii , și care trece prin cel puțin un punct al patrulaterului OABC. O astfel de dreaptă trece prin punctul C. Din construcție îi determinăm coordonatele.
Rezolvarea problemei: ;
.
Răspuns Adică să primească cel mai mare venit
, este necesara producerea a 8 rochii model A. Venitul va fi de 3200 den. unitati
Stare problematica
Exemplul 2
Soluţie
O rezolvam grafic.
Desenăm axele de coordonate și .
Construim o linie dreaptă.
La .
La .
Rezolvați grafic o problemă de programare liniară.
Construim o linie dreaptă.
Desenați o linie dreaptă prin punctele (0; 6) și (6; 0).
La .
La .
De aici.
Construim o linie dreaptă.
Desenați o linie dreaptă prin punctele (3; 0) și (7; 2).
Construim o linie dreaptă (axa absciselor).
Regiunea soluțiilor admisibile (ADA) este limitată de liniile drepte construite. Pentru a afla care parte, observăm că punctul aparține ODR, deoarece satisface sistemul de inegalități:
Umbrim zona de-a lungul limitelor liniilor construite, astfel încât punctul (4; 1) să cadă în partea umbrită. Obținem triunghiul ABC. Construim orice linie
.
La .
La .
nivelul funcției țintă, de exemplu,
Desenați o linie dreaptă de nivel prin punctele (0; 6) și (4; 0). Deoarece funcția obiectiv crește odată cu creșterea și , tragem o linie dreaptă, paralel cu linia
.
Desenăm o dreaptă paralelă cu dreapta (A1.1), cât mai departe posibil de aceasta în direcția creșterii , și care trece prin cel puțin un punct al patrulaterului OABC. O astfel de dreaptă trece prin punctul C. Din construcție îi determinăm coordonatele.
Rezolvarea problemei: ;
nivelul și distanța maximă față de acesta în direcția creșterii și trecând prin cel puțin un punct al triunghiului ABC. O astfel de dreaptă trece prin punctul C. Din construcție îi determinăm coordonatele.
Stare problematica
Exemplu fără soluție
Soluţie
Rezolvați grafic o problemă de programare liniară. Aflați valoarea maximă și minimă a funcției obiectiv.
Desenăm axele de coordonate și .
Construim o linie dreaptă.
La .
La .
Rezolvăm problema grafic.
Construim o linie dreaptă.
La .
La .
Desenați o linie dreaptă prin punctele (0; 8) și (2.667; 0).
Construim o linie dreaptă.
La .
La .
Desenați o linie dreaptă prin punctele (0; 3) și (6; 0).
Desenați o linie dreaptă prin punctele (3; 0) și (6; 3).
Liniile drepte sunt axele de coordonate.
Regiunea soluțiilor admisibile (ADA) este limitată de liniile drepte construite și axele de coordonate. Pentru a afla care parte, observăm că punctul aparține ODR, deoarece satisface sistemul de inegalități:
Umbrim zona astfel încât punctul (3; 3) să cadă în partea umbrită. Obținem o zonă nelimitată delimitată de linia întreruptă ABCDE.
Construim o linie arbitrară a nivelului funcției obiectiv, de exemplu, .
La .
La .
(A3.1)
Desenați o linie dreaptă prin punctele (0; 7) și (7; 0).
Pentru a găsi maximul, trebuie să trasați o linie paralelă cât mai departe posibil în direcția creșterii și care trece prin cel puțin un punct al regiunii ABCDE. Cu toate acestea, din moment ce zona este nelimitată din lateral valori mariși , atunci o astfel de linie dreaptă nu poate fi trasă. Indiferent ce linie dreaptă trasăm, vor exista întotdeauna puncte în regiune care sunt mai îndepărtate în direcția creșterii și .
Prin urmare, nu există maxim. o poți face cât de mare vrei.
.
Căutăm minim. Tragem o linie dreaptă paralelă cu dreapta (A3.1) și pe cât posibil de aceasta în direcția descrescătoare , și trecând prin cel puțin un punct al regiunii ABCDE. O astfel de dreaptă trece prin punctul C. Din construcție îi determinăm coordonatele. Valoarea minima
Rezolvarea problemei: ;
functie obiectiv:
Nu există o valoare maximă.
.
