Экстремальные модели менеджмента и экономики

Скачать в pdf «Экстремальные модели менеджмента и экономики»

%


0


Х4= 1


0


0


0


1


0


0


%


5/4


А/


0


0


5


0


0


0


5


10/4


opt

Получено оптимальное целочисленное решение задачи. При этом, кроме основных переменных, дополнительные переменные тоже получились целочисленными.


Оптимальное решение: Х = 14; х2 = 143; х3 = 0; целевая функция равна 4850,00 у.е.


Вопросы для самопроверки


1.    Является ли условие целочисленности переменных задачи линейного программирования обязательным?


2.    Можно ли применять методы математического округления оптимального решения задачи до целых значений, если существует требование целочисленности?


3.    В чем заключается основная идея метода отсечений Гомори решения задач линейного программирования?


4.    Можно ли добиться целочисленности всех переменных задачи (основных и дополнительных) методом отсечений Гомори?


5.    Решите методом отсечений Гомори следующие задачи линейного программирования:


а)    max(x1+2х2), x1 + 3x2 = 48,


7x12= 78,


x1, х2> 0, x1, x2 £ Z;


б)    в контейнер вместимостью 214 л должны быть загружены неделимые предметы первого, второго и третьего типов. Предметы имеют объемы соответственно 8, 23 и 43 л и стоимость 2, 7 и 14 у.е. Определить такую загрузку контейнера, при которой он не будет перегружен и суммарная стоимость погруженных предметов будет максимальной.


3.2. Метод ветвей и границ решения задачи о коммивояжере


Класс методов ветвей и границ достаточно многообразен. Впервые термин «ветви и границы» был использован в работе Литтла Дж. и др. «Алгоритм для решения задачи о коммивояжере» (1965). Первый алгоритм ветвей и границ для решения задач целочисленного линейного программирования дали Лэнд и Дойг. Этот метод применим для решения как полностью, так и частично целочисленных задач и относится к методам дискретной оптимизации.

Скачать в pdf «Экстремальные модели менеджмента и экономики»