ежень.
В В
Запишемо систему обмежень у вигляді рівностей, для вирішення алгебраїчним методом.
В результаті рішення знайдений оптимальний план завдання: х1 = 9/4, х2 = 5/2, F = -41/4. Це рішення не відповідає умові цілочисельності, поставленому в задачі. Розіб'ємо вихідний багатокутник рішень на дві області, виключивши з нього область 3 В
Змінений багатокутник рішень задачі
Складемо нові системи обмежень для утворилися областей багатокутника рішень. Ліва область являє собою чотирикутник (трапецію). Система обмежень для лівої області багатокутника рішень представлена ​​нижче. br/>В В
Система обмежень для лівої області
Правий область представляє собою точку С.
Система обмежень для правої області рішень представлена ​​нижче.
Нові системи обмежень представляють із себе дві допоміжні завдання, які необхідно вирішити незалежно один від одного. Вирішимо задачу цілочисельного програмування для лівої області багатокутника рішень. br/>
,
В результаті рішення знайдений оптимальний план завдання: х1 = 3, х2 = 3, F = -12. Цей план задовольняє умові цілочисельності змінних в задачі і може бути прийнятий в якості оптимального опорного плану для вихідної задачі цілочислового лінійного програмування. Проводити рішення для правої області рішень немає сенсу. На малюнку нижче представлений хід рішення целочисленной завдання лінійного програмування у вигляді дерева. p align="justify"> Хід вирішення целочисленной завдання лінійного програмування методом Гоморі.
У багатьох практичних додатках представляє великий інтерес завдання цілочисельного програмування, в якій дана система лінійних нерівностей і лінійна форма
В В В В
Потрібно знайти цілочисельне рішення системи (1), яке мінімізує цільову функцію F, причому, всі коефіцієнти - цілі.
Один з методів розв'язання задачі цілочислового програмування запропонований Гоморі. Ідея методу полягає у використанні методів безперервного лінійного програмування, зокрема, симплекс-методу. p align="justify">) Визначається за допомогою симплекс-методу рішення задачі (1), (2), у якої знято вимогу цілочисельності рішення; якщо рішення виявляється цілочисл...
