На головну
Знаходження початкового базисного розподілу поставок
Одним з можливих методів знаходження початкового базисного розподілу поставок є метод "північно-західного" кута, показаний в наступному прикладі.
приклад7.2. Знайти початкове базисне розподіл поставок для транспортної задачі з прикладу 7.1.
Рішення.дамо змінної х11максимально можливе значення або, іншими словами, максимальну можливу поставку в клітку (1,1) таблиці поставок: x11 = Min {60, 20} = 20. Після цього попит першого споживача повністю задоволений, а тому перший стовпець таблиці поставок випадає з подальшого розгляду (заповнені клітини будемо перекреслювати, як в табл. 7.2); клітини, що випали з подальшого розгляду, перекреслені штриховий лінією. У таблиці поставок знайдемо "північно-західний" кут - клітку (1,2), а також дати туди максимально можливу поставку. З огляду на, що перший постачальник вже віддав 20 одиниць вантажу, і у нього залишилося тільки 40 = 60 - 20 одиниць вантажу, отримуємо, що х12= Min {40,110} = 40. Після цього потужність першого постачальника повністю реалізована і з розгляду випадає перший рядок таблиці поставок [перекреслюємо суцільною лінією клітку (1,2) і штриховий лінією залишилися вільні клітини першого рядка]. У решти таблиці знову знаходимо "північно-західний кут" і т.д. В результаті отримуємо наступне вихідне розподіл поставок:
Таблиця 7.2
Число заповнених клітин в отриманому розподілі дорівнювала m + n - 1 = 3 + 4 - 1 = 6, тобто числа основних (базисних) змінних. Це, звичайно, не випадково. Дійсно, на кожному кроці (крім останнього) даного методу з розгляду випадали або рядок, або стовпець, а на останньому кроці і стовпець, і рядок. Тому число заповнених клітин (число кроків) на одиницю менше, ніж сума числа рядків і стовпців таблиці поставок, тобто одно m + n - 1. Виявляється (див. Теорему 7.2), що ця ж особливість кроків методу "північно-західного" кута є причиною того, що отримане розподіл є базисним.
Метод "північно-західного кута" має істотний недолік: він побудований без урахування значень коефіцієнтів витрат завдання. З іншого боку, даний метод допускає модифікацію, позбавлену цього недоліку: на кожному кроці максимально можливу поставку слід давати не в "північно-західну" клітку залишилася таблиці, а в клітку з найменшим коефіцієнтом витрат. При цьому розподіл поставок виявляється, взагалі кажучи, ближче до оптимуму, ніж розподіл, отримане за методом "північно-західного кута". Такий метод отримання опорного плану називається методом найменших витрат. Розглянемо цей метод на наступному прикладі.
приклад7.3. Знайти методом найменших витрат первинний розподіл поставок в завданні з прикладу 7.1.
Рішення.Знаходимо в таблиці поставок клітини з найменшим коефіцієнтом витрат. Таких клітин дві - (1,1) і (2,1) з коефіцієнтами витрат, рівними 1. Порівняємо максимально можливі поставки для цих клітин: для клітини (1,1) х11= Min {60,20} = 20, для клітини (2,1) x21 = min {120,20} = 20. Так як вони збігаються, то максимально можливу поставку даємо в будь-яку з них. Наприклад, даємо поставку, рівну 20 одиницям, в клітку (2,1). В результаті попит першого споживача задоволений, і перший стовпець таблиці поставок випадає з подальшого розгляду (див. Табл. 7.3).
Таблиця 7.3
У решти таблиці найменшим коефіцієнтом витрат мають дві клітини; с12= с24 = 2. Порівняємо максимально можливі поставки для цих клітин: для клітини (1,2) х12 = Min {60,110} = 60; для клітини (2,4) х24 = min {120 - 20, 110} = = 100. Даємо поставку в клітку (2,4), для якої максимально можлива поставка виявилася більше: х24 = 100. При цьому з розгляду випадає другий рядок таблиці поставок (див. Табл. 7.4). Аналогічно, продовжуючи заповнення таблиці поставок крок за кроком, отримуємо х12 = min {40,110} = 60, х32= min {100,110 -60} = 50, х34 = min {100 - 50,110 - 100} = 10, x33 = Min {100 - 60,40} = 40 (див. Табл. 7.5).
Порівняємо знайдене розподіл поставок з розподілом, отриманим для тієї ж задачі за методом "північно-західного" кута (приклад 7.2, табл. 7.2). Обчислимо для кожного з цих розподілів сумарні витрати в грошових одиницях:
в прикладі 7.2
в прикладі 7.3 .
Як очікувалося, при застосуванні методу "північно-західного" кута сумарні витрати більше, ніж при застосуванні методу найменших витрат. Таким чином, у другому випадку ми знаходимося ближче (по числу необхідних кроків) до оптимуму, ніж в першому. Розподілу, одержувані за допомогою зазначених методів, є базисними, і розглянемо ті особливі випадки, які можуть зустрітися при використанні цих методів.
Таблиця 7.4
Таблиця 7.5
теорема 7.2. Нехай на кожному кроці заповнення таблиці поставок виникає одна заповнена 'клітина, причому з розгляду на кожному (крім останнього) кроці випадає або один рядок, або один стовпець. Тоді змінні, відповідні заповненим клітинам, можна прийняти за базисні.
З теореми 7.2 випливає, що методи "північно-західного" утла і найменших витрат призводять до базисних розподілів поставок, якщо на кожному (крім останнього) кроці з розгляду випадає або один рядок, або один стовпець.
Розглянемо тепер ті особливі випадки, коли на певному етапі заповнення з розгляду випадають одночасно і рядок, і стовпець. Зазначимо, як слід чинити, щоб метод заповнення і раніше задовольняв умовам теореми 7.2, і отримується розподіл поставок було базисним.
приклад7.4. Знайти початкове базисне розподіл поставок для наступної транспортної задачі (табл. 7.6):
Таблиця 7.3
Скористаємося методом "північно-західного" кута. На першому кроці слід дати постачання, рівну 20 одиницям, в клітку (1,1). В результаті буде задоволений попит першого споживача і з розгляду випаде перший стовпець. На другому кроці поставку в 10 одиниць слід дати в клітку (1,2). При цьому з подальшого розгляду випадають і перший постачальник (який реалізував залишки свого вантажу), і другий споживач, повністю задовольнив свій попит. Продовжуючи використовувати метод "північно-західного" кута, ми доповнимо таблиці поставок, але число заповнених клітин виявиться менше, ніж число основних (базисних) змінних, рівне m + n - 1 = 3 + 3 1 = 5. Таке розподіл не буде базисним, і для продовження вирішення розподільний метод буде неприйнятний. Уникнути цього можна, використовуючи наступний штучний прийом.
Розіб'ємо другий крок на два кроки. Припустимо, що після поставки в клітку (1,2) з розгляду випадає, наприклад, тільки перший рядок. Для того, щоб вивести з розгляду другий стовпець, робимо ще один крок: даємо нульову (фіктивну) поставку в довільну, але не викреслити клітку другого шпальти, наприклад, в клітку (2.2). Після таких трьох кроків маємо табл. 7.7.
Таблиця 7.7
Аналогічно, можна було припустити, що після другого кроку ізрассмотренія випав тільки другий стовпець. Тоді на третьому кроці нульову поставку слід дати в довільну, але не викреслити клітку першого рядка.
При подальшому заповненні таблиці поставок використовуємо метод "північно-західного" кута звичайним чином. Остаточно отримуємо розподіл поставок (табл. 7.8).
Таблиця 7.8
Перекреслені клітини, що відповідають базисним змінним, і в подальшому будемо називати заповненими, незважаючи на те, що серед них можливі клітини з нульовими поставками.
Розглянутий штучний прийом застосовується також при методі найменших витрат, якщо при використанні цього методу на певному етапі з розгляду випадають одночасно і рядок, і стовпець.
при обмеженнях | Особливі випадки симплексного методу | II. Проблема виродженого базисного рішення | сімплексні таблиці | Поняття про М-методі (методі штучного базису) | Економічна інтерпретація завдання, двоїстої задачі про використання ресурсів | Взаємно двоїсті задачі лінійного програмування і їх властивості | Перша теорема подвійності | Друга теорема подвійності | Об'єктивно обумовлені оцінки та їх зміст |