Методы принятия управленческих решений: для менеджеров

109 Требование целочисленности приводит к допустимому мно­ жеству решений задачи, которое представляется как совокупность точек с целочисленными координатами. Можно добавить новые ог­ раничения, связывающие внешние целочисленные точки, и в качест­ ве многогранника решений использовать множество, ограниченное осями координат и новым контуром. Получим новую задачу, ее оп­ тимальное решение будет удовлетворять условию целочисленности. Метод решения задачи полностью целочисленного програм­ мирования предложен Р.Гомори. Он основан на симплекс-методе и состоит в следующем. Симплекс-методом находим оптимальный план задачи без учета целочисленности. Вычисления заканчивают, если он является целочисленным. Если оптимальный план содержит хоть одну дробную компоненту x j , то вводят дополнительные ог­ раничения, чтобы учесть целочисленность компонент. Вычисления продолжают до получения нового оптимального плана. Если и он не является целочисленным, вводят следующее ограничение. Процесс продолжают, пока либо не будет найден целочисленный оптималь­ ный план, либо показано, что оптимальных планов нет. Рассмотрим, как составить дополнительное ограничение. Пусть оптимальный план X = (xj ,^2 ) получен с помощью базисных столбцов Тогда последняя симплекс- таблица (табл.52) имеет вид Таблица 52 Базис С В ^1 <^'2 '-w+l 0, А Лп ^1 С] ^1* 1 0 0 0 ^!m+l ^im+1 *2 С2 ^2* 1 0 ^2 т+\ ^2m+l 0 0 1 '-т ^тт+\ ^тт+\ т + 1 ^0 0 ... 0 Дт+1 А«