Целочисленные оптимизационные модели

Формулировка целочисленной оптимизационной модели.

Примеры. Способы ответа

В моделях экономического планирования время от времени видится требование целочисленности всех либо некоторых переменных. Такие модели именуются целочисленными либо частично целочисленными оптимизационными моделями.

Разглядим формулировку для того чтобы вида модели (обычный пример).В некоем транспортном средстве имеется m отсеков, оборудованных для перевозки видов продукции. Известна вместимость , , каждого отсека.

Наряду с этим — ый, , вид продукции характеризуется:

1) неделимостью, т.е. для транспортировки продукцию возможно выбирать числом , кратном единице: 0, 1, 2, …;

2) полезностью с единицы — ой продукции, к примеру, ценой единицы груза;

3) величиной занятости — го отсека при перевозке единицы — ой продукции.

Пускай — количество выбираемых для транспортировки единиц — ой продукции, загружённой в контейнер. Требуется отыскать замысел перевозки, при котором максимизируется неспециализированная полезность рейса. Математическая модель примет вид:

при ограничениях на вместимости отсеков:

Примером целочисленной оптимизационной модели есть задача коммивояжера. Эта задача формируется следующим образом.

Коммивояжер обязан побывать в ряде городов. Расстояние между городами известно. Коммивояжер выбирает самый маленький замкнутый маршрут, начинающийся в городе, где он живет, проходящий только один раз через любой город, что он обязан посетить и заканчивающийся в исходном пункте. Его маршрут обязан минимизировать суммарную длину пройденного пути.

Для составления математической модели введем матрицу расстояний между городами — и малоизвестные размеры:

Целочисленная оптимизационная модель примет вид:

при ограничениях:

.

Совокупность ограничений снабжает построение маршрута, при котором коммивояжер въезжает в любой город лишь один раз и выезжает из каждого города лишь один раз.

Еще одним примером целочисленной оптимизационной модели есть задача о назначениях.

Имеется исполнителей, каковые смогут делать разных работ. Известна полезность , связанная с исполнением — ым исполнителем — ой работы. Нужно так назначить исполнителей на работы, дабы добиться большой полезности при условии, что любой исполнитель возможно назначен лишь на одну работу и за каждой работой должен быть закреплен лишь один исполнитель. Для составления математической модели введем малоизвестные

Тогда математическая модель примет вид: отыскать замысел назначения , при котором

и что удовлетворяет ограничениям

.

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

Способы ответа целочисленных оптимизационных моделей возможно поделить на следующие группы.

1) способы отсечения;

2) комбинаторные способы;

3) приближенные способы.

Сущность способов отсечения пребывает в том, что сперва решается задача без условия целочисленности. В случае если полученный замысел будет целочисленным, то задача решена. В другом случае добавляется новое ограничение со особенностями: 1) оно должно быть линейным; 2) должно отсекать отысканный оптимальный нецелочисленный замысел; 3) не должно отсекать ни одного целочисленного замысла. Такое дополнительное ограничение именуется верным отсечением. После этого полученная задача решается с учетом нового ограничения и т.д.

Комбинаторные способы – способы направленного частичного перебора допустимых замыслов. Из них самоё универсальным есть способ границ и ветвей.

Применение ЭВМ стало причиной появлению приближенных способов ответа целочисленных оптимизационных моделей.

Лекция 2: Задача линейного программирования. Задача о ресурсах


Также читать:

Понравилась статья? Поделиться с друзьями: