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

Тема 4. Транспортна задача.

Мета: Навчитися розв’язувати ТЗ.

План.

1. Зведення задач відкритого типу до задач закритого типу.

2. Алгоритм розв'язування транспортної задачі на ПЕОМ.

3. Пошук розв'язку транспортної задачі засобами Excel.

 

1. Зведення задач відкритого типу до задач закритого типу.

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

                                                                        (1)

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

Теорема. Для існування розв’язку транспортної задачі необхідно і достатньо, щоб запаси вантажу у пунктах відправлення дорівнювали потребам у вантажі у пунктах призначення, тобто, щоб виконувалась рівність (1).

У випадку, якщо запаси перевищують потреби, тобто , вводиться фіктивний (n+1)-й пункт призначення із потребою  і відповідні тарифи вважаються рівними нулю: с_in+1=0 (). Отримана задача є транспортною задачею для якої виконується рівність (1).

Аналогічно при  вводиться фіктивний (m+1)-й пункт відправлення із запасом вантажу  і тарифи вважаються рівними нулю: с_m+1j=0 ().

Задача. В пунктах відправлення А₁, А₂, А₃, .... знаходиться однорідний вантаж в кількості a₁, а₂, а₃, .... відповідно, який необхідно перевезти в пункти призначення  В₁, В₂, В₃, .... , потреба кожного з яких становить b_1, b₂, b_3, .... . Відома відстань між пунктами перевезень (оцінки).

Маємо три постачальника з такими запасами вантажу: А₁ = 26 т, А₂ = 33 т, А₃ = 45 т;  і чотири споживача з потребою на цей вантаж: В₁ = 14 т, В₂  = 19 т, В₃ = 20 т, В₄ = 5 т.

Відома відстань між пунктами перевезень.

Відстань між пунктами перевезень, км (С_ij).

Постачальники	Споживачі
	B1	B2	B3	B4
A1	6	4	15	19
A2	13	17	28	3
A3	5	20	6	10

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

Рішення.

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

- загальні запаси = 26+33+45 = 104 т;

- загальні потреби = 14+19+20+5 = 58 т.

Отже задача відкрита, тому необхідно ввести фіктивного споживача, якому слід перевезти В_фікт = 104–58 = 46 т.

 

2. Алгоритм розв'язування транспортної задачі на ПЕОМ.

1. Створимо підготовчу форму для розв’язання задачі (див рис. 1). Відстань між пунктами перевезень вказана в клітинках B4:Е6. В клітинках B11:Е13 після застосування Поиска решения з’являться шукані значення змінних. Клітинка В17 буде містити вартість перевезення. У чарунки В14:Е14 та F11:F13 введено формули для лівих частин обмежень. Значення правих частин обмежень – в чарунках B15:Е15, G11:G13. В чарунці В17 задана формула для розрахунку значення цільової функції.

Рис. 1. Підготовча форма для розв’язання транспортної задачі

 

3. Пошук розв'язку транспортної задачі засобами Excel.

1. Виконаємо пункти головного меню Сервис→Поиск решения. На екрані з’явиться діалогове вікно „Поиск решения”, в якому треба встановити такі параметри (див. рис. 2):

Рис. 2. Діалогове вікно “Поиск решения” при розв’язанні транспортної задачі

 

1. в полі Установить целевую ввести адресу чарунки, що містить цільову функцію (в нашому прикладі В17);
2. у полі Равной встановити перемикач в положення Минимальному значению (за спрямованістю цільової функції);
3. у полі Изменяя ячейки ввести діапазон чарунок для шуканих змінних В11:Е13;
4. задати праві частини обмежень таким чином:

• в діалоговому вікні Поиск решения клацнути на кнопці Добавить. Відкриється діалогове вікно „Добавление ограничения” (рис. 3)

Рис. 3. Діалогове вікно „Добавление ограничения” при розв’язанні транспортної задачі

 

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

Рис. 4. Введення обмежень моделі групою при розв’язанні транспортної задачі

 

5. встановити параметри пошуку рішень. Для цього в діалоговому вікні „Поиск решения” клацнути на кнопці Параметры. Відкриється діалогове вікно „Параметры поиска решения” (рис. 5), в якому необхідно встановити прапорці в полях Линейная модель і Неотрицательные значения. Псля втановлення необхідних параметрів клацать на кнопці ОК і потрапляють знов у вікно „Поиск решения”.

Рис. 5. Діалогове вікно Параметры поиска решения

 

6. клацнути на кнопці Выполнить діалогового вікна „Поиск решения”, після чого на екрані з’явиться вікно Результаты поиска решения (рис. 6).

Рис. 6. Діалогове вікно Результаты поиска решения

 

Можна зберегти знайдений розв’язок, якщо обрати опцію Сохранить найденное решение, або Восстановить исходные значения, якщо потрібно перейти до розв’язування іншої задачі.

Діалогове вікно „Результаты поиска решения” може містити й інші повідомлення. Так, наприклад, якщо виведеться повідомлення „Значения целевой ячейки не сходятся” або „Поиск не может найти подходящего решения”, то необхідно перевірити правильність складаня і введення моделі. Якщо помилок немає, то ці повідомлення означають, що задача не має розв’язку.

2. Проаналізуємо отримані результати (рис. 7), які знаходяться в чарунках B11:Е13 i B17.

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

1. мінімальна вартість перевезення вантажу 533 гр. од.
2. матриця перевезень:

 

Рис. 7. Результати розв’язання транспортної задачі

 

Методичне забезпечення

1. Сергієнко В.А. Математичне програмування. Конспект лекцій для студентів напряму підготовки 6.030601 „Менеджмент” денної та заочної форм навчання / В.А. Сергієнко, Л.П. Перхун, 2010. – 140 С.
2. Лавров Є.А. Математичне програмування: навчальний посібник / Є.А. Лавров, Л.П. Перхун, В.А. Сергієнко / За ред. Є.А. Лаврова. – Суми, 2010. – 224 С.

 

Рекомендована література

Базова

1. Бех О.Б. Збірник задач з математичного програмування. Навч. пос. / О.Б. Бех, Т.А. Огородня, А.Ф. Щебрак – К.: Видавництво Ліра-К, 2013. – 212 С.
2. Бех О.Б. Математичне програмування. Пос. / О.Б. Бех, Т.А. Огородня, А.Ф. Щебрак – К.: Видавництво Ліра-К, 2013. – 200 С.
3. Вдовин М. Л. Математичне програмування теорія та практикум. Пос. / М.Л. Вдовин, С.Г. Данилюк – К.: Видавництво Ліра-К, 2014. – 160 С.
4. Глушик М. М. Математичне програмування. Підручник / М. М. Глушик, І.М. Копич, В.М. Сороківський – К.: Видавництво Ліра-К, 2014. – 280 С.
5. Глушик М. Математичне програмування. Підручник / М. Глушик, І.Копич, О.Пенцак, В. Сорківський – К.: Видавництво Ліра-К, 2013. – 216 С.
6. Копич І.М. Математичні моделі в менеджменті та маркетингу. Навч. пос. / І.М. Копич, В.М. Сороківський ,В.І.Стефаняк – К.: Видавництво Ліра-К, 2014. – 376 С.
7. Кучма М.І. Математичне програмування: приклади та задачі. пос. / М.І. Кучма – К.: Видавництво Ліра-К, 2013. – 344 С.
8. Мартиненко М.А. Математичне програмування: підручник / М.А. Мартиненко, О.М. Нещадим, В.М. Сафонов – К.: Видавництво Ліра-К, 2010. – 311 С.

 

Інформаційні ресурси

(в т.ч. електронна бібліотека СНАУ)

1. http://web.archive.org/web/20070205063920/http://dims.karelia.ru/~alexmou/tpr/tpr_02_linear_programming.ppt – слайди по лінійному програмуванню
2. Український інститут ІТ в освіті Економіко-математичне моделювання (Демо-версія)  [Електронний ресурс]. – Режим доступу: http://moodle.ipo.kpi.ua/moodle/mod/resource/index.php?id=125
3. Іващук О.Т. Економіко-математичне моделювання [Електронний ресурс] / О.Т. Іващук. – Т.: ТНЕУ «Економічна думка», 2008. – 704 с.
4. Курило А.О. Математичне програмування. Конспект лекцій. - Суми, 2015 рік 136 ст., табл. 51, рис. 36.
5. Курило А.О. Математичне програмування. Частина 1: методичні вказівки щодо виконання практичних та самостійних робіт. – Суми, 2015, ст.76, табл. 20, рис. 11.
6. Курило А.О. Математичне програмування. Частина 2: методичні вказівки щодо виконання практичних та самостійних робіт. – Суми, 2015, ст.84, табл. 16, рис. 13.
7. Сергієнко В.А.  Математичне програмування. Конспект лекцій для студентів напряму підготовки 6.030601 „Менеджмент” денної та заочної форм навчання./ В.А.Сергієнко, Л.П. Перхун. 2009 – 149 с.
8. Сергієнко В.А., Перхун Л.П. Електронний засіб навчального призначення: «Математичне програмування» для студентів денної та заочної форм навчання за напрямом підготовки 6.030601 «Менеджмент», 2010.