Главная | Обратная связь | Поможем написать вашу работу!

Побудова циклу перерозподілу ресурсів

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

Вибрана змінна є початком циклу.

Цикл – це замкнена ломана, яка в кожній вершині змінює напрямок під кутом 90°.

Правила побудови циклу наступні:

– усі вершини циклу, крім початкової, повинні проходити через базисні змінні

– дві сусідні вершини, які включено до циклу, з’єднуються прямою;

– у кожній вершині циклу виконується поворот під кутом 90°;

– у будь-якому рядку чи колонці, де проходить цикл, є тільки дві вершини циклу;

– якщо позначити вершини циклу послідовно знаками "+" та "-", то кількість таких позначок має бути однаковою;

– якщо при побудові циклу є перетин прямих, то точки перетину цих прямих не будуть вершинами циклу.

Геометрично конфігурація циклу є замкненим контуром, форма якого може бути різною, наприклад, такою, як на рис.3.1.

Рис. 3.1.

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

У наведеному прикладі для змінної , яка не виконує умови оптимальності, цикл перерозподілу ресурсів показано у наступній таблиці:


І		20
ІІ

Цикл подається у вигляді ланцюга:

Після визначення циклу розмічаються змінні , які ввійшли до циклу, знаками „+” та „-” (ці знаки означають, що деякі змінні слід збільшити, а деякі – зменшити на величину коригування плану перевезень). Знаки „+” та „- ” чергуються, починаючи зі знаку „+”. У даному прикладі .

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

Наприклад, для вершини , з якої неможливо побудувати цикл за певними правилами, можна використати вироджений цикл , який позначено в таблиці, наведеній нижче:


І
ІІ
ІІІ

Фіктивну базисну змінну називають нульовою поставкою.

3.4.6. Знаходження нового плану розподілу ресурсів

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

що аналогічно виведенню базисної змінної з головного рядка симплекс-таблиці.

У розглянутому прикладі для знайденого циклу величина коригування

Потім, ураховуючи знаки змінних, які ввійшли до циклу, та величину , перераховують змінні циклу згідно з формулою

При цьому в базис уводиться одна із змінних (у разі виродження плану таких змінних може бутидекілька).

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

Процес знаходження нових значень змінних відповідає процесу розрахунку за формулами перетворень елементів симплекс-таблиці у симплексному методі.

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

Оскільки перерозподіляється одиниць ресурсів, а економія від перевезень однієї одиниці вантажу дорівнює , величина нового плану поліпшується на величину , тобто

Згідно з побудованим циклом у прикладі та значенням = 20 маємо новий план перевезень, який наведено у наступній таблиці:


І
ІІ

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

1. Складають рівняння потенціалів для всіх ; у прикладі є випадок виродження, тому до системи вводиться ще одне рівняння для фіктивної базисної змінної