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

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


Для правообладателей

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

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

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

Содержание

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

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

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

–метод основан на переходе от одного опорного плана к

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

Слайд 3 В этом случае каноническая задача

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

линейного программирования должна содержать единичную подматрицу порядка m

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

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

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

Пусть требуется найти максимальное значение функции

при

условиях










Здесь -заданные постоянные числа, причем

Слайд 5 Перепишем ЗЛП в векторной форме: найти

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

максимум функции



при условиях



Здесь

Слайд 6 Так как

Так как

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

Слайд 7 План, при котором

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

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

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

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

Признак оптимальности. 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)Находят опорный план.

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

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

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

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

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

столбец определяется наибольшим по абсолютной величине отрицательным числом

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

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

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

Слайд 24 Решение.
Приведем задачу к каноническому виду,

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

введя новые переменные
В целевую функцию эти

переменные войдут с нулевыми коэффициентами:

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

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

членов составим векторы




Единичные векторы образуют единичную подматрицу

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

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

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

оптимальность. В нашем примере



Для заполнения последней строки таблицы сразу вычислим симплекс-разности


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

Слайд 27






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

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

Слайд 28 Таблица 0.

Таблица 0.

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

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

имеется 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

  • Имя файла: simpleks-metod.pptx
  • Количество просмотров: 98
  • Количество скачиваний: 3