Strona główna

Zadanie Programowania Liniowego (postać standardowa)


Pobieranie 120.33 Kb.
Data19.06.2016
Rozmiar120.33 Kb.

K.Pieńkosz Badania Operacyjne Programowanie liniowe

Zadanie Programowania Liniowego

(postać standardowa)

Polega na znalezieniu optymalnych wartości zmiennych decyzyjnych = (x1x2,..., xn)T maksymalizujących funkcję celu

przy spełnieniu ograniczeń



gdzie cj, aij, bi znane współczynniki oraz m < n



Zapis wektorowy

gdzie


  1. c = (c1c2,..., cn)T

  2. b = (b1b2,..., bm)T

  3. A = [aij] – macierz ograniczeń m x n

Inne równoważne postaci zadania PL

  1. “min” zamiast “max” w funkcji celu

  2. znaki “’’ lub “’’ zamiast “=’’ w ograniczeniach

  3. zmienne decyzyjne xj nieograniczone lub ograniczone dowolnymi wartościami od dołu i/lub od góry

Reguły równoważnych przekształceń

  1. zamiana rodzaju ekstremów

min cTx = – (max -cTx )

  1. zamiana ograniczeń nierównościowych na równościowe

wprowadzenie zmiennej dopełniającej xd

aTx b aTx + xd = b, xd 0

aTx b aTxxd = b, xd 0

  1. zamiana ograniczeń równościowych na nierównościowe

aTx = b aTx b i aTx b

  1. zamiana zmiennych nieograniczonych na zmienne nieujemne

wprowadzenie par zmiennych xj+, xj i podstawienie

xj := xj+ – xj , xj+ 0 i xj 0

Przykład

Firma wytwarza dwa rodzaje farb – do malowania wnętrz (W) i na zewnątrz (Z). Do produkcji tych farb niezbędne są dwa podstawowe składniki A i B. Maksymalne dzienne zapasy tych składników wynoszą odpowiednio 6 i 8 kg, natomiast ich zużycie na 1 tonę farby jest następujące:




Zużycie składników (w kg)




Składniki

farba W

farba Z

A

2

1

B

1

2

Badania rynkowe pokazały, że dzienny zbyt na farbę W nigdy nie przekracza 2 ton i nie jest wyższy od zbytu na farbę Z o więcej niż 1 tonę. Zysk ze sprzedaży 1 tony farby W wynosi 20 tys. zł, a farby Z 30 tys. zł.

Należy określić dzienne wielkości produkcji farb W i Z przynoszące największy łączny zysk.

Model Programowania Liniowego

  1. zmienne decyzyjne

xW – dzienna wielkość produkcji farby W (w tonach)

xZ – dzienna wielkość produkcji farby Z (w tonach)



  1. funkcja celu

max x0 = 20xW + 30xZ

  1. ograniczenia

2xW + xZ 6

xW + 2xZ 8

xWxZ 1

xW 2

xW 0, xZ 0





Interpretacja graficzna zadania PL

max x0 = 20xW + 30xZ (0)

przy ograniczeniach

2xW + xZ 6 (1)



xW + 2xZ 8 (2)

xWxZ 1 (3)

xW 2 (4)

xW 0 (5)



xZ 0 (6)


Rozwiązanie optymalne:

xW* = 11/3 , xZ* = 31/3 , x0* = 1262/3

Analiza parametryczna

max x0 = cxW + 30xZ cparametr

przy ograniczeniach

2xW + xZ 6



xW + 2xZ 8

xWxZ 1

xW 2

xW 0, xZ 0



wartość c

rozwiązanie optymalne

optymalna wartość f. celu

(-, 15]

xW=0, xZ=4

120

[60, )


xW=2, xZ=2

2c + 60

Analiza parametryczna

max x0 = 20xW + 30xZ

przy ograniczeniach

2xW + xZ b b – parametr



xW + 2xZ 8

xWxZ 1

xW 2

xW 0, xZ 0



wartość b

rozwiązanie optymalne

wartość f. celu

(-, 0]





[7, )


xW=2, xZ=3

130

Przypadki w Programowaniu Liniowym

  1. zbiór rozwiązań dopuszczalnych jest pusty (ograniczenia są sprzeczne) – brak rozwiązań

  2. zbiór rozwiązań dopuszczalnych jest niepusty oraz funkcja celu jest ograniczona od góry (dla problemu maksymalizacji) – istnieje co najmniej jedno rozwiązanie optymalne w punkcie wierzchołkowym

  3. funkcja celu jest nieograniczona z góry na zbiorze rozwiązań dopuszczalnych – zadanie jest nieograniczone, brak skończonego rozwiązania optymalnego

Wniosek


Rozwiązań optymalnych zadania PL można szukać wśród punktów wierzchołkowych (dopuszczalnych rozwiązań bazowych)


Ogólna idea algorytmu sympleks

  1. Wyznacz początkowy punkt wierzchołkowy (początkowe dopuszczalne rozwiązanie bazowe)

  2. Test optymalności – czy rozwiązanie gorsze od sąsiednich ? Jeżeli nie, to STOP – znaleziono rozwiązanie optymalne, jeżeli tak idź do 3.

  3. Przejdź do sąsiedniego punktu wierzchołkowego, dającego lepszą wartość funkcji celu. Idź do 2.

Szczegółowe elementy algorytmu sympleks

  1. wyznaczanie początkowego rozwiązania bazowego

  2. warunki optymalności rozwiązania bazowego

  3. wykrywanie niedopuszczalności i nieograniczoności

  4. sposób przechodzenia z bazy do bazy

  5. postępowanie w przypadku degeneracji

Początkowe rozwiązanie bazowe
ZPL




  1. Metoda kar




  1. Metoda dwufazowa

1. faza - wyznaczenie dopuszczalnego rozwiązania bazowego


2. faza - algorytm sympleks

Dualność
Zadanie pierwotne Zadanie dualne






Przykład – zadanie dualne
do modelu PL problemu produkcji farb

min v0 = 6v1 + 8v2 + v3 + 2v4

przy ograniczeniach

2v1 + v2 + v3 + v4 20



v1 + 2v2v3 30

v1 0, v2 0, v3 0, v4 0



Rozwiązanie optymalne:

v1* = 31/3 , v2* = 131/3 , v3* = 0, v4* = 0

v0* = 1262/3
Właściwości zadań dualnych
Między zadaniem pierwotnym a zadaniem dualnym zachodzi dokładnie jeden z następujących związków:

  1. oba zadania mają skończone rozwiązania optymalne. Wtedy max cTx = min bTv ,

  2. jedno z zadań jest niedopuszczalne, a drugie nieograniczone,

  3. oba zadania są niedopuszczalne.

Jeżeli


x - dowolne rozwiązanie dopuszczalne problemu pierwotnego

v - dowolne rozwiązanie dopuszczalne problemu dualnego

to



cTx bTv



Zadaniem dualnym do dualnego jest zadanie pierwotne


Związki między optymalnymi rozwiązaniami

zadania pierwotnego i dualnego
Niech

x*= (x1*x2*,..., xn*)T – optymalne rozw. zadania pierwotnego

v*= (v1*v2*,..., vm*)T – optymalne rozw. zadania dualnego

B*– baza dla optymalnego rozwiązania zadania pierwotnego


  • cTx*= bTv*



  • xB*= B* -1 b, v*=cBT B* -1

  • Warunek komplementarności


©snauka.pl 2016
wyślij wiadomość