Таблиця 7.2

Звідки	Куди
2	3	4	5	6	7	8
1
2
3
4
5
6
7

Знайти, який максимальний обсяг продукції можна перевезти з пункту 1 до пункту 8, якщо враховувати пропускні спроможності кожної окремої ділянки мережі.

Розв’язування задачі про визначення максимального потоку на комп’ютері. Відкриємо робочу книгу Excel "Potik.xls" та у клітинках A1:H1 (об'єднуємо) запишемо назву задачі: "Визначення максимального потоку".

Блок клітинок A3:H12 відведемо для вихідних даних з таблиці 7.2 про пропускні спроможності дуг. Зафарбовані клітинки відповідають випадкам, коли безпосереднє транспортне сполучення від пункту до пункту відсутнє. Залишимо ці клітинки незаповненими – Excel сприйматиме їх як клітинки з нульовими значеннями.

Для інформації про план перевезень відведемо блок клітинок A14:H23. За формою він є копією блоку A3:H12. Значення змінних – про обсяги перевезень за окремими маршрутами – міститимуться у клітинках B17:H23.

Стовпчик I17:I23 відведемо для підсумовування елементів відповідного рядка від колонок B до H включно. Знайдені у цих клітинках за допомогою функцій підсумовування значення відповідатимуть: у клітинці I17 – розміру вихідного потоку, який обчислюється за формулою (7.8); у клітинках I18: I23 – правим частинам обмежень (7.9).

Рядок B24:H24 теж відведемо для допоміжних сум елементів відповідного стовпчика у рядках з 17-го по 23-й. У клітинках B24:G24 значення відповідатимуть лівим частинам обмежень (7.9), а в клітинці H24 – кінцевому потоку, який визначається формулою (7.10).

У клітинках A26:C26 створимо інформаційний блок про розмір потоку. Для цього об’єднаємо клітинки A26:B26 та запишемо в них назву цільового показника: "Розмір потоку", а в клітинку C26 впишемо формулу для його обчислення: = I17.

Оберемо в меню “Сервис” команду “Поиск решения” та в полі “Установить целевую ячейку” діалогового вікна інструменту пошуку рішення вкажемо на адресу цільової клітинки: $C$26.

Перемикач вибору оптимізаційного спрямування цільової функції ввімкнемо у положення “максимальному значению”.

У полі “Изменяя ячейки” вкажемо на адреси клітинок із усіма змінними, які відповідають обсягам перевезень: $B$17:$H$23.

Тепер введемо обмеження задачі:

1)

$I$17

=

$H24

– відповідає одночасно вимогам (7.8) та (7.10);

2)

$I$18:$I$23

=

$B$24:$G$24

– відповідає вимогам (7.9);

3)

$B$17:$H$23

<=

$B$6:$H$12

– відповідає вимогам (7.11), а також унеможливлює перевезення за відсутніми на транспортній мережі сполученнями.

Зазначимо параметри пошуку рішення: “Линейная модель”, “Неотрицательные переменные” та послідовно натиснемо кнопки "OK" і “Выполнить”.

У вікні “Результаты поиска решения” увімкнемо перемикач “Сохранить найденное решение” та натиснемо ОК.

Розв’язок задачі показано на рисунку 7.4. Розмір максимального потоку дорівнює 450 одиниць продукції (клітинка C26). Знайдені оптимальні обсяги перевезень за маршрутами показані також на рис. 7.5 над кожною дугою; під дугами наведено вихідні дані про пропускні спроможності – вони записані у дужках.

 

 

	A	B	C	D	E	F	G	H	I
	Визначення максимального потоку
	Пропускні спроможності дуг
	Звідки	Куди
	План перевезень
	Звідки	Куди
								Разом
									450
									100
									150
									200
									100
									150
									200
	Разом	100	150	200	100	150	200	450
	Розмір потоку

 

Рис. 7.4. Робочий лист Excel з умовами та результатами розв’язування прикладу визначення максимального потоку у транспортній мережі

 

 

					(160)
		(100)					(140)			(180)
			(150)
						(170)				(230)
	(200)					(160)				(200)
					(220)

 

Рис. 7.5. Максимальний потік транспортної мережі

 

7.3. Завдання для самостійного опрацювання

 

1. Знайти найкоротший транспортний маршрут від вершини 1 до вершини 12 на транспортній мережі, граф та довжини (у кілометрах) окремих ділянок якої наведено на рисунку 7.6.

 

Рис. 7.6. Граф транспортної мережі та довжини його дуг

 

2. Яким буде найкоротший маршрут з вершини 1 до вершини 12 (завдання 1, рис. 7.6), якщо транспортні сполучення між окремими пунктами з односторонніх замінити на двосторонні (тобто замість кожної дуги ввести до розгляду дві дуги: та )?

3. Знайти максимальний потік продукції від пункту 1 до пункту 10 на транспортній мережі, граф та пропускні спроможності окремих ділянок якої наведені на рисунку 7.7.

 

Рис. 7.7. Граф транспортної мережі та пропускні спроможності його дуг

 

4. Чи зміниться розмір максимального потоку (завдання 3, рис. 7.7), якщо пропускну спроможність пункту 5 обмежити до 100 одиниць продукції?

РОЗДІЛ 8. ОПТИМАЛЬНИЙ ВИБІР МІСЦЯ РОЗТАШУВАННЯ РОЗПОДІЛЬЧОГО ЦЕНТРУ

 

Перевезення продукції від постачальників до споживачів може здійснюватися через розподільчі центри – один або декілька. Такими центрами можуть бути або регіональні сховища продукції (наприклад, при транспортуванні пального), або діагностичні центри (наприклад, при перевезенні автомобільних моторів на автозаводи) тощо. Виникає задача: де саме слід якнайкраще розташувати такі розподільчі центри?

Розрізнятимемо два типи задач оптимального вибору місця розташування розподільчого центру:

1) задачі з неперервними змінними, в яких невідомими виступають координати розподільчого центру;

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

Опрацюємо ці оптимізаційні задачі на конкретних прикладах.

 

9.1. Вибір оптимального місця розташування сховища пального

9.2. Визначення оптимального місця розміщення нового проміжного розподільчого центру – вузлу транспортної мережі

9.3. Завдання для самостійного опрацювання

 

 

8.1. Вибір оптимального місця розташування сховища пального

 

Постановка та економіко–математична модель задачі. Вздовж траси Київ–Одеса розташовано 8 автозаправних станцій (АЗС) фірми “Нафтогаз”. Відомо, на якому кілометрі траси знаходиться кожна АЗС, та який середній щодобовий продаж пального на цій станції (таблиця 8.1).