problemă de programare liniară duală

Întreprinderea produce n produse (P1, P2, ..., Pn) folosind pentru producerea de m tipuri de resurse (S1, S2, ..., Sm). Date cunoscute cu privire la normele de consum de resurse pe unitatea de producție a fiecărei specii și a întreprinderii lor, adică stocurile

- rata de consum de resurse Si pentru a produce o unitate de produse Pj; - furnizarea de resurse Si în întreprindere.

Pj prețul unitar al produselor este.

Este necesar să se facă un plan de producție în care veniturile din vânzarea acesteia ar fi maxim.

Vom nota cu - volumul de producție Pj. planificate pentru producție - cantitățile necunoscute. Apoi, un model matematic al acestei probleme va fi după cum urmează:

Problema rezultată este o problemă de programare liniară scrisă într-o formă standardizată. Pentru comoditatea problemei (8.1) - (8.3) pot fi reprezentate într-o formă compactă:

Ca urmare, modelul matematic al problemei de planificare a producției poate fi formulată după cum urmează: pentru a face planul de producție X = (x1, x2, ..., xn), satisfăcând sistemul de constrângeri (8.4), condiția (8.5), în care funcția obiectiv (8.6) devine cea mai mare valoare.

Să presupunem că o anumită organizație a decis să cumpere din resursele companiei S1, S2, ..., Sm, și este necesar să se stabilească prețul optim pentru aceste resurse y1, y2, ..., ym. în următoarele condiții:

1) costul total al resurselor pentru entitatea contractantă ar trebui să fie minimă;

2) pentru fiecare tip de resurse necesare pentru întreprinderi să plătească nu mai puțin decât suma pe care îl poate primi procesarea acestui tip de resursă în produsul finit.

Pe baza condițiilor de organizare 1-cumpărare este interesat de faptul că costul tuturor resurselor Z în cantități b1, b2, ..., bm la preturi respectiv y1, y2, ..., ym sunt minime, adică,

Pe baza condițiilor de 2 pentru a îndeplini cerințele Vanzatorului costul resurselor consumate în producerea unei unități de producție a fiecărui tip nu ar trebui să fie mai mică decât prețul său, și anume

Conform yi sale variabile natura nu este negativă, adică,
. (8.9)

Astfel, modelul matematic pentru entitatea contractantă va avea următoarea formă:

Să comparăm modelul matematic (8.1) - (8.3) și (8.7) - (8.9):

1) numărul de necunoscute este egal cu numărul de sarcini audio alte limitări;

2) limitări matricea coeficienților de o singură problemă se obține prin transpunerea unei matrice a coeficienților de alte constrângeri ale sarcinii sistemului;

3) Inegalitatea Sistemele de constrângeri au sens opus;

4) disponibilitatea restricțiilor impuse de sistem unul dintre obiectivele necunoscutele sunt coeficienții în funcția obiectiv a unei alte sarcini sau vice-versa;

5) funcții obiectiv în probleme au sensuri opuse.

problemă de programare liniară are cinci semne formale de mai sus-menționate, numit simmetrichnoydvoystvennoy pereche. în care unul dintre ele (original) este luată ca bază. iar celălalt - dublă.

În teoria programării liniare, de asemenea, distinge nesimmetrichnyedvoystvennyepary. De exemplu, în cazul în care sistemul de sarcini constrângeri includ limitate în acțiuni și / sau condițiile nu sunt non-negativitate de variabile.

Reguli pentru structura unei perechi dublă:

1) Semne de inegalități în problema inițială, limitele impuse sistemului sunt în conformitate cu funcția sa de obiectiv, și anume, în cazul în care este redusă la minimum, inegalitatea trebuie să fie de forma «≥», și, dacă este maximizată, «≤». Acest principiu se aplică și la problema dublă.

2) Se determină numărul de parametri necunoscuți ai problemei duale, egal cu numărul de constrângeri ale problemei inițiale.

3) Se determină intervalul de valori permise pentru fiecare dintre variabilele problemei dublă în conformitate cu următoarele reguli:

fiecare i-lea restricție inegalitatea corespunde problemei inițiale i -s problemă variabilă dublă care îndeplinește condiția de bază non-negativitate; și fiecare i-lea constrângerile privind egalitatea ale problemei inițiale corespunde i stea variabila a problemei duale, semn nelimitat.

4) Se determină constrângerile problemă coeficienții duale de matrice ale matricei sistemului prin transpoziția coeficienților limitările problemei inițiale.

5) determină disponibilitatea constrângerilor dubla problemă a sistemului egal cu coeficienții necunoscutele în funcția obiectiv a problemei inițiale.

6) înregistrate de sistemul limitează problema dublă, în cazul în care fiecare tip de limitare este determinată pe baza următoarelor reguli:

fiecare j -lea problemă inițială variabilă care satisface condiția non-negativitate corespunde j -lea inegalitate ogranichenie- dublă problemă (inegalitate aparență este stabilită în conformitate cu principiul formulat în norma 1 și pornind de la faptul că funcția obiectiv a problemei duale are funcțiile de aterizare opuse sensul problemei inițiale (regula 7)); și fiecare j-lea variabilă a problemei inițiale, semn nelimitat corespunde constrângerilor de egalitate j retragerea din problema dublă.

7) determină coeficienții necunoscuți funcției obiectiv a problemei duale, un număr egal de constrângeri de sistem libere ale problemei inițiale corespunzătoare. Apoi a înregistrat funcția obiectiv a problemei duale, și va avea opusul funcției obiectiv a sensului problemei inițiale, și anume, minimizate dacă funcția obiectivă a problemei inițiale este maximizată, și vice-versa.

Exemplul 8.1. Crearea dublă la următoarea problemă de programare liniară:

În conformitate cu regula 1 a sistemului de acționare a unor restricții în conformitate cu o funcție de țintă (înmulțit cu prima constrângere -1), atunci problema originală va avea forma:

În conformitate cu articolul 2 introduce două variabile Y1 și Y2. în care, în baza regulii 3, y1 ≥ 0, iar y2 variabilă nu este limitată în semn.

Definim matricea problemei dublă a restricțiilor de coeficienți pe baza articolului 4:

În conformitate cu articolul 5 componente vectoriale numere libere corespunzătoare sunt coeficienți necunoscuți funcției obiectiv a problemei inițiale, adică

Scriem constrângerile problemei dublă:

Prima și a doua restricție au o inegalitate din cauza faptului că x1 variabile și x2 satisface starea non-negativitate și semnul «≥» determinată de regulile 1 și 7. Variabilele X3 și X4 nu sunt restricționate în semn, astfel încât a treia și a patra constrângeri ale problemei duale scrise în formă ecuații.

Pe baza articolului 7, vom scrie funcția obiectiv a problemei dublă:
.

Astfel, dubla pereche va fi după cum urmează: