Решение задач целочисленного линейного программирования в MathCAD

 

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

В общем виде задача целочисленного линейного программирования имеет следующий вид:

,

, , (6.29)

, ,

.

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

Методы целочисленной оптимизации можно разделить на следующие основные группы: 1) методы отсечения (к примеру, метод Гомори); 2) комбинаторные методы (к примеру, метод «ветвей и границ»); 3) приближенные методы.

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

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

Из решения, представленного на рис. 54, следует, что данная задача имеет конечный оптимум, однако найденное оптимальное решение нецелочисленное.

Рис. 54. Фрагмент MathCAD-документа: