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

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

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

Табл. 7.1. Початковий розв’язок транспортної задачі (приклад 6.2). Побудова замкненого контуру.

 

Зауважимо, що ця транспортна таблиця містить більше інформації про початковий розв’язок, ніж табл. 6.4. Справа в тому, що рівняння Ui +Vj= Cij, які використовуються для знаходження потенціалів, мають настільки просту структуру, що не потребують запису в явному вигляді. Тому можна обчислити значення потенціалів безпосередньо в таблиці, маючи на увазі, що для будь-якої базисної змінної xij, що знаходиться на перетині і-го рядка та j-го стовпця, сума потенціалів відповідних рядка та стовпця має дорівнювати величині Cij. Двоїсті оцінки для небазисних змінних також зручно визначити в транспортній таблиці. Табл. 7.1 включає додатковий стовпець та додатковий рядок, які містить значення потенціалів. У нижніх лівих кутах небазисних комірок записані значення двоїстих оцінок.

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

Очевидно, що при збільшенні змінної x24 на одиницю для збереження допустимості розв’язку значення базисних змінних, що лежать у вершинах контуру, необхідно скоригувати таким чином: зменшити x34 на одиницю, збільшити x33 на одиницю й нарешті зменшити x23 на одиницю. Цей процес позначається знаками “+” і “-” у відповідних комірках табл. 7.1. Введені зміни не порушують обмежень, які накладаються на обсяги попиту та пропозиції.

Для виключення з базису з числа змінних, позначених символом “-”, вибирається змінна, що має найменше значення. Для нашого прикладу найменше значення має змінна x23=0. Значення змінної, яка виключається з базису, необхідно додати до змінних, позначених символом “+” та відняти від змінних, що позначені символом “-”. З цього моменту базисна змінна x23 стає небазисною, а змінна x24 навпаки включається до базису.

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

Перенесення за контуром значення змінної x23=0 приводить до розв’язку, представленого в табл. 7.2.

Табл. 7.2. Розв’язок задачі 6.2 після першої ітерації

 

Цьому розв’язку відповідає таке саме значення транспортних витрат, як і попередньому (Т1=Т0=335 г.о.).

Для плану перевезень, отриманого після другої ітерації (міститься в табл.7.3) сумарні транспортні витрати становитимуть: Т2=5×3+15×2+20×8+10×1+20×2=255 (г.о.).

Табл. 7.3. Розв’язок задачі 6.2 після другої ітерації

 

Величину транспортних витрат можна обчислити й більш простим способом. Дійсно, на другій ітерації до базису включається змінна x31, що має двоїсту оцінку  =8. У результаті включення до базису ця змінна зросла від 0 до 10. Таким чином, величина цільової функції (сумарних транспортних витрат) для нового розв’язку зменшиться на величину 8×10=80 і становитиме Т2=Т1-80=335-80=255 (г.о.).

Розв’язок, отриманий після третьої ітерації (див. табл. 7.4), відповідає умові оптимальності, а отже забезпечує мінімально можливу величину транспортних витрат Т3=Т2-5×3=255-15=240 (г.о.).

Табл. 7.4. Розв’язок задачі 6.2 після третьої ітерації

 

Таким чином, від постачальника А слід перевезти 20 одиниць продукції споживачеві Е; від В – 5 одиниць споживачеві D і 15 одиниць – Е; від постачальника С – 10 одиниць споживачеві D та 20 одиниць - F. Значення змінної x24=10, розташованої в стовпці фіктивного постачальника, свідчить про те, що від постачальника В слід вивозити не всю продукцію, яку він має, залишивши на складі цього постачальника 10 одиниць продукції.