Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Обратная связь

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

Содержание

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

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

В этом случае каноническая задача линейного программирования должна содержать

Рассмотрим задачу, для которой это возможно. Пусть требуется найти

Перепишем ЗЛП в векторной форме: найти максимум функции

План, при котором целевая функция ЗЛП принимает

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

3)Если же для некоторого k выполняется условие

Симплекс-таблица В столбце Сб записывают коэффициенты при неизвестных целевой функции, имеющие

Этот переход осуществляется исключением из базиса какого-нибудь из векторов и

Из базиса выводится вектор , который дает

Строка называется разрешающей строкой, элементы этой строки в

Значение нового опорного плана считают по формулам Значение целевой

Процесс решения продолжаем до получения оптимального плана либо

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

4)Находят направляющие столбец и строку. Направляющий столбец определяется наибольшим по

Решение. Приведем задачу к каноническому виду, введя новые переменные

Из коэффициентов при неизвестных и свободных членов составим векторы

Составим симплекс-таблицу и проверим план на оптимальность. В нашем примере

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

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

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

Можно рассчитывать элементы строк методом Жордана-Гаусса, домножая 1-ю строку на

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

Аналогично рассчитываем элементы 3-й строки. Значения нового опорного плана

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

В первом столбце матрицы имеется отрицательная оценка. План не оптимален,

Выводится из базиса вектор , которому соответствует

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

Слайды презентации

Слайд 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)Находят опорный план.

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

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-й строки.

Аналогично рассчитываем элементы 3-й строки. Значения нового опорного плана рассчитываем

Значения нового опорного плана рассчитываем по формулам:

После

чего заполняем таблицу 1.

Слайд 35 Таблица 1.

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

Слайд 37
В первом столбце матрицы имеется отрицательная

оценка. План не оптимален, но его можно улучшить ,

включив в базис вектор . Найдем минимальное оценочное отношение:

Слайд 38
Выводится из базиса вектор

Выводится из базиса вектор , которому соответствует минимальное оценочное

, которому соответствует минимальное оценочное отношение 70. Переходим

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