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

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

РЕФЕРАТ

Пояснювальна записка: 25с., 3 мал., 3 джерел.

Об'єкт дослідження - задача стохастичного программування.

Мета роботи - вивчення теорії одноетапних задач стохастичного программування, методів розв'язання їх детермінованих аналогів, а такой створення діалогової систем розв'язання детермінованого аналога задачі М-типу з некорельованими коефіцієнтами построкових ймовірностних обмежень.

В курсовому проекті розглянута задача стохастичного програмування М-типу з некорельованими коефіцієнтами построкових ймовірностних обмежень, в середовищі Visual Studio створена діалогова система роз'язання детермінованого аналогу цієї задачі. Для розв'язання задачі квадратичного програмування використовується метод Келлі. Для розв'язання ЗЛП на кожній інтерації метода Келлі був запрогромований симплекс-метод.

СТОХАСТИЧНЕ ПРОГРАМУВАННЯ, МЕТОД КЕЛЛІ, СІМПЛЕКС МЕТОД.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

1.1 Общая характеристика задач стохастического программирования

1.2 Задача стохастического программирования с построчными вероятностными ограничениями

1.3 Метод Келли

2. ПРАКТИЧЕСКАЯ ЧАСТЬ

2.1 Алгоритм работы программы

2.2 Описание программного продукта

2.3 Особенности применения программного продукта

2.4 Тестирование программного продукта

2.5 Тестирование метода Келли

ВЫВОДЫ

ПЕРЕЧЕНЬ ССЫЛОК

ПРИЛОЖЕНИЕ

ВВЕДЕНИЕ

Роль стохастических моделей и методов в исследовании закономерностей поведения экономических систем и в разработке количественных методов планирования экономики и управления производством имеет два аспекта -- методологический и вычислительный.

Роль вычислительного аспекта проблемы определяется тем, что планирование, управление и проектирование происходят, как правило, в условиях неполной информации. Рыночная конъюнктура, спрос на продукцию, изменения в состоянии оборудования не могут быть точно предсказаны. В условиях конкурентной экономики дополнительно возникает направленная дезинформация.

Учет случайных факторов и неопределенности в планировании и управлении -- важная задача стохастического программирования.

Однако этим не исчерпывается роль стохастических методов в анализе систем. Принципы стохастического программирования дают основание для сопоставления затрат на накопление и хранение информации с достигаемым экономическим эффектом, позволяют аргументировать рациональное разделение задач между человеком и вычислительной машиной и служат теоретическим фундаментом для алгоритмизации управления сложными системами. Принципы стохастического программирования позволяют сблизить точные, но узко направленные формальные математические методы с широкими, но нечеткими содержательными эвристическими методами анализа. И здесь, таким образом, мы переходим к методологической роли стохастического программирования в исследовании сложных систем.

В данной курсовой работе рассматривается одна из задач стохастического программирования и численный метод ее решения.

1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

1.1 Общая характеристика задач стохастического программирования

В стохастическом программировании рассматриваются проблемы принятия решений в условиях действия случайных факторов, которые необходимо учитывать в соответствующих математических моделях.

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

стохастический модель программирование

(1.1)

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

, (1.2)

. (1.3)

Задачи стохастического программирования возникают в случаях, когда функции , зависят также от случайных параметров . При этом предполагается, что является элементом пространства состояний природы (или пространства случайных параметров) . Тогда задачу стохастического программирования можно сформулировать так [17;18]:

минимизировать

(1.4)

при условиях

 , (1.5)

Постановка задач стохастического программирования существенно зависит от того, есть ли возможность при выборе решений уточнить состояние природы путем некоторых наблюдений или нет. В связи с этим различают задачи оперативного и перспективного стохастического программирования.

В задачах оперативного стохастического программирования решение принимается после некоторого эксперимента над состоянием природы , оно зависит от результатов эксперимента и является случайным вектором . Такие задачи возникают, например, в оперативном планировании, медицинской диагностике. В задачах перспективного стохастического программирования решение x принимается до проведения каких-либо наблюдений над состоянием природы и поэтому является детерминированным. Такие задачи возникают в перспективном технико-экономическом планировании, в задачах проектирования, когда параметры системы должны быть выбраны конкретными детерминированными величинами, в расчете на определенный диапазон возможных возмущений.

Задачи стохастического программирования обычно задаются в одной из следующих форм:

минимизировать

(1.6)

при условиях

,(1.7)

где - операция математического ожидания;

минимизировать

(1.8)

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

, (1.9)

где - некоторые числа; - вероятность.

Возможные и некоторые комбинации задач (1.6), (1.7) и (1.8), (1.9).

Например, найти минимум (1.6) при условиях (1.9) или минимум (1.8) при условиях (1.7). Несмотря на кажущееся различие в постановках задач (1.6), (1.7) и (1.8), (1.9), они могут быть сведены к некоторой общей формулировке, например вида (1.6), (1.7). Для этого необходимо ввести характеристические функции:

(1.10)

(1.11)

для которых

Задача (1.8), (1.9) тогда приводится к виду

минимизировать

(1.12)

при условии

Существует два основных подхода к решению задач стохастического программирования:

1) непрямые методы, которые заключаются в нахождении функций , и решении эквивалентной задачи НП вида (1.6), (1.7);

2) прямые методы стохастического программирования, основанные на информации о значении функций , , получаемой в результате проведения экспериментов.

1.2 Задача стохастического программирования с построчными вероятностными ограничениями

Рассмотрим задачу СП М-типа следующего вида:

, (1.13)

.(1.14)

Пусть , , - нормально распределенные случайные величины, т.е.

, , .

Кроме того, элементы -ой строки матрицы и вектора коррелированны между собой. Пусть, кроме того, .

Теорема 1.1. При сделанных предположениях задача СП (1.13) - (1.14) эквивалентна детерминированной задаче выпуклого программирования с линейной целевой функцией и квадратичными ограничениями.

Доказательство. Рассмотрим целевую функцию задачи (1.13) - (1.14)

, где .

Рассмотрим невязку -го условия (1.14)

.

Так как является линейной функцией от нормально распределенных аргументов , , значение в линейной форме рассматривается как константа, и, следовательно, сама функция является нормально распределенной случайной величиной, т.е.

.

Определим параметры нормального распределения , . Математическое ожидание равно

где , .

Вычислим дисперсию

,

где - центрированная случайная величина. Для вычисления представим , в виде скалярного произведения -ой строки матрицы и вектора , т.е.

, .

Тогда

,

,

,

где , - центрированные случайные величины.

(1.15)

Рассмотрим каждую из составляющих выражения (1.15)

,

где - коэффициент корреляции между -м и -м случайными элементами -й строки матрицы .

где - коэффициент корреляции между элементами и .

,

.

Неравенство (1.14) представим теперь в виде:

,

,

.

Таким образом, детерминированный аналог задачи (1.13) - (1.14) имеет вид:

, (1.16)

(1.17)

Пусть в задаче (1.13) - (1.14) элементы матрицы и вектора ограничений (1.14) являются некоррелированными случайными величинами. Тогда детерминированный эквивалент задачи (1.13) - (1.14) примет вид:

, (1.18)

(1.19)

где - дисперсия величин .

Эта задача является задачей нелинейного программирования. Для ее решения может быть использован метод Келли.

1.3 Метод Келли

Метод Келли (метод секущих плоскостей) является прямым и используется для решения задач выпуклого программирования вида:

Здесь - выпуклые функции и .

Вводя дополнительные переменную и ограничение, сделаем функционал задачи линейным:

,

Без ограничения общности считаем, что и ограничимся изучением выпуклых задач вида:

при условии, что

Также считаем, что в задаче существует оптимальное решение , которое содержится в многогранном множестве , а также .

Алгоритм метода Келли.

Итерация k.

- Шаг 1.

Решаем задачу линейного программирования

, ,

где - текущее многогранное приближение множества , причем .

Пусть - оптимальное решение этой задачи. Если , то будем считать допустимым решением исходной задачи. Алгоритм заканчивает работу. В противном случае переходим к следующему шагу.

- Шаг 2.

Найдем номер ограничения , для которого величина максимальна. Перейдем к выполнению следующей итерации с

.

Корректность определения множества .

Так как ограничение линейно, то множество является многогранным.

В силу выпуклости множества и функции имеем:

Но для выполняется . Следовательно, . Другими словами, ограничение

является отсечением, которое отсекает точку .

Если алгоритм останавливается через конечное число шагов, то текущее приближение оптимальное решение задачи. Рассмотрим случай, когда последовательность бесконечна.

Теорема.

Любая предельная точка последовательности , порожденная методом секущих плоскостей, есть оптимальное решение задачи.

Доказательство.

Последовательность значений монотонно неубывающая и ограничена сверху (так как существует оптимальное решение). Поэтому без ограничения общности считаем, что последовательность ограничена. Значит, найдется сходящаяся подпоследовательность. Для упрощения обозначений, читаем, что это и есть наша последовательность . Пусть - ее предел.

Выберем произвольное ограничение с номером . Рассмотрим подпоследовательность элементов , где , для которых секущая плоскость порождалась с помощью -го ограничения. Возможны два случая.

1. Найдется номер такой, что . Тогда

2. Подпоследовательность бесконечна. Тогда

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

Так как , то

Таким образом

Следовательно, в силу произвольного выбора , - допустимое решение задачи.

Но

То есть - оптимальное решение задачи.

2. ПРАКТИЧЕСКАЯ ЧАСТЬ

2.1 Алгоритм работы программы

В ходе курсовой работы разработана программа для решения задач вида:

(2.1)

(2.2)

где - независимые между собой случайные величины.

Детерминированный аналог данной задачи

, (2.3)

(2.4)

Он представляет собой задачу выпуклого программирования, который будем решать методом Келли.

Алгоритм метода Келли

Итерация k.

- Шаг 1.

Решаем задачу ЛП

,

где ,

- текущее многогранное приближение множества , причем .

Эту задачу линейного программирования будем решать симплекс-методом.

Пусть - оптимальное решение этой задачи. Если

,

то будем считать допустимым решением исходной задачи. Алгоритм заканчивает работу.

В противном случае переходим к следующему шагу.

- Шаг 2.

Найдем номер ограничения , для которого величина

максимальна. Перейдем к выполнению следующей итерации с

,

где ,

В результате мы получим решение детерминированого аналога задачи, которое и является решением исходной задачи.

2.2 Описание программного продукта

Был разработан программный продукт, позволяющий решать задачу стохастического программирования. Он представляет собой диалоговое приложение Windows, написаное на C#.

Для того, чтобы произвести расчет необходимо заполнить коэффициенты задачи или загрузить их из файла, клацнув «Загрузить задачу» (рис. 2.1).

Рисунок 2.1 Форма заполнения коэффициентов задачи

Далее мы можем получить график целевой функции и неравенств ограничения детерминированного аналога задачи нажав на клавишу «Нарисовать график». Для того чтобы решить эту задачу методом Келли необходимо выбрать координату правого верхнего угла прямоугольника, который представляет собой область с ограничениями задачи внутри, выбрать точность и нажать «Расчет». На рисунке 2.2 показаны результаты работы данной программы.

Рисунок 2.2

Результаты работы программы

В программе есть возможность сохранить условия задачи в файл. Для этого необходимо нажать клавишу „Сохранить задачу”.

2.3 Особенности применения программного продукта

Данный программный продукт позволяет решать задачи стохастического программирования М-типа с коррелироваными некоефициентами построчных вероятностных ограничений размерности 2x2. Точность решения зависит от выбраного в методе Келли.

2.4 Тестирование программного продукта

Задача 1. Решить задачу (2.1) - (2.2), если известно:

- независимые между собой случайные величины.

В методических указаниях [2] дается решение данной задачи.

Для решения данной задачи с помощью полученой программы найдем значение , где , - функция Лапласа, значения которой протабулированы. В результате получим , которые вписываем в диалоговую форму программы. В результате мы получаем решение, которое представлено на рисунке 2.2. Им является вектор . Значение целевой функции в этой точке .

Абсолютная погрешность (при выбраном в методе Келли ) составляет . Следовательно относительная погрешность вычислений равняется .

Задача 2. Решить задачу (2.1) - (2.2), если известно:

- независимые между собой случайные величины.

В методических указаниях [2] приводится данный пример. Его точное решение

Для решения данной задачи с помощью полученой программы аналогично найдем значение . В результате вычислений получим результат, которой представлено на рисунке 2.3. Им является вектор . Значение целевой функции в этой точке .



Рисунок 2.3

Результаты вычислений задачи 2

Абсолютная погрешность (при выбраном в методе Келли ) составляет . Следовательно относительная погрешность вычислений равняется .

2.5 Тестирование метода Келли

Задача №1.

Данная задача взята из источника [2]. Ее точное решение .

Была выбрана начальная точка . На рисунке 2.4 показаны итерации метода Келли решения данной задачи.

Рисунок 2.4

Результаты вычислений задачи 1

Таким образом, было получено приближенное решение за 3 итерации.

Задача №2.

(2.5)

Данная задача взята из курса лабораторных работ по стохастическому программированию. Ее точное решение .

Исходный код метода Келли, который используется в данной программе приводится в приложении 1. Он решает частный случай нахождения максимума линейной целевой функции. Следовательно задачу (2.5) представим ввиде:

(2.6)

Была выбрана начальная точка . На рисунке 2.5 показаны итерации метода Келли решения задачи 2.6.



Рисунок 2.5

Результаты вычислений задачи 2

Таким образом, было получено приближенное решение за 30 итераций.

ВЫВОДЫ

В ходе выполнения данной курсовой работы была рассмотрены построение детерминированных аналогов задач стохастического программирования с построчными вероятностными ограничениями, рассмотрен метод Келли для решения полученной задачи квадратичного программирования. Для решения задачи линейного программирования был использован метод Келли. Также была разработана диалоговая система решения задач стохастического программирования М-типа с некоррелированными коэффициентами построчных вероятностных ограничений.

ПЕРЕЧЕНЬ ССЫЛОК

1) Зайченко Ю.П. Исследование операций.- Киев:Вища школа, 1975.

2) Тевяшев А.Д., Задачин В.М. Методические указания к практическим занятиям по спецкурсу «Стохастическое программирование»:-Х:ХИРЭ, 1989.

3) Юдин Д.Б. Математические методы управления в условиях неполной информации: - «Советское радио», 1974.

ПРИЛОЖЕНИЕ

using System;

using System.Collections.Generic;

using System.Text;

namespace StoxProg

{

public delegate double limitation(double[] x);

public class IterationEventArgs : EventArgs

{

double[] _x;

public double[] X

{

get { return _x; }

set { _x = value; }

}

public IterationEventArgs(double[]x)

{

int n = x.Length;

_x = new double[n];

for (int i = 0; i < n; i++){

_x[i] = x[i];

}

}

}

 public class Kelli

{

public event EventHandler<IterationEventArgs> Iterate;

#region Fields

private double[] _objectCoefficients;

private List<double[]> _A = new List<double[]>();

private List<double> _b = new List<double>();

private limitation[] _limitations;

private limitation[,] _diffLims;

private double _eps = 0.0001;

#endregion

#region .ctor

public Kelli(double[] objectCoef,

List<double[]> mA,

List<double> vb,

limitation[] lims,

limitation[,] diffLims)

{

_objectCoefficients = objectCoef;

_A = mA; _b = vb;

_limitations = lims;

_diffLims = diffLims;

}

#endregion

#region Properties

public double Eps {

get { return _eps; }

set { _eps = value; }

}

protected double[,] A

{

get

{

double[,] res = new double[_A.Count, _A[0].Length];

for (int i = 0; i < _A[0].Length; i++)

{

for (int j = 0; j < _A.Count; j++)

{

res[j, i] = _A[j][i];

}

}

return res;

}

}

protected double[] b

{

get{return _b.ToArray();}

}

#endregion

public double[] Maximize(double[] x0)

{

int n = x0.Length;

double[] residual = new double[_limitations.Length];

double[] opt = new double[n];

for (int i = 0; i < n; i++) {

opt[i] = x0[i];

}

while (true)

{

opt = LP.Maximize(A, b, _objectCoefficients);

if (Iterate != null)

{

Iterate(this, new IterationEventArgs(opt));

}

double max

= residual[0]

= _limitations[0](opt);

int maxIdx = 0;

for (int i = 1; i < residual.Length; i++){

residual[i] = _limitations[i](opt);

if (residual[i] > max) {

max = residual[i];

maxIdx = i;

}

}

if (max < Eps) {

if (Iterate != null) {

Iterate(this, new IterationEventArgs(opt));

}

return opt;

}

Linearize(maxIdx, opt);

}

return opt;

}

private void Linearize(int p, double[] x)

{

int n = x.Length;

double b = - _limitations[p](x);

for (int i = 0; i < n; i++) {

b += x[i] * _diffLims[p, i](x);

}

double[] a = new double[n];

for (int i = 0; i < n; i++){

a[i] = _diffLims[p, i](x);

}

_A.Add(a);

_b.Add(b);

}

}

}

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