Економічні задачі, що зводяться до задач транспортного типу

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

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

Сформулюємо визначення транспортної задачі. Деяку продукцію, яка знаходиться в m постачальників , кількістю одиниць відповідно (запаси постачальника), потрібно перевезти n споживачам в кількості одиниць (попит споживача). Відома матриця вартості перевезення одиниці продукції від і- го постачальника до j- споживача:

. (3.1)

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

Окреслена постановка задачі вимагає рівності загальної суми запасу вантажу загальній сумі потреб у ньому:

(3.2)

Якщо така умова виконується, то таку транспортну задачу називають закритою (з правильним балансом) – ситуація, коли сума запасів постачальників дорівнює сумі потреб (попиту) споживачів, якщо є не виконується, то транспортну задачу називають відкритою (з неправильним балансом) – ситуація, коли сума запасів постачальників не дорівнює сумі потреб (попиту) споживачів.

Оскільки наперед невідомо, скільки вантажу потрібно перевезти від постачальника до споживача щоб план був оптимальним, то позначимо його через . Вартість перевезення усього вантажу від постачальника до споживача Z. Тоді, цільова функція матиме вигляд:

→ min, (3.3)

де - кількість продукції, що перевозиться від і- го постачальника до j- споживача;

- вартість перевезення одиниці продукції від і- го постачальника до j- споживача.

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

1) кількість вантажу, який потрібно перевезти до пункту В з усіх пунктів постачання, рівна , а споживачеві В потрібно одиниць вантажу, тому, враховуючи те, що всі потреби повинні бути задоволеними, можемо записати обмеження стосовно потреб: ;

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

На основі цих рівнянь формується система рівнянь-обмежень.

Приклад 1: на трьох складах підприємства є запаси продукції в кількості 120, 100, 80 одиниць. Попит на продукцію у магазинах складає 90, 90, 120 одиниць. Дана про вартість перевезень (грн.) від підприємства-постачальника та магазинів подано у таблиці 3.1.

Таблиця 3.1 –Матриця вартості перевезень

Скласти економіко-математичну модель плану перевезень вантажів, щоб витрати були мінімальними.

Розв’язання: Транспортна задача є закритою, оскільки попит на продукцію (90+90+120=300) співпадає із кількість запасів у постачальника (120+100+80=300).

Обмеження на невідомі використовуються двох типів.

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

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

Цільова функція матиме вигляд:

→ min.

3.2. Транспортна задача в середовищі Microsoft Excel

Розв’яжемо приклад 1 (транспортна задача) за допомогою Microsoft Excel.

Порядок розв’язування задачі ЛП:

1) створити документ Microsoft Excel, занести дані з таблиці 3.1 про вартість перевезень. Будуємо таблицю – матриця рішень, вказуємо величину запасів та попит на продукцію. Виділяємо комірку для цільової функції (рис. 3.1).

Рисунок 3.1 – Розв’язування транспортної задачі за допомогою Microsoft Excel

2) В комірку Е14 записуємо знак “=” і використовуємо: Вставка → Функція → Математичні → СУММПРОИЗВ (А4:С6; А9:С11) →Оk (рис. 3.2).

Рисунок 3.2 – Розв’язування транспортної задачі за допомогою Microsoft Excel

3) В комірку D9 записується формула сумування змінних у першому рядку, що відповідає запасам першого постачальника, записуємо знак “=” і використовуємо: Вставка → Функція → СУММ (А9:С9) →Оk (рис. 3.3).

Аналогічно здійснюється сумування змінних у другому та третьому рядках.

Рисунок 3.3 – Розв’язування транспортної задачі за допомогою Microsoft Excel

4) В комірці А12 записується формула сумування змінних в першому стовпці, що відповідає потребі першого споживача. Записуємо знак “=” і використовуємо: Вставка → Функція → СУММ (А9:А11) →Оk (рис. 3.4).

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

Рисунок 3.4 – Розв’язування транспортної задачі за допомогою Microsoft Excel

5) Відмітити комірку Е14 і активізувати режим Сервіс → Поиск решения. Заповнити рядок Установить целевую ячейку, включити один з варіантів оптимізації – Минимальному значению, заповнити рядок Изменяя ячейки посиланням на блок А9:С11 (рис. 3.5).

Рисунок 3.5 – Розв’язування транспортної задачі за допомогою Microsoft Excel

6) Заповнити вікно Ограничения обмеженнями за рядками та стовпцями змінних, що відповідає запасам постачальників та потребам споживачів (рис. 3.6).

Рисунок 3.6 – Розв’язування транспортної задачі за допомогою Microsoft Excel

7) Заповнивши обмеження, отримаємо (рис. 3.7):

Рисунок 3.7 – Розв’язування транспортної задачі за допомогою Microsoft Excel

8) Вибираємо Параметры та режим Линейная модель і Неотрицательные значения і натаскаємо Оk (рис. 3.8).

Рисунок 3.8 – Розв’язування транспортної задачі за допомогою Microsoft Excel

9) Виконавши ці дії, потрібно натиснути кнопку Выполнить. Після завершення обчислень з’явиться вікно Результаты поиска решения, у якому відображено повідомлення про результат роботи (рис. 3.9).

Рисунок 3.9 – Розв’язування транспортної задачі за допомогою Microsoft Excel

Отже, мінімальні витрати перевезення становлять 1060 грн.

Дата добавления: 2014-01-03