- •Общая постановка задачи оптимизации.
- •Классическая задача на условный экстремум. Необходимые и достаточные условия условного экстремума.
- •Метод множителей Лагранжа для решения классической задачи на условный экстремум.
- •Линейные неравенства и область решений системы линейных неравенств.
- •5. Общая задача линейного программирования. Геометрическая интерпретация задачи.
- •Графический метод решения задачи линейного программирования для двух переменных.
- •Решение задачи линейного программирования симплекс–методом. Симплексные таблицы. Алгоритм симплекс–метода.
- •Решение задачи оптимизации выпуска продукции симплекс–методом.
- •Модель оптимизации плана перевозок (транспортная задача). Экономическая постановка задачи.
- •9.2 Основные свойство транспортной задачи
- •9.3 Двойственная задача
- •9.4 Теоремы двойственности
- •9.5 Построение опорного плана транспортной задачи
- •9.6 Метод севево-западного угла
- •Математическая модель транспортной задачи. Открытые и закрытые задачи. Допустимый, опорный и оптимальный планы перевозок.
- •11. Построение начального (опорного) плана перевозок по методу северо–западного угла и по методу наименьшей стоимости.
- •12. Теорема о потенциалах. Метод потенциалов. Транспортные таблицы. Понятие цикла. Сущность метода потенциалов.
- •13.Критерий оптимальности и неоптимальности опорного плана. Критерий единственности оптимального опорного плана.
- •14. Понятия испытания и случайного события. Частота и относительная частота появления события в серии испытаний. Вероятность случайного события.
- •15. Совместные и несовместные события. Полная группа событий. Событие, благоприятствующее данному. Равновозможные события. Совокупность элементарных исходов.
- •16.Классическое определение вероятности. Простейшие свойства вероятности.
- •17. Основные правила комбинаторики. Сочетания, перестановки, размещения.
- •18. Частота и относительная частота появления события в серии испытаний. Стохастическая устойчивость случайного события. Статистическое определение вероятности.
- •19. Вероятность противоположного события. Условная вероятность.
- •20. Сумма и произведение случайных событий. Теорема сложения вероятностей: для двух произвольных событий, для двух несовместных.
- •21. Теорема умножения вероятностей: для двух произвольных событий; для двух независимых событий; для нескольких событий, независимых в совокупности.
- •22. Формула полной вероятности.
- •23. Теорема Байеса.
- •24. Формула Бернулли
- •25. Локальная и интегральная теоремы Лапласа. Функции Гаусса и Лапласа.
- •26. Понятие случайной величины. Закон распределения случайной величины. Функция распределения и ее свойства.
- •1) Биномиальное распределение (дискретное)
- •2) Пуассоновское распределение (дискретное)
- •3) Показательное распределение (непрерывное)
- •4) Равномерное распределение (непрерывное)
- •5) Нормальное распределение или распределение Гаусса (непрерывное)
- •27. Дискретная случайная величина. Способы задания закона распределения дискретной случайной величины.
- •28. Числовые характеристики дискретной случайной величины: математическое ожидание, дисперсия, среднее квадратическое отклонение. Их основные свойства.
- •29. Биномиальный закон распределения.
- •30. Распределение Пуассона. Простейший поток событий.
- •Ц.П.Т. Ляпунова
- •Слабый закон больших чисел
- •Усиленный закон больших чисел
- •Значение теоремы Чебышева для практики.
- •51. Понятие критерия. Критическая область и область принятия гипотезы. Односторонняя и двусторонняя критическая область, критические точки. Мощность критерия.
- •56. Коэффициенты регрессии. Линии регрессии.
- •59. Эмпирическая и теоретическая линии регрессии.
Решение задачи линейного программирования симплекс–методом. Симплексные таблицы. Алгоритм симплекс–метода.
Для решения ЗЛП существует универсальный метод – метод последовательного улучшения плана или симплекс-метод, который состоит из двух вычислительных процедур: симплекс-метода с естественным базисом и симплекс-метода с искусственным базисом (М-метод).
Выбор конкретной вычислительной процедуры осуществляется после приведения исходной ЗЛП к каноническому виду (КЗЛП):
В теории линейного программирования (ЛП) показано, что оптимальное решение ЗЛП связано с угловыми (крайними) точками многогранника решений, которым отвечают опорные планы (неотрицательные базисные решения системы уравнений КЗЛП). Каждый из опорных планов определяется системой m линейно независимых векторов, содержащихся в данной системе из n векторов А1, А2,…, Аn. Верхняя граница количества опорных планов, содержащихся в данной задаче, определяется числом сочетаний Сnm.
Понятно, что при больших m и n найти оптимальный план, перебирая указанным выше способом (прямым перебором) все опорные ЗЛП весьма трудно. Поэтому необходимо иметь схему, позволяющую осуществлять упорядоченный переход от одного опорного плана к другому. Такой схемой является симплексный метод.
Симплекс-метод с естественным базисом
Для применения симплекс-метода с естественным базисом КЗЛП должна содержать единичную подматрицу размером mxm – в этом случае очевиден начальный опорный план (неотрицательное базисное решение системы ограничений КЗЛП).
Для определенности предположим, что первые m векторов матрицы системы уравнений составляют единичную матрицу. Тогда первоначальный опорный план очевиден – (b1, b2 ,…, bm ,0,…,0).
Проверка на оптимальность опорного плана проходит с помощью признака оптимальности, переход к другому опорному плану проводится с помощью преобразований Жордана-Гаусса при использовании математического признака оптимальности. Полученный опорный план снова проверяется на оптимальность и так далее. Процесс заканчивается за конечное число шагов, причем на последнем шаге либо выявляется неразрешимость задачи (конечного оптимума нет), либо получается оптимальный опорный план и соответствующее ему оптимальное значение ЦФ.
Математический признак оптимальности состоит из следующих двух теорем:
Если для всех векторов А1, А2,…, Аn выполняется условие
где ,
то полученный опорный план является оптимальным.
Если для некоторого вектора, не входящего в базис, выполняется условие , то можно получить новый опорный план, для которого значение ЦФ будет больше исходного, при этом могут быть два случая:
если все компоненты вектора, подлежащего вводу в базис, неположительны, то ЗЛП не имеет решения (конечного оптимума нет);
если имеется хотя бы одна положительная компонента у вектора, подлежащего вводу в базис, то можно получить новый опорный план.
На основании признака оптимальности в базис вводится вектор Ак , давший минимальную отрицательную величину симплекс разности:
Чтобы выполнялось условие неотрицательности значений опорного плана, выводится из базиса вектор Аr, который дает минимальное положительное оценочное отношение
Строка Аr называется направляющей, столбец Ак и элемент ar к – направляющими.
Элементы направляющей строки в новой симплекс-таблице вычисляются по формулам:
а элементы i-й строки – по формулам:
Значения нового опорного плана рассчитываются по формулам:
для i = r ;
Процесс решения продолжают либо до получения оптимального плана, либо до установления неограниченности ЦФ. Если среди симплекс-разностей (оценок) оптимального плана нулевые только оценки, соответствующие базисным векторам, то это говорит о единственности оптимального плана. Если же нулевая оценка соответствует вектору, не входящему, то в общем случае это означает, что оптимальный план не единственный.
Примечание. Для использования приведенной процедуры к минимизации линейной функции f (x1,x2,…, xn) следует искать максимум - f (x1,x2,…, xn), затем полученный максимум взять с противоположным знаком. Оптимальное решение то же
-
хб
сб
вi
В1
В2
…
Вм
(таблица в лекциях есть, посмотрите)