3. Математичні моделі задач виробничої ситуації

Задача про максимальний потік :

.

Транспортна задача :

.

Задача розподілу методом динамічного програмування :

.

13.1.4. Розв’язування задач виробничої ситуації

I етап.

Складається мережа залізниці з одним початком та однією кінцевою точкою. Для цього вводиться фіктивна початкова точка S. Пропускні спроможності фіктивних дуг від точки S до j-ї фабрики у вигляді P_sj складаються з спроможностей P_jl для дуг,які виходять з j-ї фабрики:

.

Потім розв’язується задача про максимальний потік і знаходиться величина V_max. Згідно з кінцевою матрицею X обчислюються усі значення b_j, тобто усі можливості перевезень від кожної j-ї фабрики:

b_j = x_sj ( ).

Таким чином, величини b_j є попитом на сировину по кожній j-й фабриці. Загальний попит на сировину

тобто дорівнює максимальному потоку заданої мережі з її пропускними спроможностями.

II етап.

Розв’язується питання прив’язки складів до фабрик. Попит фабрик – це величини b_j, а можливості кожного i-го складу

.

Отже, на даному етапі розв’язується відкрита транспортна задача, у якій

з початковими даними { a_i }, { b_j }, || C_ij || .

Для розв’язування цієї задачі вводиться фіктивний споживач (фіктивна фабрика), для якого

.

Після розв’язування транспортної задачі фіктивний споживач та прив’язані до нього фіктивні поставки виключаться з подальшого розв’язування.

Обсяги складів

.

Транспортні витрати

.

III етап.

Згідно із заданими функціями витрат f_k ( x_k ) за кожною k-ю технологією, загальною величиною постачання сировини b, а також обмеженнями на складські приміщення a_k^min та a_k^max розв’язується задача розподілу сировини методом динамічного програмування.

За наслідками розв’язування знаходять обсяги завантаження сировиною кожної k-ї технологічної лінії x_k та загальні витрати на виробництво реактивів F у цілому по заводу.

IV етап.

Складається загальна схема постачання сировини та виробництва реактивів і визначаються загальні витрати:

F_о = F + F_тр.

V етап.

Висновки та пропозиції щодо поліпшення розв’язку, повторне розв’язування виробничої ситуації. Остаточний розв’язок.

3. Приклад.

Початкові дані наступні.

М ережа залізниці у вигляді зваженого графу показана на рис.13.3.

рис.13.3.

Транспортні витрати на перевезення сировини

.

Витрати на виробництво реактивів за кожною k-ю технологією

умови 5 x_k 12 та цілочисловий розподіл сировини.

Додаткові умови.

У разі необхідності можливо знизити нижню межу значень x_k до нуля, пропускні спроможності S_5t, S₄₇ та S₆₇ збільшити на дві одиниці, а спроможність S₅₇ на чотири одиниці.

Розв’язування:

Задану мережу залізниці доповнюємо однією фіктивною початковою вершиною S (рис.13.4).

Р ис.13.4.

Знаходимо пропускні спроможності від s–ї вершини до кожної j–ї фабрики P_sj:

P_S1 = P₁₄ = 4 ,

P_S2 = P₂₄ + P₂₆ = 2 + 3 =5 ,

P_S3 = P₃₅ = 10 .

Внаслідок розв’язування задачі про максимальний потік по кінцевій матриці потоків

		S	1	2	3	4	5	6	7	t
	S	x	4	4	6
	1		x			4
	2			x		2		2
Х =	3				x		6
	4					x				6
	5						x		2	4
	6							x	2
	7								x	4
	t									x

б удується мережа залізниці з розрахованими пропускними спроможностями x_jl (рис.13.5.).

Рис.13.5.

Таким чином, дуги (45), (46), (56), (47) – зайві, дуги (26), (35), (4t), (7t) – не повністю завантажені (у дужках фактичні спроможності P_jl ). Жирні лінії – робоча мережа залізниці.

Отже, максимальний потік

V_max = b = x_s1 + x_s2 + x_s3 = 4 + 4 + 6 =14,

а попит на сировину по кожній фабриці дорівнює

b₁ = x_s1 = 4;

b₂ = x_s2 = 4;

b₃ = x_s3 = 6.

Для розв’язування транспортної задачі визначають можливості постачання складів

a₁ = a₂ = a₃ = b₁ + b₂ + b₃ = 4 + 4 + 6 = 14,

а потім розв’язують транспортну задачу з початковими даними:

a_i = 14, 14, 14,

b_i = 4, 4, 6,

Кінцева таблиця розподілу:

	I	II	III	IV	ai
1		4		10	14
2			6	8	14
3	4			10	14
bj	4	4	6	28

Оскільки четвертий споживач фіктивний, тому що

то він не береться до уваги при знаходженні обсягів постачання сировини від складів:

A₁ = x₁₁ + x₁₂ + x₁₃ = 0 + 4 + 0 = 4;

A₂ = x₂₁ + x₂₂ + x₂₃ = 0 + 0 + 6 = 6;

A₃ = x₃₁ + x₃₂ + x₃₃ = 4 + 0 + 0 = 4.

Витрати на постачання сировини

F_тр = 64 + 56 + 54 = 74 тис. грн.

Схема прив’язки постачальників-складів до споживачів-фабрик

показана на рис.13.6.

Рис.13.6

Щоб знайти оптимальний розподіл сировини b =14 одиниць між k технологічними лініями, розв’язується задача розподілу методом динамічного програмування

x₁ + x₂ = 14,

5 x₁ 12,

5 x₂ 12

з цілочисловими значенням x_k.

Результатом розв’язку є наступна таблиця:

∆	x1( )	φ1( )	x2( )	φ2( )
5	5	7,5	-	-
6	6	51,0	-	-
7	7	71,5	-	-
8	8	84,5	-	-
9	9	104,5	-	-
10	10	125,0	5	62,5
11	11	148,5	6	69,0
12	12	174,0	7	76,0
13	-	-	8	83,5
14	-	-	9	91,5

Отже, розв’язком задачі розподілу буде: x₁= 5, x₂ = 9, F =91,5 тис. грн.

С хема розподілу показана на рис.13.7.

Рис.13.7

Загальні витрати на виробництво хімічних речовин

F₀ = F + F_тр = 91,5 + 74,0 = 165,5 тис.грн.

За результатами розв’язування даної виробничої ситуації схема постачання сировини та виробництва хімічних речовин зображена на рис.13.8.

С клади Фабрики Мережа Завод

Рис.13.8

Висновки та пропозиції

Згідно з додатковими умовами до прикладу доцільно буде така зміна початкових даних:

перша технологічна лінія працює на нижній межі (x₁ = 5), тому що ефективність переробки сировини має гірший показник; цю лінію треба менше завантажувати, а по другій лінії вигідно збільшити виробництво. Це можливо передбачити, якщо

0 x₁ 12,

5 x₂ 12.

З такою зміною початкових умов ведеться повторне розв’язування виробничої ситуації, що дає наступний розв’язок:

F = 90,0, x₁ = 2, x₂ = 12.

Загальні ватрати:

F₀ = F + F_тр = 90,0 + 74,0 = 164,0 тис. грн.,

що зменшило на 1.5 тис. грн. витрати на виробництво хімічної речовини.

Щоб збільшити обсяги виробництва, скористаємося додатковими умовами на збільшення перевезення сировини.

Спроможності дуг (47), (67) та (5t) можливо збільшити на дві одиниці, а дугу (57) – на чотири. Але дуга (47) зовсім не потрібна (немає сенсу збільшувати ії спроможність), щодо інших, то їх спроможності можливо збільшити: Р₆₇ = 4, Р_5t = 6, Р₅₇ = 6.

Якщо виробничу ситуацію повторно розв’язати за цими змінами, то оптимальний розв’язок наступний:

V_max = b = 19,

a₁ = 5, a₂ = 10, a₃ = 4,

b₁ = 4, b₂ = 5, b₃ = 10,

F_тр = 100,

F = 152,5,

x₁ = 7, x₂ = 12,

F₀ = F + F_тр = 100 + 152,5 = 252,5 тис.грн.

Цей варіант розв’язку передбачає зміну 0 x₁ 12, тобто для обсягу переробки сировини b=19 одиниць витрати оптимального варіанта дорівнюють 252,5 тис. грн., тобто гірші, ніж було одержано.