P1	P2	ZASOBY
S1	5	4	22
S2	5	6	45
S3	3	7	33
ZYSK	3	4

3.Zagadnienia dualne

Postać klasyczna:

Ogólna wartość posiadanych surowców:

22y₁+45y₂+33y₃

Wartość surowców potrzebna do wytworzenia produktu:

P1: 5y₁+5y₂+3y₃

P2: 4y₁+6y₂+7y₃

Zadanie minimalizacji wartości zastosowanych surowców do produkcji P1 i P2:

22y₁+45y₂+33y₃ ->min.

5y₁+5y₂+3y₃ ≥3

4y₁+6y₂+7y₃ ≥4

Zadanie to można zapisać w postaci macierzowej:

Zmienne decyzyjne:

y=

y b → min

y A ≥ c

y ≥ 0

Rozwiązując zadanie metodą dualną korzystam z podstawowych twierdzeń o dualności:

cx ≤ yb (wartości funkcji celu)

y(b-Ax) = 0 (związek 1)

x(yA-c) = 0 (związek 2)

cx = yb

Związek 1

Jeżeli x i y są dowolnymi rozwiązaniami dopuszczalnymi, odpowiednio, zadania prymarnego i dualnego, to wartości funkcji celu w tych zadaniach

spełniają zależność:

y(b-Ax)=
*
=

=y1(2-5x1-4x2)+y2(45-5x1-6x2)+y3(33-3x1-7x2)=0

Związek 2( o komplementarności)

Jeżeli x i y są rozwiązaniami optymalnymi, odpowiednio, zadania prymarnego

i dualnego, to zachodzą związki

Związek 3

Dla rozwiązań optymalnych x i y odpowiednio, zadania prymarnego

i dualnego, to zachodzi związek:

cx = y b

Uogólnienie przedstawionych warunków:

1.Jeżeli dowolna zmienna w rozwiązaniu optymalnym zadania prymarnego lub dualnego jest dodatnia, to odpowiadający jej komplementarny warunek ograniczający spełniony jest jako równanie.

2. Jeżeli dowolny warunek ograniczający dla rozwiązania optymalnego zadania prymarnego lub dualnego spełniony jest jako ostra nierówność, to odpowiadająca temu warunkowi zmienna komplementarna przyjmuje wartość zero.

Zagadnienia prymarne Zagadnienia dualne

f *(x₁,x₂,x₃)=3x₁ + 4x₂ -> max f*(y₁,y₂,y₃)=22y₁+45y₂+33y₃ min.

5x₁ + 4x₂ ≤ 22 5y₁+5y₂+3y₃ ≥3

5x₁ + 6x₂ ≤ 45 4y₁+6y₂+7y₃ ≥4

3x₁ + 7x₂ ≤ 33

x₁;x₂≥0 y₁,y₂,y₃ ≥0

(x₁ =0,96; x₂ =4,3)

ponieważ zmienne z zagadnienia prymarnego x₁;x₂≥0 więc odpowiadające im warunki komplementarne muszą być spełnione jako równania.

5y₁+5y₂+3y₃ ≥3

4y₁+6y₂+7y₃ ≥4

Sprawdźmy teraz, które z warunków ograniczających w zadaniu prymarnym jest spełniony jako nierówność ostra(podstawiamy x₁ =0,96; x₂ =4,3 )

5x₁ + 4x₂ ≤ 22 5*0,96+4*4,3=22

5x₁ + 6x₂ ≤ 45 5*0,96+6*4,3≤ 45

3x₁ + 7x₂ ≤ 33 3*0,96+7*4,3=33

Ponieważ drugi z warunków ograniczających w zadaniu prymarnym jest spełniony jako nierówność ostra,więc odpowiada mu w zadaniu dualnym zmienna komplementara y₂=0.

Podstawiajac do układu równań wartość y₂=0,otrzymujemy:

5y₁+5y₂+3y₃ =3

4y₁+6y₂+7y₃ =4

5y₁+3y₃=3/*7

4y₁+7y₃ =4/*-7

35y₁+21y₃=21

-12y₁-21y₃ =-12

23 y₁=9

y₁=0,39

3y₃=3-5*0,39

3 y₃=1,05

y₃=0,35

11

---