ня системі рівнянь і на невиражденность; у разі виродження плану додаємо умовно заповнені клітини за допомогою «0»;
· Для опорного плану визначаються потенціали ui і vj, що відповідають базисним клітинам, за умовою: ui + vj=cij
Таких рівнянь буде m + n - 1, а змінних буде m + n. Для їх визначення одну із змінних вважають рівною будь-якому постійному значенню. Зазвичай приймають u1=0.
· Після цього для небазисних клітин опорного плану визначаються оцінки c ij, де c ij=ui + vj - c ij
При цьому якщо c ij Ј0, то опорний план оптимальний, якщо ж серед c ij виявиться хоча б один позитивний елемент, то опорний план можна поліпшити.
· Поліпшення опорного плану здійснюється шляхом цілеспрямованого перенесення з клітки в клітку транспортної таблиці окремих перевезень без порушення балансу по деякому замкнутому циклу.
Циклом транспортної таблиці називається послідовне з'єднання замкнутої ламаною лінією деяких клітин, розташованих в одному ряду (рядку, стовпці), причому число клітин в одному ряду має дорівнювати двом.
Кожен цикл має парне число вершин, одна з яких у клітці з небазисной змінної, інші вершини в клітинах з базисними змінними. Клітини відзначаються знаком «+», якщо перевезення в даній клітині збільшуються і знаком «-» в іншому випадку. Цикл починається і закінчується на обраної небазисной змінної і відзначається знаком «+». Далі знаки чергуються.
Кількість одиниць продукту, переміщуваного з клітки в клітку по циклу, постійно, тому сума перевезень в кожному рядку і в кожному стовпці залишаються незмінними. Вартість всього плану змінюється на ціну циклу.
Ціна циклу - це вартість перевезення одиниці продукту по циклу з урахуванням знаків вершин.
Поліпшення опорного плану здійснюється шляхом знаходження циклу з негативною ціною.
Якщо критерій оптимальності не виконується, то переходимо до наступного кроку. Для цього:
а) в якості початкової небазисной змінної приймається та, у якої оцінка cij має максимальне значення;
б) складається цикл перерахунку;
в) знаходиться число перерахунку по циклу: число X=min {Xij}, де Xij - числа в заповнених клітинах зі знаком «-»;
г) складається нова таблиця, додаючи X в плюсові клітини і відбираючи X з мінусових клітин циклу;
Через кінцеве число кроків (циклів) обов'язково приходять до відповіді, так як транспортна задача завжди має рішення.
2. Математична постановка задачі про оптимальні перевезеннях
У загальному вигляді завдання можна представити таким чином: в m пунктах виробництва A 1, A 2, ..., A m мається однорідний вантаж у кількості відповідно a 1, a 2, ..., am. Цей вантаж необхідно доставити в n пунктів призначення B 1, B 2, ..., B n у кількості відповідно b 1, b 2, ..., bn. Вартість перевезення одиниці вантажу (тариф) з пункту A i в пункт B j дорівнює c ij.
Потрібно скласти план перевезень, що дозволяє вивести всі вантажі і має мінімальну вартість.
Позначимо через x ij кількість вантажу, що перевозиться з пункту Ai, в пункт B j. Запишемо умови задачі у розподільну таблицю, яку будемо використовувати для знаходження рішення (таблиця. 2.1).
Таблиця 2.1. Модель розподільної таблиці
B i A i B 1 B 2 ... B j ... B nb 1 b 2 ... bi ... bn A 1 a 1 c 11 x 11 c 12 x 12 ... з 1j x 1j ... c 1n x 1n A 2 a 2 c 21 x 21 c 22 x 22 ... c 2 jx 2j ... c 2n x 2n ..................... A iaic i1 x i1 c i2 x i2 ... c ij x ij ... c in x in ..................... A mamc m1 x m1 c m2 x m2 ... c mj x mj ... c mn x mn
Математична модель транспортної задачі має вигляд
при обмеженнях:
Оптимальним рішенням задачі є матриця
задовольняє системі обмежень і доставляє мінімум цільової функції.
3. Метод рішення задачі про оптимальні перевезеннях засобами Ms Excel
Знаходження оптимального плану перевезень із застосуванням комп'ютерної програми Ms Excel здійснюється за допомогою функції «Пошук рішення».
Схема виконання:
. Для зручності розрахунків необхідно окремо створити матрицю, отображающую вартість перевезень (C ij) (рисунок 3.1.), А також матрицю, яка повинна буде відображати шуканий план перевезень (малюнок. 3.2.).
Малюнок 3.1 - Фрагмент вікна програми Ms Excel: Модель таблиці «Вартість перевезен...
