Алгоритмы - построение и анализ (1021735), страница 179
Текст из файла (страница 179)
Приложения линейного программирования Линейное программирование имеет широкий спектр приложений. В любом учебнике по исследованию операций содержится множество примеров задач линейного программирования; линейное программирование — стандартный метод, который преподается студентам большинства школ бизнеса. Разработка сценария предвыборной борьбы — лишь один типичный пример. Приведем еще два примера, где с успехом используется линейное программирование. ° Авиакомпания составляет график работы экипажей. Федеральное авиационное агентство установило ряд ограничений, таких как ограничение времени непрерывной работы для каждого члена экипажа и требование, чтобы каждый конкретный экипаж работал только на самолетах одной модели на протяжении одного месяца.
Авиакомпания хочет назначить экипажи на все рейсы, задействовав как можно меньше сотрудников (членов экипажей). ° Нефтяная компания выбирает место бурения скважины. С размещением буровой в каждом конкретном месте связаны определенные затраты и ожидаемая прибыль в виде некоторого количества баррелей добытой нефти, рассчитанная на основе проведенных геологических исследований.
Средства, выделяемые на бурение новых скважин, ограничены, и компания хочет максимизировать ожидаемое количество добываемой нефти исходя нз заданного бюджета. Задачи линейного программирования также полезны при моделировании и решении задач теории графов и комбинаторных задач, таких как задачи, приведенные в данной книге. Мы уже встречались с частным случаем линейного программирования, который использовался для решения систем разностных ограничений в разделе 24.4.
В разделе 29.2 мы покажем, как сформулировать в виде задач линейного программирования некоторые задачи теории графов н задачи сетевых потоков. В разделе 35.4 линейное программирование будет использоваться в качестве инструмента поиска приблизительного решения еще одной задачи теории графов. Глава 29. Линейное программирование 877 Алгоритмы решения задач линейного программирования В данной главе изучается симплекс-алгоритм. При правильном применении данный алгоритм на практике обычно позволяет быстро решать задачи линейного программирования общего вида.
Однако при некоторых специально подобранных начальных значениях время выполнения симплекс-алгоритма может оказаться экспоненциальным. Первым алгоритмом с полиномиальным временем выполнения для решения задач линейного программирования был эллиесоидныа алгоритм, который на практике работает весьма медленно.
Второй класс полиномнальных по времени алгоритмов содержит так называемые методы внутренней точки (1шепог-ро1ш шебзосЬ). В отличие от симплекс-алгоритма, который движется по границе допустимой области и на каждой итерации рассматривает допустимое решение, являющееся вершиной симплекса, эти алгоритмы осуществляют движение по внутренней части допустимой области. Промежуточные решения являются допустимыми, но не обязательно находятся в вершинах симплекса, однако конечное решение является вершиной. Первый подобный алгоритм был разработан Кармаркаром (Каппагйаг). Для задач большой размерности производительность алгоритмов внутренней точки может быть сравнима с производительностью симплекс-алгоритма, а иногда и превышает ее. Если ввести в задачу линейного программирования дополнительное требование, чтобы все переменные принимали целые значения, получится задача целочисленного линейного лрограммирования.
В упражнении 34.5-3 предлагается показать, что в этом случае даже задача поиска допустимого решения является 1чР-полной; поскольку ни для одной 1чР-полной задачи не известны полнномиальные алгоритмы решения, для задач целочисленного линейного программирования полиномиапьные по времени алгоритмы также не известны. В отличие от них, задача линейного программирования общего вида может быль решена за полиномиальное время. В данной главе для указания конкретного набора значений переменных в задаче линейного программирования с переменными х = (хы хэ,..., х„) мы будем использовать обозначение х = (хы хз,..., х„). 29.1 Стандартная и каноническая формы задач линейного программирования В данном разделе описываются стандартная и каноническая формы задач линейного программирования, которые будут полезны при формулировании задач и работе с ними. В стандартной форме все ограничения являются неравенствами, а в канонической форме ограничения являются равенствами. Часть Ч11.
Избранные темы 878 Стандартная форма В стандартной форме заданы и действительных чисел сы сз,..., с„; т действительных чисел Ьы Ьз,..., Ь,„; и тп действительных чисел аиь где ( = 1, 2,..., т и 7' = 1, 2,..., и. Требуется найти и действительных чисел хы хз,..., х„, которые максимизируют ь с~ хд (29.16) при условиях а;х <Ь;, где(=1,2,...,т, Е 8=1 х.
> О, где 7' = 1,2,..., и. (29.17) (29.18) Обобщая введенную для двумерной задачи линейного программирования терминологию, будем называть выражение (29.16) целевой вЬункцией, а п+ т неравенств (29.17) и (29.18) — ограничениями; и ограничений (29.18) называются ограничениями неотрицательности. Произвольная задача линейного программирования не обязательно содержит ограничения неотрицательности, но в стандартной форме они необходимы. Иногда удобно записывать задачу линейного программирования в более компактной форме.
Определим т х и-матрицу А = = (ао), т-мерный вектор Ь = (Ь;), и-мерный вектор с = (с;) и и-мерный вектор х = (х ); тогда задачу линейного программирования (29.16)-(29.18) можно записать в следующем виде: Максимизировать с х при условиях Ах< Ь, (29.19) (29.20) х > О. (29.2 1) В выражении (29.19) сгх — это скалярное произведение двух векторов. В выражении (19.20) Ах — произведение матрицы и вектора, а х > 0 в (29.21) означает, что все компоненты вектора х должны быть неотрицательными.
Таким образом, задачу линейного программирования в стандартной форме можно описать с помощью тройки (А, Ь, с), и мы примем соглашение, что А, Ь, и с всегда имеют указанную выше размерность. Теперь введем терминологию для описания различных ситуаций, возникающих в линейном программировании. Некоторые термины уже использовались в двумерной задаче. Набор значений переменных х, которые удовлетворяют всем ограничениям, называется донусшимым решением, в то время как набор значений переменных х, не удовлетворяющий хотя бы одному ограничению, называется недонустимым решением.
Решению х соответствует целевое значение сгх. Глава 29. Линейное программирование 879 Допустимое решение х, целевое значение которого является максимальным среди всех допустимых решений, является олвшмальиым рензением, а его целевое значение с "х называется оптимальным целевым значением. Если задача линейного программирования не имеет допустимых решений, она называется иеразреюиимой (шгеаз(Ые), в противном случае она является разреюиимой (Геаз(Ые).
Если задача линейного программирования имеет допустимые решения, но не имеет юнечного оптимального целевого значения, она называется неограниченной (ипЬошЫед). В упражнении 29.1-9 предлагается показать, что задача линейного программирования может иметь конечное оптимальное целевое значение даже в том случае, когда ее допустимая область неограниченна. Преобразование задач линейного программирования в стандартную форму Любую задачу линейного программирования, в которой требуется минимизировать или максимизировать некую линейную функцию при наличии линейных ограничений, можно преобразовать в стандартную форму.
Исходная задача может находиться не в стандартной форме по четырем причинам. 1. Целевая функция минимизируется, а не максимизнруется. 2. На неюторые переменные не наложены условия неотрицательности. 3. Некоторые ограничения имеют форму равенств, т.е.
имеют знак равенства вместо знака "меньше или равно". 4. Некоторые ограничения-неравенства вместо знака "меньше или равно" имеют знак "больше или равно". Преобразовывая задачу линейного программирования Б в другую задачу линейного программирования К мы бы хотели, чтобы оптимальное решение задачи Б' позволяло найти оптимальное решение задачи Б.
Будем говорить, что две задачи максимизации Б и з.' эквивалентны, если для каждого допустимого решения х задачи Ь с целевым значением з существует соответствующее допустимое решение х' задачи з" с целевым значением з, а для каждого допустимого решения х' задачи з.' с целевым значением з существует соответствующее допустимое решение й задачи Б с целевым значением з.
(Это определение не подразумевает взаимно однозначного соответствия между допустимыми решениями.) Задачи минимизации Б и задача максимизации з.' эквивалентны, если для каждого допустимого решения х задачи з. с целевым значением з существует соответствующее допустимое решение х' задачи з ' с целевым значением — з, а для каждого допустимого решения х' задачи Б' с целевым значением г существует соответствующее допустимое решение й задачи з' с целевым значением — з. Часть Ч11. Избранные темы 880 Теперь покажем, как поочередно избавиться от перечисленных выше проблем.
После устранения каждого несоответствия стандартной форме докажем, что новая задача линейного программирования эквивалентна старой. Чтобы превратить задачу минимизации Ь в эквивалентную ей задачу максимизации Ь', достаточно просто изменить знаки коэффициентов целевой функции на противоположные. Поскольку Ь и Ь' имеют одинаковые множества допустимых решений и для любого допустимого решения целевое значение Ь противоположно целевому значению Г, эти две задачи линейного программирования эквивалентны. Например, пусть исходная задача имеет вид: — 2хг + Зхз Минимизировать при условиях х1+ ха=7 х1 — 2хз ( 4 х1 >О Если мы поменяем знаки коэффициентов целевой функции, то получим следую- щую задачу: Максимизировать 2х1 — Зхз при условиях х1+ хз= 7 х1 — 2хз < 4 х1 >О Теперь покажем, как преобразовать задачу линейного программирования, в которой на некоторые переменные не наложены ограничения неотрицательности, в задачу, где все переменные подчиняются этому условию.
Предположим, что для некоторой переменной х ограничение неотрицагельности отсутствует. Заменим все вхождения переменной х выражением х' — х" и добавим ограничения неотрицательности х' > О и х" > О. Так, если целевая функция содержит слагаемое с х, то оно заменяется на с х' — с х", а если ограничение г содержит слагаемое а; х, оно заменяется на а, х' — сч х'.. Любое допустимое решение х новой задачи линейного программирования соответствует допустимому решению исходной задачи с х = х' — х" и тем же самым целевым значением, следовательно, эти две задачи эквивалентны. Применив эту схему преобразования ко всем переменным, для которых нет ограничений неотрицательности, получим эквивалентную задачу линейного программирования, в которой на все переменные наложены ограничения неотрицательности. Продолжая рассмотрение нашего примера, проверяем, для всех ли переменных есть соответствуюшие ограничения неотрицательности.
Для переменной х1 такое Глава 29. Линейное программирование 881 ограничение есть, а для переменной хз — нет. Заменив переменную хз двумя переменными х~з и х~з и выполнив соответствующие преобразования, получим следующую задачу: Максимизировать 2хг — Зх~з + Зхз при условиях / я Хз Х2=7 2хз+ 2хз < 4 хмхз,хз ~ )О (29.22) хг+ х1— а;х >Ь; Е эквивалентно ограничению — абх.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
