close

Вход

Забыли?

вход по аккаунту

?

Стохастический аналог задачи линейного программирования с эффектом ветвления.

код для вставкиСкачать
ДОКЛАДЫ АКАДЕМИИ НАУК РЕСПУБЛИКИ ТАДЖИКИСТАН
2016, том 59, №7-8
МАТЕМАТИКА
УДК 519.857
Ф.Мирзоахмедов
СТОХАСТИЧЕСКИЙ АНАЛОГ ЗАДАЧИ ЛИНЕЙНОГО
ПРОГРАММИРОВАНИЯ С ЭФФЕКТОМ ВЕТВЛЕНИЯ
Центр инновационного развития науки и новых технологий АН Республики Таджикистан
(Представлено академиком АН Республики Таджикистан М.И.Илоловым 30.04.2015 г.)
В статье даётся эффективный алгоритм симплексного метода для решения общей задачи
линейного программирования, который также используется при решении стохастического
варианта этой же задачи. Доказывется сходимость алгоритма решениия стохастического варианта задачи с учётом эффекта ветвления и потверждается тестовым примером.
Ключевые слова: детерминированная и стохастическая задача, ветвление, квазиградиент, алгоритм решения, теорема сходимости, численный эксперимент.
В современных условиях, с точки зрения новизны и приложения, необходимыми условиями
математического моделирования являются наличия неопределённости, нелинейности, неоднозначности, критических точек, ветвящихся процессов и т.п.
В данной работе будет исследован стохастический аналог общей детерминированной задачи
линейного программирования (ЗЛП) с учётом бифуркационного эффекта и алгоритма её решения.
1. Детерминированная постановка ЗЛП. Классическая детерминированная ЗЛП в канонической форме ставится следующим образом [1]:
n

x*j  arg min  с j x j / x j  X   min ,
 j 1

(1)
n


X   x j :  aij x j  bi , bi  0, i  1, m.  .
j 1


(2)
где
Параметры задачи могут быть интерпретированы следующим образом: n – количество видов
выпускаемой продукции; bi – запасы i -го вида ресурсов; aij – технологические коэффициенты, которые указывают, сколько i -го ресурса требуется для производства продукта j -го вида; x j – объём
производства j -го продукта; с j – затраты, связанные с производством единицы продукта j -го вида.
Ниже изложим эффективный алгоритм решения задачи (1), (2) симплексным методом [1], который используется для приближённого решения стохастической задачи на каждой итерации.
Алгоритм 1. Задачи (1), (2) решаются с помощью симплекс-метода, заданного оператором:
Адрес для корреспонденции: Мирзоахмедов Фахриддин. 734025, Республика Таджикистан, г.Душанбе,
пр. Рудаки, 33, Центр инновационного развития науки и новых технологиий АН РТ. E-mail: mirfakh@mail.ru
303
Доклады Академии наук Республики Таджикистан
2016, том 59, №7-8
x j s1   ( x j s ), x j 0  0.
Здесь x j 0 – начальное приближение для симплекс-метода является базисным решением, векторы x j s 1 и x j s представляют собой последующее и предыдущее решения, то есть
x j s 1  min[
xi s / x
s
xij
s
ij
]  xl s / xlk s , xi s1  xi s  ( xij s  x j s1 ), i  I s 1; i  j, x j s 1  0, j  I s 1.
Здесь элементы новой симплекс-таблицы на (s+1)-й итерации метода вычисляются согласно формуле:
s 1
ik
x
s
s
s
s

 xik  ( xij  xlk ) / xlj , если i  l ,
 s
s
если i  l.

 xlk / xlj ,
2. Стохастическая постановка ЗЛП. Дополнительно к рассмотренным параметрам при постановке детерминированной ЗЛП (1),(2) ввёдем следующие обозначения:  j – независимые случайные величины, например спрос на j-ю производимую продукцию;  i и  i – удельные затраты, связанные с хранением излишней и потери от дефицита j - продукции x j . В связи со случайностью
спроса в процессе принятия решений относительно объёма производства продукции возникают следующие эффекты ветвления:

если объём производимой продукции xj в нужный момент превышает объём спроса  j , то есть
x j   j , то фирма производитель понесет затраты на xpaнeниe перепроизведённой продукции,
равные  j ( x j –  j ) , j  1, 2,..., n , связанные с профицитом в размере x j –  j ;

если объём спроса  j в нужный момент превышает объём производимой продукции x j , то есть
 j  x j , то фирма производитель тepпит yбытки, paвные  j ( j – x j ) , связанные с дефицитом в
размере  j  x j .
Функция затрат f j ( x j ,  j ) , связанная с объёмом производства продукции x j , с учётом случайного спроса  j , может быть представлена в виде следующей выпуклой разветевляющейся (кусочно-линейной) функции затрат:

 j ( x j   j ), если
f j ( x j , j )  

  j ( j  x j ), если
x j   j ,  j  0,
x j   j ,  j  0,
На pиcунке пoкaзaна функция f j ( x j ,  j ) для cлyчaя c j   j .
304
j  1, ..., n.
(3)
Математика
Ф.Мирзоахмедов
fj(xj, j)
xj=j хj
Рис. Возникновение эффекта ветвления при x j   j .
Таким образом, стохастический аналог ЗЛП (1),(2) примет вид
x j*  arg min F ( x) / X ,
(1а)
где
n
n
 n
 n
F ( x )  M   c j x j   f j ( x j ,  j )    c j x j  M  max  j ( x j   j );  j ( j  x j ) 
j 1
j 1
 j 1
 j 1

 xj

  c j x j      j ( x   j ) P(d  j )    j ( j  x j ) P(d  j )  .

j 1
j 1  0
xj


n
n
Здесь M – оператор математического ожидания; f ( x j ,  j ) – измеримая функция при каждом  j ;  j – элементарное событие вероятностного пространства (, Z , P), где  – множество
элементарных событий; Z – есть  -алгебра измеримых множеств из ; P  определённая в 
вероятностная мера, то есть P()  1 . В свою очередь Z можно интерпретировать как перечень
всех трёх групп конкретных исходов, которым можно приписать для всех групп из Z (например, это
может быть аналитическая функция и т.п.).
Целевая функция F ( x ) , помимо затрат на производство, выраженных в (1), также содержит
ожидаемые затраты, связанные с дефицитом и профицитом произведенной продукции. Задача
(1а),(2) является частным случаем общей задачи стохастического программирования [2]. Ниже рассмотрим алгоритм решения этой задачи.
Алгоритм 2. Пусть на s -м шаге (итерации) получено пpиближeниe х is , s  0,1,..., ( x 0 - заданное произвольное начальное приближение). Тогда:
1. B cooтвeтcтвии c aпpиopным pacпpeдeлeниeм  ( ) пoлyчaeм нaблюдeниe  sj нaд
peaлизaциeй cлyчaйнoй вeличины  j . Здecь  sj – нeзaвиcимoe нaблюдeниe нaд вeличинoй  j мoжeт
305
Доклады Академии наук Республики Таджикистан
2016, том 59, №7-8
быть пoлyчeнo в peзyльтaтe мaшиннoгo экcпepимeнтa (имитaциoннoй мoдeли) либo в кaчecтвe  sj
мoжeт быть взят s -й элeмeнт из нaбopa cтaтиcтичecкиx нaблюдeний (дaнныx) oтнocитeльнo вeличин
 j в paзличныe пepиoды (гoды, мecяцы, дeкaды и т. п.).
2. Вычислим вектор  s - стохастического квазиградиента функции F ( x ) , компоненты которого, согласно (3), определяются следующим образом:

если х sj   sj , s  0,1,...,
 j ,
  cj  
s
s

   j , если х j   j , j  1,..., n.
s
j
(4)
Новое приближение находим согласно следующему варианту стохастического метода линеаризаци:
х sj 1  х sj   s ( x js  x sj ), 0<  s ≤ 1, z sj 1  z sj   s ( sj  z sj ),  s  0,
j  1, n , s  0,1,....
(5)
s
Здесь x j , j  1, n является решением (согласно алгоритму 1) следующей ЗЛП:
n
s
x j  arg min  z sj x j / X
 j 1
,
s  0,1,....,
где z sj , j  1, n , определяется согласно (5), для которого  js , j  1, n , вычисляется по (4).
Важной особенностью этого простого и легко реализуемого на компьютете алгоритма является тот факт, что направление «спуска» в них строится на основе случайного вектора стохастического

квазиградиента  s , который является несмещённой оценкой обобщённого градиента F x ( x s ) целевой
функции F ( x ). Другими словами, условное математическое ожидание, то есть

M ( s /  s )  F x ( x s ) .

Здесь вектор F x ( x s ) удовлетворяет неравенству


F ( x )  F x ( x s )   F x ( x s ), x  x s 


поскольку по определению квазиградиента


f ( x, )  f ( x s ,  s )  fˆx ( x s ,  s ), x  x s .
Следовательно, взяв математическое ожидание с обеих частей этого неравенства, получаем
квазиградиент функции F  x  для любых x.
306
Математика
Ф.Мирзоахмедов
Теорема. Пусть выполняются условия

 j s  d  ,  s  0,  s  0, s  0,1,..., ,   s  ,
s 0

s
 s 2  ,


0,

s
s
s 0
Тогда с вероятностью 1 предельные точки последовательности
х 
s 
j s 0


s 0
2
s
 .
, определяемой
(4),(5) принадлежат множеству X * решений задачи (1а),(2).
Доказательство теоремы и выбор параметров метода (5) подробно исследованы в [3].
В общем случае для вектора стохастического квазиградиента имеем:

M ( s /  s )  F x ( x s ) + b s ,
где b s – смещение, которое для сходимости изложенных методов должно в определённом смысле
стремиться к 0 при s  .
Peзyльтaт численного эксперимента. Опишем использование метода стохастической линеаризации (4),(5) для решения частного случая задачи (1а), (2) с дополнительными ограничениями типа
0  xi  di , i  1, 5 , когда затраты на производство не учитываются. Подпрограмма, реализующая
алгоритм 2, написана на языке VBA .
Пусть требуется минимизировать функцию
n
F ( x )  M  max i ( xi  i ); i i  xi   min
(1в)
i 1
при ограничениях
x1  x2  2 x3  3x4  x5  200,
0  x1  50; 0  x2  7; 0  x3  7; 0  x4  0; 0  x5  25 .
(2а)
Здесь  j – случайные величины, равномерно распределённые на отрезках [lj, qj], i = 1, ..., 5.
Beктopы
l   ll , ..., l5  ;
q  (q1,..., q5 );
  1, ..., 5  ;
   1, ..., 5  заданы в виде
l   0,0,0,0,0 ; q   60,15,17,90,40 ;   1,0,3,1,2  ;    3,4,1,2,3 .
При указанных значениях аналитическое выражение функции цели (1в) имеет вид:
1
2
2
1 2 1 2
F ( x )  x12  x22  x32 
x4  x5  3x1  4 x2  x3  2 x4  3x5  278.5 .
3
15
17
60
16
(1с)
Стохастический квазиградиент  s  (1s , ..., 5s ) функции (1в) вычисляется согласно (4) аналитически по формуле

если x sj   sj ,
 j ,
 
s
s

   j , если x j   j , i  1, 2, ..., 5.
s
i
307
Доклады Академии наук Республики Таджикистан
2016, том 59, №7-8
Для сравнения было получено следующее точное решение задачи (1с), (2а) одним из методов
квадратичного программирования [3]:
x* = (41.88057; 7.00000; 2.48092; 41.27456; 22.33456), F(х*) = 98.10089.
Для решения стохастической задачи (1в), (2а) используем алгоритм 2, для которого начальное
приближение
х0 = (10.59375; 0.59375; 5.18750; 58.78125; 2.09375),
шаговые множители  s и  s определялись cлeдyюιцим образом:  s  1 /  s  1 ,   1 /  s  1
2/3
.
Пpивeдём peзyльтaты ycpeднённыx знaчeний иcкoмыx пepeмeнных и функции на итepaцияx с
161-й по 170-ю:
x1 =41.24893; x2 =7.00000; x3 =2.22827; x4 = 42.2829; x5 =20.47934;
xi 
Лeгко
зaмeтить,
1 170 s
1 170
F
(
x
)

f ( x s ,  s )  103.8945.
x
;


i
10 s 164
10 s 164
что
знaчeниe
x  ( x1 , ..., x5 )
близко
к
oптимaльнoмy
решению
x*  ( x1* , ..., x5* ) детерминированной задачи (1с),(2а), а знaчeниe F ( x ) мaло oтличaeтcя от знaчeния
F  х*  .
Пoвышениe тoчнocти этoго решения требует yвeличeния кoличecтвa итepaций. При неточности априорной информации о пapaмeтpax задачи oтпaдaeт необходимocть в получении высокой
тoчнocти решения.
Поступило.04.05.2015 г.
Л И Т Е РАТ У РА
1. Мирзоахмедов Ф. Противоречивые модели линейного программирования в производственноэкономических системах. – Душанбе: ТГНУ, 2002, 240 с.
2. Ермольев Ю.М. Методы стохастического программирования. – М.: Наука,1976, 240 с.
3. Мирзоахмедов Ф. Математические модели и методы управления производством с учетом случайных факторов. – Киев: Наукова думка, 1991, 220 с.
308
Математика
Ф.Мирзоахмедов
Ф.Мирзоахмедов
МОНАНДИИ СТОХАСТИКИИ МАСЪАЛАИ ПРОГРАММАСОЗИИ ХАТТЇ
ДАР ЊОЛАТИ БА ШОХАЊО ЉУДОШАВЇ
Маркази рушди инноватсионии илм ва технологияњои нав
Академияи илмњои Љумњурии Тољикистон
Дар маќола алгоритми самараноки методи симплексї барои њалли масъалаи умумии
програмасозии хаттї оварда шудааст, ки вай дар навбати худ барои варианти стохастикии
масъала њам истифода бурда мешавад. Ба ѓайр аз ин теоремаи наздикшавии алгоритми њалли
масъалаи стохастикї дар њолати бифуркатсионї исбот карда шуда , бо варианти тестии масъала
тасдиќ карда мешавад.
Калимањои калидї: масъалањои детерминистї ва стохастикї,
квазиградиент, алгоритми њал, теоремаи наздикшавї, таљрибаи ададї.
ба
шохањо
људошавї,
F.Mirzoakhmedov
STOCHASTIC ANALOG LINEAR PROGRAMMING PROBLEMS WITH
BIFURCATION EFFECT
Center for Innovative Devolopment of Scince and New Technologies
Academy of Sciences of the Republic of Tajikistan
The article presents algorithms effective simplex method for solving the general problem of linear
programming, which also used in solving the stochastic version of the problem. We also prove the convergence of the algorithm for solving stochastic version problem with the bifurcation effect and proves to be
true of the test example.
Key words: deterministic and stochastic problem, kvazigradient algorithm solving, convergence theorem,
numerical experiment.
309
Документ
Категория
Без категории
Просмотров
4
Размер файла
593 Кб
Теги
эффектов, аналоги, стохастических, линейного, задачи, программирование, ветвление
1/--страниц
Пожаловаться на содержимое документа