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

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

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

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 R и точкаP G. Значения функции в этой точке называется (локальным) минимумом, соответственно, локальным максимумом функции f в G тогда и только тогда, когда существует некоторая окрестность U(P) G

Точки P такая, что для всех точек P 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(х, у) т.е.

Тута ф – ла))

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

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

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

где .

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

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

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

Линии уровня и кривая .

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

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

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

где — некоторое число, отличное от нуля, и являющееся множителем Лагранжа.

Рассмотрим теперь функцию Лагранжа, зависящую от и :

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

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

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

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

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

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

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

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

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

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

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

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

- объем производства (запас) i-го поставщика, i=1, m;

- объем потребления (спрос) j-го потребителя, i=1, n;

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

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

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

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

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

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

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

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

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

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

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

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

запасы, т.е.

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

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

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

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

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

Теорема 1.

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

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

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

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

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

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

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

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

Теорема 2.

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

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

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

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

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

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

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

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

Так как

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

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

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

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

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

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

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

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

Тогда

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

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

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

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

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

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

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

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

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

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

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

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

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

то есть спрос первого потребителя полностью удовлетворен и поэтому

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

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

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

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

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

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

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

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

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

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

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

. (3.1)

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

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

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

. (3.2)

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

, (3.3)

при этом полагают .

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

. (3.4)

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

, (3.5)

при этом полагают .

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

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

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

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

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

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

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

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

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

Но (i=1, 2, ..., n), поэтому

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

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

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

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

где

— априорная вероятность (насколько вероятна причина вообще) гипотезы A

— вероятность гипотезы A при наступлении события B

— вероятность наступления события B при истинности гипотезы A

— полная вероятность наступления события B.

Следствие

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

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

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

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

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

P_n(k)=C_n^kp^kq^n-k

или

где q=1-p

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2) Сумма неограниченно растёт при .

Тогда при достаточно большом n сумма имеет распределение, близкое к нормальному.

Пусть и математическое ожидание и дисперсия случайной величины Тогда:

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

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

по распределению при .

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

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

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

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

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

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

Тогда, .

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

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

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

Х	х₁	х₂	…	х_п
р	р₁	р₂	…	р_п

Так как события |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) / ε ², что и требовалось доказать

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

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

Пусть случайная величина x имеет стандартное нормальное распределение, а случайная величина c _n² - c ²-распределение с n степенями свободы.

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

, x R, M t _n= 0, D t _n= n/(n-2), n> 2.

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

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

Пусть случайные величины c _n²и c _m² независимы и имеют распределение c ²с n и m степенями свободы соответственно.

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

, x> 0,

- гамма-функция Эйлера;

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