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?
1
 Tabela nr 1
Jednostkowe zużycie środków produkcji
Środki 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
0,2 0,4 0,3 0,5
elektryczna(kWh/szt)
Rozwiązanie zadania rozpoczynamy od zapisania programu liniowego.
Model matematyczny
Zmienne decyzyjne:
x1  planowana wielkość produkcji zabawek 1
x2 - planowana wielkość produkcji zabawek 2
x3 - planowana wielkość produkcji zabawek 3
x4 - 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:
F(x1, x2, x3, x4 ) = 4x1 + 6x2 + 3x3 +12x4 max
Warunki ograniczające
x1 + 2x2 +1,5x3 + 6x4 d" 9000
2x1 + 2x2 +1,5x3 + 4x4 d"12000
0,2x1 + 0,4x2 + 0,3x3 + 0,5x4 d"1200
x1, x2, x3, x4 e" 0
x1, x2, x3, x4 "C
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.
2
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
3
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
4
Po wprowadzeniu wszystkich ograniczeń należy przycisnąć przycisk  OK
i wrócić do okna dialogowego Solvera. Następnie należy wybrać  Opcje i zaznaczyć
x1, x2, x3, x4 e" 0
 Przyjmij nieujemne (zmienne decyzyjne mają być nieujemne: )
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
5
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
6
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 znalez
ć 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
7
1.2. Problem mieszanek
Przykład 2. Racjonalna hodowla strusi wymaga dostarczenia miesięcznie każdej
sztuce trzech składników odżywczych: S1  co najmniej 28 jedn., S2  co najmniej
50 jedn., S3  co najwyżej 60 jedn. zawartych w dwóch paszach P1 i P2. Niezbędne
dane zawiera tabela 2.
Tabela nr 2
Zawartość w 1kg paszy składnika Ceny pasz
Pasze
S1 S2 S3 w zł za kg
P1 2 10 5 3
P2 7 2,5 4 9
Ponadto wiadomo, że paszy P1 należy dostarczyć nie mniej niż paszy P2. Ile należy
zakupić paszy P1, a ile P2, 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:
x1  ilość dostarczonej paszy P1
x2 - ilość dostarczonej paszy P2
Funkcja celu
Celem zadania jest zminimalizowanie kosztów wyżywienia strusi, zatem funkcja celu
będzie następująca:
F(x1, x2 ) = 3x1 + 9x2 min
Warunki ograniczające
2x1 + 7x2 e" 28
10x1 + 2,5x2 e" 50
5x1 + 4x2 d" 60
x1 e" x2
x1, x2, x3, x4 e" 0
8
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
9
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
x1 e" x2
Ostatnie ograniczenie w oknie Solvera to ograniczenie (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.
10
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 P1 i 2,78 kg paszy P2. 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.
11
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 P1 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 P2 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
12
 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 s1 i 3 szyby typu s2.
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
Sposoby cięcia szyb
Szyby
I II III
s1 6 4 3
s2 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:
x1  ilość cięć I sposobem
x2  ilość cięć II sposobem
13
x3  ilość cięć III sposobem
Funkcja celu
Celem zadania jest zminimalizowanie odpadu powstałego przy cieciu, zatem funkcja
celu będzie następująca:
F(x1, x2, x3) = 0,6x1 +1,6x2 +1,2x3 min
Warunki ograniczające
Szyby należy wyciąć do 300 witraży, przy czym na jeden witraż wchodzą 2 szyby
typu s1 (300 " 2 = 600 szyb s1) i 3 szyby typu s2 (300 " 3 = 900 szyb s2). Zatem:
6x1 + 4x2 + 3x3 = 600
0x1 + 4x2 + 6x3 = 900
x1, x2, x3 e" 0
x1, x2, x3 "C
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
14
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
.
15
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
16
wielkości dostaw Ai (w tonach) oraz miesięczne zapotrzebowanie cukierni Bj
(w tonach) zawiera tabela nr 4. Opracować plan przewozu mąki z hurtowni do piekarni
minimalizujący całkowite koszty transportu.
Tabela nr 4
Piekarnie
Hurtownie Ai
C1 C2 C3 C4
H1 50 40 50 20 70
H2 40 80 70 30 50
H3 60 40 70 80 80
Bj 40 60 50 50 200
Model matematyczny
3 4
= = 200
Przykład 4 jest zamkniętym zadaniem transportowym, ponieważ
"Ai "Bj
i=1 j=1
Zmienne decyzyjne:
xij  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:
F(xij ) = 50x11 + 40x12 + 50x13 + 20x14 + 40x21 + 80x22 + 70x23 + 30x24 +
60x31 + 40x32 + 70x33 + 80x34 min
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)
x11 + x12 + x13 + x14 = 70
x21 + x22 + x23 + x24 = 50
x31 + x32 + x33 + x34 = 80
17
b) dla odbiorców (piekarni)
x11 + x21 + x31 = 40
x12 + x22 + x32 = 60
x13 + x23 + x33 = 50
x14 + x24 + x34 = 50
Ponadto
xij 4 e" 0
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
18
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
19
ton mąki z H1 do P3 (x13 = 30), 40 ton mąki z H1 do P4 (x14 = 40), 40 ton mąki z H2
do P1 (x21 = 40), 10 ton mąki z H2 do P4 (x24 = 10), 60 ton mąki z H3 do P2
(x32 = 60), 20 ton mąki z H3 do P3 (x33 = 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.
20