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

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

План

1. Базисний план.

2. Діагональний метод, або метод північно-західного кута.

3. Метод найменшої вартості.

4. Метод Фогеля.

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

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

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

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

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

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

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

Приклад

Заповнення таблиці починається з її північно-західного кута, тобто клітки з невідомим x₁₁. Перша база A₁ може повністю задовольнити потребу першого замовника B₁ (a₁ = 300, b₁ = 170, a₁ > b₁). Вважаючи x₁₁ = 170, вписуємо це значення в клітку x₁₁ і виключаємо з розгляду перший стовпець. На базі A₁ залишається змінений запас a¹₁ = 130. У новій таблиці, що залишилася, з трьома рядками A₁, A₂, A₃ і чотирма стовпцями B₁, B₂, B₃, B₄; північно-західним кутом буде клітка для невідомого x₁₂. Перша база із запасом може повністю задовольнити потребу другого замовника B₂ (a¹₁ = 130, b₂ = 110, a¹₁ > b₂). Вважаємо x₁₂ = 110, вписуємо це значення в клітку x₁₂ і виключаємо з розгляду другий стовпець. На базі A₁ залишається новий залишок (запас) a¹¹₁ = 20. У новій таблиці, що залишилася, з трьома рядками A₁, A₂, A₃ i трьома стовпцями B₃, B₄, B₅ північно-західним кутом буде клітка для невідомого x₁₃. Тепер третій замовник B₃ може прийняти запас з бази A₁ (a¹¹₁ = 20, b₃ = 100, a¹¹₁ < b₃). Вважаємо x₁₃ = 20, вписуємо це значення в клітку x₁₃ і виключаємо з розгляду перший рядок. У замовника з В₃ залишається ще незадоволеною потреба b¹₃ = 80.

Тепер переходимо до заповнення клітки для невідомого x₂₃ і т.д.

Через шість кроків у нас залишиться одна база A₃ із запасом вантажу (залишком від попереднього кроку) a¹₃ = 200 і один пункт B₅ з потребою b₅ = 200. Відповідно цьому є одна вільна клітка, яку і заповнюємо, поклавши x₃₅ = 200. План складений. Базис утворений невідомими x₁₁, x₁₂, x₁₃, x₂₃, x₂₄, x₃₄, x₃₅. Правильність складеного плану легко перевірити, підрахувавши суми чисел, що стоять в заповнених клітках по рядках і стовпцях.

Загальний об'єм перевезень в тонно-кілометрах для цього плану складе

S₁ = 70*170 + 50*110 + 15*20 + 40*80 + 60*70 + 11*50 + 25*200 = 30650.

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

Приклад

В даному випадку заповнення таблиці починається з клітки для невідомого x₃₂, для якого ми маємо значення c₃₂ = 10, найменше зі всіх значень c_ij. Ця клітка знаходиться на перетині третього рядка і другого стовпця, відповідним третій базі A₃ і другому замовникові B₂. Третя база A₃ може повністю задовольнити потребу другого замовника B₂ (a₃ = 250, b₂ = 110, a₃ > b₂). Вважаючи x₃₂ = 110, вписуємо це значення в клітку x₃₂ і виключаємо з розгляду другий стовпець. На базі A₃ залишається змінений запас a¹₃ = 140. У новій таблиці, що залишилася, з трьома рядками A₁, A₂, A₃ і чотирма стовпцями B₁, B₃, B₄, B₅ кліткою з найменшим значенням c_ij клітка, де c₃₄ = 11. Заповнюємо описаним вище способом цю клітку і аналогічно заповнюємо наступні клітки. В результаті виявляються заповненими (у приведеній послідовності) наступні клітки

x₃₂ = 110, x₃₄ = 120, x₁₃ = 100, x₃₅ = 20, x₁₅ = 180, x₁₁ = 20, x₂₁ = 150.

На п'ятому кроці кліток з найменшими значеннями c_ij опинилося дві (c₁₁ = c₁₅ = 70). Ми заповнили клітку для x₁₅, поклавши x₁₅ = 180. Можна було вибрати для заповнення іншу клітку, поклавши x₁₁ = 170, що приведе в результаті до іншого опорного плану. Загальний об'єм перевезень в тонно-кілометрах для цього плану складе

S₁ = 70*20 + 15*100 + 70*180 + 80*150 + 10*110 + 11*120 + 25*20 = 30420.

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

Окрім розглянутих вище способів іноді використовується, так званий, метод Фогеля. Суть його полягає в наступному: У розподільній таблиці по рядках і стовпцях визначається різниця між двома найменшими тарифами. Наголошується найбільша різниця. Далі в рядку (стовпці) з найбільшою різницею заповнюється клітка з найменшим тарифом. Рядки (стовпці) з нульовим залишком вантажу надалі в розрахунок не приймаються. На кожному етапі завантажується тільки одна клітка. Розподіл вантажу проводиться, як і раніше.

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

1. Що таке базисний план?

2. Алгоритм діагонального методу.

3. Алгоритм методу найменшої вартості.

4. Алгоритм методу Фогеля.

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