2.2 Діагональний
метод або метод північно-західного
кута
При цьому методі на кожному
кроці побудови першого опорного плану
заповнюється ліва верхня клітина (північно-західний
кут) залишилася, таблиці. При такому методі
заповнення таблиці починається з клітини
невідомого і закінчується в клітці невідомого
, тобто йде як би по діагоналі
таблиці перевезень.
Приклад(3):
Заповнення таблиці починається
з її північно-західного кута, тобто клітини
з невідомим . Перша база може повністю задовольнити
потребу першого замовника .
Вважаючи , вписуємо це значення в клітку і виключаємо з розгляду перший
стовпець. На базі залишається змінений запас . У решти нової таблиці з трьома
рядками і чотирма стовпцями ; Північно-західним кутом буде клітка для невідомого . Перша база з запасом може повністю задовольнити
потребу другого замовника . Вважаємо = 110, вписуємо це значення в клітку і виключаємо з розгляду другий
стовпець. На базі залишається новий залишок
(запас) . У решти нової таблиці з трьома
рядками і трьома стовпцями північно-західним кутом буде
клітка для невідомого . Тепер третій замовник може прийняти весь запас з
бази .
Вважаємо = 20 , Вписуємо це значення в клітку і виключаємо з розгляду перший
рядок. У замовника з залишилася ще не задоволеною
потребу .
Тепер переходимо до заповнення
клітини для невідомого і т.д.
Через шість кроків у нас залишиться одна
база із запасом вантажу (залишком
від попереднього кроку) і один пункт з потребою . Відповідно до цього є одна вільна клітина,
яку і заповнюємо, поклавши = 200 . План складений. Базис утворений
невідомими . Правильність складеного
плану легко перевірити, підрахувавши
суми чисел, що стоять в заповнених клітках
по рядках і стовпцях.
Загальний обсяг
перевезень в тонно-кілометрах для цього
плану складе:
=70*170+50*110+15*20+40*80+60*70+11*50+25*200=30650
2.1 Метод найменшої
вартості
При цьому методі на кожному
кроці побудови опорного плану першою
заповнюється та клітина залишилася, таблиці,
яка має найменший тариф. Якщо така клітина
не єдина, то заповнюється кожна з них.
Приклад
(4):
У даному випадку заповнення
таблиці починається з клітки для невідомого , Для якого ми маємо значення = 10, найменше з усіх значень . Ця клітина знаходиться на
перетині третього рядка та другого стовпця,
відповідним третій базі і другому замовнику . Третя база може повністю задовольнити
потребу другого замовника .
Вважаючи , вписуємо це значення в клітку і виключаємо з розгляду другий
стовпець. На базі залишається змінений запас = 140 . У решти нової таблиці з трьома
рядками і чотирма стовпцями кліткою з найменшим значенням
клітина, де . Заповнюємо описаним вище
способом цю клітку і аналогічно заповнюємо
наступні клітини. У результаті виявляються
заповненими (у наведеній послідовності) такі клітини:
На п'ятому кроці клітин з найменшими
значеннями виявилося дві
. Ми заповнили клітку
для , поклавши . Можна було вибрати для заповнення
іншу клітку, поклавши , що призведе в результаті до
іншого опорному плану.
Загальний
обсяг перевезень в тонно-кілометрах для
цього плану складе:
.= 70*20+15*100+70*180+80*150+10*110+11*120+25*20=30420
Зауваження. У діагональному методі не враховуються
величини тарифів, у методі ж найменшої
вартості ці величини враховуються, і
часто останній метод призводить до плану
з меншими загальними витратами (що і має
місце в нашому прикладі), хоча це й не
обов'язково.
Крім розглянутих вище способів
іноді використовується, так званий, метод
Фогеля. Суть його полягає в наступному:
У розподільній таблиці по рядках і стовпцях
визначається різниця між двома найменшими
тарифами. Відзначається найбільша різниця.
Далі в рядку (стовпці) з найбільшою різницею
заповнюється клітка з найменшим тарифом.
Рядки (стовпці) з нульовим залишком вантажу
надалі в розрахунок не приймаються. На
кожному етапі завантажується тільки
одна клітина. Розподіл вантажу провадиться,
як і раніше. .
РОЗДІЛ 3. КРИТЕРІЙ ОПТИМАЛЬНОСТІ БАЗИСНОГО
РОЗВ’ЯЗКУ ТРАНСПОРТНОЇ ЗАДАЧІ
3.1 Методи відшукання
оптимального рішення
Зі сказаного в попередньому
пункті випливає наступний критерій оптимальності
базисного рішення транспортної задачі: якщо для деякого базисного
плану перевезень алгебраїчні суми тарифів
за циклами для всіх вільних клітин негативні,
то цей план оптимальний.
Звідси випливає спосіб відшукання оптимального
рішення транспортної задачі, що полягає
в тому, що, маючи деякий базисне рішення,
обчислюють алгебраїчні суми тарифів
для всіх вільних клітин. Якщо критерій
оптимальності виконаний, то дане рішення
є оптимальним, якщо ж є клітини з негативними
алгебраїчними сумами тарифів, то переходять
до нового базису, виробляючи перерахунок
по циклу, відповідному однієї з таких
клітин. Отримане таким чином нове базисне
рішення буде краще вихідного - витрати
на його реалізацію будуть меншими. Для
нового рішення також перевіряють здійснимість
критерію оптимальності та в разі потреби
знову здійснюють перерахунок по циклу
для однієї з кліток з негативною алгебраїчною
сумою тарифів і т.д.
Через кінцеве число кроків
приходять до шуканого оптимальному базисного
рішення.У разі якщо алгебраїчні суми
тарифів для всіх вільних клітин позитивні,
ми маємо єдину оптимальне рішення, якщо
ж алгебраїчні суми тарифів для всіх вільних
клітин ненегативні, але серед них є алгебраїчні
суми тарифів, рівні нулю, то оптимальне
рішення не єдина: при перерахунку за циклом
для клітини з нульовою алгебраїчною сумою
тарифів ми отримаємо оптимальне ж рішення,
але відмінне від вихідного (витрати по
обох планів будуть однаковими).
У залежності від методів підрахунку
алгебраїчних сум тарифів для вільних
клітин розрізняють два методи відшукання
оптимального вирішення транспортної задачі:
1. Розподільний
метод. При цьому методі для кожної порожній
клітини будують цикл і для кожного циклу
безпосередньо обчислюють алгебраїчну
суму тарифів.
2. Метод потенціалів. При цьому методі попередньо
знаходять потенціали баз і споживачів,
а потім обчислюють для кожної порожній
клітини алгебраїчну суму тарифів за допомогою
потенціалів.
Переваги методу потенціалів в порівнянні
з розподільним методом полягають у тому,
що відпадає необхідність побудови циклів
для кожної з порожніх клітин і спрощується
обчислення алгебраїчних сум тарифів.
Цикл будується тільки один - той, за яким
здійснюється перерахунок.
Застосовуючи метод потенціалів,
можна говорити не про знак алгебраїчних
сум тарифів, а про порівняння непрямих тарифів з істинними.
Вимога неотрицательности алгебраїчних
сум тарифів замінюється умовою, що непрямі
тарифи не перевершують істинних.
Слід мати на увазі, що потенціали
(так само як і цикли) для кожного нового
базисного плану визначаються заново.
Вище розглядалася закрита
модель транспортної задачі, з правильним
балансом, коли виконується умова a = b. У разі виконання a ≠ b (відкрита
модель) баланс транспортної задачі може
порушуватися в 2-ух напрямках:
- Сума запасів у пунктах відправлення
перевищує суму поданих заявок (транспортна
задача з надлишком запасів).
- Сума поданих заявок перевищує
наявні запаси (транспортна задача з надлишком
заявок).
Розглянемо послідовно ці два
випадки:
Транспортна
задача з надлишком запасів.
Зведемо її до раніше розглянутої
транспортної задачі з правильним балансом.
Для цього, понад наявні n пунктів призначення
В 1, B 2, ... , B n, введемо ще один, фіктивний,
пункт призначення B n +1, якому припишемо фіктивну заявку,
рівну надлишку запасів над заявками
b n +1 = å а i - å b j (де i = 1 ,..., m; j = 1 ,..., n),
а вартість перевезень з усіх
пунктів відправлення у фіктивний пункт
призначення b n +1 будемо вважати рівною нулю.
Введенням фіктивного пункту призначення
B n +1 з його заявкою b n +1 ми зрівняли баланс транспортної
задачі, і тепер її можна вирішувати, як
звичайну транспортну задачу з правильним балансом.
Транспортна
задача з надлишком заявок.
Це завдання можна звести до
звичайної транспортної задачі з правильним
балансом, якщо ввести фіктивний пункт
відправлення A m +1 з запасом a m +1 рівним невистачаючому запасу,
і вартість перевезень з фіктивного пункту
відправлення в усі пункти призначення
прийняти рівною нулю.
РОЗДІЛ
4. ПРИКЛАДИ РОЗВ’ЯЗАННЯ ТРАНСПОРТНОЇ
ЗАДАЧІ ПРО ВИБІР ВИГІДНОГО МАРШРУТУ
4.1 Приклад рішення
транспортної задачі методом
потенціалів
Компанія
контролює три фабрики А1, А2, А3, здатні виготовляти
відповідно 150, 60 та 80 тис. од. продукції
щотижня. Вона уклала договір із чотирма
замовниками В1, В2, В3, В4, яким потрібно
щотижня доставляти відповідно 110, 40, 60
та 80 тис. од. продукції. Вартість транспортування
1000 од. продукції замовникам з кожної фабрики
наведена в таблиці 5:
Вартість транспортування
продукції
Визначити оптимальний план
перевезень продукції від кожної фабрики
до замовників, що мінімізує загальну
вартість транспортних послуг.
Побудова
математичної моделі.
Нехай 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)
та складемо її перший опорний план у цій
таблиці методом мінімальної вартості.
Таблиця 6:
Загальна вартість перевезень
продукції згідно з першим опорним планом
визначається у такий спосіб:
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 додаємо до відповідних чисел, що розміщені
в клітинках зі знаком «+», та віднімаємо
від чисел, що розміщені в клітинках, позначених
знаком «–».
У даному разі min {60; 40}= 40 тобто . Виконавши
перерозподіл перевезень продукції згідно
із записаними правилами, дістанемо такі
нові значення: для клітинки А1B3 — 40 од. продукції, а для А2B3 – (60 – 40) = 20 од., а для А2B4 – (0 + 40) = 40 од. Клітинка А1B4 звільняється і в новій таблиці
буде порожньою. Усі інші заповнені клітинки
першої таблиці, які не входили до циклу,
переписуємо у другу таблицю без змін.
Кількість заповнених клітинок у новій
таблиці також має відповідати умові невиродженості
плану, тобто дорівнювати (n + m – 1).
Отже, другий опорний план транспортної
задачі матиме такий вигляд (табл.7):
Розрахуємо значення цільової
функції відповідно до другого опорного
плану задачі:
Z2 = 4 х 110 + 2 х 40 + 1 х 20 + 2 х 40 + 1 х 40 + 2 х 40 = 740
(ум. од.).