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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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