Математическое программирование. Алгоритмический подход

А.А. ЧЕРНЯК Ж.А. ЧЕРНЯК Ю.М. МЕТЕЛЬСКИЙ



МАТЕМАТИЧЕСКОЕ

ПРОГРАММИРОВАНИЕ


Алгоритмический подход

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














Минск «Вышэйшая школа» 2007

УДК 519.85(075.8)
ББК 22.18я73
     4-49

    Рецензенты: кафедра прикладной математики и экономической кибернетики Белорусского государственного экономического университета; старший научный сотрудник Института математики Национальной академии наук Беларуси доктор физико-математических наук, профессор В.И. Берник

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


            Черняк, А. А.


⁴⁻⁴⁹ Математическое программирование. Алгоритмический подход : учеб. пособие / А. А. 4ерняк, Ж. А. 4ерняк, Ю. М. Метельский. — Минск : Выш. шк., 2006. — 352 с. : ил.
          ISBN 978-985-06-1356-1.

          Рассматриваются линейное, дискретное, выпуклое, нелинейное и динамическое программирование, транспортные и потоковые задачи, оптимизационные задачи на графах и матроидах, теория полиномиальной сводимости и NP-полноты.
          Для студентов экономических и инженерно-технических специальностей вузов. Будет полезно также магистрантам, аспирантам и преподавателям вузов.
УДК 519.85(075.8)
ББК 22.18я73
Учебное издание

Черняк Аркадий Александрович Черняк Жанна Альбертовна Метельский Юрий Михайлович
МАТЕМАТИЧЕСКОЕ ПРОГРАММИРОВАНИЕ Алгоритмический подход
Учебное пособие
Редактор Е.В. Малышева. Художественный редактор В.А. Ярошевич. Технический редактор НА. Лебедевич. Корректор В.И. Аверкина. Компьютерная верстка НВ. Шабуни.

Подписано в печать 20.06.2007. Формат 84x108/32. Бумага типографская № 2. Офсетная печать. Гарнитура «Nimbus». Усл. печ. л. 18.48. Уч.-изд. л. 16,04. Тираж 2200 экз. Заказ 1573.
Республиканское унитарное предприятие «Издательство “Вышэйшая школа”». ЛИ 02330/ 0131768 от 06.03.2006. 220048, Минск, проспект Победителей, 11. www.vshph.com
Республиканское унитарное предприятие «Типография “Победа”». 222310, Молодечно, ул. Тавлая, 11.

ISBN 978-985-06-1356-1            © 4ерняк, А.А., 4ерняк, Ж.А.,
                                    Метельский Ю.М., 2007
© Издательство «Вышэйшая школа», 2007

2

            ПРЕДИСЛОВИЕ



   Существующие учебники по математическому программированию можно условно разделить на три группы. Книги первой группы, написанные для студентов инженерно-экономических специальностей, характеризуются стандартным подбором и традиционным изложением материала. Они отражают приверженность их авторов к тем канонам в преподавании, которые были заложены еще в 70—80-х годах XX в. такими известными белорусскими математиками-педагогами, как А.В. Кузнецов, В.А. Сакович и др. Вторую группу составляют книги, ориентированные на применение компьютерных пакетов. Они учитывают современный прогресс в информационных технологиях, однако по актуальности и глубине излагаемой в них теории уступают книгам первой группы. К третьей группе можно отнести книги, предназначенные для студентов математических факультетов университетов. Эти книги в силу своей специфики имеют высокий уровень абстракции и являются узкопрофильными (например, по «выпуклому программированию», «дискретной оптимизации» и т.д.).
   Остановимся на характерных особенностях книги, предлагаемой вниманию читателя. Во-первых, учитывая и уважая возможности потенциальных читателей, авторы варьируют степень подробности и глубину изучения предмета. В каждой главе материал излагается на двух уровня, которые можно условно назвать «беллетризован-ным» и «академическим». В зависимости от содержания главы либо эти два уровня перемежаются друг с другом (параллельное изложение), либо первый предваряет второй (последовательное изложение). Первый уровень готовит читателя к последующему, математически строгому, изложению и потому не отягощен терминологией, насыщен наглядными примерами и не требует для понимания значительных математических усилий. Второй уровень предполагает глубокое постижение теории и содержит доказательства утверждений, которые вынесены в отдельные главы.
   В то же время, сохраняя традиционные разделы, оговоренные рамками государственных образовательных стандартов, авторы постарались придать книге современное звучание, адаптировав ряд ключевых результатов последних десятилетий (многие из которых были отражены только в специализированных научных изданиях) для студентов инженерно-экономических специальностей вузов. Среди них: фундаментальный алгоритм полиномиального решения задач линейной оптимизации, принципиально отличающийся от симплексных процедур не только своей

3

эффективностью, но и самой природой используемого подхода; регуляризация неустойчивых задач оптимизации, позволяющая преодолевать разрыв между реальными явлениями и их математическими моделями; введение в теорию полиномиальной сводимости и NP-полноты (эти понятия стали символом трудностей, с которыми сталкиваются разработчики алгоритмов по мере увеличения размерности и усложнения структуры оптимизационных задач).
   Во-вторых, в книге содержатся строгие доказательства достаточно сложных теорем математического программирования, а в изложении ряда разделов, уже ставших традиционными, предложены новые подходы. Так, преодолено разделение общей задачи линейного программирования на вырожденный и невырожденный случаи; приведена простая реализация симплекс-метода во избежание «зацикливания», параллельно решающая проблему нахождения начального базисного плана; дана обобщенная сетевая модель, включающая в качестве частных случаев различные оптимизационные задачи, связанные с потоковыми алгоритмами; транспортные задачи и задачи динамического программирования решаются с помощью методов теории графов, обеспечивающих наглядность в обосновании сопутствующих алгоритмов; компактно изложены теория Куна — Таккера и метод возможных направлений — традиционно сложные для усвоения разделы нелинейного программирования.
   В-третьих, данная книга реализует главный принцип, отраженный в ее названии: критерием значимости любого результата является его алгоритмическая эффективность, а описание самих алгоритмов должно представлять собой оптимальную теоретическую основу для будущих программных реализаций. При этом авторы полностью отказались от многочисленных адаптаций к «ручному» счету трудоемких вычислительных процедур благодаря существованию компьютерных пакетов, успешно справляющихся с проблемами подобного рода.
   В пособии активно используются сведения из общего курса высшей математики. Во всех подобных случаях авторы делают ссылки на один из современных учебников, оставляя тем не менее за читателем право выбора подходящего учебного пособия.
   Все отзывы, замечания и предложения просьба направлять по адресу: 220048, Минск, проспект Победителей, 11, издательство «Вышэйшая школа».
Авторы

4

                МНОГОГРАННИКИ И ПОЛИЭДРЫ





   Рассмотрим две точки B=(0;1) и D=(3;0) на координатной плоскости %i Ox₂ (рис. 1.1). Любая точка N отрезка BD может быть представлена в виде N=X B+(1-X) D, где X — некоторое число между нулем и единицей. Так как X+(1-X)=1, то, обозначив через X1 и X2 коэффициенты X и 1-X в сумме N=XB+(1-X)D, получим: N =XjB+Х2D, где Xj +X2 =1, Xj >0, X2 >0. Такое представление точки N называется выпуклой линейной комбинацией точек B и D. При этом говорят, что отрезок BD порождается точками B и D.
   Пусть A=(0;0). Возьмем произвольную точку K треугольника ABD. Продолжим отрезок AK до пересечения с BD в точке M. Поскольку точка M принадлежит отрезку BD, то M=М1 B+М2D, где М-1 +М2 =1, М1 >0, М2 >0. Аналогичное представление возможно и для точки K, принадлежащей отрезку AM: K=Р1 A+02 M, где 01+Р2 =1, Р1 >0, Р2 >0. Отсюда    K=Р1 A+Р2 (М1B+М2 D )=
=Р1 ⁺⁽м1 ⁺М2 )=Р1 ⁺в2 =
   Поскольку     Р1+Р2 М1 +

+Р2 Ц-2 ⁼Р1 ⁺в2(М1+ М-2)⁼Р1 ⁺в2 ⁼¹, Рис. 1.1. МногогранникABCD

5

то, обозначив коэффициенты 0р [ф Щ, 02 М-2 соответственно через Х1, Х₂, X3, получим: K=Х1 A+^ B+X3 D, где Х1+^2 +X,₃ =1, ^1 -0, ^2-0, Х,₃-0. Такое представление точки K называется выпуклой линейной комбинацией точек A, B, D. При этом говорят, что треугольник ABD порождается точками A, B, D   Если теперь рассмотреть четырехугольник ABCD, где C=(1;2), то любая его точка L будет выпуклой линейной комбинацией четырех точек: A, B, C, D. Действительно, ABCD можно разбить на два треугольника, и точка L окажется в одном из них, например в треугольнике BCD. Но тогда, как показано выше, L=X1 B+Х₂ C+Х₃ D, где X1+X₂ +X₃ =1, X1 -0, Х2-0, Х₃-0. Отсюда L=^iB+^2C+X3D+X4A, где X4=0, X1 +X2 +X3 +X4 =1-Таким образом, четырехугольник ABCD порождается точками A, B, C, D.
   Итак, четырехугольник ABCD состоит из всех выпуклых линейных комбинаций точек A, B, C, D. Подобные структуры называются многогранниками- Очевидно, что многогранниками являются также рассмотренные ранее отрезок BD и треугольник ABD.
   Рассмотрим теперь n-мерные точки в n-мерном точечном пространстве Afⁿ, определенном в работе [11, гл. 1].
   Пусть дана конечная система точек T={Др...,Aₖ} пространства Afⁿ. Говорят, что точка Ae Afⁿ есть выпуклая линейная комбинация точек из T, если A=X1 A1 +...+XₖAₖ, где X1+...+X ₖ =1, X i-0, i=1,., k.
   Многогранником, порожденным конечной системой точек T из Afⁿ, называется множество всех выпуклых линейных комбинаций точек из Т. Очевидно, что множество, состоящее из одной точки A, является многогранником: A=1- A.
   Вернемся теперь к четырехугольнику ABCD (рис. 1.1). Он является выпуклым многоугольником: какие бы две его точки ни взять, соединяющий их отрезок будет целиком содержаться

6

в ABCD. В то же время четырехугольник на рис. 1.2 выпуклым не является.
   Точки A, B, C, D обладают уникальным для выпуклого четырехугольника ABCD свойством: при удалении любой из них оставшаяся часть сохраняет выпуклость. Именно в силу это

Рис. 1.2. Невыпуклый четырехугольник

го свойства точки A, B, C, D называются вершинами множе

ства ABCD. Никакие другие точки четырехугольника ABCD подобным свойством не обладают и поэтому не могут назы

ваться его вершинами.

   В общем случае n-мерного пространства Afⁿ многогранник, порожденный системой из двух точек, называется отрезком . Множество точек, содержащее вместе с любыми двумя своими точками и отрезок, их соединяющий, называется выпуклым . Вершиной выпуклого множества F называется точка, удаление которой из F приводит к пустому или выпуклому множеству. Таким образом, одноточечное множество F={ A} всегда выпукло и A — вершина F.
   Следующая теорема утверждает, что вершины многогранника могут быть только среди точек, его порождающих.
   Теорема 1.1. Пусть многогранник M порожден системой точек T={ Ai,.., Aₖ }. Тогда любая его вершина принадлежит T. (Доказательство дано в задаче T1.1.)
   Теорема 1.2. Любой многогранник M порождается множеством своих вершин. (Доказательство дано в задаче T1.4.)
   Таким образом, наиболее «экономной» системой точек, порождающей многогранник, является множество его вершин. Из теорем 1.1, 1.2 непосредственно вытекает следующее утверждение.
   Следствие 1.1. Любой многогранник имеет по меньшей мере одну вершину, и число его вершин всегда конечно.
   Существуют выпуклые множества с бесконечным числом вершин. Так, любая точка границы круга является его вершиной. Кроме того, каждая точка круга есть выпуклая линейная комбинация некоторых его вершин (например, концов диаметра, проведенного через эту точку), и каждая выпуклая ком
7

Рис. 1.3. Многогранная

         бинация его вершин A^ ,..., An содержится в круге (многогранник A1 ... Aₙ является вписанным n-угольником и поэтому целиком содержится в круге). Другими словами, круг также совпадает с множеством всех выпуклых линейных комбинаций своих вершин.
//>////„ Многогранник является A Di ** ограниченным выпуклым область множеством с конечным числом вершин. Однако сущест

вуют неограниченные выпуклые множества с конечным числом вершин, включающие и многогранники, порожденные их вершинами. Рассмотрим изображенную на рис. 1.3 область, ограниченную лучами Dxi, Ax 2 координатных осей Oxi, Ox₂

и ломаной ABCD. Ее вершинами являются точки A=(0;25), B=(20/7;75/7), C=(3;8), D=(20;0), и она содержит многогранник ABCD.

Зафиксируем теперь два вектора:      Pi = DDi =(i;0),

P2 = AAi =(0;1). Возьмем произвольную точку L, принадлежащую области x2ABCDxi. Очевидно, что L=M+ML, где M — некоторая точка многогранника ABCD. В свою очередь, вектор

ML разложим (по правилу параллелограмма) в сумму векторов MLi + ML2=«iPi+«2P2, где «^«2 — неотрицательные числа. Эта сумма называется неотрицательной линейной комбинацией векторов pi и P2. Таким образом, область x 2 ABCDxi — это выпуклое множество с конечным числом вершин, состоящее из всех сумм вида M+p, где M — выпуклая линейная комбинация вершин; p — неотрицательная линейная комбинация фик

8

сированной системы векторов {p^,Р2}. Подобные структуры называются многогранными областями.
   Рассмотрим общий случай n -мерных пространств. Пусть дана конечная система векторов V={ p\,..., p>ᵣ} n -мерного векторного пространства Rⁿ [11, гл. 31]. Говорят, что вектор pieRⁿ есть неотрицательная линейная комбинация векторов из V, если p=«ipi +...+аᵣpᵣ, аi>0, i=1,.,r. Многогранной областью, порожденной конечной системой точек T из Afⁿ и конечной системой векторов V из Rⁿ, называется множество всех точек, которые представимы в виде M+p, где M — выпуклая линейная комбинация точек из T; p — неотрицательная линейная комбинация векторов из V. Из этих определений ясно, что любой многогранник — это многогранная область, порожденная конечной системой точек T и нулевым вектором 0.
   Утверждение 1.1. Ограниченные многогранные области, и только они, являются многогранниками. (Доказательство дано в задаче T1.5.)
   Утверждение 1.2. Многогранная область является выпуклым множеством. (Доказательство дано в задаче T1.6.)
   Рассмотрим теперь четырехугольник, изображенный на рис. 1.1, с иной точки зрения. Вспомним, что любая прямая aX1 + bx2 = c делит координатную плоскость x Ox-2 на две полуплоскости, множества точек которых задаются неравенствами aX1 + bx2 <c и aX1+bx2 >c соответственно. Отрезки AB, BC, CD, AD принадлежат прямым x1 =0, x-2 -x1 =1, x1 + x-2=3, x2=0 соответственно. Поэтому неравенства x1 >0, x2 - x1 <1, x1 + x 2 <3, x2 >0 задают полуплоскости, отмеченные на рис. 1.4 зубцами. Следовательно, пересечение этих полуплоскостей (а им как раз и является четырехугольник ABCD) совпадает с множеством всех решений системы неравенств

9

X 2 - xi <1,
<x1 + x2 <3, Xi >0, X2 >0.

(1.1)

Рис. 1.4. Множество решений системы (1.1)

   Аналогична структура и многогранной области, изображенной на рис. 1.3: она совпадает с множеством всех решений системы неравенств

      5 X1 + x 2 >25,
      19 x₁ + x ₂ >65,
^   ¹  ²            (1.2)
      8 x1 +17 x2 >160,
      x₁ >0, x ₂ >0,

поскольку лучи Ax2, Dx1 и отрезки AB, BC, CD принадлежат прямым x1 =0, x2 =0, 5 x1 + x 2=25, 19x1 + x2 =65, 8x1 +17x2 =160 соответственно. Оказывается, что совпадение с множествами решений систем линейных неравенств является характеристическим свойством многогранных областей (см. теорему 1.3).
   Известно (см. [11, гл. 39]), что линейное уравнение ^1 x1 +...+aₙxₙ=b, в котором не все коэффициенты ар...,aₙ равны нулю, определяет гиперплоскость пространства Afⁿ. Множество всех точек (xp...,xₙ) из Afⁿ, удовлетворяющих неравенству ^1 x1 +...+aₙxₙ>b, называется полупространством в Afⁿ. Пересечение конечного числа полупространств в Afⁿ называется полиэдром.
   Следующая теорема, которая приводится без доказательства, является фундаментальным утверждением теории полиэдров.
   Теорема 1.3. Многогранная область — это полиэдр, и каждый полиэдр — это многогранная область. Многогранник — это ограниченный полиэдр, и каждый ограниченный полиэдр — многогранник.
   Теорема 1.3 раскрывает геометрию множества решений системы линейных неравенств. Следующая теорема при более общих предположениях означает, что любую точку вне задан

10