MOO programowanie liniowe(chyba się przyda!!!), Automatyka i Robotyka, Semestr III, Metody Obliczeniowe ...
[ Pobierz całość w formacie PDF ]
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
0
c
1
x
1
c
2
x
2
...
c
n
x
n
min
(1)
Funkcje
f
nazywamy
funkcją celu
lub
funkcją kryterialną
. Zadaniem programowania
liniowego jest minimalizacja lub maksymalizacja funkcji celu przy określonych założeniach:
a
11
x
1
a
12
x2
...
a
1n
x
n
b
1
a
21
x
1
a
22
x2
...
a
2n
x
n
b
2
...
a
m1
x
1
a
m2
x2
...
a
mn
x
n
b
m
x
1
, x
2
,
...
, x
n
0
(2)
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
n+1
. Nowa zmienna
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
0
c
1
x
1
c
2
x
2
...
c
n
x
n
0x
n
1
0x
n
2
...0x
n
m
min
(3)
a
11
x
1
a
12
x2
...
a
1n
x
n
x
n
1
=
b
1
a
21
x
1
a
22
x2
...
a
2n
x
n
x
n
1
=
b
2
...
a
m1
x
1
a
m2
x2
...
a
mn
x
n
x
n
m
=
b
m
x
1
, x
2
,
...
, x
n
, x
n
1
, x
n
2
, x
n
m
0
(4)
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 znaleźć 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
x
1
2
x
2
2
x
3
15
3
x
1
0
x
2
1
x
3
20
2
x
1
2
x
2
2
x
3
18
f
=60
x
1
40
x
2
64
x
3
(5)
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.
[
]
(6)
B
=
[
]
(7)
b
=
[
]
(8)
1 2 2 1 0 0
3 0 1 0 1 0
2 2 2 0 0 1
1 0 0
0 1 0
0 0 1
15
20
18
A
=
f
=
[
60 40 64 0 0 0
]
(9)
I
=
[
0 0 0 0 0 0
]
(10)
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
i
X
i
x
1
x
2
x
3
x
4
x
5
x
6
b
i
b
i
/ A
ir
0
x
4
1
2
2
1
0
0
15
7.5
0
x
5
3
0
1
0
1
0
20
20
0
x
6
2
2
2
0
0
1
18
9
I
j
0
0
0
0
0
0
c
j
- I
j
60
40
64
0
0
0
Tabela 1. Krok 1.
Zadanie uważa się za skończone, gdy spełnione jest
kryterium optymalności
. Gdy
wskaźnik optymalności t = c
j
- I
j
dla wszystkich zmiennych niebazowych jest niedodatni (nieujemny
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
3
. Nową
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
i
/ A
ir
jest najmniejsza. Iloraz należy obliczyć jedynie dla dodatnich
zmiennych decyzyjnych
A
ir
. W naszym przypadku zmienna x
4
będzie opuszczać bazę.
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
A
=
B
−1
A
oraz
b
=
B
−1
b
. Macierz B z nową zmienną bazową ma postać:
[
]
(11)
2 0 0
1 1 0
2 0 1
B
=
Współrzędne nowego wierzchołka liczone są ze wzoru
I
=
c
T
B
−1
A
co prowadzi do
nowych współrzędnych:
I
=
[
32 64 64 32 0 0
]
.Wektor c
B
zawiera wagi zmiennych
bazowych pozyskane z poprzedniego wierzchołka.
Obliczone wartości tworzą kolejną, drugą tabele simpleksów. Wskaź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
i
X
i
x
1
x
2
x
3
x
4
x
5
x
6
B
i
B
i
/ A
ir
64
x
3
0.5
1
1
0.5
0
0
7.5
15
0
x
5
2.5
-1
0
-0.5
1
0
12.5
5
0
x
6
1
0
0
-1
0
1
3
3
I
j
32
64
64
32
0
0
c
j
- I
j
28
-24
0
-32
0
0
Tabela 2. Krok 2
I
i
X
i
x
1
x
2
x
3
x
4
x
5
x
6
B
i
64
x
3
0
1
1
1
0
-0.5
6
0
x
5
0
-1
0
2
1
-2.5
5
60
x
1
1
0
0
-1
0
1
3
I
j
60
64
64
4
0
28
c
j
- I
j
0
-24
0
-4
0
-28
Tabela 3. Krok 3
Funkcja przyjmuje wartość maksymalną równą 564 dla x
1
=3, x
2
=0, x
3
=6. Dodatkowo
zmienna bilansująca x
5
znajduje się w bazie, co prowadzi do wniosku, że układ posiada zbędne
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
.
[ Pobierz całość w formacie PDF ]