Российский экономический

6.
2. Примеры задач 
целочисленного программирования 
В параграфе рассматриваются примеры решения задач, ни одна из кото-
рых не является ярко выраженной задачей целочисленного программирования. 
Значительно больший интерес представляют открываемые целочисленным 
112

---

программированием возможности приведения «некорректных» задач к стан-
дартному виду задач математического программирования. Использование спе-
циальных приемов позволяет получить решение в ряде случаев, когда решить 
задачу с помощью прямых методов оказывается крайне затруднительным. 
 
Пример 
(задача с постоянными элементами затрат).
 
В одной из типичных за-
дач планирования производства рассматривается 
N
видов промышленной про-
дукции. Затраты на производство продукции вида 
j
складываются из постоянных 
затрат в объеме 
𝐾
𝑗
, не зависящем от количества произведенной продукции и те-
кущих издержек 
𝑐
𝑗
на производство единицы продукции.
 
Таким образом, если 
𝑥
𝑗
— объем выпуска продукции вида 
j
, функцию сум-
марных затрат можно записать следующим образом: 
𝐶
𝑗
(𝑥
𝑗
) = {
𝐾
𝑗
+ 𝑐
𝑗
𝑥
𝑗
, 𝑥
𝑗
> 0
0, 𝑥
𝑗
= 0
. 
Естественным выглядит стремление минимизировать величину суммарных 
затрат: 
𝑧 = ∑
𝐶
𝑗
(𝑥
𝑗
) → min
𝑁
𝑗=1
. 
Рассматриваемый критерий не является линейным по переменной 
𝑥
𝑗
вслед-
ствие разрыва в начале координат. Поэтому задача с целевой функцией 
z
оказы-
вается непригодной для дальнейшего исследования классическими методами. 
Введение дополнительных булевых переменных позволяет преобразовать за-
дачу к виду, «более приемлемому» с аналитических позиций. Пусть: 
𝑦
𝑗
= {
0, 𝑥
𝑗
= 0
1, 𝑥
𝑗
> 0
, 
что можно переписать в форме (линейного) неравенства: 
𝑥
𝑗
≤ 𝑀𝑦
𝑗
. 
Здесь 
М > 0
достаточно велико, чтобы условие 
𝑥
𝑗
≤ 𝑀
выполнялось для всех 
допустимых объемов выпуска продукции. Теперь исходную задачу можно 
сформулировать следующим образом: 
𝑧 = ∑
𝐶
𝑗
𝑥
𝑗
+ 𝐾
𝑗
𝑦
𝑗
→ min
𝑁
𝑗=1
. 
0 ≤ 𝑥
𝑗
≤ 𝑀𝑦
𝑗
, 𝑗 = 1, … , 𝑁
, 
𝑦
𝑗
∈ {0,1}, 𝑗 = 1, … , 𝑁
. 
Рассмотрим подробнее ограничение 
𝑥
𝑗
≤ 𝑀𝑦
𝑗
. При условии 
𝑥
𝑗
> 0
имеем 
𝑦
𝑗
= 1
, и целевая функция включает постоянные затраты 
𝐾
𝑗
. Если 
𝑥
𝑗
= 0
, то 
𝑦
𝑗
может принимать значения 0 или 1, однако поскольку 
𝐾
𝑗
> 0
и 
z
требуется ми-
нимизировать, переменная 
𝑦
𝑗
, должна быть равна нулю. 
Следует подчеркнуть, что исходная задача с постоянными элементами 
затрат не имеет никакого отношения к целочисленному программированию. 
Тем не менее «преобразованная» задача представляет собой частично целочис-
ленную задачу с булевыми переменными («0 – 1» задачу). Необходимость рас-
смотренного преобразования была обусловлена исключительно аналитически-
ми соображениями. В самом деле, введенные булевы переменные являются 
вспомогательными, так как ассоциированную с ними информацию можно 
назвать полезной лишь условно. Например, 
𝑦
𝑗
= 0
в оптимальном решении 
означает, что 
𝑥
𝑗
> 0
.