066 067 2

66

Programowanie liniowe

Twierdzenie 1.3

Dla rozwiązań optymalnych⁹ x, y, odpowiednio, zadania prymalnego i dual- ^:

nego zachodzi związek: cx=yb.

otu śk

Twierdzenie 1.4

Optymalne rozwiązanie zadania dualnego otrzymujemy ze wzoru:

y = c_B A h ,    |

gdzie A,,' jest macierzą odwrotną do macierzy bazowej A_n dla rozwiązania optymalnego zadania prymalnego, a c_n jest wektorem współczynników funkcji celu | zadania prymalnego stojących przy zmiennych bazowych w bazie A„.

Pokażemy zastosowanie twierdzenia o komplementarności dla zadania z przykładu 1.1. Równość (1.9) zapiszemy następująco:

	t	~14~		~2	2		\		14 — 2jC| -2-t2
						X\
y(b-Ax) = ly„ y2, y3]		8		1	2	x2		= L.vi, y2, y3]	8-x, -2x2
	\	16		4	0	—1	/		16 — 4jc i

= yi(14-2x, -2j:₂) + y₂(8-X| -2x₂)+yx₃(16-4.r_l) = 0.

b    A    _

Zależność (1.10) przyjmuje postać:

fV

	f	2 2~	\		V
			r		*1
> 1 n X II	[a. y2, y>}	1 2	- 12 3]		x2
	\	4 0	)

^x\

= 12yi + y₂ + 4y, — 2, 2y,+2y₂-3|

X₂

= (2y, + y₂ + 4y,-2)X| +(2.y, +2y₂-3)„t₂ = 0. ) —Z warunku (1.9) otrzymujemy:

>i (14 ~ 2x, — 2xf) +y₂(8 — jc, — 2x₂) +y₃( 16 — 4y,) = 0.

⁹ Jeżeli zarówno zadania prymalne jak i dualne mają rozwiązania dopuszczalne, to oba mają rozwiązania optymalne.

Od'-:

¹!    V'!-,

C

\IQW4 H Ił)

0,    "H)

f il.f-)

Jest to suma trzech składników, która ma dać wartość zero. Składniki te są iloczynami wartości nieujemnych. Wynika stąd, że każdy ze składników tej sumy musi być równy zeru. Gdyby choć jeden z tych składników był dodatni, to przynajmniej jeden z pozostałych składników musiałby przyjąć wartość ujemną dla skompensowania występującej wartości dodatniej, a to nie jest możliwe. Otrzymujemy więc zależności:

y,(14—2*i — 2x₂) = 0,    >0 A    - l - c O    (1.11)

y₂(8-x,-2x₂) = 0,    M    (1.12)

yj(16—4y,) = 0.    ^A    ‘    (1-13)

Z powyższych warunków wynika kilka istotnych wniosków.

Warunek (1.11)

Jeżeli yi > 0, to j14 — 2x,-2*₂-0. Oznacza to, że w zadaniu prymalnym pierwszy warunek ograniczający, komplementarny do zmiennej y, > 0, musi być spełniony jako równanie.

Jeżeli 14 — 2jc,-2x₂ > 0 (czyli w zadaniu prymalnym pierwszy warunek ograniczający jest spełniony jako ostra nierówność), to zmienna komplementarna y,=0.

Warunek (1.12)

Jeżeli y₂> 0, to 8-x,~2x₂ = 0. Oznacza to, że w zadaniu prymalnym drugi warunek ograniczający, komplementarny do zmiennej y₂ > 0, musi być spełniony jako równanie.

Jeżeli 8-x, -2x₂ > 0 (co oznacza, że drugi warunek ograniczający w zadaniu prymalnym jest spełniony jako ostra nierówność), to zmienna komplementarna

y₂=0-

Warunek (1.13)

Jeżeli >3>0, to 16-4x, = 0. Oznacza to, że w zadaniu prymalnym trzeci warunek ograniczający, komplementarny do zmiennej y₃ > 0, musi być spełniony jako równanie.

Jeżeli 16 — 4x|>0 (co oznacza, że trzeci warunek ograniczający w zadaniu prymalnym jest spełniony jako ostra nierówność), to zmienna komplementarna

y₃ = 0.    "O

Z warunku (1.10) otrzymujemy:

(2y, + .y_: + 4y₃-2)X| + (2y, +2y₂-3)x₂ = 0.

Podobnie jak w poprzednim przypadku mamy:

(1.14)

(1.15)

(2y, + y₂ + 4y,-2)x, =0,

(2>’i +2 y₂ - 3)x₂ = 0.