О применении r-алгоритма для решения одного класса задач стохастического программирования

О применении r-алгоритма для решения одного класса задач стохастического программирования

The paper investigates the efficiency of r-algorithms used to solve stochastic problems with a simple recourse and a random technology matrix of second-stage constraints. The computational results are given for the case, when the SLP-IOR package is used.

Gespeichert in:
Bibliographische Detailangaben
Datum:2005
1. Verfasser: Лиховид, А.П.
Format: Artikel
Sprache:Russian
Veröffentlicht: Інститут кібернетики ім. В.М. Глушкова НАН України 2005
Schriftenreihe:Теорія оптимальних рішень
Online Zugang:https://nasplib.isofts.kiev.ua/handle/123456789/84918
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:О применении r-алгоритма для решения одного класса задач стохастического программирования / А.П. Лиховид // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 3-8. — Бібліогр.: 5 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-84918
record_format dspace
spelling nasplib_isofts_kiev_ua-123456789-849182025-02-09T14:39:25Z О применении r-алгоритма для решения одного класса задач стохастического программирования Using the r-algorithm to solve one stochastic problem class Лиховид, А.П. The paper investigates the efficiency of r-algorithms used to solve stochastic problems with a simple recourse and a random technology matrix of second-stage constraints. The computational results are given for the case, when the SLP-IOR package is used. 2005 Article О применении r-алгоритма для решения одного класса задач стохастического программирования / А.П. Лиховид // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 3-8. — Бібліогр.: 5 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/84918 519.8 ru Теорія оптимальних рішень application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
language Russian
description The paper investigates the efficiency of r-algorithms used to solve stochastic problems with a simple recourse and a random technology matrix of second-stage constraints. The computational results are given for the case, when the SLP-IOR package is used.
format Article
author Лиховид, А.П.
spellingShingle Лиховид, А.П.
О применении r-алгоритма для решения одного класса задач стохастического программирования
Теорія оптимальних рішень
author_facet Лиховид, А.П.
author_sort Лиховид, А.П.
title О применении r-алгоритма для решения одного класса задач стохастического программирования
title_short О применении r-алгоритма для решения одного класса задач стохастического программирования
title_full О применении r-алгоритма для решения одного класса задач стохастического программирования
title_fullStr О применении r-алгоритма для решения одного класса задач стохастического программирования
title_full_unstemmed О применении r-алгоритма для решения одного класса задач стохастического программирования
title_sort о применении r-алгоритма для решения одного класса задач стохастического программирования
publisher Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate 2005
url https://nasplib.isofts.kiev.ua/handle/123456789/84918
citation_txt О применении r-алгоритма для решения одного класса задач стохастического программирования / А.П. Лиховид // Теорія оптимальних рішень: Зб. наук. пр. — 2005. — № 4. — С. 3-8. — Бібліогр.: 5 назв. — рос.
series Теорія оптимальних рішень
work_keys_str_mv AT lihovidap oprimeneniiralgoritmadlârešeniâodnogoklassazadačstohastičeskogoprogrammirovaniâ
AT lihovidap usingtheralgorithmtosolveonestochasticproblemclass
first_indexed 2025-11-26T23:31:00Z
last_indexed 2025-11-26T23:31:00Z
_version_ 1849897634318254080
fulltext Теорія оптимальних рішень. 2005, № 4 3 ÒÅÎÐ²ß ÎÏÒÈÌÀËÜÍÈÕ Ð²ØÅÍÜ Рассматривается исследование эффективности применения r- алгоритмов для решения стохас- тических задач с простой рекур- сией и случайной технологической матрицей ограничений второго этапа. Приведены результаты сравнительных вычислительных экспериментов с использованием пакета SLP-IOR.  А.П. Лиховид, 2005 ÓÄÊ 519.8 À.Ï. ËÈÕÎÂÈÄ Î ÏÐÈÌÅÍÅÍÈÈ R-ÀËÃÎÐÈÒÌÀ ÄËß ÐÅØÅÍÈß ÎÄÍÎÃÎ ÊËÀÑÑÀ ÇÀÄÀ× ÑÒÎÕÀÑÒÈ×ÅÑÊÎÃÎ ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈß Введение. Хорошо известным специальным видом двухэтапной стохастической задачи является модель с простой рекурсией [1]. Но эффективные алгоритмы решения и вычис- лительные результаты касались только мо- делей, когда вектор правых частей ограниче- ний второго этапа был случайным [2]. В ра- боте [3] был предложен подход к решению задач для случайной технологической мат- рицы ограничений второго этапа с примене- нием r-алгоритмов [4]. В предлагаемой ра- боте, которая является продолжением рабо- ты [3], представлены результаты вычисли- тельных экспериментов эффективности при- менения r-алгоритмов для решения задач такого класса. Рассмотрим следующую по- становку задачи: )],([min xQcx x + .Xx ∈ (1) Здесь }:{ bAxRxX n ≤∈= + – детерминиро- ванные ограничения, ограничения на неот- рицательность для переменных первого эта- па; ](([)( ))ω(Τ−)ω= ω xhvExQ является функцией ожидаемых затрат, где ω – слу- чайный вектор, )(zv – целевая функция для задачи второго этапа: ,, ],[min m y Rzzyy yqyq ∈=− + −+ −−++ ., mm RyRy + − + + ∈∈ (2) А.П. ЛИХОВИД 4 Теорія оптимальних рішень. 2005, № 4 Предположим, что m,,i,qq ii K10 =≥+ −+ , откуда функция v является ограни- ченной и выпуклой [2]. Обозначим отклонения IihxTx iii ∈ω−ω=ωη ),()(),( . Для каждого инди- видуального отклонения штрафы + iq и − iq назначаются, соответственно, за из- лишки )},(,0max{),( ωη=ωη + xx ii и дефицит )},(,0max{),( ωη−=ωη − xx ii . Целе- вую функцию можно представить в виде ( ) .),(),(         ωη+ωη+ ∑ ∈ −−++ ω Ii iiii xqxqEcx (3) Воспользуемся сепарабельностью функции ожидаемых затрат Q . Пусть iω обозначает компоненты вектора ω , от которых фактически зависят )(ωiT и )ω(ih . Тогда ))(),(()((( iiiiii hThT ωω=)ω),ω , mi ,...,1= , а функция Q может быть записана в виде ∑ = = m i i xQxQ 1 ),()( (4) где ],))()([(]))()([()( − ω −+ ω + ω−ω+ω−ω= xThEqxThEqxQ iiiiiiiiiii ii mi ,,1 K= . Здесь математическое ожидание берется относительно распределения iω . Учитывая, что zzz =− −+ )()( , и, используя ранее введенное обозначение )()(),( iiiiii hxTx ω−ω=ωη , получаем следующее выражение: =ωη+ωη= + ω −− ω + ]),([]),([)( iiiiiii xEqxEqxQ ii ],),([()()( − ω −+− ωη++−= iiiiiii xEqqhxtq i (5) где )]([ iii TEt i ω= ω , )]([ iii hEh i ω= ω . Предположим, что ω , следовательно, и iω имеют дискретное распределе- ние s i s ii p=ω=ω }Pr{ , iSs ∈ . В этом случае получаем: ,)},(,0max{]),([ ∑ ∈ − ω ωη−=ωη i i Ss s i s i xpxE =ωη+ωη= + ω −− ω + ]),([]),([)( iiiiiii xEqxEqxQ ii .)},(,0max{)()( ∑ ∈ −+− ωη−++−= iSs s i s iiiii xpqqhxtq (6) Для учета ограничений первого этапа Xx ∈ можно использовать, например метод негладких штрафных функций [4]. Тогда, чтобы решить задачу (1) для О ПРИМЕНЕНИИ R-АЛГОРИТМА ДЛЯ РЕШЕНИЯ ОДНОГО КЛАССА ЗАДАЧ … Теорія оптимальних рішень. 2005, № 4 5 случая дискретного распределения, можно применить алгоритмы субградиент- ного типа. Предлагаем в этом случае воспользоваться r-алгоритмами [4]. Есть несколько преимуществ в использовании данного подхода. 1. Исходя из сепарабельности функции Q , можно рассмотреть только ∑ = m i iS 1 подзадач второго этапа вместо 1 m i i S = ∏ (при условии, что строки являются неза- висимыми), чтобы вычислить значение Q и субградиент для каждого текущего решения kx . 2. Вместо решения каждой подзадачи второго этапа как задачи линейного программирования можно использовать аналитические формулы для вычисле- ния )( kxQ и субградиента целевой функции в точке kx . Для проверки предлагаемого алгоритма была разработана программа SIMPLE_T на языке программирования C++. Вычислительные эксперименты проводились с использованием известной системы моделирования для задач стохастического программирования SLP-IOR [2]. Специализированных про- грамм для задач с простой рекурсией и случайной технологической матрицей второго этапа, с которыми можно было бы сравнить результаты, в распоряже- нии не было, поэтому было проведено сравнение времени решения с програм- мой для задач с фиксированной рекурсией DAPPROX v1.0 (Kall & Mayer, 2001) из пакета SLP-IOR, которая имела среди всех программ, входящих в этот пакет, лучшее быстродействие. Характеристики компьютера, на котором проводились исследования: − компьютер IBM PC; − процессор CPU Pentium 750MHz; − оперативная память 256MB; − операционная система Windows 98. Предлагаемый алгоритм был проверен на разнообразных тестовых задачах. Они представляют собой задачи линейного стохастического программирования с простой рекурсией и случайной технологической матрицей (правыми частями ограничений) второго этапа. Тестовые задачи генерировались с помощью средств системы моделирования SLP-IOR. Каждый пример refineD5–refineD20 генерировался на основе задачи REFINE из [1] с помощью аппроксимации всех непрерывных распределений исходной задачи дискретными распределениями с количеством реализаций соответственно равными 0}{5,10,15,2=k . При этом общее число реализаций для каждого примера, которые просматривала про- грамма DAPPROX, равнялось 6 k , а число реализаций, которые учитывались программой SIMPLE_T, равнялось 3 k . Аналогично примеры mixD2–mixD12_5 А.П. ЛИХОВИД 6 Теорія оптимальних рішень. 2005, № 4 генерировались на основе задачи Product Mix из [5], при этом для примеров mixD12_2 и mixD12_5 число случайных параметров равнялось 12, количество дискретных реализаций 2 и 5 соответственно, для остальных примеров из этой группы число случайных параметров равнялось 10, количество реализаций для дискретных аппроксимаций было соответственно {2,3,4,13}=k . Параметры r-алгоритма для решения тестовых задач были выбраны сле- дующими: 2=α – коэффициент растяжения пространства; 6 1 10− + ≤− kk xx – точность при завершении по аргументу ( k – номер итерации); 10=h – величи- на начального шага . Параметры программы DAPPROX взяты по умолчанию. В табл. 1 приведены параметры этих тестовых задач. ТАБЛИЦА 1 Тестовая задача m1 n1 m2 n2 NRand iS Nrealiz MixD2 1 4 2 4 10 52 102 MixD3 1 4 2 4 10 53 103 MixD4 1 4 2 4 10 54 104 MixD13 1 4 2 4 10 513 1013 refine5 1 2 2 4 6 35 65 refine10 1 2 2 4 6 310 610 refine15 1 2 2 4 6 315 615 refine20 1 2 2 4 6 320 620 mixD12_2 1 5 2 4 12 62 122 mixD12_5 1 5 2 4 12 65 125 Здесь m1 – число ограничений первого этапа; n1 – число переменных первого этапа; m2 – число ограничений второго этапа; n2 – число переменных второго этапа; iS – число случайных реализаций для i-го ограничения второго этапа; Nrand – число случайных параметров; Nrealiz – общее число случайных реализаций. В табл. 2 представлено время решения для некоторых тестовых задач, в табл. 3 приведены значения функционала при завершении выполнения соответ- ствующей программы. Здесь введены следующие обозначения: * – остановка программы из-за недостатка памяти; F – задача не была решена. О ПРИМЕНЕНИИ R-АЛГОРИТМА ДЛЯ РЕШЕНИЯ ОДНОГО КЛАССА ЗАДАЧ … Теорія оптимальних рішень. 2005, № 4 7 ТАБЛИЦА 2 МОДЕЛИ Время решения для задач с простой рекурсией (сек.) SIMPLE_T DAPPROX mixD2 0.02 0.84 mixD3 0.03 2.3 mixD4 0.09 3.24 mixD13 24.09 28.1 refine15 0.26 173.46* refine5 0.01 3.74 refine10 0.08 49.03 refine20 0.6 537.94* mixD12_2 0.11 F mixD12_5 2.193 F ТАБЛИЦА 3 МОДЕЛИ Значение функционала при завершении SIMPLE_T DAPPROX mixD2 -22026.32 -22026.325 mixD3 -17857.756 -17857.756 mixD4 -27153.412 -27153.411 mixD13 -18018.69 -18018.698 refine15 115.877 115.876* refine5 111.65 111.65 refine10 115.063 115.06 refine20 116.175 116.17* mixD12_2 1363.82 F mixD12_5 170.33 F Заключение. Все тестовые задачи были успешно решены программой SIMPLE_T, реализующей предложенный алгоритм. Отметим, что программа SIMPLE_T эффективно справлялась с примерами mixD12_2 и mixD12_5, кото- рые превышали возможности программы DAPPROX. Полученные результаты показывают на данных тестовых примерах, что специализированная программа, учитывающая сепарабельность модели, является более эффективным средством для решения данного класса задач стохастического программирования, чем су- ществующие программы, предназначенные для решения задач с фиксированной рекурсией. А.П. ЛИХОВИД 8 Теорія оптимальних рішень. 2005, № 4 О.П. Лиховид ПРО ВИКОРИСТАННЯ R-АЛГОРИТМУ ДЛЯ РІШЕННЯ ОДНОГО КЛАСУ ЗАДАЧ СТОХАСТИЧНОГО ПРОГРАМУВАННЯ Розглядається дослідження ефективності використання r-алгоритмів для рішення стохастич- них задач з простою рекурсією та випадковою технологічною матрицею обмежень другого етапу. Приведені результати обчислювальних експериментів з використанням пакету SLP- IOR. А.P. Likhovid USING THE R-ALGORITHM TO SOLVE ONE STOCHASTIC PROBLEM CLASS The paper investigates the efficiency of r-algorithms used to solve stochastic problems with a sim- ple recourse and a random technology matrix of second-stage constraints. The computational results are given for the case, when the SLP-IOR package is used. 1. Kall P., Wallace S.W. Stochastic programming. – London: John Wiley and Sons, 1994. – 225 p. 2. Mayer J. Stochastic Linear Programming Algorithms: A Comparison Based on a Model Manegement System. – Amsterdam: ODP, 1998. – 153 p. 3. Лиховид А.П. О реализации алгоритма решения одного класса двухэтапных задач с простой рекурсией // Теория оптимальных решений. – Киев: Ин-т кибернетики им. В.М. Глушкова НАН Украины. – 2001. – С. 3–9. 4. Shor N.Z. Nondifferentiable Optimization and Polynomial Problems. – Boston Dordrecht. – London: Kluwer Academic Publishers, 1998. – 412 p. 5. King A.J. Stochastic programming problems: examples from the literature. In Yu. Ermoliev and R.J-B. Wets, editors, Numerical techniques for stochastic optimization. Springer- Verlag, Berlin, 1988. – 30, P. 543–567. Получено 25.03.2005

Ähnliche Einträge