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

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

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

Учебник

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. Цели, задачи и принципы исследования 
экономических операций

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

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

ций можно считать выявление и количественное обоснование 
наилучших вариантов проведения операции в условиях существования различных ограничений.
Методологическую основу исследования операций составляет системный анализ как совокупность методологических средств, используемых для подготовки и обоснования 
решений по сложным проблемам различного, в том числе и военного, характера. Системное представление любого объекта, 
в том числе и операции, требует рассмотрения этого объекта 
в трех аспектах: 
 − как нечто целое (система);
 − как часть наиболее общей системы (надсистемы или более масштабной операции);
 − как совокупность более мелких частей (элементов, подсистем, подопераций). Здесь уместно привести слова известного историка Л. Н. Гумилева, в которых наиболее четко изложена 
суть системного анализа: “Изучение любой системы целесообразно лишь в целом. Даже если нас интересует только какаянибудь деталь, то все равно надо окинуть взором всю систему, 
найти место этой детали, установить ее соподчиненность в системной иерархии, взаимосвязи, а уж потом говорить о той части, которая заставила поставить проблему”.
Практическая реализация методологии системного анализа при проведении исследования конкретной операции заключается в том, чтобы придерживаться определенных принципов: цели, внешнего дополнения, декомпозиции, целостности. 
Принцип — это всякое основание, из которого надо исходить 
и которым необходимо руководствоваться в деятельности для 
достижения успеха.
Принцип цели является важнейшим принципом системного анализа, на основании которого происходит объединение 
экономических объектов и разрозненных действий людей по их 
использованию в единую целенаправленную деятельность, т. е. 
экономическую в операцию. Исходя из этого принципа, необходимо в первую очередь определить цели предстоящей операции. До тех пор, пока цель не определена, нет смысла говорить 

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

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