Побудова економіко-математичної моделі розробки асортименту швейних виробів (стр. 3 из 3)

5. Перерахувати різницю між двома клітинами з найменшими витратами в кожному рядку та кожному стовпцю, які залишилися незаповненими. При розрахунку подальшої різниці не потрібно враховувати рядки та стовпці з показниками потреби або поставок, які дорівнюють нулю. Повернутись до етапу 2. Цей метод у 80% випадків дозволяє отримати оптимальне або близьке до нього рішення.

На складЗ фабрики	К		Л		М		Н		Поставки з фабрики
А	10	12	13	11	16	12
	Б		12	19	10		15	7	17	17
В		15	8	21		12	7		19		15
	Г	18		9	2	16		17	14	20
Потреба складів			18			22		10			14		6464

1	2	3	4	5	6	7
11-10=1	1	-	-	-	-	-
15-12=3	3	3	5	-	-	-
15-12=3	3	3	3	3	3	3
14-9=5	2	2	2	2	2	-

1	10-9=1	16-13=3	12-11=1	16-14=2
2	-	3	1	2
3	-	3	1	2
4	-	3	-	2
5	-	3	-	2
6	-	3	-	-
7	-	2	-	-

Загальні витрати = 12·13 + 10·15 + 7·17 + 8·21 + 7·19 + 18·9 + 2·16 = 920 грн.

Стадія 3. Знаходження оптимального рішення

Пошук оптимального рішення полягає в оцінці кожної невикористаної клітини та визначенні, чи не буде переміщення в неї вигіднішим з позиції зменшення загальних витрат. Якщо це так, то переміщення виконується і процес повторюється доти, поки не будуть оцінені всі клітини та виконані усі відповідні переміщення.

Метод послідовних кроків

Етапи процесу:

1. Оберіть будь-яку пусту клітину та укажіть замкнений шлях, що веде до неї. Цей шлях складається з горизонтальних та вертикальних ліній, які ведуть від пустої клітини через інші назад до неї ж. В замкненому шляху може бути тільки одна пуста клітина – та, що розглядається. Повороти шляху на 90є можуть виконуватися лише в найближчих до пустої заповнених клітинах.

2. Перемістіть одну одиницю із заповненої клітини у куті замкненого шляху в пусту клітину та приведіть інші заповнені клітини, що залишилися в інших кутах у відповідність до заданих потреб та поставок.

3. Визначить доцільність здійсненого переміщення:

Σ витрат в клітинах, __ Σ витрат в клітинах, до яких була додана одиниця з яких була віднята одиниця

Якщо витрати в результаті переміщень скоротилися, то необхідно перемістити якомога більше одиниць з оціненої заповненої клітини в пусту. Якщо витрати збільшилися, то ніяких переміщень не виконують, а пусту клітину помічають, щоб більше до неї не повертатися.

4. Повторювати етапи 1 – 3 доти, доки не будуть оцінені всі пусті клітини.

Максимальна кількість одиниць, яку можна додати до будь-якої клітини, не повинна перевищувати кількість, що вказана в клітині з найменшим значенням, з якої буде проводитися віднімання. Це необхідно для врахування обмежень щодо потреб та поставок.

Щоб впевнитися, що отриманий розподіл дійсно оптимальний, потрібно знову оцінити кожну пусту клітину та розглянути доцільність переміщення в неї. Якщо в кожній з перевірених клітин витрати зростуть, то задача вирішена та розподіл є оптимальним.

Якщо оцінка пустої клітини дає в результаті таке саме значення, що і розподіл, який розглядається, значить існує рівноцінне альтернативне оптимальне рішення. (Зазвичай пусту клітину, визначену як альтернативний оптимальний маршрут, помічають 0.)

В транспортних задачах у випадках, 1) коли кількість заповнених клітин менше суми кількості рядків та стовпців мінус 1 (m+n-1) або 2) коли перше значення в рядку або стовпці задовольняє обмеженням як по рядку, так і по стовпцю, може спостерігатися явище виродження.

Тоді в будь-яку пусту клітину (або декілька) записується деяка кількість одиниць θ (зазвичай це 0) таким чином, щоб можна було скласти замкнений шлях для оцінки інших пустих клітин. Це значення залишається в задачі доти, поки воно не зникне при відніманні або до отримання остаточного рішення.

Оптимізація розподілу (метод північно-західного кута)

На складЗ фабрики	К		Л		М		Н		Поставки з фабрики
А	12	10	г	13	11	16	12
		Б		6	12	11		19	б	15	17	17
В	в		15		11		21	4		12	а		19	15
		Г	9	16		6	17		14	14		20
Потреба складів	18		22		10		14			6464

а) В-Н +1 (пуста клітина) + -

В-М -1 19 (В-Н) 12 (В-М)

Г-М +1 17 (Г-М) 14 (Г-Н)

Г-Н -1 36 > 26

Переміщення недоцільно

б) Б-М +1 (пуста клітина) + -

Б-Л -1 15 (Б-М) 19 (Б-Л)

В-Л +1 21 (В-Л) 12 (В-М)

В-М -1 36 > 31

Переміщення недоцільно

в) В-К +1 (пуста клітина) + -

Б-К -1 15 (В-К) 12 (Б-К)

Б-Л +1 19 (Б-Л) 21 (В-Л)

В-Л -1 34 > 33

Переміщення недоцільно

г) А-Л +1 (пуста клітина) + -

А-К -1 13 (А-Л) 10 (А-К)

Б-К +1 12 (Б-К) 19 (Б-Л)

Б-Л -1 25 < 29

Переміщення доцільно

На складЗ фабрики	К		Л		М		Н		Поставки з фабрики
А	1	10	11	13	д	11	16	12
		Б		17		12	+		19	+	15	17	17
В	+		15		11	21		4	12		+	19		15
		Г	9	е		16	6		17	14		14	20
Потреба складів	18		22		10			14			6464

д) А-М +1 (пуста клітина) + -

А-Л -1 11 (А-М) 13 (А-Л)

В-Л +1 21 (В-Л) 12 (В-М)

В-М -1 33 > 25

Переміщення недоцільно

е) Г-Л +1 (пуста клітина) + -

В-Л -1 16 (Г-Л) 21 (В-Л)

В-М +1 12 (В-М) 17 (Г-М)

Г-М -1 28 <38

Переміщення доцільно

На складЗ фабрики	К		Л		М		Н		Поставки з фабрики
А	1	10	11	13	+	11	є	16	12
		Б		17		12		+		19	+	15	17	17
В	+		15		5	21	10		12	+		19	15
		Г	ж	9		6		16	+		17	14		14	20
Потреба складів	18			22			10			14			6464

є) А-Н +1 (пуста клітина) + -

А-Л -1 16 (А-Н) 13 (А-Л)

Г-Л +1 16 (Г-Л) 14 (Г-Н)

Г-Н -1 32 > 27

Переміщення недоцільно

ж) Г-К +1 (пуста клітина) + -

А-К -1 9 (Г-К) 10 (А-К)

А-Л +1 13 (А-Л) 16 (Г-Л)

Г-Л -1 22 < 26

Переміщення доцільно

На складЗ фабрики	К		Л		М		Н		Поставки з фабрики
А	+	10	12	13	+	11	+	16	12
		Б		17		12		+		19	+	15	з	17	17
В	+		15		5	21	10		12	+		19		15
		Г	1	9		5		16	+		17	14	14		20
Потреба складів	18			22			10			14			64 64

з) Б-Н +1 (пуста клітина) + -

Б-К -1 17 (Б-Н) 12 (Б-К)

Г-К +1 9 (Г-К) 14 (Г-Н)

Г-Н -1 26 =26

Переміщення можна не робити.

Загальні витрати =12·13 + 17·12 + 5·21 + 10·12 + 1·9 + 5·16 + 14·14= 870 грн.

Отже, всі клітини перевірено і ми впевнились, що отриманий розподіл дійсно оптимальний і становить 870 грн.