Общая постановка задачи оптимизации.

Общая постановка задачи оптимизации.

Линейное программирование. Постановка задачи математического программирования начинается с определения цели(целевая функция)

F(x)=f(x)->opt(i) (max, min)

Для нахождения решения задачи необходимо определить переменные задачи x = (x1,x2,…,xn)ограничения накладываемые на них. Эти ограничения представляют систему:

g (x) <0

g(x)>0

g(x)=0

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

Классификация:

Если функция цели:

1. Линейная функция gi(x) также линейные функции, то модель называется моделью лин. программирования

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

3. Если переменные задачи xi, являются переменные зависящими от времени, то модель называется моделью динамического программирования.

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

Пусть функция f определена в некоторой области G общая постановка задачи оптимизации. - student2.ru R и точкаP общая постановка задачи оптимизации. - student2.ru G. Значения функции в этой точке называется (локальным) минимумом, соответственно, локальным максимумом функции f в G тогда и только тогда, когда существует некоторая окрестность U(P) общая постановка задачи оптимизации. - student2.ru G

Точки P такая, что для всех точек P общая постановка задачи оптимизации. - student2.ru U(P) имеет место соответственно

f(P) >f(Pо). Максимум или минимум функции f называется также (локальным) экстремумом функции f в G. Значение локального экстремума функции f в точке Pо является наименьшим или наибольшим значением функции в некоторой окрестности точки Pо, однако оно не совпадает, вообще говоря, с наименьшим или наибольшим значением функции в области G.

Необходимые условия существования экстремума. Если f(Pо) есть экстремум функции f, дифференцируемой по каждой из координат в некоторой окрестности U(Pо) точки Pо, то имеет место f(Po)=0; (i=1,..,n)

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

Тута ф – ла))

Метод множителей Лагранжа для решения классической задачи на условный экстремум.

Метод множителей Лагранжа, метод нахождения условного экстремума функции общая постановка задачи оптимизации. - student2.ru , где общая постановка задачи оптимизации. - student2.ru , относительно общая постановка задачи оптимизации. - student2.ru ограничений общая постановка задачи оптимизации. - student2.ru , где общая постановка задачи оптимизации. - student2.ru меняется от единицы до общая постановка задачи оптимизации. - student2.ru .

§ Составим функцию Лагранжа в виде линейной комбинации функции общая постановка задачи оптимизации. - student2.ru и функций общая постановка задачи оптимизации. - student2.ru , взятых с коэффициентами, называемыми множителями Лагранжа — общая постановка задачи оптимизации. - student2.ru :

общая постановка задачи оптимизации. - student2.ru

где общая постановка задачи оптимизации. - student2.ru .

§ Составим систему из общая постановка задачи оптимизации. - student2.ru уравнений, приравняв к нулю частные производные функции Лагранжа общая постановка задачи оптимизации. - student2.ru по общая постановка задачи оптимизации. - student2.ru и общая постановка задачи оптимизации. - student2.ru .

§ Если полученная система имеет решение относительно параметров общая постановка задачи оптимизации. - student2.ru и общая постановка задачи оптимизации. - student2.ru , тогда точка общая постановка задачи оптимизации. - student2.ru может быть условным экстремумом, то есть решением исходной задачи. Заметим, что это условие носит необходимый, но не достаточный характер.

Двумерный случай

общая постановка задачи оптимизации. - student2.ru

общая постановка задачи оптимизации. - student2.ru

Линии уровня общая постановка задачи оптимизации. - student2.ru и кривая общая постановка задачи оптимизации. - student2.ru .

Пусть требуется найти экстремум некоторой функции двух переменных общая постановка задачи оптимизации. - student2.ru при условии, задаваемом уравнением общая постановка задачи оптимизации. - student2.ru . Мы будем считать, что все функции непрерывно дифференцируемы, и данное уравнение задает гладкую кривую общая постановка задачи оптимизации. - student2.ru на плоскости общая постановка задачи оптимизации. - student2.ru . Тогда задача сводится к нахождению экстремума функции общая постановка задачи оптимизации. - student2.ru на кривой общая постановка задачи оптимизации. - student2.ru . Будем также считать, что общая постановка задачи оптимизации. - student2.ru не проходит через точки, в которых градиент общая постановка задачи оптимизации. - student2.ru обращается в общая постановка задачи оптимизации. - student2.ru .

Нарисуем на плоскости общая постановка задачи оптимизации. - student2.ru линии уровня функции общая постановка задачи оптимизации. - student2.ru (то есть кривые общая постановка задачи оптимизации. - student2.ru ). Из геометрических соображений видно, что экстремумом функции общая постановка задачи оптимизации. - student2.ru на кривой общая постановка задачи оптимизации. - student2.ru могут быть только точки, в которых касательные к общая постановка задачи оптимизации. - student2.ru и соответствующей линии уровня совпадают. Действительно, если кривая общая постановка задачи оптимизации. - student2.ru пересекает линию уровня общая постановка задачи оптимизации. - student2.ru в точке общая постановка задачи оптимизации. - student2.ru трансверсально (то есть под некоторым ненулевым углом), то двигаясь по кривой общая постановка задачи оптимизации. - student2.ru из точки общая постановка задачи оптимизации. - student2.ru мы можем попасть как на линии уровня, соответствующие большему значению общая постановка задачи оптимизации. - student2.ru , так и меньшему. Следовательно, такая точка не может быть точкой экстремума.

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

общая постановка задачи оптимизации. - student2.ru

где общая постановка задачи оптимизации. - student2.ru — некоторое число, отличное от нуля, и являющееся множителем Лагранжа.

Рассмотрим теперь функцию Лагранжа , зависящую от общая постановка задачи оптимизации. - student2.ru и общая постановка задачи оптимизации. - student2.ru :

общая постановка задачи оптимизации. - student2.ru

Необходимым условием ее экстремума является равенство нулю градиента общая постановка задачи оптимизации. - student2.ru . В соответствии с правилами дифференцирования, оно записывается в виде

общая постановка задачи оптимизации. - student2.ru

Мы получили систему, первые два уравнения которой эквивалентны необходимому условию локального экстремума (1), а третье — уравнению общая постановка задачи оптимизации. - student2.ru . Из нее можно найти общая постановка задачи оптимизации. - student2.ru . При этом общая постановка задачи оптимизации. - student2.ru , поскольку в противном случае градиент функции общая постановка задачи оптимизации. - student2.ru обращается в нуль в точке общая постановка задачи оптимизации. - student2.ru , что противоречит нашим предположениям. Следует заметить, что найденные таким образом точки общая постановка задачи оптимизации. - student2.ru могут и не являться искомыми точками условного экстремума — рассмотренное условие носит необходимый, но не достаточный характер. Нахождение условного экстремума с помощью вспомогательной функции общая постановка задачи оптимизации. - student2.ru и составляет основу метода множителей Лагранжа, примененного здесь для простейшего случая двух переменных. Оказывается, вышеприведенные рассуждения обобщаются на случай произвольного числа переменных и уравнений, задающих условия.

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

Противоречивость системы

l Разумеется, возможен и такой случай, когда нет ни одной точки, принадлежащей одновременно всем рассматриваемым полуплоскостям, т.е. когда область К «пуста»; это означает, что система противоречива.

Выпуклость области решений

l Область решений X всегда выпукла.

l Множество точек (на плоскости или в пространстве) называется выпуклым, если вместе с любыми двумя своими точками А и В оно содержит и весь отрезок АВ.

Постановка задачи

Классическая транспортная задача ЛП формулируется следующим образом.

Имеется m пунктов производства (поставщиков) и n пунктов

потребления (потребителей) однородного продукта. Заданы величины:

общая постановка задачи оптимизации. - student2.ru - объем производства (запас) i-го поставщика, i=1, m ;

общая постановка задачи оптимизации. - student2.ru - объем потребления (спрос) j-го потребителя, i=1, n ;

общая постановка задачи оптимизации. - student2.ru - стоимость перевозки (транспортные затраты) единицы продукта от i-го поставщика к j-му потребителю.

Требуется составить такой план перевозок, при котором спрос

всех потребителей был бы выполнен и при этом общая стоимость всех

перевозок была бы минимальна.

Математическая модель транспортной задачи имеет вид

общая постановка задачи оптимизации. - student2.ru

Транспортная задача, в которой суммарные запасы

общая постановка задачи оптимизации. - student2.ru

и суммарные потребности

общая постановка задачи оптимизации. - student2.ru

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

В случае, когда суммарные запасы превышают суммарные

потребности, т.е.

общая постановка задачи оптимизации. - student2.ru

вводится фиктивный n+1 потребитель, потребности которого

общая постановка задачи оптимизации. - student2.ru

В случае, когда суммарные потребности превышают суммарные

запасы, т.е.

общая постановка задачи оптимизации. - student2.ru

, вводится фиктивный m+1 поставщик, запасы которого

общая постановка задачи оптимизации. - student2.ru

Стоимость перевозки единицы груза как до фиктивного потребителя, так и стоимость перевозки единицы груза от фиктивного поставщика

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

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

закрытой модели.

Теорема 1.

Базисное решение закрытой модели транспортной задачи содержит m+n-1 базисных компонент.

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

Количество базисных компонент определяется число линейно независимых ограничений задачи. В транспортной задаче не все m+n ограничений линейно-независимы.

Действительно, сложив первые m ограничений и следующие n ограничений задачи, получим

общая постановка задачи оптимизации. - student2.ru

Но в закрытой модели выполняется балансовое равенство

общая постановка задачи оптимизации. - student2.ru

поэтому получаем, что нетривиальная линейная комбинация строк ограничений (линейная комбинация с ненулевыми коэффициентами) равна нулю. Это означает, что среди ограничений задачи есть линейно-зависимое ограничение. Следовательно, число линейно-независимых ограничений равно m+n-1 и базис задачи состоит из m+n-1 компонент.

Теорема доказана

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

Теорема 2.

Оптимальный план закрытой модели транспортной задачи существует всегда.

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

Оптимальное решение задачи ЛП существует, если, во-первых, существует допустимое решение и, во-вторых, целевая функция ограничена на этом допустимом решении.

Покажем существование допустимого решения. Так как

суммарные запасы

общая постановка задачи оптимизации. - student2.ru

совпадают с суммарными потребностями

общая постановка задачи оптимизации. - student2.ru

то всегда можно найти такой план перевозок, который будет допустимым решением (все запасы вывозятся и все потребности выполняются в силу балансового равенства).

Покажем ограниченность целевой функции.

Так как

общая постановка задачи оптимизации. - student2.ru

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

Теорема доказана

Двойственная задача

Запишем транспортную задачу в матричном виде

общая постановка задачи оптимизации. - student2.ru

A- матрица ограничений, имеющая в соответствии с векторами х и b вид :

общая постановка задачи оптимизации. - student2.ru

Двойственная задача к транспортной задаче в матричном виде будет иметь вид

общая постановка задачи оптимизации. - student2.ru

у- произвольного знака.

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

общая постановка задачи оптимизации. - student2.ru

Тогда

общая постановка задачи оптимизации. - student2.ru

и ограничения двойственной задачи будут иметь вид :

общая постановка задачи оптимизации. - student2.ru

или в общем виде двойственная задача

общая постановка задачи оптимизации. - student2.ru

Двойственные переменные i, i=1,...,m, j, j=1,...,n, называются платежами, а

общая постановка задачи оптимизации. - student2.ru

- псевдостоимость перевозок единицы груза из пункта i в пункт j, i=1,...,m, j=1,...,n.

Теоремы двойственности

ИЗ теории двойственности ЛП практический интерес представляет вторая теорема двойственности, из которой получается следующий критерий.

Метод севево-западного угла

Рассмотрим "северо-западный угол" незаполненной таблицы, то

есть клетку, соответствующую первому поставщику и первому потребителю.

Возможны три случая.

общая постановка задачи оптимизации. - student2.ru

Это означает, что первый поставщик отгрузил весь произведенный продукт первому потребителю и его

запас равен нулю, поэтому

общая постановка задачи оптимизации. - student2.ru

При этом неудовлетворенный спрос в первом пункте потребления равен

общая постановка задачи оптимизации. - student2.ru

общая постановка задачи оптимизации. - student2.ru

то есть спрос первого потребителя полностью удовлетворен и поэтому общая постановка задачи оптимизации. - student2.ru

а остаток продукта в первом пункте производства равен

общая постановка задачи оптимизации. - student2.ru

общая постановка задачи оптимизации. - student2.ru

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

поэтому условно считается, что выбывает только поставщик,

общая постановка задачи оптимизации. - student2.ru

а спрос потребителя остается неудовлетворенным и равным нулю.

общая постановка задачи оптимизации. - student2.ru

После этого рассматриваем северо-западный угол оставшейся не-

заполненной части таблицы и повторяем те же действия. В результате

через n+m-1 шагов получим опорный план.

10. Математическая модель транспортной задачи. Открытые и закрытые задачи. Допустимый, опорный и оптимальный планы перевозок.

Под названием «транспортная задача» объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

Открытая и закрытая транспортные задачи. Выделяют два типа ТЗ: открытая ТЗ и закрытая ТЗ.

Транспортная задача называется закрытой, если выполняется условие баланса : суммарный объем производства равен суммарному объему потребления:

общая постановка задачи оптимизации. - student2.ru . (3.1)

Следнет обратить внимание на то, что математическая модель задает закрытую транспортную задачу.

Открытая ТЗ имеет место в двух случаях.

Первый случай. Суммарный объем производства меньше суммарного объема потребления:

общая постановка задачи оптимизации. - student2.ru . (3.2)

Известно, что для существования допустимого решения транспортной задачи необходимо и достаточно, чтобы задача была закрытой. Поэтому транспортную задачу открытого типа предварительно необходимо свести к закрытой, для чего вводится фиктивный пункт производства с номером m+1 с объемом производства:

общая постановка задачи оптимизации. - student2.ru , (3.3)

при этом полагают общая постановка задачи оптимизации. - student2.ru .

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

общая постановка задачи оптимизации. - student2.ru . (3.4)

Для сведения ТЗ к закрытому типу вводят фиктивный пункт потребления с номером n+1 с объемом потребления:

общая постановка задачи оптимизации. - student2.ru , (3.5)

при этом полагают общая постановка задачи оптимизации. - student2.ru .

Методы решения.

· Как задача линейного программирования ТЗ может быть решена симплекс методом [4].

· Также разработаны специальные (более эффективные) методы решения транспортной задачи: обобщенный венгерский метод [4]; метод северо-западного угла, метод минимального элемента для нахождения опорного плана; метод потенциалов для нахождения оптимального плана [3].

11. Построение начального (опорного) плана перевозок по методу северо–западного угла и по методу наименьшей стоимости.

1.Метод северо-западного угла. При нахождении опорного плана на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Заполнение клеток таблицы условий начинается с левой верхней клетки для неизвестного общая постановка задачи оптимизации. - student2.ru («северо-западный угол») и заканчивается клеткой для неизвестного , общая постановка задачи оптимизации. - student2.ru т.е. как бы по диагонали таблицы.

2. Метод наименьшей стоимости. Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку общая постановка задачи оптимизации. - student2.ru , которая ей соответствует, помещают меньшее из чисел общая постановка задачи оптимизации. - student2.ru и общая постановка задачи оптимизации. - student2.ru , затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс размещения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

Формула полной вероятности.

Пусть событие A может произойти только вместе с одним из попарно несовместных событий H1, H2, ..., Hn, образующих полную группу. Тогда, если произошло событие A, то это значит, что произошло одно из попарно несовместных событий H1A, H2A, ..., HnA. Следовательно,

общая постановка задачи оптимизации. - student2.ru

Применяя аксиому сложения вероятностей, имеем

общая постановка задачи оптимизации. - student2.ru

Но общая постановка задачи оптимизации. - student2.ru (i=1, 2, ..., n), поэтому

общая постановка задачи оптимизации. - student2.ru  

Эта формула называется формулой полной вероятности. События H1, H2, ..., Hn часто называют «гипотезами».

Теорема Байеса.

Теорема Байеса— позволяет определить вероятность того, что произошло какое-либо событие (гипотеза) при наличии лишь косвенных тому подтверждений (данных), которые могут быть неточны.

Формула Байеса:

общая постановка задачи оптимизации. - student2.ru ,

где

общая постановка задачи оптимизации. - student2.ru — априорная вероятность (насколько вероятна причина вообще) гипотезы A

общая постановка задачи оптимизации. - student2.ru — вероятность гипотезы A при наступлении события B

общая постановка задачи оптимизации. - student2.ru — вероятность наступления события B при истинности гипотезы A

общая постановка задачи оптимизации. - student2.ru — полная вероятность наступления события B.

Следствие

Формула Байеса является важным следствием из формулы полной вероятности события, зависящего от нескольких несовместных гипотез (и только от них!).

общая постановка задачи оптимизации. - student2.ru — вероятность наступления события B, зависящего от ряда гипотез общая постановка задачи оптимизации. - student2.ru , если известны степени достоверности этих гипотез (например, измерены экспериментально);

Формула Бернулли

Если производятся испытания, при которых вероятность появления события А в каждом испытании не зависит от исходов других испытаний, то такие испытания называют независимыми относительно события А.

Вероятность того, что в n независимых испытаниях, в каждом из которых вероятность появления события равна р(0 < p < 1), событие наступит ровно k раз (безразлично, в какой последовательности), равна:

Pn(k)=Cnkpkqn-k

или

общая постановка задачи оптимизации. - student2.ru

где q=1-p

Вероятность того, что в n испытаниях событие наступит: а) менее k раз; б) более k раз; в) не менее k раз; г) не более k раз, — находят соответственно по формулам:

Pn(0)+Pn(1)+...+Pn(k-1);

Pn(k+1)+Pn(k+2)+...+Pn(n);

Pn(k)+Pn(k+1)+...+Pn(n);

Pn(0)+Pn(1)+...+Pn(k);

Правило трех сигм

Правила трех сигм: если случайная величина распределена нормально, то абсолютная величина ее отклонения от математического ожидания не превосходит утроенного среднего квадратического отклонения.

P(|X − a| < δ) = 2Φ общая постановка задачи оптимизации. - student2.ru σ)

положив δ = σt. В итоге получим

P(|X − a| < σt) = 2Φ (t).

Если t = 3 и, следовательно, σt = 3σ, то

P(|X − a| < 3σ) = 2Φ (3) = 2 · 0.49865 = 0.9973,

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

37) Понятие о теореме Ляпунова

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

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

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

Пусть с общая постановка задачи оптимизации. - student2.ru последовательность попарно независимых случайных величин с математическими ожиданиями M общая постановка задачи оптимизации. - student2.ru и дисперсиями D общая постановка задачи оптимизации. - student2.ru , причём эти величины обладают следующими двумя свойствами:

1) Существует такое число L, что для любого i имеет место неравенство общая постановка задачи оптимизации. - student2.ru т, е. все значения случайных величин, как говорят, равномерно ограничены, относительно математических ожиданий;

2) Сумма общая постановка задачи оптимизации. - student2.ru неограниченно растёт при общая постановка задачи оптимизации. - student2.ru .

Тогда при достаточно большом n сумма общая постановка задачи оптимизации. - student2.ru имеет распределение, близкое к нормальному.

Пусть общая постановка задачи оптимизации. - student2.ru и общая постановка задачи оптимизации. - student2.ru математическое ожидание и дисперсия случайной величины общая постановка задачи оптимизации. - student2.ru Тогда:

общая постановка задачи оптимизации. - student2.ru

общая постановка задачи оптимизации. - student2.ru

общая постановка задачи оптимизации. - student2.ru .

Ц.П.Т. Ляпунова

Пусть выполнены базовые предположения Ц.П.Т. Линдеберга. Пусть случайные величины общая постановка задачи оптимизации. - student2.ru имеют конечный третий момент. Тогда определена последовательность общая постановка задачи оптимизации. - student2.ru Если предел общая постановка задачи оптимизации. - student2.ru (условие Ляпунова), то

общая постановка задачи оптимизации. - student2.ru по распределению при общая постановка задачи оптимизации. - student2.ru .

38)Закон больших чисел.

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

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

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

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

Слабый закон больших чисел

общая постановка задачи оптимизации. - student2.ru

Тогда, общая постановка задачи оптимизации. - student2.ru .

Неравенство Чебышева

p( | X – M(X)| < ε ) ≥ D(X) / ε².

Доказательство. Пусть Х задается рядом распределения

Х х1 х2 хп
р р1 р2 рп
         

Так как события |X – M(X)| < ε и |X – M(X)| ≥ ε противоположны, то р ( |X – M(X)| < ε ) + + р ( |X – M(X)| ≥ ε ) = 1, следовательно, р ( |X – M(X)| < ε ) = 1 - р ( |X – M(X)| ≥ ε ). Найдем р ( |X – M(X)| ≥ ε ).

D(X) = (x1 – M(X))²p1 + (x2 – M(X))²p2 + … + (xn – M(X))²pn . Исключим из этой суммы те слагаемые, для которых |X – M(X)| < ε. При этом сумма может только уменьшиться, так как все входящие в нее слагаемые неотрицательны. Для определенности будем считать, что отброшены первые kслагаемых. Тогда

D(X) ≥ (xk+1 – M(X))²pk+1 + (xk+2 – M(X))²pk+2 + … + (xn – M(X))²pn ≥ ε² (pk+1 + pk+2 + … + pn).

Отметим, что pk+1 + pk+2 + … + pn есть вероятность того, что |X – M(X)| ≥ ε, так как это сумма вероятностей всех возможных значений Х, для которых это неравенство справедливо. Следовательно, D(X) ≥ ε² р(|X – M(X)| ≥ ε), или р (|X – M(X)| ≥ ε) ≤ D(X) / ε². Тогда вероятность противоположного события p( | X – M(X)| < ε ) ≥ D(X) / ε², что и требовалось доказать

Теорема Чебышева:

общая постановка задачи оптимизации. - student2.ru

Распределение Стьюдента

Пусть случайная величина x имеет стандартное нормальное распределение, а случайная величина c n2 - c 2-распределение с n степенями свободы. общая постановка задачи оптимизации. - student2.ru

Если x и c n2 - независимы, то про случайную величину говорят, что она имеет распределение Стьюдента с n степенями свободы. Плотность вероятности этой случайной величины вычисляется по формуле:

общая постановка задачи оптимизации. - student2.ru общая постановка задачи оптимизации. - student2.ru , x общая постановка задачи оптимизации. - student2.ru R,Mt n = 0,Dt n = n/(n-2), n>2.

При больших n распределение Стьюдента практически не отличается от N(0, 1).

Распределение Фишера

Пусть случайные величины c n2и c m2 независимы и имеют распределение c 2 с n и m степенями свободы соответственно. общая постановка задачи оптимизации. - student2.ru

Тогда о случайной величине говорят, что она имеет F-распределение. Плотность вероятности этой случайной величины вычисляется по формуле:

общая постановка задачи оптимизации. - student2.ru , x>0,

общая постановка задачи оптимизации. - student2.ru - гамма-функция Эйлера;

общая постановка задачи оптимизации. - student2.ru , m>2; общая постановка задачи оптимизации. - student2.ru, m > 4.
53. Критерии и правила проверки гипотез: о равенстве дисперсий и математических ожиданий двух нормальных генеральных совокупностей; о том, что генеральная совокупность распределена по нормальному закону.

Общая постановка задачи оптимизации.

Линейное программирование. Постановка задачи математического программирования начинается с определения цели(целевая функция)

F(x)=f(x)->opt(i) (max, min)

Для нахождения решения задачи необходимо определить переменные задачи x = (x1,x2,…,xn)ограничения накладываемые на них. Эти ограничения представляют систему:

g (x) <0

g(x)>0

g(x)=0

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

Классификация:

Если функция цели:

1. Линейная функция gi(x) также линейные функции, то модель называется моделью лин. программирования

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

3. Если переменные задачи xi, являются переменные зависящими от времени, то модель называется моделью динамического программирования.

Наши рекомендации