3179027800

Elementy Badań Operacyjnych

D(200; 600)    F(D) = 30-200 + 20-600 = 18000,

E(0; 800)    F(E) = 30-0 + 20-800 = 16 000.

Najwyższą wartość funkcja celu przyjmuje w punkcie D; zatem współrzędne tego punktu stanowią rozwiązanie optymalne problemu.

Rozwiązanie optymalne można znaleźć także znacznie szybciej. Przyjmuje się mianowicie dowolną wartość funkcji celu (taką aby można było ją nanieść na rysunek) i rysuje jej wykres, dla odróżnienia od warunków ograniczających - na rys. 1.1 zaznaczono ją linią przerywaną. Przyjmijmy np. wartość początkową 6000. Mamy zatem F(x\, *2) = 30xi + 20x2 = 6000; funkcja przecina oś Xi w punkcie 200 i oś X2 w punkcie 300. Zauważmy, że gdybyśmy przyjęli wartość wyższą np., 12000 to otrzymalibyśmy prostą o równaniu F(xi, X2) = 30xi + 20x2⁼ 12000. Prosta ta byłaby równoległa do pierwszej prostej, ale bardziej oddalona od początku układu współrzędnych. Gdybyśmy natomiast wzięli pewną wartość niższą np. 3000, to prosta F(x 1, X2) = 30xi + 20x2⁼ 3000 byłaby też równoległa do prostej pierwszej, ale leżałaby bliżej początku układu współrzędnych. Widzimy zatem, iż gdybyśmy na rysunek nanieśli proste dla różnych wartości F(xi, X2), wszystkie one byłyby równoległe do siebie i do pierwszej wyznaczonej prostej. Znalezienie punktu optymalnego sprowadza się do tego, aby w wieloboku rozwiązań dopuszczalnych znaleźć punkt leżący na prostej o najwyższej wartości funkcji celu.

Praktycznie jednak wystarczy wykreślić jedną prostą i ją przesuwać równolegle, w zależności od potrzeb w górę lub w dół, tak aby w przypadku maksymalizacji funkcji celu znaleźć punkt zbioru rozwiązań dopuszczalnych położony możliwie najdalej od początku układu współrzędnych (jeżeli funkcja celu jest minimalizowana - będziemy szukać punktu położo-

Antoni Goryl, Anna Walkosz: Programowanie liniowe strona 8