Студопедия

КАТЕГОРИИ:


Архитектура-(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= 21 х4 + 4 х5

3 3 3

х2=8 – х5

х3=18+х45

Z=25 12 x41 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; Просмотров: 695; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.009 сек.