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

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

Нажмите для полного просмотра!
Симплекс-метод, слайд №1Симплекс-метод, слайд №2Симплекс-метод, слайд №3Симплекс-метод, слайд №4Симплекс-метод, слайд №5Симплекс-метод, слайд №6Симплекс-метод, слайд №7Симплекс-метод, слайд №8Симплекс-метод, слайд №9Симплекс-метод, слайд №10Симплекс-метод, слайд №11Симплекс-метод, слайд №12Симплекс-метод, слайд №13Симплекс-метод, слайд №14Симплекс-метод, слайд №15Симплекс-метод, слайд №16Симплекс-метод, слайд №17Симплекс-метод, слайд №18Симплекс-метод, слайд №19Симплекс-метод, слайд №20Симплекс-метод, слайд №21Симплекс-метод, слайд №22Симплекс-метод, слайд №23Симплекс-метод, слайд №24Симплекс-метод, слайд №25Симплекс-метод, слайд №26Симплекс-метод, слайд №27Симплекс-метод, слайд №28Симплекс-метод, слайд №29Симплекс-метод, слайд №30Симплекс-метод, слайд №31Симплекс-метод, слайд №32Симплекс-метод, слайд №33Симплекс-метод, слайд №34Симплекс-метод, слайд №35Симплекс-метод, слайд №36Симплекс-метод, слайд №37Симплекс-метод, слайд №38Симплекс-метод, слайд №39Симплекс-метод, слайд №40

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


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

Слайд 1



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

Слайд 2



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

Слайд 3



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

Слайд 4
Симплекс-метод, слайд №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
Описание слайда:
Алгоритм решения задачи : Стандартная задача ЛП сводится к основной задаче. 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 , где
Описание слайда:
Определяется начальное допустимое решение Для этого запишем систему ограничений в векторной форме x1A1+x2A2+…+ xnAn+xn+1An+1+…+ xn+mAn+m =A0 , где

Слайд 7



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

Слайд 8



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

Слайд 10



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

Слайд 11



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

Слайд 12



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

Слайд 13



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

Слайд 14



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

Слайд 15



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

Слайд 16



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

Слайд 17



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

Слайд 18



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

Слайд 19



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

Слайд 20



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

Слайд 21



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

Слайд 22



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

Слайд 23



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

Слайд 24
Симплекс-метод, слайд №24
Описание слайда:

Слайд 25



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

Слайд 26



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

Слайд 27



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

Слайд 28



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

Слайд 29
Симплекс-метод, слайд №29
Описание слайда:

Слайд 30



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

Слайд 31
Симплекс-метод, слайд №31
Описание слайда:

Слайд 32



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

Слайд 33



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

Слайд 34
Симплекс-метод, слайд №34
Описание слайда:

Слайд 35



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

Слайд 36
Симплекс-метод, слайд №36
Описание слайда:

Слайд 37
Симплекс-метод, слайд №37
Описание слайда:

Слайд 38



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

Слайд 39



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

Слайд 40



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



Похожие презентации
Mypresentation.ru
Загрузить презентацию