Reguli pentru compilarea problemelor de programare liniară duală. Conceptul problemei duale a programării liniare Parametrii de control nenuli ai soluției optime a dualului

Structura și proprietățile problemei duale

Din punct de vedere economic, orice problemă de maximizare a LP poate fi considerată ca o problemă a repartizării resurselor limitate b 1 ,b 2 ,…,b m între diferiți consumatori, de exemplu, între unele procese tehnologice, care sunt reprezentate prin coloane. A 1 ,A 2 ,…A n din matricea de constrângeri a problemei . Orice soluție fezabilă la problema LPx 1 ,x 2 ,…x n oferă o distribuție specifică indicând ponderea fiecărei resurse care ar trebui utilizate în implementarea procesului tehnologic corespunzător.

Luați în considerare un exemplu. Fabrica produce trei tipuri de produse x 1 , x 2 și x 3 , fiecare dintre ele necesită timp pentru prelucrare la mașini de strunjire, frezat și găurit. Cantitatea de timp pentru mașină pentru fiecare dintre mașini este limitată. Fie c 1 ,c 2 ,c 3 profitul din vânzarea unei unități de tipul de produs corespunzător. Este necesar să se determine cât de mult din fiecare tip de produs trebuie produs în timpul săptămânii pentru a maximiza profitul.

În mod formal, această sarcină este scrisă după cum urmează:

maximizează (c 1 x 1 +c 2 x 2 +c 3 x 3) (1)

sub restricții

a 11 x 1 + a 12 x 2 + a 13 x 3 ≤ b 1 ;

a 21 x 1 + a 22 x 2 + a 23 x 3 ≤ b 2 ;

a 31 x 1 +a 32 x 2 +a 33 x 3 ≤b 3 , (2)

unde a 1 j ,a 2 j ,a 3 j este timpul necesar procesării unei unități de al-lea tip de produs, respectiv, pe mașini de strung, frezat și găurit (j= 1, 2, 3); b 1 ,b 2 ,b 3 - resursa saptamanala de timp utilaj, respectiv, pentru masini de strunjire, frezat si gaurit.

Să desemnăm y 1 ,y 2 și y 3 - prețul unității de timp de lucru la mașinile de strunjire, frezat și găurit. Atunci a 11 y 1 + a 21 y 2 + a 31 y 3 - poate fi interpretat ca costul de fabricație a unei unități din primul tip de produs; a 12 y 1 + a 22 y 2 + a 32 y 3 - costul de fabricare a unei unități de produs de tip al doilea etc. d.

Să presupunem că prețurile resurselor y 1 ,y 2 ,…,y m sunt alese astfel încât să fie valabile următoarele relații:

a 11 y 1 + a 21 y 2 + a 31 y 3 ≥ c 1 ;

a 12 y 1 + a 22 y 2 + a 32 y 3 ≥ c 2 ;

a 13 y 1 +a 23 y 2 +a 33 y 3 ≥ c 3 . (3)

Deoarece b 1 ,b 2 și b 3 sunt resursa folosită a timpului mașinii pentru fiecare dintre mașini, atunci b 1 y 1 +b 2 y 2 +b 3 y 3 sunt costurile totale de producție.

Este necesar să se găsească astfel de y 1 ,y 2 și y 3 care să îndeplinească condițiile (3) în care costurile totale de producție sunt minimizate:

minimizați g(y 1 ,y 2 ,y 3)=b 1 y 1 +b 2 y 2 +b 3 y 3 (4)

in conditii

y 1 ≥0; y 2 ​​​​≥0; y 3 ≥0.

O astfel de sarcină se numește sarcină dublăîn raport cu problema (1), numită linie dreaptă.

Acum notăm problemele directe și duale în cazul general.

Problemă directă:

maximiza

in conditii

(7)

Problemă dublă:

minimiza

in conditii

(10)

Sub formă de matrice, o pereche de probleme duale se scrie după cum urmează:

maximiza

in conditii

minimiza

in conditii

A T y≥c; (cincisprezece)

Comparând formele de scriere a problemelor directe și duale, putem stabili următoarele relații între ele:

dacă problema directă este o problemă de maximizare, atunci problema duală va fi o problemă de minimizare și invers;

coeficienţii funcţiei obiective ai problemei directe c 1 ,c 2 ,…,c n deveniți membri liberi ai constrângerilor problemei duale;

termeni liberi ai constrângerii problemelor directe b 1 ,b 2 ,…,b m devin coeficienți ai funcției obiective a problemei duale;

matricea de constrângeri a problemei duale se obţine prin transpunerea matricei de constrângeri a problemei directe;

semnele inegalităților în constrângeri sunt inversate;

numărul de constrângeri din problema primară este egal cu numărul de variabile din problema duală, iar numărul de constrângeri din problema duală este egal cu numărul de variabile din problema primară.

Variabilele y 1 ,y 2 ,…,ym ale problemei duale sunt uneori numite prețuri umbră.

Este mai profitabil să rezolvi problema duală decât linia dreaptă inițială, dacă este în linie dreaptă

problemă cu un număr mic de variabile, există un numar mare de restricţii (m n).

Legătura dintre soluțiile optime ale problemelor directe și duale se stabilește prin intermediul următoarelor teoreme de dualitate.

TEOREMA 1.În cazul în care un - soluții admisibile ale problemelor directe și duale, adică atunci

acestea. valorile funcției obiective a problemei directe nu depășesc niciodată valoarea funcției obiective a problemei duale.

TEOREMA 2 (teorema principală a dualității).În cazul în care un -soluţii admisibile la problemele directe şi duale, iar dacă , apoi sunt soluții optime ale unei perechi de probleme duale.

TEOREMA 3.Dacă în soluţia optimă a problemei directe(5) – (7) i-a constrângere este satisfăcută ca o inegalitate strictă, atunci valoarea optimă a variabilei duale corespunzătoare este egală cu zero, i.e.

Unde - ial treilea rând al matricei A.

Semnificația teoremei 3 este următoarea. Dacă există o abundență a unei resurse și constrângerea i-a pentru soluția optimă este satisfăcută ca o inegalitate strictă, atunci aceasta devine nesemnificativă, iar prețul optim al resursei corespunzătoare este egal cu 0.

Teorema 3 este completată de Teorema 4, care stabilește relația dintre soluția optimă a problemei directe și constrângerile problemei duale.

TEOREMA 4. Dacă în soluţia optimă a problemei duale constrângereajeste satisfăcută ca o inegalitate strictă, atunci valoarea optimă a variabilei corespunzătoare problemei directe trebuie să fie egală cu zero, adică dacă apoi

Să oferim o interpretare economică a teoremei 4.

Din moment ce cantitatile sunt prețurile resurselor corespunzătoare, atunci

este costul procesului tehnologic al j-lea, valoarea este profitul din vânzări pe unitate de produs. Prin urmare, din punct de vedere economic, Teorema 2.7 înseamnă următoarele: dacă al j-lea proces tehnologic se dovedește a fi strict neprofitabil din punct de vedere al prețurilor optime ale resurselor, atunci în soluția optimă a problemei directe, intensitatea acestei procesul tehnologic ar trebui să fie egal cu 0.

Astfel, teorema 4 exprimă principiul rentabilității producție organizată optim.

De asemenea, rezultă din aceasta că

(20)

Să presupunem că printre variabilele x 1 ,x 2 ,…,x n ale problemei directe există un set de mvariabile care au o valoare diferită de zero în soluția optimă. Să fie, de exemplu, primele variabile în ordine să se dovedească astfel.

Apoi, pe baza ecuației (22), se obțin m condiții de rentabilitate:

(21)

Să prezentăm două teoreme mai importante ale teoriei dualității.

TEOREMA 5 (teorema existenței).Problemele primare și duale au soluții optime dacă și numai dacă ambele au soluții fezabile.

TEOREMA 6 (teorema dualității).Vector validX 0 este optim dacă și numai dacă problema duală are o astfel de soluție fezabilăy 0 , ce

Între soluțiile optime ale problemelor directe și duale, elementele rândurilor index ale tabelelor simplex corespunzătoare acestor soluții, există următoarea relație:

i=1, 2, …,m;j=1, 2, …,n,

unde n este numărul de variabile ale problemei directe, m este numărul constrângerilor sale; sunt elementele corespunzătoare ale rândului index al problemelor directe și, respectiv, duale. Mai mult, dacă n+i, unde 1 ≤i≤m este mai mare decât numărul de vectori coloană ai matricei de constrângeri a formei extinse a problemei corespunzătoare, atunci elementele se găsesc prin permutarea ciclică a elementelor rândului index, începând cu elementul

Caz general de dualitate

În secțiunea anterioară, relațiile principale au fost stabilite pentru o pereche de probleme LP duale sub constrângeri sub formă de inegalități. Să generalizăm acum aceste rezultate în cazul constrângerilor arbitrare.

Fie ca problema directă LP să fie dată sub forma:

maximiza

in conditii

Atunci problema duală în ceea ce privește (24)-(26) (sau conjugatul său) este de a minimiza forma liniară:

minimiza

in conditii

Astfel, o problemă asociată cu o problemă cu condiții mixte este compusă după următoarele reguli:

Dacă variabila x j a problemei directe se presupune a fi nenegativă, atunci a j a condiție a sistemului de constrângeri (28) este o inegalitate.

Dacă nu se impune o astfel de constrângere pe x j, atunci a j-a constrângere a problemei duale este o egalitate.

Semnele variabilelor problemei duale y i și constrângerile corespunzătoare ale problemei primare sunt legate într-un mod similar. Rețineți că dacă punem m 1 =min și n 1 =n, atunci obținem caz special perechi de probleme duale cu constrângeri sub formă de inegalităţi.

Programare liniară. Enunțarea problemelor de programare liniară

Programarea liniară se ocupă cu studiul soluțiilor la probleme extreme, care se caracterizează printr-o relație liniară între o variabilă și un criteriu liniar. O condiție necesară pentru astfel de sarcini este prezența restricțiilor asupra resurselor, amploarea cererii, capacitatea de producție și multe altele.

Modelul matematic al ZLP:

1.Maximul sau minim al funcției obiectiv (criteriul optimității).

2. Sistem de restricții în formă ecuatii lineareși inegalități.

3. Non-negativitatea variabilelor.

Este admisibilă o soluție care satisface sistemul de constrângeri și cerințele de nenegativitate a soluțiilor, iar soluțiile care satisfac concomitent condițiile min/max sunt optimizate.

Vedere generală a ZLP

Max(min)F(x)=c1x1+c2x2+…cnxn

A11x1+a12x2+…a1nxn<=b1

A21x1+a22x2+…a2nxn<=b2

Am1x1+am2x2+…amnxn<=bnm, x1,x2,…xn>=0

Proprietăți ZLP:

1. Mulțimea admisibilă de soluții LLP este fie goală, fie este un poliedru convex.

2. Dacă mulțimea admisibilă nu este goală, iar funcția obiectiv este mărginită de sus pentru maximizare și de jos - pentru minimizare, atunci are o soluție optimă.

3. Rezolvarea optimă a problemelor de programare liniară (dacă există), atunci ele sunt la graniță, adică. dacă există o soluție optimă, atunci acesta este unul dintre vârfurile poliedrului soluțiilor fezabile; dacă 2 sau mai multe vârfuri sunt soluții fezabile, atunci orice combinație a acestora este soluția optimă.

Metodă grafică de rezolvare a LLP

Dacă numărul de necunoscute este 2, atunci poate fi rezolvat grafic. Găsiți o soluție X=(x1,x2)? Satisfacerea conditiei max(min)z=c1x1+c2x2. Când sumele j sunt limitate de la 1 la n (aij*xj)<=bj, x1, x2 >=0.

Fiecare dintre inegalitățile 2 definește un semiplan pe planul de coordonate, iar sistemul de inegalități 2 și 3, dacă este compatibil, definește intersecția planurilor. Aceasta va fi o mulțime convexă, care poate fi reprezentată ca:

1. Poligon convex.

2. Arie poligonală convexă nelimitată.

3.Tăiați.

5. Un punct.

6. Set gol.

Interpretarea geometrică a funcției obiectiv:

Z=C 1 X 1 +C 2 X 2 (1)

Pentru valori fixe, Z=Z 0 definește linia z0=c1x1+c2x.

Când schimbăm Z, obținem o familie de drepte paralele, numite linii de nivel.

Vectorul С=(С 1 , С 2) cu coordonatele la x1 și x2 este perpendicular pe fiecare dintre liniile de nivel.

Vectorul C arată direcțiile de cea mai mare creștere (scădere) a funcției obiectiv.

Dacă construim într-o singură figură aria soluțiilor fezabile vectorul C și una dintre liniile de nivel, de exemplu Z=0, atunci problema se reduce la determinarea aria soluțiilor fezabile a punctului de direcție al vectorului C prin care trece linia de nivel Z max (min), corespunzătoare valorii mai mari (mai mici) a funcției Z. Dacă problema este rezolvabilă, pot apărea următoarele cazuri:

1. Problema are o soluție unică.

2. Sarcina are un număr infinit de soluții (optim alternativ).

3. Funcția obiectiv nu este limitată, zona soluțiilor fezabile este un singur punct (Fig. 1).

Metoda simplex

Construirea unei linii de bază inițiale

Să luăm în considerare 3 cazuri.

1) Fie sistemul de constrângeri să aibă forma

X i + ij X j =b i , b i =>0,(i=1,m)

X 0 \u003d (0,0, ..., 0, b i)

O constrângere a unei probleme de programare liniară canonică are o formă preferată dacă, pentru partea sa nenegativă, partea stângă conține o variabilă care intră cu un coeficient egal cu 1, iar restul cu un coeficient egal cu 0. Dacă fiecare constrângere a unui problema de programare liniară canonică are o formă preferată, adică sistemul de constrângeri este redus la o singură bază nenegativă, apoi planul de referință inițial se construiește astfel: Variabilele preferate sunt alese ca fiind de bază, iar toate celelalte variabile sunt libere.

IjXj<=b i , b i >=0

Se introduce o variabilă suplimentară cu un coeficient egal cu 0

Ij X j +X n+1 =b i , b i >=0

X 0 =(0,…,0,b 1 ,...,b m)

Ij X j >=b i , b i >=0

Ij X j -X n+i =b i

Max(min)Z= j X j -(+)M i

Tabele simplex

Un semn al optimității planului de bază. Problema de maximizare

Dacă pentru un plan de referință toate estimările dj sunt nenegative, atunci un astfel de plan este optim. Dacă problema minimă inițială și dj-ul nu sunt pozitive, atunci un astfel de plan este optim.

Luați în considerare trecerea la un plan de referință care nu este mai rău folosind exemplul problemei LP pentru max.

Dacă în linia de index dj< 0, то план не оптимален и его можно улучшить. Среди отрицательных оценок находят максимальную по абсолютной величине.

Dacă sarcina este la minimum, atunci coloana de rezolvare Max|dj|=|dj 0 |

Variabila Xj 0 trebuie introdusă în bază. Pentru a determina variabila derivată din bază, găsiți relația: B i /A ij , A ij >0

Min = B i 0 /A i 0 j 0

La intersecția rândului de rezolvare și a coloanei de rezolvare, există un element redimensionabil.

1. Elementele rândului I 0 al noului tabel sunt egale cu elementele corespunzătoare ale liniei permisive din tabelul anterior împărțite la elementul permisiv.

2. Toate elementele coloanei J 0 sunt egale cu 0, cu excepția elementului de activare.

3. Toate celelalte elemente ale noului tabel se calculează conform regulii: produsul diagonalei principale minus produsul diagonalei secundare împărțit la elementul de rezolvare.

Trei semne:

1. Optim alternativ (un semn al infinitului setului de planuri optime). Dacă rândul index al ultimului tabel simplex (conținând proiectul optim) conține cel puțin o estimare zero corespunzătoare variabilei libere, atunci problema LP are un set infinit de modele optime.

2. Semn de nelimitare a funcției obiectiv. Dacă nu există un singur element pozitiv în coloana de rezolvare, atunci funcția obiectivă pe setul de planuri admisibile nu este limitată.

3. Un semn de incompatibilitate a sistemului de restricții. Dacă în planul optim al problemei M nu toate variabilele artificiale sunt egale cu 0, atunci sistemul de constrângeri al problemei inițiale este inconsecvent.

Probleme de programare liniară duală

Fiecare problemă de programare liniară este strâns legată de o altă problemă liniară, numită problemă duală. Sarcina inițială este directă sau inițială. O pereche de probleme LP duale simetrice are următoarea formă:

Drept - maxZ = Xj>=0

Dual minZ = Xj>=0

O pereche de sarcini duale pot fi interpretate economic:

Linie directă - Cât de mult și ce fel de produse Xj ar trebui produse, astfel încât la costuri unitare date Cj, volumul resurselor Bi și ratele de consum Aij maximizează producția în termeni valorici.

Dual - Care ar trebui să fie estimarea unității fiecărei resurse pentru a minimiza estimarea costului total pentru toate resursele pentru Bi Cj Aij dat.

Reguli de construcție:

1. Înregistrarea sarcinii inițiale este ordonată, i.e. dacă funcția obiectivă a problemei este maximizată, atunci constrângerile de inegalitate trebuie să fie > sau = (pentru a minimiza< или =) Достигается умножением ограничений на -1.

2. Dacă problema directă este rezolvată la maximum, atunci problema duală este rezolvată la minimum.

3. Fiecare constrângere a problemei directe corespunde unei variabile a problemei duale și invers.

4. Matricea sistemului de constrângeri a problemei duale se obține din matricea sistemului de constrângeri a problemei directe prin transpunere.

5. Termenii liberi ai sistemului de constrângeri ai problemei directe sunt coeficienții variabilelor corespunzătoare funcției obiective a problemei directe și invers.

6. Dacă se impune condiția de non-negativitate transferului problemei directe, atunci constrângerea corespunzătoare problemei duale se scrie ca o constrângere de inegalitate, dacă nu - ca o constrângere de egalitate.

7. Dacă orice restricție a problemei directe este scrisă ca egalitate, atunci condiția de non-negativitate nu este impusă variabilei corespunzătoare problemei duale.

Sarcina de transport

Să reprezentăm problema transportului după criteriul costului sub forma unui tabel

În tabel sunt prezentate furnizorii A1… care au în stoc, respectiv, 1… unități de marfă omogenă. Această marfă trebuie livrată la n consumatori, în cantități de 1 ... unități, costul este dat cu ij transport de marfă de la i furnizor j la consumator. Se impune planificarea transportului (indicați câte unități de marfă trebuie trimise de la I al acelui furnizor j către consumator, astfel încât să satisfacă cât mai mult posibil cererea consumatorului și astfel încât costul total al transportului să fie minim).

c 1 - preț.

Sarcinile, în care stocurile totale de bunuri ale furnizorilor sunt egale cu cerințele totale, se numesc închise.

I != I – atunci problema este deschisă.

La rezolvarea problemelor de transport, teorema rangului matricei este importantă:

Rangul matricei problemei de transport este cu 1 mai mic decât numărul de ecuații (r=m+n-1).

Acesta este câte celule ar trebui să fie ocupate de X în problema transportului. Rezolvarea problemei transportului se realizează folosind metoda generală de îmbunătățire secvențială a planului, care include următorii pași:

1. Determinarea planului de referință inițial.

2. Evaluează acest plan.

3. Trecerea la următorul plan prin înlocuirea uneia dintre variabilele de bază cu una liberă.

Există diferite modalități de implementare a etapelor de rezolvare a problemei transportului:

Regula colțului de nord-vest

Regula elementului minim

Metoda Vogel4

Metoda potențială

Metoda potențială

Să trecem la construirea unui plan optim de transport. Conform acestui plan de bază, care are numărul de celule ocupate m + n-1. Fiecărui furnizor și fiecărui consumator i se dă un număr numit potențial. Potențialele sunt alese astfel încât suma lor pentru fiecare celulă încărcată cu marfă să fie egală cu tariful pentru transportul unei unități de marfă. Deci, dacă celula (I,k) este de bază (ocupată), atunci u i +v k =C ik unde y este potențialul total al furnizorului total.

Apoi calculăm estimările celulelor libere după formula: S ij =C ij -(U i +V j)

Dacă pentru celulele libere toate estimările S ij sunt mai mari sau egale cu 0, atunci planul de transport rezultat este optim. Dacă există cel puţin o estimare S ij< 0 число базисных вводят в клетку, для которой оценка S ij минимальной. Для такой клетки строится цикл и производится перемещение груза так, чтобы баланс цикла сохранялся.

U 3 =
Într-o celulă plină, tariful este egal cu suma potențialelor

F=320+150+140+150+1020+120=1900

Metoda în care una dintre problemele reciproc duale este mai întâi rezolvată prin metoda simplex, iar apoi optimul și soluția optimă a celeilalte probleme sunt găsite folosind teoreme de dualitate, se numește metoda dual simplex.

Teorema 1 (Prima teoremă a dualității). Dacă una dintre problemele reciproc duale are o soluție optimă, atunci la fel

altul, iar valorile optime ale funcțiilor lor obiective sunt egale cu:

Dacă funcția obiectivă a problemei inițiale nu este mărginită, atunci sistemul de constrângeri al problemei duale este inconsecvent.

Notă: afirmația inversă față de a doua parte a primei teoreme a dualității nu este adevărată în cazul general.

Teorema 2. Componentele planului optim pentru problema duală ( având condiţia de non-negativitate) sunt egale valori absolute ale coeficienților

Componentele planului optim pentru problema duală ( nelimitat în semn) sunt egale valorile coeficientului cu variabilele corespunzătoare ale funcției obiective a problemei inițiale exprimate în termenii variabilelor libere ale soluției sale optime.

Teorema 3. Componente pozitive (diferite de zero) ale soluției optime pentru una dintre probleme pereche dublă simetrică corespund componentelor zero ale soluției optime a unei alte probleme, adică pentru orice și:

Teorema 4 (A treia teoremă a dualității). Componentele planului optim al problemei duale sunt egale cu valorile derivatelor parțiale ale funcției liniare conform argumentelor corespondente, i.e.

. (7.2)

Interpretarea economică a celei de-a treia teoreme a dualității: componentele planului optim al problemei duale arată prin câte unităţi monetare profitul (venitul) maxim din vânzarea produselor se va modifica atunci când stocul resursei corespunzătoare se va modifica cu o unitate.

Exemplul 9.1. Pe baza soluției din Exemplul 5.2 (fișierul „Algoritm și exemple ale metodei simplex”), determinăm soluția optimă a problemei duale prin metoda dual simplex.

Această pereche dublă este simetrică. Problemele sunt scrise în formă standard, le vom aduce la forma canonică:

Să stabilim o corespondență între variabilele problemelor reciproc duale.

Pe baza soluției din Exemplul 5.2. tabelul simplex al ultimei iterații (Tabelul 5.10) arată astfel:

Tabelul 9.3

În conformitate cu teorema 2, valorile optime ale variabilelor și vor fi egale cu valorile absolute ale coeficienților pentru variabilele corespunzătoare ale funcției obiective a problemei inițiale, exprimate în termenii variabilelor libere ale optimului acesteia. soluţie.

Conform tabelului 9.3, scriem funcția obiectiv a problemei inițiale, exprimată în termenii variabilelor libere ale soluției sale optime:

Prin urmare, ,.

Variabilele , , și nu sunt prezente în funcția obiectiv (adică, coeficienții lor sunt egali cu zero), prin urmare, valorile optime ale variabilelor corespunzătoare , , și sunt egale cu zero.

Conform teoremei 1, .

Astfel, valoarea optimă a funcției obiectiv , care se realizează la .

Exemplul 9.2. Pe baza soluției problemei inițiale, găsiți soluția optimă a problemei duale folosind metoda dual simplex.

Această pereche dublă este asimetrică. Să reducem problema duală la forma canonică.

Pentru a stabili corespondența dintre variabilele perechii duale, introducem două variabile fictive lipsă în problema inițială.

Să stabilim o corespondență între variabilele problemelor reciproc duale.

Tabelul 9.4

Corespondența variabilelor perechii duale

Să rezolvăm problema inițială prin metoda simplex.

Folosind metoda Jordan-Gauss, selectăm în sistemul de constrângeri ale problemei inițiale ca variabile de bază și ( Notă: nu utilizați variabile fictive ca variabile de bază).

În urma transformărilor, obținem următoarea matrice de coeficienți:

.

Sistemul de constrângeri al problemei inițiale va lua următoarea formă:

Să exprimăm variabilele de bază în termenii celor libere; ca urmare, problema inițială va lua următoarea formă:

Înlocuind valorile obținute ale variabilelor de bază în funcția obiectiv, aceasta va lua următoarea formă:

Ca rezultat al rezolvării problemei originale transformate prin metoda simplex la ultima iterație, obținem următorul tabel simplex:

Tabelul 9.5

Tabel simplex al soluției optime a problemei inițiale

Sunt prezentate reguli pentru alcătuirea problemelor duale. Sunt considerate perechi simetrice, asimetrice și mixte. Sunt analizate exemple de compunere de probleme duale.

Problemele duale sau conjugate de programare liniara au proprietatea ca din rezolvarea uneia dintre probleme se poate obtine rezolvarea altei probleme. Aici luăm în considerare regulile pentru alcătuirea problemelor duale.

Problemă dublă simetrică

Luați în considerare o problemă de programare liniară cu variabile nenegative și inegalități ale sistemului de constrângeri de următoarea formă:
(1.1) ;
(1.2)
Aici , , sunt câteva numere. Toate rândurile sistemului (1.2) sunt inegalități cu semne .

(2.1) ;
(2.2)
Aici toate rândurile sistemului (2.2) sunt inegalități cu semne . Matricea coeficienților sistemului de constrângeri (2.2) este matricea transpusă a sistemului (1.2). Conține rânduri și coloane. Problema duală are variabile. Toate variabilele sunt nenegative.

Problema inițială (1) este adesea numită problemă directă, în timp ce problema (2) este numită problemă duală. Dacă luăm problema (2) ca problemă inițială, atunci problema (2) va fi o problemă directă, iar problema (1) va fi una duală. Sarcini (1) și (2) se numesc probleme duale simetrice.

Astfel, o problemă duală simetrică poate fi compusă numai dacă toate variabilele problemei inițiale sunt nenegative și sistemul de constrângeri nu conține egalități. Dacă se caută maximul funcției obiectiv, atunci inegalitățile trebuie convertite la forma . Dacă se caută un minim, atunci inegalitățile trebuie convertite la forma . Pentru a schimba semnul, trebuie să înmulțiți ambele părți ale inegalității cu -1 .

Un exemplu de compunere a unei probleme duale simetrice

;

Problema inițială este problema găsirii minimului. Prin urmare, toate inegalitățile trebuie să aibă semne. Prima și a treia inegalități conțin semnul . Să le înmulțim cu -1 :

Să transpunem această matrice. Adică scriem primul rând ca prima coloană, scriem al doilea rând ca a doua coloană, scriem al treilea rând ca a treia coloană.

Problema dublă arată astfel:
;

;

Problemă dublă asimetrică

Provocarea la maximum

Să luăm în considerare problema de programare liniară maximă canonică cu variabile nenegative și egalități ale sistemului de constrângeri:
(3.1) ;
(3.2)
Aici , , sunt câteva numere. Toate rândurile sistemului (3.2) sunt egalități. Toate variabilele sunt nenegative.

Problema dublă arată astfel:
(4.1) ;
(4.2)
Aici toate rândurile sistemului (4.2) sunt inegalități cu semne . Matricea coeficienților sistemului de constrângeri (4.2) este matricea transpusă a sistemului (3.2). Problema duală are variabile. Variabilele pot fi atât pozitive, cât și negative.

Diferența dintre perechea asimetrică de probleme (3) și (4) și perechea simetrică (1) și (2) este că sistemul de constrângeri (3.2) conține doar egalități, în timp ce sistemul (4.2) nu conține condiții pentru variabilele să fie nenegative.

Provocarea minimă

Acum luați în considerare problema de programare liniară minimă canonică:
(5.1) ;
(5.2)

Problema dublă arată astfel:
(6.1) ;
(6.2)

Sistemul de constrângeri (6.2) diferă de (4.2) prin faptul că inegalitățile au semnele .

Conexiune cu o pereche simetrică de probleme duale

Să arătăm că o pereche asimetrică de probleme (3)-(4) poate fi obținută dintr-o pereche simetrică (1)-(2).

Deci, să presupunem că avem o problemă directă cu o funcție obiectiv
(3.1)
și un sistem de restricții
(3.2)
Fiecare egalitate poate fi reprezentată prin două inegalități:

Înmulțim inegalitățile cu semne cu -1 :

Sistemul de constrângeri are inegalități.

Conform formulelor (1)-(2), obținem o problemă duală:
;


problema duală are variabile nenegative:
.
Este ușor de observat că aceste variabile intră în problemă sub formă de diferențe
.

Să facem înlocuiri
.
Deoarece și , variabilele pot fi atât pozitive, cât și negative.

Și obținem problema dublă (4):
(4.1) ;
(4.2)

Dacă luăm (4) ca problemă inițială, atunci, efectuând toate acțiunile în ordine inversă, obținem problema duală (3).

În același mod, se poate obține problema duală (6) din problema (5) și problema duală (5) din problema (6).

problema mixta

Acum luați în considerare o problemă mixtă.

Să avem o problemă directă (1) pentru maxim, în sistemul de constrângeri al cărui rând --lea este o egalitate. Atunci problema duală are forma (2) cu o singură excepție - variabila poate fi fie pozitivă, fie negativă. Adică nu există nicio restricție.

Același lucru se va întâmpla dacă avem o problemă directă (2) pentru un minim, în sistemul de constrângeri al cărui rând --lea este o egalitate. Problema duală are forma (1) cu o singură excepție - variabila poate fi de orice semn.

Acum să presupunem că avem o problemă directă de maxim (1), dar nu există nicio constrângere. Adică, variabila poate fi fie pozitivă, fie negativă. Atunci problema duală are forma (2) cu o excepție - al-lea rând al sistemului de constrângeri este o egalitate.

Și în sfârșit, să avem o problemă directă (2) pentru un minim, dar nu există nicio constrângere . Atunci problema duală are forma (1) cu o excepție - al-lea rând al sistemului de constrângeri este o egalitate.

Toate acestea ne permit să formulăm reguli pentru alcătuirea problemelor duale.

Reguli pentru compilarea problemelor duale

1. Pentru problema maximă inițială, reducem toate inegalitățile sistemului de constrângeri la forma:
.
Pentru problema minimă inițială, reducem toate inegalitățile la forma:
.
Dacă este necesară schimbarea semnului, atunci înmulțim ambele părți ale inegalităților cu -1 .
2. Compunem o problemă duală în același mod ca și pentru o pereche de probleme simetrice.
3. Dacă în problema inițială, rândul --lea al sistemului de constrângeri este o egalitate, atunci ștergem condiția de non-negativitate a --lea variabilă a problemei duale.
4. Dacă în problema inițială, nu există o condiție de non-negativitate pentru variabila -a, , atunci în linia -a a problemei duale schimbăm semnul inegalității în semnul egal.

Un exemplu de compunere a unei probleme mixte duale

Având în vedere o problemă de programare liniară:
;

Scrie o problemă dublă.

Funcția obiectiv are un termen liber 5. Pentru a-l aduce la forma (2.1), introducem o variabilă și adăugăm egalitatea . Apoi sarcina va lua forma:

;

Această problemă este problema găsirii minimului. Prin urmare, toate inegalitățile trebuie să aibă semne. A treia inegalitate conține semnul . Deci hai să o înmulțim cu -1 :

Să rescriem sistemul de constrângeri, specificând în mod explicit coeficienții variabilelor:

Matricea de coeficienți ai sistemului de constrângeri are forma:

Să transpunem această matrice. Adică scriem primul rând ca prima coloană, scriem al doilea rând ca a doua coloană și așa mai departe.

Să compunem problema duală ca pentru o pereche simetrică.
;

Deoarece în problema inițială liniile 1, 2 și 4 ale sistemului de constrângeri sunt egalități, în problema duală variabilele , și pot avea orice semn. Singura variabilă nenegativă este . Prin urmare, condițiile pentru non-negativitatea variabilelor au forma:
.

Deoarece variabilele și pot avea semne arbitrare în problema inițială, rândurile 3 și 4 ale sistemului de constrângeri ale problemei duale sunt egalități.

Astfel, problema dublă arată astfel:
;

din a patra ecuație. Înlocuiți variabila cu valoarea ei și înmulțiți al treilea rând cu -1 .

Metoda simplex este universală. Poate fi folosit pentru a rezolva orice problemă de programare liniară. Cu toate acestea, datorită versatilității sale, nu este lipsit de unele deficiențe. În unele cazuri, așa-numita metodă duală este mai potrivită pentru rezolvarea problemelor de programare liniară. Această metodă se bazează pe teoria dualității, una dintre cele mai importante componente ale teoriei generale a programării liniare.

Teoria dualității este folosită pentru a dezvolta metode de rezolvare a multor clase importante practic de probleme de optimizare liniară: probleme de tip transport, probleme cu numere întregi liniare etc. Luați în considerare principalele prevederi ale acestei teorii.

Fiecare problemă de programare liniară îi corespunde unei alte probleme, într-un anumit sens opus acesteia. Dacă prima sarcină se numește directă, atunci opusul se numește dual. Deoarece dualul în raport cu problema duală este problema directă inițială, nu contează care dintre probleme se numește directă și care este duală. Prin urmare, problemele primare și duale sunt numite probleme duale perechi.

Problema duală este formulată direct din linie dreaptă folosind anumite reguli. Deoarece problemele directe pot avea restricții sub formă de inegalități de tip, tip sau sub formă de egalități, atunci regulile de obținere a problemelor duale pentru ele se dovedesc a fi diferite.

Există probleme duale simetrice, asimetrice și mixte. În problemele simetrice, constrângerile problemei directe au forma . În constrângerile problemei asimetrice, constrângerile problemei directe folosesc semne egale. În problemele mixte, se folosesc ambele tipuri de relații „mai puțin sau egal cu” și „Egal cu”. În problemele asimetrice și mixte, variabilele nou introduse nu sunt supuse cerinței ca acestea să fie nenegative.

Calculele bazate pe relații de dualitate încep prin reducerea problemelor primare și duale la forma standard. Prin urmare, ne putem limita la formularea regulilor pentru formarea unei probleme duale în raport cu o problemă de programare liniară standard. Regulile pentru derivarea problemei duale pentru alte tipuri de probleme LP pot fi derivate din aceste reguli.

Scriem problema LP în forma standard:

,

,

i=1,..,m; j=1,...,n.

Să numim această problemă directă. Atunci problema dublă cu privire la aceasta va fi:

,

i=1,..,m; j=1,...,n.

După analiza sarcinilor, putem trage următoarele concluzii:

1. Fiecare constrângere a problemei primare corespunde unei variabile a problemei duale.

2. Fiecare variabilă a problemei directe corespunde restrângerii problemei duale.

3. Coeficienții pentru orice variabilă din constrângerile problemei directe devin coeficienții pentru constrângerea problemei duale corespunzătoare acestei variabile, iar partea dreaptă a constrângerii care se formează este egală cu coeficientul pentru această variabilă în expresia lui funcţia obiectivă.

4. Forma extremumului problemei duale este opusă formei extremumului problemei directe;

5. Vectorii B și C din problemele directe și duale sunt interschimbați;

6. Matrice A a problemei duale se obţine prin transpunerea matricei DAR sarcină directă;

7. Toate constrângerile problemei duale au forma pentru problema de maximizare și forma pentru problema de minimizare a formei liniare.

Pentru cazul unei probleme duale simetrice:

Pentru cazul unei probleme asimetrice:

Problema dublă arată astfel:

Problemele mixte conțin restricții sub formă de egalități și inegalități. Atunci când compilați o problemă duală, este necesar să folosiți regulile de tranziție pentru problemele simetrice și asimetrice.

Exemplele de mai jos servesc la ilustrarea regulilor de obținere a problemelor duale.

Exemplu Este dată o problemă de programare liniară (în stânga fiecărei constrângeri există o variabilă duală asociată acesteia). Această problemă este asimetrică.

,

Să formulăm o problemă dublă pentru această problemă. Funcția obiectiv a problemei duale este o formă liniară obținută ca produs dintre vectorul b=(10,20,60,80) și vectorul variabilelor problemei duale Y =( ). În plus, deoarece funcția obiectiv este maximizată în problema primară, este minimizată în problema duală. Ținând cont de observațiile făcute, obținem

Partea stângă a primei constrângeri a problemei duale este produsul vectorului sistemului de constrângeri al problemei directe, asociat cu variabila , de vectorul variabilelor problemei duale. Partea dreaptă a acestei constrângeri este egală cu coeficientul variabilei , în funcția obiectivă a problemei directe.

Și întrucât, în plus, problema directă este problema găsirii maximului, prima constrângere are forma:

Argumentând în mod similar, obținem a doua constrângere a problemei duale: . Absența unei variabile în această constrângere se datorează faptului că nu există o variabilă în a doua constrângere a problemei directe.

Variabila asociată cu cea de-a treia variabilă a problemei duale apare numai în prima constrângere a problemei primare. Din acest motiv, pentru a treia constrângere, obținem . Argumentând prin analogie, obținem a patra, a cincea și a șasea restricție: .

Astfel, în ciuda faptului că condiția de non-negativitate nu a fost impusă în mod specific variabilelor problemei duale, totuși, pentru toate acestea s-a dovedit a fi satisfăcută.

Exemplu Având în vedere o problemă de programare liniară într-o formă nestandard

,

,

,

Nelimitat în semn .

Scriem această problemă în formă standard. Pentru a face acest lucru, facem o schimbare de variabile , să introducem o variabilă redundantă în a doua constrângere și o variabilă suplimentară în a treia constrângere. obține

,

.

Să formulăm o problemă dublă. Deoarece funcția obiectiv este minimizată în problema directă, funcția obiectiv a problemei duale are forma .

Din același motiv, prima, a doua și a treia constrângere ale problemei duale, asociate, respectiv, cu variabilele sunt scrise astfel:

,

Deoarece variabila apare doar în a doua și variabila doar în a treia ecuație a problemei primare, constrângerile asociate problemei duale sunt:

.

Astfel, dintre cele trei variabile ale problemei duale, una - sa dovedit a fi nemărginită în semn.

Cu ajutorul teoremelor de dualitate, cunoscând soluția uneia dintre probleme, puteți găsi soluția optimă a celeilalte fără a o rezolva.

Luați în considerare o problemă mixtă.

Sarcina dublă pentru aceasta va arăta astfel:

Dacă folosim forma canonică a unei probleme de programare liniară, atunci avem de-a face cu o problemă de programare liniară asimetrică.

Forma canonică a problemei este:

Problema dublă va arăta astfel:

Teorema 1. Pentru orice pereche de soluții fezabile la problemele primare și duale, valoarea funcției obiectiv în problema de maximizare nu depășește valoarea funcției obiectiv în problema de minimizare.

Valoarea practică a acestei teoreme este următoarea. În practică, uneori este mai bine să obțineți o soluție aproape de optim, dar într-un timp scurt, decât cea optimă, dar într-un timp mult mai lung. În acest caz, ultima inegalitate poate servi ca o estimare a proximității soluției obținute la următoarea iterație la optim.

Teorema 2. Dacă una dintre problemele duale are o soluție optimă, atunci cealaltă are și o soluție optimă, iar valorile funcțiilor obiectiv pentru ambele soluții sunt aceleași. Dacă una dintre problemele duale are o funcție obiectivă nelimitată, atunci cealaltă este de nerezolvat, adică nu are soluții fezabile.

Teorema. Pentru ca soluțiile admisibile să fie optime, este necesar și suficient ca acestea să satisfacă sistemul de ecuații

.

Această teoremă înseamnă că una dintre variabilele oricăreia dintre probleme este strict mai mare decât zero, atunci restricția corespunzătoare acesteia în cealaltă problemă duală este satisfăcută ca o egalitate strictă și, invers, dacă, în soluția optimă, orice restricție. este satisfăcută ca o inegalitate strictă, atunci restricția corespunzătoare variabilei în soluția optimă este zero.

Exemplu Să rezolvăm o problemă simetrică. Lasă problema inițială să arate ca

După ce am rezolvat problema printr-o metodă grafică, obținem

Să creăm o problemă dublă pentru ea

Deoarece funcțiile obiectiv în punctul optim sunt egale, atunci

Din moment ce variabilele
, atunci constrângerile corespunzătoare acestora în problema duală conțin un semn egal. Aceste restricții au forma

Înlocuiți valorile constrângerilor . obține

.

În acest sistem, doar prima inegalitate este strictă. Prin urmare, . Alte valori ale variabilelor pot fi găsite din sistemul de ecuații

.

Ca urmare a rezolvării acestui sistem de liniară ecuații algebrice, primim

Rezolvăm aceeași problemă, dar presupunând că soluția este cunoscută

Deoarece a doua și a treia variabilă sunt strict mai mari decât zero, restricția corespunzătoare acestora este satisfăcută ca o egalitate strictă.

.

Rezolvând acest sistem de ecuații, obținem

Dacă problema inițială este rezolvată prin metoda simplex și coeficienții sunt obținuți în funcția obiectiv final - matrice - un rând de coeficienți, atunci soluția problemei duale poate fi găsită prin formula unde este matricea coeficienților pentru variabilele de bază ale funcției obiectiv în soluția optimă a problemei inițiale.

Luați în considerare interpretarea economică a problemei duale.

Teorema. Valorile variabilelor din soluția optimă a problemei duale sunt estimări ale influenței termenilor liberi ai constrângerilor problemei originale asupra valorii optime a funcției sale obiective. La fel de

Apoi variabilele duale arată cum se va schimba funcția obiectiv atunci când resursa se schimbă cu una