2.I. OPTYMALIZACJA ROZKROJU MATERIAŁU.

Model rozkroju nazywany jest również w literaturze modelem minimalizacji odpadów. Do rozwiązywania tych problemów wykorzystuje się metodę programowania liniowego.

W optymalizacji rozkroju materiału występować mogą następujące przypadki.

1. Jeden format materiału wyjściowego pociąć można na różne elementy wyrobu złożonego. Określa się możliwe technologicznie strategie rozkroju materiału wyjściowego. Dla każdej strategii określa się wielkość powstającego odpadu. Zadanie formułuje się następująco:

Określić program cięcia zapewniający uzyskanie określonej liczby elementów przy minimalnej wielkości odpadu.

2. Kilka różnych formatów materiału wyjściowego rozkroić na żądane elementy wyrobu złożonego. Określa się technologicznie możliwe strategie rozkroju dla każdego formatu wyjściowego. Dla każdej strategii określa się wielkość powstającego odpadu. Wtedy zadanie formułuje się następująco: Określić strukturę materiału wyjściowego tak aby uzyskać minimum odpadu przy określonej liczbie elementów.

Dla wymienionych przypadków liniowy model ma następującą postać:

x_j ≥ 0

F =

gdzie:

a_ij - liczba sztuk elementu „i” otrzymana z jednostki materiału wyjściowego przy danej strategii rozkroju „j”

x_j - liczba jednostek materiału wyjściowego, która będzie rozkrojona daną strategią „j”

b_i - założona liczba elementów

c_j - odpad jednostki materiału wyjściowego przy strategii rozkroju „j”

3. W skład wyrobu złożonego wchodzą różne elementy w określonych ilościach. Wtedy można optymalizować nie tylko wielkości odpadu, ale również liczbę kompletów (wyrobów złożonych). Mając możliwe technologicznie strategie rozkroju zadanie formułuje się następująco:

Określić program cięcia zapewniający uzyskanie maksymalnej liczby kompletów (wyrobów złożonych) przy określonej liczbie i strukturze materiału wyjściowego.

Dla tego przypadku liniowy model ma następującą postać:

x_j ≥ 0

F = x_j+1 →max

gdzie:

a_ij - liczba sztuk elementu „i” otrzymana z jednostki materiału wyjściowego przy danej strategii rozkroju „j”

x_j - liczba jednostek materiału wyjściowego, która będzie rozkrojona daną strategią „j”

B - określona wielkość materiału wyjściowego

d_i - liczba sztuk elementu „i” w jednostce wyrobu złożonego

x_j+1 - liczba sztuk wyrobu złożonego (liczba kompletów)

Konkretne przykłady rozkroju.

1. Na jeden komplet wyrobu składają się:

1 detal typu A

3 detale typu B

5 detali typu C

Detale wycinane są z blachy siedmioma strategiami. W tabeli podano liczbę detali i odpad z jednego arkusza dla każdej strategii cięcia.

Detale	Strategie rozkroju
		I	II	III	IV	V	VI	VII
A	2	1	1	0	0	0	0
B	0	1	0	3	2	1	0
C	0	1	3	0	2	4	6
Odpad	0	0,5	0,5	0,1	0,1	0,1	0,1

Ile razy należy zastosować możliwe strategie rozkroju aby otrzymać nie mniej niż 1200 kompletów minimalizując odpady.

2. Zakład produkujący puszki otrzymuje surowiec o dwóch formatach arkuszy blachy 1,5×1 i 1,8×1. Na komplet wyrobu składają się 2 sztuki denka i 1 ściana boczna. Dla każdego formatu arkusza blachy stosować można trzy strategie rozkroju. W tabeli podano liczbę detali i odpad dla każdego formatu i każdej strategii.

	Format A			Format B
Detale	strategie rozkroju			strategie rozkroju
		I	II	III	I	II	III
Denko	70	15	10	30	20	-
Ścianka boczna	-	20	30	25	30	50
Odpad	0,1	0,2	0,2	0,3	0,4	0

Jaką strukturę wsadu należy zamówić aby otrzymać 10000 sztuk puszek przy minimalnym odpadzie.

Modele zadań.

1. 2x₁ + x₂ + x₃ ≥ 1200

x₂ + 3x₄ + 2x₅ + x₆ ≥ 3600

x₂ + 3x₃ + 2x₅ + 4x₆ + 6x₇ ≥ 6000

F = 0,5x₂ + 0,5x₃ + 0,1x₄ + 0,1x₅ + 0,1x₆ + 0,1x₇ → min

2. x - liczba sztuk blach ciętych daną strategią

70x₁ + 15x₂ + 10x₃ + 30x₄ + 20x₅ = 20000szt

20x₂ + 30x₃ + 25x₄ + 30x₅ + 50x₆ = 10000szt

F = 0,1x₁ + 0,2x₂ + 0,2x₃ + 0,3x₄ + 0,4x₅ →min

3. Zakład produkuje trzy wyroby, które wycinane są z pręta wyjściowego o długości 5,6 m. długości poszczególnych wyrobów wynoszą: A - 1,2 m.; B - 1,6 m.; C - 1,9 m. Wyprodukować należy nie mniej niż 200 szt. - A; 300 szt. - B; 100 szt. - C. Wyjściowy pręt można ciąć dziewięcioma różnymi strategiami. W tabeli podana jest liczba detali i odpad dla każdej strategii cięcia.

Detale	Strategie cięcia
		I	II	III	IV	V	VI	VII	VIII	IX
A	4	-	1	1	2	3	3	-	-
B	-	3	-	1	2	-	1	2	1
C	-	-	2	1	-	1	-	1	2
Odpad	0,8	0,8	0,6	0,9	0	0,1	0,4	0,5	0,2

Jakie strategie cięcia stosować aby otrzymać nie mniej ( lub dokładnie ) niż podana liczba wyrobów przy minimalnym odpadzie. Jak będzie wyglądał model liniowy zadania gdy wprowadzimy dodatkowo. Jakie strategie cięcia zastosować aby zminimalizować odpad przy równoczesnym zmaksymalizowaniu zysku. Zysk na wyrób wynosi: A - 50; B - 200; C - 400.

Będzie to problem z zakresu programowania liniowego wielokryterialnego.

Mamy dwie funkcje kryterium. Pierwsza o postaci jak poprzednio.

F = 0,8x₁ + 0,8x₂ + 0,6x₃ + 0,9x₄ + 0,5x₅ + 0,1x₆ + 0,4x₇ + 0,5x₈ + 0,2x₉ →min

Druga funkcja będzie miała postać.

50*4x₁ + 200*3x₂ + (50 + 2*400)x₃ + (50 + 200+400)x₄ + (2*50 + 2*200)x₅ + (3*50 + 1*400)x₆ + (3*50 + 1*200)x₇ + (2*200 + 1*400)x₈ + (1*200 + 2*400)x₉ → max

Aby zadanie miało rozwiązanie to do układu nierówności z pierwszego przypadku o postaci:

1. 4x₁ + x₃ + x₄ + 2x₅ + 3x₆ + 3x₇ ≥ 200

2. 3x₂ + x₄ + 2x₅ + x₇ + 2x₈ + x₉ ≥ 300

3. 2x₃ + x₄ + x₆ + x₈ + 2x₉ ≥ 100

należy dodać układ nierówności ograniczających obszar rozwiązań dopuszczalnych od góry wprowadzając ograniczenie wynikające z możliwości produkcyjnych. Produkcja wyrobów ma być nie większa niż A - 400; B - 500; C - 200.

Otrzymane nierówności:

4. 4x₁ + x₃ + x₄ + 2x₅ + 3x₆ + 3x₇ ≤ 400

5. 3x₂ + x₄ + 2x₅ + x₇ + 2x₈ + x₉ ≤ 500

6. 2x₃ + x₄ + x₆ + x₈ + 2x₉ ≤ 200

4. Zmieniamy przykład 2.

Zakład produkuje puszki z surowca w postaci dwóch rodzajów blachy: 21500 mb o szerokości 1,5 m. i 14000 mb o szerokości 1,8 m. Z każdej postaci blach wycina się elementy sześcioma strategiami w ilościach podanych w tabeli

Elementy	Blacha o szerokości 1,5 m.			Blacha o szerokości 1,8 m.
		I	II	III	IV	V	VI
Denko	70	15	10	30	20	-
Ścianka boczna	-	20	30	25	30	50

Zmaksymalizować liczbę otrzymanych puszek wiedząc, że każda puszka ma dwa denka i jedną ściankę boczną.

oznaczenia

X₁ → x₆ - ilość metrów blachy ciętej daną strategią

X₇ - liczba puszek

zapis modelu

x₁ + x₂ + x₃ ≤ 21500

x₄ + x₅ + x₆ ≤ 14000

70x₁ + 15x₂ + 10x₃ + 30x₄ + 20x₅ = 2x₇

20x₂ + 30x₃ + 25x₄ + 30x₅ + 50x₆ = x₇

F = x₇ → max

rozwiązanie:

X₁ = 20625

X₃ = 875

∑ 21500

x₆ = 14000

x₇ = 726250

5. Do wyprodukowania drążków o długości A = 0,6 m.; B = 1,5 m. ; C = 2,5 m. , których ilości powinny odpowiadać ilościom A : B : C równym 2 : 1 : 3 przeznacza się 1000 belek o długości 3m. Określić program cięcia zapewniający uzyskanie maksymalnej liczby kompletów. Zastosować można cztery strategie cięcia. Liczby sztuk blach przy każdej strategii podaje tabela.

Drążki	Strategie cięcia
		I	II	III	IV
A	5	2	-	-
B	-	1	2	-
C	-	-	-	1

x₁ → x₄ - liczba belek ciętych daną strategią

x₅ - liczba kompletów

x₁ + x₂ + x₃ + x₄ ≤ 1000

5x₁ + 2x₂ = 2x₅

x₂ + 2x₃ = x₅

x₄ = 3x₅

F = x₅ → max

---