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 m

2

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 m

2

i 4 m

2

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, Ł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

Łódź

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 B

1

, 12 mg żelaza i mieć wartość energetyczną równą 360 kcal. 100 g

płatków Corn Flakes zawiera 1, 2 mg witaminy B

1

, 12 mg żelaza i ma wartość energetyczną równą

368 kcal, natomiast 100 g płatków Nesquik zawiera 1, 5 mg witaminy B

1

, 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) = u

1

+ 2u

2

+ 3u

3

→ min.

u ∈ U = {u = (u

1

, u

2

, u

3

) ∈ R

3

; u

1

≥ 0,

10u

1

+ 20u

2

+ 30u

3

≤ 11,

100u

1

+ 200u

2

+ 300u

3

≤ 12,

1
2

u

1

+

1
3

u

2

+

1
4

u

3

= 0}

w postaci zadania kanonicznego.

Zadanie 1.12. Zapisać zadanie ogólne



















































J (u) = 3u

1

+ 5u

2

+ 7u

3

+ 9u

4

→ min.

u ∈ U = {u = (u

1

, u

2

, u

3

, u

4

) ∈ R

4

; u

2

≥ 0, u

4

≥ 0,

11u

1

+ 12u

2

+ 13u

3

+ 14u

4

≤ 1,

21u

1

+ 23u

3

≤ −1,

32u

2

≥ 8,

1
1

u

1

+

1
2

u

2

+

1
3

u

3

+

1
4

u

4

= 2,

1

11

u

1

+

1

14

u

4

= −2}

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) = u

1

+ 2u

2

→ min.

u ∈ U = {u = (u

1

, u

2

) ∈ R

2

; u ≥ 0,

−2u

1

− u

2

≤ −2,

1
2

u

1

− u

2

≤

1
2

,

−u

1

+ u

2

≤ 2,

u

1

≤ 3}

Zadanie 2.2. Rozwiązać w sposób geometryczny następujące zadanie:











































J (u) = −2u

1

+ u

2

→ min.

u ∈ U = {u = (u

1

, u

2

) ∈ R

2

; u ≥ 0,

−u

1

− u

2

≤ −1,

−u

1

+ u

2

≤ −1,

−u

1

+ 2u

2

≤ 0,

2u

1

− u

2

≤ 5}

Zadanie 2.3. Rozwiązać w sposób geometryczny następujące zadanie:























J (u) = 2u

1

− u

2

→ min.

u ∈ U = {u = (u

1

, u

2

) ∈ R

2

; u ≥ 0,

−

1
2

u

1

+ u

2

≤ 2,

−

1
2

u

1

− u

2

≤ −1}

Zadanie 2.4. Rozwiązać w sposób geometryczny następujące zadanie:























J (u) = −u

1

+ u

2

→ min.

u ∈ U = {u = (u

1

, u

2

) ∈ R

2

; u ≥ 0,

−

1
2

u

1

+ u

2

≤ 2,

−

1
3

u

1

+ u

2

= 1}

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: M 1, M 2, M 3. Maszyna M 1 może być wykorzystana przez 24000
s, M 2 - 40000 s, M 3 - 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) = −u

1

− 3u

2

− 2u

4

− 3u

5

→ min.

u ∈ U = {u = (u

1

, u

2

, u

3

, u

4

, u

5

) ∈ R

5

; u ≥ 0,

u

1

+ 2u

4

+ 3u

5

= 15,

2u

1

+ u

3

+ u

4

+ 5u

5

= 20,

u

1

+ u

2

+ 2u

4

+ u

5

= 10}

Zadanie 2.7. Rozwiązać w sposób geometryczny następujące zadanie:































J (u) = −u

1

− 2u

2

+ u

3

→ min.

u ∈ U = {u = (u

1

, u

2

, u

3

, u

4

, u

5

) ∈ R

5

; u ≥ 0,

3u

1

− 2u

2

+ 2u

3

− 2u

4

+ 3u

5

= 38,

−u

1

+ u

2

+ 3u

4

− u

5

= 13,

u

1

− u

2

+ u

3

= 14}

5

3

Punkty wierzchołkowe

Zestaw 3. Punkty wierzchołkowe

Zadanie 3.1. Znaleźć, w oparciu o twierdzenie, punkty wierzchołkowe zbioru

U = {u = (u

1

, u

2

) ∈ R

2

;

u ≥ 0,

−

1

3

u

1

+ u

2

= 1}.

Zadanie 3.2. Znaleźć, w oparciu o twierdzenie, punkty wierzchołkowe zbioru

U = {u = (u

1

, u

2

, u

3

, u

4

) ∈ R

4

;

u ≥ 0,

u

1

+ u

2

+ 3u

3

+ u

4

= 3,

u

1

− u

2

+ u

3

+ 2u

4

= 1}.

Zadanie 3.3. Znaleźć, w oparciu o twierdzenie, punkty wierzchołkowe zbioru

U = {u = (u

1

, u

2

, u

3

, u

4

) ∈ R

4

;

u ≥ 0,

u

1

+ u

4

= 0,

2u

2

+ u

4

= 3,

3u

3

= 0}

i wskazać ich bazy.

Zadanie 3.4. Znaleźć, w oparciu o twierdzenie, punkty wierzchołkowe zbioru

U = {u = (u

1

, u

2

, u

3

) ∈ R

3

;

u ≥ 0,

u

1

+ 2u

2

+ 3u

3

= 4,

−u

1

+ 5u

3

= 0}.

Podać bazy znalezionych punktów wierzchołkowych.

Zadanie 3.5. Znaleźć, w oparciu o twierdzenie, punkty wierzchołkowe zbioru

U = {u = (u

1

, u

2

, u

3

) ∈ R

3

;

u ≥ 0,

u

1

+ u

2

+ 2u

3

= 10,

−u

1

+ 3u

3

= 9,

u

1

+ 2u

2

+ 7u

3

= 29}.

6

4

Metoda sympleksowa

Zestaw 4. Metoda sympleksowa

Zadanie 4.1. Rozwiązać metodą sympleksową zadanie:























J (u) = u

1

− u

2

+ u

4

→ min.

u ∈ U = {u = (u

1

, u

2

, u

3

, u

4

) ∈ R

4

; u ≥ 0,

2u

1

− 2u

2

+ 4u

3

+ u

4

= 2,

u

1

+ u

2

+ u

4

= 0}

startując z punktu wierzchołkowego v = (0, 0,

1
2

, 0), wiedząc, że jego bazą jest układ kolumn

"

2

1

#

,

"

4

0

#

.

Zadanie 4.2. Rozwiązać metodą sympleksową zadanie:























J (u) = u

1

+ 2u

2

+ 3u

3

+ 4u

4

→ min.

u ∈ U = {u = (u

1

, u

2

, u

3

, u

4

) ∈ R

4

; u ≥ 0,

u

1

+ u

2

+ 3u

3

+ u

4

= 3,

u

1

− u

2

+ u

3

+ 2u

4

= 1}

startując z punktu wierzchołkowego v = (2, 1, 0, 0).

Zadanie 4.3. Rozwiązać metodą sympleksową zadanie:























J (u) = u

1

+ 2u

2

+ 3u

3

+ 4u

4

→ min.

u ∈ U = {u = (u

1

, u

2

, u

3

, u

4

) ∈ R

4

; u ≥ 0,

u

1

+ u

2

+ 3u

3

+ u

4

= 3,

u

1

− u

2

+ u

3

+ 2u

4

= 1}

startując z punktu wierzchołkowego v = (0,

5
3

, 0,

4
3

).

Zadanie 4.4. Zapisać zadanie























J (u) = u

1

+ 2u

2

+ 3u

3

+ 4u

4

→ min.

u ∈ U = {u = (u

1

, u

2

, u

3

, u

4

) ∈ R

4

; u ≥ 0,

u

1

+ u

2

+ 3u

3

+ u

4

≤ 3,

u

1

− u

2

+ u

3

+ 2u

4

= 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) = u

1

− u

2

+ 2u

4

→ min.

u ∈ U = {u = (u

1

, u

2

, u

3

, u

4

) ∈ R

4

; u ≥ 0,

2u

1

− 3u

2

+ 4u

3

+ u

4

= 3,

u

1

+ u

2

− 2u

3

= 10}

i punktu wierzchołkowego v = (

33

5

,

17

5

, 0, 0).

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 = (u

1

, u

2

, u

3

, u

4

) ∈ R

4

;

u ≥ 0,

u

1

+ u

2

+ 3u

3

+ u

4

= 3,

u

1

− u

2

+ u

3

+ 2u

4

= 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) = u

1

+ 3u

2

− 5u

3

+ u

4

− 3u

5

→ min.

u ∈ U = {u = (u

1

, u

2

, u

3

, u

4

, u

5

) ∈ R

5

; u ≥ 0,

u

1

+ u

2

− 4u

3

+ u

4

− 3u

5

= 3,

u

1

− 4u

3

+ 2u

4

− 5u

5

= 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 v

1

i v

4

. Czy punkt v jest rozwiązaniem zadania? Odpowiedź

uzasadnić.

8