Симплекс-метод решения задач линейного программирования

Нажмите для полного просмотра!

Симплекс-метод решения задач линейного программирования, слайд №2

Симплекс-метод решения задач линейного программирования, слайд №3

Симплекс-метод решения задач линейного программирования, слайд №4

Симплекс-метод решения задач линейного программирования, слайд №5

Симплекс-метод решения задач линейного программирования, слайд №6

Симплекс-метод решения задач линейного программирования, слайд №7

Симплекс-метод решения задач линейного программирования, слайд №8

Симплекс-метод решения задач линейного программирования, слайд №9

Симплекс-метод решения задач линейного программирования, слайд №10

Симплекс-метод решения задач линейного программирования, слайд №11

Симплекс-метод решения задач линейного программирования, слайд №12

Симплекс-метод решения задач линейного программирования, слайд №13

Симплекс-метод решения задач линейного программирования, слайд №14

Симплекс-метод решения задач линейного программирования, слайд №15

Симплекс-метод решения задач линейного программирования, слайд №16

Симплекс-метод решения задач линейного программирования, слайд №17

Симплекс-метод решения задач линейного программирования, слайд №18

Симплекс-метод решения задач линейного программирования, слайд №19

Симплекс-метод решения задач линейного программирования, слайд №20

Симплекс-метод решения задач линейного программирования, слайд №21

Симплекс-метод решения задач линейного программирования, слайд №22

Симплекс-метод решения задач линейного программирования, слайд №23

Симплекс-метод решения задач линейного программирования, слайд №24

Симплекс-метод решения задач линейного программирования, слайд №25

Симплекс-метод решения задач линейного программирования, слайд №26

Симплекс-метод решения задач линейного программирования, слайд №27

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Симплекс-метод решения задач линейного программирования. Доклад-сообщение содержит 27 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Слайд 2

Описание слайда:

Содержание Определение К-матрицы в КЗЛП Переход от одной К-матрицы КЗЛП к другой К-матрице Симплекс-разность К-матрицы КЗЛП Способ построения опорного плана, более близкого к оптимальному Критерий оптимальности опорного плана Критерий отсутствия конечного решения Алгоритм симплекс-метода Пример 1 Пример 2

Слайд 3

Описание слайда:

Пусть требуется решить задачу (1) Или (2)

Слайд 4

Описание слайда:

Так как решением задачи (2) является крайняя точка множества Р ее допустимых решений, или, что то же самое, неотрицательное базисное решение системы линейных уравнений , то метод решения задачи (1) должен содержать 4 момента: Так как решением задачи (2) является крайняя точка множества Р ее допустимых решений, или, что то же самое, неотрицательное базисное решение системы линейных уравнений , то метод решения задачи (1) должен содержать 4 момента: 1) обоснование способа перехода от одного опорного плана (К-матрицы) к другому; 2) указание признака оптимальности, позволяющего проверить, является ли данный опорный план оптимальным; 3) указание способа построения нового опорного плана, более близкого к оптимальному; 4) указание признака отсутствия конечного решения.

Слайд 5

Описание слайда:

Определение К-матрицы в КЗЛП Рассмотрим каноническую задачу линейного программирования (КЗЛП): Будем считать, что ранг матрицы А равен m, причем m

Слайд 6

Описание слайда:

Переход от одной К-матрицы ЗЛП к другой К-матрице. Пусть известна К-матрица (3) Обозначим через вектор номеров базисных (единичных) столбцов матрицы , - вектор, компоненты которого есть базисные компоненты опорного плана, определяемого матрицей , и могут быть отличны от нуля.

Слайд 7

Описание слайда:

Слайд 8

Описание слайда:

Слайд 9

Описание слайда:

Слайд 10

Описание слайда:

Симплекс-разность К-матриц ЗЛП. Изменение функции при переходе от одной К-матрицы к другой.

Слайд 11

Описание слайда:

Слайд 12

Описание слайда:

Способ построения опорного плана (матрицы ), более близкого к оптимальному, чем

Слайд 13

Описание слайда:

Слайд 14

Описание слайда:

Критерий оптимальности опорного плана Теорема 3 Пусть все симплекс - разности матрицы неотрицательные. Тогда опорный план , определяемый матрицей , является оптимальным. Доказательство. По условиям теоремы или (8) Пусть Произвольный план ЗЛП. Умножим левую и правую части (8) на , тогда в силу неотрицательности получим (9)

Слайд 15

Описание слайда:

Согласно (9) имеем: Согласно (9) имеем: или Что и доказывает теорему.

Слайд 16

Описание слайда:

Критерий отсутствия конечного решения. Теорема 4 Пусть в матрице есть , и в столбце ( , ) нет ни одного положительного элемента. Тогда ЗЛП (1) не имеет конечного решения. Доказательство. Пусть К-я симплекс-разность матрицы (10) и все (11) Матрица определяет опорный план

Слайд 17

Описание слайда:

Рассмотрим вектор Рассмотрим вектор у которого где -любое положительное число. Остальные n-m+1 компонент вектора положим равными нулю. В силу условия (11) компоненты вектора неотрицательны. Легко убедиться в том, что компоненты вектора удовлетворяют и функциональным ограничениям ЗЛП, т.е. вектор - план ЗЛП при любом положительном .

Слайд 18

Описание слайда:

Имеем: Имеем: Или окончательно (12) Т.к. , то из (12) следует, что для любого числа М>0 всегда можно найти план ЗЛП, для которого т.е. линейная форма не ограничена сверху на множестве планов. Терема доказана.

Слайд 19

Описание слайда:

Пример 1 Симплекс-методом решить ЗЛП: (1) (2)

Слайд 20

Описание слайда:

Приводим систему линейных неравенств (2) к каноническому виду, вводя в каждое неравенство дополнительную переменную Приводим систему линейных неравенств (2) к каноническому виду, вводя в каждое неравенство дополнительную переменную , . Получим систему линейных уравнений: (3)

Слайд 21

Описание слайда:

Целевая функция (1) будет иметь вид Целевая функция (1) будет иметь вид Расширенная матрица системы линейных уравнений (3) является исходной К-матрицей ЗЛП, которая определяет исходный опорный план:

Слайд 22

Описание слайда:

Введём следующие обозначения: Введём следующие обозначения: S-номер итерации i-номера строк таблицы -номера столбцов, образующих единичную подматрицу -коэффициенты целевой функции при столбцах, образующих единичную подматрицу -соответствуют переменным задачи -сначала содержит правые части системы уравнений , в конце алгоритма - искомые значения переменных -для вычисления значений

Слайд 23

Описание слайда:

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

Слайд 24

Описание слайда:

На второй итерации S=2, все следовательно, опорный план На второй итерации S=2, все следовательно, опорный план определяемый К-матрицей , оптимальный, Оптимальное значение линейной формы равно:

Слайд 25

Описание слайда:

Пример 2 Симплекс-методом решить ЗЛП: (4) (5) Приводим ЗЛП (4-5) к каноническому виду (6)

Слайд 26

Описание слайда:

Результаты последовательных итераций запишем в симплекс-таблицу. Результаты последовательных итераций запишем в симплекс-таблицу.

Слайд 27

Описание слайда:

Из симплекс-таблице при S=2 следует, что согласно шагу 3 Из симплекс-таблице при S=2 следует, что согласно шагу 3 симплекс-алгоритма данная ЗЛП не имеет конечного решения, т.к. отрицательная симплекс-разность соответствует столбцу , все элементы которого неположительны. Итак,