Metod Obliczeniowe Optymalizacji - laboratorium
Programowanie liniowe
Wprowadzenie
Celem ćwiczenia jest zapoznanie się z Zadaniem Programowania Liniowego (ZPL), nabycie
umiejętności rozwiązania ZPL za pomocą metody Simpleksów oraz implementacja i rozwiązanie
przykładowego problemu w środowisku MATLAB OPTIMIZATION TOOLBOX.
Programowanie liniowe
Zadanie programowania liniowego należy do zadań optymalizacji statycznej. Każde zadanie
można sprowadzić do liniowej funkcji celu i liniowych ograniczeniach. Postać standardową
programowania liniowego można przedstawić jako:
f = f ƒÄ…c1 x1ƒÄ…c2 x2ƒÄ…...ƒÄ…cn xn Śąmin
(1)
0
Funkcje f nazywamy funkcjÄ… celu lub funkcjÄ… kryterialnÄ…. Zadaniem programowania
liniowego jest minimalizacja lub maksymalizacja funkcji celu przy określonych założeniach:
a11 x1ƒÄ…a12 x2ƒÄ…...ƒÄ…a1n xnÄ…Ä…b1
a21 x1ƒÄ…a22 x2ƒÄ…...ƒÄ…a2n xnÄ…Ä…b2
... (2)
am1 x1ƒÄ…am2 x2ƒÄ…...ƒÄ…amn x Ä…Ä…bm
n
x1 , x2 ,... , xn‡Ä…0
Zależności (2) określają zbiór rozwiązań dopuszczalnych. Naturalnym problemem w przy
programowaniu jest implementacja nierówności. W tym celu zadanie programowania liniowego
należy przekształcić na postać kanoniczną. Aby uzyskać postać kanoniczną należy do (1) i (2)
dodać zmienne sztuczne nazwane zmiennymi bilansującymi, które w ostatecznym rozwiązaniu
będą zerowane.
W celu pozbycia się nierówności należy dodać kolejną zmienną x . Nowa zmienna
n+1
powinna być nieujemna, co pozwala na przekształcenie nierówności na równanie. Zadanie
zdefiniowane w (1) i (2) po przekształceniu na postać kanoniczną przybiera formę:
f = f ƒÄ…c1 x1ƒÄ…c2 x2ƒÄ…...ƒÄ…cn xnƒÄ…0xnƒÄ…1ƒÄ…0xnƒÄ…2ƒÄ…...ƒÄ…0xnƒÄ…mŚą min
(3)
0
a11 x1ƒÄ…a12 x2ƒÄ…...ƒÄ…a1n xnƒÄ…xnƒÄ…1 =b1
a21 x1ƒÄ…a22 x2ƒÄ…...ƒÄ…a2n xnƒÄ… xnƒÄ…1 =b2
... (4)
am1 x1ƒÄ…am2 x2ƒÄ…...ƒÄ…amn xnƒÄ… xnƒÄ…m=bm
x1 , x2 ,... , xn , xnƒÄ…1 , xnƒÄ…2 , xnƒÄ…m‡Ä…0
Metoda Simpleks
Rozwiązanie zadania programowania liniowego znajduje się w wierzchołku zbioru
rozwiązań dopuszczalnych. Metoda simpleks dokonuje przeglądu wierzchołków w celu znalezienia
optymalnego rozwiązania. W przypadku dużej ilości zmiennych, czas przeszukiwania wszystkich
wierzchołków byłby zdecydowanie za długi. Dlatego metoda simpleksów przeszukuje tylko
wybrane wierzchołki, tak dobierając kolejny, by funkcja celu malała.
Algorytm rozwiązania zadania programowania liniowego można sformułować następująco.
Należy znalez
ć dowolne (początkowe) rozwiązanie wierzchołkowe. Poprzez wymianę jednej
kolumny z bazy należy generować kolejne, sąsiednie rozwiązania wierzchołkowe tak, aby funkcja
celu malała (rosła).
Przykład Metody Simpleks
Algorytm zostanie wytłumaczony przykładem. Pewna firma produkuje 3 wyroby używając
3 maszyn. Maszyny nie mogą pracować dłużej niż 15, 20 i 18 godzin odpowiednio. Wartość
produktów to 60, 40 i 64 odpowiednio. Należy zmaksymalizować zysk. Ograniczenia maszyn
przedstawione sÄ… jako:
1 x1ƒÄ…2 x2ƒÄ…2 x3Ä…Ä…15
3 x1ƒÄ…0 x2ƒÄ…1 x3Ä…Ä…20
(5)
2 x1ƒÄ…2 x2ƒÄ…2 x3Ä…Ä…18
f =60 x1ƒÄ…40 x2ƒÄ…64 x3
Pierwszym krokiem jest zmiana układu (5) na postać kanoniczną poprzez dodanie
zmiennych bilansujących i pozbycie się nierówności. Następnym krokiem jest stworzenie macierzy
A ze zmiennymi decyzyjnymi, macierzy B ze zmiennymi bazowymi, macierzy b z aktualnym
rozwiÄ…zaniem dla zmiennych bazowych, macierzy f z wagami zmiennych bazowych oraz macierzy
I ze współrzędnymi aktualnego wierzchołka.
1 2 2 1 0 0 1 0 0 15
A= B= b=
3 0 1 0 1 0 (6) 0 1 0 (7) 20 (8)
[ ] [ ] [ ]
2 2 2 0 0 1 0 0 1 18
[ ] (9) [ ] (10)
f = 60 40 64 0 0 0 I = 0 0 0 0 0 0
Początkowo zakłada się że zmienne bilansujące znajdują się w bazie a punkt startowy to 0
dla każdej zmiennej. Stąd biorą się podane postacie macierzy. Z posiadanych danych można
utworzyć pierwszą tabele simpleksów:
I X x x x x x x b b / A
i i 1 2 3 4 5 6 i i ir
0 x 1 2 2 1 0 0 15 7.5
4
0 x 3 0 1 0 1 0 20 20
5
0 x 2 2 2 0 0 1 18 9
6
I 0 0 0 0 0 0
j
c 40 64 0 0 0
j - I 60
j
Tabela 1. Krok 1.
Zadanie uważa się za skończone, gdy spełnione jest kryterium optymalności. Gdy
wskaz
nik optymalności t = c dla wszystkich zmiennych niebazowych jest niedodatni (nieujemny
j - I
j
dla zadania minimalizacji), wtedy rozwiązanie jest optymalne. Tabela 1 przyjmuje kilka wartości
dodatnich, więc rozwiązanie nie jest optymalne.
Należy zastosować kryterium wejścia. Przedstawione rozwiązanie jest nieoptymalne, więc
istnieje przynajmniej jedna zmienna, którą trzeba przenieść do bazy w celu poprawy funkcji celu.
Do bazy należy prowadzić zmienną, która daje największy (najmniejszy dla minimalizacji)
współczynnik optymalności. W naszym przykładzie jest to r=3 co odpowiada zmiennej x . Nową
3
zmienną wstawia się na miejsce zmiennej ustalonej przez kryterium wyjścia. Usunięcie zmiennej
powinno zagwarantować, że nowe rozwiązanie bazowe będzie dopuszczalne. Z bazy usuwamy
zmienną dla której wartość b / A jest najmniejsza. Iloraz należy obliczyć jedynie dla dodatnich
i ir
zmiennych decyzyjnych A . W naszym przypadku zmienna x będzie opuszczać bazę.
ir 4
Kolejnym krokiem jest skonstruowanie 2-giej tabeli simpleksów poprzez obliczenie nowych
wartości macierzy. Nowe zmienne decyzyjne i bazowe otrzymuje się poprzez wyliczenie wyrażenia

Ä…
Ä…
oraz . Macierz B z nową zmienną bazową ma postać:
A= B-1 A b=B-1 b
2 0 0
B=
(11)
1 1 0
[ ]
2 0 1

Ä…
Współrzędne nowego wierzchołka liczone są ze wzoru I =cT B-1 A co prowadzi do
B
nowych współrzędnych: [ ] .Wektor c zawiera wagi zmiennych
I = 32 64 64 32 0 0
B
bazowych pozyskane z poprzedniego wierzchołka.
Obliczone wartości tworzą kolejną, drugą tabele simpleksów. Wskaz
nik optymalności nadal
zawiera nieujemne wartości, więc rozwiązanie nadal nie jest optymalne. Analogiczne należy
powtórzyć kryterium wejścia i wyjścia, i skonstruować kolejna tabele aż kryterium optymalności
zostanie spełnione. W naszym zadaniu już krok 3-ci zawiera optymalne rozwiązanie.
I X x x x x x x B B / A
i i 1 2 3 4 5 6 i i ir
64 x 0.5 1 1 0.5 0 0 7.5 15
3
0 x 2.5 -1 0 -0.5 1 0 12.5 5
5
0 x 1 0 0 -1 0 1 3 3
6
I 32 64 64 32 0 0
j
c 0 -32 0 0
j - I 28 -24
j
Tabela 2. Krok 2
I X x x x x x x B
i i 1 2 3 4 5 6 i
64 x 0 1 1 1 0 -0.5 6
3
0 x 0 -1 0 2 1 -2.5 5
5
60 x 1 0 0 -1 0 1 3
1
I 60 64 64 4 0 28
j
c 0 -24 0 -4 0 -28
j - I
j
Tabela 3. Krok 3
Funkcja przyjmuje wartość maksymalną równą 564 dla x =3, x =0, x =6. Dodatkowo
1 2 3
zmienna bilansująca x znajduje się w bazie, co prowadzi do wniosku, że układ posiada zbędne
5
ograniczenia, jednak zostały one specjalnie dobrane by w pełni zilustrować algorytm.
Wymagania
Przed przystąpieniem do laboratorium należy zapoznać się z zadaniem programowania
liniowego i metodą simpleks. Należy znać definicje: funkcji celu, zbioru rozwiązań
dopuszczalnych, postaci standardowej, kanonicznej, zmiennych bilansujÄ…cych, bazowych,
swobodnych, rozwiązania bazowego, kryterium wyjścia, wejścia i optymalności oraz należy znać
sposób tworzenia tabeli simpleksowej i liczenia kolejnych kroków. Należy pamiętać o
wydrukowaniu jednej strony tytułowej na każdą 3-2 osobową sekcje.
Program laboratorium
Część I:
Implementacja podanego w instrukcji przykładu programowania liniowego. Należy stworzyć
program w pliku .m w środowisku MATLAB, który zgodnie z algorytmem simpleks rozwiąże
zadanie przedstawione w sekcji przykład metody simpleks. Program powinien dać te same wyniki
co przykład oraz powinien być przystosowany do zmiany zmiennych początkowych.
Część II:
Rozwiąż podane na laboratorium zadanie programowania liniowego, używając napisanego w części
I programu. Wyznacz tabele simpleksowe kolejnych kroków. Na podstawie ostatniej tabeli wskaż
rozwiÄ…zanie.
Część III:
Rozwiąż zadanie z części II używając polecenia linprog z MATLAB OPLIMIZATION TOOLBOX.
Zwrócić uwagę na różne składnie funkcji, na przykład czym się różni linprog(f,A,b,[],[],lb) od
linprog(f,[],[],A,b,lb)
Sprawozdanie
W sprawozdaniu należy opisać wnioski ze wszystkich 3 części. Z części II należy umieścić
wyniki, stworzyć tabele simpleksów dla każdego kroku oraz przedstawić w skrócie sposób
działania algorytmu. Po wykonaniu części III należy porównać wyniki własnego algorytmu z
funkcją linprog. Dodatkowo należy dołączyć kod z pliku .m z MATLAB-a.
Literatura
Przykładowe materiały dostępne to:
1. Wykład.
2. Literatura podana na wykładzie (w części dotyczącej ZPL).
3. MATLAB OPTIMIZATION TOOLBOX help - plik załączony do instrukcji jako pdf.
4. Liczne materiały dostępne w sieci. Przykładowe hasła: linear programming, simplex
algorithm, programowanie liniowe, algorytm simpleks.