Математическое программирование

К. В. Балдин, Н. А. Брызгалов, 
А. В. Рукосуев

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

Учебник

2-е издание

Под общей редакцией доктора 
экономических наук, 
профессора К. В. Балдина

Рекомендовано уполномоченным учреждением 
Министерства образования и науки РФ —
Государственным университетом управления 
в качестве учебника для студентов высших учебных 
заведений, обучающихся по направлению подготовки 
«Экономика» и экономическим специальностям

Регистрационный номер рецензии 542 от 29.12.2008 г. 
(Федеральный институт развития образования) 

Москва, 2018

Издательско-торговая корпорация «Дашков и К°»

УДК 330.115
ББК 65.01
Б20
Авторы:
К. В. Балдин — доктор экономических наук, профессор; Н. А. Брызгалов — 
кандидат технических наук, доцент; А. В. Рукосуев — старший преподаватель.
Рецензенты:
И. В. Минаев — доктор технических наук, профессор; Н. Н. Пилипенко — 
доктор экономических наук, профессор, заслуженный деятель науки РФ

Балдин К. В.
Математическое программирование: Учебник / К. В. Балдин, Н. А. Брызгалов, А. В. Рукосуев. / Под общ. ред. д.э.н., проф. 
К. В. Балдина. — 2-е изд. — М.: Издательско-торговая корпорация «Дашков и К°», 2018. — 218 с.

ISBN 978-5-394-01457-4

В учебнике рассматриваются теоретические основы математического программирования с позиций методологии системного анализа. Представлены методы решения задач линейного, нелинейного, 
динамического программирования и некоторых специальных задач линейного программирования. Рассматриваются проблемы применения известных методов и моделей теории игр в разработке рациональных управленческих решений в неопределенных условиях. 
В приложениях представлены задачи для самостоятельного решения.
Для студентов вузов, обучающихся по направлениям подготовки «Экономика», «Менеджмент» и «Торговое дело».

Подписано в печать 20.09.2017. Формат 60×84 1/16. 
Печать офсетная. Бумага офсетная № 1. Печ. л. 13,75.  
Тираж 100 экз. 

Издательско-торговая корпорация «Дашков и К°»
129347, Москва, Ярославское шоссе, д. 142, к. 732
Тел.:  8 (495) 668-12-30, 8 (499) 183-93-23
E-mail: sales@dashkov.ru — отдел продаж;
office@dashkov.ru — офис; http://www.dashkov.ru

Б20

ISBN 978-5-394-01457-4

© К. В. Балдин, Н. А. Брызгалов, 
А. В. Рукосуев, 2008
© ООО «ИТК «Дашков и К°», 2008

СОДЕРЖАНИЕ

СПИСОК СОКРАЩЕНИЙ ........................................................................................6

ВВЕДЕНИЕ .............................................................................................................................7

1. 
МЕТОДИЧЕСКИЕ ОСНОВЫ 
МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ .................9

1.1. 
Цели, задачи и принципы исследования 
экономических операций ....................................................................9
1.2. 
Основные понятия исследования операций ....................15
1.3. 
Классификация методов оптимизации 
и их краткая характеристика ......................................................20
1.4. 
Методика проведения исследования операций ...........23
1.5. 
Ключевые понятия системного подхода .............................26
1.6. 
Принципы и аспекты системного подхода .......................37
1.7. 
Системный подход к управлению 
методами решения задач комплексного 
экономического анализа ...................................................................44

2. 
ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 
И МЕТОДЫ ИХ РЕШЕНИЯ ......................................................................54

2.1. 
Постановка задачи 
линейного программирвоания .....................................................54
2.2. 
 Графический метод решения задач 
линейного программирования .....................................................56
2.3. 
Симплекс-метод решения задач 
линейного программирования .....................................................63

2.3.1. Стандартная форма задач линейного 
программирования ................................................................63
2.3.2. Основные понятия симплекс-метода ...................65
2.3.3. Алгоритм симплекс-метода ..........................................68
2.3.4. Метод искусственных переменных .......................71
2.4. 
Двойственная задача 
линейного программирования .....................................................75
2.5. 
Анализ чувствительности задачи 
линейного программирования .....................................................81
2.6. 
Классификация методов решения задач 
целочисленного линейного программирования ...........86
2.7. 
Метод отсекающих плоскостей Гомори ..............................88
2.7.1. Метод Гомори для полностью 
целочисленных задач .........................................................88
2.7.2. Метод Гомори 
для частично-целочисленных задач .....................95
2.8. 
Метод ветвей и границ .......................................................................97

3. 
СПЕЦИАЛЬНЫЕ ЗАДАЧИ 
ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ...................................101

3.1. 
Вербальная и математическая постановка 
транспортной задачи 
линейного программирования ..................................................101
3.2. 
Решение транспортной задачи ................................................105
3.3. 
Практическое решение задачи 
оптимального планирования......................................................115
3.4. 
Многопродуктовая транспортная задача .......................122
3.5. 
Транспортная модель 
с промежуточными пунктами ...................................................126

4. 
ЗАДАЧИ НЕЛИНЕЙНОГО И ДИНАМИЧЕСКОГО 
ПРОГРАММИРОВАНИЯ .........................................................................130

4.1. 
Экономическая и геометрическая интерпретации 
задачи нелинейного программирования .........................130

4.2. 
Метод множителей Лагранжа ..................................................137
4.3. 
Задачи динамического программирования ..................142
4.3.1. Задача об оптимальном распределении 
однородного ресурса.........................................................143
4.3.2. О применимости метода 
динамического программирования .....................152
4.3.3. Алгоритм метода динамического 
программирования .............................................................153
4.3.4. Задача об оптимальной загрузке 
транспортного средства неделимыми 
предметами (задача о рюкзаке) .............................155
4.3.5. Задачи для самостоятельного решения ..........161
4.4. 
Сетевое планирование и управление .................................162
4.5. 
Классические и современные методы теории игр ..172

ЛИТЕРАТУРА ................................................................................................................199

ПРИЛОЖЕНИЯ ............................................................................................................203

СПИСОК СОКРАЩЕНИЙ

ДЗЛП — двойственная задача линейного программирования;
ДП — 
динамическое программирование;
ЗЛП — 
задача линейного программирования;
ИО — 
исследование операций;
КЭА — 
комплексно-экономический анализ;
ЛП — 
линейное программирование;
ЛПР — 
лицо принимающее решение;
МДП — метод динамического программирования;
МТС — 
материально-технические средства;
НДБР — начальное допустимое базисное решение;
НЛП — нелинейное программирование;
ОДР — 
область допустимых решений;
ОФ — 
ограничивающая функция;
ПЗЛП — прямая задача линейного программирования;
ППП — пакет прикладных программ;
ПЭВМ — персональная электронно-вычислительная машина;
СМ — 
симплекс-метод;
СПУ — 
сетевое планирование и управление;
ТЗЛП — транспортная задача линейного программирования;
ТМО — теория массового обслуживания;
ТПР — 
теория принятия решения;
ЦЛП — целочисленное линейное программирование;
ЦФ — 
целевая функция;
ЭВМ — электронно-вычислительная машина;
ЭВТ — 
электронно-вычислительная техника;
ЭИС — 
экономическая информационная система.

ВВЕДЕНИЕ

Математическое программирование — совокупность методов принятия оптимальных решений на основе нахождения оптимума функции многих переменных, находящихся 
на границах области допустимых решений. При этом область 
допустимых решений определяется соответствующими функциональными ограничениями. В математическое программирование входит линейное, дискретное, нелинейное, выпуклое, 
динамическое программирование, теория игр, теория графов и 
теория массового обслуживания.
Особое место в математическом программирование занимает линейное программирование, характеризуемое высокой 
надежностью и простотой вычислительного алгоритма, удобного для разработки машинной программы. Наиболее изученным разделом математического программирования является 
линейное программирование. Для решения задач этого класса разработан целый ряд эффективных методов, алгоритмов 
и программ. Линейное программирование представляет собой 
важнейшую часть математической дисциплины, занимающейся изучением решения экстремальных задач. В общем виде 
вербальная постановка задач линейного программирования состоит в нахождении наибольшего или наименьшего значения 
целевой функции при заданных ограничениях.
Целью выпуска данного учебного пособия является формирование у студентов навыков постановки задач оптимизации 
на вербальном и математическом уровнях, а также решение 
задач предлагаемыми методами и соответствующая интерпретация полученных результатов. В книге введена единая общепризнанная терминология и система обозначений, что позволяет студентам использовать методы оптимизации как средство, 
предназначенное для обоснования управленческих решений.

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

1. МЕТОДИЧЕСКИЕ ОСНОВЫ 
МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ

1.1. Цели, задачи и принципы исследования 
экономических операций

Исследование операций как самостоятельное научное направление возникло из потребностей наилучшей организации 
экономических операций, а также прогнозирования их исхода при 
принятии руководством различных решений. Однако с течением 
времени стало очевидно, что подобные организационные задачи 
(согласования, упорядочения, распределения и др.) возникают и 
в других, самых различных сферах человеческой деятельности 
и имеют, несмотря на их качественное различие, сходные черты. 
Во-первых, во всех этих задачах рассматривается некоторая совокупность мероприятий (система действий), направленных на 
достижение конкретной цели. Во-вторых, считаются заданными 
некоторые фиксированные условия, характеризующие обстановку выполнения этих мероприятий и изменить которые не представляется возможным (например, отпущенные средства, располагаемые ресурсы, качественные характеристики используемых 
технических средств и др.). В-третьих, в рамках этих фиксированных условий необходимо принимать решения, чтобы рассматриваемая совокупность мероприятий была в определенном смысле наиболее выгодной. Этой общности оказалось достаточно для 
построения единой системы методов, которые и стали называться 
“исследованием операций” (ИО).
Под операцией в данном случае понимается система 
действий, объединенных общим замыслом и направленных на 

достижение определенной цели. Операция — это обобщенное 
понятие, охватывающее все те виды деятельности человека, 
непременным атрибутом которых является принятие решений. 
Примеры экономических операций: анализ финансово-хозяйственной деятельности предприятия, анализ эффективности 
привлекательности инвестиционного проекта.
Принятие решения по своей сути представляет собой выбор одного из множества возможных вариантов осуществления 
операции. Способность делать правильный выбор — ценное качество, которое присуще людям в разной степени. Высокопрофессиональные менеджеры, например, отличались и отличаются от своих коллег или конкурентов прежде всего умением 
делать наилучший выбор, т. е. принимать лучшие решения. Но 
всякое решение лучше, разумнее, если оно будет подкреплено 
количественными, математическими расчетами. Для проведения таких расчетов и служат методы исследования операций. 
Таким образом, в современном понимании исследование операций — это научный метод, дающий в распоряжение руководителя количественные основания для принятия им решений, 
связанных с организацией и осуществлением операции.
Объектом исследования операций является операция, а в 
качестве предмета исследования операций выступают закономерности, связывающие организацию и условия проведения 
операции с ее конечным результатом.
Необходимо подчеркнуть, что процедура непосредственного принятия решений выходит за рамки исследования операций, и процесс исследования завершается представлением руководителю рекомендаций, полученных на основе применения 
математических методов. Поэтому цель исследования операций 
заключается в выработке научно-обоснованных рекомендаций 
для принятия решений.
Операция, как правило, всегда проводится при фиксированных условиях, т. е. управление ею осуществляется в рамках 
имеющихся различного рода ограничений: социальных, экономических, технических, финансовых, материальных, людских 
и т. д. Исходя из этого, основной задачей исследования опера