Опорний конспект лекцій з курсу Дослідження операцій Тема 8 Транспортні задачі лінійного програмування, Поняття потенціалу і циклу, НУДПСУ

Лекція №8. ТРАНСПОРТНІ ЗАДАЧІ ЛІНІЙНОГО ПРОГРАМУВАННЯ. Поняття потенціалу і циклу

План

1. Поняття циклу.

2. Перерахунок по циклу.

3. Обчислення суми алгебри тарифів.

4. Поняття потенціалу.

5. Обчислення потенціалів.

6. Додаткова перевірка обчислених потенціалів.

3.3. Поняття потенціалу і циклу

Для переходу від одного базису до іншого при розв'язку транспортної задачі використовуються так звані цикли.

Циклом перерахунку або коротше, циклом в таблиці перевезень називається послідовність невідомих, що задовольняє наступним умовам:

1. Одне з невідомих послідовності вільне, а всі інші – базисні.

2. Кожні два сусідніх в послідовності невідомих лежать або в одному стовпці, або в одному рядку.

3. Три послідовних невідомих не можуть знаходитися в одному стовпці або в одному рядку.

4. Якщо, починаючи з якого-небудь невідомого, ми послідовно переходитимемо від одного до наступного за ним невідомому те, через декілька кроків ми повернемося до початкового невідомого.

Друга умова означає, що у двох сусідніх невідомих в циклі або перші, або другі індекси однакові.

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

Можна довести, що для будь-якої вільної клітки таблиці перевезень існує один і лише один цикл, що містить вільне невідоме з цієї клітки, і що число вершин в циклі завжди парно.

Так, наприклад, в таблиці перевезень, що складена за діагональним методом при розв'язку задачі з попереднього пункту, вільному невідомому x₂₁ відповідає цикл x₂₁,x₂₃,,x₁₃,,x₁₁,x₂₁ і т.д.

Хай тепер маємо деяку вільну клітку з відповідним до неї циклом. Якщо змінимо значення вільного невідомого, збільшивши його на деяке число x, то, переходячи послідовно від однієї вершини циклу до іншої, повинні будемо через незмінність сум по рядках і по стовпцях по черзі зменшувати і збільшувати значення невідомих в циклі на те ж саме число x. Наприклад, у вказаному вище циклі для вільного невідомого x₂₁ отримаємо:

старі значення: x₂₁ = 0, x₂₃ = 80, x₁₃ = 20, x₁₁ = 170, x₂₁ = 0;

нові значення: x¹₂₁ = х, x¹₂₃ = 80 – х, x¹₁₃ = 20 + х, x¹₁₁ = 170 – х, x¹₂₁ = х.

Очевидно, якщо забезпечити вершини циклу по черзі знаками «+» і «–», приписавши вершині у вільній клітці знак «+», то можна сказати, що у вершинах із знаком «+» число x додається до колишнього значення невідомого, такого, що знаходиться в цій вершині, а у вершинах із знаком «–» це число x віднімається з колишнього значення невідомого, такого, що знаходиться в цій вершині.

Зауважимо, що оскільки число вершин в циклі завжди парне, то, повертаючись у вільну клітку, слід приписати їй знак «+», тобто той знак, який їй вже приписаний при виході з неї. Це дуже істотна обставина, оскільки інакше прийшли б до суперечності. Байдуже також, в якому напрямі обходиться цикл при позначенні вершин.

Якщо як x обрати найменше з чисел, що стоять у вершинах, забезпечених знаком «–», то, принаймні, одна з колишніх базисних невідомих прийме значення нуль, і зможемо перевести його в число вільних невідомих, зробивши замість нього базисним те невідоме, яке було вільним.

Так, наприклад, в розглянутому вище циклі маємо негативні вершини x₂₃ і x₁₁; отже, вибравши х = min {80; 170} = 80, отримуємо:

старі значення: x₂₁= 0, x₂₃= 80, x₁₃= 20, x₁₁ = 170, x₂₁= 0;

нові значення: x¹₂₁ = 80, x¹₂₃ = 0, x¹₁₃ = 100, x¹₁₁ = 90, x¹₂₁ = 80, тобто замість колишнього базисного рішення отримуємо нове базисне рішення

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

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

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

Описане вище перетворення таблиці перевезень, в результаті якого перетвориться базис, називається перерахунком по циклу.

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

З'ясуємо тепер, як перерахунок по циклу впливає на загальний об'єм витрат на перевезення і за якої умови ці витрати стають менше.

Хай x_pq – деяке вільне невідоме, для якого уже побудували цикл і здійснили перерахунок по циклу з деяким числом x. Якщо вершині циклу, що знаходиться в i-й рядку і j-м стовпці таблиці перевезень, приписано знак «+», то значення невідомого x_ij, що знаходиться в цій вершині, збільшується на x, що у свою чергу викликає збільшення витрат на c_ijx, де c_ij – тариф, відповідний цій клітці; якщо ж вказаній вершині приписано знак «–», то значення невідомого x_ij зменшується на x, що викликає зменшення витрат на c_ijx.

Складемо тарифи, що відповідають позитивним вершинам циклу, і віднімемо з цієї суми суму тарифів, відповідних негативним вершинам циклу; отриману різницю S_pq назвемо сумою алгебри тарифів для даного вільного невідомого x_pq. Підрахунок суми алгебри тарифів можна тлумачити і так: припишемо тарифам ті ж знаки, які приписані відповідним вершинам циклу, тоді сума алгебри тарифів дорівнює сумі таких тарифів із знаком («відносних тарифів»).

Тепер, очевидно, можемо укласти, що в цілому при перерахунку по циклу, відповідному вільному невідомому x_pq, загальний об'єм витрат на перевезення зміниться на добуток суми алгебри тарифів на x, тобто на величину S_pqx. Отже, якщо сума алгебри тарифів для деякого вільного невідомого x_pq негативна (S_pq < 0), то перерахунок по циклу, відповідному цьому невідомому, приводить до зменшення загальної суми витрат на реалізацію плану перевезень. Якщо ж сума алгебри тарифів позитивна (S_pq > 0), то перерахунок по відповідному циклу призведе до збільшення загальної суми витрат. І, нарешті, якщо сума алгебри тарифів дорівнює нулю (S_pq = 0), то перерахунок по відповідному циклу взагалі не змінить загальну суму витрат (тобто два різні базисні плани вимагають однакових витрат на їх реалізацію).

Так, наприклад, для циклу x₂₁,x₃₂,x₁₃,x₁₁,x₂₁ в розглянутій задачі сума алгебри тарифів

S₂₁ = с₂₁ – с₂₃ + с₁₃ – с₁₁ = 80 – 40 + 15 + 79 = – 15 < 0.

Значить, перерахунок по цьому циклу знижує витрати. І дійсно, здійснивши такий перерахунок, отримуємо план, за яким об'єм перевезень в тонно-кілометрах складає

S₂ = 70*90 + 50*110 + 15*100 + 80*80 + 60*70 + 11*50 + 25*200= 29450,

тоді як за початковим планом він склав S₁ = 30650. Маємо зниження об'єму перевезень на 1200 тонно-кілометрів, що і слід було чекати, оскільки сума алгебри тарифів в даному випадку дорівнює – 15, а перерахунок по циклу здійснюється за допомогою числа х = 80 (зміна витрат рівна – 15*80 = – 1200).

Обчислення суми алгебри тарифів для кожного з вільних невідомих можна проводити без побудови відповідного циклу, користуючись, так званими, потенціалами. Припишемо кожній базі A_і, деяке число u_і, і кожному споживачеві B_i деяке число v_i

A_i ® u_i,i = 1,…,m, B_j ® v_j, j = 1,…n,

отже

u_і + v_j = c_ij, (3.6)

де c_ij – тарифи, відповідні кліткам, заповненим базисними невідомими. Ці числа u_і, і v_j називаються потенціалами відповідних баз і споживачів.

Знаючи потенціали, легко обчислити суму алгебри тарифів. Дійсно, якщо в сумі алгебри тарифів по циклу, відповідному вільному невідомому x_pq, замінити тарифи базисних кліток їх виразами через потенціали по формулах (3.6), то, через чергування знаків при вершинах циклу, всі потенціали, окрім u_p і v_q скоротяться, і ми отримаємо

S_pq = c_pq– (u_p + v_q).

Так, наприклад, для циклу x₂₁,x₂₃,x₁₃,x₁₁,x₂₁ в розглянутій вище задачі маємо

S₂₁ = с₂₁ – с₂₃ + с₁₃ – с₁₁ = с₂₁ – (u₂ + v₃) + (u₁ + v₃) – (u₁ + v₁) = с₂₁ – (u₂ + v₁).

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

u_p + v_q = c¹_pq (3.7)

називають непрямим тарифом цієї клітки. Отже, сума алгебри тарифів для вільної клітки x_pq дорівнює різниці її сьогодення («істинного») і непрямого тарифів

S_pq = c_pq– c¹_pq. (3.8)

З (3.8) витікає, що якщо непрямий тариф для даної вільної клітки більше її дійсного тарифу, то сума алгебри тарифів по циклу, відповідному цій клітці, буде негативна; якщо ж непрямий тариф менше істинного, то сума алгебри тарифів позитивна, і, нарешті, якщо непрямий тариф дорівнює істинному, то сума алгебри тарифів також дорівнює нулю.

Потенціали можна знайти з системи рівності (3.6), розглядаючи їх як систему (m + n - 1) рівнянь з m+n невідомими. Оскільки невідомих тут на одиницю більше, ніж рівнянь, то, принаймні, один з потенціалів можемо обрати довільно, поклавши, наприклад, u₁ = 0; тоді решта потенціалів легко визначається з рівнянь (3.6).

Наприклад, для плану, отриманого за діагональним методом в розглянутій вище задачі, маємо

u₁ + v₁ = 70,

u₁ + v₂ = 50,

u₁ + v₃ = 15,

u₂ + v₃ = 40,

u₂ + v₄ = 60,

u₃ + v₄ = 11,

u₃ + v₅ = 25.

Система містить сім рівнянь з вісьма невідомими. Вибираючи довільно значення, знаходимо послідовно з перших трьох рівнянь значення, потім з четвертого рівняння –, з п'ятого рівняння –, з шостого рівняння u₃ = 11 – v₄ і, нарешті, з сьомого рівняння – v₅ = 25 – u₃.

Поклавши, наприклад, u₁ = 0, набуваємо значень потенціалів

v₁ = 70,

v₂ = 50,

u₁ = 0, v₃ = 70,

u₂ = 25, v₄ = 35,

u₃ = – 24, v₅ = 49.

Знайдемо тепер непрямі тарифи для вільних кліток і порівняємо їх з дійсними тарифами

с¹₁₄ = u₁ + v₄ = 35 < с₁₄, с¹₂₅ = u₂ + v₅ = 74 < с₂₅,

с¹₁₅ = u₁ + v₅ = 49 < с₁₅, с¹₃₁ = u₃ + v₁ = 46 < с₃₁,

с¹₂₁ = u₂ + v₁ = 95 > с₂₁, с¹₃₂ = u₃ + v₂ = 26 > с₃₂,

с¹₂₂ = u₂ + v₂ = 75 < с₂₂, с¹₃₃ = u₃ + v₃ = – 9 < с₃₃.

Для кліток з невідомими x₂₁ і x₃₂ непрямі тарифи більше істинних. Отже, для них ми матимемо негативні суми алгебри тарифів

S₂₁ = с₂₁ – с¹₂₁ = 80 – 65 = – 15,

S₃₂ = с₃₂ – с¹₂₃ = 10 – 26 = – 16.

Значення S₂₁ = – 15 вже було раніше, обчислюючи суму алгебри тарифів для цієї клітки безпосередньо по циклу.

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

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

Контрольні запитання

1. Що таке цикл?

2. Як здійснюється перерахунок по циклу?

3. Як обчислюється сума алгебри тарифів?

4. Що таке потенціал?

5. Як обчислюються потенціали?

6. Як здійснюється додаткова перевірка обчислених потенціалів?

З повагою ІЦ “KURSOVIKS”!