Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

5.5.4. Приклади розв’язування транспортних задач методом потенціалів

Компанія контролює три фабрики А1, А2, А3, здатні виготовляти відповідно 150, 60 та 80 тис. од. продукції щотижня. Вона уклала договір із чотирма замовниками В1, В2, В3, В4, яким потрібно щотижня доставляти відповідно 110, 40, 60 та 80 тис. од. продукції. Вартість транспортування 1000 од. продукції замовникам з кожної фабрики наведена в табл. 5.10.

Таблиця 5.10

Вартість транспортування продукції

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

Побудова математичної моделі. Нехай xij — кількість продукції, що перевозиться з і-ї фабрики до j-го замовника . Оскільки транспортна задача за умовою є збалансованою, закритою , то математична модель задачі матиме вигляд:

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

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

Загальні витрати, пов’язані з транспортуванням продукції, визначаються як сума добутків обсягів перевезеної продукції на вартості транспортування 1000 од. продукції до відповідного замовника і за умовою задачі мають бути мінімальними. Тому формально це можна записати так:

min Z = 4x11 + 4x12 + 2x13 + 5x14 + 5x21 + 3x22 + x23 +  2x24 +  2x31 + + x32 +4x33 +2x34.

Загалом математична модель сформульованої задачі має вигляд:

min Z = 4x11 + 4x12 + 2x13 + 5x14 + 5x21 + 3x22 + x23 + 2x24 + 2x31 + x32 + + 4x33 +2x34

за умов:

Розв’язання. Запишемо умови задачі у вигляді транспортної таблиці (табл. 5.11) та складемо її перший опорний план у цій таблиці методом мінімальної вартості.

Таблиця 5.11

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

Z1 = 4 х 110 + 5 х 40 + 1 х 60 + 1 х 40 + 2 х 40 = 820 (ум. од.).

Перший опорний план транспортної задачі вироджений, оскільки кількість заповнених клітинок у таблиці дорівнює п’яти, а (m + n – 1) = 3 + 4 – 1 = 6.

Для дальшого розв’язування задачі необхідно в одну з порожніх клітинок записати «нульове перевезення» так, щоб не порушити опорності плану, тобто можна зайняти будь-яку пусту клітинку, яка не утворює замкненого циклу із заповненими клітинами. Наприклад, заповнимо нулем клітинку А2В4. Тепер перший план транспортної задачі є невиродженим, і його можна перевірити на оптимальність методом потенціалів.

На основі першої умови оптимальності ui + vj = cij складемо систему рівнянь (для заповнених клітин таблиці) для визначення потенціалів першого опорного плану:

Записана система рівнянь є невизначеною, і один з її розв’язків дістанемо, узявши, наприклад, v4 = 0. Тоді всі інші потенціали однозначно визначаються з цієї системи рівнянь: u1 = 5, u2 = 2, u3 = 2, v1 = – 1, v2 = – 1, v3 = – 1. Ці значення потенціалів першого опорного плану записуємо у транспортну таблицю.

Потім згідно з алгоритмом методу потенціалів перевіряємо виконання другої умови оптимальності ui + vj ≤ cij (для порожніх клітинок таблиці):

А1B2 : u1 + v2 = 5 + (–1) = 4 = 4;

А1B3 : u1 + v3 = 5 + (–1) = 4 > 2;

А2B1 : u2 + v1 = 2 + (–1) = 1 < 5;

А2B2 : u2 + v2 = 2 + (–1) = 1 < 3;

А3B1 : u3 + v1 = 2 + (–1) = 1 < 2;

А3B3 : u3 + v3 = 2 + (–1) = 1 < 4.

Умова оптимальності не виконується для клітинки А1B3. Порушення D13 = (u1 + v3) – c13 = 4 – 2 = 2 записуємо в лівому нижньому кутку відповідної клітинки.

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

Потрібно заповнити клітинку А1B3, в якій є єдине порушення умови оптимальності. Ставимо в ній знак «+». Для визначення клітинки, що звільняється, будуємо цикл, починаючи з клітинки А1B3, та позначаємо вершини циклу почергово знаками «–» і «+». Тепер необхідно перемістити продукцію в межах побудованого циклу. Для цього у порожню клітинку А1B3 переносимо менше з чисел хij, які розміщені в клітинках зі знаком «–». Одночасно це саме число хij додаємо до відповідних чисел, що розміщені в клітинках зі знаком «+», та віднімаємо від чисел, що розміщені в клітинках, позначених знаком «–».

У даному разі , тобто . Виконавши перерозподіл перевезень продукції згідно із записаними правилами, дістанемо такі нові значення: для клітинки А1B3 — 40 од. продукції, а для А2B3 – (60 – 40) = 20 од., а для А2B4 – (0 + 40) = 40 од. Клітинка А1B4 звільняється і в новій таблиці буде порожньою. Усі інші заповнені клітинки першої таблиці, які не входили до циклу, переписуємо у другу таблицю без змін. Кількість заповнених клітинок у новій таблиці також має відповідати умові невиродженості плану, тобто дорівнювати (n + m – 1).

Отже, другий опорний план транспортної задачі матиме такий вигляд (табл. 5.12):

Таблиця 5.12

Розрахуємо значення цільової функції відповідно до другого опорного плану задачі:

Z2 = 4 х 110 + 2 х 40 + 1 х 20 + 2 х 40 + 1 х 40 + 2 х 40 = 740 (ум. од.).

Новий план знову перевіряємо на оптимальність, тобто повторюємо описані раніше дії. Другий опорний план транспортної задачі також неоптимальний (має місце порушення для клітинки А3B1). За допомогою побудованого циклу, виконавши перехід до третього опорного плану транспортної задачі, отримуємо табл. 5.13:

Таблиця 5.13

Визначимо загальну вартість витрат на транспортування продукції згідно з третім опорним планом:

Z3 = 4 х 90 + 2 х 60 + 2 х 60 + 2 х 20 + 1 х 40 + 2 х 20 = 720 (ум. од.).

Перевірка останнього плану на оптимальність за допомогою методу потенціалів показує, що він оптимальний. Тому:

.

За оптимальним планом перевезень перший замовник отримує 90 тис. од. продукції з першої фабрики та 20 тис. од. — з третьої. Другий споживач задовольняє свій попит за рахунок виробництва та перевезення 40 тис. од. продукції з третьої фабрики і т. д. При цьому загальна вартість перевезень всієї продукції є найменшою і становить 720 ум. од.