Презентация Симплекс-метод

Категория: Математика


500500500500500500500500500500500500500500500500500500500500500500500500500500500500500500500500500500500500500500500500

Вы можете ознакомиться и скачать презентацию на тему Симплекс-метод. Доклад-сообщение содержит 40 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.


Слайды и текст этой презентации

Слайд 1
Описание слайда:
Симплекс-метод Впервые симплексный метод был предложен американским ученым Дж. Данцигом в 1949 году, однако еще в 1939 году идеи метода были разработаны российским ученым А.В. Канторовичем. СМ решения задачи ЛП основан на переходе от одного допустимого решения к другому, при котором значение ЦФ возрастает. Указанный переход возможен, если известно какое-нибудь допустимое решение.

Слайд 2
Описание слайда:
Из линейной алгебры известно: Из линейной алгебры известно: Равенства называются линейно независимыми, если никакое из них нельзя получить из других путем умножения на какие-то коэффициенты и суммирования, т.е. никакое из них не является следствием остальных. В линейной алгебре доказывается, что максимальное число линейно независимых равенств, связывающих n переменных x1 …xn, равно n . В линейной алгебре доказывается, что систему из r независимых равенств с n переменными всегда можно разрешить относительно каких-то r переменных (называемых базовыми) и выразить через них остальные n-r переменных (называемых свободными). Свободным переменным можно придавать какие угодно значения. Теорема1 Любому допустимому решению задачи ЛП соответствует по крайней мере хотя бы одна угловая точка многоугольника решений, и наоборот, любой угловой точке многогранника решений соответствует допустимое базисное решение.

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

Слайд 4
Описание слайда:

Слайд 5
Описание слайда:
Алгоритм решения задачи : Стандартная задача ЛП сводится к основной задаче. F= c1x1+…+cnxnmax a11x1+…+a1nxn+xn+1=b1 a11x1+…+a1nxn +xn+2=b2 …. am1x1+…+amnxn+ xn+m=bm xj  0 j=1,n

Слайд 6
Описание слайда:
Определяется начальное допустимое решение Для этого запишем систему ограничений в векторной форме x1A1+x2A2+…+ xnAn+xn+1An+1+…+ xn+mAn+m =A0 , где

Слайд 7
Описание слайда:
По данным задачи составляется симплекс-таблица:

Слайд 8
Описание слайда:
В (m+1) –й строке в столбцах векторов Aj записываются значения В (m+1) –й строке в столбцах векторов Aj записываются значения

Слайд 9
Описание слайда:
Полученное допустимое решение проверяется на оптимальность (в случае максимизации). Полученное допустимое решение проверяется на оптимальность (в случае максимизации). Используются теоремы: Теорема2 Если для некоторого опорного плана x* выполняются неравенства Δj ≥0, то этот план оптимальный . Теорема3 Если для опорного плана Х задачи ЛП существует хотя бы один элемент j , для которого Δj < 0 и среди коэффициентов разложения j-го вектора есть хотя бы один аij >0, то существует такой опорный план Х’, для которого F(x’)>F(x). Если хотя бы для одной отрицательной оценки ∆j < 0. коэффициенты разложения aij соответствующего вектора неположительные, то линейная функция не ограничена на многограннике решений, и следовательно, задача не имеет решения.

Слайд 10
Описание слайда:
Наличие оптимальности проверяется по следующему признаку: Наличие оптимальности проверяется по следующему признаку: Согласно теорем выясняется, имеется ли хотя бы одно отрицательное ∆j (ЦФ исследуется на максимум). Если нет, то найденное решение является оптимальным. Если же среди чисел ∆j имеются отрицательные, то либо устанавливается неразрешимость задачи, либо переходят к новому допустимому решению.

Слайд 11
Описание слайда:
В случае исследования целевой функции на минимум допустимое решение является оптимальным, если все разности ∆j ≤ 0 . Если хотя бы одно ∆j>0 , тогда в базис включается вектор, соответствующий этой оценке, и вычисляется новое допустимое решение, при котором линейная целевая функция будет принимать меньшее значение. В случае исследования целевой функции на минимум допустимое решение является оптимальным, если все разности ∆j ≤ 0 . Если хотя бы одно ∆j>0 , тогда в базис включается вектор, соответствующий этой оценке, и вычисляется новое допустимое решение, при котором линейная целевая функция будет принимать меньшее значение. Если положительных элементов в последней строке симплекс-таблицы, несколько, то в базис должен быть включен вектор, которому соответствует максимальный положительный ∆j .> 0. Если имеется несколько одинаковых максимальных значений ∆j , то из соответствующих им векторов включается в базис вектор, которому соответствует минимальное Сj . Если хотя бы для одной положительной оценки ∆j> 0. коэффициенты разложения aij соответствующего вектора неположительные, то линейная функция не ограничена на многограннике решений, и следовательно, задача не имеет решения.

Слайд 12
Описание слайда:
Находится направляющий столбец и направляющая строка. Находится направляющий столбец и направляющая строка. Направляющий столбец определяется наибольшим по абсолютной величине отрицательным числом ∆j , а направляющая строка – минимальным отношением компонент столбца вектора А0 к положительным компонентам направляющего столбца Выбор максимального по модулю отрицательного элемента ∆j означает включение в базис переменной, увеличение которой приводит к максимальному росту ЦФ

Слайд 13
Описание слайда:
Определяются положительные компоненты нового допустимого решения и коэффициенты разложения векторов Aj по векторам нового базиса и числа F0 ∆j по следующим формулам: Определяются положительные компоненты нового допустимого решения и коэффициенты разложения векторов Aj по векторам нового базиса и числа F0 ∆j по следующим формулам:

Слайд 14
Описание слайда:
Полученные данные записываются в новую симплекс–таблицу:

Слайд 15
Описание слайда:
Проверяют найденное допустимое решение на оптимальность Проверяют найденное допустимое решение на оптимальность Если решение не является оптимальным то возвращаются к п.5 , если оптимальное или установлена неразрешимость задачи процесс решения заканчивается.

Слайд 16
Описание слайда:
Пример Для изготовления изделий A, B и C предприятие использует три вида сырья. Составить план производства изделий, при котором общая стоимость всей произведенной предприятием продукции является максимальной

Слайд 17
Описание слайда:
Составим математическую модель задачи.

Слайд 18
Описание слайда:
Запишем эту задачу в форме основной задачи линейного программирования.

Слайд 19
Описание слайда:
Полученную систему уравнений запишем в векторной форме:

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

Слайд 21
Описание слайда:
Составим первую симплексную таблицу и проверим исходное решение на оптимальность.

Слайд 22
Описание слайда:
Значения, стоящие в четвертой строке симплексной таблицы вычисляются следующим образом:

Слайд 23
Описание слайда:
Исходное решение не является оптимальным, т.к. в 4-й строке таблицы имеются три отрицательных числа: Исходное решение не является оптимальным, т.к. в 4-й строке таблицы имеются три отрицательных числа: -9, -10, -16.

Слайд 24
Описание слайда:

Слайд 25
Описание слайда:
Составим новую симплексную таблицу:

Слайд 26
Описание слайда:
Заполняем строку A3, разделив все элементы на разрешающий а22 =8

Слайд 27
Описание слайда:
Вычисление остальных элементов таблицы производим по рекуррентным формулам:

Слайд 28
Описание слайда:
Тогда компоненты вектора A0 находятся

Слайд 29
Описание слайда:

Слайд 30
Описание слайда:
Вычислим компоненты вектора A1:

Слайд 31
Описание слайда:

Слайд 32
Описание слайда:
Аналогично находятся элементы столбцов векторов A2, A5.

Слайд 33
Описание слайда:
Теперь заполним четвертую строку симплексной таблицы.

Слайд 34
Описание слайда:

Слайд 35
Описание слайда:
Решение X2 не является оптимальным, т.к. в 4-ой строке последней симплекс–таблице в столбце вектора A2 стоит отрицательное число –2. В базис вводится вектор A2,

Слайд 36
Описание слайда:

Слайд 37
Описание слайда:

Слайд 38
Описание слайда:
Ответ Это решение соответствует плану выпуска продукции, включающего изготовление 8 изделий B и 20 изделий C. При этом сырье I и II видов используется полностью и остается неиспользованным 96 кг сырья III вида. Стоимость производимой продукции равна 400 рублей.

Слайд 39
Описание слайда:
Вопросы В чем смысл симплекс-метода? Что необходимо для реализации СМ? Теорема о соответствии допустимых решений задачи и многоугольника решений. С чего начинается решение задачи СМ? Как определяется начальное допустимое решение (опорный план)? Что такое оценка плана? Теоремы, позволяющие проверить решение на оптимальность (при максимизации).

Слайд 40
Описание слайда:
Что меняется при определении минимального решения? Что меняется при определении минимального решения? Как определяется направляющий столбец? Как определяется направляющая строка? Как рассчитать следующую симплекс-таблицу? Когда задача не имеет решения?



Похожие презентации

Mypresentation.ru

Загрузить презентацию