412 2

412

JO. Optymalizacja

Optymalny wektor dopuszczalny (rozwiązanie optymalne) jest tym wektorem dopu^ czalnym, dla którego funkcja f osiąga największą z wartości osiąganych dla wektorów dopuszczalnych. Fundamentalne znaczenie ma poniższe twierdzenie 10.1.1, o którego prawdziwości czytelnik może łatwo się upewnić dla n—mś3 (ogólny dowód przytacza Gass [145], rozdział 3, twierdzenia 2 i 4). Zauważmy jednak, że terminologia w tej świetnej książce i w innych różni się nieco od naszej. Na przykład punkt, nazywany tu bazowym wektorem dopuszczalnym, określa się niekiedy jako „bazowe rozwiązanie dopuszczalne”. Podobnie, termin „rozwiązanie dopuszczalne” oznacza czasem to, co n\y nazywamy „wektorem dopuszczalnym”. Zmodyfikowaliśmy terminologię, gdyż — mówiąc - określenie „dopuszczalny” wskazuje na spełnienie ograniczeń (wraz z warunkami nieujemności) w danym punkcie, a nic np. to, żc ten punkt jest „możliwym” rozwiązaniem całego zadania. Takie same nazwy jak w tej książce stosują Kiinzi i in. [153). Sądzimy też. że taka terminologia jest bardziej sugestywna z geometrycznego punktu widzenia, pozwalającego na wyobrażenie sobie rozważanych algorytmów i twierdzeń.

Twierdzenie 10.1.1. Pewien optymalny wektor dopuszczalny jest również bazowym wektorem dopuszczalnym, tzn. co najmniej n-m jego współrzędnych jest zerami. Inaczej mówiąc, istnieje optymalne rozwiązanie dopuszczalne, w którym co najwyżej m współrzędnych jest dodatnich (a inne są zerami). Wektory kolumnowe z układu (10.1.2) odpowiadające niezerowym współrzędnym są niezależne liniowo.

Może istnieć wiele rozwiązań optymalnych; nie wszystkie z nich muszą być bazowymi wektorami dopuszczalnymi. Na przykład w zadaniu podobnym do przykładu 10.1.1 funkcja /mogłaby być taka, że prosta/(x₃, xj)=0 byłaby równoległa do jednego z boków pięciokąta; zob. przykład 10.2.31

Pytania przeglądowe

1.    Podać postać normalną zadania programowania liniowego. Określić pojęcia „wektor (punkt) dopuszczalny”, „bazowy- wektor dopuszczalny ” i „zmienna wolna”.

2.    Sformułować podstawowe twierdzenie optymalizacji liniowej (twierdzenie 10.1.1)-Czy może istnieć więcej niż jedno rozwiązanie optymalne? Czy każde rozwiązanie opV" malne jest bazowym wektorem dopuszczalnym?

10.2. Metoda sympleks

Zadanie polega obecnie na znalezieniu prawdziwego bazowego wektora dopusz^ nego, a więc tego, który ma n zerowych współrzędnych. W teorii można by wypróbo wszystkie możliwe sposoby — jest ich    ~~ wyboru n—m zerowych zmie^Q0^^c^

spośród n, odrzucić te kombinacje, które nie dają wektorów- dopuszczalnych i.wyhf*^-wśród pozostałych punkt dający największą wartość/. Byłoby to jednak niezmienne^⁰⁵®*