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

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

Ця сторінка призначена для навчання студентів розв’язанню однієї з задач лінійного програмування − транспортної задачі. Її постановка така. Є m постачальників вантажу (складів) з запасами a1, a2, ..., am. Далі, є n отримувачів вантажу (магазинів) з потребами b1, b2, ..., bn. Задана також матриця C вартостей перевезень розміром m×n. Кожен її елемент cij − це вартість перевезення одиниці товару з i-го складу до j-го магазину. Треба так спланувати перевезення, щоб перевезти весь можливий вантаж за мінімальну загальну вартість.

З теорією розв’язання транспортних задач можна ознайомитися, наприклад, в [1].

Введення вхідних даних

Введіть у наступних областях введення запаси, потреби та матрицю вартостей. Запаси та потреби вводяться у вигляді одновимірних векторів. Числа розділяйте пробілами. Кількість чисел у цих векторах визначає розміри задачі m і n. Матриця вартостей − двовимірна, її розміри повинні бути m×n. Числа в кожному рядку матриці вартостей розділяйте пробілами, а рядки − символом переведення рядка, тобто натискайте Enter (чи Return).

Далі оберіть метод побудови початкового плану перевезень та натисніть кнопку "Рахувати". Буде побудований початковий план перевезень. Обираючи в цьому плані ту чи іншу вільну клітинку, можна клацнути на ній мишкою та подивитися: чи треба вводити її у базис. Якщо змінну можна ввести у базис, то відповідний цикл перекидання вантажу (кутові точки) буде виділений символами ©. Якщо при цьому можна вивести з базису кілька змінних (вироджений розв’язок), виводиться змінна з максимальною вартістю. При кількох одинакових вартостях виводиться перша, що зустрінеться. Якщо ж жодну змінну ввести у базис не вдається, то оптимальний план перевезень (або один з оптимальних планів, якщо розв’язок не єдиний) досягнутий.

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

Запаси ai =
Потреби bj =
Матриця вартостей:

Метод побудови початкового плану: