Лабораторна робота № 4 за темою: „Розв'язування транспортної задачі лінійного програмування в середовищі ms Excel ”.

Мета роботи: навчитися розв'язувати транспортні задачі лінійного програмування в середовищі MS Excel.

Завдання: 1) розв'язати транспортну задачу лінійного програмування індивідуального варіанту в середовищі MS Excel; 2) скласти звіт.

Приклад транспортної задачі лінійного програмування. Визначити оптимальний план перевезення вантажів.

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

Історично методи лінійного програмування почали розвиватися з дослідження транспортних задач. Вивчення транспортних задач має виключно практичне значення, так як, по-перше, дозволяє знизити транспортні витрати конкретного підприємства на 10- 30%, а по-друге, велику кількість інших прикладних задач можна описати математичними моделями, подібними з моделями транспортних задач.

Методи лінійного програмування діляться на дві групи: універсальні і спеціальні. За допомогою універсальних методів можна розв’язати будь-яку задачу лінійного програмування, в тому числі і транспортну. Спеціальні методи застосовуються для рішення окремих класів задач лінійного програмування. Вони, як правило, простіші універсальних, але застосовуються не для всіх задач. До спеціальних методів відносяться методи розв’язування транспортної задачі, які враховують специфіку її обмежень:

1. всі обмеження задані у вигляді рівнянь;

2. кожне невідоме входить лише в два рівняння;

3. коефіцієнти при невідомих – одиниці.

В даних методичних вказівках ми не задавались ціллю вивчити теоретичні основи рішення транспортних задач. Основна задача – продемонструвати на конкретних прикладах, з якою легкістю в MS Excel можна розв’язувати транспортні задачі різної складності (в тому числі і цілочислові).

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

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

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

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

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

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

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

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

, (закрита) (3)

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

, (4)

. (відкрита) (5)

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

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

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

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

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

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

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

обмеженням по ресурсам

; (6)

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

; (7)

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

. (8)

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

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

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

, (9)

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

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

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

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

і приймаються вартість m перевезень вантажу в цей пункт рівними нулю:

c_i,n+1=0 (i=1,…m).

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

.

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

,

і вартість n перевезень вантажу із цього пункту приймаються рівними нулю.

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

.

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