3.3 Розподільний метод

 

Як і в симплекс-методі, поліпшувати отриманий допустимий розв’язок будемо за рахунок перекладу однієї з базисних змінних в розряд вільних і однієї з вільних змінних у розряд базисних. Кількість вільних і кількість базисних змінних при цьому не змінюється.

Процес поліпшення допустимого розв’язку розглянемо як продовження прикладу 3.3 (п. 3.2). В отриманому допустимому розв’язку є дві вільні змінні х₁₂ і х₂₁. Довільно виберемо змінну х₂₁ і збільшимо значення цієї змінної від нуля до одиниці х₂₁=1 (табл. 3.4.). При цьому порушуються баланси потужності в 1-му стовпці й 2-му рядку.

Таблиця 3.4

 

Для відновлення цих балансів зменшимо на одиницю значення базисних змінних, які входять в 1-й стовпець і 2-й рядок (х₁₂=19, х₂₃=4). При цьому порушуються баланси по 1-му рядку й 3-му стовпцю. Базисну змінну х₁₃, що перебуває на перетині 1-го рядка й 3-го стовпця, збільшимо на одиницю (х₁₃=31). Баланси потужності за всіма рядками і стовпцями виявляються відновленими.

У результаті виконаних дій у транспортній матриці отримано замкнутий цикл, вершини якого відзначені знаками "+" і "‑". Початкова вершина циклу лежить у клітці вільної змінної х₂₁, що переводиться в базис. Всі інші вершини циклу лежать у клітинках базисних змінних х₁₁, х₁₃ і х₂₃. Знак "+" у вершині циклу відповідає збільшенню змінної, знак "‑" ‑ її зменшенню. При збільшенні на одиницю вільної змінної зміна цільової функції визначиться як алгебраїчна сума питомих вартостей, що розміщені у вершинах циклу. Зміна цільової функції при збільшенні на одиницю вільної змінної х₂₁ складе:

         (3.4)

Видно, що при збільшенні вільної змінної х₂₁ значення цільової функції зменшується. Цю вільну змінну варто перевести в базис.

Зовсім аналогічні дії можна виконати й для вільної змінної х₁₂. Нескладно показати, що збільшення цієї змінної на одиницю дасть збільшення цільової функції:

       (3.5)

Тому вільну змінну х₁₂ не слід переводити в базис.

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

Отримано новий допустимий розв’язок (табл. 3.5 і рис. 3.4).

Таблиця 3.5

Рис. 3.4. Схема електричної мережі

 

У цьому новому розв’язку:

‑ вільні змінні: х₁₂=0, х₂₃=0;

‑ базисні змінні: х₁₁=15, х₁₃=35, х₂₁=5, х₂₂=25 о.п.;

‑ значення цільової функції:

Видно, що значення цільової функції покращилося в порівнянні з попереднім розв’язком (136<137).

У новому розв’язку будуються цикли перерахунку й визначаються зміни цільової функції Z для кожної вільної змінної х₁₂ і х₂₃. Якщо для кожної вільної змінної зміна цільової функції Z>0, то отриманий розв’язок буде оптимальним.