422 2

422

10. Optymalizacja

badania

(a)    Wyrazić zadanie dualne w postaci normalnej określonej w § 10.1 (zauważmy nie ma tu warunku nieujemności dla y).

(b)    Wykazać, że zadaniem dualnym dla zadania dualnego jest zadanie pierwotne

10.4. Zadanie transportowe i niektóre inne zadania

optymalizacyjne

Jednym z najhardziej znanych zadań optymalizacji jest zadanie transportowe. Załóżmy, że koncern ma / zakładów wytwarzających tygodniowo a_lt a_{2i a}, jednostek pewnego produktu. Dostarcza się go J odbiorcom, odpowiednio w ilości ój, b_x, ..., bj jednostek. Zakładamy, że łączne zapotrzebowanie jest równe całej produkcji, taj.

(10.4.1)    r*-iv

Przewiezienie jednostki produktu z /-tego zakładu do /-tego odbiorcy kosztuje c_i} dolarów. Zadanie polega na takim ustaleniu ilości x_tJ towaru dostarczanego z /-tego zakładu do /-tego odbiorcy (dla wszystkich /~1, 2,/ oraz j=l, 2,aby zminimalizować łączny koszt transportu. Jest to następujące zadanie optymalizacji liniowej (zmienne mają tu po dwa wskaźniki):

Znaleźć minimum wyrażenia

<10.4 2)    /=£

i=l}=1

przy warunkach (10.4.3)

i- 1

0=1,2,...,/),

(7=1,2.....J) (/+ J równań) i

(10.4.4)    x_tJ>0

{1J nierówności). Równania są zależne liniowo, gdyż i j    j i

Z Z^xiy^— Z Z^x/y=0-

*«iy-i y=u**i

Równań niezależnych liniowo jest więc co najwyżej m = /+ J-1. Z twierdzenia 101-¹ ^ nika, że istnieje optymalny schemat przewozów, w którym używa się co najwyżej i *' spośród U możliwych tras od producentów do odbiorców. W zasadzie zadanie transport można rozwiązywać metodą sympleks; istnieją jednak znacznie efektywniejsze met°4y WT korzystające szczególną strukturę układu (10.4.3); zob. np. Gass [145].