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

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

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

Средства, выделяемые на бурение новых скважин, ограничены, и компания хочет максимизировать ожидаемое количество добываемой нефти исходя из заданного бюджета. 890 Часть гтэ'. Иэбранные тены Задачи линейного программирования полезны также при моделировании и решении задач теории графов и комбинаторных задач, таких как задачи„приведенные в данной книге. Мы уже встречались с частным случаем линейного программирования, который использовался для решения систем разностных ограничений в разделе 24.4.

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

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

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

О том, где найти дополнительную информацию по указанным алгоритмам, говорится в заключительных замечаниях к данной главе. Если ввести в задачу линейного программирования дополнительное требование, чтобы все переменные принимали целые значения, получится задача цело. численного линейного программирования. В упр. 34.5.3 предлагается показать, что в этом случае даже задача поиска допустимого решения является ХР-полной; поскольку ни для одной ИР-полной задачи полиномиальные алгоритмы решения неизвестны, для задач целочисленного линейного программирования полиномиальные по времени алгоритмы также неизвестны.

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

Глава г9. линейное нраграммиравание а91 29.1. Стандартная и каноническая формы задачи линейного программирования В данном разделе описываются стандартная и каноническая формы задач линейного программирования, которые будут полезны при формулировании задач и работе с ними. В стандартной форме все ограничения являются неравенствами, а в канонической форме все ограничения являются равенствами (за исключением ограничений, требующих, чтобы все переменные были неотрицательными). с,ху 1=1 и сн х, < Ь, при(=1,2,...,т (29.16) максимизируют при условиях (29.17) х.

>0 при7'=1,2,...,п. (29.18) Обобщая введенную для двумерной задачи линейного программирования терминологию, будем называть выражение (29.16) целевой функцией, а и + т неравенств (29.17) и (29.18) — ограничениями; и ограничений (29.18) называются ограничениями неолнрицанеельнослни. Произвольная задача линейного программирования не обязательно содержит ограничения неотрицательности, но в стандартной форме они необходимы. Иногда удобно записывать задачу линейного программирования в более компактной форме.

Определим т х и-матрицу А,= (а,,), т-мерный вектор 6 = (6,), и-мерный вектор с = (с,) и и-мерный вектор х = (х.). Тогда задачу линейного программирования (29.16)-(29.18) можно записать в следующем виде: максимизировать с х при условиях Ах < Ь (29.19) (29.20) (29.21) х>0 В строке (29.19) сгх представляет собой скалярное произведение двух векторов. В неравенстве (29.20) Ах является произведением матрицы и вектора, а х > 0 в (29.21) означает, что все компоненты вектора х должны быть неотрицательными. Таким образом, задачу линейного программирования в стандартной форме можно описать с помощью тройки (А, Ь, с), и мы примем соглашение, что А, Ь, и с всегда имеют указанную выше размерность.

Стандартная форма В стандартной форне задаются и действительных чисел ем сз,...,с„; т действительных чисел 6з, Ьз,..., Ь; и тп действительных чисел а,, где 1 = 1, 2,..., т и 1 = 1, 2,..., и. Требуется найти п действительных чисел хы хз,..., х„, которые б92 Часть Иб Избранные нти Теперь введем терминологию для описания различных ситуаций, возникающих в линейном программировании. Некоторые термины уже использовались в двумерной задаче. Набор значений переменных х, которые удовлетворяют всем ограничениям, называется допустимым решением, в то время как набор значений переменных х, не удовлетворяющий хотя бы одному ограничению, называется недопустимым решением.

Решению х соответствует целевое значение сгх. Допустимое решение х, целевое значение которого является максимальным среди всех допустимых решений, является онтимаяьньии решением, а его целевое значение стх называется онтимальньии целевым значением. Если задача линейного программирования не имеет допустимых решений, она называется неразрешимой (шгеаз(Ые), в противном случае она является разрешимой (Геаз)Ые).

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

Исходная задача может находиться ие в стандартной форме по четырем причинам. !. Целевая функция минимизируется, а ие максимизируется. 2. На некоторые переменные не наложены условия неотрицательности. 3. Некоторые ограничения имеют форму равенств, т.е. имеют знак равенства вместо знака "меньше или равно". 4. Некоторые ограничения-неравенства вместо знака "меньше или равно" имеют знак "больше или равно". Преобразовывая задачу линейного программирования Т, в другую задачу линейного программирования К мы бы хотели, чтобы оптимальное решение задачи Б' позволяло найти оптимальное решение задачи Т.

Будем говорить, что две задачи максимизации, Т, и К эквивалентам, если для каждого допустимого решения х задачи Т, с целевым значением г существует соответствующее допустимое решение х' задачи г.' с целевым значением г, а для каждого допустимого решения х' задачи г.' с целевым значением г существует соответствующее допустимое решение х задачи Т с целевым значением г. (Из этого определения не следует взаимно однозначное соответствие между допустимыми решениями.) Задача минимизации Б и задача максимизации Ь' эквивалентны, если для каждого допустимого решения х задачи Т, с целевым значением г существует соответствующее допустимое решение х' задачи г.' с целевым значением — г, а для каждого допустимого решения х' задачи г,' с целевым значением г существует соответствующее допустимое решение х задачи Т с целевым значением — г. 893 Глава 29.

Линейное нрограммирование Теперь покажем, как поочередно избавиться от перечисленных выше возможнык проблем. После устранения каждого несоответствия стандартной форме докажем, что новая задача линейного программирования эквивалентна старой. Чтобы превратить задачу минимизации Ь в эквивалентную ей задачу максимизации К достаточно просто изменить знаки коэффициентов целевой функции на противоположные. Поскольку Ь и Ь' имеют одинаковые множества допустимых решений и для любого допустимого решения целевое значение 7 противоположно целевому значению К эти две задачи линейного программирования эквивалентны. Например, пусть исходная задача имеет вид минимизировать — 2х1 + Зхз при условиях х1 + хз = 7 х1 — 2хз < 4 х) > О. Если мы поменяем знаки коэффициентов целевой функции, то получим следую- щую задачу: максимизировать 2х1 — Зхз при условиях х1 + хз = 7 х1 — 2хз < 4 х1 >О.

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

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