Tomasz Kowalski
Wykłady z matematyki dla studentów kierunków ekonomicznych
Wykład 29
ZAGADNIENIA PROGRAMOWANIA LINIOWEGO - lista zadań
1. Rozwiązać następujące ZPL korzystając z metody gradientowej (metody izolinii):
z = 3x1 + 4x2 max z = x1 + 5x2 min z = 2x1 + 5x2 max
ż#-3x1 + 2x2 d" 6,
ż#-x1 + 3x2 d" 3,
ż#-x1 + 2x2 d" 2,
ª#3x ª#x ª#x
a) + 2x2 d" 18, b) + x2 d" 5, c) + x2 d" 4,
ª# ª# ª#
1 1 1
¨# ¨# ¨#
ª#x1 + x2 e" 1, ª#x1 + 3x2 e" 3, ª#x1 + 2x2 e" 2,
ª#x1 e" 0, x2 e" 0. ª#x1 e" 0, x2 e" 0. ª#x1 e" 0, x2 e" 0.
©# ©# ©#
2. Rozwiązać następujące ZPL korzystając z zasady przeglądania wierzchołków ZRD:
z = 2x1 + x2 max z = 2x1 + 3x2 max z = 3x1 + 4x2 min
ż#-3x1 + 2x2 d" 6,
ż#-x1 + 2x2 d" 3, ż#-x1 + 2x2 d" 4,
ª#3x ª#3x ª#3x
a) - x2 d" 6, b) + x2 d" 9, c) + 2x2 d" 18,
ª# ª# ª#
1 1 1
¨# ¨# ¨#
1
ª#x + 2x2 e" 2, ª#x1 + 2x2 e" 2, ª#x1 + x2 e" 1,
ª#x1 e" 0, x2 e" 0. ª#x1 e" 0, x2 e" 0. ª#x1 e" 0, x2 e" 0.
©# ©# ©#
.
z = 2x1 + 2x2 max z = 4x1 + 2x2 max
2x1 + x2 e" 6, 2x1
ż# ż# - x2 d" 6,
ª#x ª#2x
d) + x2 d" 9, e) + x2 d"10,
ª# ª#
1 1
¨# ¨#
1 1
ª#2x - 3x2 d" -2, ª#4x - x2 e" -4,
ª#x1 e" 0, x2 e" 0. ª#x1 e" 0, x2 e" 0.
©# ©#
3. Zakład krawiecki szyje spodnie i spódnice. Przy szyciu spodni i spódnic zakład wykorzystuje dwa
zasoby: materiał i siłę roboczą. Na wykonanie pary spodni potrzeba 2m materiału oraz 8 roboczogodzin,
na uszycie spódnicy potrzeba 3m materiału i 2 roboczogodziny. Zakład może maksymalnie wykorzystać
60 m materiału i 80 roboczogodzin. Ze sprzedaży wyrobów otrzymuje 18 zł za spódnicę i 32 zł za
spodnie.
a) Ułożyć ZPL, które pozwoli znalez
ć plan produkcji maksymalizujący przychód przedsiębiorstwa.
b) Rozwiązać zadanie metodą graficzną.
Zadania do wykładu 29: Zagadnienia programowania liniowego
2
Odpowiedzi
1. a) b) c)
x1 = 3, x2 = 0, zmin = 3
x1 = 2, x2 = 2, zmax = 14
x1 = 2, x2 = 6, zmax = 30
2.a) b) c)
(2,0) (3,3) (0,1,5) (0,1) (2,0) (3,0) (2,3) (0,2) (0,1) (1,0) (6,0) (2,6) (0,3) (0,1)
4 9 1,5 1 4 6 13 6 3 3 18 30 12 4
d) e)
(2,2) (5,4) (0,9) (0,6) (0,0) (3,0) (4,2) (1,8) (0,4)
8 18 18 12 0 12 20 20 8
W obu przypadkach istnieje nieskończenie wiele rozwiązań optymalnych. Oprócz wskazanych dwóch
wierzchołków są nimi wszystkie punkty łączące te wierzchołki.
3. Przy oznaczeniach x1 - liczba szytych spodni, x2 - liczba szytych spódnic ZPL ma postać:
z = 32x1 +18x2 max
2x1 + 3x2 d" 60,
ż#
Rozw. optymalne x1 = 6, x2 =16 . Wtedy zmax = 480 .
¨#
8x1 + 2x2 d" 80,
©#
x1, x2 e" 0.