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