ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2008, том 48, < 11, с. 1968-1978
УДК 519.658
ОБРАТНАЯ ДОПОЛНИТЕЛЬНОСТЬ В МОДЕЛИ ДЕФИЦИТА РЕСУРСОВ
© 2008 г. А. В. Зыкина
(644050 Омск, пр-т Мира, 11, ОмГТУ) e-mail: avzykina@mail.ru Поступила в редакцию 16.03.2007 г.
Переработанный вариант 02.04.2008 г.
Рассматривается понятие обратной дополнительности для параметрического семейства задач оптимизации. Введенное понятие является эффективным инструментом для решения сложных прикладных задач, возникающих в социально-экономических системах. В качестве примера построена нелинейная модель дефицита ресурсов, равновесие которой характеризуется внешней рыночной стоимостью ресурсов, совпадающей с внутренними объективно обусловленными оценками ресурсов. Предлагается экстрапроксимальный метод для вычисления равновесного решения. Доказывается сходимость. Библ. 21.
Ключевые слова: обратная задача, задача дополнительности, двойственность, седловая точка, экстрапроксимальный метод, сходимость.
ВВЕДЕНИЕ
Рассмотрим задачу выпуклого программирования (ВП)
min{ f о( X )| f ! ( X )<fm( x )< bm, X G X } , (1)
где выпуклое множество Xç R",f0, ..., fm : I —► R - выпуклые функции.
Общепринятая экономическая интерпретация задачи ВП - это модель производства, в которой требуется выбрать интенсивности x = (x1, ..., x„), x g X, работы предприятия такие, чтобы обеспечить выпуск продукции в соответствии с технологическим процессом (f1(x), ..., fm(x)) из ограниченных объемов запасов ресурсов b = (b1, ..., bm) с минимальными издержкамиf0(x).
В соответствии с классической теорией двойственности каждому виду ресурса i g {1, 2, ..., m} соответствует внутренняя объективно обусловленная оценка ui > 0, i g {1, 2, ..., m}, по Л.В. Кан-таровичу (множители Лагранжа), причем более дефицитные ресурсы имеют большие оценки и, наоборот, ресурсы, имеющиеся в избытке, получают нулевые оценки. Однако в случае противоречивости исходной модели (1), например при недостатке запасов ресурсов b для планируемого производства X, система ограничений будет несовместной, а соответствующая задача оптимизации (1) становится несобственной и классический аппарат двойственности уже применять нельзя [1]. Одним из подходов, предложенных в [1]-[3] для коррекции таких задач, является параметризация и определение параметров, обеспечивающих разрешимость задачи. При этом можно дополнительно оптимизировать получаемую в результате коррекцию задачи.
Очевидно, что если объемы ресурсов (компоненты в векторе b) неограниченно увеличивать, то их дефицитность будет уменьшаться, на каком-то этапе система ограничений станет совместной и в случае несобственности I рода задача оптимизации будет разрешимой; соответственно увеличению объемов ресурсов b = (b1, ..., bm) будут уменьшаться объективно обусловленные оценки u = (u1, ..., um) и издержки предприятияf0(x) по выпуску продукции. Но чем больше расходуется ресурсов для производства, тем больше спрос на эти ресурсы и тем больше их рыночная стоимость. В связи с этим возникает проблема согласования дефицитности ресурсов с их внешней рыночной стоимостью. Решение этой проблемы приводит к различного рода равновесным конструкциям, таким как задачи о вычислении неподвижных точек, обратные задачи оптимизации и др. Одна из первых моделей равновесия в экономике предложена Вальрасом (см. [4]). Состояние равновесия по Вальрасу характеризуют рыночные цены ресурсов, для которых суммарный спрос по каждому товару совпадает с суммарным предложением. Этот подход в моделиро-
1968
вании социально-экономических систем получил широкое применение благодаря доказательству существования равновесных цен для математической модели рыночной экономики Эрроу-Дебре. Однако многочисленные попытки сделать равновесие по Вальрасу универсальным инструментом исследования в экономических моделях столкнулись со значительными трудностями при моделировании реальных экономических систем. В связи с этим необходимо, с одной стороны, выделить круг задач, которые могут быть решены на основе равновесного подхода, с другой стороны, ввести обобщение понятия равновесия. Исследования такого рода см. в работах [5]-[7], постановки таких задач можно встретить в [8], [9]. В предлагаемой работе рассмотрим одно из возможных обобщений таких постановок.
1. ПОСТАНОВКА ЗАДАЧИ
Существенным недостатком модели экономической системы (1) является неизменность самой системы по отношению к внешним управляющим воздействиям в течение заданного периода времени. В этом случае при построении модели (1) предполагается, что выбор каких-либо внешних управляющих воздействий (к примеру, изменение рыночных цен на используемые в системе ресурсы) не приведет к изменению самой системы (в том числе не изменятся и двойственные переменные - объективно обусловленные оценки ресурсов). Очевидно, такое предположение намного сужает область применения подобных моделей. Для устранения этого недостатка введем в задачу ВП (1) параметры y = (y1, ..., ym), характеризующие рыночную стоимость ресурсов, тогда объемы запасов ресурсов b естественно рассматривать как функцию от у. Кроме того, издержки производства свяжем покоординатно с ресурсами, что тоже вполне естественно, так как с каждым видом ресурса могут быть связаны свои производственные затраты. Итак, пусть
Fo(x) = (/oi(x), ., fom(x)), Fi(x) = (fii(x), ., fim(x)), P(y) = (px(y), ., Pm(y)), x e X, X с [", X - выпуклое
множество, y e R+" , f0i(x) и f1i(x), i = 1, 2, ..., m, - выпуклые скалярные функции. Функции f0i(x), i = 1, 2, ..., m, задают издержки производства на единицу рыночной стоимости yi для каждого вида ресурса, при возрастании стоимости yi увеличиваются и издержки yif0i(x), функция
m
yT F о (x) = ^ yif 0 i( x)
i = i
задает суммарные издержки. Функции f1i(x), i = 1, 2, ..., m, определяют технологический процесс или расход ресурсов на производство с интенсивностями x = (xx, ..., x„), функции pi(y), i = 1, 2, ..., m, - запасы ресурсов в зависимости от их рыночной стоимости y = (yb ..., ym).
В результате получаем задачу параметрического выпуклого программирования
min{yTFo(x) | Fi (x)< P(y), x e X}, y e С, (2)
содержательно состоящую в минимизации суммарных издержек yт F0(x) производства из ограниченных объемов запасов ресурсов P(y) при меняющейся рыночной стоимости y e [7 ресурсов и заданном технологическом процессе Fx(x). Целевая функция в (2), характеризующая издержки производства, может иметь более общую форму, а именно
min{ F(x, y) | Fi( x)< P( y), x e X}, y e С, (3)
где F : R" x —- [ - функция, выпуклая по переменной x для каждого фиксированного параметра y.
Предположим, что при каждом значении y > 0 задача ВП (3) разрешима и удовлетворяет некоторым условиям регулярности, следовательно, при каждом значении y > 0 существует седло-вая точка (x*, u*) = (x(y), u(y)) функции Лагранжа
L(x, u, y) = F(x, y) + uT[F1 (x) - P(y)], x e X, u e , (4)
и, следовательно, выполняется система неравенств
L(x*, u, y)< L(x*, u*, y)< L(x, u*, y) Vx e X, u e [7. (5)
Подставляя выражение функции Лагранжа (4) в неравенства (5), получаем для каждого значения параметра y > 0 и соответствующей седловой точки (x*, u*) = (x(y), u(y)) систему неравенств
F(x*, y) + uT[Fi(x*) - P(y)]<
< F(x*, y) + (u*)т[F1 (x*) - P(y)]< (6)
< F(x, y) + (u*)т[Fi(x) - P(y)]
с.
для всех х е X, и е
Из первого неравенства (6) вытекает вариационное неравенство
< и - и*, Р(у) - ^(х* ))> 0 Уи е С. (7)
Полагая в (7) сначала и = 2и*, затем и = 0, получаем при каждом значении у > 0 равенство
(и *) т[ Р (у) - х *)] = 0, (8)
выполняющееся при ограничениях
Р(у )> F1 (х *), и * > 0. (9)
Поскольку условия (8), (9) выполняются при каждом значении у > 0, то можно построить точечно-множественное отображение
В: к; — ^Г (10)
которое каждому внешнему параметру у > 0 ставит в соответствие выпуклое замкнутое множество множителей Лагранжа и* с задачи ВП (3), такое, что для любого и* е и* справедливы равенство (8) и неравенства (9).
При выполнении условий теоремы Какутани отображение (10) имеет неподвижную точку В(у) = у = и*, для которой в силу соотношений (8), (9) получаем
Р( и * )> F1( х *), и * > 0, (и* )т [Р( и*) - Fl(x*)] = 0. (11)
Здесь точка х* является точкой минимума функции Лагранжа (4) на множестве X при у = и* и и = и*; это следует из второго неравенства (6), а именно
F (х *, и *) + (и* )т [ F1 (х *) - Р (и * )]< F (х, и *) + (и * )т [ F1( х) - Р (и *)], что эквивалентно задаче ВП (3) при значении параметра у = и*:
шт { F( х, и * )| F1 (х )< Р (и *), х е X }. (12)
Заметим, что соотношения (11) задают параметрическую по параметру х = х* нелинейную задачу дополнительности; с другой стороны, задача ВП (12) является параметрической по параметру у = и*. В силу этого пара задач (11), (12) является взаимно обратной парой задач.
Итак, для решения поставленной задачи (3) при выполнении условий регулярности для каждого значения параметра у > 0 и существовании неподвижной точки точечно-множественного отображения (10) поставим следующую обратную задачу: в параметрическом по параметру у > 0 семействе задач ВП (3) найти задачу, решение х = х(у) которой выступает в качестве параметра нелинейной задачи дополнительности
Р(у)> F1 (х), у > 0, у[Р(у) - ^(х)] = 0. (13)
Введенное дополнительное условие у т[Р(у) - F1(x)] = 0 есть не что иное, как условие дополняющей нежесткости для ограничений исходной задачи F1(x) < Р(у) и внешних управляющих воздействий у > 0. Это условие придает внешним параметрам задачи (3) (или (2)) свойства ее двойственных переменных. Построенные конструкции являются новыми и представляют собой обратные задачи, содержащие экстремальное включение и задачу дополнительности. Если в паре задач (3), (13) исходной считать задачу дополнительности (13), то задача (3) будет обратной к задаче дополнительности (13), или задачей обратной дополнительности (см. [10], [11]).
Пусть в задаче (3), (13) отображение Р линейное, тогда получим следующую задачу:
шт { Р( х, у)|^ (х)< Ру, х е X}, у е К", (14)
Ру > ^ (х), у > 0, у1 [Ру - ^ (х)] = 0, (15)
где Р - квадратная матрица соответствующе
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.