ЛАБОРАТОРНАЯ РАБОТА №4.
Решение оптимизационных задач при случайной исходной информации
Цель работы: Получение навыков составления математических моделей для решения задач линейного программирования в пакете MS Excelпри случайной исходной информации. Приобретение навыков решения оптимизационных задач при случайной исходной информации.
Краткие теоретические сведения.
B.1. Основные понятия
В предыдущих главах рассматривалось решение оптимизационных задач, в которых вся исходная информация была однозначно определена. Такая информация называется детерминированной. Примером детерминированной исходной информации могут служить однозначные значения коэффициентов z i, a ij и b j (i =1, 2,… n; j =1, 2,… m) в линейной математической модели (2.1). В практических задачах далеко не всегда исходная информация бывает детерминированной.
Достаточно часто исходная информация или ее часть представляют собой случайные величины или случайные функции. В частности, мощности нагрузок в проектируемой системе электроснабжения можно считать случайными величинами, а изменения во времени напряжений в узлах существующей системы электроснабжения – случайными функциями. Для решения оптимизационных задач со случайной исходной информацией используются методы стохастического программирования.
Известно, что случайными величинами занимается раздел высшей математики – теория вероятностей. Поэтому прежде чем перейти к методам решения оптимизационных задач вспомним некоторые понятия этой теории.
Случайной величиной s называется такая величина, которая может принять то или иное значение, причем заранее неизвестно, какое именно.
Случайная величина s может быть непрерывной или дискретной. В заданном диапазоне изменения случайной величины количество значений дискретной случайной величины ограничено, а количество значений непрерывной случайной величины не ограничено. Примером непрерывной случайной величины является величина напряжения в некотором узле системы электроснабжения. Примером дискретной случайной величины является количество генераторов, одновременно работающих в энергосистеме.
Математическим ожиданием случайной величины называется ее среднее значение, полученное в результате n реализаций:
где s i – значение случайной величины в i -й реализации.
Среднеквадратичное (стандартное) отклонение определяет разброс значений случайной величины относительно ее математического ожидания:
Важной характеристикой случайной величины служит вероятность Р появления этой случайной величины в конкретном интервале значений.
Для количественной оценки вероятности случайной величины вводится функция распределения вероятности. Допустим, что случайная величина s может принимать значения от -∞ до +∞. Функция распределения Р(s) этой случайной величины показывает вероятность того, что случайная величина попадет в интервал от -∞ до s. Следовательно,
Р (-∞) = 0, Р (+∞) = 1.
Наибольшее распространение на практике получил нормальный закон распределения. В соответствии с этим законом с вероятностью 0,999 случайная величина s (-∞ < s < +∞) находится в интервале
М [ s ] - 3σ[ s ] < s < M [ s ] + 3σ[ s ],
что и принимается за действительные пределы изменения случайной величины s.
При решении практических задач достаточно часто применяют нормальный стандартный закон распределения. Этот закон описывает вероятность появления стандартной случайной величины η, имеющей математическое ожидание М [η]=0 и среднеквадратичное отклонение σ[η]=1, в интервале -3 < η < 3 (рис. 1).
Рис. 1. Функция распределения нормального стандартного закона
С помощью этого графика решаются две обратные друг другу задачи. С одной стороны, определяется, каково должно быть значение случайной величины η, чтобы вероятность ее появления составила, например Р (η)=0,8. Это значение случайной величины составляет η < 0,84. С другой стороны, определяется вероятность появления случайной величины η, не превышающей, например значения 0,84 (η < 0,84). Эта вероятность составляет Р (η)=0,8.
В Excel эти два вычисления выполняются с помощью статистических функций НОРМСТОБР(0,8)=0,84 и НОРМСТРАСП(0,84) = 0,8 после обращения к мастеру функций f x в главном меню.
От функции распределения нормального стандартного закона можно перейти к функции распределения нормального закона любой случайной величины s оптимизационной задачи.
Связь между этой случайной величиной s и и стандартной случайной величиной η выражается зависимостью
s = М [ s ] + ησ[ s ]. (1)
Математические модели стохастических задач
Следует иметь в виду, что универсальных методов решения задач стохастического программирования, пригодных для всех классов оптимизационных задач, нет. Поэтому ограничимся рассмотрением математических моделей только одного класса стохастических задач, а именно, стохастических задач линейного программирования.
Напомним, что математическая модель задачи линейного программирования, включающая в себя целевую функцию, ограничения и граничные условия, имеет следующий вид:
Z = z 1 x 1 +z2x2+...+znxn → extr,
a 11 x 1 +a 12 x 2 +...+a 1n xn < b 1,
a 21 x 1 +a 22 x 2 +...+a2nxn = b 2,
.....................
a m1 x 1 +am2x2+...+amnxn > bm,
d i < х i < D i, i = 1, 2, ... n,
В детерминированной постановке оптимизационной задачи коэффициенты z i, a ji и b j (i =1,2,… n; j =1,2,… m) и границы d i и D i диапазона изменения переменных однозначно определены.
Если коэффициенты z i целевой функции являются случайными величинами, ищется экстремальное значение математического ожидания целевой функции
М [ Z ] → extr;
Если коэффициенты a ij и (или) b j системы ограничений являются случайными величинами, то для каждого j -го ограничения задается значение вероятности Р зад j, с которой должно выполняться это ограничение. Вероятность выполнения каждого j -го ограничения должна быть не меньше заданной
P (a j1 x 1 +aj2x2+...+ajnxn < bj) > Р зад j, j =1, 2,… m.
Граничные условия в практических оптимизационных задачах, как правило, не содержат случайных величин и записываются без изменения.
Итак, математическая модель задачи стохастического программирования имеет следующий вид:
М [ Z ] → extr;
P (a j1 x 1 +aj2x2+...+ajnxn < bj) > Р зад j, j =1, 2, … m; (2)
d i < х i < D i, i = 1, 2, ... n.