Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 195

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 195)

На данном этапе ограничимся рассмотрением задачи максимизации линейной функции от и переменных прн условии выполнения т линейных неравенств. Начнем с рассмотрения следующей задачи линейного программирования с двумя переменными: Глянь 29. Пикейное лрограмнираелкие ,' т ) — — — — к, лздо 'ь'ь еь (б) (а) Рэвс. 29.2. (в) Задача линейного программирования (29.12)-(29.15). Кюкдое отрлннченне представлено линией н нвпрлвленнем. Пересечение ограничений, представляющее область допустимым решений, заштриховано. (б) Пунктнрнымн линиями показаны тачки, для которых целевое значение рвано соответственно О, 4 н 8.

Оптимальным решеннем данной задачи линейного протрвммнровяння является хт = 2 н хэ = 6 с целевым энвченнем 8. ной задачи линейного программирования. Если изобразить зти ограничения в декартовой системе координат (хыхз), как показано на рис.29.2,(а), то множество допустимых решений (заштрихованная область на рисунке) образует выпуклую область' в двумерном пространстве. Эта выпуклая область называется облпсдевю доиустнмык ревненмй, или допустимой областью (Геааэййе гебэоп). Функция, которую мы хотим максимизировать, называется целевой функцией (оЬ)есбте бэпсиоп). Теоретически можно было бы оценить значение целевой функции х1+ хз в каждой точке допустимой области (значение целевой функции в определенной точке называется нелепым значением (оЬ)есйте та!це)). Затем можно найти точку, в которой целевое значение максимально; она и будет оптимальным решением.

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

В двумерном случае оптимальное решение можно найти с помощью графической процедуры. Множеспю точек, для которых хз + хз = д, при любом д представляет собой прямую с коэффициентом наклона — 1. Если мы построим график функции х1 + хз = О, получится прямая с козффициентом наклона — 1, проходящая через начало координат, как показано на рис. 29.2,(б). Пересечение ~Инчултлвно выпуклая область опрелеляетсл клк область, удовлетворяющая таму трсбавлнкю, чта длл любых двух тачек, арннэллелнллы абллстл, все тачкл сасдлнлювюта нх атзюэкл также должны лрянадлюяльь этой абллстя.

Часть И!. Избранные темы данной прямой и допустимой области представляет собой множество допустимых решений, целевое значение в которых равно О. В данном случае пересечением прямой и допустимой областей является точка (О, 0). В общем случае для любого г пересечением прямой х1 + хз = г с допустимой областью является множество допустимых решений, в которых целевое значение равно ж На рис. 29.2,(б) показаны прямые х1 + хз = О, х1 + хз = 4 и хз + хз = 8.

Поскольку допустимая область на рис. 29.2 ограничена, должно существовать некоторое максимальное значение з, для которого пересечение прямой х1 + хз = з и допустимой области является непустым множеством. Любая точка этого пересечения является оптимальным решением задачи линейного программирования; в данном случае такой точкой является х1 = 2, хз = 6 с целевым значением 8. То, что оптимальное решение задачи линейного программирования оказалось в некоторой вершине допустимой области, не случайно.

Максимальное значение г, при котором прямая х1 + хз = г пересекает допустимую область, должно находиться на границе допустимой области, поэтому пересечение данной прямой и границы допустимой области может быть либо вершиной, либо отрезком. Если пересечение является вершиной, то существует единственное оптимальное решение, находящееся в данной вершине. Если же пересечение является отрезком, то все точки этого отрезка имеют одинаковое целевое значение и являются оптимальными решениями; в частности, оптимальными решениями являются оба конца отрезка. Каждый конец отрезка является вершиной, поэтому в данном случае также существует оптимальное решение в вершине допустимой области.

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

Аналогично в случае п переменных каждое ограничение определяет полупространство в п-мерном пространстве. Допустимая область, образуемая пересечением этих иолупространств, называется симилексом (з1шр)ех). Целевая функция в этом случае представляет собой гиперплоскость, и благодаря выпуклости допустимой области оптимальное решение находится в некоторой вершине симплекса. Симплекс-алгоритм получает на вход задачу линейного программирования и возвращает оптимальное решение. Он начинает работу в некоторой вершине симплекса н выполняет последовательность итераций.

В каждой итерации осу- Глава 29. Линейное программирование ществляется переход вдоль ребра симплекса нз текущей вершины в соседнюю, целевое значение в которой не меньше (а обычно больше), чем в текущей вершине. Симплекс-алгоритм завершается при достижении локального максимума, т.е. вершины, все соседние вершины которой имеют меньшее целевое значение. Поскольку допустимая область является выпуклой, а целевая функция линейна, локальный оптимум в действительности является глобальным. В разделе 29г4 мы воспользуемся понятием двойственности, чтобы показать, что решение, полученное с помощью симплекс-алгоритма, действительно оптимально. Хотя геометрическое представление позволяет наглядно проиллюстрировать операции симплекс-алгоритма, мы не будем непосредственно обращаться к нему при подробном рассмотрении симплекс-метода в разделе 29.3.

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

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

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

Федеральное авиационное агентство установило ряд ограничений, таких как ограничение времени непрерывной работы для каждого члена экипажа и требование, чтобы каждый конкретный экипаж работал только на самолетах одной модели на протяжении одного месяца. Авиакомпания планирует назначить экипажи на все рейсы, задействовав как можно меньше сотрудников (членов экипажей). Нефтяная компания выбирает место бурения скважины. С размещением буровой в каждом конкретном месте связаны определенные затраты и ожидаемая прибыль в виде некоторого количества баррелей добытой нефти, рассчитанная на основе проведенных геологических исследований.

Характеристики

Список файлов книги