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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Симплекс-метод, слайд №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


Симплекс-метод Лекции 6, 7
Описание слайда:
Симплекс-метод Лекции 6, 7

Слайд 2


Симплекс-метод с естественным базисом Симплекс –метод основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает при условии, что задача имеет оптимальный план и каждый опорный план является невырожденным. Этот переход возможен, если известен какой-либо опорный план.
Описание слайда:
Симплекс-метод с естественным базисом Симплекс –метод основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает при условии, что задача имеет оптимальный план и каждый опорный план является невырожденным. Этот переход возможен, если известен какой-либо опорный план.

Слайд 3


В этом случае каноническая задача линейного программирования должна содержать единичную подматрицу порядка m Тогда очевиден первоначальный опорный план( неотрицательное базисное решение системы ограничений КЗЛП).
Описание слайда:
В этом случае каноническая задача линейного программирования должна содержать единичную подматрицу порядка m Тогда очевиден первоначальный опорный план( неотрицательное базисное решение системы ограничений КЗЛП).

Слайд 4


Рассмотрим задачу, для которой это возможно. Пусть требуется найти максимальное значение функции при условиях Здесь -заданные постоянные числа, причем
Описание слайда:
Рассмотрим задачу, для которой это возможно. Пусть требуется найти максимальное значение функции при условиях Здесь -заданные постоянные числа, причем

Слайд 5


Перепишем ЗЛП в векторной форме: найти максимум функции при условиях Здесь
Описание слайда:
Перепишем ЗЛП в векторной форме: найти максимум функции при условиях Здесь

Слайд 6


Так как , то по определению опорного плана , где последние компоненты вектора равны нулю, является опорным планом Опорный план называется невырожденным, если он содержит m положительных компонент. В противном случае он называется вырожденным.
Описание слайда:
Так как , то по определению опорного плана , где последние компоненты вектора равны нулю, является опорным планом Опорный план называется невырожденным, если он содержит m положительных компонент. В противном случае он называется вырожденным.

Слайд 7


План, при котором целевая функция ЗЛП принимает свое максимальное (минимальное ) значение , называется оптимальным Этот план определяется системой единичных векторов , которые образуют базис m-векторного пространства. Проверка на оптимальность опорного плана происходит с помощью критерия оптимальности.
Описание слайда:
План, при котором целевая функция ЗЛП принимает свое максимальное (минимальное ) значение , называется оптимальным Этот план определяется системой единичных векторов , которые образуют базис m-векторного пространства. Проверка на оптимальность опорного плана происходит с помощью критерия оптимальности.

Слайд 8


Признак оптимальности. 1)Опорный план ЗЛП является оптимальным, если для любого .
Описание слайда:
Признак оптимальности. 1)Опорный план ЗЛП является оптимальным, если для любого .

Слайд 9


2)Если для некоторого j=k и среди чисел нет положительных, т.е. , то целевая функция ЗЛП не ограничена на множестве ее планов, т.е. ЗЛП не имеет решения, так как нет конечного оптимума.
Описание слайда:
2)Если для некоторого j=k и среди чисел нет положительных, т.е. , то целевая функция ЗЛП не ограничена на множестве ее планов, т.е. ЗЛП не имеет решения, так как нет конечного оптимума.

Слайд 10


3)Если же для некоторого k выполняется условие , но среди чисел есть положительные, т.е. не все , то можно получить новый опорный план, для которого значения целевой функции . На основании признака оптимальности делаем вывод о целесообразности перехода к новому опорному плану.
Описание слайда:
3)Если же для некоторого k выполняется условие , но среди чисел есть положительные, т.е. не все , то можно получить новый опорный план, для которого значения целевой функции . На основании признака оптимальности делаем вывод о целесообразности перехода к новому опорному плану.

Слайд 11


Симплекс-таблица
Описание слайда:
Симплекс-таблица

Слайд 12


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

Слайд 13


Здесь , т.е. Значение После заполнения таблицы исходный опорный план проверяют на оптимальность. Для этого просматривают элементы (m+1)-й строки. Может иметь место один из 3-х случаев.
Описание слайда:
Здесь , т.е. Значение После заполнения таблицы исходный опорный план проверяют на оптимальность. Для этого просматривают элементы (m+1)-й строки. Может иметь место один из 3-х случаев.

Слайд 14


1) Все Тогда составленный план оптимален. 2) для некоторого j и все соответствующие этому j . Тогда целевая функция неограничена. 3) для некоторых индексов j и для каждого такого j по крайней мере одно из чисел положительно. Здесь можно перейти к новому опорному плану.
Описание слайда:
1) Все Тогда составленный план оптимален. 2) для некоторого j и все соответствующие этому j . Тогда целевая функция неограничена. 3) для некоторых индексов j и для каждого такого j по крайней мере одно из чисел положительно. Здесь можно перейти к новому опорному плану.

Слайд 15


Этот переход осуществляется исключением из базиса какого-нибудь из векторов и включением в него другого. В базис вводим вектор , давший минимальную отрицательную величину симплекс-разности
Описание слайда:
Этот переход осуществляется исключением из базиса какого-нибудь из векторов и включением в него другого. В базис вводим вектор , давший минимальную отрицательную величину симплекс-разности

Слайд 16


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

Слайд 17


Строка называется разрешающей строкой, элементы этой строки в новой симплекс-таблице вычисляются по методу Жордана-Гаусса, т.е. по формулам:
Описание слайда:
Строка называется разрешающей строкой, элементы этой строки в новой симплекс-таблице вычисляются по методу Жордана-Гаусса, т.е. по формулам:

Слайд 18


Элементы i-й строки –по формулам
Описание слайда:
Элементы i-й строки –по формулам

Слайд 19


Значение нового опорного плана считают по формулам Значение целевой функции при переходе от одного опорного плана к другому , улучшенному, изменяется по формуле
Описание слайда:
Значение нового опорного плана считают по формулам Значение целевой функции при переходе от одного опорного плана к другому , улучшенному, изменяется по формуле

Слайд 20


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

Слайд 21


Алгоритм применения симплекс-метода 1)Находят опорный план. 2)Составляют симплекс-таблицу. 3)Выясняют, имеется ли хотя бы одна отрицательная оценка. Если нет, то найденный опорный план оптимален. Если же есть отрицательные оценки, то либо устанавливают неразрешимость задачи, либо переходят к новому опорному плану.
Описание слайда:
Алгоритм применения симплекс-метода 1)Находят опорный план. 2)Составляют симплекс-таблицу. 3)Выясняют, имеется ли хотя бы одна отрицательная оценка. Если нет, то найденный опорный план оптимален. Если же есть отрицательные оценки, то либо устанавливают неразрешимость задачи, либо переходят к новому опорному плану.

Слайд 22


4)Находят направляющие столбец и строку. Направляющий столбец определяется наибольшим по абсолютной величине отрицательным числом , а направляющая строка—минимальным числом Q. 5)Определяют положительные компоненты нового опорного плана. Составляется новая таблица. 6)Проверяют найденный опорный план на оптимальность.
Описание слайда:
4)Находят направляющие столбец и строку. Направляющий столбец определяется наибольшим по абсолютной величине отрицательным числом , а направляющая строка—минимальным числом Q. 5)Определяют положительные компоненты нового опорного плана. Составляется новая таблица. 6)Проверяют найденный опорный план на оптимальность.

Слайд 23


Пример. Решить симплекс-методом ЗЛП
Описание слайда:
Пример. Решить симплекс-методом ЗЛП

Слайд 24


Решение. Приведем задачу к каноническому виду, введя новые переменные В целевую функцию эти переменные войдут с нулевыми коэффициентами:
Описание слайда:
Решение. Приведем задачу к каноническому виду, введя новые переменные В целевую функцию эти переменные войдут с нулевыми коэффициентами:

Слайд 25


Из коэффициентов при неизвестных и свободных членов составим векторы Единичные векторы образуют единичную подматрицу и составляют базис первоначального плана. Свободные неизвестные приравниваются к нулю. Получаем первоначальный опорный план: Х= (0;0;350;240;150).
Описание слайда:
Из коэффициентов при неизвестных и свободных членов составим векторы Единичные векторы образуют единичную подматрицу и составляют базис первоначального плана. Свободные неизвестные приравниваются к нулю. Получаем первоначальный опорный план: Х= (0;0;350;240;150).

Слайд 26


Составим симплекс-таблицу и проверим план на оптимальность. В нашем примере Для заполнения последней строки таблицы сразу вычислим симплекс-разности Для этого поочередно умножаем столбец Сб на соответствующие элементы каждого столбца
Описание слайда:
Составим симплекс-таблицу и проверим план на оптимальность. В нашем примере Для заполнения последней строки таблицы сразу вычислим симплекс-разности Для этого поочередно умножаем столбец Сб на соответствующие элементы каждого столбца

Слайд 27


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

Слайд 28


Таблица 0.
Описание слайда:
Таблица 0.

Слайд 29


Определяем разрешающий элемент симплексной таблицы. Т.к. имеется 2 отрицательные оценки, то выбираем ту, что дает максимальную по абсолютной величине отрицательную оценку, т. е. -20. Это означает, что в базис включается вектор , а исключается из базиса тот вектор, которому соответствует .
Описание слайда:
Определяем разрешающий элемент симплексной таблицы. Т.к. имеется 2 отрицательные оценки, то выбираем ту, что дает максимальную по абсолютной величине отрицательную оценку, т. е. -20. Это означает, что в базис включается вектор , а исключается из базиса тот вектор, которому соответствует .

Слайд 30


Разрешающим элементом является . Значение целевой функции в следующей симплекс-таблице будет равно:
Описание слайда:
Разрешающим элементом является . Значение целевой функции в следующей симплекс-таблице будет равно:

Слайд 31


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

Слайд 32


Можно рассчитывать элементы строк методом Жордана-Гаусса, домножая 1-ю строку на (-0,5) и прибавляя ее ко 2-й, а затем на(-1) и прибавляя к 3-й, обнулив таким образом элементы 2-го выделенного (разрешающего) столбца, или по формулам треугольника
Описание слайда:
Можно рассчитывать элементы строк методом Жордана-Гаусса, домножая 1-ю строку на (-0,5) и прибавляя ее ко 2-й, а затем на(-1) и прибавляя к 3-й, обнулив таким образом элементы 2-го выделенного (разрешающего) столбца, или по формулам треугольника

Слайд 33


Элементы 2-ой строки получаем по методу Жордана-Гаусса (или по формулам треугольника)
Описание слайда:
Элементы 2-ой строки получаем по методу Жордана-Гаусса (или по формулам треугольника)

Слайд 34


Аналогично рассчитываем элементы 3-й строки. Значения нового опорного плана рассчитываем по формулам: После чего заполняем таблицу 1.
Описание слайда:
Аналогично рассчитываем элементы 3-й строки. Значения нового опорного плана рассчитываем по формулам: После чего заполняем таблицу 1.

Слайд 35


Таблица 1.
Описание слайда:
Таблица 1.

Слайд 36


Проверим план на оптимальность. Вычислим симплекс-разности.
Описание слайда:
Проверим план на оптимальность. Вычислим симплекс-разности.

Слайд 37


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

Слайд 38


Выводится из базиса вектор , которому соответствует минимальное оценочное отношение 70. Переходим к следующему опорному плану. Вводим в базис вектор , делим разрешающую строку на разрешающий элемент и заполняем 3-ю строку таблицы 2. После чего методом Жордана-Гаусса домножаем эту строку на (-0,286) и прибавляем к первой, затем домножим эту строку на (-1,857) и прибавляем ко второй.
Описание слайда:
Выводится из базиса вектор , которому соответствует минимальное оценочное отношение 70. Переходим к следующему опорному плану. Вводим в базис вектор , делим разрешающую строку на разрешающий элемент и заполняем 3-ю строку таблицы 2. После чего методом Жордана-Гаусса домножаем эту строку на (-0,286) и прибавляем к первой, затем домножим эту строку на (-1,857) и прибавляем ко второй.

Слайд 39


Таблица 2
Описание слайда:
Таблица 2

Слайд 40


Вычисляем симплекс-разности. План оптимален. Значение целевой функции
Описание слайда:
Вычисляем симплекс-разности. План оптимален. Значение целевой функции

Скачать

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