Метод північно-західного кута
Беремо «північно-західну» клітку матриці - це клітина А1В1 і записуємо в неї максимально можливу поставку - 40 т (обсяг вивантаження 40 т, ресурси станції навантаження 100 т). Оскільки ресурси станції навантаження А1 не вичерпані, слідуємо по першому рядку вправо і записуємо в клітку А1В2 кореспонденцію рівну максимально можливій величині - 60 т. Таким чином виходить, що ресурси станції А1 повністю використані, однак попит станції вивантаження В2 не задоволений. Тоді від клітини А1В2опускаемся вниз до клітини А2В2 і записуємо в неї поставку рівну 20 т. Описаним способом слідуємо далі до останньої «південно-західної» клітини матриці. В результаті отримуємо допустимий план перевезень вантажу. Вантажообіг або функціонал транспортної задачі (сума творів кореспонденцій на відстань, розрахована за табл. 1.3) складе:
Fсев-зап. = 40 ∙ 10 + 60 ∙ 9 + 20 ∙ 7 + 110 ∙ 13 + 20 ∙ 6 + 30 ∙ 7 + 60 ∙ 1 + + 30 ∙ 2 = 2960 ткм [см. формулу (1.4)].
Після розстановки кореспонденції матриця перевіряється на виродження, т. Е. Має виконуватися умова
, ( 1.5)
де m - кількість рядків, n - кількість стовпців, Nбаз - кількість базисних клітин.
Іншими словами, кількість клітин матриці, що містять кореспонденції, має дорівнювати сумі рядків і стовпців без одиниці. У нашому випадку ця умова дотримується: 8 = 4 + 5 - 1. План транспортної задачі, що відповідає умові (n + m - 1) називають базисним. Засадничими також називаються клітини матриці, що містять поставки. Клітини, в яких поставки відсутні, називаються небазисними.
|
|
|
Метод північно-західного кута має істотний недолік. При його використанні не враховуються значення показників критерію оптимальності в клітинах матриці. Тому поставки можуть потрапити в «дорогі» клітини зі свідомо високою ціною або великою відстанню. Опорний план, отриманий з використанням даного методу, як правило, далекий від оптимального, що обумовлює великий обсяг подальших розрахунків для доведення його до оптимального. Описаний метод зазвичай не застосовується.
Найбільш доцільним при ручному вирішенні транспортних задач вважається метод мінімальної вартості або, як його ще називають, метод найменшого елемента в матриці. Суть його в наступному. У транспортній матриці вибирається клітина з мінімальною вартістю (відстанню). У нашому випадку це клітка А3В5. У неї записується максимально можлива поставка - це 90 т (табл. 1.4).
Таблиця 1.4
Метод найменшого елемента в матриці
Далі відшукуються клітина, що має наступне за величиною відстань. В нашій матриці це дві клітини з відстанню 2 км в п'ятому стовпці. Однак в ці клітини поставки кореспонденцію вантажів ставити не можна, оскільки попит станції В5 повністю задоволений зі станції А3. Тому стовпець 5 з подальшої побудови плану виключаємо. Наступні за величиною показника критерію оптимальності клітини з відстанню 4 км це клітини А2В1 і А4В2. Вибираємо одну з них, наприклад, А2В1 і записуємо в неї поставку 40 т. Далі йде клітина А4В2 - поставка 30 т, потім А1в4 - 50 т, А2В2 - 50 т. Всі ресурси, що залишилися по станціях навантаження розподіляємо між клітинами третього стовпчика в клітини А1В3 і А2В3. Після складання опорного плану, щоб уникнути помилок доцільно перевірити баланси навантаження, вивантаження і суми кореспонденцій по рядках і по стовпцях матриці. Функціонал F плану, складеного методом найменшої вартості, дорівнює 2150 ткм. Таким чином, побудований план значно краще плану, побудованого методом північно-західного кута. Однак число базисних клітин в плані - 7. Це не відповідає умові ( 1.5), т. Е. Менше необхідного на одиницю. Такий план математики назвали виродженим (випадок виродження). Випадок виродження «лікують» шляхом введення в матрицю потрібної кількості базисних клітин з нульовими поставками. Нульову поставку необхідно вводити в матрицю поруч з базисної кліткою, яка зумовила «пропажу» базисної клітини. менше необхідного на одиницю. Такий план математики назвали виродженим (випадок виродження). Випадок виродження «лікують» шляхом введення в матрицю потрібної кількості базисних клітин з нульовими поставками. Нульову поставку необхідно вводити в матрицю поруч з базисної кліткою, яка зумовила «пропажу» базисної клітини. менше необхідного на одиницю. Такий план математики назвали виродженим (випадок виродження). Випадок виродження «лікують» шляхом введення в матрицю потрібної кількості базисних клітин з нульовими поставками. Нульову поставку необхідно вводити в матрицю поруч з базисної кліткою, яка зумовила «пропажу» базисної клітини.
|
|
|
|
|
|
Для того щоб зрозуміти, чому «пропадають» поставки, звернемося до методу північно-західного кута. З табл. 1.3 випливає, що як тільки була заповнена «північно-західна» клітина, поруч з нею відразу з'являється сусідня базисна клітина, потім ще одна і т.д. Ланцюжок базисних клітин без розриву слід до «південно-східного кута» матриці. Однак якби в цьому ланцюжку з'явилася клітина, що зв'язує постачальника і споживача з рівними обсягами навантаження і вивантаження, і в неї була б записана така ж поставка, то це призвело б до зникнення базисної клітини. Описана ситуація мала місце в табл. 1.4, коли в клітку А3В5 була введена кореспонденція об'ємом 90 т, що дорівнює обсягам навантаження і вивантаження за відповідними станціям. Тому необхідно ввести в план додаткову базисну клітку з нульовою поставкою. Ця клітина повинна стояти поряд з кліткою А3В5. З трьох сусідніх клітин слід вибрати клітку з мінімальним відстанню, наприклад, А2В5. Записуємо в неї кореспонденцію, рівну «0» (табл. 1.5).
|
|
|
Таблиця 1.5
Додавання нульовий поставки
Таким чином, причиною виродження плану транспортної задачі є наявність постачальників і споживачів з рівними обсягами навантаження і вивантаження або рівними обсягами сум навантаження і вивантаження за кількома станцій в різноманітних комбінаціях. Такі випадки необхідно вміти знаходити для того, щоб правильно визначати місця для нульових поставок. У процесі виконання завдання можливі випадки, коли число базисних клітин перевищує величину «n + m - 1». Це означає появу помилки внаслідок того, що при побудові опорного плану в якусь клітку була введена не максимально можлива поставка.
Операція 2. Перевірка плану на оптимальність.
Операція 2.1. Розрахунок потенціалів.
Перевірка плану транспортної задачі в описуваному методі на оптимальність здійснюється за допомогою потенціалів. Потенціали - це такі числа, які за певними правилами призначаються кожному рядку і кожному стовпці. Потенціали строкобозначім ui, потенціали стовпців - vj. Вони можуть приймати будь-які значення. Однак зручніше працювати з позитивними, цілими і відносно невеликими числами. Такий потенціал спочатку призначається будь-якому рядку або стовпцю. Рекомендуємо виконати наступні дії. Виберемо базисну клітку з максимальною відстанню. В нашій матриці це клітина А2В3. Дамо рядку, в якій знаходиться ця клітина, потенціал, рівний 0 (u3 = 0). Далі можна розрахувати потенціали стовпців по базисним клітинам рядки 3 по формулі
. ( 1.6)
Потенціал першого стовпчика v1 = u2 + c21 = 0 + 4 = 4;
другого: v2 = u2 + c22 = 0 + 7 = 7;
третього: v3 = u2 + c23 = 0 + 13 = 13;
п'ятого: v5 = u2 + c25 = 0 + 2 = 2.
Розраховані потенціали записуємо навпаки відповідних стовпців нижче матриці. Оскільки за всіма базисним клітинам рядки 2 потенціали стовпів знайдені, переходимо до розрахунку потенціалів рядків.
Потенціал рядка 1 розраховуємо по знайденому потенціалу стовпчика 3 і базисної клітці А1В3 за формулою
, ( 1.7)
де u1 = v3 - c31 = 13 - 8 = 5.
Для рядка 3 потенціал дорівнюватиме:
u3 = v5 - c35 = 2 - 1 = 1.
Також розраховуємо потенціали для всіх рядків і стовпців (табл. 1.6).
Таблиця 1.6
Дата добавления: 2019-09-02; просмотров: 528; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!