![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Целочисленные оптимизационные модели в промышленности, АПК. Примеры. Методы решения.
В моделях экономического планирования иногда встречается требование целочисленности всех или некоторых переменных. Такие модели называются целочисленными или частично целочисленными оптимизационными моделями. Рассмотрим формулировку такого вида модели (типичный пример).В некотором транспортном средстве имеется m отсеков, оборудованных для перевозки При этом 1) неделимостью, т.е. для транспортировки продукцию можно выбирать в количестве 2) полезностью с 3) величиной Пусть при ограничениях на вместимости отсеков: Примером целочисленной оптимизационной модели является задача коммивояжера. Эта задача формируется следующим образом. Коммивояжер должен побывать в ряде городов. Расстояние между городами известно. Коммивояжер выбирает самый короткий замкнутый маршрут, начинающийся в городе, где он живет, проходящий один и только один раз через каждый город, который он должен посетить и заканчивающийся в исходном пункте. Его маршрут должен минимизировать суммарную длину пройденного пути. Для составления математической модели введем матрицу расстояний между городами -
Целочисленная оптимизационная модель примет вид: при ограничениях:
Система ограничений обеспечивает построение маршрута, при котором коммивояжер въезжает в каждый город только один раз и выезжает из каждого города только один раз. Еще одним примером целочисленной оптимизационной модели является задача о назначениях. Имеется
Тогда математическая модель примет вид: найти план назначения и который удовлетворяет ограничениям
Отметим, что точкой оптимума для целочисленной оптимизационной модели может быть любая точка из области допустимых решений. Но решить целочисленную оптимизационную модель симплексным методом нельзя, так как округляя решение до целого, мы можем получить план далекий от оптимального или вообще не удовлетворяющий системе ограничений. Методы решения целочисленных оптимизационных моделей можно разделить на следующие группы. 1) методы отсечения; 2) комбинаторные методы; 3) приближенные методы. Сущность методов отсечения состоит в том, что сначала решается задача без условия целочисленности. Если полученный план будет целочисленным, то задача решена. В противном случае добавляется новое ограничение со свойствами: 1) оно должно быть линейным; 2) должно отсекать найденный оптимальный нецелочисленный план; 3) не должно отсекать ни одного целочисленного плана. Такое дополнительное ограничение называется правильным отсечением. Затем полученная задача решается с учетом нового ограничения и т.д. Комбинаторные методы – методы направленного частичного перебора допустимых планов. Из них наиболее универсальным является метод ветвей и границ. Использование ЭВМ привело к появлению приближенных методов решения целочисленных оптимизационных моделей.
|