Целочисленные оптимизационные модели в промышленности, АПК. Примеры. Методы решения.

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

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

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

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

.

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

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

1) методы отсечения;

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

3) приближенные методы.

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

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

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