020 021 2

20 Programowanie liniowe

Zadania programowania liniowego o małych rozmiarach (w których występują dwie zmienne ograniczające lub też dwa ograniczenia) można rozwiązać metodą geometryczną, rysując na płaszczyźnie zbiór rozwiązań dopuszczalnych i znajdując taką warstwicę funkcji celu, która ma przynajmniej jeden punkt wspólny ze zbiorem rozwiązań dopuszczalnych i jednocześnie wyznacza optymalną (czyli maksymalną lub minimalną) wartość funkcji celu.

W wielu zagadnieniach praktycznych niezbędne jest rozwiązanie zadań, w których występują setki lub tysiące zmiennych decyzyjnych i warunków ograniczających. Uniwersalnie stosowanym sposobem rozwiązania takich zadań jest wówczas metoda simpleks. Jej wykorzystanie wymaga sprowadzenia zbioru warunków ograniczających do postaci układu równań liniowych. Można to łatwo osiągnąć, dołączając do warunków ograniczających w postaci nierówności zmienne bilansujące. Dokonanie tego zabiegu doprowadza często zbiór warunków ograniczających do znanej z algebry liniowej teorii rozwiązywania układu równań liniowych postaci bazowej. Pozwala ona łatwo wskazać na rozwiązanie bazowe i wyróżnić zmienne bazowe oraz zmienne nic-bazowe.

Zazwyczaj pierwsze otrzymane w taki sposób rozwiązanie bazowe nie jest optymalne i wymaga poprawy. Pozwala na to algorytm metody simpleks. Ma on charakter iteracyjny. W kolejnych krokach, wykorzystując kryterium optymalno-ści, sprawdzamy, czy aktualnie rozpatrywane rozwiązanie jest optymalne, czy też nie. Jeżeli rozwiązanie nie jest optymalne, to należy je poprawić. Metoda simpleks wskazuje na sposób uzyskania kolejnego rozwiązania dopuszczalnego. Polega ona na tym, że jedna z dotychczasowych zmiennych niebazowych zostaje wprowadzona do bazy, natomiast jedna z dotychczasowych zmiennych bazowych opuszcza bazę. Kryterium wejścia wskazuje na to, która zmienna niebazowa ma się stać zmienną bazową, natomiast kryterium wyjścia wskazuje na zmienną bazową, która ma opuścić bazę. Sposób generowania nowego rozwiązania proponowany w metodzie simpleks gwarantuje, że nowa wartość funkcji celu będzie lepsza (a przynajmniej nie gorsza) od wartości dotychczasowej.

Przedstawiony powyżej podstawowy wariant metody wymaga często uzupełnienia. Może się okazać, że doprowadzenie zbioru warunków ograniczających do postaci równości nie jest wystarczające do otrzymania pierwszego rozwiązania dopuszczalnego. Możemy je wówczas uzyskać, wprowadzając do zadania nowe zmienne, zwane zmiennymi sztucznymi. Zbiór rozwiązań dopuszczalnych może być pusty. Łatwo to wykryć wtedy, kiedy możliwe jest zastosowanie metody geometrycznej.

Pokażemy, w jaki sposób można się o tym dowiedzieć przez analizę tablic simpleksowych. Analiza ta pozwala również określić, czy istnieje dokładnie jedno rozwiązanie optymalne, czy jest ich nieskończenie wiele lub też czy funkcja celu jest nieograniczona.

Innym dodatkowo rozpatrywanym zagadnieniem jest analiza wrażliwości współczynników funkcji celu oraz prawych stron warunków ograniczających.

Chodzi tu o to, aby ustalić, w jakim zakresie współczynniki te mogą ulegać zmianie, aby nie spowodowało to zmiany rozwiązania w warunkach wyjściowych.

Mając dane zadanie programowania liniowego (zwane dalej zadaniem pry-malnym), możemy — zgodnie z ustalonymi regułami — utworzyć zadanie dualne. Para zadań złożona z zadania prymalnego i dualnego charakteryzuje się interesującymi i ważnymi własnościami, mającymi zastosowanie w rozpatrywanych dalej zagadnieniach. Własności te wykorzystywane są w pewnej odmianie metody simpleks, którą — dla odróżnienia od poprzedniej, prymalnej metody simpleks — nazwiemy dualną metodą simpleks.

Możemy również rozpatrywać parametryczne programowanie liniowe. Wartości współczynników funkcji celu lub warunków ograniczających uzależnione są od wartości pewnego parametru. Można podzielić obszar zmienności parametru na przedziały i wskazać, jakie rozwiązania optymalne odpowiadają wartościom parametru należącym do tych przedziałów.

W rozdziale tym zajmiemy się przedstawieniem najważniejszych zagadnień programowania liniowego. Omówimy sposób budowy modelu matematycznego tego zadania, metodę geometryczną oraz różne aspekty prymalnej metody simpleks. Przedstawimy reguły tworzenia zadania dualnego oraz dualnej metody simpleks, omówimy również najważniejsze własności programowania parametrycznego.

Modele liniowe mają ogromne znaczenie w badaniach operacyjnych. Wciąż rozwiązuje się praktycznie wiele takich zagadnień. Przedstawimy dalej trzy wybrane zagadnienia: zagadnienie rozkroju, diety i parametrycznego programowania produkcji Rozwiążemy je, wykorzystując programy komputerowe wchodzące w skład pakietu Badania operacyjne z komputerem. Wersja 2.01 (2007): SIMP. EXE, DUAL.EXE i PARAM.EXE¹.

1.2. Metoda geometryczna

1.2.1. Model matematyczny

Budowę modelu matematycznego zilustrujemy za pomocą prostego problemu programowania produkcji, który następnie zostanie wielokrotnie wykorzystany w dalszych rozważaniach.

1

W powszechnie dostępnym arkuszu kalkulacyjnym Microsoft F.xce! znajdziemy moduł pod nazwą So'ver. który umożliwia nam rozwiązanie większych zadań liniowych niż programy dydaktyczne z pakietu Badania operacyjne z komputerem. Wersja 2.07 (2007) (maksimum 200 zmiennych). Zapewne osoby zainteresowane profesjonalnym wykorzystaniem metod badań operacyjnych sięgną w przyszłości do tego oprogramowania, a także do innych wyspecjalizowanych pakietów, takich jak SAS, LINDO itd. Podobna uwaga dotyczy również innych zagadnień rozpatrywanych w tej pracy.