Serviciu pentru rezolvarea problemelor de programare liniară. Rezolvarea unei probleme de producție folosind metoda simplex tabelară Funcția obiectivă a metodei simplex

. Algoritmul metodei simplex

Exemplul 5.1. Rezolvați următoarea problemă de programare liniară folosind metoda simplex:

Soluţie:

eu repetare:

x3, x4, x5, x6 x1,x2. Să exprimăm variabilele de bază în termeni de cele libere:

Să reducem funcția țintă la următoarea vedere:

Pe baza problemei obținute, vom forma tabelul simplex inițial:

Tabelul 5.3

Tabel simplex original

				Relații evaluative

Conform definiției soluției de bază, variabilele libere sunt egale cu zero, iar valorile variabilelor de bază sunt egale cu valorile corespunzătoare ale numerelor libere, adică:

Etapa 3: verificarea compatibilității sistemului de restricții PAP.

La această iterație (în Tabelul 5.3), semnul de inconsecvență al sistemului de constrângeri (semnul 1) nu este identificat (adică nu există o linie cu un număr liber negativ (cu excepția liniei funcției obiectiv) în care să nu existe să fie cel puțin un element negativ (adică coeficient negativ pentru o variabilă liberă)).

La această iterație (în Tabelul 5.3), semnul de nemărginire al funcției obiectiv (semnul 2) nu a fost identificat (adică nu există nicio coloană cu un element negativ în rândul funcției obiectiv (cu excepția coloanei numerelor libere). ) în care nu ar exista cel puţin un element pozitiv) .

Deoarece soluția de bază găsită nu conține componente negative, este admisibilă.

Etapa 6: verificarea optimității.

Soluția de bază găsită nu este optimă, deoarece conform criteriului de optimitate (semnul 4) linia funcției obiectiv nu trebuie să conțină elemente negative(numarul liber al acestei linii nu este luat in considerare atunci cand se ia in considerare aceasta caracteristica). Prin urmare, conform algoritmului metodei simplex, trecem la etapa 8.

Întrucât soluția de bază găsită este admisibilă, vom căuta coloana de rezolvare după următoarea schemă: determinăm coloanele cu elemente negative din rândul funcției obiectiv (cu excepția coloanei numerelor libere). Conform Tabelului 5.3, există două astfel de coloane: coloana „ x1„și coloana” x2" Din astfel de coloane se selectează cel care conține cel mai mic element din rândul funcției țintă. Ea va fi cea permisivă. Coloana " x2" conține cel mai mic element (–3) în comparație cu coloana " x1

Pentru a determina linia de rezolvare, găsim rapoartele pozitive estimate ale numerelor libere la elementele coloanei de rezoluție se acceptă ca fiind rezolvată linia care corespunde celui mai mic raport de evaluare pozitivă;

Tabelul 5.4

Tabel simplex original

În tabelul 5.4, cea mai mică relație de evaluare pozitivă corespunde liniei „ x5„, prin urmare, va fi permisiv.

Elementul situat la intersecția coloanei de activare și a rândului de activare este acceptat ca activator. În exemplul nostru, acesta este elementul care se află la intersecția liniei „ x5„și coloane” x2».

Elementul de rezolvare arată o bază și o variabilă liberă care trebuie schimbate în tabelul simplex pentru a trece la o nouă soluție de bază „îmbunătățită”. ÎN în acest caz, acestea sunt variabile x5Şi x2, în noul tabel simplex (Tabelul 5.5) le schimbăm.

9.1. Transformarea elementului rezolutiv.

Elementul de rezoluție din tabelul 5.4 este convertit după cum urmează:

Introducem rezultatul rezultat într-o celulă similară din Tabelul 5.5.

9.2. Conversie șir de rezoluție.

Împărțim elementele rândului de rezolvare a tabelului 5.4 la elementul de rezolvare al acestui tabel simplex, rezultatele se încadrează în celule similare ale noului tabel simplex (tabelul 5.5). Transformările elementelor șirului de rezoluție sunt date în Tabelul 5.5.

9.3. Conversia coloanei de rezoluție.

Împărțim elementele coloanei de rezoluție din tabelul 5.4 la elementul de rezoluție al acestui tabel simplex, iar rezultatul este luat cu semnul opus. Rezultatele obținute se încadrează în celule similare ale noului tabel simplex (Tabelul 5.5). Transformările elementelor coloanei de rezoluție sunt date în Tabelul 5.5.

9.4. Transformarea elementelor rămase ale tabelului simplex.

Transformarea elementelor rămase ale tabelului simplex (adică elementele care nu sunt situate în rândul de rezolvare și coloana de rezolvare) se realizează conform regulii „dreptunghi”.

De exemplu, luați în considerare transformarea unui element situat la intersecția liniei " x3„ și coloanele „”, îl vom desemna condiționat „ x3" În tabelul 5.4, desenăm mental un dreptunghi, al cărui vârf se află în celula a cărei valoare o transformăm (adică în celula „ x3"), iar celălalt (vertex diagonal) este într-o celulă cu un element de rezoluție. Celelalte două vârfuri (ale celei de-a doua diagonale) sunt determinate în mod unic. Apoi valoarea transformată a celulei " x3" va fi egală cu valoarea anterioară a acestei celule minus fracția, în numitorul căreia se află elementul de rezoluție (din tabelul 5.4), iar în numărător este produsul altor două vârfuri neutilizate, adică:

« x3»: .

Valorile altor celule sunt convertite în mod similar:

« x3 x1»: ;

« x4»: ;

« x4 x1»: ;

« x6»: ;

« x6 x1»: ;

«»: ;

« x1»: .

Ca urmare a acestor transformări, a fost obținut un nou tabel simplex (Tabelul 5.5).

II repetare:

Etapa 1: întocmirea unui tabel simplex.

Tabelul 5.5

Tabel simplexII iterații

				Estimată relaţie

Etapa 2: determinarea soluției de bază.

Ca rezultat al transformărilor simplex, a fost obținută o nouă soluție de bază (Tabelul 5.5):

După cum puteți vedea, cu această soluție de bază valoarea funcției obiectiv = 15, care este mai mare decât cu soluția de bază anterioară.

Incoerența sistemului de restricții în conformitate cu caracteristica 1 din Tabelul 5.5 nu a fost identificată.

Etapa 4: verificarea mărginirii funcției obiectiv.

Nelimitarea funcției obiectiv în conformitate cu criteriul 2 din Tabelul 5.5 nu este dezvăluită.

Etapa 5: verificarea admisibilității soluției de bază găsite.

Soluția de bază găsită conform criteriului 4 nu este optimă, deoarece linia funcției obiectiv a tabelului simplex (Tabelul 5.5) conține un element negativ: –2 (numărul liber al acestei linii nu este luat în considerare atunci când se consideră acest lucru caracteristică). Prin urmare, trecem la etapa 8.

Etapa 8: determinarea elementului rezolutiv.

8.1. Definiția coloanei de rezoluție.

Soluția de bază găsită este acceptabilă determinăm coloanele cu elemente negative din rândul funcției obiectiv (cu excepția coloanei numerelor libere). Conform Tabelului 5.5, există o singură astfel de coloană: „ x1" Prin urmare, îl acceptăm așa cum este permis.

8.2. Definiția unui șir de activare.

Conform valorilor obținute ale relațiilor evaluative pozitive din tabelul 5.6, minimul este relația corespunzătoare liniei „ x3" Prin urmare, îl acceptăm așa cum este permis.

Tabelul 5.6

Tabel simplexII iterații

				Estimată relaţie
				3/1=3 – min

Etapa 9: transformarea tabelului simplex.

Transformările tabelului simplex (Tabelul 5.6) sunt efectuate în același mod ca în iterația anterioară. Rezultatele transformărilor elementelor tabelului simplex sunt prezentate în Tabelul 5.7.

III repetare

Pe baza rezultatelor transformărilor simplex ale iterației anterioare, compilam un nou tabel simplex:

Tabelul 5.7

Tabel simplexIII iterații

				Estimată relaţie

Etapa 2: determinarea soluției de bază.

Ca rezultat al transformărilor simplex, a fost obținută o nouă soluție de bază (Tabelul 5.7):

Etapa 3: verificarea compatibilității sistemului de restricții.

Incoerența sistemului de restricții în conformitate cu caracteristica 1 din Tabelul 5.7 nu a fost identificată.

Etapa 4: verificarea mărginirii funcției obiectiv.

Nelimitarea funcției obiectiv în conformitate cu criteriul 2 din Tabelul 5.7 nu este dezvăluită.

Etapa 5: verificarea admisibilității soluției de bază găsite.

Soluția de bază găsită în conformitate cu criteriul 3 este admisibilă, deoarece nu conține componente negative.

Etapa 6: verificarea optimității soluției de bază găsite.

Soluția de bază găsită conform criteriului 4 nu este optimă, deoarece linia funcției obiectiv a tabelului simplex (Tabelul 5.7) conține un element negativ: –3 (numărul liber al acestei linii nu este luat în considerare atunci când se consideră acest lucru). caracteristică). Prin urmare, trecem la etapa 8.

Etapa 8: determinarea elementului rezolutiv.

8.1. Definiția coloanei de rezoluție.

Soluția de bază găsită este acceptabilă determinăm coloanele cu elemente negative din rândul funcției obiectiv (cu excepția coloanei numerelor libere). Conform Tabelului 5.7, există o singură astfel de coloană: „ x5" Prin urmare, îl acceptăm așa cum este permis.

8.2. Definiția unui șir de activare.

Conform valorilor obținute ale relațiilor evaluative pozitive din tabelul 5.8, minimul este relația corespunzătoare liniei „ x4" Prin urmare, îl acceptăm așa cum este permis.

Tabelul 5.8

Tabel simplexIII iterații

				Estimată relaţie
				5/5=1 – min

Etapa 9: transformarea tabelului simplex.

Transformările tabelului simplex (Tabelul 5.8) sunt efectuate în același mod ca în iterația anterioară. Rezultatele transformărilor elementelor tabelului simplex sunt prezentate în Tabelul 5.9.

IV repetare

Etapa 1: construirea unei noi mese simplex.

Pe baza rezultatelor transformărilor simplex ale iterației anterioare, compilam un nou tabel simplex:

Tabelul 5.9

Tabel simplexIV iterații

				Estimată relaţie
			–(–3/5)=3/5
			–(1/5)=–1/5
			–(9/5)=–9/5
			–(–3/5)=3/5

Etapa 2: determinarea soluției de bază.

Ca urmare a transformărilor simplex s-a obţinut o nouă soluţie de bază conform Tabelului 5.9, soluţia este următoarea:

Etapa 3: verificarea compatibilității sistemului de restricții.

Incoerența sistemului de restricții în conformitate cu caracteristica 1 din Tabelul 5.9 nu a fost identificată.

Etapa 4: verificarea mărginirii funcției obiectiv.

Nelimitarea funcției obiectiv în conformitate cu criteriul 2 din Tabelul 5.9 nu este dezvăluită.

Etapa 5: verificarea admisibilității soluției de bază găsite.

Soluția de bază găsită în conformitate cu criteriul 3 este admisibilă, deoarece nu conține componente negative.

Etapa 6: verificarea optimității soluției de bază găsite.

Soluția de bază găsită în conformitate cu caracteristica 4 este optimă, deoarece nu există elemente negative în linia funcției obiectiv a tabelului simplex (Tabelul 5.9) (numărul liber al acestei linii nu este luat în considerare atunci când se ia în considerare această caracteristică) .

Etapa 7: verificarea alternativei soluției.

Soluția găsită este unică, deoarece nu există elemente zero în linia funcției obiectiv (Tabelul 5.9) (numărul liber al acestei linii nu este luat în considerare atunci când se consideră această caracteristică).

Răspuns: valoarea optimă a funcţiei obiectiv a problemei luate în considerare =24, care se realizează la.

Exemplul 5.2. Rezolvați problema de programare liniară de mai sus, cu condiția ca funcția obiectiv să fie minimizată:

Soluţie:

eu repetare:

Etapa 1: formarea tabelului simplex inițial.

Problema originală de programare liniară este dată în formă standard. Să o aducem la forma canonică prin introducerea unei variabile suplimentare nenegative în fiecare dintre constrângerile de inegalitate, i.e.

În sistemul de ecuații rezultat luăm ca variabile permise (de bază). x3, x4, x5, x6, atunci variabilele libere vor fi x1,x2. Să exprimăm variabilele de bază în termeni de cele libere.

O metodă universală pentru rezolvarea problemelor LP se numește metoda simplex. Aplicarea acestei metode și cea mai comună modificare a acesteia - metoda simplex în două faze.

În metoda grafică de rezolvare a problemelor LP, am ales de fapt din mulțimea de vârfuri aparținând graniței mulțimii de soluții la sistemul de inegalități vârful la care valoarea funcției obiectiv a atins un maxim (minim). În cazul a două variabile, această metodă este complet intuitivă și vă permite să găsiți rapid o soluție la problemă.

Dacă o problemă are trei sau mai multe variabile, iar în problemele economice reale aceasta este exact situația, este dificil de vizualizat zona de soluție a sistemului de constrângeri. Astfel de probleme sunt rezolvate folosind metoda simplex sau prin metoda îmbunătăţirilor succesive. Ideea metodei este simplă și este următoarea.

După o anumită regulă, se găsește planul de referință inițial (un vârf al zonei de constrângere). Verifică dacă planul este optim. Dacă da, atunci problema este rezolvată. Dacă nu, atunci trecem la un alt plan îmbunătățit - la un alt vârf. valoarea funcției obiectiv pe acest plan (la acest vârf) este evident mai bună decât în ​​cel precedent. Algoritmul de tranziție este realizat folosind un anumit pas de calcul, care este convenabil scris sub formă de tabele numite tabele simplex . Deoarece există un număr finit de vârfuri, într-un număr finit de pași ajungem la soluția optimă.

Luați în considerare metoda simplex exemplu concret sarcini privind întocmirea unui plan.

Să remarcăm încă o dată că metoda simplex este aplicabilă rezolvării problemelor canonice LP reduse la o formă specială, adică având o bază, părți din dreapta pozitive și o funcție obiectiv exprimată în termeni de variabile nebazice. Dacă sarcina nu este redusă la o formă specială, atunci sunt necesari pași suplimentari, despre care vom vorbi mai târziu.

Să luăm în considerare problema unui plan de producție, după ce am construit anterior un model și l-am adus într-o formă specială.

Sarcină.

Pentru fabricarea produselor OŞi ÎN Depozitul poate elibera cel mult 80 de unități de materii prime. Mai mult, pentru fabricarea produsului O se consumă două unităţi, iar produsele ÎN- o unitate de materii prime. Este necesar să se planifice producția astfel încât să se asigure cel mai mare profit în cazul produselor O este necesar să producă nu mai mult de 50 de bucăți și produse ÎN- nu mai mult de 40 buc. Mai mult, profitul din vânzarea unui produs O- 5 ruble, și de la ÎN- 3 freci.

Să construim model matematic, notând ca X 1 cantitate de produse A in plan, pt X 2 - numărul de produse ÎN. atunci sistemul de constrângeri va arăta astfel:

x 1 ≤50
x 2 ≤40
2x 1 +x 2 ≤80
x 1 ≥0, x 2 ≥0
5x 1 +3x 2 →max

Să aducem problema în formă canonică prin introducerea de variabile suplimentare:

x 1 +x 3 =50
x 2 +x 4 =40
2x 1 +x 2 +x 5 =80
x 1 ≥0, x 2 ≥0
5x 1 +3x 2 →max
-F = -5x 1 - 3x 2 → min.

Această problemă are o formă specială (cu o bază, părțile din dreapta sunt nenegative). Poate fi rezolvată folosind metoda simplex.

euetapă.Înregistrarea unei probleme într-un tabel simplex. Există o corespondență unu-la-unu între sistemul de constrângeri al problemei (3.10) și tabelul simplex. Există atâtea rânduri în tabel câte egalități există în sistemul de constrângeri și sunt atâtea coloane câte variabile libere. Variabilele de bază umplu prima coloană, variabilele libere umplu rândul de sus al tabelului. Linia de jos se numește linia indicelui coeficienții variabilelor din funcția obiectiv; În colțul din dreapta jos, inițial se scrie 0 dacă nu există niciun membru liber în funcție; dacă există, atunci scrieți-l cu semnul opus. În acest loc (în colțul din dreapta jos) va exista o valoare a funcției obiectiv, care ar trebui să crească în valoare absolută la trecerea de la un tabel la altul. Deci, Tabelul 3.4 corespunde sistemului nostru de restricții și putem trece la etapa II a soluției.

Tabelul 3.4

de bază			gratuit

IIetapă. Verificarea optimității planului de referință.

Acest tabel 3.4 corespunde următorului plan de referință:

(X 1 , X 2 , X 3 , X 4 , X 5) = (0, 0, 50, 40, 80).

Variabile libere X 1 , X 2 este egal cu 0; X 1 = 0, X 2 = 0. Și variabilele de bază X 3 , X 4 , X 5 iau valori X 3 = 50, X 4 = 40, X 5 = 80 - din coloana termeni liberi. Valoarea funcției obiective:

-F = - 5X 1 - 3X 2 = -5 0 - 3 0 = 0.

Sarcina noastră este să verificăm dacă un anumit plan de referință este optim. Pentru a face acest lucru, trebuie să vă uitați la linia index - linia funcției țintă F.

Sunt posibile diverse situații.

1. În index F- nu există elemente negative în șir. Aceasta înseamnă că planul este optim și o soluție la problemă poate fi scrisă. Funcția obiectiv și-a atins scopul valoare optimă, egală cu numărul, stând în colțul din dreapta jos, luată cu semnul opus. Să trecem la etapa a IV-a.

2. Rândul index are cel puțin un element negativ a cărui coloană nu are elemente pozitive. Apoi concluzionăm că funcţia obiectiv F→∞ scade fără limită.

3. Rândul index are un element negativ care are cel puțin un element pozitiv în coloana sa. Apoi trecem la următoarea etapă III. Recalculăm tabelul, îmbunătățind planul de referință.

IIIetapă. Îmbunătățirea planului de referință.

Din elementele negative ale indicelui F-rânduri, selectați-l pe cel cu cel mai mare modul, apelați coloana corespunzătoare rezolvând și marcați-l cu „”.

Pentru a selecta un rând de rezolvare, este necesar să se calculeze rapoartele elementelor coloanei de termeni liberi numai La pozitiv elemente ale coloanei de rezoluție. Selectați cel minim dintre relațiile obținute. Elementul corespunzător la care se atinge minimul se numește rezolvare. O vom evidenția cu un pătrat.

În exemplul nostru, elementul 2 este permisiv. Linia corespunzătoare acestui element se mai numește și rezolvare (Tabelul 3.5).

Tabelul 3.5

După ce am selectat elementul care permite, recalculăm tabelul conform regulilor:

1. Într-un tabel nou de aceeași dimensiune ca și înainte, variabilele rândului și coloanei de rezolvare sunt schimbate, ceea ce corespunde trecerii la o nouă bază. În exemplul nostru: X 1 este inclus în bază, în schimb X 5, care părăsește baza și este acum liber (Tabelul 3.6).

Tabelul 3.6

2. În locul elementului de rezoluție 2, scrieți numărul său invers ½.

3. Împărțim elementele liniei de rezoluție la elementul de rezoluție.

4. Împărțim elementele coloanei de rezoluție la elementul de rezoluție și le scriem cu semnul opus.

5. Pentru a completa elementele rămase din tabelul 3.6, recalculăm folosind regula dreptunghiului. Să presupunem că vrem să numărăm elementul la poziția 50.

Conectăm mental acest element cu cel de rezoluție, găsim produsul, scădem produsul elementelor situate pe cealaltă diagonală a dreptunghiului rezultat. Împărțim diferența la elementul de rezolvare.

Deci, . Scriem 10 în locul unde erau 50. În mod similar:
, , , .

Tabelul 3.7

Avem un nou tabel 3.7, variabilele de bază sunt acum variabilele (x 3,x 4,x 1). Valoarea funcției obiectiv a devenit -200, i.e. a scăzut. Pentru a verifica optimitatea acestei soluții de bază, trebuie să trecem din nou la etapa II. Procesul este evident finit, criteriul de oprire este punctele 1 și 2 din etapa II.

Să completăm soluția problemei. Pentru a face acest lucru, să verificăm linia index și, văzând un element negativ -½ în ea, apelăm rezolvarea coloanei corespunzătoare și, conform etapei III, recalculam tabelul. După compilarea relațiilor și alegând minimul = 40 dintre ele, am determinat elementul de rezolvare 1. Acum efectuăm recalcularea conform regulilor 2-5.

Tabelul 3.8

După recalcularea tabelului, ne asigurăm că nu există elemente negative în rândul index, prin urmare, problema este rezolvată, planul de bază este optim.

IVetapă. Scrierea soluției optime.

Dacă metoda simplex s-a oprit conform punctului 1 al etapei II, atunci soluția problemei este scrisă după cum urmează. Variabilele de bază preiau valorile coloanei de termeni inactivi în consecință. În exemplul nostru X 3 = 30, X 2 = 40, X 1 = 20. Variabilele libere sunt 0, X 5 = 0, X 4 = 0. Funcția obiectiv ia valoarea ultimului element al coloanei de termeni liberi cu semnul opus: - F = -220 → F= 220, în exemplul nostru funcția a fost examinată la min și inițial F→ max, deci semnul s-a schimbat efectiv de două ori. Aşa, X* = (20, 40, 30, 0, 0), F* = 220. Răspuns la problemă:

Este necesar să se includă 20 de produse de acest tip în planul de producție O, 40 de produse de tip B, în timp ce profitul va fi maxim și va fi egal cu 220 de ruble.

La sfârșitul acestei secțiuni, prezentăm o diagramă a algoritmului metodei simplex, care repetă exact pașii, dar poate pentru unii cititori va fi mai convenabil de utilizat, deoarece săgețile indică o direcție clară a acțiunilor.

Legăturile de deasupra casetelor din diagramă indică la ce etapă sau subpunct aparține grupul corespunzător de transformări. regula de găsire a planului de referință inițial va fi formulată în paragraful 3.7.

Exemplu. Rezolvați următoarea problemă LP în formă canonică folosind metoda simplex.
f(x)=x 1 +9x 2 +5x 3 +3x 4 +4x 5 +14x 6 → min
x 1 +x 4 =20
x 2 +x 5 =50
x 3 +x 6 =30
x 4 +x 5 +x 6 =60
x i ≥ 0, i = 1,…,6
Se spune că o problemă LP are o formă canonică dacă toate restricțiile (cu excepția condițiilor pentru non-negativitatea variabilelor) au forma de egalități, iar toți termenii liberi sunt nenegativi. Deci avem problema în formă canonică.
Ideea metodei simplex este următoarea. Mai întâi trebuie să găsiți un vârf (inițial) al poliedrului de soluții fezabile (soluție de bază fezabilă inițială). Apoi, trebuie să verificați această soluție pentru optimitate. Dacă este optim, atunci s-a găsit o soluție; dacă nu, atunci mergeți la alt vârf al poliedrului și verificați din nou optimitatea. Datorită finiturii vârfurilor poliedrului (o consecință a finiității constrângerilor problemei LP), într-un număr finit de „pași” vom găsi punctul necesar de minim sau maxim. De remarcat că la trecerea de la un vârf la altul, valoarea funcției obiectiv scade (în problema minimă) sau crește (în problema maximă).
Astfel, ideea metodei simplex se bazează pe trei proprietăți ale problemei LP.
Soluţie. Pentru a găsi soluția de bază fezabilă inițială, de ex. pentru a determina variabilele de bază, sistemul (5.6) trebuie redus la o formă „diagonală”. Folosind metoda gaussiana (metoda eliminarii secventiale a necunoscutelor), obtinem din (5.6):
x 2 +x 1 +x 3 =40
x 4 +x 1 =20
x 5 -x 1 -x 3 =10
x 6 +x 3 =30
Prin urmare, variabilele de bază sunt x 2 , x 4 , x 5 , x 6 , Le dăm valori egale cu membrii liberi ai șirurilor corespunzătoare: x 2 =40, x 4 =20, x 5 =10, x 6 =30,. Variabile x 1Şi x 3 nu sunt de bază: x 1 =0, x 3 =0.
Să construim soluția de bază fezabilă inițială
x 0 = (0,40,0,20,10,30) (5,9)
Pentru a verifica optimitatea soluției găsite x 0 este necesar să excludeți variabilele de bază din funcția țintă (folosind sistemul (5.8)) și să construiți un tabel special simplex.
După eliminarea variabilelor, este convenabil să scrieți funcția obiectiv sub forma:
f(x) = -7x 1 – 14x 3 +880 (5,10)
Acum, folosind (5.8)–(5.10), compunem tabelul simplex inițial:

Linia zero conține coeficienții cu semnul opus variabilelor corespunzătoare pentru funcția obiectiv. Criteriul de optimizare (pentru problema minimă de căutare): soluție de bază admisibilă( x 0) este optim dacă nu există un singur număr strict pozitiv în linia zero (fără numărarea valorii funcției obiectiv (880)). Această regulă se aplică și următoarelor iterații (tabele). Elementele din rândul zero vor fi numite estimări de coloană.
Deci soluția de bază fezabilă inițială (5.9) este suboptimă: 7>0, 14>0 .
Coloana zero conține valorile variabilelor de bază. Ele trebuie să fie nenegative (vezi ecuația (5.7)). Coeficienții variabilelor din sistemul (5.8) se scriu de la prima până la a patra rând.
Deoarece x 0 nu este optim, atunci trebuie să trecem la un alt vârf al poliedrului soluțiilor admisibile (construiți un nou d.b.r.). Pentru a face acest lucru, trebuie să găsiți elementul principal și să efectuați o anumită transformare (transformare simplex).
În primul rând, găsim elementul principal al tabelului, care se află la intersecția coloanei principale (coloana cu cel mai mare scor pozitiv) și rândul principal (rândul corespunzător raportului minim dintre elementele coloanei zero și elementele corespunzătoare (strict pozitive) ale coloanei principale).
În tabelul 1, coloana principală este a treia coloană, iar rândul principal este al patrulea rând. (min(40/1,30/1)=30/1) sunt indicate prin săgeți, iar elementul de conducere este indicat printr-un cerc. Elementul principal indică faptul că variabila de bază x 6 trebuie înlocuit cu unul care nu este de bază x 3. Atunci noile variabile de bază vor fi x 2 , x 3 , x 4 , x 5 ,, și nebază - x 1, x 6,. Aceasta înseamnă trecerea la un nou vârf al poliedrului soluțiilor admisibile. Pentru a găsi valorile coordonate ale unei noi soluții de bază fezabile x00 trebuie să construiți un nou tabel simplex și să efectuați transformări elementare în el:
O)împărțiți toate elementele liniei de conducere la elementul de conducere, transformând astfel elementul de conducere în 1 (pentru ușurința calculului);
b) folosind elementul principal (egal cu 1), transformați toate elementele coloanei principale în zerouri (asemănător cu metoda de eliminare a necunoscutelor);
Ca urmare, valorile noilor variabile de bază sunt obținute în coloana zero x 2 , x 3 , x 4 , x 5 ,(vezi tabelul 2) - componentele de bază ale noului vârf x00(componente care nu sunt de bază x 1 =0, x 6 =0,).

După cum arată Tabelul 2, noua soluție de bază x 00 =(0,10,30,20,40,0) suboptimal (linia zero conține un scor nenegativ de 7). Prin urmare, cu elementul principal 1 (a se vedea tabelul 2) construim un nou tabel simplex, i.e. construi o nouă soluție de bază fezabilă

Tabelul 3 corespunde unei soluții de bază acceptabile x 000 =(10,0,30,10,50,0) si este optim, pentru ca nu există evaluări pozitive în linia zero. De aceea f(x 000)=390 este valoarea minimă a funcției obiectiv.
Răspuns: x 000 =(10, 0, 30, 10, 50, 0)- punct minim, f(x 000)=390.

Problemă de programare liniară standard convențional

Trebuie să finalizați următoarele sarcini în ordinea afișată.

1. Găsiți planul optim pentru problema directă:
   a) metoda grafica;
   b) utilizarea metodei simplex (pentru construirea planului de referință inițial se recomandă utilizarea metodei bazei artificiale).
2. Construiți o problemă dublă.
3. Găsiți planul optim pentru problema duală din soluția grafică a dreptei, folosind condițiile de slăbiciune complementară.
4. Găsiți planul optim pentru problema duală folosind prima teoremă a dualității, folosind tabelul simplex final obținut prin rezolvarea problemei directe (vezi secțiunea 1b). Verificați afirmația „valorile funcțiilor obiective ale unei perechi de probleme duale coincid în soluțiile lor optime”.
5. Rezolvați problema duală folosind metoda simplex, apoi, folosind tabelul simplex final al problemei duale, găsiți planul optim pentru problema directă folosind prima teoremă a dualității. Comparați rezultatul cu rezultatul obținut grafic (a se vedea paragraful 1a).
6. Găsiți soluția optimă a întregului:
   a) metoda grafica;
   b) Metoda Gomori.
   Comparați valorile funcțiilor de soluție întregi și non-întregi

Întrebări pentru autocontrol

1. Cum se construiește un tabel simplex?
2. Cum se reflectă o modificare a bazei în tabel?
3. Formulați un criteriu de oprire pentru metoda simplex.
4. Cum se organizează recalcularea tabelului?
5. Care linie este convenabilă pentru a începe recalcularea tabelului?

Această metodă este o metodă de enumerare intenționată a soluțiilor de referință la o problemă de programare liniară. Permite, într-un număr finit de pași, fie să se găsească o soluție optimă, fie să se stabilească că nu există o soluție optimă.

Conținutul principal al metodei simplex este următorul:

1. Indicați o metodă pentru găsirea soluției de referință optime
2. Indicați metoda de trecere de la o soluție de referință la alta, la care valoarea funcției obiectiv va fi mai apropiată de cea optimă, adică. indica o modalitate de a îmbunătăți soluția de referință
3. Stabiliți criterii care vă permit să opriți imediat căutarea soluțiilor de asistență la soluția optimă sau să trageți o concluzie despre absența unei soluții optime.

Algoritmul metodei simplex pentru rezolvarea problemelor de programare liniară

Pentru a rezolva o problemă folosind metoda simplex, trebuie să faceți următoarele:

1. Aduceți problema în formă canonică
2. Găsiți soluția de suport inițială cu o „bază unitară” (dacă nu există o soluție de suport, atunci problema nu are o soluție din cauza incompatibilității sistemului de constrângeri)
3. Calculați estimări ale descompunerilor vectoriale pe baza soluției de referință și completați tabelul metodei simplex
4. Dacă criteriul de unicitate al soluției optime este îndeplinit, atunci soluția problemei se termină
5. Dacă este îndeplinită condiția existenței unui set de soluții optime, atunci toate soluțiile optime se găsesc prin enumerare simplă

Un exemplu de rezolvare a unei probleme folosind metoda simplex

Exemplul 26.1

Rezolvați problema folosind metoda simplex:

Soluţie:

Aducem problema în formă canonică.

Pentru a face acest lucru, introducem o variabilă suplimentară x 6 cu coeficient +1 în partea stângă a primei constrângeri de inegalitate. Variabila x 6 este inclusă în funcția obiectiv cu un coeficient de zero (adică nu este inclusă).

Primim:

Găsim soluția inițială de suport. Pentru a face acest lucru, echivalăm variabilele libere (nerezolvate) cu zero x1 = x2 = x3 = 0.

Primim soluție de referință X1 = (0,0,0,24,30,6) cu baza unitară B1 = (A4, A5, A6).

Noi calculăm estimări ale descompunerilor vectoriale condiții pe baza soluției de referință conform formulei:

Δ k = C b X k - c k

• C b = (c 1, c 2, ..., c m) - vector de coeficienți ai funcției obiectiv pentru variabilele de bază
• X k = (x 1k, x 2k, ..., x mk) - vector de expansiune a vectorului corespunzător A k în funcție de baza soluției de referință
• C k este coeficientul funcției obiectiv pentru variabila x k.

Estimările vectorilor incluși în bază sunt întotdeauna egale cu zero. Soluția de referință, coeficienții de expansiune și estimările expansiunilor vectorilor de condiții bazate pe soluția de referință sunt scrise în tabel simplex:

În partea de sus a tabelului, pentru ușurința calculului estimărilor, se scriu coeficienții funcției obiectiv. În prima coloană „B” sunt înscriși vectorii incluși în baza soluției de referință. Ordinea în care acești vectori sunt scriși corespunde numărului de necunoscute permise în ecuațiile de constrângere. În a doua coloană a tabelului „C b” se scriu în aceeași ordine coeficienții funcției obiectiv pentru variabilele de bază. Cu aranjarea corectă a coeficienților funcției obiectiv în coloana „C b”, estimările vectorilor unitari incluși în bază sunt întotdeauna egale cu zero.

În ultimul rând al tabelului cu estimări ale Δ k în coloana „A 0” sunt scrise valorile funcției obiectiv pe soluția de referință Z(X 1).

Soluția suport inițial nu este optimă, deoarece în problema maximă estimările Δ 1 = -2, Δ 3 = -9 pentru vectorii A 1 și A 3 sunt negative.

Conform teoremei de îmbunătățire a soluției suport, dacă în problema maximă cel puțin un vector are o estimare negativă, atunci puteți găsi o nouă soluție suport pe care valoarea funcției obiectiv va fi mai mare.

Să determinăm care dintre cei doi vectori va duce la o creștere mai mare a funcției obiectiv.

Incrementul functiei obiectiv se gaseste prin formula: .

Calculăm valorile parametrului θ 01 pentru prima și a treia coloană folosind formula:

Se obține θ 01 = 6 pentru l = 1, θ 03 = 3 pentru l = 1 (Tabelul 26.1).

Găsim incrementul funcției obiectiv la introducerea în bază a primului vector ΔZ 1 = - 6*(- 2) = 12, iar al treilea vector ΔZ 3 = - 3*(- 9) = 27.

În consecință, pentru o abordare mai rapidă a soluției optime, este necesar să se introducă vectorul A3 în baza soluției de referință în locul primului vector al bazei A6, deoarece minimul parametrului θ 03 este atins în primul rând ( l = 1).

Efectuăm transformarea Jordan cu elementul X13 = 2, obținem a doua soluție de referință X2 = (0,0,3,21,42,0) cu baza B2 = (A3, A4, A5). (Tabelul 26.2)

Această soluție nu este optimă, deoarece vectorul A2 are o estimare negativă Δ2 = - 6. Pentru a îmbunătăți soluția, este necesar să se introducă vectorul A2 în baza soluției de referință.

Determinăm numărul vectorului derivat din bază. Pentru a face acest lucru, calculăm parametrul θ 02 pentru a doua coloană, este egal cu 7 pentru l = 2. În consecință, derivăm al doilea vector de bază A4 din bază. Efectuăm transformarea Jordan cu elementul x 22 = 3, obținem a treia soluție de referință X3 = (0,7,10,0,63,0) B2 = (A3, A2, A5) (Tabelul 26.3).

Această soluție este singura optimă, deoarece pentru toți vectorii care nu sunt incluși în bază estimările sunt pozitive

Δ 1 = 7/2, Δ 4 = 2, Δ 6 = 7/2.

Răspuns: max Z(X) = 201 la X = (0,7,10,0,63).

Metoda de programare liniară în analiza economică

Metoda de programare liniară face posibilă justificarea celui mai optim decizie economică in conditii de restrictii severe legate de resursele folosite in productie (mijloace fixe, materiale, resurse de munca). Utilizarea acestei metode în analiza economică face posibilă rezolvarea problemelor legate în principal de planificarea activităților unei organizații. Această metodă ajută la determinarea cantităților optime de producție, precum și a direcțiilor de utilizare cât mai eficientă a resurselor de producție disponibile organizației.

Prin această metodă se rezolvă așa-numitele probleme extreme, care constă în găsirea valorilor extreme, adică a maximului și minimului de funcții ale mărimilor variabile.

Această perioadă se bazează pe rezolvarea unui sistem de ecuații liniare în cazurile în care fenomenele economice analizate sunt legate printr-o dependență liniară, strict funcțională. Metoda de programare liniară este utilizată pentru a analiza variabilele în prezența anumitor factori limitatori.

Este foarte comun să se rezolve așa-numita problemă de transport folosind metoda de programare liniară. Conținutul acestei sarcini este de a minimiza costurile suportate în legătură cu operațiunea vehicule sub restricțiile existente privind numărul de vehicule, capacitatea lor de transport, durata de funcționare a acestora, în cazul în care este nevoie de deservire a numărului maxim de clienți.

Pe langa asta, această metodă este utilizat pe scară largă în rezolvarea problemelor de programare. Această sarcină constă într-o astfel de distribuție a timpului de funcționare pentru personalul unei organizații date, care ar fi cea mai acceptabilă atât pentru membrii acestui personal, cât și pentru clienții organizației.

Această sarcină este de a maximiza numărul de clienți deserviți în condiții de limitare a numărului de membri ai personalului disponibil, precum și a fondului de timp de lucru.

Astfel, metoda de programare liniară este destul de comună în analiza plasării și utilizării. diverse tipuri resurselor, precum și în procesul de planificare și prognoză a activităților organizațiilor.

Cu toate acestea, programarea matematică poate fi aplicată și acelor fenomene economice, relația dintre care nu este liniară. În acest scop, pot fi utilizate metode de programare neliniară, dinamică și convexă.

Programarea neliniară se bazează pe natura neliniară a funcției obiectiv sau a constrângerilor, sau ambele. Formele funcției obiective și constrângerile de inegalitate în aceste condiții pot fi diferite.

Programarea neliniară este utilizată în analiza economică, în special, atunci când se stabilește relația dintre indicatorii care exprimă eficiența activităților unei organizații și volumul acestei activități, structura costurilor de producție, condițiile pieței etc.

Programarea dinamică se bazează pe construirea unui arbore de decizie. Fiecare nivel al acestui arbore servește drept etapă pentru determinarea consecințelor unei decizii anterioare și pentru eliminarea opțiunilor ineficiente pentru acea decizie. Astfel, programarea dinamică are o natură în mai multe etape, în mai multe etape. Acest tip de programare este folosit în analiza economică pentru a găsi opțiuni optime pentru dezvoltarea unei organizații atât acum, cât și în viitor.

Programarea convexă este un tip de programare neliniară. Acest tip de programare exprimă natura neliniară a relației dintre rezultatele activităților unei organizații și costurile acesteia. Programarea convexă (alias concavă) analizează funcțiile obiectiv convexe și sistemele de constrângeri convexe (puncte valori acceptabile). Programare convexă aplicată în analiză activitate economicăîn vederea minimizării costurilor, şi concavă - în vederea maximizării veniturilor în condiţiile restricţiilor existente asupra acţiunii factorilor care influenţează în sens invers indicatorii analizaţi. În consecință, cu tipurile de programare luate în considerare, funcțiile obiectiv convexe sunt minimizate, iar funcțiile obiectiv concave sunt maximizate.

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 adecvate 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 selectarea unui element de rezoluție - sunt compilate rapoartele elementelor pozitive ale coloanei de rezolvare și 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 liniei 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

Principal ideea unei metode simplex pentru rezolvarea problemelor constă în îmbunătățirea consecventă a soluțiilor suport ale ZLP.

Există mai multe forme de scriere a metodei simplex.

1. Forma de bază de înregistrare prin metoda simplex;
2. Metoda simplex sub forma unui tabel simplex;
3. Metoda simplex modificată;
4. Metoda simplex sub formă de coloană;
5. Metoda simplex sub formă de linie.

Să determinăm valoarea maximă a funcției obiectiv F(X) = 3x 1 +5x 2 +4x 3 în următoarele condiții de constrângere.
0,1x 1 +0,2x 2 +0,4x 3 ≤1100
0,05x 1 +0,02x 2 +0,02x 3 ≤120
3x 1 +x 2 +2x 3 ≤8000

Pentru a construi primul plan de referință, reducem sistemul de inegalități la un sistem de ecuații prin introducerea de variabile suplimentare (tranziție la forma canonică).
0,1x 1 + 0,2x 2 + 0,4x 3 + 1x 4 + 0x 5 + 0x 6 = 1100
0,05x 1 + 0,02x 2 + 0,02x 3 + 0x 4 + 1x 5 + 0x 6 = 120
3x 1 + 1x 2 + 2x 3 + 0x 4 + 0x 5 + 1x 6 = 8000

Forma de bază de înregistrare prin metoda simplex

Soluția se realizează prin exprimarea variabilelor de bază în termeni de variabile nebazice: x 0 = 3x 1 +5x 2 +4x 3 x 4 = 1100-0,1x 1 -0,2x 2 -0,4x 3 x 5 = 120-0,05x 1 -0,02x 2 -0,02x 3 x 6 = 8000-3x 1 -x 2 -2x 3

Metoda simplex sub forma unui tabel simplex

Soluția este prezentată sub forma unui tabel simplex. Formularul este conceput pentru calcule computerizate. Când se utilizează o bază artificială, se folosește un număr special M (de obicei 10000).

Plan	Bază	ÎN	x 1	x 2	x 3	x 4	x 5	x 6	min
1	x4	1100	0.1	0.2	0.4	1	0	0	5500
	x5	120	0.05	0.02	0.02	0	1	0	6000
	x6	8000	3	1	2	0	0	1	8000
Linie index	F(X1)	0	-3	-5	-4	0	0	0	0
2	x2	5500	0.5	1	2	5	0	0	11000
	x5	10	0.04	0	-0.02	-0.1	1	0	250
	x6	2500	2.5	0	0	-5	0	1	1000
Linie index	F(X2)	27500	-0.5	0	6	25	0	0	0
3	x2	5375	0	1	2.25	6.25	-12.5	0	11000
	x1	250	1	0	-0.5	-2.5	25	0	250
	x6	1875	0	0	1.25	1.25	-62.5	1	1000
Linie index	F(X3)	27625	0	0	5.75	23.75	12.5	0	0

Metoda simplex modificată

Matricea coeficientilor A = a ij Matricea b. Iterația #1. = (4, 5, 6) Matricea c. c = (-3, -5, -4, 0, 0, 0) c B = (0, 0, 0) c N = (-3, -5, -4) Calculam: Matricea B -1 se calculează prin adunări algebrice. u = c B B -1 = (0, 0, 0)

Metoda simplex sub formă de coloană

Să trecem la forma coloană a metodei simplex. Să exprimăm fiecare variabilă în termeni de variabile non-bazice. x 0 = 0-3(-x 1)-5(-x 2)-4(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 1 = 0-1(-x 1)+0(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 2 = 0+0(-x 1)-1(-x 2)+0(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 3 = 0+0(-x 1)+0(-x 2)-1(-x 3)+0(-x 4)+0(-x 5)+0(-x 6) x 4 = 1100+0,1(-x 1)+0,2(-x 2)+0,4(-x 3)+1(-x 4)+0(-x 5)+0(-x 6) x 5 = 120+0,05(-x 1)+0,02(-x 2)+0,02(-x 3)+0(-x 4)+1(-x 5)+0(-x 6) x 6 = 8000+3(-x 1)+1(-x 2)+2(-x 3)+0(-x 4)+0(-x 5)+1(-x 6) Acest sistem corespunde tabelului T 0. 0 -1 0 0 0 0 -1 0 0 0 0 -1 1100 0.1 0.2 0.4 120 0.05 0.02 0.02 8000 3 1 2 0 -3 -5 -4

Metoda simplex sub formă de linie

Ca bază inițială admisibilă, putem lua B 0 =<4, 5, 6>. Următorul tabel îi va corespunde. 1100 0.1 0.2 0.4 1 0 0 120 0.05 0.02 0.02 0 1 0 8000 3 1 2 0 0 1 0 -3 -5 -4 0 0 0

Se numește matricea Q formată din coeficienții sistemului tabel simplex, corespunzător bazei B. Tabelul simplex se numește acceptabil, sau direct admisibil, dacă q i0 ≥ 0. Elementele q i0 din ultimul rând al tabelului simplex Q se numesc estimări relative.

Forme de soluție folosind metoda bazei artificiale

Pentru utilizarea variabilelor artificiale introduse în funcția obiectiv se impune o așa-numită penalizare a lui M, un număr pozitiv foarte mare care de obicei nu este specificat.
Baza rezultată se numește artificială, iar metoda soluției se numește metoda bazei artificiale.
Mai mult, variabilele artificiale nu sunt legate de conținutul problemei, dar permit construirea unui punct de plecare, iar procesul de optimizare obligă aceste variabile să ia valori zero și să asigure admisibilitatea soluției optime.

Forme de soluție folosind metoda bazei artificiale:

1. metoda M (tabel simplex);
2. Metoda simplex în două etape sau în două faze (Formă de înregistrare de bază, Metoda simplex modificată, Metoda Simplex în formă de coloană, Metoda Simplex în formă de linie).