a
b
c
d
x
y
z
AC
i
Randomize
Про калькулятор методу потенціалів
Розв'яжіть транспортні задачі методом потенціалів онлайн — знайдіть початковий опорний план та ітеруйте з детальним покроковим розв'язком. з повним, детальним, покроковим описом розв'язань, що розв'язує задачі лінійного програмування розміром до 20×20 з коефіцієнтами таких типів: десяткові числа та дроби.
Щоб почати обчислення, спочатку необхідно ввести розміри задачі у поля вводу у верхній частині екрана, а також вибрати потрібну операцію з бічного меню.
Нижче знаходиться вікно вводу, де за допомогою клавіатури потрібно ввести коефіцієнти, обмеження та значення правих частин. Тут також розташована панель керування вводом, яка спрощує роботу із задачами ЛП і містить такі елементи керування:
- Перший елемент дозволяє розгорнути вікно вводу. Це може бути особливо корисно, коли таблиця не вміщається повністю на екрані. Якщо таблиця все ще не повністю видна після розгортання вікна, можна змінити масштаб за допомогою кнопок + / -;
- Другий елемент копіює поточні вхідні дані задачі до буфера пам'яті. Це може бути корисно, коли ви часто розв'язуєте ту саму задачу ЛП або потрібно переносити дані між операціями;
- Останній елемент вставляє раніше скопійовані вхідні дані, що дозволяє відновити дані задачі лише кількома кліками замість повторного введення вручну;
Далі внизу знаходиться панель інструментів, яка дозволяє налаштувати калькулятор та спростити роботу з ним. Вона візуально розділена на три частини, кожна з яких відповідає за таку функціональність:
- Перша частина дозволяє вибрати формат чисел при відображенні результату розв'язання. Також можна вимкнути покрокові коментарі, якщо ви вже розумієте метод і потребуєте лише перевірки власних обчислень, або приховати покрокове розв'язання повністю, якщо потрібна лише кінцева відповідь;
- Друга частина містить кнопки для зміни розмірів таблиці вводу, очищення окремих коефіцієнтів або всього вводу, а також головну кнопку зі знаком рівності, що переводить на екран розв'язання. Всі ці кнопки продубльовані клавіатурними скороченнями. Наведіть курсор на кнопку, щоб побачити відповідну клавішу у підказці. Також можна використовувати клавіші зі стрілками для переміщення курсора між полями вводу;
- Остання частина дозволяє вибрати кількість знаків після коми для округлення нецілих результатів. Попередній перегляд показує, як виглядатимуть округлені значення;
Що таке метод потенціалів (транспортна задача)?
Метод потенціалів (метод МОДІ) розв'язує збалансовану транспортну задачу, яка прагне перевезти товари від n постачальників до m споживачів з мінімальними загальними витратами при обмеженнях на запаси та потреби. Задача є збалансованою, коли загальна пропозиція дорівнює загальному попиту. Метод працює з базисним допустимим розв'язком, що складається рівно з n + m - 1 невироджених розподілів, і ітеративно покращує його шляхом знаходження та перерозподілу по циклах покращення.
Як розв'язати транспортну задачу методом потенціалів?
Починайте з пошуку початкового базисного допустимого розв'язку методом північно-західного кута або аналогічною евристикою. Обчисліть потенціали постачальників u_i та потенціали споживачів v_j, розв'язавши u_i + v_j = c_ij для кожної базисної клітинки. Обчисліть скорочені витрати d_ij = c_ij - u_i - v_j для всіх небазисних клітинок; якщо всі скорочені витрати невід'ємні — поточний розв'язок оптимальний. Інакше оберіть клітинку з найбільш від'ємними скороченими витратами як вхідну, побудуйте замкнений цикл через базисні клітинки та перемістіть максимально можливий потік по циклу для покращення цілі. Повторюйте, доки всі скорочені витрати не стануть невід'ємними.
Приклад розв'язання транспортної задачі методом потенціалів
Методом північно-західного кута будуємо перший опорний план транспортної задачі:
Знаходимо потенціали для всіх споживачів і постачальників із співвідношення Ui + Vj = Cij, де:
Ui — потенціал i-го постачальника;
Vj — потенціал j-го споживача;
Cij — вартість перевезення товарів у базисній клітинці, розташованій у i-му рядку, j-му стовпці;
Потім обчислюємо оцінки небазисних клітинок за співвідношенням Oij = Cij - (Ui + Vj), де
Oij — вартість перевезення товарів у відповідній небазисній клітинці;
Оскільки серед оцінок є від'ємні значення, опорний план можна покращити;
Для цього вводимо до базису клітинку з найменшою від'ємною оцінкою;
Для введення клітинки до базису відносно неї будується цикл;
Перша вершина циклу знаходиться в клітинці, яка вводиться до базису;
Всі інші вершини — у базисних клітинках;
Цикл показує порядок перерозподілу ресурсів при введенні клітинки до базису;
Порядок перерозподілу визначається знаками + і -, які чергуються у клітинках, де розташовані вершини циклу;
У клітинці, що вводиться до базису, завжди стоїть знак +;
Знаходимо потенціали для всіх споживачів і постачальників із співвідношення Ui + Vj = Cij, де:
Ui — потенціал i-го постачальника;
Vj — потенціал j-го споживача;
Cij — вартість перевезення товарів у базисній клітинці, розташованій у i-му рядку, j-му стовпці;
Потім обчислюємо оцінки небазисних клітинок за співвідношенням Oij = Cij - (Ui + Vj), де
Oij — вартість перевезення товарів у відповідній небазисній клітинці;
Оскільки серед оцінок немає від'ємних значень, опорний план можна вважати оптимальним;
(3 * 0) + (1 * 1) + (1 * 2) + (5 * 0) + (5 * 0) = 3
3
Часті запитання
Для чого використовується метод потенціалів (транспортна задача)?
Він розв'язує транспортну задачу — перевезення товарів від кількох постачальників до кількох споживачів з мінімальною загальною вартістю за заданих обсягів постачання, обсягів попиту та вартостей перевезення одиниці товару.
Що означають «збалансована» та «незбалансована» задача?
Задача є збалансованою, коли загальне постачання дорівнює загальному попиту. Коли вони відрізняються, метод додає фіктивного постачальника або споживача, щоб поглинути надлишок, а потім розв'язує збалансований варіант.
Що таке потенціали u та v?
Це двоїсті змінні, по одній на кожного постачальника (u) і кожного споживача (v). Вони перевіряють оптимальність: якщо для кожної порожньої клітинки вартість мінус (u + v) є невід'ємною, поточний план перевезень оптимальний.
Як читати оптимальний план?
Результат показує, скільки одиниць перевозити кожним маршрутом від постачальника до споживача, та мінімальну загальну вартість. Маршрути, що не використовуються, мають нульове перевезення.