Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 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 Теперь покажем, как поочередно избавиться от перечисленных выше проблем. После устранения каждого несоответствия стандартной форме докажем, что новая задача линейного программирования эквивалентна старой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
