Programowanie liniowe
Witold Jurek
Przykład
Zakład krawiecki szyje sukienki i spodnie. Przy szyciu spodni
i sukienek zakład wykorzystuje dwa  zasoby : materiał, siłę
roboczą. Na wykonanie pary spodni potrzeba 2 m materiału
oraz 8 roboczogodzin; na uszycie sukienki potrzeba 3 m
materiału i 2 roboczogodziny. Na szycie spodni i sukienek
zakład może wykorzystać 60 m materiału i 80 roboczogodzin.
Ze sprzedaży wyrobów zakład otrzymuje 180 zł za sukienkę
oraz 320 zł za spodnie.
1. Ustalić plan produkcji zakładu, przy którym przychód ze
sprzedaży uszytych wyrobów będzie maksymalny.
W.J. Programowanie liniowe 2
Przykład. Zadanie programowania
liniowego (ZPL)
Zmienne:
- liczba uszytych sukienek
xsp - liczba uszytych spodni
Zadanie
W.J. Programowanie liniowe 3
1
Elementy zadania programowania
liniowego (ZPL)
1. Zmienne (decyzyjne), parametry zadania
2. Warunki ograniczające, ograniczenia
1. Warunki brzegowe
3. Funkcja kryterium, funkcja celu
W.J. Programowanie liniowe 4
ZPL. Przypadek ogólny
Funkcja kryterium (funkcja celu)
5�P�15�e�1 + 5�P�25�e�2 + & + 5�P�5�[� 5�e�5�[� 5�Z�5�N�5�e�
Warunki ograniczające (ograniczenia)
5�N�115�e�1 + 5�N�125�e�2 + & + 5�N�15�[� 5�e�5�[� d" 5�O�1
5�N�215�e�1 + 5�N�225�e�2 + & + 5�N�25�[� 5�e�5�[� d" 5�O�2
& & & & & & & & & & & ..
5�N�5�Z�15�e�1 + 5�N�5�Z�25�e�2 + & + 5�N�5�Z�5�[� 5�e�5�[� d" 5�O�5�Z�
Warunki brzegowe
5�e�1, 5�e�2, & , 5�e�5�[� e" 0
W.J. Programowanie liniowe 5
ZPL. Zapis macierzowy
Macierz parametrów
5�N�11 5�N�12 & 5�N�15�[� 5��1.
5�N�21 5�N�22 & 5�N�25�[� 5��2. 5�� 5�� & 5��
5�� = = = .1 .2 .5�[�
& & & & &
5�N�5�Z�1 5�N�5�Z�2 & 5�N�5�Z�5�[� 5��5�Z�.
Wektor zmiennych decyzyjnych Wektor wyrazów wolnych
5�e�1
5�O�1
5�e�2
5�O�2
5�1� = 5�� =
&
&
5�e�5�[�
5�O�5�Z�
Wektor parametrów funkcji kryterium
5�P�1 5�P�2 & 5�P�5�[�
5�� =
W.J. Programowanie liniowe 6
2
Przykład ZPL. Zapis macierzowy
5ؙ�5�"�5�
� 5���5���
5�� 5���
5�� = 5�1� = 5�� =
5ؙ�5�"�5�ę� 5���5���
5��� 5���
5�� = 5���5���5��� 5��5���5���
Przykładowe zadanie w zapisie macierzowym
cx max
Ax d" b
x e" 0
Jest to ZPL o postaci standardowej
W.J. Programowanie liniowe 7
Zbiór wypukły
Zbiór A jest wypukły, jeżeli dla dowolnych elementów
a1, a2 �� A i dowolnej liczby l� �� [0 , 1] element
l�a1 +� (1-� l�)a2 �� A
Zbiór wartości zmiennych decyzyjnych spełniających
warunki ograniczające ZPL nazywamy zbiorem rozwiązań
dopuszczalnych ZPL
Zbiór rozwiązań dopuszczalnych ZPL jest wypukły.
W.J. Programowanie liniowe 8
Przykład. Zadanie programowania
liniowego (ZPL)
Zmienne:
- liczba uszytych sukienek
xsp - liczba uszytych spodni
Zadanie
W.J. Programowanie liniowe 9
3
Metoda geometryczna.
Zadanie pierwotne
Zbiór rozwiązań dopuszczalnych ZPL
W.J. Programowanie liniowe 10
Solver. Raport wyników
Komórka celu (Maks)
Wartość
Komórka Nazwa początkowa Wartość końcowa
$G$7 4800 4800
Komórki zmiennych
Wartość
Komórka Nazwa początkowa Wartość końcowa Całkowite
$D$6 xsu 16 16 Ciągłe
$E$6 xsp 6 6 Ciągłe
Ograniczenia
Wartość Zapas
Komórka Nazwa komórki Formuła Stan czasu
$F$10 80 $F$10<=$G$10 Wiążące 0
$F$9 60 $F$9<=$G$9 Wiążące 0
W.J. Programowanie liniowe 11
Postaci ZPL
Postać Postać
standardowa kanoniczna
cx ��max (albo min) cx ��max (albo min)
Ax Ł� b (albo ł�) Ax = b
x ł� 0 x ł� 0
W.J. Programowanie liniowe 12
4
Zmienne swobodne
Jeżeli
5��5؊�.5�1� d" 5�O�5؊� to 5�`�5؊� = 5�O�5؊� - 5��5؊�.5�1� oraz 5�`�5�V� e" 0
Jeżeli
5��5؊�.5�1� e" 5�O�5؊� to 5�`�5؊� = 5��5؊�.5�1� - 5�O�5؊� oraz 5�`�5�V� e" 0
Uwaga
Zmienne swobodne mają zerowe wagi (parametry) w funkcji
kryterium (celu)
W.J. Programowanie liniowe 13
Postać standardowa i kanoniczna ZPL
1. Przy ewentualnym użyciu zmiennych swobodnych każde
zadanie programowania liniowego można przedstawić w
postaci kanonicznej.
2. Zapisując ewentualne równanie jako układ dwóch
nierówności (przeciwnie skierowanych) każde zadanie
programowania liniowego można przedstawić w postaci
standardowej.
W.J. Programowanie liniowe 14
Przykład. Zadanie o postaci kanonicznej
Zmienne swobodne
5�`�5�Z� = 60 - 35�e�5�`�5�b� - 25�e�5�`�5�]�
5�`�5�_� = 80 - 25�e�5�`�5�b� - 85�e�5�`�5�]�
Przykładowe zadanie o postaci kanonicznej
1805�e�5�`�5�b� + 3205�e�5�`�5�]� 5�Z�5�N�5�e�
35�e�5�`�5�b� + 25�e�5�`�5�]� + 5�`�5�Z� = 60
25�e�5�`�5�b� + 85�e�5�`�5�]� + 5�`�5�_� = 80
5�e�5�`�5�b� , 5�e�5�`�5�]� , 5�`�5�Z� , 5�`�5�_� e" 0
W.J. Programowanie liniowe 15
5
Zadania dualne względem siebie
Zadanie pierwotne (I) Zadanie dualne (I)
Zadanie pierwotne (II) Zadanie dualne (II)
yb �� max
c1x1 +� c2x2 �� min
A1x1 +� A2x2 =� b yA1 Ł� c1
x1 ł� 0 yA2 =� c2
W.J. Programowanie liniowe 16
Cechy zadań dualnych względem siebie
Wyrazy wolne zadania pierwotnego są wagami funkcji
kryterium (funkcji celu) zadania dualnego
Wagi funkcji kryterium (funkcji celu) zadania pierwotnego
są wyrazami wolnymi ograniczeń zadania dualnego
Zadanie dualne ma tyle zmiennych ile ograniczeń (równań)
ma zadanie pierwotne
Zadanie dualne ma tyle ograniczeń (nierówności) ile
zmiennych nieujemnych ma zadanie pierwotne
Zadanie dualne ma tyle ograniczeń (równań) ile zmiennych
o dowolnym znaku ma zadanie pierwotne
W.J. Programowanie liniowe 17
Przykład. Zadanie o postaci kanonicznej
Przykładowe zadanie o postaci kanonicznej
1805�e�5�`�5�b� + 3205�e�5�`�5�]� 5�Z�5�N�5�e�
35�e�5�`�5�b� + 25�e�5�`�5�]� + 5�`�5�Z� = 60
25�e�5�`�5�b� + 85�e�5�`�5�]� + 5�`�5�_� = 80
5�e�5�`�5�b� , 5�e�5�`�5�]� , 5�`�5�Z� , 5�`�5�_� e" 0
Wektor wag funkcji celu: 5�� = 180 320 0 0
3 2 1 0
Macierz współczynników: 5�� =
2 8 0 1
5�f�5�Z� 5�f�5�_�
Zmienne dualne: 5�f�5�Z�, 5�f�5�_� ; 5�2� =
W.J. Programowanie liniowe 18
6
Przykładowe zadanie dualne
5�f�5�Z� 5�f�5�_�
Zmienne dualne: 5�f�5�Z�, 5�f�5�_� ; 5�2� =
Zadanie:
605�f�5�Z� + 805�f�5�_� 5�Z�5�V�5�[�
35�f�5�Z� + 25�f�5�_� e" 180
25�f�5�Z� + 85�f�5�_� e" 320
5�f�5�Z� , 5�f�5�_� e" 0
Uwaga. Otrzymane zadanie jest ZPL o postaci standardowej
W.J. Programowanie liniowe 19
Przykład c.d.
2. Rozwiązać zadanie dualne do zadania z punktu 1.
(Zadanie, w którym zmiennymi decyzyjnymi będą ceny
1 m materiału i 1 roboczogodziny).
3. Co stałoby się z przychodem zakładu, gdyby miał on o
10 m materiału więcej?
W.J. Programowanie liniowe 20
Metoda geometryczna.
Zadanie dualne
100
5�f�_5�_�
80
60
5�f�_5�Z�^0=40; 5�f�_5�_�
40 ^0=30
20
5�f�_5�Z�
0
0 10 20 30 40 50 60 70 80
-20
-40
W.J. Programowanie liniowe 21
7
Solver. Raport wyników
Komórka celu (Min)
Wartość Wartość
Komórka Nazwa początkowa końcowa
$G$16 0 4800
Komórki zmiennych
Wartość Wartość Całkowit
Komórka Nazwa początkowa końcowa e
$D$15 ym 0 40 Ciągłe
$E$15 yr 0 30 Ciągłe
Ograniczenia
Wartość Zapas
Komórka Nazwa komórki Formuła Stan czasu
$F$18 180 $F$18>=$G$18 Wiążące 0
$F$19 320 $F$19>=$G$19 Wiążące 0
W.J. Programowanie liniowe 22
Solver. Raport wyników
Komórka celu (Maks)
Wartość
Komórka Nazwa początkowa Wartość końcowa
$G$7 4800 4800
Komórki zmiennych
Wartość
Komórka Nazwa początkowa Wartość końcowa Całkowite
$D$6 xsu 16 16 Ciągłe
$E$6 xsp 6 6 Ciągłe
Ograniczenia
Wartość Zapas
Komórka Nazwa komórki Formuła Stan czasu
$F$10 80 $F$10<=$G$10 Wiążące 0
$F$9 60 $F$9<=$G$9 Wiążące 0
W.J. Programowanie liniowe 23
Twierdzenia programowania liniowego
Rozważamy parę następujących zadań:
zadanie pierwotne zadanie dualne
cx �� max yb �� min
Ax Ł� b yA ł� c
x ł� 0 y ł� 0
Twierdzenie 1
Niech P oznacza zbiór rozwiązań dopuszczalnych zadania
pierwotnego, a D zbiór rozwiązań dopuszczalnych zadania
dualnego. Dla każdego x �� P oraz dla każdego y �� D
zachodzi cx Ł� yb.
W.J. Programowanie liniowe 24
8
Szkic dowodu twierdzenia 1
Warunki ograniczające ZPL dualnych względem siebie:
Ax d" b yA e" c
tak więc
yAx d" yb yAx e" cx
Z obu tych nierówności wynika nierówność podwójna
cx d" yAx d" yb
W.J. Programowanie liniowe 25
Twierdzenia programowania liniowego
Twierdzenie 2
Jeżeli istnieją takie �� P oraz takie �� D, że
to jest rozwiązaniem optymalnym zadania pierwotnego, a
jest rozwiązaniem optymalnym zadania dualnego.
Twierdzenie 3
Jeżeli dodanie jedynki do i-tego wyrazu wolnego zadania pier-
wotnego nie zmienia rozwiązania zadania dualnego, to przyrost
wartości funkcji celu (zadania pierwotnego, zadania dualnego)
jest równy wartości optymalnej, , zmiennej dualnej.
W.J. Programowanie liniowe 26
Twierdzenia programowania liniowego
Twierdzenie 4
Na to, by �� P było rozwiązaniem optymalnym zadania
pierwotnego, a �� D było rozwiązaniem optymalnym
zadania dualnego potrzeba i wystarcza, by spełnione były
następujące warunki:
oraz
W.J. Programowanie liniowe 27
9
Szkic dowodu twierdzenia 4
Z dowodu twierdzenia 1 wynika, że dla rozwiązań
optymalnych, 5�1�0, 5�2�0, zachodzi
5��5�1�0 = 5�2�05��5�1�5��� = 5�2�5���5��
Rozważmy równania
5��5�1�0 = 5�2�05��5�1�5��� 5�2�05��5�1�5��� = 5�2�5���5��
5�� - 5�2�05�� 5�1�5��� = 0 5�2�0 5��5�1�5��� - 5�� = 0
5�[� 5�Z�
5�P�5�W� - 5�2�05��.5�W� 5�e�5�W�0 = 0 5�f�5�V�0 5��5�V�.5�1�0 - 5�O�5�V� = 0
5�W� =1 5�V�=1
W.J. Programowanie liniowe 28
Szkic dowodu twierdzenia 4 c.d.
Z ostatnich równań wynika, że następujące iloczyny są równe
zeru
0
(1) 5�P�5�W� - 5�2�05�� 5�e�5�W� = 0 dla j =1,2,& ,n
.5�W�
(2) 5�f�5�V�0 5��5�V�.5�1�0 - 5�O�5�V� = 0 dla i = 1,2,& ,m
ponieważ:
0
(1) czynniki 5�P�5�W� - 5�2�05�� , 5�e�5�W� iloczynów 1 mają te same
.5�W�
znaki dla j =1,2,& ,n
(2) iloczynów 5�f�5�V�0, 5��5�V�.5�1�0 - 5�O�5�V� iloczynów (2) mają te same
znaki dla i = 1,2,& ,m
W.J. Programowanie liniowe 29
Rozwiązanie bazowe
Niech będzie dany układ m równań o n niewiadomych, przy
czym m Ł� n. Rozwiązanie bazowe jest otrzymywane w
następujący sposób:
(a) n  m zmiennym nadawane są wartości zerowe,
tak, aby macierz współczynników przy pozostałych
(niewyzerowanych) zmiennych była nieosobliwa,
(b) wartości pozostałych zmiennych wyznaczane są
poprzez rozwiązanie powstałego układu m równań o m
niewiadomych.
W.J. Programowanie liniowe 30
10
Własności rozwiązania bazowego
Nieosobliwa macierz współczynników przy
niewyzerowanych zmiennych nosi nazwę bazy rozwiązania.
Jeżeli wszystkie macierze współczynników przy
niewyzerowanych zmiennych są nieosobliwe, to dany układ
równań ma rozwiązań bazowych.
W.J. Programowanie liniowe 31
Rozwiązania bazowe. Przykład
Układ ograniczeń przykładowego ZPL o postaci kanonicznej
Jest to układ 2 równań o 4 niewiadomych. Jeśli wszystkie
macierze bazowe są nieosobliwe, to układ równań ma 6
rozwiązań bazowych.
W.J. Programowanie liniowe 32
Rozwiązanie bazowe. Przykład
Rozwiązania bazowe
Rozwiązania bazowe odpowiadają punktom przecięcia na wykresie ze
zbiorem rozwiązań dopuszczalnych ZPL.
Punkty przecięcia należą bądz
nie do zbioru rozwiązań dopuszczalnych
W.J. Programowanie liniowe 33
11
Rozwiązania bazowe. Przykład
Zbiór rozwiązań dopuszczalnych przykładowego ZPL
40
x_sp
30
(0,30)
20
10
(16,6)
0
0 10 20 30 40
x_su
(0,0)
-10
-20
-30
W.J. Programowanie liniowe 34
Elementy algorytmu simpleks
Rozwiązywane jest zadanie o postaci kanonicznej
Dane jest rozwiązanie bazowe układu warunków
ograniczających (równań)
W.J. Programowanie liniowe 35
Elementy algorytmu simpleks
Kryteria simpleks
Wartości zmiennych bazowych
Wartość funkcji kryterium
Kryterium wprowadzania zmiennej do rozwiązania bazowego
(kryteria simpleks)
W.J. Programowanie liniowe 36
12
Przykład. Zadanie o postaci kanonicznej
Przykładowe zadanie o postaci kanonicznej
1805�e�5�`�5�b� + 3205�e�5�`�5�]� 5�Z�5�N�5�e�
35�e�5�`�5�b� + 25�e�5�`�5�]� + 5�`�5�Z� = 60
25�e�5�`�5�b� + 85�e�5�`�5�]� + 5�`�5�_� = 80
5�e�5�`�5�b� , 5�e�5�`�5�]� , 5�`�5�Z� , 5�`�5�_� e" 0
W.J. Programowanie liniowe 37
Elementy algorytmu simpleks
Przykładowe kryteria simpleks
Analizowane rozwiązania bazowe dopuszczalne
Rozwiązanie bazowe I
5�`�5�Z� 5�e�5�`�5�b�
5�1�5�5� = 5�1�5�A� =
5�`�5�_� 5�e�5�`�5�]�
1 0 3 2
5�
� = 5� � = 5��5�5� = 5��5�A� =
0 0 180 320
0 1 2 8
5��5�A� - 5��5�5�5�
�-15� � = 180 320
W.J. Programowanie liniowe 38
Elementy algorytmu simpleks
Przykładowe kryteria simpleks
Rozwiązanie bazowe III
5�e�5�`�5�]� 5�e�5�`�5�b�
5�1�5�5� = 5�1�5�A� =
5�`�5�Z� 5�`�5�_�
2 1 3 0
5�
� = 5� � = 5��5�5� = 5��5�A� =
320 0 180 0
8 0 2 1
5��5�A� - 5��5�5�5�
�-15� � = -40
100
W.J. Programowanie liniowe 39
13
Elementy algorytmu simpleks
Przykładowe kryteria simpleks
Rozwiązanie bazowe IV
5�e�5�`�5�b� 5�e�5�`�5�]�
5�1�5�5� = 5�1�5�A� =
5�`�5�_� 5�`�5�Z�
3 0 2 1
5�
� = 5� � = 5��5�5� = 5��5�A� =
180 0 320 0
2 1 8 0
5��5�A� - 5��5�5�5�
�-15� � = -60
200
W.J. Programowanie liniowe 40
Elementy algorytmu simpleks
Przykładowe kryteria simpleks
Rozwiązanie bazowe VI
5�e�5�`�5�b� 5�`�5�Z�
5�1�5�5� = 5�1�5�A� =
5�e�5�`�5�]� 5�`�5�_�
3 2 1 0
5�
� = 5� � = 5��5�5� = 180 320 0 0
5��5�A� =
2 8 0 1
5��5�A� - 5��5�5�5�
�-15� � = -40 -30
W.J. Programowanie liniowe 41
Elementy algorytmu simpleks. Usuwanie
zmiennej z rozwiązania bazowego
Kryteria usuwania zmiennej z rozwiązania bazowego
przy czym j jest numerem zmiennej wprowadzanej, a
elementem macierzy
W.J. Programowanie liniowe 42
14
Simpleks. Przykład.
Rozwiązanie bazowe 1 (I)
Wprowadzana zmienna , usuwana zmienna
W.J. Programowanie liniowe 43
Simpleks. Przykład.
Rozwiązanie bazowe 2 (III)
Wprowadzana zmienna , usuwana zmienna
W.J. Programowanie liniowe 44
Simpleks. Przykład.
Rozwiązanie bazowe 3 (VI)
Rozwiązanie optymalne
W.J. Programowanie liniowe 45
15
Przykład. Zadanie o postaci kanonicznej
Przykładowe zadanie o postaci kanonicznej
1805�e�5�`�5�b� + 3205�e�5�`�5�]� 5�Z�5�N�5�e�
35�e�5�`�5�b� + 25�e�5�`�5�]� + 5�`�5�Z� = 60
25�e�5�`�5�b� + 85�e�5�`�5�]� + 5�`�5�_� = 80
5�e�5�`�5�b� , 5�e�5�`�5�]� , 5�`�5�Z� , 5�`�5�_� e" 0
W.J. Programowanie liniowe 46
Raport wyników
Komórka celu (Maks)
Wartość Wartość
Komórka Nazwa początkowa końcowa
$I$7 FC 0 4800
Komórki zmiennych
Wartość Wartość Całkowit
Komórka Nazwa początkowa końcowa e
$D$6 xsu 0 16 Ciągłe
$E$6 xsp 0 6 Ciągłe
$F$6 sm 60 0 Ciągłe
$G$6 sr 80 0 Ciągłe
Ograniczenia
Zapas
Komórka Nazwa Wartość komórki Formuła Stan czasu
$H$10 80 $H$10=$I$10 Wiążące 0
$H$9 60 $H$9=$I$9 Wiążące 0
W.J. Programowanie liniowe 47
Raport wrażliwości
Komórki zmiennych
Końcowa Koszt Współczynnik Dopuszczalny Dopuszczalny
Komórka Nazwa wartość zmniejszony funkcji celu wzrost spadek
$D$6 xsu 16 0 180 300 100
$E$6 xsp 6 0 320 400 200
$F$6 sm 0 -40 0 40 1E+30
$G$6 sr 0 -30 0 30 1E+30
Ograniczenia
Końcowa Cena Prawa strona Dopuszczalny Dopuszczalny
Komórka Nazwa wartość dualna ograniczenia wzrost spadek
$H$10 80 30 80 160 40
$H$9 60 40 60 60 40
W.J. Programowanie liniowe 48
16
Raport granic
Współczynnik
Komórka Nazwa wartość
$I$7 4800
Zmienna Dolna Współczynnik Górna Współczynnik
Komórka Nazwa wartość granica Wynik granica Wynik
$D$6 xsu 16 16 4800 16 4800
$E$6 xsp 6 6 4800 6 4800
$F$6 sm 0 0 4800 0 4800
$G$6 sr 0 0 4800 0 4800
W.J. Programowanie liniowe 49
Analiza wrażliwości
Wyraz wolny pierwszego równania: wzrost o 50 (mniej niż
maksymalny wzrost w raporcie wrażliwości)
Komórki zmiennych
Wartość Wartość
Komórka Nazwa Całkowite
początkowa końcowa
$D$6 xsu 0 36 Ciągłe
$E$6 xsp 0 1 Ciągłe
$F$6 sm 0 0 Ciągłe
$G$6 sr 0 0 Ciągłe
Ograniczenia
Wartość Zapas
Komórka Nazwa Formuła Stan
komórki czasu
$H$10 80 $H$10=$I$10 Wiążące 0
$H$9 110 $H$9=$I$9 Wiążące 0
W.J. Programowanie liniowe 50
Analiza wrażliwości
Wyraz wolny pierwszego równania: wzrost o 70 (więcej niż
maksymalny wzrost w raporcie wrażliwości)
Komórki zmiennych
Wartość Wartość
Komórka Nazwa Całkowite
początkowa końcowa
$D$6 xsu 0 40 Ciągłe
$E$6 xsp 0 0 Ciągłe
$F$6 sm 0 10 Ciągłe
$G$6 sr 0 0 Ciągłe
Ograniczenia
Wartość
Komórka Nazwa Formuła Stan Zapas czasu
komórki
$H$10 80 $H$10=$I$10Wiążące 0
$H$9 130 $H$9=$I$9 Wiążące 0
W.J. Programowanie liniowe 51
17
Analiza wrażliwości
Wyraz wolny pierwszego równania: wzrost o 60 (dokładnie o
maksymalny wzrost w raporcie wrażliwości)
Komórki zmiennych
Wartość Wartość
Komórka Nazwa Całkowite
początkowa końcowa
$D$6 xsu 0 40 Ciągłe
$E$6 xsp 0 0 Ciągłe
$F$6 sm 0 0 Ciągłe
$G$6 sr 0 0 Ciągłe
Ograniczenia
Końcowa Cena Prawa strona Dopuszczalny Dopuszczalny
Komórka Nazwa wartość dualna ograniczenia wzrost spadek
$H$10 80 30 80 400 0
$H$9 120 40 120 0 100
W.J. Programowanie liniowe 52
Przykład ZPL
Pewna firma produkuje 4 wyroby (WA, WB, WC, WD), wykorzys-
tując w tym celu dwa limitowane zasoby: energię elektryczną i pe-
wien surowiec. Na uzyskanie jednostki wyrobu WA potrzeba
100KWh energii oraz 2t surowca. Wykonanie jednostki wyrobu
WB wymaga zużycia 150 KWh energii oraz 5t surowca. Jed-
nostkowe nakłady na wytworzenie wyrobu WC wynoszą 150 KWh
energii oraz 1t surowca, a jednostkowe nakłady na wykonanie
wyrobu WD wynoszą 500 KWh energii i 4t surowca.
Sformułować ZPL, umożliwiające znalezienie optymalnego planu
produkcji, wiedząc, że zakład może zużyć co najwyżej 40.000
KWH oraz 300t surowca. Przychód jednostkowy z tytułu sprzedaży
wyrobów jest następujący: odpowiednio: 15, 4, 12 i 5 zł.
W.J. Programowanie liniowe 53
ZPL
Zmienne decyzyjne
5�e�5�4�, 5�e�5�5�, 5�e�5�6�, 5�e�5�7� - ilości wyrobów: WA, WB, WC, WD
Zadanie
155�e�5�4� + 45�e�5�5� + 125�e�5�6� + 55�e�5�7� 5�Z�5�N�5�e�
1005�e�5�4� + 1505�e�5�5� + 1505�e�5�6� + 5005�e�5�7� d" 40000
25�e�5�4� + 55�e�5�5� + 5�e�5�6� + 45�e�5�7� d" 300
5�e�5�4�; 5�e�5�5�; 5�e�5�6�; 5�e�5�7� e" 0
W.J. Programowanie liniowe 54
18
Raport wyników
Komórka celu (Maks)
Komór Wartość Wartość
ka Nazwa początkowa końcowa
$J$9 FC 0 3900
Komórki zmiennych
Komór Wartość Wartość
ka Nazwa początkowa końcowa Całkowite
$F$8 WA 0 100 Ciągłe
$G$8 WB 0 0 Ciągłe
$H$8 WC 0 200 Ciągłe
$I$8 WD 0 0 Ciągłe
Ograniczenia
Komór Wartość
ka Nazwa komórki Formuła Stan Zapas czasu
$J$11 FC 40000 $J$11<=$K$11 Wiążące 0
$J$12 FC 400 $J$12<=$K$12 Wiążące 0
W.J. Programowanie liniowe 55
Raport wrażliwości
Komórki zmiennych
Kom Naz Koń- Koszt Współczyn Dopusz Dopusz
órka wa cowa zmniej nik czalny czalny
wartość szony funkcji celu wzrost spadek
$F$8 WA 100 0 15 9 7
$G$8 WB 0 -29 4 29 1E+30
$H$8 WC 200 0 12 10,5 4,5
$I$8 WD 0 -38,5 5 38,5 1E+30
Ograniczenia
Kom Naz Koń Cena Prawa Dopusz Dopusz
órka wa cowa dualna strona czalny czalny
wartość ograniczenia wzrost spadek
$J$11 FC 40000 0,045 40000 20000 20000
$J$12 FC 400 5,25 400 400 133,333
W.J. Programowanie liniowe 56
Zadanie transportowe
W 2 magazynach znajduje się pewien towar w ilości 10 i 7
jedn. Towar ten należy dostarczyć do 3 sklepów, które
zamówiły go w ilości 4, 5 oraz 8 jedn. Koszty przewozu
jednostki towaru z magazynów do sklepów zawiera tabela.
Sklep 1 Sklep 2 Sklep 3
Magazyn 1 3 2 1
Magazyn 2 4 2 3
Ile towaru, z którego magazynu i do którego sklepu należy
przewiez
ć, aby łączny koszt przewozu był jak najmniejszy?
W.J. Przykłady ZPL 57
19
Zadanie transportowe
Sformułowanie zadania
Zmienne decyzyjne: 5�e�5�V�5�W� - przewóz towaru z i  tego (i = 1,2)
magazynu do j  tego (j = 1, 2, 3) sklepu
Zadanie
35�e�11 + 25�e�12 + 5�e�13 + 45�e�21 + 25�e�22 + 35�e�23 5�Z�5�V�5�[�
5�e�11 + 5�e�12 + 5�e�13 = 10
5�e�21 + 5�e�22 + 5�e�23 = 7
5�e�11+ 5�e�21 = 4
5�e�12+ 5�e�22 = 5
5�e�13+ 5�e�23 = 8
5�e�11; 5�e�12; 5�e�13; 5�e�21; 5�e�22; 5�e�23 e" 0
W.J. Przykłady ZPL 58
Zadanie transportowe
Rozwiązanie
Komórka celu (Min)
Wartość Wartość
Komórka Nazwa
początkowa końcowa
$H$19 0 32
Komórki zmiennych
Wartość Wartość
Komórka Nazwa Całkowite
początkowa końcowa
$E$6 Zmienne 0 2 Ciągłe
$F$6 0 0 Ciągłe
$G$6 0 8 Ciągłe
$E$7 Zmienne 0 2 Ciągłe
$F$7 0 5 Ciągłe
$G$7 0 0 Ciągłe
W.J. Programowanie liniowe 59
Problem diety
Pasza dostarczana zwierzętom na fermie opasu młodego
bydła rzez
nego powinna zawierać co najmniej 720 g białka,
900 g węglowodanów i 60 g tłuszczu. Ferma dysponuje tzw.
 sianokiszonką ,której 1 kg zawiera 24 g białka 10 g
węglowodanów, 1 g tłuszczu oraz kiszonką z
kukurydzy,której 1 kg zawiera 12 g białka 45 g
węglowodanów, 1,5 g tłuszczu. Koszt uzyskania 1 kg
 sianokoszonki wynosi 0,2 zł, a kg kiszonki z kukurydzy
wynosi 0,3 zł.
1. Wyznaczyć optymalną dawkę pokarmową minimalizującą
koszt opasu bydła rzez
nego.
2. Sprawdzić, czy zadanie posiada więcej niż jedno rozwiązanie
optymalne, a jeżeli tak - to jakie.
W.J. Przykłady ZPL 60
20
Problem diety
Sformułowanie zadania
Zmienne decyzyjne: 5�e�1 - liczba kg sianokiszonki
5�e�2 - liczba kg kiszonki z kukurydzy
Zadanie
0,25�e�1 + 0,35�e�2 5�Z�5�V�5�[� (koszt)
245�e�1 + 125�e�2 e" 720 (białko)
105�e�1 + 455�e�2 e" 900 (węglowodany)
5�e�1 + 1,55�e�2 e" 60 (tłuszcz)
5�e�1; 5�e�2 e" 0
W.J. Przykłady ZPL 61
Planowanie produkcji
Stolarnia wytwarza stoły i krzesła ogrodowe. W tabeli podane
są nakłady zasobów na jednostkę produkcji oraz jednostkowy
zysk. Produkcje ograniczają dwa zasoby: drewno (dostępne
w ilości 100 m3) oraz praca (dostępna w ilości 110 godzin).
Stół Krzesło Zasób
Drewno 10 7 100
Praca 5 10 110
Zysk 6$ 8$
Stolarni, która meble ogrodowe sprzedaje w kompletach (stół
i 4 krzesła) zależy na tym, by osiągnąć jak największy zysk
W.J. Przykłady ZPL 62
Planowanie produkcji
Sformułowanie zadania
Zmienne decyzyjne: 5�e�5�`� - liczba wyprodukowanych stołów
5�e�5�X� - liczba wyprodukowanych krzeseł
Zadanie
65�e�5�`� + 85�e�5�X� 5�Z�5�N�5�e�
105�e�5�`� + 75�e�5�X� d" 100
55�e�5�`� + 105�e�5�X� d" 110
45�e�5�`� - 5�e�5�X� = 0
5�e�5�`�; 5�e�5�X� e" 0
W.J. Przykłady ZPL 63
21