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