2.1 Примеры задач целочисленного программирования.
Задача “о ранце” (задача “о загрузке”).
Это задача, связанная с выбором наилучшего состава предметов, подлежащих укладке в походный ранец (вагон, корабль и т.д.) при известном предельном весе ранца, причём каждому из предметов ставится в соответствие оценка его важности. Получающаяся задача имеет линейную ц.ф. и линейное ограничение, выраженное через целочисленные переменные.
Пример: максимизировать
ц.ф. 
При ограничениях 
и целые;
В практических
ситуациях на переменные задачи о ранце
часто накладывается ограничение вида
.
В этом случае задачу называют “0 - 1”
задачей о ранце.
В более общем
случае на практике может потребоваться,
чтобы значение переменных удовлетворяло
условиям
.
В этом случае получающаяся задача
называется задачей о ранце с ограниченными
сверху переменными.
Задачу о ранце можно решить в виде обычной задачи ЛП путём простого ранжирования переменных в соответствии со значениями отношения коэффициентов ц.ф. к коэффициентам ограничений. Это так называемый “алгоритм жадности”.
В этом случае задачу можно сформулировать так:
Максимизировать
ц.ф. 
При
ограничениях 
(1)
и целые;
Здесь
при всех j
.
Ранжирование
переменных осуществляется в соответствии
с такой штриховой индексацией:
,
где последовательность
получена
перестановкой прежних индексов в
соответствии со сформулированным
правилом.
Задача решается
путём приписывания переменной
максимально возможного значения, не
нарушающего ограничения (1) или любого
другого ограничения, наложенного на
(например, ограничение типа “0 - 1”).
Затем переменной
придаётся максимально возможное
значение, не нарушающее ограничение, с
учётом уже присвоенного значения
переменной
и так далее.
В случае рассматриваемой задачи:
,
,
,
,
.
Тогда 
,
– так выглядит решение для задачи ЛП.
Для задачи ЦП
решение будет таким:
,
,
.
Часто на практике встречается обобщённая задача о ранце, которая называется многомерной задачей о ранце и формулируется следующим образом:
Минимизировать
ц.ф. вида: 
При ограничениях 
И при условии 
,
Простые алгоритмы решения многомерной задачи о ранце можно получить в связи с тем, что при таких ограничениях дробный вектор можно округлить до ближайшего нижнего целочисленного значения , также удовлетворяющего этому условию.
Эта задача характерна для практических приложений, связанных с расчетом загрузки транспортных средств, распределения капиталовложений и т.д.
2.2
Задачи с постоянными элементами затрат
Это задачи, которые характеризуются наличием в составе управляющих переменных так называемых «единовременных» затрат (первоначальной инвестицией) и связаны с выбором вариантов при создании или расширении сферы деятельности какого-либо предприятия.
Этот класс задач наиболее часто в практических приложениях связан с производством и отражает не только текущие издержки, связанные с функционированием предприятия, но и начальные единовременные затраты.
Минимизировать
ц.ф. 
При ограничениях
,
Векторы
и
имеют
одинаковую размерность, и условие
означает
.
Последнее условие
выражает тот аспект, что изготовление,
покупка или обработка некоторого
положительного количества продукта
требует фиксированных затрат
.
Из условия
автоматически следует
(но только в случае минимизации).
Данной формулировке
задачи придают более формализованную
структуру, предполагая, что существует
некоторая предельная величина
,
при которой для всех
,
удовлетворяющих ограничениям
и
выполняется условие
,
тогда к задаче можно добавить ограничение
вида
,
которое будет выполняться при всех
.
В этом случае формулировка рассматриваемой
задачи как задача ЦП может быть дана
следующим образом:
Минимизировать ц.ф.
При ограничениях
;
,
,
- целое, где
- последовательность
.
Для того, чтобы в
явном виде показать, что
,
иногда добавляют ограничение вида
(
-
единичный вектор), хотя при
это ограничение избыточно.
5.2
- получение ослабленной задачи путём замены некоторых ограничений задачи-истока некоторой неотрицательной линейной комбинацией этих ограничений, которые затем вносятся в ц.ф. (как в обобщённом методе Лагранжа).
- эти ограничения используются в виде одного или более составных ограничений и называются замещёнными ограничениями.
Все эти методы с последовательным усилением ограничений основываются на одном из вариантов простой процедуры:
решить очередную ослабленную задачу
если это решение для задачи-истока недопустимо, определить подмножество нарушенных ограничений и подмножество ограничений, имеющих запас, после чего видоизменить ослабленную задачу путём увеличения весов линейной комбинации, связанной с первым множеством и уменьшения весов, связанной со вторым.
2. На шаге 2) и 3) можно воспользоваться эвристическими методами получения пробных решений выбранной задачи, после чего проверить, обеспечивают ли они улучшение решения исходной задачи.
В схеме реализации двойственных методов, помимо указанных, имеется три основных процедуры, которые связаны с выбором дальнейших путей решения и которые определяют эффективность всех методов:
Выбор следующей задачи из списка
Выбор ослабленной задачи (или их совокупности) для задания задачи-истока
Выбор отсечения или множества предварительных отсечений, которые необходимы для ограничений новых порождённых задач.