КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Алгоритм решения ЗЛЦП
1.Симплексным методом решить задачу без учета условия целочисленности, если все компоненты оптимального плана целые, то он является оптимальным и для задачи целочисленного программирования.
2.Если среди компонент оптимального решения есть нецелые, то выбрать компоненту с наибольшей целой частью и сформировать правильное отсечение.
3.Неравенство, определяющее правильное отсечение введением дополнительной, неотрицательной целочисленной переменной, преобразовать в равносильное уравнение и включить его в систему ограничений.
4.Полученную расширенную задачу решить симплексным методом, если оптимальный план будет целочисленным, то задача ЛЦП решена, в противном случае вернуться к пункту 2 алгоритма.
Пример: При решении некоторой оптимизационной задачи симплексным методом получено некоторое базисное решение: х1= 2 – 1 х4 + 4 х5 3 3 3 х2=8 – х5 х3=18+х4+х5 Z=25 1 – 2 x4 – 1 x5 3 3 3
X=(2; 8; 18; 0; 0) Z=25 1 3 3 Это базисное решение оптимизировано. Однако решение Х не удовлетворяет условию целочисленности, т.к. по первому уравнению с переменной x1=2/3-1/3x4+4/3x5 , получившей нецелочисленное значение в оптимальном решении(2/3). Составляем правильное отсечение, в виде дополнительного ограничения. 2/3 + 1/3 х4– 4/3 х5≤0 (1) Обращаем внимание на то, что берем дробную часть свободного члена с тем же знаком, который он имеет в уравнении, а дробные части коэффициентов при не основных переменных х4 и х5 – с противоположными знаками. Так как дробные части: 2/3 = 0+2/3 =2/3
1/3 = 0+1/3 =1/3
-4/3 = -2+2/3 =2/3, тогда последнее неравенство в соответствии c (1) запишется в виде: 2/3+1/3х4-2/3х5≤0 (2)–правильное отсечение.
Введя дополнительную целочисленную переменную х6 ≥ 0, получим равносильное неравенству (2),уравнение:
2/3+1/3х4-2/3х5 +х6=0 Включаем это уравнение в систему ограничений, после чего повторяем алгоритм решения задачи симплексным методом, применительно к расширенной задаче. Дополнительное уравнение вводится в систему, полученную на последнем шаге решения задачи(без условия целочисленности).
Дата добавления: 2014-01-06; Просмотров: 706; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |