СИМПЛЕКС-МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Содержание

Слайд 2

Элементы линейной алгебры и геометрии выпуклых множеств Теоретические основы методов линейного программирования

Элементы линейной алгебры и геометрии выпуклых множеств
Теоретические основы методов линейного

программирования
Слайд 3

Элементы линейной алгебры Пусть дана система линейных уравнений c переменными (*)

Элементы линейной алгебры

Пусть дана система линейных уравнений c переменными
(*)

- ранг матрицы, то есть максимальное число независимых уравнений системы. Пусть .
Пусть в (*) все уравнения системы линейно независимы, то есть . Соответственно
Слайд 4

Элементы линейной алгебры Пусть дана система линейных уравнений c переменными (*)

Элементы линейной алгебры

Пусть дана система линейных уравнений c переменными
(*)

- ранг матрицы, то есть максимальное число независимых уравнений системы. Пусть .
Пусть в (*) все уравнения системы линейно независимы, то есть . Соответственно
Слайд 5

Элементы линейной алгебры Определение. Любые переменных называются базисными (или основными), если

Элементы линейной алгебры

Определение. Любые переменных называются базисными (или основными), если определитель

матрицы (базисный минор), составленный из коэффициентов при них, отличен от нуля. Остальные переменных называются свободными (или неосновными).
Слайд 6

Элементы линейной алгебры Определение. Решение системы называется допустимым, если оно содержит

Элементы линейной алгебры

Определение. Решение системы называется допустимым, если оно содержит только

неотрицательные компоненты, в противном случае решение называется недопустимым. Определение. Решение системы, в котором все свободных переменных равны нулю, называется базисным. В задачах линейного программирования особый интерес представляют допустимые базисные решения или опорные планы.
Слайд 7

Элементы линейной алгебры Определение. Решение системы называется допустимым, если оно содержит

Элементы линейной алгебры

Определение. Решение системы называется допустимым, если оно содержит только

неотрицательные компоненты, в противном случае решение называется недопустимым. Определение. Решение системы, в котором все свободных переменных равны нулю, называется базисным. В задачах линейного программирования особый интерес представляют допустимые базисные решения или опорные планы.
Слайд 8

Элементы линейной алгебры Определение. Решение системы называется допустимым, если оно содержит

Элементы линейной алгебры

Определение. Решение системы называется допустимым, если оно содержит только

неотрицательные компоненты, в противном случае решение называется недопустимым. Определение. Решение системы, в котором все свободных переменных равны нулю, называется базисным. В задачах линейного программирования особый интерес представляют допустимые базисные решения или опорные планы. Определение. Базисное решение, в котором хотя бы одна базисных переменных равна нулю, называется вырожденным.
Слайд 9

Элементы линейной алгебры Определение. Решение системы называется допустимым, если оно содержит

Элементы линейной алгебры

Определение. Решение системы называется допустимым, если оно содержит только

неотрицательные компоненты, в противном случае решение называется недопустимым. Определение. Решение системы, в котором все свободных переменных равны нулю, называется базисным. В задачах линейного программирования особый интерес представляют допустимые базисные решения или опорные планы. Определение. Базисное решение, в котором хотя бы одна базисных переменных равна нулю, называется вырожденным.
Слайд 10

Элементы геометрии выпуклых множеств Определение. Множество точек называется выпуклым, если оно

Элементы геометрии выпуклых множеств

Определение. Множество точек называется выпуклым, если оно вместе

с любыми двумя своими точками содержит весь отрезок соединяющий эти точки.
Слайд 11

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

Элементы геометрии выпуклых множеств

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

ее окрестности содержатся точки только данного множества. Определение. Точка множества называется граничной, если в любой ее окрестности содержатся как точки, принадлежащие данному множеству, так и точки, не принадлежащие ему. Определение. Точка множества называется угловой или крайней, если она не является внутренней ни для какого отрезка целиком принадлежащего данному множеству.
Слайд 12

Элементы геометрии выпуклых множеств

Элементы геометрии выпуклых множеств

Слайд 13

Элементы геометрии выпуклых множеств Очевидно, что для выпуклого множества угловые точки

Элементы геометрии выпуклых множеств

Очевидно, что для выпуклого множества угловые точки всегда

совпадают с вершинами многоугольника, для невыпуклого множества это необязательно.
Слайд 14

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

Элементы геометрии выпуклых множеств

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

свои граничные точки. Определение. Множество точек называется ограниченным, если существует круг радиусом конечной длины с центром в любой точке множества, который полностью содержит в себе данное множество, в противном случае множество называется неограниченным.
Слайд 15

Элементы геометрии выпуклых множеств Выпуклое замкнутое множество точек пространства (плоскости) имеющее

Элементы геометрии выпуклых множеств

Выпуклое замкнутое множество точек пространства (плоскости) имеющее конечное

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

Теоретические основы методов ЛП Множество всех допустимых решений задачи линейного программирования

Теоретические основы методов ЛП

Множество всех допустимых решений задачи линейного программирования является

выпуклым, а точнее, представляет выпуклый многогранник или выпуклую многогранную область, которые называют одним термином – многогранником решений.
Слайд 17

Теоретические основы методов ЛП Теорема. Если задача линейного программирования имеет оптимальное

Теоретические основы методов ЛП

Теорема. Если задача линейного программирования имеет оптимальное решение,

то линейная функция принимает максимальное (минимальное) значение в одной из угловых точек многогранника решений. Если линейная функция принимает максимальное (минимальное) значение более чем в одной угловой точке, то она принимает его в любой точке, являющейся выпуклой линейной комбинацией этих точек.
Слайд 18

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

Теоретические основы методов ЛП

Теорема. Каждому допустимому базисному решению задачи линейного программирования

соответствует угловая точка многогранника решений, и наоборот, каждой угловой точке многогранника решений соответствует допустимое базисное решение.
Слайд 19

Теоретические основы методов ЛП Следствие. Если задача линейного программирования имеет оптимальное

Теоретические основы методов ЛП

Следствие. Если задача линейного программирования имеет оптимальное решение,

то оно совпадает, по крайней мере, с одним из ее допустимых базисных решений.
Слайд 20

Симплексный метод решения задач ЛП Джордж Данциг, 1947

Симплексный метод решения задач ЛП

Джордж Данциг, 1947

Слайд 21

Симплексный метод основывается область допустимых решений задачи линейного программирования является выпуклым

Симплексный метод основывается

область допустимых решений задачи линейного программирования является выпуклым

множеством с конечным числом угловых точек, то есть многогранником или многоугольным множеством;
оптимальным решением задачи линейного программирования является одна из угловых точек области допустимых решений;
угловые точки области допустимых решений алгебраически представляют некоторые базисные (опорные) решения системы ограничений задачи.
Слайд 22

Симплексный метод основывается область допустимых решений задачи линейного программирования является выпуклым

Симплексный метод основывается

область допустимых решений задачи линейного программирования является выпуклым

множеством с конечным числом угловых точек, то есть многогранником или многоугольным множеством;
оптимальным решением задачи линейного программирования является одна из угловых точек области допустимых решений;
угловые точки области допустимых решений алгебраически представляют некоторые базисные (опорные) решения системы ограничений задачи.
Слайд 23

Симплексный метод основывается область допустимых решений задачи линейного программирования является выпуклым

Симплексный метод основывается

область допустимых решений задачи линейного программирования является выпуклым

множеством с конечным числом угловых точек, то есть многогранником или многоугольным множеством;
оптимальным решением задачи линейного программирования является одна из угловых точек области допустимых решений;
угловые точки области допустимых решений алгебраически представляют некоторые базисные (опорные) решения системы ограничений задачи.
Слайд 24

Симплексный метод состоит в целенаправленном переборе опорных решений задачи линейного программирования.

Симплексный метод состоит

в целенаправленном переборе опорных решений задачи линейного программирования.


Так как общее число опорных решений конечно, то через определенное число шагов будет либо найдено оптимальное решение, либо установлено его отсутствие.
Чтобы получить новый опорный план, первоначальный базис преобразовывают в новый. Для этого из первоначального базиса удаляют некоторую базисную переменную и вместо нее вводят другую из группы свободных.
Слайд 25

Геометрический смысл симплексного метода состоит в последовательном переходе от одной вершины

Геометрический смысл симплексного метода

состоит в последовательном переходе от одной вершины

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

Основное содержание симплексного метода найти начальное опорное решение; осуществить переход от

Основное содержание симплексного метода

найти начальное опорное решение;
осуществить переход от одного

опорного решения к другому, на котором значение целевой функции ближе к оптимальному;
определить критерии завершения процесса решения задачи, позволяющие своевременно прекратить перебор решений на оптимальном решении или сделать заключение об отсутствии решения.
Слайд 27

Основное содержание симплексного метода найти начальное опорное решение; осуществить переход от

Основное содержание симплексного метода

найти начальное опорное решение;
осуществить переход от одного

опорного решения к другому, на котором значение целевой функции ближе к оптимальному;
определить критерии завершения процесса решения задачи, позволяющие своевременно прекратить перебор решений на оптимальном решении или сделать заключение об отсутствии решения.
Слайд 28

Основное содержание симплексного метода найти начальное опорное решение; осуществить переход от

Основное содержание симплексного метода

найти начальное опорное решение;
осуществить переход от одного

опорного решения к другому, на котором значение целевой функции ближе к оптимальному;
определить критерии завершения процесса решения задачи, позволяющие своевременно прекратить перебор решений на оптимальном решении или сделать заключение об отсутствии решения.
Слайд 29

Симплексный метод решения задач ЛП Рассмотрим задачу ЛП в канонической форме:

Симплексный метод решения задач ЛП

Рассмотрим задачу ЛП в канонической форме:
Пусть

(иначе, умножим соответ-ствующее уравнение на -1); уравнения системы ограничений линейно независимы; ; система ограничений совместна
Слайд 30

Специальная форма задачи ЛП

Специальная форма задачи ЛП


Слайд 31

Алгоритм симплекс-метода для задачи на минимум Шаг 0. Подготовительный этап. Шаг

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

Шаг 0. Подготовительный этап.
Шаг 1. Составляем

симплекс-таблицу, соответствующую специальной форме
Шаг 2. Проверка на оптимальность
Шаг 3. Проверка на неразрешимость
Шаг 4. Выбор ведущего столбца q
Шаг 5. Выбор ведущей строки p
Шаг 6. Преобразование симплексной таблицы
Шаг 7. Переход к следующей итерации осуществляется возвратом к шагу 2
Слайд 32

Шаг 0. Подготовительный этап Приводим задачу ЛП к специальной форме

Шаг 0. Подготовительный этап

Приводим задачу ЛП к специальной форме

Слайд 33

Шаг 1. Составляем симплекс-таблицу, соответствующую специальной форме

Шаг 1. Составляем симплекс-таблицу,
соответствующую специальной форме


Слайд 34

Рассмотрим реализацию метода на следующем примере:

Рассмотрим реализацию метода
на следующем примере:

Слайд 35

Слайд 36

Слайд 37

Слайд 38

Шаг 0

Шаг 0

Слайд 39

Шаг 1. Составляем симплекс-таблицу, соответствующую специальной форме

Шаг 1. Составляем симплекс-таблицу,
соответствующую специальной форме


Слайд 40

Шаг 2. Проверка на оптимальность Так как коэффициенты строки целевой функции

Шаг 2. Проверка на оптимальность


Так как коэффициенты строки целевой функции

неотрицательны, то начальное базисное решение
не является оптимальным. Значение целевой функции для этого базиса L=0.
Слайд 41

Шаг 2. Проверка на неразрешимость

Шаг 2. Проверка на неразрешимость


Слайд 42

Шаг 4. Выбор ведущего столбца q Ведущий столбец

Шаг 4. Выбор ведущего столбца q


Ведущий столбец

Слайд 43

Шаг 5. Выбор ведущей строки p Ведущая строка

Шаг 5. Выбор ведущей строки p


Ведущая строка

Слайд 44

Шаг 5. Выбор ведущей строки p Ведущий (разрешающий) элемент

Шаг 5. Выбор ведущей строки p


Ведущий (разрешающий) элемент

Слайд 45

Шаг 6. Преобразование симплексной таблицы a)

Шаг 6. Преобразование симплексной таблицы
a)


Слайд 46

Шаг 6. Преобразование симплексной таблицы б) Ведущий элемент заменяем обратной величиной

Шаг 6. Преобразование симплексной таблицы
б)


Ведущий элемент заменяем обратной величиной

Слайд 47

Шаг 6. Преобразование симплексной таблицы б) Ведущий элемент заменяем обратной величиной

Шаг 6. Преобразование симплексной таблицы
б)


Ведущий элемент заменяем обратной величиной

Слайд 48

Шаг 6. Преобразование симплексной таблицы в) Все элементы ведущего столбца делятся

Шаг 6. Преобразование симплексной таблицы
в)


Все элементы ведущего столбца делятся на

разрешающий элемент и меняют знак на противоположный
Слайд 49

Шаг 6. Преобразование симплексной таблицы в) Все элементы ведущего столбца делятся

Шаг 6. Преобразование симплексной таблицы
в)


Все элементы ведущего столбца делятся на

разрешающий элемент и меняют знак на противоположный
Слайд 50

Шаг 6. Преобразование симплексной таблицы г) Все элементы ведущей строки делятся на разрешающий элемент

Шаг 6. Преобразование симплексной таблицы
г)


Все элементы ведущей строки делятся на

разрешающий элемент
Слайд 51

Шаг 6. Преобразование симплексной таблицы г) Все элементы ведущей строки делятся на разрешающий элемент

Шаг 6. Преобразование симплексной таблицы
г)


Все элементы ведущей строки делятся на

разрешающий элемент
Слайд 52

Шаг 6. Преобразование симплексной таблицы д) Оставшиеся элементы симплексной таблицы преобразуются по схеме «прямоугольника»

Шаг 6. Преобразование симплексной таблицы
д)


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

схеме «прямоугольника»
Слайд 53

Шаг 6. Преобразование симплексной таблицы д) Схема прямоугольника

Шаг 6. Преобразование симплексной таблицы
д) Схема прямоугольника

Слайд 54

Шаг 6. Преобразование симплексной таблицы д) Опорное решение, соответствующее таблице Значение

Шаг 6. Преобразование симплексной таблицы
д)


Опорное решение, соответствующее таблице
Значение целевой

функции на этом базисе
L=-90.
- Предыдущая
Речевая коммуникация в деловой сфере
Следующая -
Расчет линейных электрических цепей с синусоидальным источником ЭДС

Похожие презентации

Единая школьная карта
Технологии разработки ПО. Основные понятия и определения
НОВАЯ ЭКОНОМИЧЕСКАЯ АССОЦИАЦИЯ ВТОРОЙ РОССИЙСКИЙ ЭКОНОМИЧЕСКИЙ КОНГРЕСС БОРЬБА С УКЛОНЕНИЕМ ОТ УПЛАТЫ НАЛОГОВ И «НАЛОГОВЫМИ
CSS (Cascading Style Sheets)
құндылық
Мохандас Карамчанд Ганди
«Есть такая профессия – ученик»
Реабилитация. Возмещение вреда
Общие сведения о языке программирования Паскаль
Заболевания щитовидной железы
Электро Механик
Роспись яиц
Презентация Социально-обеспечительные правоотношения
«TIS-Трудозатраты» Система учета занятости сотрудников. - презентация
умножение и деление на 8 - презентация для начальной школы
Web-программирование. Лекция 5. python 3 (часть 2)
Презентация "Макроэкономическая нестабильность и ее основные проявления" - скачать презентации по Экономике
Стратегии тестирования
«Закрепление внетабличного деления и умножения» Математика, 3 класс Учитель начальных классов Симбирева Дарья Викторовна, ГБОУ
Диаграммы классов. Объектно- ориентированное программирование. (Лекция 5)
Комплексное оснащение предприятий ресторанного бизнеса на примере овощерезки Robot Coupe CL 50
Христианская апологетика и история
Сервис Фото для участников MyWeb Фотохостинг на MyWeb http://myweb.kz/
Прогнозирование денежного потока инвестиционного проекта
Анализ алгоритмов. (Лекция 16)
The military factor in contemporary international relation
Описание слайда: Методики определения потребности в лекарственных средствах.
ЗАЩИТА АНАЛИТИЧЕСКОГО ОТЧЁТА Юдиной Ирины Николаевны воспитатель ГПД
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть