Методи складання початкового опорного плану

 

 

МІНІСТЕРСТВО ОСВІТА ТА НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ АВІАЦІЙНИЙ УНІВЕРСИТЕТ

Навчально-науковий Інститут Економіки та Менеджменту

Факультет Економіки і Підприємництва

 

 

 

Кафедра економічної кібернетики

 

 

 

 

 

 

КУРСОВА РОБОТА

З ДИСЦИПЛІНИ «ЕКОНОМІЧНА КІБЕРНЕТИКА»

 

 

НА ТЕМУ: «ЗАДАЧА ПРО ВИБІР НАЙБІЛЬШ ЕКОНОМНОГО ВИБОРУ МАРШРУТУ»

 

 

 

 

 

 

 

 

 

 

 

Виконала:

Студентка 2 курсу, група ФЕП-210

Жаб’як Софія Андріївна

 

 

 

 

 

Київ – 2017

 

 

ЗМІСТ

 

 

 

 

 

 

 

 

ВСТУП

Кожна людина щодня, не завжди усвідомлюючи це, вирішує проблему: як отримати найбільший ефект, володіючи обмеженими засобами. Наші засоби та ресурси завжди обмежені. Життя було б менш цікавою, якби це було не так. Не важко виграти бій, маючи армію в 10 разів більшу, ніж у супротивника. Щоб досягти найбільшого ефекту, маючи обмежені кошти, треба скласти план, або програму дій. Раніше план у таких випадках складався на око . У середині XX століття був створений спеціальний математичний апарат, що допомагає це робити з науки . Відповідний розділ математики називається математичним програмуванням. Слово програмування "тут і в аналогічних термінах ( лінійне програмування, динамічне програмування і т.п.) зобов'язана почасти історичного непорозуміння, почасти неточному перекладу з англійської. З програмуванням для ЕОМ математичне програмування має лише те загальне, що більшість виникаючих на практиці задач математичного програмування занадто громіздкі для ручного рахунку, вирішити їх можна тільки за допомогою ЕОМ, попередньо склавши програму. Часом народження лінійного програмування прийнято вважати 1939 р., коли була надрукована брошура Леоніда Віталійовича Канторовича «Математичні методи організації і планування виробництва».

Під назвою транспортна задача об'єднується широке коло завдань з єдиною математичною моделлю. Дані завдання відносяться до завдань лінійного програмування і можуть бути вирішені симплексним методом. Однак матриця системи обмежень транспортної задачі настільки своєрідна, що для її рішення розроблені спеціальні методи. Ці методи, як і симплексний метод, дозволяють знайти початкове опорне рішення, а потім, поліпшуючи його, отримати оптимальне рішення.

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

Мета транспортної діяльності вважається досягнутою при виконанні шести умов:

• потрібний товар;
• необхідної якості;
• в необхідній кількості доставлений;
• в потрібний час;
• в потрібне місце;
• з мінімальними витратами.

Об'єктом вивчення є матеріальні і відповідні їм фінансові, інформаційні потоки, які супроводжують виробничо-комерційну діяльність.

 

РОЗДІЛ 1. ТРАНСПОРТНА ЗАДАЧА ЛІНІЙНОГО ПРОГРАМУВАННЯ

1.1 Загальна постановка, цілі, завдання. Основні типи, види моделей

 

Під назвою "транспортна задача" об'єднується широке коло завдань з єдиною математичною моделлю. Дані завдання відносяться до завдань лінійного програмування і можуть бути вирішені симплексним методом. Однак матриця системи обмежень транспортної задачі настільки своєрідна, що для її рішення розроблені спеціальні методи. Ці методи, як і симплексний метод, дозволяють знайти початкове опорне рішення, а потім, поліпшуючи його, отримати оптимальне рішення. У загальній постановці транспортна задача полягає у знаходженні оптимального плану перевезень деякого однорідного вантажу з m баз n споживачам .

Розрізняють два типи транспортних завдань: але критерієм вартості (план перевезень оптимальний, якщо досягнуть мінімум витрат на його реалізацію) і за критерієм часу (план оптимальний, якщо на його реалізацію витрачається мінімум часу). 

1. Позначимо кількість вантажу, що є на кожній з m баз (запаси), відповідно 

, А загальна кількість наявного в наявності вантажу – a:

2. замовлення кожного із споживачів (потреби) позначимо відповідно   , А загальна кількість потреб - .
3. Тоді за умови  a = b, ми маємо закриту модель, а за умови a ≠ b – відкриту модель транспортної задачі.

Очевидно, у випадку закритої моделі весь наявний вантаж розвозиться повністю, і всі потреби замовників повністю задоволені; у разі ж відкритої моделі або всі замовники задоволені і при цьому на деяких базах залишаються надлишки вантажу (а > b) або весь вантаж виявляється витраченим, хоча потреби повністю не задоволені (а < b).

Так само існують одноетапні моделі задач, де перевезення здійснюється безпосередньо від, наприклад, бази або заводу виробника до споживача, і двохетапні, де між ними є "перевалочний пункт", наприклад - склад.  
План перевезень із зазначенням запасів і потреб зручно записувати у вигляді такої таблиці, званої таблицею перевезень (1): 

Умови a = b або a ≠ b означає, з якою завданням ми маємо справу, із закритою моделлю або відкритою моделлю транспортної задачі. Змінне  означає кількість вантажу, що перевозиться з бази споживачеві . Сукупність цих величин утворює матрицю (матрицю перевезень). 

Очевидно, змінні повинні відповідати умовам (1.4):

Система (1.4) містить m + n рівнянь з m n невідомими. Її особливість полягає в тому, що коефіцієнти при невідомих всюди рівні одиниці. Крім того, всі рівняння системи (1.4) можуть бути розділені на дві групи: перша група з т перших рівнянь ("горизонтальні" рівняння) і друга група з п решти рівнянь ("вертикальні" рівняння). У кожному з горизонтальних рівнянь містяться невідомі з одним і тим же першим індексом (вони утворюють один рядок матриці перевезень), у кожному з вертикальних рівнянь містяться невідомі з одним і тим же другий індексом (вони утворюють один стовпець матриці перевезень). Таким чином, кожна невідома зустрічається в системі (1.4) двічі: в одному і тільки одному горизонтальному і в одному і тільки одному вертикальному рівняннях. 

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

 

де символи означають підсумовування за відповідним індексом.

При цьому легко помітити, що під символами такого підсумовування об'єднуються тільки вільні невідомі (i ≥ 2, j ≥ 2).

У розглянутій нами системі тільки два рівняння, а саме перше горизонтальне і перше вертикальне, містять більше одного невідомого з числа обраних нами для побудови базису. Виключивши з першого горизонтального рівняння базисні невідомі  за допомогою вертикальних рівнянь, ми отримуємо рівняння (1.5):

  

або коротше (1.6):

,

де символ   означає суму всіх вільних невідомих. Аналогічно, виключивши з першого вертикального рівняння базисні невідомі за допомогою горизонтальних рівнянь, ми отримуємо рівняння (1.6а):

 

Так як для закритої моделі транспортної задач a = b, то отримані нами рівняння (1.6) та (1.6а ) однакові і, виключивши з одного з них невідоме  , ми отримаємо рівняння-тотожність 0 = 0, яке з системи викреслюється. 

Отже, перетворення системи (1.5) звелося до заміни двох рівнянь (першого горизонтального і першого вертикального) рівнянням (1.6). Решта рівняння залишаються незмінними. Система прийняла вигляд (1.7):

 

У системі (1.7) виділено зазначений вище базис: базисні невідомі з перших т рівнянь утворюють перший стовпець матриці перевезень, а базисні невідомі решти рівнянь утворюють перший рядок матриці перевезень без першого невідомого[Вона входить у перше рівняння системи (1.7)]. У системі (1.7) є m + n – 1 рівнянь, виділений базис містить m + n - 1 невідомих, а, отже, і ранг системи (1.5) r = n + m – 1.

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

Сукупність тарифів  також утворює матрицю, яку можна об'єднати матрицею перевезень і даними про запаси та потреби в одну таблицю (2):

Сума всіх витрат, тобто вартість реалізації даного плану перевезень, є лінійною функцією змінних  (1.8):

 

 

Необхідно в області допустимих рішень системи рівнянь (1.5) знайти рішення, яке мінімізує лінійну функцію (1.8).  
Таким чином, ми бачимо, що транспортна задача є задачею лінійного програмування. Для її вирішення застосовують також симплекс-метод, але в силу специфіки завдання тут можна обійтися без симплекс-таблиць. Рішення можна отримати шляхом деяких перетворень таблиці перевезень. Ці перетворення відповідають переходу від одного плану перевезень до іншого. Але, як і в загальному випадку, оптимальне рішення шукається серед базисних рішень. Отже, ми будемо мати справу тільки з базисними (або опорними) планами. Так як в даному випадку ранг системи обмежень - рівнянь дорівнює m + n - 1 то серед всіх m n невідомих  виділяється m + n - 1 базисних невідомих, а решта (m – 1) (n – 1) невідомих є вільними. У базисному рішенні вільні невідомі рівні нулю. Зазвичай ці нулі в таблицю не вписують, залишаючи відповідні клітини порожніми.

Таким чином, в таблиці перевезень, що представляє опорний план, ми маємо   m + n -1 заповнених і (m –1) (n – 1)  порожніх клітин.  
Для контролю треба перевіряти, дорівнює чи сума чисел в заповнених клітках кожного рядка таблиці перевезень запасу вантажу на відповідній базі, а в кожному стовпці - потреби замовника [цим підтверджується, що цей план є рішенням системи (1.5)]. 

Зауваження 1. Не виключаються тут і вироджені випадки, тобто можливість звернення до нуль однієї або кількох базисних невідомих. Але ці нулі на відміну від нулів вільних невідомих вписуються у відповідну клітину, і ця клітина вважається заповненою. 

Зауваження 2. Під величинами  , Очевидно, не обов'язково мати на увазі тільки тарифи. Можна також вважати їх величинами, пропорційними тарифами, наприклад, відстанями від баз до споживачів. Якщо, наприклад, виражені в тоннах, а   в кілометрах, то величина S, яка визначається формулою (1.8), є кількістю тонно-кілометрів, що складають обсяг даного плану перевезень.

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

 

РОЗДІЛ 2. МЕТОДИ ВИРІШЕННЯ ТРАНСПОРТНОЇ ЗАДАЧІ

2.1  Методи складання  початкового опорного плану

 

Як і в загальному випадку, рішення транспортної задачі починається з відшукання першого опорного плану (вихідного базису). Ми розглянемо два найбільш поширені методи побудови такого базису. Суть обох цих методів полягає в тому, що базисний план складається послідовно, у кілька кроків (точніше, m + n - 1 кроків). На кожному з цих кроків заповнюється одна клітина, до того ж так, що, або повністю задовольняється один із замовників (той, у стовпці якого знаходиться заповнювана клітина), або повністю вивозиться весь запас вантажу з однієї з баз (з тією, в рядку якої знаходиться заповнювана клітина).

У першому випадку ми можемо виключити стовпець, що містить заповнену на цьому кроці клітку, і вважати, що завдання звелася до заповнення таблиці з кількістю стовпців, на одиницю меншим, ніж було перед цим кроком, але з тією ж кількістю рядків і з відповідно зміненим запасом вантажу на одній з баз (на тій базі, якою було задоволено замовник на даному кроці).

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

Починаючи зі спочатку даної таблиці і повторивши m + n - 2 разів описаний крок, ми прийдемо до "таблиці", що складається з одного рядка і одного стовпця (інакше кажучи, з однієї порожньої клітки). Іншими словами, ми прийшли до завдання з однією базою і з одним споживачем, причому потреби цього єдиного замовника рівні запасу вантажу на цій єдиній базі. Заповнивши останню клітку, ми звільняємо останню базу і задовольняємо потребу останнього замовника. У результаті, здійснивши m + n – 1 кроків, ми і отримаємо шуканий опорний план. 

Зауваження. Може статися, що вже на деякій (але не на останньому!) Кроці потреба чергового замовника виявиться рівною запасу вантажу на черговий базі. Тоді після заповнення черговий клітини обсяг таблиці як би одночасно зменшується на одні стовпець і на один рядок. Але і при цьому ми повинні вважати, що зменшення обсягу таблиці відбувається або на один стовпець, а на базі зберігається "залишок" рівний нулю, або на один рядок, а у замовника ще залишилася незадоволена "потреба" в кількості нуля одиниць вантажу, яка і задовольняється на одному з наступних кроків. Цей нуль ("запас" або "потребою" - байдуже) треба записати в чергову заповнюють клітину на одному з наступних кроків. Тому що при цьому виявляється рівною нулю одна з базисних невідомих, то ми маємо справу з виродженим випадком. 

Різниця методів відшукання першого опорного плану полягає у відмінності способів набору заповнюваної клітини. 

 

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-ух напрямках:

1. Сума запасів у пунктах відправлення перевищує суму поданих заявок (транспортна задача з надлишком запасів).
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 (ум. од.).