• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Метод Гомори

Перший алгоритм Р. Гомори полягає в наступному:

Хай задана повністю цілочисельна лінійна задача:

(5.2)

(5.3)

Хай в результаті лінійних операцій над рівняннями системи (5.3) отримано нове лінійне рівняння

(5.4)

Цілою частиною числа називається найбільше ціле число , яке не перевищуюче . Наприклад ; .

Замінивши в рівнянні (5.4) всі коефіцієнти їх цілими частинами, отримаємо:

(5.5)

Якщо всі є цілочисельними, то ліва частина рівняння (5.5) теж цілочисельна. Рівняння (5.5) можна посилити таким чином:

(5.6)

Це обмеження-нерівність (4.6) можна перетворити в обмеження-рівняння шляхом введення додаткової цілочисельної і ненегативної змінної : (5.7)

Віднімемо (5.4) з (5.7). Враховуючи, що отримаємо:

(5.8)

В першому методі Гомори всі обмеження формуються відповідно до рівнянь (5.8) – це і є відсікання нецілочисельних крапок.

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

, (5.9)

то рівняння додаткового обмеження-відсікання виглядає таким чином:

. (5.10)

Побудова відсікання - «велика ітерація». Далі для звуженої області проводяться «малі ітерації».

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

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

2) початкова задача лінійного програмування має рішення, а цілочисельна не має. В симплекс-таблиці це видно таким чином: в стовпці вільних членів в деякому рядку стоїть неціле число, а вся решта коефіцієнтів цього рядка ­– цілі числа.

Збіжність даного алгоритму достатньо повільна. Для задачі з 10-ма змінними необхідно провести порядку 1000 ітерацій.

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

Округлення нецілочисельного рішення до найближчого цілого може дати крапку, що не належить області.

Другий алгоритм Р. Гомори:

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

при , ( - цілочисельні);

при , ( - нецілочисельні).

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

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

, (5.11)

де - вільна змінна.

Тоді по другому алгоритму Гомори відсікання будується таким чином:

, (5.12)

де (5.13)

Читайте також:

1. B. Тип, структура, зміст уроку і методика його проведення.
2. D) методу мозкового штурму.
3. Demo 11: Access Methods (методи доступу)
4. H) інноваційний менеджмент – це сукупність організаційно-економічних методів управління всіма стадіями інноваційного процесу.
5. I Метод Шеннона-Фано
6. I. ЗАГАЛЬНІ МЕТОДИЧНІ ВКАЗІВКИ
7. I. Метод єдиної подібності.
8. I. Метод рiвних вiдрiзкiв.
9. II. МЕТОДИЧНІ ВКАЗІВКИ
10. II. УЧЕБНЫЕ И МЕТОДИЧЕСКИЕ ПОСОБИЯ, ПРАКТИКУМЫ
11. IV. КЕРІВНИЦТВО, КОНТРОЛЬ І НАДАННЯ ОРГАНІЗАЦІЙНО-МЕТОДИЧНОЇ ДОПОМОГИ ПРАКТИКАНТАМ.
12. IV. Метод супутних змін.

Переглядів: 547