Презентация Симплекс-метод Лекции 6, 7 онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Симплекс-метод Лекции 6, 7 абсолютно бесплатно. Урок-презентация на эту тему содержит всего 40 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:40 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:0.97 MB
- Просмотров:122
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: Симплекс-метод
Лекции 6, 7
№2 слайд
Содержание слайда: Симплекс-метод с естественным базисом
Симплекс –метод основан на переходе от одного опорного плана к другому, при котором значение целевой функции возрастает при условии, что задача имеет оптимальный план и каждый опорный план является невырожденным.
Этот переход возможен, если известен какой-либо опорный план.
№3 слайд
Содержание слайда: В этом случае каноническая задача линейного программирования должна содержать единичную подматрицу порядка m
Тогда очевиден первоначальный опорный план( неотрицательное базисное решение системы ограничений КЗЛП).
№4 слайд
Содержание слайда: Рассмотрим задачу, для которой это возможно.
Пусть требуется найти максимальное значение функции
при условиях
Здесь -заданные постоянные числа, причем
№5 слайд
Содержание слайда: Перепишем ЗЛП в векторной форме: найти максимум функции
при условиях
Здесь
№6 слайд
Содержание слайда: Так как ,
то по определению опорного плана
,
где последние компоненты вектора равны нулю, является опорным планом
Опорный план называется невырожденным, если он содержит m положительных компонент. В противном случае он называется вырожденным.
№7 слайд
Содержание слайда: План, при котором целевая функция ЗЛП принимает свое максимальное
(минимальное ) значение , называется оптимальным
Этот план определяется системой единичных векторов , которые образуют базис m-векторного пространства.
Проверка на оптимальность опорного плана происходит с помощью критерия оптимальности.
№8 слайд
Содержание слайда: Признак оптимальности.
1)Опорный план ЗЛП является оптимальным, если
для любого .
№9 слайд
Содержание слайда: 2)Если для некоторого j=k
и среди чисел
нет положительных, т.е. , то целевая функция ЗЛП не ограничена на множестве ее планов, т.е. ЗЛП не имеет решения, так как нет конечного оптимума.
№10 слайд
Содержание слайда: 3)Если же для некоторого k выполняется условие , но среди чисел есть положительные, т.е. не все , то можно получить новый опорный план, для которого значения целевой функции
.
На основании признака оптимальности делаем вывод о целесообразности перехода к новому опорному плану.
№11 слайд
Содержание слайда: Симплекс-таблица
№12 слайд
Содержание слайда: Симплекс-таблица
В столбце Сб записывают коэффициенты при неизвестных целевой функции, имеющие те же индексы, что и векторы данного базиса.
В столбце -положительные компоненты исходного опорного плана, в нем же в результате вычислений получают положительные компоненты оптимального плана.
Первые m строк заполняют по исходным данным задачи, а показатели (m+1)-й строки вычисляют. В этой строке в столбце вектора записывают значение целевой функции, которое она принимает при данном опорном плане, а в столбце вектора - значение
№13 слайд
Содержание слайда: Здесь , т.е.
Значение
После заполнения таблицы исходный опорный план проверяют на оптимальность. Для этого просматривают элементы (m+1)-й строки. Может иметь место один из 3-х случаев.
№14 слайд
Содержание слайда: 1) Все Тогда составленный план оптимален.
2) для некоторого j и все соответствующие этому j . Тогда целевая функция неограничена.
3) для некоторых индексов j и для каждого такого j по крайней мере одно из чисел положительно. Здесь можно перейти к новому опорному плану.
№15 слайд
Содержание слайда: Этот переход осуществляется исключением из базиса какого-нибудь из векторов и включением в него другого.
В базис вводим вектор , давший минимальную отрицательную величину симплекс-разности
№16 слайд
Содержание слайда: Из базиса выводится вектор , который дает наименьшее положительное оценочное отношение
для всех , т.е. минимум достигается при i=r.
Число называется разрешающим элементом.
№17 слайд
Содержание слайда: Строка называется разрешающей строкой, элементы этой строки в новой симплекс-таблице вычисляются по методу Жордана-Гаусса, т.е. по формулам:
№18 слайд
Содержание слайда: Элементы i-й строки –по формулам
№19 слайд
Содержание слайда: Значение нового опорного плана считают по формулам
Значение целевой функции при переходе от одного опорного плана к другому , улучшенному, изменяется по формуле
№20 слайд
Содержание слайда: Процесс решения продолжаем до получения оптимального плана либо до установления неограниченности ЦФ.
Если среди оценок оптимального плана нулевые только оценки , соответствующие базисным векторам, то оптимальный план единствен.
Если же нулевая оценка соответствует вектору, не входящему в базис, то в общем случае это означает, что опорный план не единствен.
№21 слайд
Содержание слайда: Алгоритм применения симплекс-метода
1)Находят опорный план.
2)Составляют симплекс-таблицу.
3)Выясняют, имеется ли хотя бы одна отрицательная оценка. Если нет, то найденный опорный план оптимален. Если же есть отрицательные оценки, то либо устанавливают неразрешимость задачи, либо переходят к новому опорному плану.
№22 слайд
Содержание слайда: 4)Находят направляющие столбец и строку. Направляющий столбец определяется наибольшим по абсолютной величине отрицательным числом , а направляющая строка—минимальным числом Q.
5)Определяют положительные компоненты нового опорного плана. Составляется новая таблица.
6)Проверяют найденный опорный план на оптимальность.
№23 слайд
Содержание слайда: Пример.
Решить симплекс-методом ЗЛП
№24 слайд
Содержание слайда: Решение.
Приведем задачу к каноническому виду, введя новые переменные
В целевую функцию эти переменные войдут с нулевыми коэффициентами:
№25 слайд
Содержание слайда: Из коэффициентов при неизвестных и свободных членов составим векторы
Единичные векторы образуют единичную подматрицу и составляют базис первоначального плана. Свободные неизвестные приравниваются к нулю.
Получаем первоначальный опорный план:
Х= (0;0;350;240;150).
№26 слайд
Содержание слайда: Составим симплекс-таблицу и проверим план на оптимальность. В нашем примере
Для заполнения последней строки таблицы сразу вычислим симплекс-разности
Для этого поочередно умножаем столбец Сб на соответствующие элементы каждого столбца
№27 слайд
Содержание слайда: Составим теперь нулевую симплексную таблицу
№28 слайд
Содержание слайда: Таблица 0.
№29 слайд
Содержание слайда: Определяем разрешающий элемент симплексной таблицы. Т.к. имеется 2 отрицательные оценки, то выбираем ту, что дает максимальную по абсолютной величине отрицательную оценку, т. е. -20.
Это означает, что в базис включается
вектор , а исключается из базиса тот вектор, которому соответствует
.
№30 слайд
Содержание слайда: Разрешающим элементом
является .
Значение целевой функции в следующей симплекс-таблице будет равно:
№31 слайд
Содержание слайда: Элементы направляющей строки в новой таблице вычисляем, деля эту строку на ведущий элемент(в том числе и клетку в столбце план):
№32 слайд
Содержание слайда: Можно рассчитывать элементы строк методом Жордана-Гаусса, домножая 1-ю строку на (-0,5) и прибавляя ее ко 2-й, а затем на(-1) и прибавляя к 3-й, обнулив таким образом элементы 2-го выделенного (разрешающего) столбца, или по формулам треугольника
№33 слайд
Содержание слайда: Элементы 2-ой строки получаем по методу Жордана-Гаусса (или по формулам треугольника)
№34 слайд
Содержание слайда: Аналогично рассчитываем элементы 3-й строки.
Значения нового опорного плана рассчитываем по формулам:
После чего заполняем таблицу 1.
№35 слайд
Содержание слайда: Таблица 1.
№36 слайд
Содержание слайда: Проверим план на оптимальность.
Вычислим симплекс-разности.
№37 слайд
Содержание слайда: В первом столбце матрицы имеется отрицательная оценка. План не оптимален, но его можно улучшить , включив в базис вектор . Найдем минимальное оценочное отношение:
№38 слайд
Содержание слайда: Выводится из базиса вектор , которому соответствует минимальное оценочное отношение 70. Переходим к следующему опорному плану. Вводим в базис вектор , делим разрешающую строку на разрешающий элемент и заполняем 3-ю строку таблицы 2. После чего методом Жордана-Гаусса домножаем эту строку на (-0,286) и прибавляем к первой, затем домножим эту строку на (-1,857) и прибавляем ко второй.
№39 слайд
Содержание слайда: Таблица 2
№40 слайд
Содержание слайда: Вычисляем симплекс-разности.
План оптимален. Значение целевой функции
Скачать все slide презентации Симплекс-метод Лекции 6, 7 одним архивом:
