Содержание к диссертации
Введение
Глава I. Исходная оценочная и двойственная задачи математического программирования 21
1.1. Определения, основные обозначения, геометрическая интерпретация 21
1.2. Некоторые свойства функции f{U) 29
1.3. Общая схема метода решения оценочной задачи в случае конечности множества . 39
1.4. Заключение 45
Глава 2. Построение приближенных методов решения задачи с правильным ограничением 47
2.1. Предварительные замечания 48
2.2. Метод решения двойственной задачи 51
2.3. Получение приближенных решений исходной задачи 61
2.4. Метод решения двойственной задачи 69
2.5. Заключение 85
Глава 3. Специальные задачи математического программирования 87
3.1. Предварительные замечания 88
3.2. Простейшая задача распределения ресурсов 91
3.3. Задача выпуклого целочисленного программирования с одним ограничением . 95
3.4. Некоторые модели задачи о ранце . 100
3.5. Двумерная задача о ранце 108
3.6. Задача минимизации числа транспортныхсредств 111
3.7. Задача нахождения связывающего дерева максимального веса с дополнительным ограничением 113
3.8. Минимаксная задача математического программирования 115
3.9. Задача дробного программирования 118
Список основной использованной литературы 125
Приложение 134
- Общая схема метода решения оценочной задачи в случае конечности множества
- Получение приближенных решений исходной задачи
- Задача выпуклого целочисленного программирования с одним ограничением
- Задача нахождения связывающего дерева максимального веса с дополнительным ограничением
Введение к работе
Исследования в области построения алгоритмов решения экстремальных задач математического программирования в настоящее время переживают пору интенсивного роста, это обусловлено тесной связью задач математического программирования с реальными физическими задачами, задачами экономики и многими другими областями человеческой деятельности.
Трудности, связанные с разработкой численных методов решения задач на ЭВМ, возникают в связи со сложностью и громоздкостью математических моделей реальных ситуаций. Преодоление этих трудностей является важной актуальной задачей математического программирования, как с точки зрения требований, предъявляемых к вычислительным методам со стороны практики, так и с точки зрения методов математической оптимизации. Модели прикладных задач, как правило, характеризуются большой размерностью и относительно малой точностью исходных данных. При этом задача с конкретными числовыми данными есть лишь представитель из совокупности задач математического программирования, описывающих одну и ту же реальную ситуацию. В связи с этим основной задачей в практических расчетах следует считать не нахождение оптимального решения конкретной задачи, а скорее нахождение серии "близких к оптимуму" решений, выбором из которой можно ограничиться при решении исходной прикладной задачи. Тем более, что сама исследуемая задача обычно является лишь частью более сложной, и зачастую решаемой лишь эвристически, задачи. При такой постановке задачи принципиальное значение приобретает задача на хождения приближенного экстремума и его корректировка при изменении исходных данных.
В диссертационной работе исследуется метод, позволяющий получать серию "близких к оптимуму" решений некоторого класса задач математического программирования, и оценка качества как самих решений, так и метода получения этих решений. Прежде чем описывать метод, определим некоторые понятия, характеризующие качество алгоритма.
Для отыскания решений одной и той же математической задачи могут быть применены различные алгоритмы, приводящие к различным результатам и требующие различных вычислительных усилий. К числу важных характеристик алгоритмов, по-видимому, следует отнести количество операций (трудоемкость), необходимых для реализации алгоритма. Под операцией будем понимать элементарную операцию (логическую операцию сравнения либо арифметическое действие). При вычислениях на ЭВМ определяющее значение имеет также и количество ячеек памяти, требуемое для реализации алгоритма. Поэтому второй важной характеристикой алгоритма естественно считать объем памяти, используемый при реализации алгоритма; под объемом памяти будем понимать количество ячеек, требуемое для хранения всех необходимых в процессе работы алгоритма величин при условии, что каждое число занимает одну ячейку. Если для точных алгоритмов оценок трудоемкости и объема памяти можно считать достаточными для грубой характеристики качества алгоритма, то для приближенных алгоритмов, кроме того, необходимо еще иметь представление о точности получаемых решений.
Алгоритм будем характеризовать оценками (сверху) для количества операций и объема памяти, необходимыми для решения задачи. Указанные оценки естественно рассматривать в зависимости от размерности задачи, причем важен лишь вид этих зависимостей с точностью до постоянного множителя.Далее оценку числа операций будем обозначать через Ж , а объема памяти через 0[ . При этом, если оценка Ж имеет вид 3C=cf(L), где СУ0 - константа, Z - некоторый параметр, то будем писать X -f(L) или X=0(-flL)). Аналогичные обозначения будем использовать и для объема памяти Ж ,
Оценки трудоемкости и объема памяти назовем эффективными, если они являются степенными выражениями относительно размерности задачи. Под размерностью задачи понимается число битов, необходимых для записи исходных данных задачи. Если не оговорено противное, то под знаком too. понимается логарифм по основанию два. Алгоритм будем называть эффективным, если он имеет эффективные оценки трудоемкости.
Как показывает опыт, для некоторых дискретных задач математического программирования (например, для задачи о ранце) трудоемкость известных точных методов имеет порядок сложности полного перебора, т.е. экспоненциальным образом зависит от длины записи исходных данных. Такой рост трудоемкости задачи быстро выводит алгоритм за пределы его практической реализуемости. Косвенным доказательством трудности построения эффективных точных алгоритмов для ряда задач математического программирования являются результаты Кука П3?3 и Карпа [16, 32,373. Поэтому поиски эффективных и точных алгоритмов решения многих известных задач представляются мало перспективными. Это обстоятельство существенным образом побуждает нас
ограничиться классом приближенных алгоритмов.
Будем говорить, что приближенный алгоритм решения экстремальной задачи математического программирования имеет оценку точности і (является &-приближенным), О если абсолютная погрешность допустимого (т.е. удовлетворяющего всем ограничениям рассматриваемой задачи) решения х , получаемого посредством данного алгоритма, не превышает величины 6 ; решение X при этом будем называть -оптимальным (или -приближенным). Под абсолютной погрешностью понимается величина \Е[Хтт) - ЕІХ)\, где Е- целевая функция рассматриваемой задачи, а Я опт" оптимальное решение. Ясно, что чем меньше величина 8 , тем алгоритм точнее.
Охарактеризуем используемый в диссертации математический аппарат, который позволяет строить серию "близких к оптимуму" решений задач математического программирования, и на котором основаны алгоритмы решения конкретных задач.
В ходе развития математического программирования было замечено, что при исследовании экстремальных задач полезно наряду с исходной задачей рассматривать двойственную к ней экстремальную задачу. Это привело к созданию принципа двойственности, позволяющего с единой точки зрения исследовать широкий круг задач математического программирования.
Неявное использование наряду с исходной экстремальной задачей двойственной к ней, можно найти еще в работах П.Л.Че-бышева, посвященных задаче наилучшего приближения заданной функции линейными комбинациями фиксированных функций. В настоящее время теорию двойственности можно считать в основном завершенной. Помимо схем, пригодных для исследования отдельных классов задач [114,17,22,31,42,491], имеется универсальная схема принципа двойственности С5Щ. Применение теории двойственности для анализа и корректировки несобственных (т.е. не имеющих решения) задач исследуется в С2И.
Исходная условно экстремальная задача может быть переформулирована в виде минимаксной задачи; изменение порядка выполнения операций взятия максимума и минимума приводит к двойственной задаче. Решение, получаемой таким образом двойственной задачи, вообще говоря, не совпадает с решением исходной; имеет место "разрыв двойственности". Кроме того, численное решение двойственной задачи может оказаться столь же трудным, сколь и решение исходной.
В § І.З показано, что если множество 42- конечно, то оценочная и двойственная задачи являются задачами линейного программирования, причем эти задачи находятся в отношении взаимной двойственности (в смысле двойственности задач линейного программирования). Описывается алгоритм решения оценочной задачи, основанный на симплекс-методе [503 и методе генерации столбцов Г423. Трудоемкость решения оценочной задачи определяется трудоемкостью симплекс-метода, а число ячеек памяти, требуемой для решения оценочной, а, следовательно, и двойственной задачи 0{mz).
Выбор симплекс-метода для решения оценочной задачи обусловлен тем, что, как известно из большого вычислительного опыта, его практическая эффективность удовлетворительная, хотя теоретически его трудоемкость имеет экспоненциальную зависимость от размерности задачи. Как отмечалось в С29], при определенных вероятностных предположениях число итераций в симплекс-методе при фиксированном числе ограничений растет в среднем полиномиальною по числу переменных. В Q58D описан теоретически эффективный алгоритм решения задач линейного программирования, однако, работоспособность этого алгоритма существенным образом зависит от точности вычисления промежуточных результатов. Поэтому в настоящее время с практической точки зрения симплекс-метод, пожалуй, является более предпочтительным для решения двойственной задачи. Он позволяет строить последовательность векторов и , причем каждому и соответствует решение іг" исходной задачи, в силу свойства].
Таким образом, так как исходные данные практических задач часто задаются неточно [44], то последовательность іг" может быть полезна для изучения зависимости решений исходной задачи от вектора Q & ) , если же Q{W ) "близко" к А , то решение и практически можно считать приемлемым по точности.
Вторая глава является основной в диссертационной работе. В ней изложен метод решения двойственной задачи для исходной задачи вида max (vw л] при достаточно общих предположениях. Получена оценка числа точек U-1SX , в которых требуется искать элемент множества &&{и) для приближенного решения двойственной задачи, и доказана оценка отклонения приближенного решения от оптимального.
В математическом программировании общепринято деление задач на различные классы в зависимости от вида целевой функции и характера ограничений (линейное программирование, выпуклое программирование, дискретное программирование, геометрическое программирование и т.п.).
Идея метода решения двойственной задачи состоит в следующем: исходная область неопределенности разбивается на две равные части и определяется часть, содержащая приближенное решение двойственной задачи и т.д. В результате приходим к некоторой конечной области, содержащей приближенное решение задачи тип. Имеет место
В третьей главе диссертационной работы исследуется возможность применения общей схемы двойственности для получения решений ряда специальных задач математического программирования в случае /vz = / .В этом случае, если исходная задача имеет допустимые решения, то рассмотрение двойственной задачи позволяет получить хотя бы одно из них. В случае решение двойственной задачи, вообще говоря, может не быть допустимым для исходной.
В работах [2,9,10,57,77,81] предлагаются -приближенные ( - любое положительное число) методы решения некоторых дискретных задач. В [9] проведен анализ приближенных алгоритмов, определен класс быстрых алгоритмов, т.е. &-приближенных алгоритмов, трудоемкость и память которых ограничены сверху полиномами от числа переменных и &ч . Построение быстрых алгоритмов для большинства дискретных оптимизационных задач является проблематичным делом. Так, например, для двумерной задачи о ранце специального вида (§ 3.6) существование быстрого алгоритма ее решения означало бы совпадение классов задач, решаемых за полиномиальное время, и классов задач, решаемых с помощью перебора конечномерных булевых векторов [19]. В настоящее время вопрос о совпадении этих классов не решен. Следует отметить работу [34], в которой изучаются возможности приближенных алгоритмов градиентного типа для решения задач дискретной оптимизации.
В главе 3 проиллюстрировано приложение результатов первой и второй глав для решения ряда задач математического программирования, при этом для дискретных задач, как правило, имеет место "разрыв двойственности" (несовпадение значений целевых функций исходной и двойственной задачи), что не позволяет получить -приближенное решение с любой наперед заданной точностью. Тем не менее, приближенное решение с априорной оценкой точности, может быть получено быстро, причем объем памяти, требуемый для нахождения приближенного решения, того же порядка, что и объем памяти, используемый для хранения исходных данных. Привлечение двойственной задачи, как правило, оправдывается в случае простоты решения этой задачи по сравнению с исходной.
В § 3.1 приведены предварительные замечания.
В §§ 3.2-3.7 приведен перечень основных задач, для которых получена оценка точности и трудоемкости приближенного решения. Точность решения является оценкой сверху для "разрыва двойственности" рассматриваемых дискретных задач. Алгоритмы решения приведенных задач основаны на теоремах § 2.3.
В § 3.8 идея метода решения двойственной задачи используется для получения решений с апостериорной оценкой точности минимаксной задачи.
В § 3.9 рассматривается задача дробного программирования. Решение этой задачи сводится к нахождению нуля функции flu) . Показывается, что в случае существования эффективного алгоритма вычисления значения функции р(и) для приближенного решения задачи дробного программирования всегда существует эффективный алгоритм. В качестве иллюстративного примера рассмотрено решение задачи о назначении с дробным функционалом.
Основные результаты диссертации опубликованы в работах С83-89Ц и докладывались на ІУ, У Всесоюзных конференциях по проблемам теоретической кибернетики (г.Новосибирск,1977,1980), на ІУ, У Всесоюзных семинарах по комбинаторному анализу (г. Москва, 1978,1981), на ЗУ Сибирской школе-семинаре по методам оптимизации и их приложениям, на Семинаре по дискретной оптимизации (г. Симферополь, 1983), на Всесоюзной конференции по проблемам теоретической кибернетики (г. Саратов, 1983), а также на семинарах в Институте математики СО АН СССР.
Автор выражает искреннюю признательность научному руководителю Э.Х. Гимади за постоянное внимание и всестороннюю поддержку, и Н.И. Глебову за советы и критические замечания, оказанные при выполнении данной работы.
Общая схема метода решения оценочной задачи в случае конечности множества
В І.З показано, что если множество 42- конечно, то оценочная и двойственная задачи являются задачами линейного программирования, причем эти задачи находятся в отношении взаимной двойственности (в смысле двойственности задач линейного программирования). Описывается алгоритм решения оценочной задачи, основанный на симплекс-методе [503 и методе генерации столбцов Г423. Трудоемкость решения оценочной задачи определяется трудоемкостью симплекс-метода,а число ячеек памяти, требуемой для решения оценочной, а, следовательно, и двойственной задачи 0{mz).
Выбор симплекс-метода для решения оценочной задачи обусловлен тем, что, как известно из большого вычислительного опыта, его практическая эффективность удовлетворительная,хотя теоретически его трудоемкость имеет экспоненциальную зависимость от размерности задачи. Как отмечалось в С29], при определенных вероятностных предположениях число итераций в симплекс-методе при фиксированном числе ограничений растет в среднем полиномиально по числу переменных. В Q58D описан теоретически эффективный алгоритм решения задач линейного программирования, однако, работоспособность этого алгоритма существенным образом зависит от точности вычисления промежуточных результатов. Поэтому в настоящее время с практической точки зрения симплекс-метод, пожалуй, является более предпочтительным для решения двойственной задачи. Он позволяет строить последовательность векторов и , причем каждому и соответствует решение іг" исходной задачи, в силу свойства I, является -оптимальным решением задачи max{f[ir)\ ilffkgl(ir )9ecm tii 0;gUr)-%(tr), еоляи о].
Таким образом, так как исходные данные практических задач часто задаются неточно [44], то последовательность іг" может быть полезна для изучения зависимости решений исходной задачи от вектора Q & ) , если же Q{W ) "близко" к А , то решение и практически можно считать приемлемым по точности.
Вторая глава является основной в диссертационной работе. В ней изложен метод решения двойственной задачи для исходной задачи вида max (vw л] при достаточно общих предполо жениях. Получена оценка числа точек U-1SX , в которых требуется искать элемент множества &&{и) для приближенного решения двойственной задачи, и доказана оценка отклонения приближенного решения от оптимального.
В математическом программировании общепринято деление задач на различные классы в зависимости от вида целевой функции и характера ограничений (линейное программирование,выпуклое программирование, дискретное программирование, геометрическое программирование и т.п.).
Ограничение w к исходной задачи max {vW /4j будем называть правильным, если введение его в целевую функцию задачи тля V , относящейся к какому-либо классу, с помощью множителя Лагранжа, не выводит эту новую задачу из упомянутого класса. Во второй главе рассмотрены некоторые достаточные условия, которые при т-\ позволяют эффективно получить при-женное решение исходной задачи с правильным ограничением,после того как получено решение двойственной.
Пусть т= / , если из каких-либо априорных соображений можно задать число а О , при котором то, в силу выпуклости функции cpiU), для приближенного нахождения пил (d)(u)±U A) может быть приме-нена процедура одномерной оптимизации. В [54] приведено несколько эффективных процедур одномерного поиска, позволящих определить интервал значений переменной, внутри которого лежит минимум унимодальной функции. Процедуры одномерного поиска, приспособленные для алгоритма наискорейшего спуска [78] изложены в [69, 76].
Идейно эта процедура опирается на метод дихотомии (поиск Больцаяо). Суть этого метода состоит в том, что начальный интервал неопределенности OnjU] делится на две равные части. В зависимости от соотношения между значением iic (U) в точке деления 11= — и числом п левая или правая часть бе рется в качестве нового интервала. Если имеет место неравенство U[U) А , то в качестве нового интервала берется правая половина, в случае и (и) л - левая. Если ц (U)=A, то точка деления является -оптимальным решением задачи
Таким образом, при поиске получаются интервалы, длина каждого из которых равна половине длины его предшественника. Так как выбранный интервал содержит точку приближенного решения, то, очевидно, процедура дихотомии сходится к приближенному решению задачи mm (ф(и)+и-А) , причем, в силу специфики функции у {и) , удается оценить точность решения задачи пг ыъ (ip{U)\u-А) через длину текущего интервала.
Получение приближенных решений исходной задачи
В третьей главе диссертационной работы исследуется возможность применения общей схемы двойственности для получения решений ряда оптимизационных задач специального вида. В основном рассматриваются задачи дискретного программирования, характерной особенностью которых является возможность получения точного решения за конечное число шагов перебором всех допустимых вариантов и практическая его нереализуемость даже во многих простейших случаях. Привлечение двойственной задачи, как правило, оправдывается в случае простоты решения этой задачи по сравнению с исходной. Однако, для дискретных экстремальных . задач возникает проблема "разрыва двойственности", вызванная дискретностью множества определения рассматриваемых функций и наличием значительного числа локальных экстремумов. В 3.1 приведены предварительные замечания, определен случай, когда исходная задача имеет решение и выделенное ограничение этой задачи существенно. В 3.2-3.7 приведен перечень некоторых задач, для которых получена оценка трудоемкости решения двойственной задачи и точности получаемого допустимого решения исходной.Точность решения является оценкой сверху для "разрыва двойственности". Для каждой задачи приведена математическая постановка, конспективно описан алгоритм решения, приведена оценка его трудоемкости. В 3.8 рассмотрена минимаксная задача, доказана теорема, позволяющая получить приближенное решение с апостериорной оценкой точности. В 3.9 показывается, что идея метода решения двойственной задачи применима для задач дробного программирования. 3.1. Предварительные замечания В первой и второй главах результаты в основном формулировались для исходной задачи вида max vW-/U. Однако, при решении задач математического программирования, интерес представляют не только значения целевых функций условно экстремальных задач, но и те аргументы, на которых эти значения достигаются. В 3.2-3.7 в качестве исходной рассматривается задача вида: XeS и множества (U) = (Х Л (p(U)=f[X)-U-$M} , f6(U)-{US\ if [UH/(Xk/«y(X))&}.Обозначим: Xй (X & ) - элемент множества $(U){]j&lU)), если а помечен верхним индексом t , то через X (X ) обозначается элемент множества /(# ) (/ (# )) Очевидно, 4To(/(X , (X"))e W ж[ЦЦ\д[%1))ь&(и). Пусть j ж G - вещественные числа, удовлетворяющие условиям: fzmax-PiX), G max\tnax g(X),A]. (3.5) Решение задачи P будем осуществлять следующим образом. По исходной задаче (3.1)-(3.3) строим двойственную к ней задачу сЮ ; применяя описанный в 2.2 алгоритм Д .находим решение (решения) задачи 0 ; используя решение (решения) задачи ьО находим решение задачи (3.1)-(3.3). При описании алгоритма решения рассматриваемых в 3.2-3.7 задач, алгоритм Д излагать не будем, а зададим лишь конкретные значения необходимых для его работы величин.С целью сокращения объема опустим несущественные детали, будем придерживаться конспективного изложения, так как подробное изложение материала третьей главы (за исключением 3.8,3.9) опубликовано в 1977-1979 гг. [83-86]. Проведем изложение по следующей схеме: 1. Формулировка исходной задачи И в виде (3.1)-(3.3). 2. Конкретизация вида функции (3.4), построение двойственной задачи JD , некоторый совместный анализ задач Р и JP 3. Описание алгоритма Г нахождения элемента X є jf(U-) (X. е[(і/)) и оценка трудоемкости алгоритма Г . Ь "О 4. Задание величин ЗМ, Л U , требуемых для решения задач с0 и Р. 5. Описание алгоритма Н перехода от решения задачи к решению задачи Р и оценка его трудоемкости. 6. Оценка точности и трудоемкости решения задачи Р . В пункте 6 будет приведена лишь оценка числа операций. Объем памяти, требуемый для решения исходной задачи, складывается из объемов памяти, требуемых для работы алгоритмов Г ,Д и Н. В [84-86] показано, что объем памяти, требуемый для решения каждой из рассмотренных в 3.2-3.7 задач, того же порядка, что и объем памяти, используемый для хранения исходных данных соответствующих задач.
Задача выпуклого целочисленного программирования с одним ограничением
В этом параграфе рассматриваются две постановки задачи о ранде с дополнительными ограничениями на переменные.В первой постановке переменные булевы (т.е. принимают лишь два значения - 0 либо I), во второй - неотрицательные целые.Вторая постановка отличается от первой лишь формально, так как, введя дополнительные переменные, можно от целочисленных переменных перейти к булевым [7, с. 284]. Однако, такой переход может привести к значительному увеличению числа булевых переменных. К тому же вторая постановка имеет специфику, которая позволяет получить более содержательные результаты в отношении эффективности получения решений рассматриваемым здесь подходом, в частности, выделить класс задач, решаемых точно.
Пусть переменные Xj (/=/7 задачи (3.25)-(3.27) разбиты на Н непересекающихся групп, причем в пределах -й группы не менее i0i и не более 4/ переменных может быть отлично от нуля. Иными словами, к ограничениям (3.25), (3.26) добавлены следующие: Будем называть задачу максимизации (3.27) при условиях (3.25), (3.26), (3.28), (3.29) задачей . Алгоритм точного решения задачи Sf для целых a , уЦ ti, с использованием динамического программирования, приведен в [8]. 2. Функция if [и) для задачи «5г имеет вид: а задача записывается очевидным образом. 3. В силу сепарабельности функции (3.30), компоненты . , у =/,л, вектора X f Ш) находятся очевидным образом. Действительно, для нахождения компонент Xj , jeJ&, Достаточно упорядочить по неубыванию разности (Cf-U d:), j Jli а а и, с учетом ограничения (3.28), найти значения ?,jji. Ясно, что трудоемкость алгоритма Г имеет вид: 3 . Рассмотрим встречающийся на практике частный случай задачи Л . Пусть исходные данные (/,#;, і=Ці) обладают тем свойством, что последовательность dj Cr-U dj, j ej% вогнута. Под вогнутой последовательностью понимается такая последова тельность dvdz ,,,, dni... вещественных чисел,что разность dj-d-_f (/ ) не возрастает с увеличением индекса у . Пусть элементы множества Jp перенумерованы индексом у , так,что тогда последовательность d;=C.--U-a вогнута, если с увеличением а отношения JH—L не воз растают. » Если последовательность Яу вогнута, то для отыскания ее максимального элемента может быть применен метод Фибоначчи [54], требующий 0 [ton I / I) операций. Пусть величины CLj, / 6 ]і образуют арифметическую прогрессию с разностью La , одинаковой для всех Н групп и последовательность d = C -U CLj 1 j 7/- вогнута, тогда трудоемкость получения оптимального решения задачи % оценивается величиной X , определяемой соотношением (3.36).
Отметим в заключение, что задача % может быть использована при решении задач о раскрое, когда ограничено число ножей, применяемых в установле для резки бумаги (см..например, [71]). Частным случаем задачи J является задача, используемая в качестве вспомогательной для решения задачи выбора оптимальной системы (модулей) при неявном задании множества допустимых комплексов [6].
Задача о ранде в вариантной постановке является частным случаем задаче и 3 при значениях l0l=0, 4=/,//f, fy=/ i = H UH\ 4/ = /, =/,tf, в ограничении (3.28). Термин "вариантная" взят из экономической интерпретации рассматриваемой задачи. С помощью вариантной задачи о ранце описываются задачи размещения и развития производства однородной продукции или нескольких различных, но частично или полностью взаимозаменяемых изделий, искусственно сводимых к одному условному продукту [43, с. 334]. Через Й обозначим число различных заводов, производящих этот продукт, а через f/ l -число вариантов развития (ь0=0) или реконструкции ( = Я-то завода, a,: IjtJi) - величину затрат, а С: (jzjt,) -объем выпуска продукции при развитии (реконструкции) /-го варианта на 1-м заводе. Требуется на каждом предприятии выбрать такой вариант развития (реконструкции) чтобы максимизировать суммарный объем выпуска продукции, не выходя за пределы лимита л по ограниченному ресурсу.
Задача нахождения связывающего дерева максимального веса с дополнительным ограничением
Если функции f и а - линейны, а множество Q - многогранно, то функцию Я называют дробно-линейной, а задачу (3.58)-(3.59) - задачей дробно-линейного программирования. К решению задач дробно-линейного программирования применим метод, отличный от симплекс-метода в проверке условий оптимальности [62]. Приспособление известных методов решения задач линейного, сепарабельного и квадратичного программирования для соответствующих задач дробного программирования, предлагалось в работе [60] .
Задачу (3.58)-(3.59) в общем случае будем называть задачей дробного программирования. Напомним, что a[U) 0 (см. I.I), под решением задачи дробного программирования будем понимать элемент множества Q , под оптимальным решением foaT (в пределах данного параграфа) понимается такое реше ние,что ——\ \ для любого 1Гй . Случай а[і5ппг)=0 будет естественным образом доопределен в дальнейшем изложении. В данном параграфе изучается вопрос о связи экстремума некоторой линейной комбинации функций и с оптимальным значением целевой функции задачи дробного программирования и показывается, что если существует эффективный алгоритм вычисления экстремумов линейных комбинаций функций f и с ,то для нахождения -оптимального ( - любое наперед заданное положительное число) значения целевой функции задачи дробного программирования всегда существует эффективный алгоритм. Рассмотрим задачу нахождения максимума целевой функции задачи дробного программирования. Введем функцию ср (U) = =tnCLX (f [5)- 0((1)), LLZR , имеет место ЛЕММА 3.1. Если целевая функция задачи (3.58)-(3.59) ограничена сверху, то функция (f(U) обращается в нуль тогда и только тогда, когда ц = тисе І-—- , Рассмотрим задачу нахождения минимума целевой функции задачи дробного программирования. Введем функцию (f (и) = - nun (-f(iJ)+U а{(?)). Имеет место та J ЛЕММА З.і . Если целевая функция задачи (3.58)-(3.59) ограничена снизу, то функция ср (а) обращается в нуль тогда и только тогда, когда ц-пгіпі - , treQ g-ur) Доказательство аналогично доказательству леммы 3.1. Ограничимся, для определенности, задачей нахождения максимума целевой функции задачи дробного программирования.Пусть известны два значения и ъ U параметра И , такие,что кр[и") 0 ь(р(иг) и и -и В Тогда, в силу леммы 3.1 и свойства I ( 1.2), и тйХ -—г id! , таким образом, и и и" являются -оптимальными значениями целевой функции задачи (3.58)-(3.59), а элементы Uєй zj eQ - -оптимальными решениями этой задачи. Рассмотрим вопрос о нахождении интервала \и\ и"] , при котором (f{a") o Ф[и ). пусть тип д((г) 0. Если пьах-Р(ії) = 0 то, очевидно, шах- =0. ireQ ireQ f(tr) Если max f\(J) 0. то Ф[0)=тах Ш) 0,в.и.щ іі"=тахпії) ТЕОРЕМА 3.4. Априорная оценка числа Т точек, в которых достаточно вычислить значение функции if(u) , для получения &-оптимального значения целевой функции задачи дробного шагов придем к неравенству и1 -W б. Таким образом, 66 и 11 являются 6-оптимальными значениями целевой функции задачи дробного программирования, которым соответст-вуют решения и и и . Пусть rnCLxf[lf)y 0 , нетрудно убедиться, что если функ ция (aj- кусочно-линейна на интервале [б?,//] {u=max-f[if) ireQ %[ітил Q[lf)) )и li" -IIs Л (см. неравенство (2.30)),то точите 5 ное решение задачи дробного программирования получается следующим образом. Обозначим U=(zlurJ)-Z{Ur 2))[ylUTJ) y[aT Z)). Очевидно, имеет место одно из неравенств %[ЦГ,І)-Ц. ЦШГ ) 0, Z{U )-(1-11 (її1 ) 0. В случае первого неравенства lToar = lf , иопт= и ривается аналогично в противном случае Л_= If Случай maxf[if) 0 рассмат 123 Все изложенное в данном параграфе можно перенести на случай, когда на функцию (J, имеет место ограничение g[U) 0 для любого U 0,. В качестве примера рассмотрим одно обобщение задачи нахождения паросочетания максимального веса [30, 67] .в двудольном графе (задачу о назначении с дробным функционалом). Предположим, что имеется к работ A,, h Zf ")An ЯП- механизмов Я,,В т-ч ц Механизмы различаются по своим способностям и по затратам на настройку для выполнения той или иной работы, причем каждый механизм назначается только на одну работу и каждая работа предназначается только для одного механизма. Пусть Сц О - произво-длительность 6-го механизма на у -й работе, a CLn O - затраты на настройку. Наилучшим считается распределение работ, максимизирующее удельную производительность,измеряемую отношением суммы производительностеи всех ft механизмов к сумме затрат на настройку этих механизмов.
