Лабораторна робота № 4 розрахунок транспортної задачі засобами excel

Метою даної лабораторної роботи є отримання відомостей і навичок роботи з різними типами транспортних задач та їх вирішення за допомогою МS Ехсеl.

Теоретичні відомості

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

Найпростіше формулювання транспортної задачі за критерієм вартості звучить таким чином.

У m пунктах відправлення знаходяться, відповідно, a₁, a₂,…a_m одиниць однорідного вантажу (ресурси), що повинен бути доставлений у n заданих пунктів призначення (споживання), відповідно, у кількостях b₁, b₂,…b_n одиниць (потреби). Нехай вартість перевезення одиниці вантажу з і-го пункту відправлення в j–й пункт призначення дорівнює G_ij, а відповідна кількість одиниць перевезеного вантажу рівна х_ij (і=1,...m; j=1,…n).

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

Матриці, утворені значеннями змінних і коефіцієнтами x_ij, називаються, відповідно, планом перевезень і матрицею транспортних витрат.

Розрізняють закриті і відкриті математичні моделі транспортної задачі. У моделях першого типу зберігається баланс між сумарними ресурсами і сумарними потребами:

а в моделях другого типу порушений баланс між сумарними ресурсами і потребами:

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

З курсу лінійного програмування відомо, що для закритої моделі справедливі наступні твердження:

• рівність (1) є необхідною і достатньою умовою сумісності транспортної задачі;

• будь-яка транспортна задача має оптимальний план;

• якщо величини і є цілими числами, то і всі значення змінних х_ij в оптимальному плані будуть цілими величинами.

Рішення закритої моделі транспортної задачі

План перевезень називається припустимим, якщо величини x_ij задовільняють наступні обмеження:

обмеження за ресурсами

обмеження за потребами

обмеження за невід’ємністю

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

Транспортна задача описується цільовою функцією:

яка відповідає сумарним витратам на перевезення.

Рішення задачі зводиться до мінімізації цієї цільової функції для всіх величин x_ij, що задовольняють умовам (4)-(7).

Рішення відкритої моделі транспортної задачі

У випадку перевищення сумарних ресурсів над сумарними потребами (2) для визначення оптимального плану перевезень вводять фіктивний (n+1)-й пункт призначення з потребою

і припускають вартість m перевезень вантажів у цей пункт рівними нулю: G_i,n+1 (і=1,...m).

Отримана задача перетворюється в закриту транспортну задачу, тому що для неї виконується рівність

Для визначення оптимального плану перевезень у випадку перевищення сумарних потреб над сумарними ресурсами (3) вводиться фіктивний (m+1)-й пункт відправлення вантажу, запас якого дорівнює

і вартості n перевезень вантажів з цього пункту приймаються рівними нулю: G_n+1,j (j=1,...m).

Нова задача є вже закритою задачею, тому що для неї виконується рівність

Слід зазначити, що для випадку відкритої задачі цільова функція Z так само буде визначатися формулою (7), тому що вартості перевезень вантажів з фіктивного пункту відправлення чи вантажу у фіктивний пункт призначення за визначенням дорівнюють нулю.

Наслідки

• Введення фіктивних пунктів відправлення вантажу чи призначення вантажу зводить відкриту задачу до закритої, що дозволяє уніфікувати підхід до рішення транспортних задач.

• 3 уведенням фіктивного пункту призначення в оптимальному плані основні змінні покажуть раціональні маршрути й обсяги перевезень у них, а-змінні, зв’язані з фіктивним пунктом споживання, - не перевезений залишок запасів.

• Аналогічно з уведенням фіктивного пункту відправлення вантажу в оптимальному плані, основні змінні покажуть раціональні маршрути й обсяги перевезень у них, а змінні, зв'язані з фіктивним пунктом відправлення, покажуть незадоволений попит.

Визначення оптимального плану перевезень як закритого, так і відкритого типу задач можна розв`язувати за допомогою надбудови Пошук рішення МS Ехсеl.

Постановка задачі. На трьох складах А, В, С є 65+р, 100+р і 105+р тон бензину відповідно. Потрібно скласти план його перевезення до чотирьох споживачів (І, II, III, IV) так, щоб вони одержали необхідні 45+р, 60+р, 80+р і 65+р тон бензину відповідно, а витрати на перевезення були мінімальними. Вартість перевезення 1 тони бензину (в грош.од.) зі складів до споживачів зазначена в таблиці 4.1.

Таблиця 4.1.

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

Склади	Споживачі
	І	II	III	IV
А	4+0.5р	5+0.2р	7+0.1р	3+0.6р
В	5+0.3р	3+0.4р	4+0.5р	5+0.4р
С	3+0.6р	6+0.1р	5+0.4р	4+0.4р

Порядок виконання роботи:

1. Запустіть прикладну програму МS Ехсеl. В робочому листі, що з`явився, наберіть таблицю з вихідними даними (див. табл. 4.2).

Таблиця 4.2.

Зразок заповнення робочого листа в МS Ехсеl

	A	B	C	D	E		F
1	Cклади	Споживачі					Запаси
2		I	II	III	IV
3	A	0	0	0	0
4	B	0	0	0	0
5	C	0	0	0	0
6	Всього						ΣF3:F5=
7	Попит						ΣB7:E7=
	A	B	C	D	E
9	Cклади	Споживачі
10		I	II	III	IV
11	A	Gij	Gij	Gij	Gij
12	B	Gij	Gij	Gij	Gij
13	C	Gij	Gij	Gij	Gij
15	A	B	C	D	E
16	Цільова чарунка					0
17
18	Обмеження А					0
19	Обмеження В					0
20	Обмеження С					0
21	Обмеження І					0
22	Обмеження ІІ					0
23	Обмеження ІІІ					0
24	Обмеження ІV					0

2. У діапазон кліток ВЗ:В5 як початкові значення попереднього розподілу запасів бензину на складах А, В, С між споживачами І, II, III, IV заносимо нулі. У діапазон кліток FЗ:F5 записуємо запаси бензину, розміщені на складах А, В, С відповідно. У діапазон кліток В7:Е7 - потреби в бензині споживачів І, II, III, IV.

3. В клітку F6 заносимо контрольну суму об’ємів бензину, розміщеного на складах, тобто суму кліток FЗ:F5. В клітку F7 заносимо контрольну суму потреби в бензині всіх споживачів, тобто суму чарунок В7:Е7.

4. Якщо контрольні суми в клітках F6 та F7 збігаються, то розглянута модель транспортної задачі є закритою, якщо суми відрізняються – відкритою. У випадку відкритої задачі її потрібно звести до закритої шляхом введення фіктивного пункту призначення (якщо наявні сумарні ресурси перевищують сумарні потреби) або фіктивного пункту відправлення вантажу(якщо сумарні потреби більші за наявні ресурси).

5. У діапазоні кліток В11:Е13 формуємо матрицю вартостей (витрат) перевезень однієї тони бензину з кожного складу кожному споживачеві.

6. У клітку F15 заносимо формулу для розрахунку цільової функції, використовуючи вбудовану функцію =СУММПРОИЗВ(В11:Е13; ВЗ:Е5).

7. Обмеження задачі записуються в клітки F17:F23. Так, для обмеження А заносимо в клітку F17 сумарну кількість бензину, що буде перевезено зі складу А всім споживачам, скориставшись вбудованою функцією СУММ. Для обмеження 1 заносимо в клітку F20 сумарну кількість бензину, що доставляється першому споживачу з усіх складів (за допомогою формули =СУММ(ВЗ:В5)). Аналогічно заповнюються інші обмеження.

8. Після завершення формування робочого листа, запускаємо з меню Сервис (Данные) команду Поиск решения. У полі Установить целевую ячейку вказуємо адресу клітки, що буде містити рішення задачі. У нашому випадку це F15. У розділі Равной. обираємо перемикач Минимальному значенню, а в полі Изменяя ячейку - діапазон кліток $В$3:$Е$5.

9. Щоб ввести обмеження задачі, натискаємо кнопку Добавить. При цьому відкривається діалогове вікно (Добавить ограничения). Вводимо перше обмеження: $F17=$F$3, тобто сумарна кількість перевезеного зі складу А бензину для всіх споживачів дорівнює запасу бензину, розміщеного на тому ж складі. Аналогічним чином вводимо інші обмеження задачі, щоразу натискаючи по закінченню введення кнопку ОК.

10. Для реалізації умови невід’ємності значень у діалоговому вікні Поиск решения натискаємо клавішу Параметры і після появи ще одного діалогового вікна Параметры поиска решений включаємо прапорець Неотрицательные значенния. Крім того, додаємо в умову цілочисельності, натиснувши в діалоговому вікні Поиск решения кнопку Добавить, обираємо в діалоговому вікні, що з’явилося, Добавить ограничения для діапазону комірок B3:F5 значення «ціл» (ціле).

11. При натисканні кнопки Выполнить діалогового вікна Поиск решения з'являється діалогове вікно Результати поиска решений. Слід обрати тип звіту — Результати. Після натискання кнопки ОК з'являється новий робочий лист зі звітом за результатами.

12. Проаналізуйте отримані результати розрахунку; здайте роботу викладачеві.