y"> x 2 x 3 x 4 x 5 x 1 21010-2x 2 501-205x 4 20001-4F (X0) -2900-10-1
Рішення вийшло цілочисловим. Оптимальний цілочисельний план можна записати так:
F опт (X) = 29, Х опт (2, 5)
Глава 2. Моделювання, алгоритмізація та програмування методу
2.1 Математична модель задачі
Необхідно знайти максимум або мінімум функції
В
за умов
В
де Z - безліч цілих чисел.
Для вирішення завдання ЦЛП може бути застосований метод Гомори. p align="justify"> Метод Гоморі містить два етапи.
Етап 1. Рішення вихідної задачі звичайним симплекс-методом і перевірка рішення на целочісленноесть. Якщо рішення містить хоча б одне дробове значення, то переходять до етапу 2, в іншому випадку розрахунок закінчується. p align="justify"> Етап 2. Складання додаткового обмеження (перетину) і рішення розширеної задачі звичайним симплекс-методом. Додаткове обмеження (перетин) відсікає нецілочисельне рішення. Перетин володіє наступними двома властивостями:
) будь цілочисельне рішення йому задовольняє;
) будь-яка не цілочисельне рішення задачі йому не задовольняє.
Пояснимо, як складається розтин.
Нехай виконаний етап 1;
В
- дробове число.
Розглянемо i-е обмеження:
b i = x i < span align = "justify"> + a im + l x m +1 + a im +2 x m +2 + ... + a in x n .
Так як b i - дробове, а в правій частині всі змінні цілі, хоча б одне значення a ij
