Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
В методах отсечения основу составляют 3 алгоритма Гомори(дискретный, смешанный, циклический). Все они базируются на использовании процедуры линейного программирования для последовательности задач, в которую по мере решения вводятся особые дополнительные ограничения.
В комбинаторных методах процедура линейного программирования почти не используется, а используется сокращения поиска возможных решений с помощью анализа исходного множества решений
Приближенные методы применяются для решения задач большой размерности, решения которых в значительной степени затруднено дефицитом временных и технических ресурсов.
Человеко-машинные методы требуют значительных вычислений.
Общая задача целочисленного линейного программирования
Рассмотрим задачу о размещении оборудования: есть n предметов, каждый из которых обладает определенный коэффициентов полезности(стоимость, калорийность и т.д.). Общая полезность от размещенных предметов равна сумме полезностей отдельных предметов. Все n предметов не могут быть размешены в заданном объеме (ограничения по объему) и/или грузоподъемность тела меньше суммарного веса предметов(ограничения по массе)
Требуется при ограничениях по массе и объему обеспечить размещения предметов, при котором общая полезность размещенных предметов была бы максимальной
Введем обозначение:
Тогда формально задача ставится следующим образом:
Дата публикования: 2015-02-03; Прочитано: 235 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!