Faptele de bază ale teoriei dualității

în cazul în care numărul de variabile din cele două mai multe numărul de constrângeri egalitate, adică, n-m = 2,

în care rangul matricei A = m. Apoi, cele două variabile în acest sistem de ecuații, să zicem x1 și x2. sunt libere, adică, poate fi exprimat prin ele toate celelalte variabile:

... în cazul în care - unele numere. Substituind aceste expresii în funcția obiectiv, obținem

în cazul în care - unele numere.

Luați în considerare problema programării liniare cu două variabile:

Folosind construcții geometrice, vom găsi soluția ei (). Înlocuind aceste numere în (7.9), (7.10), obținem o soluție și valoarea problemei inițiale (7.8).

Exemplul 7.2. Găsiți valoarea maximă a funcției

Decizie. Spre deosebire de problemele discutate mai sus în constrângerile cu probleme originale sunt prezentate sub forma unor ecuații. În acest caz, numărul de necunoscute este egal cu cinci. Prin urmare, această problemă ar trebui să fie redusă la o problemă în care numărul de necunoscute ar fi egal cu doi. În acest caz, acest lucru se poate face prin trecerea de la sarcina inițială înregistrată sub formă de bază, sarcina înregistrată în formularul standard.

Sa arătat mai sus (a se vedea. § 1.2), că sarcina inițială este înregistrată sub formă de miez pentru problema constând în găsirea valorii maxime a funcției

Din funcția obiectiv a originalului variabile problema x3. x4, x5 eliminate prin substituirea acestor valori ale constrângerilor respective ale sistemului de ecuații.

Construim un poligon face problema rezultată (Fig. 7.1.). După cum se poate observa din Fig. 7.1. valoarea maximă a funcției obiectiv a problemei ia în punctul de intersecție al liniilor I și II. De-a lungul fiecare din valoarea limită dreaptă a uneia dintre variabilele excluse în timpul tranziției la inegalitatea corespunzătoare este zero. De aceea, în fiecare dintre vârfurile poligonului obținute soluții finale de cel puțin două variabile ale problemei inițiale devine zero. Astfel, la punctul avem x3 = 0 și x4 = 0. Substituind etiznacheniya în prima și a doua ecuații de constrângeri de sistem ale problemei originale, obținem un sistem de două ecuații

Substituind valorile x1 și x2 în a treia ecuație a constrângerilor problemă originale ale sistemului, determinăm valoarea ravnoe14 x5 variabilă.

Prin urmare, planul optim al problemei este x * = (3, 4, 0, 0, 14). În acest sens, valoarea funcției obiectiv este Fmax = 18.

7.1.3. Dualitatea în programarea liniară

Fiecare problemă LP poate fi asociată cu o altă sarcină PL, numită dublă. Studiul lor comun este subiectul teoriei dualității, care este o secțiune importantă a programării liniare. Mai mult teoria dualității spectaculoasă este, în cazurile în care dubla problema este rezolvată mai ușor decât directă.

Pentru comoditate, vom scrie din nou problema generală LP:

Dual problemă (7.11) este următoarea problemă:

Pentru a construi problema duală este necesar să se utilizeze următoarele reguli:

1) dacă problema directă este rezolvată la maxim, apoi dual - cel puțin, și vice-versa;

2) în constrângerile maximizare - inegalitățile ≤ sens și în problema de minimizare - adică ≥;

3) Orice problemă transmite mărginite sarcini variabile duale corespunzătoare, și invers, fiecare limitare a problemei duale corespunde unei probleme directe variabile;

4) constrângeri ale matricei sistemului obținut din problema duală a constrângerilor sistemului de transpunere matrice problemă inițială;

5) termenii constante constrângerile de sistem sunt coeficienți problemă directe pentru variabilele respective ale funcției obiectiv a problemei duale, și vice-versa;

6) Dacă problema directă variabila impus condiția nu este negativitate (≥), atunci limita corespunzătoare a problemei duale este scris ca o constrângere - inegalitate. dacă nu, cum constrângerile privind egalitatea;

7) în cazul în care restricția i-e a problemei inițiale este inegalitate, atunci variabila i din dual ³0 problema yi. Dacă constrângerea i-lea este o ecuație, yi variabila poate lua valori atât pozitive, cât și negative, adică condiția este să nu negativitate nu este impusă.

În primul rând, masa este stocată toate informațiile cu privire la problema directă: valorile parametrilor ij, bi. și Cj. semne sau inegalități egalitati în constrângerile (dreapta), condițiile de non-negativitate variabilelor relevante (de mai sus). Apoi, fiecare i - lea rând (i-lea limita problema directă) este asociată cu yi variabilă dublă, care se suprapune peste starea de non-negativitate, în cazul în care dreptul în această linie este un semn de inegalitate. În partea de jos a pus jos semne de inegalitate sau de echitate, în funcție de faptul dacă sunt sau nu impuse impus condiția-Vie non-negativitatea a variabilei corespunzătoare a problemei directe. După această sarcină dublă „citi“ prin înmulțirea vectorului y = (yi) pe coloanele matricei A = (Aij) și vectorul b = (bi).

Tabel. 7.1 având în vedere problemele directe și duale, în cele mai importante cazuri speciale.

Forma de înregistrare probleme directe și duale

Forma problemei LP primara

Forma problemei LP dublă corespunzătoare