Badania Operacyjne Bogumił Dałkowski
Modele optymalizacji liniowej
1
Badania Operacyjne Bogumił Dałkowski
Proces budowy modelu
model wyboru decyzji optymalnej, tzn.
takiej, która przy istniejących
ograniczeniach zapewnia, ze względu na
przyjęte kryterium, najlepszą realizację
celu
2
Badania Operacyjne Bogumił Dałkowski
Proces budowy modelu
1. Zdefiniowanie decyzji (zmiennych
decyzyjnych) x
2. Ustalenie warunków wyznaczających
zbiór decyzji dopuszczalnych D
3. Przyjęcie miernika realizacji celu f
4. Określenie podjęcia decyzji optymalnej
3
Badania Operacyjne Bogumił Dałkowski
Model optymalizacji liniowej
decyzję można wyrazić za pomocą nieujemnych
wartości liczbowych k zmiennych (zmiennych
decyzyjnych)
x=[x1, x2, & , xk],
ograniczenia dotyczące wyboru decyzji (zbiór
decyzji dopuszczalnych D) można zapisać jako
układ nierówności lub równań liniowych, jakie
muszą spełniać wartości zmiennych decyzyjnych
a1* x1 + a2* x2 + & + ak* xk <= b
4
Badania Operacyjne Bogumił Dałkowski
Model optymalizacji liniowej
stopień osiągnięcia celu przez decyzję
dopuszczalną wyraża wartość funkcji
liniowej f (funkcja celu)
f(x) = c1* x1 + c2* x2 + & + ck* xk
Kryterium optymalności jest max albo min
wartości funkcji celu f na zbiorze decyzji
dopuszczalnych D
5
Badania Operacyjne Bogumił Dałkowski
Model optymalizacji liniowej
ci - współczynniki funkcji celu
aij - współczynniki warunków
ograniczających
bi  wyrazy wolne warunków
ograniczających
6
Badania Operacyjne Bogumił Dałkowski
Wybór decyzji optymalnej
Solver
Komórka celu
Komórki zmieniane (decyzyjne)
Warunki ograniczające
Opcje
 Przyjmij model liniowy
 Przyjmij nieujemne
7
Badania Operacyjne Bogumił Dałkowski
Raport wyników
Solver
Komórka celu
Komórki decyzyjne
Warunki ograniczające
 Wiążące
 Nie wiążące
8
Badania Operacyjne Bogumił Dałkowski
Raport wrażliwości
Stabilność decyzji optymalnej
Sekcja raportu wrażliwości: Komórki decyzyjne
 Przyrost krańcowy = 0, tzn. jest jedna decyzja
optymalna
Stabilność decyzji optymalnej względem zmian
współczynników funkcji celu decyzji optymalnej
Sekcja raportu wrażliwości: Komórki decyzyjne
 Dopuszczalny wzrost / spadek współczynnika funkcji
celu, który nie powoduje zmiany decyzji optymalnej
(przy zachowaniu wartości pozostałych
współczynników funkcji celu jak w zadaniu
wyjściowym)
9
Badania Operacyjne Bogumił Dałkowski
Raport wrażliwości
Stabilność decyzji optymalnej względem zmian wyrazów
wolnych w warunkach ograniczających.
Sekcja raportu: Warunki ograniczające
 Cena dualna  przyrost wartości funkcji celu z tytułu
wzrostu o 1 wartości wyrazu wolnego
 Dopuszczalny wzrost / spadek wartości wyrazu
wolnego, który nie powoduje zmiany decyzji
optymalnej (przy zachowaniu wartości pozostałych
wyrazów wolnych jak w zadaniu wyjściowym)
10
Badania Operacyjne Bogumił Dałkowski
Studium przypadku - Mieszanki
W zakładzie przeróbczym w wyniku
oczyszczania otrzymuje się 3 gatunki węgla
Popioły [%] Substancje Koszt Produkcja
Gatunek
lotne [%] [zł /1 tona] [ton/mies]
A 10 10 60 10 000
B 15 15 50 20 000
C 15 40 40 30 000
11
Badania Operacyjne Bogumił Dałkowski
Studium przypadku - Mieszanki
Zamówienia klientów:
Gatunek Popioły [%] Substancje Cena
lotne [%] [zł /1 tona]
Mieszanka 14 - 22 14 - 18 65
półgruba
Mieszanka 12 - 15 18 - 30 60
gruba
12
Badania Operacyjne Bogumił Dałkowski
Studium przypadku - Mieszanki
Należy określić program produkcji mieszanek,
tak aby sprzedana została cała produkcja i
uzyskano maksymalny zysk
13
Badania Operacyjne Bogumił Dałkowski
Studium przypadku - Mieszanki
1. Zmienne decyzyjne
Gatunek A B C
Mieszanka x1 x2 x3
półgruba
Mieszanka x4 x5 x6
gruba
14
Badania Operacyjne Bogumił Dałkowski
Studium przypadku - Mieszanki
2. Ustalenie warunków wyznaczających
zbiór decyzji dopuszczalnych D
Warunek 1  ograniczenia produkcyjne
x1 + x4 = 10 000
x2 + x5 = 20 000
x3 + x6 = 30 000
Warunek 2  zawartość popiołów
 w mieszance półgrubej
14 <= (10 * x1 + 15 * x2 + 15 * x3) / (x1 + x2 + x3) <= 22
 w mieszance grubej
12 <= (10 * x4 + 15 * x5 + 15 * x6) / (x4 + x5 + x6) <= 15
15
Badania Operacyjne Bogumił Dałkowski
Studium przypadku - Mieszanki
Warunek 3  zawartość substancji lotnych
 w mieszance półgrubej
14 <= (10 * x1 + 15 * x2 + 40 * x3) / (x1 + x2 + x3) <= 18
 w mieszance grubej
18 <= (10 * x4 + 15 * x5 + 40 * x6) / (x4 + x5 + x6) <= 30
16
Badania Operacyjne Bogumił Dałkowski
Studium przypadku - Mieszanki
3. Funkcja celu
Przychody ze sprzedaży mieszanki półgrubej
65 * (x1 + x2 + x3)
Przychody ze sprzedaży mieszanki grubej
60 * (x4 + x5 + x6)
Koszt jednostkowy mieszanki półgrubej
(60 * x1 + 50 * x2 + 40 * x3) / (x1 + x2 + x3)
Koszt jednostkowy mieszanki grubej
(60 * x4 + 50 * x5 + 40 * x6) / (x4 + x5 + x6)
17
Badania Operacyjne Bogumił Dałkowski
Studium przypadku - Mieszanki
Funkcja celu
f(x)= 5*x1 + 15*x2 + 25*x3 + 0*x4 + 10*x5 + 20*x6
4. Kryterium optymalizacji
Należy uzyskać jak największy zysk
f(x) -> Max
18
Badania Operacyjne Bogumił Dałkowski
Studium przypadku - Warsztaty
Warsztat mechaniczny ma tokarkę (T) i
dwie frezarki (F1, F2)
Należy ustalić dodatkowy program pracy
warsztatu przy pozostałym czasie
dyspozycyjnym maszyn
19
Badania Operacyjne Bogumił Dałkowski
Studium przypadku - Warsztat
Klienci zamawiają części A, B, C
Wykonanie każdej z części A, B, C wymaga
pracy tokarki i jednej z frezarek
Czas operacji Część A Część B Część C Czas
dyspozycyjny
Tokarka
2 1 5 200
Frezarka 1
6 5 3 84
Frezarka 2
5 5 4 100
Zysk jedn.
60 40 35
20
Badania Operacyjne Bogumił Dałkowski
Studium przypadku - Warsztat
1. Zmienne decyzyjne
Czas operacji Część A Część B Część C Czas
dyspozycyjny
Tokarka
x1 x2 x3 200
Frezarka 1
x4 x5 x6 84
Frezarka 2
x7 x8 x9 100
Zysk jedn.
60 40 35
21
Badania Operacyjne Bogumił Dałkowski
Studium przypadku - Warsztat
2. Ustalenie warunków wyznaczających
zbiór decyzji dopuszczalnych D
Warunek 1  ograniczenia równościowe
x1 = x4 + x7
x2 = x5 + x8
x3 = x6 + x9
Warunek 2  ograniczenie czasu dyspozycyjnego
maszyn
2 * x1 + x2 + 5 * x3 <= 200
6 * x4 + 5 * x5 + 3 * x6 <= 84
5 * x7 + 5 * x8 + 4* x9 <= 100
22
Badania Operacyjne Bogumił Dałkowski
Studium przypadku - Warsztat
3. Funkcja celu
Miernikiem realizacji celu jest zysk ze
sprzedaży części A, B, C
f(x) = 60 * x1 + 40 * x2 + 35 * x3
23
Badania Operacyjne Bogumił Dałkowski
Studium przypadku - Warsztat
4. Kryterium optymalizacji
Należy uzyskać jak największy zysk
f(x) -> Max
24
Badania Operacyjne Bogumił Dałkowski
Studium przypadku - Warsztat
Jaki jest optymalny program produkcji:
Przy jakim poziomie ceny części B ich
produkcja będzie optymalna ?
Jaką sumę można przeznaczyć na zakup
dodatkowego wyposażenia frezarek, które
skraca czas obróbki części o 20% ?
25
Badania Operacyjne Bogumił Dałkowski
Studium przypadku - Batony
Przedsiębiorstwo wytwarzające wyroby
czekoladowe postanawia uruchomić produkcję
próbną dwóch wyrobów W1, W2
Na uruchomienie produkcji może przeznaczyć
 6 godz pracy urządzenia
 240 kg masy bakaliowej (podstawowy składnik
produkcji)
Pracownicy oddelegowani do produkcji próbnej
powinni zarobić co najmniej 400 zł
Wielkość produkcji wyraża się w kg [100 kg]
26
Badania Operacyjne Bogumił Dałkowski
Studium przypadku - Batony
Wyrób Praca Masa Robocizna Zysk
urządzeń [kg/100 kg] [zł/100 kg] [zł/100 kg]
[h/100 kg]
W1 2,0 40 100 480
W2 1,2 60 200 210
Zasoby 6,0 [h] 240 [kg] 400 [zł]
27
Badania Operacyjne Bogumił Dałkowski
Studium przypadku - Batony
1. Zmienne decyzyjne
x1  planowana wielkość produkcji W1
x2  planowana wielkość produkcji W2
jednostka produkcji [100 kg]
28
Badania Operacyjne Bogumił Dałkowski
Studium przypadku - Batony
2. Ustalenie warunków wyznaczających
zbiór decyzji dopuszczalnych D
Warunek 1  ograniczenie czasu pracy
urządzenia
2 * x1 + 1,2 * x2 <= 6
Warunek 2  ograniczenie surowcowe
40 * x1 + 60 * x2 <= 240
Warunek 3  ograniczenie płacowe
100 * x1 + 200 * x2 => 400
29
Badania Operacyjne Bogumił Dałkowski
Studium przypadku - Batony
3. Funkcja celu
Miernikiem realizacji celu jest zysk ze
sprzedaży wyrobów produkcji próbnej
f(x) = 480 * x1 + 210 * x2
4. Kryterium optymalizacji
Należy uzyskać jak największy zysk
f(x) = 480 * x1 + 210 * x2 -> Max
30