Сведение задачи оптимизации с дробно-линейным функционалом к аналогичной задаче с линейным функционалом

Размещено на http://www.allbest.ru/

СВЕДЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ С ДРОБНО-ЛИНЕЙНЫМ ФУНКЦИОНАЛОМ К АНАЛОГИЧНОЙ ЗАДАЧЕ С ЛИНЕЙНЫМ ФУНКЦИОНАЛОМ

В.Г. Мотанов - канд. физ.-мат. наук, доцент

ФГОУ ВПО «Московский государственный университет природообустройства», г. Москва, Россия

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

Рассмотрим следующую задачу:

Максимизировать

при ограничениях

Обозначим множество решений неравенств (2),(3) через M. Если знаменатель функции (1) в точках множества М обращается в 0, то функция (1) не ограничена на множестве М ни сверху, ни снизу. В этом случае задача (1),(2),(3) тривиальна. Поэтому предположим, что знаменатель в точках множества М не обращается в 0. Кроме того, предположим, что множество M ограничено. Задачу (1),(2),(3) при этих предположениях будем называть задачей D. Оказывается, что с точки зрения проективной геометрии задача D эквивалентна задаче оптимизации с линейным функционалом, которую будем называть задачей L. Точнее, всегда найдётся некоторое проективное преобразование пространства y1, y2,...,yn, переводящее задачу D в задачу L, причём это преобразование не разрывает множество М, так как гиперплоскость, переходящая в бесконечно удалённую гиперплоскость не проходит через внутренние точки множества М. В частности, если ограничения (2) линейны, то задача D будет задачей дробно-линейного программирования, которую для краткости будем называть задача DL. В этом случае проективное преобразование переводит многогранное множество М снова в многогранное множество, так как гиперплоскость, переходящая в бесконечно удалённую гиперплоскость не проходит через внутренние точки множества М. В этом случае задача DL эквивалентна задаче линейного программирования, которую для краткости будем называть задачей LL. По той же причине, если ограничения (2) выпуклы, то задача D в этом случае будет эквивалентна задаче выпуклого программирования с линейном функционалом.

Покажем, что с точки зрения проективной геометрии задача D эквивалентна задаче L. Для этого сначала покажем, что любое проективное преобразование, переводящее гиперплоскость

(4)

в бесконечно удалённую гиперплоскость, «выпрямляет» дробно-линейную функцию (1), то есть переводит дробно-линейную функцию (1) в линейную функцию.

Подействуем проективным преобразованием

(j = 1,2,…,n) (5)

на гиперплоскость (4). Получим

или, меняя порядок суммирования

Проективным преобразованием (5) гиперплоскость (4) переводится в бесконечно удалённую гиперплоскость тогда и только тогда, когда

Но в этом случае, если то, очевидно, что дробно-линейная функция (1) переходит в линейную, то есть задача D переходит в задачу L. Указанных проективных преобразований существует бесконечно много. Возникает задача нахождения наиболее простого такого преобразования. Критерии простоты при этом возможны различные. Важным критерием простоты является сохранение структуры ограничений (2), (3), то есть сохранение, как числа ограничений вида (2), так и числа ограничений вида (3). Будем искать такое проективное преобразование (5), которое ограничения (3) переводит в ограничения такого же вида, то есть в ограничения

y`j 0, (j = 1,2,…,n). (6)

Сначала покажем, что этого всегда можно добиться, если Действительно, рассмотрим проективное преобразование вида

Подействуем этим преобразованием на гиперплоскость (4). Получим

Преобразование (7) переводит бесконечно удалённую гиперплоскость в гиперплоскость

Так как множество M ограничено, то на точках множества M' (в которое переводится множество М преобразованием (7)) левая часть (9) отлична от нуля. Поэтому, на точках множества M' уравнение (8) можно переписать в виде:

или

Теперь выберем такими, чтобы гиперплоскость (4) переводилась преобразованием (7) в бесконечно удалённую гиперплоскость. Полагая

добьёмся этого. Кроме того, легко проверяется, что проективное преобразование

переводит дробно-линейную функцию (1) в линейную функцию

где

Ниже будет показано, что на множестве М' функция

имеет один и тот же знак. Отсюда следует, что ограничения (3) при преобразовании (11) очевидно переходят или в ограничения (6) или в ограничения

которые заменой перейдут в ограничения вида (6).

Пусть ограничения (2),(3) преобразованием (11) переводятся в следующие ограничения:

Очевидно, что максимумы (минимумы) функции (1) на множестве М и функции (12) на множестве М' одинаковы. Таким образом, в случае , задача D проективным преобразованием координат (11) переводится в следующую эквивалентную задачу L.

Максимизировать линейную функцию (12) на множестве М', определяемом неравенствами (13), (3'). При этом существенно, что за счёт специального выбора проективного преобразования ограничения (2), (3) переходят в ограничения такого же типа (13), (3'). В частности, если ограничения (2) линейны, то ограничения (13) также будут линейными. В этом случае задача (1), (2), (3) является задачей дробно-линейного программирования и проективным преобразованием (11) она переводится в задачу линейного программирования (12), (13), (3') с сохранением структуры ограничений (2), (3).

После определения оптимального решения полученной задачи (12), (13), (3') в штрихованных координатах, с помощью формул (11) выразим это решение в исходных координатах.

Осталось показать, что на точках множества M' знак функции (*) будет один и тот же, а также определить этот знак. Покажем, что этот знак однозначно определяется знаком знаменателя функции (1), который не меняется на точках множества М, и знаком числа bn+1. Для этого необходимо воспользоваться преобразованием обратным к преобразованию (11). Найдём это преобразование. Из (11) вытекает, что для любых i, j = 1,2,...,n

дробный линейный проективный геометрия

Откуда

Далее, из (11) имеем

Откуда, в силу (15)

или

Следовательно,

Подставляя (16) в (*), после несложных преобразований, получим

то есть знак функции (*) совпадает со знаком выражения

Следовательно, если знаки знаменателя функции (1) на множестве М и числа bn+1 совпадают, то функция (*) положительна на множестве M'. В противном случае функция (*) на множестве M' отрицательна.

Случай bn+1 = 0 сводится к рассмотренному случаю, например, с помощью линейного преобразования вида

где j, (1 j n) такое, что bj 0, а ij =

С целью иллюстрации изложенной теории рассмотрим элементарный пример.

Пусть требуется максимизировать дробно-линейную функцию

на множестве М

Согласно общей теории эта задача дробно-линейного программирования проективным преобразованием:

переводится в следующую задачу линейного программирования:

Максимизировать линейную функцию

на множестве M'

Легко убедиться, что максимальное решение последней задачи достигается в точке и Этому решению соответствует следующее максимальное решение исходной задачи дробно-линейного программирования которое вычисляется по формулам (17), (18).

Библиографический список

1. Мотанов В.Г. О задачах оптимизации с дробно-ли-нейным функционалом. //Экономика и математические методы. 1971. № 4.

2. Базара М., Шетти К. Нелинейное программирование. - М.: Мир, 1982.

Размещено на Allbest.ru