Математическое программирование: теория и методы

Министерство науки и высшего образования  

Российской Федерации 

Уральский федеральный университет 

имени первого Президента России Б. Н. Ельцина 

МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ: 

ТЕОРИЯ И МЕТОДЫ

Уч е б н о е  п о со бие

Рекомендовано методическим советом  

Уральского федерального университета для студентов,

обучающихся по всем инженерно-техническим  
направлениям подготовки и специальностям

Екатеринбург 

Издательство Уральского университета 

2020 

УДК 519.85(075.8) 
ББК 22.1я73 
          М34

Авторы: Н. В. Гредасова, А. Н. Сесекин, А. Ф. Шориков, М. А. Плескунов 

Рецензенты:
 кафедра экономики и информатизации АНО ВО «Гуманитарный 
университет» (завкафедрой д-р экон. наук, доц. Н. В. Хмелькова);
канд. физ.-мат. наук, ст. науч. сотр. отдела оптимального управления ИММ УрО РАН Д. С. Завалищин

Научный редактор — д-р физ.-мат. наук, проф. В. И. Зенков 

М34
Математическое программирование: теория и методы : учебное пособие / Н. В. Гредасова, А. Н. Сесекин, А. Ф. Шориков, 
М. А. Плескунов ; Мин-во науки и высш. образования РФ. — 
Екатеринбург : Изд-во Урал. ун-та, 2020. — 200 с.
ISBN 978-5-7996-3093-5

Настоящее учебное пособие посвящено задачам линейного и динамического программирования. Содержит постановки основных задач линейного и динамического программирования и основные методы их решения.
Издание предназначается студентам, обучающимся по всем направлениям подготовки и специальностям.
УДК 519.85(075.8) 
ББК 22.1я73 

ISBN 978-5-7996-3093-5
© Уральский федеральный  
     университет, 2020

Оглавление

Введение ...............................................................................................5
1. Постановка задачи линейного программирования ........................6

1.1. Примеры задач линейного программирования .......................6
1.2. Формы записи задач линейного программирования.............13

2. Графический метод решения задач линейного  
программирования .............................................................................21
Задачи для самостоятельного решения .........................................34

3. Теоретические основы линейного программирования ................35

3.1. Выпуклые множества ..............................................................35
3.2. Свойства задач линейного программирования ......................37

4. Решение систем линейных уравнений методом  
Жордана-Гаусса .................................................................................39
5. Симплекс-метод .............................................................................43

5.1. Общая схема симплекс-метода ...............................................44
5.2. Симплекс-таблицы .................................................................47
5.3. Контроль за правильностью заполнения  
симплекс-таблиц ...........................................................................57
5.4. Сокращенные симплекс-таблицы ..........................................57
Задачи для самостоятельного решения .........................................68

6. Метод искусственного базиса ........................................................69
7. М-метод ..........................................................................................74
Задачи для самостоятельного решения .........................................78

8. Теория двойственности ..................................................................79

8.1. Постановка двойственной задачи ..........................................79
8.2. Принцип двойственности .......................................................83
Задачи для самостоятельного решения .........................................95

9. Двойственный симплекс-метод .....................................................96
Задачи для самостоятельного решения .........................................99
10. Транспортная задача .................................................................. 100
10.1. Постановка транспортной задачи ....................................... 100
10.2. Опорный план транспортной задачи и его построение ..... 103
10.3. Преобразование опорного плана в другой опорный план. 
Оценка опорной плана ................................................................ 107
10.4. Алгоритм распределительного метода ................................ 110
10.5. Потенциалы поставщиков и потребителей ........................ 111
10.6. Алгоритм метода потенциалов ............................................ 113

10.7. Несбалансированная транспортная задача ........................ 119
10.8. Усложненные постановки задачи транспортного типа ..... 136
10.9. Блокирование поставок ...................................................... 138
10.10. Несбалансированная транспортная задача  
с приоритетами ..............................................................................44
Задачи для самостоятельного решения ....................................... 176
11. Метод динамического программирования ................................ 179
11.1. Постановка оптимизационной задачи для применения  
метода динамического программирования ................................ 179
11.2. Общая схема метода динамического программирования. 
Уравнение Беллмана .................................................................... 180
11.3. Организация вычислительного процесса  
в схеме метода динамического программирования ................... 182
11.4. Обсуждение возможностей применения  
метода динамического программирования ................................ 185
11.5. Пример решения конкретной задачи целочисленной  
оптимизации с аддитивной целевой функцией  
методом динамического программирования ............................. 187
12. Библиографический список ....................................................... 193

ВВЕДЕНИЕ 

Математическое программирование – раздел математики, занимающийся 

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

«программирование» возник исторически, он не имеет отношения к 

традиционному пониманию программирования как процессу составления 

программ для ЭВМ, а означает в этом случае планирование, выбор 

оптимальной программы действий (от англ. programming).  

Линейное программирование – раздел математического программирования, 

в котором изучаются методы решения задач нахождения экстремума линейной 

функции многих переменных при наличии линейных ограничений. Впервые 

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

составлению оптимального плана перевозок, минимизирующего суммарный 

пробег, встречается в работе советского экономиста А. Н. Толстого (1930 г.). 

В 1931 г. венгерский математик Б. Эгервари рассмотрел одну из частных 

задач линейного программирования – задачу выбора. Им был намечен и метод 

ее решения, который получил название «венгерского метода». Этот метод был 

позже развит американским математиком Г. У. Куном применительно к общему 

классу транспортных задач. Систематическое исследование задач линейного 

программирования, прежде всего экономических задач, разработка общих 

методов их решения были начаты в 1939 г. в работах советского математика 

Л. В. Канторовича и его учеников. Л. В. Канторовичем был предложен общий 

метод решения задач линейного программирования, который лишь в деталях 

отличается от общепринятого сейчас симплекс-метода. В 1975 г. академику 

Л. В. Канторовичу за разработку математических методов в экономике была 

присуждена 
(совместно 
с 
американским 
экономистом 
Т. Купмансом) 

Нобелевская премия по экономике. 

Почти одновременно и, по-видимому, независимо от работ академика 

Канторовича 
методы 
линейного 
программирования 
разрабатывались 

американскими 
учеными. 
В 
американской 
литературе 
первая 
работа, 

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

Ф. Л. Хичкоком. Основной метод решения задач линейного программирования 

– симплекс-метод – был опубликован в 1949 г. Дж. Данцигом. Дальнейшее 

развитие методы линейного и нелинейного программирования получили в 

работах Форда, Фалкерсона, Куна, Гасса, Лемке и др. 

Динамическое программирование, как и линейное программирование, 

является составной частью математического программирования. 

Динамическое программирование – метод нахождения оптимальных 

решений 
многошаговых 
процессов. 
Динамическое 
программирование 

сформировалось в начале 50-х годов XX века благодаря работам американского 

математика Р. Беллмана. 

 

 

 

1. Постановка задачи линейного программирования 

1.1. Примеры задач линейного программирования 

Прежде чем применить методы линейного программирования к решению 

конкретной экономической задачи, необходимо составить ее математическую 

модель. Под экономико-математической моделью понимают математическое 

описание 
исследуемого 
экономического 
процесса, 
в 
котором 
учтены 

закономерности экономического процесса в абстрактной математической 

форме. Если исследуемая экономическая задача носит экстремальный характер, 

т. е. требуется максимизировать или минимизировать какую-то характеристику 

исследуемого процесса (а именно к таким задачам относятся задачи линейного 

программирования), то в модель вводится некоторая целевая функция, 

экстремум которой требуется найти. 

Обычно 
схема 
формирования 
экономико-математической 
модели 

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

1) сначала осуществляется выбор некоторого числа переменных величин, 

заданием числовых значений которых однозначно определяется одно из 

возможных состояний исследуемого явления; 

2) затем с помощью введенных переменных устанавливаются взаимосвязи, 

присущие исследуемому явлению, в виде математических соотношений 

(уравнений, 
неравенств); 
эти 
соотношения 
образуют 
систему 

ограничений задачи; 

3) вводится 
количественное 
выражение 
выбранного 
критерия 

оптимальности в форме целевой функции. 

Для иллюстрации приведенной схемы рассмотрим следующие примеры, 

задачи 
составления 
производственного 
плана 
распределения 
ресурсов, 

составления рациона питания и транспортную задачу 

Задача составления производственного плана распределения ресурсов 

При изготовлении n видов продукции 
)
,...,
2,1
(
n
j
Pj

 используется m видов 

сырья 
)
,...,
2,1
(
m
i
Si

, запасы которого 
ib  для 
iS  известны. Количество единиц 

сырья 
iS , идущего на изготовление единицы продукции 
jP , равно 
ij
a , а 

прибыль, полученная от реализации единицы продукции 
jP , равна 
jc (ден. ед.). 

Все перечисленные выше данные представлены в табл. 1.1. Требуется составить 

такой план выпуска продукции, при котором прибыль от ее реализации 

окажется максимальной. 

Составим экономико-математическую модель задачи. Пусть 
(
1, )
jx
j
n

  –  

количество единиц продукции 
jP . Если продукция 
jP  не выпускается, то 
0

jx
, 

в противном случае 
0

jx
. 

Таблица 1.1 

Виды 

сырья 

Запасы 

сырья 

Количество единиц сырья 
iS , идущего на 

изготовление единицы продукции  
jP  

1P
2P
3P
... 
jP  
... 
n
P

1S  
1b
11
a  
12
a
13
a
... 
j
a1  
... 
n
a1

2
S  
2b
21
a
22
a
23
a
... 
j
a2  
... 
n
a2

... 
... 
... 
... 
... 
... 
... 
... 
... 

iS  
ib
1ia
2
ia
3
ia
... 
ij
a  
... 
in
a

... 
... 
... 
... 
... 
... 
... 
... 
... 

m
S  
m
b
1
m
a
2
m
a
3
m
a
... 
mj
a  
... 
mn
a

Прибыль 
1c  
2c
3c
... 
jc  
... 
nc  

 
Количество сырья 
iS , идущего на изготовление всех видов продукции 

nP
P ,...,
1
, вычисляется как  


n

j
j
ij x
a

1
 и не должно превышать имеющегося запаса 

сырья 
ib , следовательно,  

1
(
1,
).

n

ij
j
i
j
a x
b
i
m





 

От реализации 
jx  единиц продукции 
jP  получают прибыль 
j
j x
c
 

(аналогично для любого 
n
j
,1

), поэтому суммарная прибыль от реализации 

всей продукции  





n

j
j
j x
c
z

1
. 

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

максимизироваться, получаем следующую математическую модель. 

Найти 
1,
,
n
x
x

, удовлетворяющие следующим требованиям: 

1
(
1,
);

n

ij
j
i
j
a x
b
i
m





                                                               (1.1) 

0 (
1, );
jx
j
n


                                             (1.2)  

1
max

n

j
j
j
z
c x





.                                           (1.3)  

Система (1.1) называется системой ограничений,  условие (1.2) – 

условием неотрицательности, функция  z  в (1.3) – целевой функцией.  

 

Задача о составлении рациона питания (задача «о диете») 

К этому классу задач относятся задачи о составлении различных смесей, 

сплавов, растворов, обладающих определенными нормативными свойствами. 

Смеси составляются из имеющихся компонентов, каждый из которых содержит 

определенные доли полезных веществ. Смесь должна содержать не менее 

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

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

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

минимальной. Наиболее наглядно эта задача формулируется в виде задачи о 

составлении рациона питания. 

При откорме каждое животное должно получать не менее 
ib  

определенного количества вещества 
iS  (например, белков, жиров, углеводов, 

витаминов и микроэлементов, т. е. 
1,5
i 
). Для составления рациона 

используют, например, три вида корма Р1, Р2, Р3. Содержание количества 

единиц питательных  веществ  в  одном  килограмме  каждого  вида корма 

дается в табл. 1.2, где в последней строке приведена стоимость 1 кг корма в 

денежных единицах. 

Таблица 1.2 

 
Питательные 
вещества 

Норма 
содержания  
питательных 
веществ в 
смеси 

Количество единиц питательных веществ 
в 1 кг корма 

 

1P  

 

2P  

 

3P  

1S  
1b  
11
a
12
a
13
a

2
S  
2b  
21
a
22
a
23
a

3
S  
3b  
31
a
32
a
33
a

4
S  
4b  
41
a
42
a
43
a

5
S  
5b  
51
a
52
a
53
a

Стоимость 1 кг корма 
1c
2c
3c  

 

Требуется составить дневной рацион так, чтобы при минимальных 

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

питательных веществ. 

Составим экономико-математическую модель задачи. Пусть х1, х2, х3 – 

количество кормов соответственно Р1, Р2, Р3, тогда питательного вещества 

(
1,5)
iS i
 содержится в рационе в количестве 


3

1
j
j
ij x
a
, что по условию должно 

быть не менее 
ib . Составим следующую систему ограничений: 

3

1
(
1,5)
ij
j
i
j
a x
b
i





.  

Количество 
кормов 
есть 
величина 
неотрицательная, 
поэтому 

0 (
1,2,3).
jx
j


 

Стоимость всего рациона – целевая функция 




3

1
j
j
j x
c
z
. Так как затраты 

на корм должны быть минимальными, получим следующую математическую 

модель задачи. 

Найти такие значения неизвестных х1, х2, х3, которые удовлетворяют 

следующим условиям: