Линейные целочисленные задачи оптимизации

ЛИНЕЙНЫЕ 
ЦЕЛОЧИСЛЕННЫЕ 
ЗАДАЧИ ОПТИМИЗАЦИИ

Г.А. СОКОЛОВ

УЧЕБНОЕ ПОСОБИЕ

Рекомендовано
в качестве учебного пособия 
для студентов высших учебных заведений, 
обучающихся по направлениям подготовки 
38.03.01 «Экономика», 38.03.02 «Менеджмент»
(квалификация (степень) «бакалавр»)

Москва
ИНФРА-М
2020

УДК 519.8(075.8)
ББК 22.18я73
 
С59

Соколов Г.А. 
Линейные целочисленные задачи оптимизации : учебное пособие / 
Г.А. Соколов. — Москва : ИНФРА-М, 2020. — 132 с.  — (Высшее образование: Бакалавриат). — DOI 10.12737/19667.

ISBN 978-5-16-011144-5 (print)
ISBN 978-5-16-103227-5 (online)

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

УДК 519.8(075.8)
ББК 22.18я73

Р е ц е н з е н т ы:
Н.Г. Назаров, д-р техн. наук, профессор, ведущий научный сотрудник АО 
«ЦНИИ ЭИСУ»;
В.К. Гарипов, д-р техн. наук, профессор кафедры информационных технологий и приборостроения Московского государственного технического 
университета радиотехники, электроники и автоматики

С59

© Соколов Г.А., 2016
ISBN 978-5-16-011144-5 (print)
ISBN 978-5-16-103227-5 (online)

ВВЕДЕНИЕ. ПОСТАНОВКА ЗАДАЧ 

ОПТИМИЗАЦИИ И ИХ КЛАССИФИКАЦИЯ

В настоящее время практически во всех учебных программах эко
номических и технических вузов предусмотрены разделы, посвященные теории оптимизации. Методы решения безусловных экстремальных задач обычно изучаются в курсах высшей математики, 
а методы решения условно-экстремальных задач (в частности, линейного и нелинейного программирования, динамического программирования, теории игр) — в специальных курсах или в курсе исследования операций. В настоящем пособии, посвященном дискретным 
задачам, предполагается, что читатель, во-первых, знаком с основами названных разделов теории оптимизации, а во-вторых, бурное 
развитие таких прикладных задач [16], как задачи транспортного 
типа, планирования работ при создании автоматизированных систем 
управления, оптимального управления производством, оптимального распределения ресурсов, оптимального прогнозирования, оптимизации учебных расписаний, оптимизации перевозки грузов, составления оптимальной производственной программы и т.д., требуют 
для своего решения специальных методов, относящихся к теории 
дискретной оптимизации.

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

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

Книга написана простым языком, доступным студентам второго 

курса. Для формул, таблиц и рисунков принята двойная нумерация: 
первый — номер лекции, второй — порядковый.

Оптимизационные задачи рассматриваются для функций, опре
деленных на множествах так называемого конечномерного евклидового пространства E n.

Совокупность всех наборов X
x
x
xn
= (
,
,...,
)
1
2
 вещественных чисел 

называют евклидовым пространством размерности n:

1) если точки этого пространства можно складывать, вычитать, 

умножать на число и при этом выполняется свойство линейности;

2) если определено понятие произведения двух векторов 

X
x
x
xn
= (
,
,...,
)
1
2
 и  по формуле XY
x y
x y
x y
n
n
= (
)
1
1
2
2
,
,...,
 и, как след
ствие, определена длина (норма) вектора //
//
X
XX
=
(
). Множество 

3

O
x
y
E
y
x
n

ε
ε
( ) =
∈
−
≤
{
}
:||
||
 называют ε-окрестностью точки х. 

Множество X
E n
⊂
 называют замкнутым, если оно содержит все свои 

предельные точки, ограниченным, если существует такое ε ∈
∞
(
)
0,
,

что O
x
X
x
X
ε ( ) ⊇
∀
∈
, выпуклым, если оно вместе с любыми своими 

двумя точками ′
′′
x
x
,
 содержит соединяющий их отрезок вида 

[
,
]
{
:
,
}
′
′′ =
∈
=
′ +
−
(
) ′′
≤
≤
x x
x
E
x
x
x
n
λ
λ
λ
1
0
1  (рис. В.1).

                                            а                                                б

Рис. В.1: множества: а — выпуклое, б — невыпуклое

Функция f x( ), определенная на выпуклом множестве X
E n
⊂
,

называется выпуклой (вниз) на X, если f
x
x
f x
(
)
λ
λ
λ
′ +
−
(
) ′′ ≤
′
(
) +
1

+
−
(
)
′′
(
) ∀ ′
′′ ∈
∈
1
0 1
λ
λ
f x
x
x
X
,
,
[ , ].

Если для всех ′ ≠
′′
x
x
приведенное неравенство выполняется как 

строгое, то функция f x( ) называется (строго) выпуклой вниз. Если 
это неравенство выполняется в обратную сторону, то функция f x( )
называется (строго) выпуклой вверх (рис. В.2).

                                         а                                                                  б

Рис. В.2: а — функция, выпуклая вверх, б — функция, выпуклая вверх и вниз

Дважды непрерывно дифференцируемые функции f на выпуклом 

множестве X
E n
⊂
 выпукла (строго) тогда и только тогда, когда ма
трица вторых производных ∂
( )

∂ ∂

2 f x
x x
i
j

 неотрицательная (положи
f(x)

x
x1
x2

f(x)

x
x1
x2

4

тельная) определена. Для функции одной переменной это опреде
ление упрощается: ∂
( )

∂
≥
>(
)

2

2
0
0
f x
x
(
)
. Если f  на выпуклом множестве 

X
E n
⊂
 выпукла вниз, то множество {
:
( )
},
x
X
f x
b
∈
≤
 где b ∈ E, вы
пукло. Если f  на выпуклом множестве X
E n
⊂
 выпукла вверх, то 

множество {
:
( )
},
x
X
f x
b
∈
≥
 где b ∈ E выпукло.

Пусть задано множество X
E n
⊂
и функция f x( ), определенная 

на Х, тогда задача определения экстремальной точки этой функции 
принимает вид:

( )

( )

или

min,

max,
.

n

n

f x
x
X
E

f x
x
X
E

⇒
∈
⊂

⇒
∈
⊂

(В.1)

При этом f называется целевой функцией, функцией цели, Х на
зывается допустимым множеством, x
X
∈
называется допустимой 

точкой (планом).

Точка x* называется точкой глобального минимума функции f на 

Х, если

f x
f x
x
X
*
.
(
) ≤
( ) ∀
∈

Точка x* называется точкой локального минимума функции f на 

Х, если

f x
f x
x
O
x
*
* .
(
) ≤
( ) ∀
∈
(
)
ε
 (В.2)

Точка x* называется точкой глобального максимума функции f на 

Х, если

f x
f x
x
X
*
(
) ≥
( ) ∀
∈
x
X
*
.
∈

Точка x* называется точкой локального максимума функции f на 

Х, если

f x
f x
x
O
x
*
* .
(
) ≥
( ) ∀
∈
(
)
ε

При n = 1 говорят об одномерной задаче оптимизации, при n > 1

говорят о многомерной задаче оптимизации. И в том, и в другом 
случае следует различать два варианта. Если множество Х = En, то 
задача (1) называется задачей безусловной оптимизации, если же 
множество Х является истинным подмножеством Еn, т.е. 
X
E
X
E
n
n
⊂
≠
,
, то задача (1) называется задачей условной оптими
зации (условно экстремальной задачей). Последние принято разбивать на два класса. К первому относят так называемые классические 
задачи на условный экстремум, когда допустимое множество задается 
системой уравнений

5

X
x
E
g x
i
n
n

i
=
∈
( ) =
=
{
:
,
, ...,
}.
0
1

Ко второму относят так называемые задачи математического про
граммирования, когда допустимое множество имеет вид:

X
x
E
g x
i
k g x
i
k
k
n
n

i
i
=
∈
( ) =
=
( ) ≤
=
+
+
{
}
:
,
, ...,
;
,
,
, ...,
.
0
1
0
1
2

В каждом классе можно выделить важные подклассы так называ
емых выпуклых задач безусловной или условной оптимизации, когда 
Х — выпуклое множество, а f — выпукла вверх при максимизации 
и выпукла вниз при минимизации. Исключительная роль выпуклых 
задач объясняется тремя их свойствами.

1. Для выпуклой задачи локальный экстремум является одновре
менно глобальным.

Действительно, пусть x
X
* ∈
 — локальное решение, тогда существует 

величина ε > 0, такая что f x
f x
x
O
x
*
* .
(
) ≤
(
) ∀
∈
(
)
0
0
ε
 В частности, 

можно выбрать такое λ0
0 1
∈(
)
,
, что x
x
x
O
x
0
0
0
1
=
+
−
(
)
∈
(
)
λ
λ
ε

*
* , где 

х — произвольная точка из Х, лежащая вне области O
x
ε

* .
(
)  Тогда в силу 

выпуклости вверх функции f имеем:

f x
f
x
x
f x
f x

f x
f x
f

*
*
*

*

(
) ≤
+
−
(
)
(
) ≤
( ) +
−
(
) (
) =

=
( ) −
(
) +

λ
λ
λ
λ

λ
λ

0
0
0
0

0
0

1
1

x
f x
f x

f x
f x
x
X

*
*

*

[
]

(
)
,

(
) ⇒
( ) −
(
) ≥
⇒

⇒
( ) ≥
∀
∈

λ0
0

что и требовалось доказать.

2. Второе свойство состоит в том, что необходимые условия оп
тимальности для выпуклых задач одновременно являются и достаточными. Докажем это свойство применительно к задачам безусловной оптимизации. Вспомним, что необходимые условия оптимальности состоят в том, что

grad f x
f x

x

f x

x

f x

xn

*
,
, ...,
,

*
*
*

(
) =
∂ (
)

∂

∂ (
)

∂

∂ (
)

∂







 =

1
2

0

где x* есть точка минимума функции f x( ) при X
E n
=
.

Для выпуклых вниз функций, если 
(
)
и 
0 1
x
X
∈
λ ∈
,
, то

f
x
f x
f x
f x
f x
f x
f x

f x

λ
λ
λ
λ
λ
+
−
(
) (
)
(
) ≤
( ) +
−
(
) (
) =
( ) −
(
) +
(
) ⇒

⇒
(

1
1
*
*
*
*
[
]

) −
(
) ≥
(
) +
−
(
)
(
) −
(
)
f x
f x
x
x
f x
*
*
*
* .
1
λ
λ

Полученное свойство имеет важное значение для вычислительной 

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

6

3. Третье свойство состоит в том, что множество решений 

само выпуклое. Действительно, пусть 
(
)
1
2
и
0 1
x
x
X
∈
λ ∈
*
,
,
, тогда 

f x
f x
f
1
2
(
) =
(
) =
*, при этом

f
f
x
x
f x
f x
f

x
x
X

*
*

*,

≤
+
−
(
)
(
) ≤
(
) +
−
(
) (
) =
⇒

⇒
+
−
(
)
∈

λ
λ
λ
λ

λ
λ

1
2
1
2

1
2

1
1

1

т.е. X * выпукло. Если f x( ) — строго выпуклая, то предыдущее 
неравенство принимает вид f
f
x
x
f x
* ≤
+
−
(
)
(
) <
(
) +
λ
λ
λ
1
2
1
1

+
−
(
) (
) =
1
2
λ f x
f , что невозможно. Следовательно, x
x
1
2
=
, т.е. ре
шение единственное.

Частным случаем выпуклых задач математического программи
рования являются так называемые задачи квадратичного программирования

f x
c x
Ax x
( ) = (
) +
(
) ⇒
,
,
min,
1
2

где А — симметричная положительная (неотрицательная) матрица 
размера n
n
× , а (с – n)-мерный вектор, при следующих ограниче
ниях:

a x
b
i
k

a x
b
i
k
k
m

x

ij

j

n

j
i

ij

j

n

j
i

j

=

=

∑

∑

≥
=

=
=
+
+

1

1

1 2

1
2

,
, , ...,
,

,
,
, ...,
,

≥
=
≤
0
1 2
,
, , ...,
,
j
s
m

а также задачи квадратичного программирования.

Частным случаем последней является задача линейного програм
мирования, когда А = 0. В качестве частного случая задач нелинейного 
программирования следует назвать задачу геометрического программирования, когда в роли функции цели выступает так называемый 

позином: ( )
1
2

1
2

1

где
0
0
...
,
,
,
m

n

i
i
i
i

i
m
i
ij
f x
c x x
x
x
c
a
=
>
>
∑
— произвольные 

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

В качестве частного случая задач математического программиро
вания следует назвать задачи псевдобулева и целочисленного программирования. Именно эти задачи являются основным предметом 
рассмотрения в настоящей книге.

ЛЕКЦИЯ 1.

ПРИМЕРЫ И ФОРМАЛЬНЫЕ МОДЕЛИ 

ДИСКРЕТНОЙ ОПТИМИЗАЦИИ

В последние 50 лет наблюдается бурное развитие экономико-ма
тематических моделей как в содержательном плане, так и в плане их 
формального анализа. Речь идет в первую очередь о моделях дискретной оптимизации. Этому способствовали, с одной стороны, возрастающие запросы науки и практики экономики, а с другой стороны — развитие вычислительной техники.

В наиболее общей форме задача целочисленной оптимизации 

имеет следующий вид: найти вектор х с неотрицательными компонентами x j j
n
,
, ..., ,
=1
 который максимизирует функцию f x( ) при огра
ничениях g
x
x
i
m
i
n
1
0
1
, ...,
,
, ...,
.
(
) ≤
=
 Задачи, в которых переменные 

являются неотрицательными целыми числами, можно свести 
к случаю двоичных переменных, заменив каждую переменную хj выражением x
x
x
x
x
j
j
j
j

k

jk
=
+
+
+
+
−

1
2

2

3

1
2
2
2
...
, где 
0 
 1
или .
jk
x
=

Пример. Минимизировать в неотрицательных целых числах х1 и х2

функцию

x
x

x
x

x
x

1
2

1
2

1
2

3

3
4

3

+
⇒

−
≥

+
≤

min,

,

.

Из второго неравенства следует x
x
1
2
3
,
,
≤
 положим 

x
x
x

x
x
x

1
11
12

2
21
22

2

2

=
+

=
+

,

,

где x
x
x
x
11
22
12
21
,
,
,
принимают значения ноль или единица и, под
ставив их в вышестоящие функции, получим задачу линейного псевдобулевого программирования:

x
x
x
x

x
x
x
x

x
x
x

11
12
21
22

11
12
21
22

11
12
21

2
3
6

3
6
2
4

2
2

+
+
+
⇒

+
−
−
≥

+
+
+

min,

,

x22
3
≤
.

ПРИМЕРЫ ЗАДАЧ

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

8

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

Пусть i — номер пункта размещения действующего предприятия 

или возможного размещения нового, i = 1, 2, …, m; j — номер пункта 
потребления продукции, j = 1, 2, …, n; bj— потребность в готовой 
продукции пункта j; хi — искомая мощность предприятия в пункте i; 
f x
i
i
( ) — суммарные приведенные затраты, связанные с размещением 

в пункте i предприятия мощности хi; сij— транспортные затраты по доставке единицы продукции из пункта i в пункт j; хij — искомый объем 
поставок продукции из пункта i в пункт j; H
h
h
h
i
i
i
isi
= {
}
1
2
,
, ...,
— 

набор возможных мощностей для пункта размещения i.

Задача состоит в определении для каждого пункта i такого объема 

производства xi из заданного набора Hi и такого плана перевозок xij
готовой продукции, чтобы суммарные производственно-транспортные затраты

f x
c x
i

i

m

i
ij
ij

j

n

i

m

=
=
=
∑
∑
∑
( ) +
⇒

1
1
1

min

при 

x
H
i
m

x
i
m j
n

i
i

ij

∈
=

≥
=
=

,
, , ...,
,

,
, , ...,
,
, , ...,
.

1 2

0
1 2
1 2

Задача 1.2. Многопродуктовые задачи размещения производства
Пусть задано m пунктов производства r видов продуктов. Каждый 

пункт производства i характеризуется множеством вариантов специализации Li
i
i
isi
= {H , H , ..., H },
1
2
 а вариант специализации k задается 

r-мерным вектором H
,
, ...,
ik
ik
ik
rik
a
a
a
= (
)
1
2
, где компоненты alik, 

l = 1, 2, …, r являются объемами производства первого продукта 
в пункте j. Для каждого Hikзаданы производственные затраты ϕi
ik
H
(
),

связанные с реализацией этого варианта в пункте i. Задана также 
потребность пункта j в потреблении продукта i = 1, 2, …, n.

Задача состоит в определении для каждого пункта i (i = 1, 2, …, n) 

такого варианта специализации X
x
x
x
i
i
i
ri
= (
)
1
2
,
, ...,
Хi = (х1i, x2i, …, 

xri) из заданного варианта специализации Li
i
i
isi
= {H , H , ..., H }
1
2

и плана перевозок xlij, i = 1, 2, …, m; j = 1, 2, …, n; l = 1, 2, …, r, чтобы 
суммарные затраты были минимальными

ϕi
i

i

m

lij

i

r

j

n

i

m

lij
x
c x
( ) +
⇒

=
=
=
=
∑
∑
∑
∑

1
1
1
1

min

9

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

x
x
i
m l
r

x
b
j

lij
li

j

m

iij

i

m

lj

≤
=
=

=
=

=

=

∑

∑

,
, , ...,
;
, , ..., ,

,
, ,

1 2
1 2

1 2

1

1

...,
;
, , ..., ,

,
, ...,
,
, , ...,
,

n l
r

X
x
x
x
i
m

x

i
i
i
ri
i

lk

=

= (
) ∈
=

1 2

1 2
1
2
H

i
i
m j
n l
r
≥
=
=
=
0
1 2
1 2
1 2
,
, , ...,
;
, , ..., ;
, , ..., .

.

Задача 1.3. Задачи построения расписаний
Весьма важной прикладной задачей дискретной оптимизации 

является задача теории расписаний или задача календарного планирования. Общая ее постановка такова. Имеется m станков и n деталей, каждая из которых должна пройти обработку на всех станках 
в определенном порядке. Этот порядок может быть одинаковым или 
различным для различных станков. При этом обработка любой детали на любом из станков, раз начавшись, должна быть доведена 
до конца без перерывов. Задана матрица A
aij
=||
||, где аij — время об
работки детали i на станке j. Требуется выбрать такой порядок запуска деталей в обработку, который минимизировал бы общее время 
выполнения всех работ.

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

Задача 1.4. Формирование производственной программы предпри
ятия из портфеля заказов

Для большинства предприятий значительную долю расходов 

на производство составляет оплата потребляемых материальных ценностей. В этих условиях при составлении плана предприятия следует 
учитывать ограниченность имеющихся материальных ресурсов. Задача построения оптимального плана с учетом вышеизложенных 
особенностей состоит в следующем. Предприятие к концу года имеет 
портфель заказов. Все заказы выполнить невозможно из-за дефицита 
некоторых материалов. Известны нормы расхода каждого вида материала на изготовление каждого заказа, запасы материалов, наконец, прибыль, которую получает предприятие от выполнения каждого заказа. Кроме того, каждому заказу в зависимости от его важности ставится в соответствие «вес».

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

10