Metoda Cal pentru rezolvarea problemelor de programare liniară

Cel mai simplu și mai evident metoda de programare liniară (LP) este o metodă grafică. Acesta este utilizat pentru a rezolva problemele LP cu două variabile.

Luați în considerare problema LP în notație standard:

Fie n = 2. și anume ia în considerare această problemă în planul. Lăsați sistemul de inegalități compatibil (are cel puțin o soluție).

Fiecare inegalitate sistemului definește un geometrically semiplan cu linia de delimitare ai1x1 + ai2x2 = bi. i = 1,2, ... m. Condițiile nonnegativeness definesc semiplanul, respectiv, cu liniile de delimitare x1 = 0, x2 = 0. sistemul este consistent, deci semiplanul ca seturi convexe se intersectează, formează o parte comună, care este convexă și o pluralitate este un set de puncte, coordonatele fiecăruia dintre acestea sunt soluția la acest sistem. Totalitatea acestor puncte se numește soluții poligon. Acesta poate fi un punct, un segment, o rază, poligon, zona poligonală nelimitată.

Astfel, problema de programare liniara geometrica (ZLP) reprezintă găsirea unui punct al soluțiilor poligon care coordonează furniza valoare liniară obiectiv maximă funcție (minimă), în care soluțiile admisibile sunt soluții ale tuturor punctelor poligonului.

Ecuația liniară descrie setul de puncte situate pe o linie dreaptă. inegalitate descrie o anumită zonă în avion. Determina care parte a planului descris de inegalitate 2x1 + 3h212. În primul rând, vom construi un 2x1 drept + 3x2 = 12. Această linie trece prin punctul (6, 0) și (0, 4). Pentru a determina care planul jumătate satisface nevoia de a selecta orice punct de pe grafic nu este deținut, în mod direct, și să înlocuiască coordonatele sale în inegalitatea. Dacă inegalitatea, atunci acest punct este o soluție fezabilă și semiplanul care conține satisface punctului

inegalitate. Convenabil pentru utilizare atunci când sunt substituite în inegalitate este originea. Suplean x1 = x2 = 0 în 2x1 inegalitatea + 3h212. Obținem 20 + 3012. Această afirmație este adevărată, deci inegalitatea 2x1 + 3x2 12 corespunde inferior semiplanul care conține punctul (0,0). Acest lucru se reflectă în graficul prezentat în figura 1.

Fig. 1. Inegalitatea 2x1 + 3x2 12 corespunde inferior semiplanul.

În mod similar, puteți grafic fiecare problemă de constrângere de programare liniară.

Decizia fiecare sistem ZLP constrângeri de inegalitate este semiplanul care conține linia de delimitare și situate pe o parte a acesteia. Intersecția semiplanuri, fiecare dintre care este definită de inegalitatea corespunzătoare a sistemului, numit domeniul soluțiilor fezabile sau domeniu. Trebuie amintit faptul că zona de soluții fezabile satisface

Condițiile nonnegativeness (xj 0, j = 1, ..., n). Coordonatele oricărui punct aparținând domeniului de definiție este o soluție valabilă pentru problema.

Pentru a găsi valoarea extremale a funcției obiectiv când rezolvarea problemelor reprezentate grafic LP folosind vectorul gradientului, coordonatele care sunt derivate parțiale ale funcției obiective, adică,

.

Acest vector indică direcția cea mai abruptă funcției din stânga-tse schimbare. O linie dreaptă perpendicular pe vectorul gradientului este nivelul liniei funcției obiectiv. În orice moment funcția obiectiv linia nivel are aceeași valoare. Egalăm valoarea functiei obiectiv a constanta „a“. Modificarea valorii „a“. Obținem o familie de linii paralele, fiecare dintre acestea fiind un nivel de linie.

O proprietate importantă a unei funcții liniare a liniei de nivel este că mișcarea paralelă a liniei într-o singură direcție sporește nivelul, în timp ce deplasarea în cealaltă direcție - scade.

Din punct de vedere geometric, problema programării liniare se solicită un astfel de punct de colț sau un set de puncte ale setului fezabil de soluții, care se realizează prin cel mai de sus nivel linie (inferior) situate pe (aproape) în altă direcție de cea mai abruptă creștere.

Soluție grafică Metoda ZLP constă din următorii pași.

Construit o zonă poligonală de soluții fezabile ZLP - SDT,

Gradient vector Construit CP într-un punct X0 apartine SDT -

.

Nivelul 3. Linia C1x1 + C2x2 = a (a este o valoare constantă) - o linie perpendiculară pe vectorul gradientului

- se deplasează în direcția vectorului în maksimizatsiif caz (x1, x2), atâta timp cât frunzele din afara SDT. Punct de rezervă (sau puncte) din regiune cu mișcare și un punct de maxim f (x1, x2).

4. Pentru a găsi originea sa este suficientă pentru a rezolva două ecuații ale liniilor derivate din restricțiile relevante și oferind la punctul de intersecție al maxim. Valoarea lui f (x1, x2), găsit în punctul rezultat este maxim.

La minimizarea f (x1, x2) la nivelul liniei se deplasează în direcția opusă vectorului de gradient. În cazul în care o linie dreaptă, așa cum se mișcă nu lasă SDT, corespunzător al maximă sau minimă a lui f (x1, x2) nu există.

Dacă nivelul liniei paralelă cu orice problemă de limitare funcțională, valoarea DF optimă va fi atinsă în orice punct al acestei limitări, situată între două puncte unghiulare optime și, prin urmare, oricare dintre aceste puncte este soluția optimă ZLP.

Luați în considerare soluția grafică a problemelor de programare lineară prin exemplul următor.