Программа решения задач стохастического программирования с построчными вероятностными ограничениями
Задача стохастического программирования: их общая характеристика, особенности методов решения (с построчными вероятностными ограничениями и Келли). Описание алгоритма работы программы. Программный продукт: описание, специфика применения, тестирование.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 08.11.2009 |
| Размер файла | 913,9 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
СОДЕРЖАНИЕ
Введение
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 показаны итерации метода Келли решения данной задачи.
Таким образом, было получено приближенное решение за 3 итерации.
Рисунок 2.4 - Результаты вычислений задачи 1
Задача №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);
}
}
}
Подобные документы
Особенности решения задач нелинейного программирования различными методами для проведения анализа поведения этих методов на выбранных математических моделях нелинейного программирования. Общая характеристика классических и числовых методов решения.
дипломная работа [2,4 M], добавлен 20.01.2013Основные принципы разработки программ. Разработка алгоритма решения задачи о пересечении двухвыпуклым многоугольником. Реализация разработанного алгоритма на языке программирования. Тесты для проверки работы программы. Графическая иллюстрация решения.
курсовая работа [53,3 K], добавлен 20.11.2015Понятие о стохастическом программировании, М-постановка и Р-постановка целевой функции. Описание этапов решения задач стохастического программирования: предварительный, оперативный анализ стохастической модели, переход к детерминированному эквиваленту.
курсовая работа [63,2 K], добавлен 15.06.2010Особенности задач линейного программирования. Симплексный метод решения задач линейного программирования. Обоснование выбора языка, инструментария программирования, перечень идентификаторов и блок-схема алгоритма. Логическая схема работы программы.
дипломная работа [2,4 M], добавлен 13.08.2011Транспортная задача как одна из самых распространенных специальных задач линейного программирования: понятие, основное назначение. Формальное описание метода минимального элемента. Характеристика этапов разработки алгоритма решения поставленной задачи.
курсовая работа [713,3 K], добавлен 19.10.2012Анализ метода линейного программирования для решения оптимизационных управленческих задач. Графический метод решения задачи линейного программирования. Проверка оптимального решения в среде MS Excel с использованием программной надстройки "Поиск решения".
курсовая работа [2,2 M], добавлен 29.05.2015Характеристика параметрических методов решения задач линейного программирования: методы внутренней и внешней точки, комбинированные методы. Алгоритм метода барьерных поверхностей и штрафных функций, применяемых для решения задач большой размерности.
контрольная работа [59,8 K], добавлен 30.10.2014Разработана программа решения двух задач на языке программирования Turbo Pascal. Спецификация задания. Описание входных и выходных данных. Математическая постановка задачи. Алгоритм ее решения. Описание и блок-схема программы. Результаты тестирования.
курсовая работа [275,8 K], добавлен 28.06.2008Характеристика этапов решения задач на электронных вычислительных системах. Разработка алгоритма и основы программирования. Язык Ассемблера, предназначенный для представления в удобочитаемой символической форме программ, записанных на машинном языке.
контрольная работа [60,5 K], добавлен 06.02.2011Приобретение теоретических и практических навыков программирования на языке Паскаль. Математическая формулировка задачи и выбор метода обработки информации. Разработка алгоритма и его описание. Описание программы. Форма представления исходных данных.
курсовая работа [224,3 K], добавлен 11.02.2016
