Wydział Matematyki  Programowanie liniowe  Ćwiczenia
Zestaw 1. Modelowanie zadań programowania liniowego.
Zadania dotyczÄ…ce zagadnienia planowania produkcji
Zadanie 1.1. Zapisać następujące zadanie w postaci zadania programowania liniowego.
Producent odzieży powinien określić, ile kurtek i płaszczy należy wyprodukować tak, aby zysk
osiągnięty z ich sprzedaży był maksymalny. Do produkcji wykorzystywany jest jeden rodzaj tkaniny.
Producent posiada 150 m2 tej tkaniny. Zgodnie z zamówieniami należy wyprodukować co najmniej 20
kurtek i co najwyżej 10 płaszczy. Do produkcji jednej kurtki i jednego płaszcza potrzeba odpowiednio
2, 5 m2 i 4 m2 tkaniny. Przy sprzedaży jednej kurtki producent osiąga zysk 60 zł, płaszcza 50 zł.
Zadanie 1.2. Zapisać następujące zadanie w postaci zadania programowania liniowego.
Wytwórca mebli powinien określić, ile stołów, krzeseł, biurek i szaf powinien wyprodukować tak,
aby zysk osiągnięty z ich sprzedaży był maksymalny. Do produkcji wykorzystywane są dwa typy
desek. Wytwórca posiada 1500 m desek I typu i 1000 m desek II typu oraz dysponuje kapitałem 860
godzin roboczych na wykonanie zaplanowanej produkcji. Ze złożonych zamówień wynika, że należy
wyprodukować co najmniej 40 stołów, 130 krzeseł, 30 biurek i nie więcej niż 10 szaf. Do produkcji
każdego stołu, krzesła, biurka i szafy potrzeba odpowiednio 5, 1, 9, 12 m desek I typu i 2, 3, 4, 1 m
desek II typu. Na wykonanie stołu potrzeba 3 godzin pracy, krzesła - 2 godzin, biurka - 5 godzin, szafy
- 10 godzin. Ze sprzedaży jednego stołu, krzesła, biurka i szafy wytwórca osiąga zysk odpowiednio 50,
20, 60 i 40 zł.
Zadanie 1.3. Zapisać następujące zadanie w postaci zadania programowania liniowego. Podać wektor
c określający funkcjonał kosztu orza macierz A i wektor b występujące w opisie ograniczeń.
Producent farb musi określić, ile litrów farby białej, zielonej, niebieskiej i czerwonej powinien
wyprodukować tak, aby zysk osiągnięty z ich sprzedaży był maksymalny. Do produkcji wykorzystywane
są trzy surowce: A, B i C. Producent posiada 230 litrów surowca A, 200 litrów surowca B i 170 litrów
surowca C oraz dysponuje kapitałem 160 godzin roboczych na wykonanie zaplanowanej produkcji.
Ze złożonych zamówień wynika, że należy wyprodukować co najmniej 125 litrów farby białej, co
najmniej 135 litrów farby zielonej, co najwyżej 205 litrów farby niebieskiej i nie mniej niż 175 litrów
farby czerwonej. Ilość poszczególnych surowców potrzebnych do wyprodukowania 1 litra każdej farby
przedstawione są w następującej tabeli (w litrach)
biała zielona niebieska czerwona
A 0,30 0,60 0,35 0,15
B 0,25 0,20 0,45 0,55
B 0,45 0,20 0,20 0,30
Ponadto wyprodukowanie 1 litra każdej farby wymaga 15 minut pracy. Zysk ze sprzedaży 1 litra farby
białej wynosi 7 zł, zielonej - 6 zł, niebieskiej - 7 zł i czerwonej - 5 zł.
1 Modelowanie zadań programowania liniowego.
Zadania dotyczÄ…ce zagadnienia transportowego
Zadanie 1.4. Zapisać następujące zadanie w postaci zadania programowania liniowego.
Pewien wytwórca posiada centrale zbytu w Lublinie, A
odzi i Szczecinie. Centrale te posiadajÄ…
odpowiednio 40, 20 i 40 jednostek produktu. Punkty sprzedaży zamówiły następujące ilości produktu:
Białystok - 25, Cieszyn - 10, Kraków - 20, Sopot - 30, Warszawa - 15. Koszt transportu jednostki (w
zł.) z każdej centrali zbytu do dowlnego punktu sprzedaży podaje następująca tabela:
Białystok Cieszyn Kraków Sopot Warszawa
Lublin 55 30 40 50 40
A
ódz
35 30 100 45 60
Szczecin 40 60 95 35 30
Należy rak zaplanować dystrybucję produktu, by koszt transportu był minimalny.
Zadanie 1.5. Zapisać następujące zadanie w postaci zadania programowania liniowego.
Dyrektor pewnego przedsiębiorstwa powinien obsadzić trzy stanowiska, które wymagają różnych
kwalifikacji i praktyki zawodowej, przy czym ma do dyspozycji trzech konkretnych pracowników. Ze
względu na różne ich kwalifikacje, czas praktyki i zdobyte doświadczenie wartość (dla przedsiębiorstwa)
każdego z tych pracowników zależy od stanowiska, na którym jest on zatrudniony. Poniższa tabela
zawiera oceny wartości poszczególnych pracowników zatrudnionych na poszczególnych stanowiskach
Stanowisko I Stanowisko II Stanowisko III
Pracownik A 5 4 7
Pracownik B 6 7 3
Pracownik C 8 11 2
Należy rak rozmieścić pracowników na rozważanych stanowiskach, by całkowita ich wartość dla przed-
siębiorstwa była maksymalna.
Zadania dotyczÄ…ce zagadnienia diety
Zadanie 1.6. Zapisać następujące zadanie w postaci zadania programowania liniowego.
Zadaniem dietetyka jest opracowanie składu porannej owsianki tak, aby zawierała ona niezbędne
dzienne zapotrzebowanie organizmu na określone składniki odżywcze i jednocześnie była możliwie
najtańszą. Dietetyk ma do dyspozycji płatki Corn Flakes i Nesquik. Śniadanie powinno zawierać
co najmniej 1 mg witaminy B1, 12 mg żelaza i mieć wartość energetyczną równą 360 kcal. 100 g
płatków Corn Flakes zawiera 1, 2 mg witaminy B1, 12 mg żelaza i ma wartość energetyczną równą
368 kcal, natomiast 100 g płatków Nesquik zawiera 1, 5 mg witaminy B1, 10 mg żelaza i ma wartość
energetyczną równą 390 kcal. Ponadto 100 g płatków Corn Flakes kosztuje 32 gr, a 100 g płatków
Nesquik - 36 gr.
Zadanie 1.7. Zapisać następujące zadanie w postaci zadania programowania liniowego.
Hodowca krowy karmi zwierzÄ™ produktami pochodzÄ…cymi z gospodarstwa rolnego. Jednak ze wzglÄ™-
du na konieczność zapewnienia w diecie odpowiednich ilości pewnych składników odżywczych (nazwij-
my je A, B, C) hodowca musi zakupić raz w roku trzy dodatkowe produkty (nazwijmy je I, II, III),
2
1 Modelowanie zadań programowania liniowego.
które zawierają te składniki. 1 kg produktu I zawiera 63 g składnika A i 9 g składnika B, 1 kg pro-
duktu II zawiera 14 g składnika B i 28 g składnika C, zaś 1 kg produktu III zawiera 50 g składnika
A i 15 g składnika C. Minimalne zapotrzebowanie zwierzęcia na poszczególne składniki wynosi:
870 g składnika A,
200 g składnika B,
450 g składnika C.
Każdy z produktów zawiera jednak pewne ilości szkodliwych środków konserwujących. I tak, 1 kg
produktu I zawiera 7 g tych środków, produktu II - 11 g, produktu III - 9 g. Roczne spożycie tych
środków nie powinno być większe niż 150 g. Przyjmijmy na koniec, że 1 kg produktu I kosztuje 35 zł,
produktu II - 29 zł, produktu III - 19 zł. Celem hodowcy jest ustalenie ilości kupowanych produktów
I, II, III tak, aby zapewnić zwierzęciu odpowiednią dietę i jednocześnie ponieść możliwie najmniejsze
koszty.
Formalny zapis zadań programowania liniowego
Zadanie 1.8. Zapisać zadanie 1.4 w postaci podstawowego zadania programowania liniowego.
Zadanie 1.9. Zapisać zadanie 1.2 w postaci kanonicznego zadania programowania liniowego.
Zadanie 1.10. Zapisać zadanie 1.6 w postaci kanonicznego zadania programowania liniowego.
Zadanie 1.11. Zapisać zadanie ogólne
Å„Å‚
ôÅ‚ J(u) = u1 + 2u2 + 3u3 min.
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚ u " U = {u = (u1, u2, u3) " R3; u1 e" 0,
òÅ‚
10u1 + 20u2 + 30u3 d" 11,
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚ 100u1 + 200u2 + 300u3 d" 12,
ôÅ‚
ôÅ‚
ół
1 1 1
u1 + u2 + u3 = 0}
2 3 4
w postaci zadania kanonicznego.
Zadanie 1.12. Zapisać zadanie ogólne
Å„Å‚
ôÅ‚ J(u) = 3u1 + 5u2 + 7u3 + 9u4 min.
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚ u " U = {u = (u1, u2, u3, u4) " R4; u2 e" 0, u4 e" 0,
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚ 11u1 + 12u2 + 13u3 + 14u4 d" 1,
òÅ‚
21u1 + 23u3 d" -1,
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚ 32u2 e" 8,
ôÅ‚
ôÅ‚
ôÅ‚
1 1 1 1
ôÅ‚
ôÅ‚ u1 + u2 + u3 + u4 = 2,
ôÅ‚
1 2 3 4
ôÅ‚
ół
1 1
u1 + u4 = -2}
11 14
w postaci zadania kanonicznego.
3
2 Geometryczne rozwiązywanie zadań programowania liniowego.
Zestaw 2. Geometryczne rozwiązywanie zadań programowania
liniowego.
Zadanie 2.1. Rozwiązać w sposób geometryczny następujące zadanie:
Å„Å‚
ôÅ‚
J(u) = u1 + 2u2 min.
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
u " U = {u = (u1, u2) " R2; u e" 0,
ôÅ‚
ôÅ‚
ôÅ‚
òÅ‚
-2u1 - u2 d" -2,
1 1
ôÅ‚
u1 - u2 d" ,
ôÅ‚
2 2
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
-u1 + u2 d" 2,
ôÅ‚
ôÅ‚
ôÅ‚
ół
u1 d" 3}
Zadanie 2.2. Rozwiązać w sposób geometryczny następujące zadanie:
Å„Å‚
ôÅ‚
J(u) = -2u1 + u2 min.
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
u " U = {u = (u1, u2) " R2; u e" 0,
ôÅ‚
ôÅ‚
ôÅ‚
òÅ‚
-u1 - u2 d" -1,
ôÅ‚
-u1 + u2 d" -1,
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
-u1 + 2u2 d" 0,
ôÅ‚
ôÅ‚
ôÅ‚
ół
2u1 - u2 d" 5}
Zadanie 2.3. Rozwiązać w sposób geometryczny następujące zadanie:
Å„Å‚
ôÅ‚
J(u) = 2u1 - u2 min.
ôÅ‚
ôÅ‚
ôÅ‚
òÅ‚
u " U = {u = (u1, u2) " R2; u e" 0,
ôÅ‚
-1u1 + u2 d" 2,
ôÅ‚
2
ôÅ‚
ôÅ‚
ół
-1u1 - u2 d" -1}
2
Zadanie 2.4. Rozwiązać w sposób geometryczny następujące zadanie:
Å„Å‚
ôÅ‚
J(u) = -u1 + u2 min.
ôÅ‚
ôÅ‚
ôÅ‚
òÅ‚
u " U = {u = (u1, u2) " R2; u e" 0,
ôÅ‚
-1u1 + u2 d" 2,
ôÅ‚
2
ôÅ‚
ôÅ‚
ół
-1u1 + u2 = 1}
3
Zadanie 2.5. Rozwiązać w sposób geometryczny następujące zadanie
W pewnym zakładzie wytwarzane są produkty A i B. Do produkcji każdego z nich wykorzysty-
wana jest praca trzech maszyn: M1, M2, M3. Maszyna M1 może być wykorzystana przez 24000
s, M2 - 40000 s, M3 - 27000 s. Poniższa tabela podaje czas pracy każdej maszyny potrzebny do
wyprodukowania jednostki każdego produktu:
4
2 Geometryczne rozwiązywanie zadań programowania liniowego.
A B
M1 3 6
M2 8 4
M3 9 3
Zysk ze sprzedaży jednostki produktu A wynosi 9 zł, B - 6 zł. Należy zaplanować produkcję tak, aby
zysk ze sprzedaży był maksymalny.
Zadanie 2.6. Rozwiązać w sposób geometryczny następujące zadanie:
Å„Å‚
ôÅ‚ J(u) = -u1 - 3u2 - 2u4 - 3u5 min.
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚ u " U = {u = (u1, u2, u3, u4, u5) " R5; u e" 0,
òÅ‚
u1 + 2u4 + 3u5 = 15,
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚ 2u1 + u3 + u4 + 5u5 = 20,
ôÅ‚
ôÅ‚
ół
u1 + u2 + 2u4 + u5 = 10}
Zadanie 2.7. Rozwiązać w sposób geometryczny następujące zadanie:
Å„Å‚
ôÅ‚ J(u) = -u1 - 2u2 + u3 min.
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚ u " U = {u = (u1, u2, u3, u4, u5) " R5; u e" 0,
òÅ‚
3u1 - 2u2 + 2u3 - 2u4 + 3u5 = 38,
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚ -u1 + u2 + 3u4 - u5 = 13,
ôÅ‚
ôÅ‚
ół
u1 - u2 + u3 = 14}
5
3 Punkty wierzchołkowe
Zestaw 3. Punkty wierzchołkowe
Zadanie 3.1. Znalez
ć, w oparciu o twierdzenie, punkty wierzchołkowe zbioru
1
U = {u = (u1, u2) " R2; u e" 0, - u1 + u2 = 1}.
3
Zadanie 3.2. Znalez
ć, w oparciu o twierdzenie, punkty wierzchołkowe zbioru
U = {u = (u1, u2, u3, u4) " R4; u e" 0, u1 + u2 + 3u3 + u4 = 3, u1 - u2 + u3 + 2u4 = 1}.
Zadanie 3.3. Znalez
ć, w oparciu o twierdzenie, punkty wierzchołkowe zbioru
U = {u = (u1, u2, u3, u4) " R4; u e" 0, u1 + u4 = 0, 2u2 + u4 = 3, 3u3 = 0}
i wskazać ich bazy.
Zadanie 3.4. Znalez
ć, w oparciu o twierdzenie, punkty wierzchołkowe zbioru
U = {u = (u1, u2, u3) " R3; u e" 0, u1 + 2u2 + 3u3 = 4, -u1 + 5u3 = 0}.
Podać bazy znalezionych punktów wierzchołkowych.
Zadanie 3.5. Znalez
ć, w oparciu o twierdzenie, punkty wierzchołkowe zbioru
U = {u = (u1, u2, u3) " R3; u e" 0, u1 + u2 + 2u3 = 10, -u1 + 3u3 = 9, u1 + 2u2 + 7u3 = 29}.
6
4 Metoda sympleksowa
Zestaw 4. Metoda sympleksowa
Zadanie 4.1. Rozwiązać metodą sympleksową zadanie:
Å„Å‚
ôÅ‚
J(u) = u1 - u2 + u4 min.
ôÅ‚
ôÅ‚
ôÅ‚
òÅ‚
u " U = {u = (u1, u2, u3, u4) " R4; u e" 0,
ôÅ‚
2u1 - 2u2 + 4u3 + u4 = 2,
ôÅ‚
ôÅ‚
ôÅ‚
ół
u1 + u2 + u4 = 0}

2
1
startując z punktu wierzchołkowego v = (0, 0, , 0), wiedząc, że jego bazą jest układ kolumn ,
2
1

4
.
0
Zadanie 4.2. Rozwiązać metodą sympleksową zadanie:
Å„Å‚
ôÅ‚
J(u) = u1 + 2u2 + 3u3 + 4u4 min.
ôÅ‚
ôÅ‚
ôÅ‚
òÅ‚
u " U = {u = (u1, u2, u3, u4) " R4; u e" 0,
ôÅ‚
u1 + u2 + 3u3 + u4 = 3,
ôÅ‚
ôÅ‚
ôÅ‚
ół
u1 - u2 + u3 + 2u4 = 1}
startując z punktu wierzchołkowego v = (2, 1, 0, 0).
Zadanie 4.3. Rozwiązać metodą sympleksową zadanie:
Å„Å‚
ôÅ‚
J(u) = u1 + 2u2 + 3u3 + 4u4 min.
ôÅ‚
ôÅ‚
ôÅ‚
òÅ‚
u " U = {u = (u1, u2, u3, u4) " R4; u e" 0,
ôÅ‚
u1 + u2 + 3u3 + u4 = 3,
ôÅ‚
ôÅ‚
ôÅ‚
ół
u1 - u2 + u3 + 2u4 = 1}
5 4
startując z punktu wierzchołkowego v = (0, , 0, ).
3 3
Zadanie 4.4. Zapisać zadanie
Å„Å‚
ôÅ‚
J(u) = u1 + 2u2 + 3u3 + 4u4 min.
ôÅ‚
ôÅ‚
ôÅ‚
òÅ‚
u " U = {u = (u1, u2, u3, u4) " R4; u e" 0,
ôÅ‚
u1 + u2 + 3u3 + u4 d" 3,
ôÅ‚
ôÅ‚
ôÅ‚
ół
u1 - u2 + u3 + 2u4 = 1}
w postaci zadania kanonicznego, rozwiązać tak otrzymane zadanie metodą sympleksową, a następnie
podać rozwiązanie zadania wyjściowego.
Zadanie 4.5. Utworzyć tablicę sympleksową dla zadania
Å„Å‚
ôÅ‚
J(u) = u1 - u2 + 2u4 min.
ôÅ‚
ôÅ‚
ôÅ‚
òÅ‚
u " U = {u = (u1, u2, u3, u4) " R4; u e" 0,
ôÅ‚
2u1 - 3u2 + 4u3 + u4 = 3,
ôÅ‚
ôÅ‚
ôÅ‚
ół
u1 + u2 - 2u3 = 10}
17
i punktu wierzchołkowego v = (33, , 0, 0).
5 5
7
5 Wybór początkowego punktu wierzchołkowego
Zestaw 5. Wybór początkowego punktu wierzchołkowego
Zadanie 5.1. Sprawdzić, korzystając z zadania pomocniczego, czy zbiór
U = {u = (u1, u2, u3, u4) " R4; u e" 0, u1 + u2 + 3u3 + u4 = 3, u1 - u2 + u3 + 2u4 = 1}
jest niepusty i jeśli tak - wyznaczyć, przy pomocy metody sympleksowej, punkt wierzchołkowy tego
zbioru.
Zadanie 5.2. Rozważmy zadanie
Å„Å‚
ôÅ‚
J(u) = u1 + 3u2 - 5u3 + u4 - 3u5 min.
ôÅ‚
ôÅ‚
ôÅ‚
òÅ‚
u " U = {u = (u1, u2, u3, u4, u5) " R5; u e" 0,
ôÅ‚
u1 + u2 - 4u3 + u4 - 3u5 = 3,
ôÅ‚
ôÅ‚
ôÅ‚
ół
u1 - 4u3 + 2u4 - 5u5 = 6}.
Utworzyć tablicę sympleksową dla punktu wierzchołkowego v = (0, 0, 0, 3, 0), wiedząc, że współrzędny-
mi bazowymi tego punktu są współrzędne v1 i v4. Czy punkt v jest rozwiązaniem zadania? Odpowiedz

uzasadnić.
8