Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 178
Текст из файла (страница 178)
° Х>>) = 6 называется линейньои равенством, а выражения ~(хыхз,...,х„) < Ь ~(хыхз,...,х„) > 6 линейньини неравенствами. Термин линейные ограничения применяется как к линейным равенствам, так и к линейным неравенствам. В линейном программировании не допускается использование строгих неравенств. Формально задача линейного программирования — это задача минимизации или максимизации линейной функции при соблюдении конечного множества линейных ограничений. Если выполняется минимизация, то такая задача называется задачей минимизааии, а если производится максимизация, то такая задача называется задачей максимизаиии.
Вся оставшаяся часть данной главы будет посвящена формулированию и решению задач линейного программирования. Для решения задач линейного программирования существует несколько алгоритмов с полиномиальным временем выполнения, однако изучать их в данной главе мы не будем. Вместо этого мы рассмотрим самый старый алгоритм линейного программирования — симплекс- алгоритм. В худшем случае симплекс-алгоритм не выполняется за полиномиальное время, однако обычно он достаточно эффективен и широко используется на практике.
Краткий обзор задач линейного программирования Чтобы описывать свойства задач линейного программирования и алгоритмы их решения, удобно договориться, в каких формах их записывать. В данной главе мы будем использовать две формы: стандартную и каноническую (з1аск). Глава 29. Линейное программирование 873 Их строгое определение будет дано в разделе 29.1. Неформально, стандартная форма задачи линейного программирования — это задача максимизации линейной функции при соблюдении линейных неравенств, а каноническая форма — это задача максимизации линейной функции при соблюдении линейных равелспзв. О".ычнс мы будем использовать стандартную форму задач линейного программирования, однако при описании принципа работы симплекс-алгоритма удобней использовать каноническую форму.
На данном этапе ограничимся рассмотрением задачи максимизации линейной функции тз переменных при условии выполнения т линейных неравенств. Рассмотрим следующую задачу линейного программирования с двумя переменными: Максимизировать щт при условиях 4хт (29.11) ха< 8 + хз ( 10 — 2хз ) — 2 хыкз ~ )0 (29. 12) (29.13) (29.
14) (29.15) 2хд бщг Любой набор значений переменных хт и хз, удовлетворяющий всем ограничениям (29.! 2)-(29.15), называется долусшимым решением (Геаз)Ые зо!пбоп) данной задачи линейного программирования. Если изобразить эти ограничения в декартовой системе координат (щы хз), как показано на рис. 29.1а, то множество допустимых решений (заштрихованная область на рисунке) образует выпуклую область1 в двумерном пространстве. Эта выпуклая область называется допустимой обласшью ((еаз1Ые ге81оп). Функция, которую мы хотим максимизировать, называется целевой функцией (оЬ)есйче бшсйоп). Теоретически, можно было бы оценить значение целевой функции щг + хз в каждой точке допустимой области (значение целевой функции в определенной точке называется целевым значением (оЬ)есйче ча1пе)).
Затем можно найти точку, в которой целевое значение максимально; она и будет оптимальным решением. В данном примере (как и в большинстве задач линейного программирования) допустимая область содержит бесконечное множество точек, поэтому хотелось бы найти способ, который позволит находить точку с максимальным целевым значением, не прибегая к вычислению значений целевой функции в каждой точке допустимой области. В двумерном случае оптимальное решение можно найти с помощью графической процедуры. Множество точек, для которых хг + хз = д, при любом л 'Интуитивно выпуклая область определяется как область, удовлетворяющая тому требованию, чтобы длл любых двух точек, принадлежащих области, все точки соединяющего их отрезка также принадлежали атой области.
Часть Ч11. Избранные темы 874 Рис. 29.1. а) Задача линейного программирования (29.12К29.15); б) Пунктирные линии показывают точки, в которых целевое значение равно О, 4 и 8, соответственно представляет собой прямую с коэффициентом наклона — 1. Если мы построим график функции хг + хз = О, получится прямая с коэффициентом наклона— -1, проходящая через начало координат, как показано на рис.
29.1б. Пересечение данной прямой и допустимой области — это множество допустимых решений, целевое значение в которых равно О. В данном случае пересечением прямой и допустимой области является точка (О, О). В общем случае для любого я пересечением прямой хз + хз = я с допустимой областью является множество допустимых решений, в которых целевое значение равно ж На рис.
29.1б показаны прямые хг+хз = О, хг+хз = 4 и хз+хз = 8. Поскольку допустимая область на рис. 29.1 ограничена, должно существовать некое максимальное значение г, для которого пересечение прямой хг + хз = х и допустимой области является непустым множеством. Любая точка этого пересечения является оптимальным решением задачи линейного программирования; в данном случае такой точкой является хз = 2, хз = б с целевым значением 8. То, что оптимальное решение задачи линейного программирования оказалось в некоторой вершине допустимой области, не случайно.
Максимальное значение з, при котором прямая хз + хз = = г пересекает допустимую область, должно находиться на границе допустимой области, поэтому пересечение данной прямой и границы допустимой области может быть либо вершиной, либо отрезком. Если пересечение является вершиной, то существует единственное оптимальное решение, находящееся в данной вершине.
Если же пересечение является отрезком, то все точки этого отрезка имеют одинаковое целевое значение и являются оптимальными решениями; в частности, Глава 29. Линейное программирование 875 оптимальными решениями являются оба конца отрезка. Каждый конец отрезка— это вершина, поэтому в данном случае также существует оптимальное решение в вершине допустимой области. Несмотря на то, что для задач линейного программирования, где число переменных больше двух, простое графическое решение построить невозможно, наши интуитивные соображения остаются в силе. В случае трех переменных каждое ограничение описывается полупространством в трехмерном пространстве.
Пересечение этих полупространств образует допустимую область. Множество точек, в которых целевая функция имеет значение з„представляет собой некую плоскость. Если все коэффициенты целевой функции неотрицательны и начало координат является допустимым решением рассматриваемой задачи линейного программирования, то при движении этой плоскости по направлению от начала координат получаются точки с возрастающими значениями целевой функции. (Если начало координат не является допустимым решением или некоторые коэффициенты целевой функции отрицательны, интуитивная картина будет немного сложнее.) Как и в двумерном случае, поскольку допустимая область выпукла, множество точек, в которых достигается оптимальное целевое значение, должно содержать вершину допустимой области.
Аналогично, в случае п переменных каждое ограничение определяет полупространство в и-мерном пространстве. Допустимая область, образуемая пересечением этих полупространств, называется симклексаи (з1шр!ех). Целевая функция в данном случае представляет собой гиперплоскость, и благодаря выпуклости допустимой области оптимальное решение находится в некой вершине симплекса. Симплекс-алгоритм получает на входе задачу линейного программирования и возвращает оптимальное решение. Он начинает работу в некоторой вершине симплекса и выполняет последовательность итераций. В каждой итерации осуществляется переход вдоль ребра симплекса из текущей вершины в соседнюю, целевое значение в которой не меньше (как правило, больше), чем в текущей вершине.
Симплекс-алгоритм завершается при достижении локального максимума, т.е. вершины, все соседние вершины которой имеют меньшее целевое значение. Поскольку допустимая область является выпуклой, а целевая функция линейна, локальный оптимум в действительности является глобальным. В разделе 29.4 мы воспользуемся понятием двойственности, чтобы показать, что решение, полученное с помощью симплекс-алгоритма, действительно оптимально.
Хотя геометрическое представление позволяет наглядно проиллюстрировать операции симплекс-алгоритма, мы не будем непосредственно обращаться к нему при подробном рассмотрении симплекс-метода в разделе 29.3. Вместо этого мы воспользуемся алгебраическим представлением. Сначала запишем задачу линейного программирования в канонической форме в виде набора линейных равенств. Эти линейные равенства выражают одни переменные, называемые базисныии, через другие переменные, называемые небазисньиии.
Переход от одной вершины Часть ЧП. Избранные темы 876 к другой осуществляется путем замены одной из базисных переменных на небазисную. Данная операция называется замещеиием и алгебраически заключается в переписывании задачи линейного программирования в эквивалентной канонической форме. Приведенный выше пример с двумя переменными был исключительно простым.
В данной главе нам предстоит рассмотреть и более сложные случаи: задачи линейного программирования, не имеющие решений; задачи, не имеющие конечного оптимального решения, и задачи, для которых начало координат не является допустимым решением. Приложения линейного программирования Линейное программирование имеет широкий спектр приложений. В любом учебнике по исследованию операций содержится множество примеров задач линейного программирования; линейное программирование — стандартный метод, который преподается студентам большинства школ бизнеса. Разработка сценария предвыборной борьбы — лишь один типичный пример. Приведем еще два примера, где с успехом используется линейное программирование.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
