Глава 5. Задача целочисленного линейного программирования
5.1.Постановки и методы решения
Целочисленное программирование ориентировано на решение задач математического программирования, в которых все или некоторые переменные должны принимать только целочисленные значения.
Задача называется полностью целочисленной, если условие целочисленности наложено на все ее переменные; когда это условие относится лишь к некоторым переменным, задача называется частично целочисленной. Если при этом ЦФ и функции, входящие в ограничения, линейные, то задача является линейной целочисленной.
Несмотря на то, что к настоящему времени разработан ряд методов решения целочисленных задач, ни один из них не обеспечивает желаемой эффективности соответствующих вычислительных процедур, что особенно проявляется при увеличении размерности задачи. Таким образом, в отличие от ЗЛП, время решения которых относительно невелико, реализация целочисленных алгоритмов в ряде случаев весьма затруднительна.
Одна из основных трудностей в целочисленном программировании связана с эффектом ошибки округления, возникающим при использовании цифровых ЭВМ. Даже наличие алгоритмов, применимых для решения задач с целочисленными коэффициентами и позволяющих обойтись без оперирования дробями (и, следовательно, избежать влияния ошибок округления), не упрощает ситуации, поскольку такие алгоритмы (в ряде случаев) сходятся чрезвычайно медленно.
Методы решения задач целочисленного линейного (ЗЦЛП) программирования можно условно разделить на две группы: методы отсечений, комбинаторные методы.
Исходной задачей для демонстрации возможностей методов отсечений, используемых при решении линейных целочисленных задач, является задача с ослабленными ограничениями, которая возникает в результате исключения требования целочисленности переменных. По мере введения специальных дополнительных ограничений, учитывающих требование целочисленности, многогранник допустимых решений ослабленной задачи постепенно деформируется, до тех пор пока координаты оптимального решения не станут целочисленными. Название «методы отсечений» связано с тем обстоятельством, что вводимые дополнительные ограничения отсекают (исключают) некоторые области многогранника допустимых решений, в которых отсутствуют точки с целочисленными координатами.
В основе комбинаторных методов лежит идея перебора всех допустимых целочисленных решений. Разумеется, на первый план здесь выдвигается проблема разработки тестовых процедур, позволяющих непосредственно рассматривать лишь часть (относительно небольшую) указанных решений, а остальные допустимые решения учитывать некоторым косвенным образом.
Определение задачи целочисленного программирования.
Задача математического программирования, управляемые переменные которой принимают только целочисленные значения, называется задачей целочисленного программирования (ЗЦП)
Экономические задачи, сводящиеся к ЗЦП:
Задача о ранце (задача о загрузке)
Задача о назначениях
Задача коммивояжера
Задача оптимального раскроя
Задача о распределении капитальных вложений
Пример. 5.1. Задача формирования портфеля инвестиционных проектов для предприятий
Обозначим через:
m
– количество рассматриваемых
предприятий;
i
- номер предприятия;
ni
– число вариантов развития (проектов);
j
– номер варианта (проекта);
– капитальные вложения для i-го
предприятия при j-ом
варианте развития;
– выпуск продукции i-м
предприятием по j-му
варианту;
К
– общий объем капитальных вложений;
B
– общий объем выпуска для
всех предприятий;
– прибыль от реализации j-го
проекта на i-ом
предприятии.
В принятых обозначениях модель оптимального портфеля примет вид.
В общем виде постановка задачи целочисленного линейного программирования (ЗЦЛП) имеет вид:
- полностью целочисленная ЗЛП
- частично целочисленная ЗЛП
Пример 5.2:
Решением
данной задачи без условия целочисленности
(ЗЛП) является точка
.
Решением
ЗЦЛП является точка
.
Всевозможные способы (по недостатку, по избытку) приводят к следующим точкам:
каждая из которых не является допустимой, т.е. попытка найти решение ЗЦЛП путем округления соответствующего решения ЗЛП является несостоятельной.
П
ример
5.3:
Существует принципиальная возможность свести решение задачи
(5.1)-(5.4) к нахождению оптимального плана некоторой задачи
линейного программирования (без условия целочисленности переменных).
Основная трудность в использовании этой возможности состоит в том, что в вычислительном отношении эта проблема столь же сложна, как и исходная задача поиска оптимального целочисленного решения. Однако эта идея привела к созданию нескольких алгоритмов решения ЗЦЛП, носящих название "методы отсечения".