Метод проектов
<<  Метод тренингов Методы радиометрии  >>
Симплекс-метод
Симплекс-метод
Симплекс-метод с естественным базисом
Симплекс-метод с естественным базисом
В этом случае каноническая задача линейного программирования должна
В этом случае каноническая задача линейного программирования должна
Рассмотрим задачу, для которой это возможно
Рассмотрим задачу, для которой это возможно
Перепишем ЗЛП в векторной форме: найти максимум функции при условиях
Перепишем ЗЛП в векторной форме: найти максимум функции при условиях
Так как , то по определению опорного плана , где последние компоненты
Так как , то по определению опорного плана , где последние компоненты
План, при котором целевая функция ЗЛП принимает свое максимальное
План, при котором целевая функция ЗЛП принимает свое максимальное
Признак оптимальности
Признак оптимальности
2)Если для некоторого j=k и среди чисел нет положительных, т.е. , то
2)Если для некоторого j=k и среди чисел нет положительных, т.е. , то
3)Если же для некоторого k выполняется условие , но среди чисел есть
3)Если же для некоторого k выполняется условие , но среди чисел есть
Симплекс-таблица
Симплекс-таблица
Симплекс-таблица
Симплекс-таблица
Здесь , т.е. Значение После заполнения таблицы исходный опорный план
Здесь , т.е. Значение После заполнения таблицы исходный опорный план
1) Все Тогда составленный план оптимален
1) Все Тогда составленный план оптимален
Этот переход осуществляется исключением из базиса какого-нибудь из
Этот переход осуществляется исключением из базиса какого-нибудь из
Из базиса выводится вектор , который дает наименьшее положительное
Из базиса выводится вектор , который дает наименьшее положительное
Строка называется разрешающей строкой, элементы этой строки в новой
Строка называется разрешающей строкой, элементы этой строки в новой
Элементы i-й строки –по формулам
Элементы i-й строки –по формулам
Значение нового опорного плана считают по формулам Значение целевой
Значение нового опорного плана считают по формулам Значение целевой
Процесс решения продолжаем до получения оптимального плана либо до
Процесс решения продолжаем до получения оптимального плана либо до
Алгоритм применения симплекс-метода
Алгоритм применения симплекс-метода
4)Находят направляющие столбец и строку
4)Находят направляющие столбец и строку
Пример
Пример
Решение
Решение
Из коэффициентов при неизвестных и свободных членов составим векторы
Из коэффициентов при неизвестных и свободных членов составим векторы
Составим симплекс-таблицу и проверим план на оптимальность
Составим симплекс-таблицу и проверим план на оптимальность
Составим теперь нулевую симплексную таблицу
Составим теперь нулевую симплексную таблицу
Таблица 0
Таблица 0
Определяем разрешающий элемент симплексной таблицы
Определяем разрешающий элемент симплексной таблицы
Разрешающим элементом является
Разрешающим элементом является
Элементы направляющей строки в новой таблице вычисляем, деля эту
Элементы направляющей строки в новой таблице вычисляем, деля эту
Можно рассчитывать элементы строк методом Жордана-Гаусса, домножая 1-ю
Можно рассчитывать элементы строк методом Жордана-Гаусса, домножая 1-ю
Элементы 2-ой строки получаем по методу Жордана-Гаусса (или по
Элементы 2-ой строки получаем по методу Жордана-Гаусса (или по
Аналогично рассчитываем элементы 3-й строки
Аналогично рассчитываем элементы 3-й строки
Таблица 1
Таблица 1
Проверим план на оптимальность
Проверим план на оптимальность
В первом столбце матрицы имеется отрицательная оценка
В первом столбце матрицы имеется отрицательная оценка
Выводится из базиса вектор , которому соответствует минимальное
Выводится из базиса вектор , которому соответствует минимальное
Таблица 2
Таблица 2
Вычисляем симплекс-разности
Вычисляем симплекс-разности

Презентация на тему: «Симплекс-метод». Автор: Admin. Файл: «Симплекс-метод.ppt». Размер zip-архива: 668 КБ.

Симплекс-метод

содержание презентации «Симплекс-метод.ppt»
СлайдТекст
1 Симплекс-метод

Симплекс-метод

Лекции 6, 7

2 Симплекс-метод с естественным базисом

Симплекс-метод с естественным базисом

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

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

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

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

4 Рассмотрим задачу, для которой это возможно

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

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

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

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

Здесь

6 Так как , то по определению опорного плана , где последние компоненты

Так как , то по определению опорного плана , где последние компоненты

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

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

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

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

8 Признак оптимальности

Признак оптимальности

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

9 2)Если для некоторого j=k и среди чисел нет положительных, т.е. , то

2)Если для некоторого j=k и среди чисел нет положительных, т.е. , то

целевая функция ЗЛП не ограничена на множестве ее планов, т.е. ЗЛП не имеет решения, так как нет конечного оптимума.

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

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

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

11 Симплекс-таблица

Симплекс-таблица

12 Симплекс-таблица

Симплекс-таблица

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

13 Здесь , т.е. Значение После заполнения таблицы исходный опорный план

Здесь , т.е. Значение После заполнения таблицы исходный опорный план

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

14 1) Все Тогда составленный план оптимален

1) Все Тогда составленный план оптимален

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

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

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

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

16 Из базиса выводится вектор , который дает наименьшее положительное

Из базиса выводится вектор , который дает наименьшее положительное

оценочное отношение для всех , т.е. минимум достигается при i=r. Число называется разрешающим элементом.

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

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

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

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

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

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

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

функции при переходе от одного опорного плана к другому , улучшенному, изменяется по формуле

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

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

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

21 Алгоритм применения симплекс-метода

Алгоритм применения симплекс-метода

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

22 4)Находят направляющие столбец и строку

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

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

23 Пример

Пример

Решить симплекс-методом ЗЛП

24 Решение

Решение

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

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

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

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

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

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

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

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

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

28 Таблица 0

Таблица 0

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

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

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

30 Разрешающим элементом является

Разрешающим элементом является

Значение целевой функции в следующей симплекс-таблице будет равно:

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

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

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

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

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

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

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

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

формулам треугольника)

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

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

Значения нового опорного плана рассчитываем по формулам: После чего заполняем таблицу 1.

35 Таблица 1

Таблица 1

36 Проверим план на оптимальность

Проверим план на оптимальность

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

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

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

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

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

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

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

39 Таблица 2

Таблица 2

40 Вычисляем симплекс-разности

Вычисляем симплекс-разности

План оптимален. Значение целевой функции

«Симплекс-метод»
http://900igr.net/prezentacija/pedagogika/simpleks-metod-104983.html
cсылка на страницу

Метод проектов

8 презентаций о методе проектов
Урок

Педагогика

135 тем
Слайды