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.