овим, то шукане рішення целочисленной завдання буде також знайдено;
) В іншому випадку, якщо деяка координата - не ціла, отримане рішення задачі перевіряється на можливість існування цілочисельного рішення (наявність цілих точок в допустимому многограннике):
якщо в якому-небудь рядку з дробовим вільним членом , всі інші коефіцієнти виявляться цілими, то в допустимому многограннике немає цілих, крапок і завдання цілочисельного програмування рішення не має;
в іншому випадку вводиться додаткове лінійне обмеження, яке відсікає від допустимого багатогранника частина, безперспективну для пошуку рішення задачі цілочисельного програмування;
) Для побудови додаткового лінійного обмеження, вибираємо l-ту рядок з дробовим вільним членом і записуємо додаткове обмеження
В
де і - відповідно дробові частини коефіцієнтів і вільного
члена . Введемо в обмеження (3) допоміжну змінну :
(4)
Визначимо коефіцієнти і , що входять до обмеження (4):
(5)
де і - найближчі цілі знизу для і відповідно.
) Далі за допомогою симплекс-методу знову вирішується завдання лінійного програмування при наявності додаткового обмеження тощо
Гомори довів, що кінцеве число подібних кроків призводить до такого завдання лінійного програмування, рішення якої буде цілочисловим і, отже, шуканим.
Рішення: Наведемо систему лінійних обмежень і функцію мети до канонічної формі:
В
Визначимо оптимальне рішення системи лінійних обмежень, тимчасово відкинувши умова цілочисельності. Використовуємо для цього симплекс-метод. Нижче послідовно в таблицях представлені вихідне рішення задачі, і наведені перетворення вихідної таблиці з метою отримання оптимального рішення задачі:
Рішення булевских задач ЛП методом Балаша.
Скласти самостійно варіант для задачі цілочисельного лінійного програмування з Булевського змінними з урахуванням наступних правил: в задачі використовується не менше 5 змінних, не менше 4 обмежень, коефіцієнти обмежень і цільової функції вибираються довільно, але таким чином, ...
