Teoria Dualitatea programării liniare

Dualitatea teoremă în programarea liniară

- teoria care studiază proprietățile generale ale unei perechi de probleme de programare liniară duală strâns legate; utilizate pentru construirea de metode numerice de rezolvare a acestor probleme. Două probleme de programare liniară

în cazul în care toate - numere date, precum și toate variabilele acestor sarcini se numește. dublu (conjugat) pereche; fiecare dintre sarcinile se numește. dublă în raport cu cealaltă. Proprietatea este o pereche dublă de probleme exprimate în teoremele de dualitate.

Prima teoremă. Dacă Optim. Primul plan (2a) există problema, există FINE. Planul de alt dintre aceste sarcini, în același timp, pentru orice pereche de planuri admise ale acestor probleme este inegalitatea devine o egalitate atunci când X și U sunt FINE. planurile respective

sarcini. În cazul în care 1 (2a), problema nu este planurile de permise și există planuri de două permise (1) problema, forma liniară a 2-a problemei (1) primește o mulțime de abs mare. cel mai mare negativ (pozitiv) valoare. Dacă există planuri de primul dopustvmye (2a) sarcină ia în mod arbitrar în absolut. valoarea valoare pozitivă (negativă), 2 (1), problema nu este planuri acceptabile.

A doua teoremă. În cazul în care X - FINE. Planul de prima problemă U - FINE. Planul de două sarcini, componentele acestor planuri sunt legate de

Invers, dacă relația (1) și (2) sunt îndeplinite pentru perechea de programe de sprijin X, U, atunci planurile optime. Relațiile (1) și (2) să servească drept criteriu de optimalitate a planului actual în cele mai multe soluții de metode de programare liniară. Fie X - programul de sprijin al prima sarcină. Substituind componentele sale în formulele (1) și (2) se calculează vectorul U. Dacă U - planul de sarcină 2, de mai sus rezultă optimalitate pereche X, V.

Variabile 2 minute (1 minut) poate fi considerată o problemă multiplicatorii Lagrange timp de 1 minut (2 minute) sarcina.

Să - funktsvya Lagrange:

Apoi, X și U sunt, respectiv, planurile FINE. planuri de 1 și 2 problemă dacă și numai dacă (X, U este un punct de șa Fct cu constrângeri în cazul în care una dintre sarcinile unei perechi dublă reprezentate în formă generală, perechea de probleme duale scrise ca:

Toate proprietățile de mai sus ale provocărilor 1 si 2 rămân pentru a 3-a și a 4-a obiectivelor. Ecuațiile (1) și (2) pentru sarcina rescrise

dualitate teorema stau la baza construcției și studiul metodelor numerice de bază ale constructe de programare liniară. Acestea sunt în mare parte extinse la cazul programării convexe și cazul infinit-dimensionale. D. T. În programarea liniară este strâns legată de teoria jocului. Luarea în considerare a unei perechi de probleme duale de programare liniară este valabil mai ales pentru economie, cercetare. În special, în cazul în care prima sarcină este sarcina de a maximiza producerea unui produs omogen și restricții privind # resurselor, FINE. Planul de două sarcini evaluează valoarea unităților de resurse. Aceste estimări sunt importante în teoria de stabilire a prețurilor.

Lit. cm. art. programare liniară.

3. N. Shore, V. A. Trubin.