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

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

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

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

 

Таблиця 5.6 - Побудова замкненого контуру для задачі прикладу 5.2. (перша ітерація)

          D         E         F          G         Ui

 

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

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

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

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

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

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

 

 

 

 

Розв’язок, отриманий після третьої ітерації (див. Табл. 5.9), відповідає умові оптимальності, а отже забезпечує мінімально можливу величину транспортних витрат Т3=Т2-53=255-15=240 (г.о.). Таким чином, від постачальника А слід перевезти 20 од. Продукції до споживача Е, від В – 5 од. До D і 15 од. До Е, від С – 10 од. Споживачу D та 20 од. Споживачу F. Значення змінної x24=10, розташованої в стовпці фіктивного постачальника, свідчить про те, що від постачальника В слід вивозити не всю продукцію, яку він має, залишивши на складі цього постачальника 10 одиниць.