Перенесення по циклу

У транспортній таблиці на рис.9 відразу дві базисні змінні – у комірках (3,1) і (3,3) – мають найбільше за модулем від’ємне число. Виберемо, наприклад, змінну х31 як таку, що залишає базис.

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

Спробуємо підібрати таке значення методом проб та помилок. Припустимо, що ми можемо присвоїти значення х31=20. Тоді щоб виконувалася, наприклад, умова

х11+х21+х31=15 (перший стовпчик),

значення базисної змінної у комірці має бути від’ємним

х11=15- 0-20=-5.

але за умовою задачі значення змінних не можуть бути від’ємними.

Розглянемо послідовність, з якою знаходимо х31.

1. Присвоїмо змінній х31 поки що невідоме значення х31*. Щоб попит для першого стовпчика зберігався у тому самому обсязі необхідне виконання рівності

x11+x21+x31=15

для цього необхідно зменшити на величину х31* значення змінної х11.

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

x11+x12+x13+x14=20

для цього необхідно збільшити на величину х31* значення змінної х12.

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

x12+x22+x32=10

для цього необхідно зменшити на величину х31* значення змінної х22.

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

x21+x22+x23+x24=30

для цього необхідно збільшити на величину х31* значення змінної х23 або х24. Збільшення х23 компенсувати буде неможливо, оскільки вона є єдиною базисною змінною у третьому стовпчику. Тому залишається збільшити значення змінної х24 на величину х31*.

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

x14+x24+x34=15

для цього необхідно зменшити на величину х31* значення змінної х34. При цьому для пропозиції у третьому рядку автоматично виконуватиметься умова

x31+x32+x33+x34=15

Тепер питання полягає у тому, як визначити х31*?

Серед усіх змінних, які ми зменшуємо на величину х31*, найменшою є х22=5, яку і виведемо з базису. Тому для виконання умови невід’ємності значення змінної

х31*=х22=5

На рис. 10 показано цикл, по якому змінюються значення базисних змінних. Комірки з цими змінними і тією, що вводиться до базису є вершинами циклу. Кількість вершин циклу завжди є парною у межах від 4 до m+n-1, тобто необов’язково усі базисні комірки мають бути вершинами циклу. Якщо у цих змінних значення збільшуються, у відповідних комірках ми ставимо «+», а якщо зменшуються, тоді «–» у відповідних комірках у правому верхньому куті, так як це показано на рис. 10. Як бачимо, базисна змінна х23 не входить до циклу.

Рис.10

Отже, маємо новий розв’язок.

х11=15–5=10 – базисна змінна

х12= 5+5=10 – базисна змінна

х13 = 0 – небазисна змінна

х14 = 0 – небазисна змінна

х21 = 0 – небазисна змінна

х22= 5–5 = 0 – змінна, що залишила базис

х23 =25 – базисна змінна, збережене значення

х24= 0+5 = 5 – базисна змінна

х31= 0+5= 5 – змінна, яку введено до базису

х32 = 0 – небазисна змінна

х33 = 0 – небазисна змінна

х11=15–5=10 – базисна змінна

На рис. 11 показано цей розв’язок. Знайшовши потенціали ui, vj з’ясували, що розв’язок не є оптимальним. На підставі нових знайдених значень cij-ui-vj вводимо до базису змінну х14. Будуємо цикл з вершинами в комірках (1,1), (1,4), (3,1), (3,4), так як це показано на рис. 11. Найбільше число, яке можна перенести по циклу – це 10. Тоді відразу дві базисні змінні х11 і х34, що входять до циклу, будуть нульовими. Визначаємо довільно, яку з них виводити з базису, наприклад, х11.

Рис.11

Тоді, переносячи по циклу х14*=10 знайдемо новий базисний розв’язок, як показано на рис.12. Приймемо, наприклад, v1=1. Знайшовши послідовно інші потенціали, встановлюємо, що розв’язок не є оптимальним. На підставі нових знайдених значень cij-ui-vj вводимо до базису змінну х33. Будуємо цикл з вершинами в комірках (3,3), (3,4), (2,4), (2,3), так як це показано на рис. 12. Найбільше число, яке можна перенести по циклу, це нуль.

Рис.12

Отже, розв’язок не зміниться, проте замість змінної х34 до базису увійде змінна х33, так як це показано на рис.13. Знайшовши послідовно потенціали, встановлюємо, що розв’язок не є оптимальним. На підставі нових знайдених значень cij-ui-vj вводимо до базису змінну х22. Будуємо цикл з вершинами в комірках (2,2), (2,4), (1,4), (1,2), так як це показано на рис. 13. Найбільше число, яке можна перенести по циклу, це х22*=5. Зверніть увагу на те, що відразу дві базисні змінні х24 і х33 будуть нульовими. Проте треба пам’ятати, що з базису завжди виводиться та змінна яка входить до циклу.

Рис.13

На рис. 14 показано новий базисний розв’язок. Знайшовши послідовно потенціали, встановлюємо, що cij-ui-vj >=0 для будь-яких i,j, тому розв’язок є оптимальним

Рис.14

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

x11= 0, x12= 5, x13= 0, x14=15,

x21= 0, x22= 5, x23=25, x24= 0,

x31=15, x32= 0, x33= 0, x34= 0,

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

Z=5*8+15*3+5*5+25*6+15*1+0*4=40+45+25+150+15=275 тис. грн.

Як ми бачимо тепер, початковий базисний розв’язок, знайдений методом найменшої вартості, не є оптимальним, оскільки вартість перевезення (Z=290) виявилася на 15 тис. грн. більшою від мінімальної вартості, проте є досить близькою до неї.

З’ясуємо, як швидко знайдеться оптимальний розв’язок нашої задачі, якщо початковий розв’язок отримано за допомогою методу мінімальної вартості (рис. 15). Для цього знайдемо потенціали. Як бачимо на рис. 15, розв’язок не є оптимальним (c14-u1-v4=-1).

Рис.15

Переносячи по циклу х14*=15 знаходимо новий базисний розв’язок, який буде оптимальним, оскільки при знайдених потенціалах виконується нерівність cij-ui-vj>=0 для будь-яких i, j.(див. рис. 16)

Рис.16

Отже, оптимальний розв’язок є таким

x11= 0, x12= 0, x13= 5, x14=15,

x21= 0, x22=10, x23=20, x24= 0,

x31=15, x32= 0, x33= 0, x34= 0,

і від m*n дуг на загальній схемі перевезення (рис. 2) залишиться лише п’ять, так як це показано на рис. 17

Рис. 17

Цей розв’язок відрізняється від того, що отримали у прикладі т.4.2 і свідчить про наявність нескінченної множини оптимальних розв’язків.

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

Список літератури

1. Таха Х.А. Введение в исследование операций, 7-е издание.: Пер. с англ. - М.: Издательский дом „Вильямс”, 2005. – 912 с.

2. Афанасьев М.Ю, Суворов Б.П. Исследование операций в экономике: модели, задачи, решения: Учебное пособие. – М.: Инфра-М, 2003. – 144с

3. Hillier F.S., Lieberman G.J., Introduction to operations research, 7-th edition. NY.: McGraw-Hill Higher Education, 2001. – 1237 P.