1
1. Programowanie liniowe
Istnieje wiele sytuacji decyzyjnych, które można opisać za pomocą modelu
matematycznego. W niniejszym rozdziale zaprezentowano takie sytuacje decyzyjne,
których modele mogą być zapisane jako zadania programowania liniowego.
Zadanie programowania liniowego polega na znalezieniu optymalnej (czyli
maksymalnej lub minimalnej) wartości funkcji liniowej zwanej funkcją celu przy
uwzględnieniu warunków ograniczających zapisanych w postaci układu nierówności
liniowych.
W procesie tworzenia programu liniowego wyróżnia się trzy podstawowe etapy:
1.
Należy zdefiniować zmienne decyzyjne (biorąc pod uwagę jednostki
w jakich są one wyrażone)
2.
Wybrać kryterium oceny podejmowania decyzji i zapisać w postaci funkcji
celu
3.
Określić wszystkie relacje między zmiennymi decyzyjnymi i zapisać je
w postaci warunków ograniczających
Zadanie programowania liniowego może mieć jedno rozwiązanie optymalne,
nieskończenie wiele rozwiązań lub może być zadaniem sprzecznym. Rozwiązania
programu liniowego mogą być liczbami całkowitymi (wtedy na zmienne decyzyjne
nałożone są dodatkowe warunki mówiące o tym).
1.1. Optymalny wybór asortymentu produkcji
Przykład 1. Zakład stolarski „Dudek” produkuje 4 rodzaje drewnianych zabawek
edukacyjnych. W procesie produkcji tych zabawek używane są dwa rodzaje drewna:
dąb i sosna oraz wykorzystywana jest energia elektryczna. Miesięczne limity drewna
wynoszą odpowiednio: dąb - 9000 kg , sosna - 12000 kg, energia elektryczna - 1200
kWh. Nakłady limitowanych środków na jednostkę produkcji zawiera tabela nr 1.
Ponadto wiadomo, że zyski jednostkowe ze sprzedaży zabawek wynoszą odpowiednio
4zł, 6zł, 3zł, 12zł. Ile należy produkować zabawek każdego rodzaju, aby nie
przekraczając limitów zużycia surowców zmaksymalizować zysk ze sprzedaży
zabawek?
2
Tabela nr 1
Ś
rodki produkcji
Jednostkowe zużycie środków produkcji
Zabawka 1
Zabawka 2
Zabawka 3
Zabawka 4
Dąb
(kg/szt)
1
2
1,5
6
Sosna
(kg/szt)
2
2
1,5
4
Energia
elektryczna
(kWh/szt)
0,2
0,4
0,3
0,5
Rozwiązanie zadania rozpoczynamy od zapisania programu liniowego.
Model matematyczny
Zmienne decyzyjne:
x
1
– planowana wielkość produkcji zabawek 1
x
2
- planowana wielkość produkcji zabawek 2
x
3
- planowana wielkość produkcji zabawek 3
x
4
- planowana wielkość produkcji zabawek 4
Funkcja celu
Celem zadania jest zmaksymalizowanie zysków ze sprzedaży zabawek, zatem funkcja
celu będzie następująca:
max
12
3
6
4
)
,
,
,
(
4
3
2
1
4
3
2
1
→
+
+
+
=
x
x
x
x
x
x
x
x
F
Warunki ograniczające
9000
6
5
,
1
2
4
3
2
1
≤
+
+
+
x
x
x
x
12000
4
5
,
1
2
2
4
3
2
1
≤
+
+
+
x
x
x
x
1200
5
,
0
3
,
0
4
,
0
2
,
0
4
3
2
1
≤
+
+
+
x
x
x
x
0
,
,
,
4
3
2
1
≥
x
x
x
x
C
x
x
x
x
∈
4
3
2
1
,
,
,
Zapis zadania w arkuszu Excel
Na rysunkach 1 i 2 przedstawiono arkusz kalkulacyjny z zapisanym zadaniem.
Pierwszy z rysunków zawiera dane wejściowe zapisane w postaci tabeli, drugi zawiera
formuły obliczeniowe.
3
Rys. 1. Dane do zadania zapisane w arkuszu
Rys. 2. Dane do zadania zapisane w arkuszu wraz z formułami obliczeniowymi
Analizując rysunki 1 i 2, w wierszu 8 znajdują się zmienne decyzyjne, w komórce F9
zapisana została formuła funkcji celu, a w wierszach 12, 13 14 formuły ograniczeń.
Aby wyznaczyć rozwiązanie optymalne tego zadania należy wybrać polecenie
Solver z menu Narzędzia (dla wersji Excel 2003 i niższych) lub polecenie Solver
z menu Dane dla wersji Excel 2007 ( zob. rysunek 3.)
Rys. 3. Pasek polecenia Solver w arkuszu Excel 2007
4
Następnie w oknie dialogowym Solvera należy wprowadzić parametry zadania
(zob. rys. 4).
Rys. 4. Okno dialogowe Solvera
Po pierwsze wprowadza się adres komórki zawierającej funkcję celu („Komórka
celu”) i określa się kierunek optymalizacji („Równa”). Następnie podaje się zakres
zmiennych decyzyjnych („Komórki zmieniane”) i wprowadza się warunki
ograniczające poprzez naciśnięcie opcji „Dodaj”. Wyświetlane jest wówczas okno
dialogowe (zob. rys.5). Aby wprowadzać kolejne ograniczenia należy wybrać przycisk
„Dodaj’. Opcja „Dodaj warunek ograniczający” pozwala również na wprowadzenie
ograniczenia mówiącego że zmienne decyzyjne mają być całkowite – jest to opcja
„int’(zob. rys. 6).
Rys. 5. Okno dialogowe opcji „Dodaj’ w Solverze
Rys. 6. Okno dialogowe opcji „Dodaj’, opcja zmienne całkowite
5
Po wprowadzeniu wszystkich ograniczeń należy przycisnąć przycisk „OK”
i wrócić do okna dialogowego Solvera. Następnie należy wybrać „Opcje” i zaznaczyć
„Przyjmij nieujemne” (zmienne decyzyjne mają być nieujemne:
0
,
,
,
4
3
2
1
≥
x
x
x
x
)
oraz „Przyjmij model liniowy”(zob rys.7).
Rys. 7. Okno dialogowe „Opcje”
Po dokonaniu opisanych czynności należy wybrać opcję „Rozwiąż” w oknie
dialogowym Solvera (zob. rys.4) i rozwiązać zadanie.
Interpretacja wyników
W wyniku wybrania przycisku „Rozwiąż”, w arkuszu pojawia się rozwiązanie
zadania i wyświetlane jest okno „Solver – Wyniki” z dwoma opcjami „Przechowaj
rozwiązanie” i „Przywróć wartości początkowe” (zob. rys 8). Aby zachować
znalezione rozwiązanie należy zaznaczyć opcję „Przechowaj rozwiązanie”.
Rys. 8. Okno dialogowe zawierające raporty
6
Okno „Solver – Wyniki” pozwala również wygenerować jeden z trzech raportów:
Wyników, Wrażliwości i Granic. W przypadku tego zadania można wygenerować
jedynie raport wyników (raport wrazliwości i granic nie ma sensu dla problemów
z ograniczeniami calkowitymi).
Rozwiązanie optymalne w arkuszu pokazane zostało na rysunku 9. W wierszu 8
znajdują się optymalne wartości zmiennych decyzyjnych, a w komórce F9 optymalna
wartość funkcji celu. Tak wiec optymalny plan produkcji obejmuje wyprodukowanie
3852 szt Zabawki 1 i 858 szt Zabawki 2, okazuje się ze nie opłacalne jest
produkowanie Zabawek 2 i 3. Planowany zysk wyniesie 25704 zł.
Na rysunku 10 przedstawiono raport wyników (pojawi się on w nowym arkuszu – zob.
rys. 9, na dole arkusza z rozwiazaniem). Raport ten zawiera wartości początkowe
zapisane w arkuszu i wartości optymalne: funcji celu w wierszu 8, wartość zmiennych
decyzyjnychw wierszach od 13 do 16 oraz wartość komórek zawierajacych warunki
ograniczające od wiersza 21 do 27. Wartość ograniczeń zapisana jest w kolumnie D,
formuła w kolumnie E, status ograniczenia w kolumnie F, a luz w kolumnie G. Status
ograniczenia informuje czy ograniczenie jest aktywne, napięte („Wiążące”) lub
nieaktywne, lużne („Niewiążące”).
Rys. 9 Arkusz zawierający rozwiązanie optymalne zadania
7
Rys. 10. Arkusz zawierający Raport wyników
Komunikaty Solvera w przypadku braku rozwiązania optymalnego
W przypadku gdy zadanie jest sprzeczne Solver wyświetla komunikat informujący
o tym, że nie może znaleźć zadowalającego rozwiązania (zob. rys 11).
Gdy funkcja celu jest nieograniczona to wyświetlany jest komunikat: „Ustawione”
wartości komórki celu nie są zbieżne” (zob. rys 12). Najczęściej oznacza to, że
w modelu lub w Solverze nie zostały uwzględnione wszystkie warunki ograniczające.
Rys. 11. Okno dialogowe Solver, gdy zadanie jest sprzeczne
Rys. 12. Okno dialogowe Solver, gdy funkcja celu jest nieograniczona
8
1.2. Problem mieszanek
Przykład 2. Racjonalna hodowla strusi wymaga dostarczenia miesięcznie każdej
sztuce trzech składników odżywczych: S
1
– co najmniej 28 jedn., S
2
– co najmniej
50 jedn., S
3
– co najwyżej 60 jedn. zawartych w dwóch paszach P
1
i P
2
. Niezbędne
dane zawiera tabela 2.
Tabela nr 2
Pasze
Zawartość w 1kg paszy składnika
Ceny pasz
w zł za kg
S
1
S
2
S
3
P
1
2
10
5
3
P
2
7
2,5
4
9
Ponadto wiadomo, że paszy P
1
należy dostarczyć nie mniej niż paszy P
2
. Ile należy
zakupić paszy P
1
, a ile P
2
, aby dostarczyć potrzebne składniki odżywcze przy
możliwie najniższych kosztach wyżywienia? Ile wynosi minimalny koszt
wyżywienia?
Rozwiązanie zadania rozpoczynamy od zapisania programu liniowego.
Model matematyczny
Zmienne decyzyjne:
x
1
– ilość dostarczonej paszy P
1
x
2
- ilość dostarczonej paszy P
2
Funkcja celu
Celem zadania jest zminimalizowanie kosztów wyżywienia strusi, zatem funkcja celu
będzie następująca:
min
9
3
)
,
(
2
1
2
1
→
+
=
x
x
x
x
F
Warunki ograniczające
28
7
2
2
1
≥
+
x
x
50
5
,
2
10
2
1
≥
+
x
x
60
4
5
2
1
≤
+
x
x
2
1
x
x
≥
0
,
,
,
4
3
2
1
≥
x
x
x
x
9
Zapis zadania w arkuszu Excel
Na rysunkach 13 i 14 przedstawiono arkusz z zapisanym zadaniem. Pierwszy
z rysunków zawiera dane wejściowe zapisane w postaci tabeli, drugi zawiera również
formuły obliczeniowe.
Rys. 13. Dane do zadania zapisane w arkuszu
Rys. 14. Dane do zadania zapisane w arkuszu wraz z formułami obliczeniowymi
10
Aby wyznaczyć rozwiązanie optymalne naszego zadania należy wybrać polecenie
Solver (zob. rysunek 3). Następnie w oknie dialogowym Solvera należy wprowadzić
parametry zadania (zob. rys. 15).
Rys. 15. Okno dialogowe Solvera z wprowadzonymi parametrami zadania
Ostatnie ograniczenie w oknie Solvera to ograniczenie
2
1
x
x
≥
(zob. rys. 16)
Rys. 16. Okno dialogowe opcji „Dodaj’ w Solverze
Następnie należy wybrać „Opcje” i zaznaczyć „Przyjmij nieujemne” oraz „Przyjmij
model liniowy”(zob. rys.7).
Interpretacja wyników
Po naciśnięciu przycisku „Rozwiąż” w oknie Solver, w arkuszu pojawia się
rozwiązanie zadania i wyświetlane jest okno „Solver – Wyniki” z dwoma opcjami
„Przechowaj rozwiązanie” i „Przywróć wartości początkowe” (zob. rys 17). Aby
zachować znalezione rozwiązanie należy zaznaczyć opcję „Przechowaj rozwiązanie”.
W polu Raporty należy wybrać wszystkie opcje („Wyników”, „Wrażliwości”,
„Granic”) trzymając wciśnięty klawisz Shift (zob. rys 17). Wówczas raporty pojawią
się w osobnych arkuszach.
11
Rys. 17. Okno dialogowe opcji „Solver – Wyniki” z zaznaczonymi wszystkimi raportami
Rozwiązanie optymalne w arkuszu pokazane zostało na rysunku 18. W wierszu 7
znajdują się optymalne wartości zmiennych decyzyjnych, a w komórce D8 optymalna
wartość funkcji celu. Tak więc optymalny plan dostarczenia paszy obejmuje
dostarczenie 4,31 kg paszy P
1
i 2,78 kg paszy P
2
. Minimalny koszt wyżywienia to
37,85 zł.
Rys. 18 Arkusz zawierający rozwiązanie optymalne zadania
Na rysunku 19 przedstawiono raport wyników. Raport ten zawiera wartości
początkowe zapisane w arkuszu i wartości optymalne: funcji celu w wierszu 8,
wartość zmiennych decyzyjnychw wierszach 13 i 14 oraz wartość komórek
zawierajacych warunki ograniczające od wiersza 19 do 22.
12
Rys. 19. Arkusz zawierający Raport wyników
Rysunek 20 zawiera arkusz z raportem wrażliwości. Są to rezultaty analizy
wrażliwości współczynników funkcji celu oraz wyrazów wolnych. Rezultaty te
pokazują w jakim przedziale mogą zmieniać się wartości jednego z parametrów
zadania (jeśli pozostałe parametry nie ulęgają zmianie), aby otrzymane rozwiązanie
pozostało rozwiązaniem optymalnym.
Rys. 20. Arkusz zawierający Raport wrażliwości
W komórkach od 9 do 10 przedstawione są wyniki analizy wrażliwości
współczynników funkcji celu. Analizując je można stwierdzić m.in. , że jeśli cena
paszy P
1
wrośnie nie więcej niż 33 zł lub spadnie o najwyżej 0, 43 zł to otrzymane
rozwiązanie nadal będzie optymalne. W przypadku paszy P
2
widać że cena może
wzrosnąć nie więcej niż 1,5 zł lub spaść o co najwyżej 8,25 zł. Wiersze od 15 do 18
zawierają analogiczną analizę wrażliwości wyrazów wolnych
13
Ostatni z raportów „Raport granic” (zob. rys 21) dla każdej zmiennej przedstawia
dolną i górną granicę jej wartości i odpowiadające jej wartości funkcji celu. Dolna
granica jest najmniejszą wartością, którą może przyjąć zmienna decyzyjna przy
ustalonych wartościach pozostałych zmiennych i zachowanych ograniczeniach. Górna
granica jest wartością największą jaką może przyjąć zmienna decyzyjna.
Rys. 21. Arkusz zawierający Raport granic
1.3. Problem rozkroju
Przykład 3. Punkt usługowy otrzymał zamówienie na wycięcie szyb do 300
jednakowych witraży, z tym ze na 1 witraż wchodzą 2 szyby typu s
1
i 3 szyby typu s
2
.
Szyby wycina się z jednakowych płyt szklanych i można je wycinać trzema
sposobami. Liczbę szyb i odpad powstały w procesie wycinania przedstawiono w
tabeli 3.
Tabela nr 3
Szyby
Sposoby cięcia szyb
I
II
III
s
1
6
4
3
s
2
0
4
6
Odpad (w kg)
0,6
1,6
1,2
Ile razy należy zastosować możliwe sposoby cięcia, aby odpad powstały przy cięciu
był jak najmniejszy?
Rozwiązanie:
Model matematyczny
Zmienne decyzyjne:
x
1
– ilość cięć I sposobem
x
2
– ilość cięć II sposobem
14
x
3
– ilość cięć III sposobem
Funkcja celu
Celem zadania jest zminimalizowanie odpadu powstałego przy cieciu, zatem funkcja
celu będzie następująca:
min
2
,
1
6
,
1
6
,
0
)
,
,
(
3
2
1
3
2
1
→
+
+
=
x
x
x
x
x
x
F
Warunki ograniczające
Szyby należy wyciąć do 300 witraży, przy czym na jeden witraż wchodzą 2 szyby
typu s
1
(300
•
2 = 600 szyb s
1
) i 3 szyby typu s
2
(300
•
3 = 900 szyb s
2
). Zatem:
600
3
4
6
3
2
1
=
+
+
x
x
x
900
6
4
0
3
2
1
=
+
+
x
x
x
0
,
,
3
2
1
≥
x
x
x
C
x
x
x
∈
3
2
1
,
,
Zapis zadania w arkuszu Excel
Na rysunkach 22 i 23 przedstawiono arkusz kalkulacyjny z zapisanym zadaniem.
Pierwszy z rysunków zawiera dane wejściowe zapisane w postaci tabeli, drugi zawiera
również formuły obliczeniowe.
Rys. 22. Dane do zadania zapisane w arkuszu
15
Rys. 23. Dane do zadania zapisane w arkuszu wraz z formułami obliczeniowymi
Aby wyznaczyć rozwiązanie optymalne danego zadania należy wybrać polecenie
Solver. Następnie w oknie dialogowym Solvera należy wprowadzić parametry
zadania (zob. rys. 24).
Rys. 24. Okno dialogowe Solvera z wprowadzonymi parametrami zadania
Po wprowadzeniu parametrów zadania w Solverze należy wybrać „Opcje”
i zaznaczyć „Przyjmij nieujemne” oraz „Przyjmij model liniowy” (zob. rys.7),
a następnie nacisnąć przycisk „Rozwiąż”.
Rozwiązanie optymalne w arkuszu pokazane zostało na rysunku 25. W wierszu 7
znajdują się optymalne wartości zmiennych decyzyjnych, a w komórce E8 optymalna
wartość funkcji celu. Tak więc optymalne rozwiązanie to, cięcie szyb 25 razy I
sposobem i 150 razy III sposobem. Minimalny odpad wyniesie wtedy 195 kg
.
16
Rys. 25 Arkusz zawierający rozwiązanie optymalne zadania
W analogiczny sposób jak w przykładzie 1 można również wygenerować „Raport
wyników” (zob. rys. 26).
Rys. 26. Arkusz zawierający Raport wyników
1.4. Zagadnienie transportowe.
Przykład 4. Trzy hurtownie H1, H2, H3 zaopatrują w mąkę cztery piekarnie P1,
P2, P3, P4. Jednostkowe koszty transportu (w zł za tonę), oferowane miesięczne
17
wielkości dostaw A
i
(w tonach) oraz miesięczne zapotrzebowanie cukierni B
j
(w tonach) zawiera tabela nr 4. Opracować plan przewozu mąki z hurtowni do piekarni
minimalizujący całkowite koszty transportu.
Tabela nr 4
Hurtownie
Piekarnie
A
i
C1
C2
C3
C4
H1
50
40
50
20
70
H2
40
80
70
30
50
H3
60
40
70
80
80
B
j
40
60
50
50
200
Model matematyczny
Przykład 4 jest zamkniętym zadaniem transportowym, ponieważ
∑
∑
=
=
=
=
4
1
3
1
200
j
j
i
i
B
A
Zmienne decyzyjne:
x
ij
– ilość ton mąki, która powinna być dostarczona z i-tej hurtowni (i = 1, 2, 3) do j-tej
piekarni (j = 1, 2, 3, 4)
Zmiennych decyzyjnych jest 12 (3
•
4 = 12)
Funkcja celu
Celem zadania jest zminimalizowanie łącznych kosztów transportu, zatem funkcja
celu będzie następująca:
min
80
70
40
60
30
70
80
40
20
50
40
50
)
(
34
33
32
31
24
23
22
21
14
13
12
11
→
+
+
+
+
+
+
+
+
+
+
+
=
x
x
x
x
x
x
x
x
x
x
x
x
x
F
ij
Warunki ograniczające
Ponieważ jest to zagadnienie transportowe zamknięte, dostawcy sprzedadzą całą ilość
oferowanego towaru, a zapotrzebowania piekarń zostaną zaspokojone w całości.
Mamy, zatem następujące warunki ograniczające:
a)
dla dostawców (hurtowni)
70
14
13
12
11
=
+
+
+
x
x
x
x
50
24
23
22
21
=
+
+
+
x
x
x
x
80
34
33
32
31
=
+
+
+
x
x
x
x
18
b)
dla odbiorców (piekarni)
40
31
21
11
=
+
+
x
x
x
60
32
22
12
=
+
+
x
x
x
50
33
23
13
=
+
+
x
x
x
50
34
24
14
=
+
+
x
x
x
Ponadto
0
4
≥
ij
x
Zapis zadania w arkuszu Excel
Na rysunkach 27 i 28 przedstawiono arkusz kalkulacyjny z zapisanym zadaniem.
Pierwszy z rysunków zawiera dane wejściowe zapisane w postaci tabeli, drugi zawiera
również formuły obliczeniowe.
Rys. 27. Dane do zadania zapisane w arkuszu
19
Rys. 28. Dane do zadania zapisane w arkuszu wraz z formułami obliczeniowymi
W celu wyznaczenia rozwiązania optymalnego danego zadania należy wybrać
polecenie Solver. Następnie w oknie dialogowym Solvera należy wprowadzić
parametry zadania (zob. rys. 29).
Rys. 29. Okno dialogowe Solvera z wprowadzonymi parametrami zadania
Po wprowadzeniu parametrów zadania w Solverze należy wybrać „Opcje”
i zaznaczyć „Przyjmij nieujemne” oraz „Przyjmij model liniowy” (zob. rys.7),
a następnie nacisnąć przycisk „Rozwiąż”.
Rozwiązanie optymalne w arkuszu pokazane zostało na rysunku 30. W wierszach od 8
do 10 znajdują się optymalne wartości zmiennych decyzyjnych, a w komórce A12
optymalna wartość funkcji celu. Tak więc optymalne rozwiazanie to dostarczenie 30
20
ton mąki z H1 do P3 (x
13
= 30), 40 ton mąki z H1 do P4 (x
14
= 40), 40 ton mąki z H2
do P1 (x
21
= 40), 10 ton mąki z H2 do P4 (x
24
= 10), 60 ton mąki z H3 do P2
(x
32
= 60), 20 ton mąki z H3 do P3 (x
33
= 20). Minimalny łączny koszt transportu maki
z hurtownii do piekarni wynosi 8000 zł.
Rys. 30. Arkusz zawierający rozwiązanie optymalne zadania
Podobnie jak w przykładzie 2 w polu Raporty można wybrać wszystkie raporty
(„Wyników”, „Wrażliwości”, „Granic”). Pojawią się one się w osobnych arkuszach.