098 099 2

■M

98

Programowanie liniowe

Przedziały, na które podzielony został zbiór parametrów, zaprezentowano na rys. 1.33.

Rysunek 1.33

(l)

(H)

0,286

<V)(VI)    (VII)

ii__

1,2    1,556

t

1.9.

Przykłady wykorzystania programowania liniowego

Przedstawimy dalej trzy przykłady zagadnień programowania liniowego. Pierwszy z nich dotyczy wyboru sposobu cięcia kłód, który pozwoli na realizację zamówienia przy minimalnym odpadzie. Jest to przykład zagadnienia rozkroju. Drugi przykład związany jest z zagadnieniem diety i określeniem optymalnego sposobu żywienia bydła. Trzeci dotyczy możliwości wykorzystania programowania parametrycznego, gdy rozpatrujemy zagadnienie planowania produkcji. Dwa pierwsze zadania można rozwiązać zarówno za pomocą programu SIMP.EXE, jak i DUAL.EXE, przy czym ze względu na postać zadań wygodnie jest wykorzystywać te programy w sposób zaproponowany w zamieszczonych dalej rozwiązaniach. Można również szukać rozwiązań całkowitoliczbowych i zastosować programy opisane w rozdziale 2.

Inne zadania, zarówno problemowe, jak i numeryczne, pozwalające na lepsze poznanie metody programowania liniowego, znajdują się na dołączonym do książki CD-ROM-ie.

1.9.1. Zagadnienie rozkroju

Przykład I.23¹³

Tartak otrzymał zamówienie na dostarczenie 100 kompletów zbrojeniowych, z których każdy składa się z jednej belki o długości 2,9 m, jednej belki o długości 2,1 mi jednej belki o długości 1,5 m o określonym przekroju. Tartak dysponuje kłodami o wymaganym przekroju, ale długość tych kłód wynosi 7,4 m. W jaki sposób należy rozcinać kłody, by wykonać zamówienie przy minimalnym odpadzie drewna? Rozpatrywane sposoby rozkroju przedstawiono w tablicy 1.47.

¹⁵ Przykład został zaczerpnięty z książki /.. Czerwińskiego, Matematyka na usługach ekonomii, PWN, Warszawa 1984.

Przykłady wykorzystania programowania liniowego

Tablica 1.47

Liczba uzyskanych desek	Sposoby rozkroju
	1	2	3	4	5	6
Długich (2,9 m)	1	1	2	0	1	0
Średnich (2,1 m)	1	0	0	2	2	1
Krótkich (1,5 m)	1	3	1	2	0	3

99

Obliczamy odpad, jaki powstaje przy zastosowaniu kolejnych sposobów rozkroju. Na podstawie danych z tablicy 1.1 dla sposobu 1 rozkroju mamy odpad wynoszący: 7,4 m— 1 -2,9 m — 1 -2,1 m — 1 • 1,5 m = 0,9 m. Dla dalszych sposobów rozkroju otrzymujemy następujące wielkości:

sposób 2 — odpad 0 m, sposób 3 — odpad 0,1 m, sposób 4 — odpad 0,2 m, sposób 5 — odpad 0,3 m, sposób 6 — odpad 0,8 m.

Rozwiązanie

Cel

Celem jest znalezienie takiego sposobu rozkroju, który minimalizuje odpad. Zmienne decyzyjne

x, — liczba kłód pociętych sposobem 1, x₂ — liczba kłód pociętych sposobem 2, x₃ — liczba kłód pociętych sposobem 3, x₄ — liczba kłód pociętych sposobem 4, x₅ — liczba kłód pociętych sposobem 5, x₆ — liczba kłód pociętych sposobem 6.

Funkcja celu