Презентация СИМПЛЕКС-МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ онлайн

Содержание слайда: СИМПЛЕКС-МЕТОД РЕШЕНИЯ ЗАДАЧ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

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

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

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

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

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

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

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

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

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

Содержание слайда:

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

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

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

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

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

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

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

Содержание слайда: Джордж Данциг, 1947 Джордж Данциг, 1947

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

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

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

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

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

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

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

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

Содержание слайда: Рассмотрим задачу ЛП в канонической форме: Рассмотрим задачу ЛП в канонической форме: Пусть (иначе, умножим соответ-ствующее уравнение на -1); уравнения системы ограничений линейно независимы; ; система ограничений совместна

Содержание слайда:

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

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

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда:

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

Содержание слайда:

Содержание слайда:

Содержание слайда:

Содержание слайда: Ведущий (разрешающий) элемент

Содержание слайда:

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

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

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

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

Содержание слайда: Все элементы ведущей строки делятся на разрешающий элемент

Содержание слайда: Все элементы ведущей строки делятся на разрешающий элемент

Содержание слайда: Оставшиеся элементы симплексной таблицы преобразуются по схеме «прямоугольника»

Содержание слайда:

Содержание слайда: Опорное решение, соответствующее таблице Значение целевой функции на этом базисе L=-90.

Содержание слайда: Переход к следующей итерации осуществляется возвратом к шагу 2.