Rezolvați metoda simplex și efectuați o interpretare grafică. Programare liniară. Metoda simplex

Ți-a plăcut? Adăugați la marcaje

Rezolvarea problemelor folosind metoda simplex: exemple online

Sarcina 1. Compania produce rafturi pentru baie în două dimensiuni - A și B. Agenții de vânzări estimează că pe piață pot fi vândute până la 550 de rafturi pe săptămână. Fiecare raft de tip A necesită 2 m2 de material, iar fiecare raft de tip B necesită 3 m2 de material. Compania poate primi până la 1200 m2 de material pe săptămână. Pentru fabricarea unui raft de tip A sunt necesare 12 minute de timp de mașină, iar pentru fabricarea unui raft de tip B - 30 de minute; Aparatul poate fi folosit 160 de ore pe săptămână. Dacă profitul din vânzarea de rafturi de tip A este de 3 unități monetare, iar din rafturi de tip B - 4 unități monetare. unități, atunci câte rafturi de fiecare tip ar trebui să fie produse pe săptămână?

Sarcina 2. Rezolvați problema programare liniară metoda simplex.

Sarcina 3. Compania produce 3 tipuri de produse: A1, A2, A3, folosind două tipuri de materii prime. Sunt cunoscute costurile fiecărui tip de materie primă pe unitate de producție, rezervele de materii prime pentru perioada de planificare, precum și profitul dintr-o unitate de producție de fiecare tip.

1. Câte articole de fiecare tip trebuie produse pentru a maximiza profitul?
2. Determinați starea fiecărui tip de materie primă și valoarea sa specifică.
3. Determinați intervalul maxim de modificare a stocurilor pentru fiecare tip de materie primă, în cadrul căruia structura planului optim, i.e. Nomenclatura de producție nu se va modifica.
4. Determinați cantitatea de produse produse și profitul din producție atunci când creșteți stocul unuia dintre tipurile rare de materii prime la valoarea maximă posibilă (în intervalul dat de producție).
5. Determinați intervalele de modificare a profitului dintr-o unitate de producție de fiecare tip la care planul optim rezultat nu se va modifica.

Sarcina 4. Rezolvați o problemă de programare liniară metoda simplex:

Sarcina 5. Rezolvați o problemă de programare liniară folosind metoda simplex:

Sarcina 6. Rezolvați problema folosind metoda simplex, considerând ca plan de referință inițial planul dat în condiția:

Sarcina 7. Rezolvați problema folosind metoda simplex modificată.
Pentru a produce două tipuri de produse A și B, se folosesc trei tipuri de echipamente tehnologice. Pentru a produce o unitate de produs A, echipamentele de primul tip folosesc a1=4 ore, echipamente de al doilea tip a2=8 ore, iar echipamentele de al treilea tip a3=9 ore. Pentru a produce o unitate de produs B, echipamentele de primul tip folosesc b1=7 ore, echipamente de al doilea tip b2=3 ore, iar echipamentele de al treilea tip b3=5 ore.
Echipamentele de primul tip pot lucra pentru producerea acestor produse timp de cel mult t1=49 ore, echipamentele de al doilea tip nu mai mult de t2=51 ore, echipamentele de al treilea tip nu mai mult de t3=45 de ore.
Profitul din vânzarea unei unități de produs finit A este ALPHA = 6 ruble, iar produsul B este BETTA = 5 ruble.
Întocmește un plan de producție a produselor A și B, asigurând profit maxim din vânzarea acestora.

Sarcina 8. Găsi solutie optima metoda dual simplex

Algoritmul principal pentru rezolvarea ZLP este metoda simplex. Poate fi folosit dacă problema de optimizare este scrisă într-un special formă canonică. În acest caz, toate restricțiile au formă de egalități și fiecare variabilă de bază apare cu un coeficient de 1 doar într-o ecuație, iar în altele coeficientul variabilei de bază este egal cu 0. Expresie analitică pentru funcţie obiectivă nu trebuie să conțină variabile de bază, ci să fie exprimate doar prin variabile libere. Dacă în acelaşi timp b i≥ 0, atunci vorbim de o formă canonică admisibilă.

Esența metodei simplex este o căutare direcționată a vârfurilor ODD pentru a determina coordonatele vârfului la care funcția obiectiv atinge un extremum. Să introducem mai multe definiții.

Soluția de referință a sistemului constrângeri este o soluție când, pentru un sistem de constrângeri într-o formă canonică admisibilă, toate variabilele libere sunt egale cu zero.

Soluție de suport degeneratăsoluție de referință în care una sau mai multe variabile de bază sunt egale cu zero.

Soluție de referință validăsoluție de referință în care toate variabilele de bază ≥ 0.

Soluția optimă a ZLP va corespunde uneia dintre soluțiile de referință admisibile. În metoda simplex, plecând de la o soluție de referință admisibilă situată la vârful poliedrului ODR, se deplasează la vârful învecinat, menținând admisibilitatea soluției.

Pentru comoditatea formulării regulilor metodei, notăm canonicul admisibil formularul PAPîntr-o altă formă numită formă standard. De exemplu:

Pentru a simplifica implementarea metodei simplex pe un computer, aceasta este prezentată în formă tabelară. În acest caz, fiecare soluție de suport corespunde unui nou tabel simplex. Fiecare rând al tabelului corespunde fie unui rând al funcției obiectiv, fie unui rând al uneia dintre constrângeri. Un exemplu de tabel pentru cazul a șapte variabile pentru notația standard este dat mai jos.

În metoda simplex, este necesar să existe o soluție inițială de suport fezabilă. Uneori, o astfel de soluție este ușor de obținut. De exemplu, dacă există o constrângere a formei cu pozitiv partea dreaptă, apoi variabilele suplimentare utilizate la scrierea constrângerilor sub formă de egalități formează o soluție de referință admisibilă în care toate variabilele de proiectare sunt egale cu zero, iar variabilele suplimentare sunt de bază. Cu toate acestea, în multe probleme există constrângeri de forma 0 și = 0, pentru care soluția de referință inițială poate fi inacceptabilă. Prin urmare, aplicarea metodei simplex în cazul general trebuie să fie precedată de etapa de căutare a unei soluții acceptabile. Să luăm în considerare una dintre variantele algoritmului metodei simplex, ținând cont de etapa de căutare a unei soluții acceptabile.

Algoritmul metodei simplex

etapa 1: găsirea unei soluții de referință acceptabile.

Pasul 1. Constrângerile de inegalitate sunt reduse la forma constrângerilor de egalitate. Sarcina este scrisă într-o formă standard.

Pasul 2. Pentru fiecare constrângere care are un termen liber negativ se examinează semnele coeficienților variabilelor libere. Dacă lipsește cel puțin un coeficient negativ, atunci restricțiile sunt inconsecvente. Dacă termenii liberi din toate constrângerile sunt nenegativi, atunci soluția de referință este admisibilă și este necesar să se treacă la a doua etapă (etapa găsirii soluției optime).

Pasul 3. Pentru o constrângere care are un termen liber negativ, este selectată variabila liberă cu un coeficient negativ. Această variabilă va fi noua variabilă de bază. Dacă există mai mult de un coeficient negativ, atunci oricare cu un coeficient negativ poate fi ales ca o nouă variabilă de bază (alegerea variabilei în acest caz va afecta numărul de modificări de bază, dar nu rezultatul final). Să fie o variabilă x l. Dacă există mai multe constrângeri cu un termen liber negativ, atunci puteți alege oricare pentru a analiza coeficienții.

Pasul 4. Pentru a selecta o nouă variabilă liberă, se ia în considerare relația b j /o jl pentru toate restricțiile și b jŞi o jl trebuie să aibă același semn. Se găsește raportul minim. Noua variabilă liberă va fi variabila de bază pentru care este constrângerea b j /o jl s-a dovedit a fi minim. În acest caz, elementul de rezolvare al tabelului va fi situat la intersecția coloanei corespunzătoare variabilei x lşi o linie corespunzătoare constrângerii pentru care s-a obţinut raportul minim.

Pasul 5. Baza este înlocuită. Pentru a recalcula valorile elementelor tabelului simplex după schimbarea bazei, introducem următoarea notație în tabel:

la q=r; s=p,numărul iterației (schimbarea bazei);

la q=r;sp,s=
;

la q r; s=p;q=
;

pentru alte elemente.

Pasul 6. Să revenim la pasul 2.

a 2-a etapa: găsirea soluției optime.

Pasul 1. Se verifică semnul optimității soluției.

Semne ale unei soluții optime:

a) funcţia obiectiv va avea o valoare maximă în cazul în care în linia (expresia) funcţiei obiectiv în forma standard de notare toţi coeficienţii variabilelor libere sunt pozitivi (nu se consideră termenul liber);

b) funcţia obiectiv va avea valoarea minimaîn cazul în care în linia funcției obiectiv în formă standard toți coeficienții variabilelor libere sunt negativi;

c) dacă în exprimarea funcției țintă în formă standard toți coeficienții variabilelor sunt de același semn și există cel puțin un coeficient zero, atunci soluția rezultată este alternativă, adică va exista un alt set de variabile care livrează aceeași valoare pentru funcția țintă.

Dacă criteriul de optimitate este satisfăcut, atunci s-a găsit o soluție. Valorile variabilelor libere sunt egale cu zero, valorile variabilelor de bază sunt egale cu termenii liberi ai constrângerilor corespunzătoare, valoarea funcției obiectiv este egală cu termenul liber al funcției obiectiv. Dacă criteriul de optimitate nu este satisfăcut, treceți la pasul 2.

Pasul 2.În conformitate cu regula de alegere a unei noi variabile de bază, transferăm una dintre variabilele libere în cele de bază.

Regula pentru alegerea unei variabile libere pentru a fi transferată la o bază

La căutarea maximului (minimului) unei funcții scrise în formă standard, trebuie transferată la bază o variabilă care are un coeficient negativ (pozitiv) în exprimarea funcției obiectiv în formă standard. Dacă există mai mult de un coeficient negativ (pozitiv). c j, apoi alegeți o variabilă care are o valoare absolută mai mare coeficient negativ (pozitiv). c j .

Pasul 3.În conformitate cu regula de alegere a unei variabile transferate de la bază la liberă, definim o nouă variabilă liberă.

Să formulăm regula pentru alegerea unei variabile care urmează să fie convertită de la bază la liberă.

Pentru a selecta o nouă variabilă liberă x i atitudinea trebuie luată în considerare b j /o ij pentru toate restricțiile (
), (
), din aceste relații selectați minimul, iar ca o nouă variabilă liberă selectați variabila de bază pentru care s-a obținut relația minimă pentru a limita b j /o ij. Atitudine b j /o ij ar trebui luate în considerare numai pentru pozitiv o ij. Dacă minimul este atins pentru mai mult de un indice j, apoi oricare dintre variabilele corespunzătoare j-a restrictii.

Dacă niciunul dintre o ij nu este pozitivă, atunci obținerea unei noi soluții fezabile este imposibilă, adică la căutarea unui minim, funcția obiectiv nu este limitată de jos, iar la căutarea unui maxim, nu este limitată de sus ( semn de nelimitare a funcției obiective).

Pasul 4. Baza este înlocuită în mod similar cu pasul 5 din prima etapă.

Pasul 5. Să trecem la pasul 1.

Exemplul 2. Găsiți sub restricții

Să scriem problema în formă standard și să o prezentăm sub forma unui tabel simplex:

Semnul inconsecvenței restricțiilor nu este satisfăcut. Nu s-a găsit o soluție admisibilă, întrucât termenul liber pentru constrângere x 5 este egal cu -5. Pentru a obține o soluție admisibilă, schimbăm baza. Să alegem ca coloană de rezolvare x 1 ; linie de permisiune - x 6 (din 2/1<5/2). Разрешающий элемент подчеркнут. Строим новую симплекс-таблицу.

Una dintre metodele de rezolvare a problemelor de optimizare ( asociată de obicei cu găsirea minimului sau maximului) programarea liniară se numește . Metoda simplex include un întreg grup de algoritmi și metode pentru rezolvarea problemelor de programare liniară. Una dintre aceste metode, care presupune înregistrarea datelor sursă și recalcularea lor într-un tabel special, se numește metoda tabulară simplex.

Să luăm în considerare algoritmul metodei simplex tabulare folosind exemplul soluției sarcina de productie, care se rezumă la găsirea unui plan de producție care să asigure profit maxim.

Date de intrare pentru problema metodei simplex

Compania produce 4 tipuri de produse, prelucrandu-le pe 3 masini.

Standardele de timp (min./buc) pentru prelucrarea produselor pe mașini sunt specificate de matricea A:

Fondul de timp de funcționare al mașinii (min.) este specificat în matricea B:

Profitul din vânzarea fiecărei unități de produs (RUB/buc) este dat de matricea C:

Scopul sarcinii de producție

Întocmește un plan de producție care să maximizeze profitul întreprinderii.

Rezolvarea problemei folosind metoda simplex tabelar

(1) Să notăm cu X1, X2, X3, X4 numărul planificat de produse de fiecare tip. Apoi planul dorit: ( X1, X2, X3, X4)

(2) Să notăm constrângerile planului sub forma unui sistem de ecuații:

(3) Atunci profitul tinta este:

Adică, profitul din îndeplinirea planului de producție ar trebui să fie maxim.

(4) Pentru a rezolva problema extremumului condiționat rezultat, înlocuim sistemul de inegalități cu un sistem de ecuații liniare prin introducerea unor variabile suplimentare nenegative în el ( X5, X6, X7).

(5) Să acceptăm următoarele plan de referință:

X1 = 0, X2 = 0, X3 = 0, X4 = 0, X5 = 252, X6 = 144, X7 = 80

(6) Să introducem datele în tabel simplex:

În ultima linie introducem coeficienții funcției obiectiv și valoarea acesteia însăși cu semnul opus;

(7) Selectați în ultima linie cel mai mare (modulo) este un număr negativ.

Să calculăm b = N / Elemente_din_coloana_selectată

Dintre valorile calculate ale lui b alegem cel mai puţin.

Intersecția coloanei și rândului selectate ne va oferi elementul de rezolvare. Schimbăm baza într-o variabilă corespunzătoare elementului de rezolvare ( X5 la X1).

• Elementul de rezolvare în sine se transformă în 1.
• Pentru elementele liniei de rezoluție – a ij (*) = a ij / RE ( adică împărțim fiecare element la valoarea elementului de rezoluție și obținem date noi).
• Pentru elementele coloanei de rezoluție, acestea sunt pur și simplu resetate la zero.
• Recalculăm elementele rămase ale tabelului folosind regula dreptunghiului.

a ij (*) = a ij – (A * B / RE)

După cum puteți vedea, luăm celula curentă care este recalculată și celula cu elementul de rezolvare. Ele formează colțuri opuse ale dreptunghiului. Apoi, înmulțim valorile din celulele celorlalte 2 colțuri ale acestui dreptunghi. Această lucrare ( O * B) împărțiți la elementul de rezolvare ( RE). Și scade din celula curentă care este recalculată ( a ij) Ce s-a întâmplat. Obținem o nouă valoare - a ij (*).

(9) Verificați din nou ultima linie ( c) pe prezența numerelor negative. Dacă nu sunt acolo, a fost găsit planul optim, trecem la ultima etapă de rezolvare a problemei. Dacă există, planul nu este încă optim și tabelul simplex trebuie recalculat din nou.

Deoarece avem din nou numere negative în ultima linie, începem o nouă iterație de calcule.

(10) Deoarece nu există elemente negative în ultima linie, asta înseamnă că am găsit planul optim de producție! Și anume: vom produce acele produse care s-au mutat în coloana „Base” - X1 și X2. Cunoaștem profitul din producția fiecărei unități de producție ( matricea C). Rămâne să înmulțim volumele de producție găsite ale produselor 1 și 2 cu profit pe 1 bucată, obținem finalul ( maxim! ) profit pentru un plan de producție dat.

RĂSPUNS:

X1 = 32 buc., X2 = 20 buc., X3 = 0 buc., X4 = 0 buc.

P = 48 * 32 + 33 * 20 = 2.196 rub.

Galyautdinov R.R.

© Copierea materialului este permisă numai dacă există un hyperlink direct către

Să luăm în considerare metoda simplex pentru rezolvarea problemelor de programare liniară (LP). Se bazează pe trecerea de la un plan de referință la altul, timp în care valoarea funcției obiectiv crește.

Algoritmul metodei simplex este următorul:

1. Transformăm problema inițială în formă canonică prin introducerea de variabile suplimentare. Pentru inegalitățile de forma ≤, variabilele suplimentare se introduc cu semnul (+), dar dacă de forma ≥, atunci cu semnul (-). Variabilele suplimentare sunt introduse în funcția obiectiv cu semne corespunzătoare cu un coeficient egal cu 0 , pentru că funcția țintă nu trebuie să-și schimbe sensul economic.
2. Vectorii sunt scrisi P i din coeficienții variabilelor și coloana termenilor liberi. Această acțiune determină numărul de vectori unitari. Regula este că ar trebui să existe atâția vectori unitari câte inegalități există în sistemul de constrângeri.
3. După aceasta, datele sursă sunt introduse într-un tabel simplex. În bază sunt introduși vectori unitari, iar prin excluderea lor din bază se găsește soluția optimă. Coeficienții funcției obiectiv se scriu cu semnul opus.
4. Un semn de optimitate pentru o problemă LP este că soluția este optimă dacă există f– în rând toți coeficienții sunt pozitivi. Regula pentru găsirea coloanei de activare - vizualizată f– un șir și dintre elementele sale negative este selectat cel mai mic. Vector P i conținutul său devine permisiv. Regula pentru alegerea unui element de rezoluție - sunt compilate rapoartele elementelor pozitive ale coloanei de rezoluție la elementele vectorului P 0 iar numărul care dă cel mai mic raport devine elementul de rezolvare în raport cu care va fi recalculat tabelul simplex. Linia care conține acest element se numește linie de activare. Dacă nu există elemente pozitive în coloana de rezoluție, atunci problema nu are soluție. După determinarea elementului de rezolvare, se procedează la recalcularea unui nou tabel simplex.
5. Reguli pentru completarea unui nou tabel simplex. Unitatea este pusă în locul elementului de rezolvare și se presupune că celelalte elemente sunt egale 0 . Vectorul de rezoluție este adăugat la bază, din care vectorul zero corespunzător este exclus, iar vectorii de bază rămași sunt scrieți fără modificări. Elementele șirului de rezoluție sunt împărțite la elementul de rezoluție, iar elementele rămase sunt recalculate conform regulii dreptunghiului.
6. Acest lucru se face până când f– toate elementele șirului nu vor deveni pozitive.

Să luăm în considerare rezolvarea problemei folosind algoritmul discutat mai sus.
Dat:

Aducem problema la forma canonică:

Compunem vectorii:

Completați tabelul simplex:

:
Să recalculăm primul element al vectorului P 0, pentru care facem un dreptunghi de numere: și obținem: .

Efectuăm calcule similare pentru toate celelalte elemente ale tabelului simplex:

În planul primit f– linia conține un element negativ – ​​(-5/3), vector P 1. Acesta conține în coloana sa un singur element pozitiv, care va fi elementul de activare. Să recalculăm tabelul cu privire la acest element:

Fără elemente negative în f– linie înseamnă găsit plan optim:
F* = 36/5, X = (12/5, 14/5, 8, 0, 0).

• Ashmanov S. A. Programare liniară, M: Nauka, 1998,
• Ventzel E.S. Cercetare operațională, M: Radio sovietică, 2001,
• Kuznețov Yu.N., Kuzubov V.I., Voloșenko A.B. Programare matematică, M: Liceu, 1986.

Soluție de programare liniară personalizată

Puteți comanda orice teme din această disciplină pe site-ul nostru. Puteți atașa fișiere și specifica termenele limită la