2.Симплексный метод решения задач линейного программирования.
Симплексный метод – это метод целенаправленного перебора опорных решений задачи линейного программирования. Он позволяет на конечное число шагов расчета либо найти оптимальное решение, либо установить, что оптимального решения не существует.
Основное содержание метода состоит в следующем:
Указать способ нахождения начального опорного решения.
Указать способ перехода от одного опорного решения к другому, на котором значение целевой функции ближе к оптимальному.
Задать критерии, которые позволяют своевременно прекратить перебор решений или сделать заключение об отсутствии решения.
2.1 Нахождение начального опорного решения и переход к новому опорному решению.
Пусть имеется задача линейного программирования в канонической форме:
(
2.1.1)
(2.1.2)
(2.1.3)
Если в каком-либо уравнении правая часть отрицательна, то это уравнение нужно умножить на -1.
Для нахождения опорного решения воспользуемся тем, что любое допустимое базисное решение является опорным. Найдем базисное решение методом Жордана-Гаусса. При этом разрешающие элементы для всех преобразований Жордана будем выбирать так, чтобы правые части уравнений системы оставались неотрицательными. Тогда найденное базисное решение будет допустимым, т.е. опорным.
Получим правило выбора разрешающих элементов для преобразований Жордана, при котором правые части системы уравнений остаются неотрицательными.
Пусть разрешающим элементом для
преобразования Жордана является
коэффициент
при неизвестной
в уравнении с номером l.
В результате преобразования Жордана
правые части уравнений, как известно,
пересчитываются по следующим формулам:
i=1,2,…,m, i≠l.
Для того чтобы правая часть
уравнения с разрешающим элементом
оставалась неотрицательной, должно
выполняться неравенство:
Т.к.
,
то первое условие для разрешающего
элемента
состоит в том, что он должен быть
положительным, т.е.
≥0.
2. Неотрицательными также должны быть правые части остальных уравнений, т.е.
i=1,2,…,m, i≠l.
Для получения требований, налагаемых на разрешаемый элемент , рассмотрим два случая:
А) если
,
то в силу того, что
≥0,
без дополнительных условий
Б) если же
>
,
то неравенство
поделим на
получим
.
Данное неравенство должно выполняться
для любого уравнения с номером I,
в котором
.
Для удобства вычислений вводят
вспомогательный параметр
.
при
>
.
(2.1.4)
Здесь k – номер вектора
условия
,
вводимого в базис (выбираемого столбца
матрицы системы ограничений), а l
– номер вектора
,
выводимого из базиса (номер строки
матрицы, в которой следует выбирать
разрешающий элемент для преобразований
Жордана ).
С помощью данного условия можно выбрать разрешающий элемент в любом столбце k матрицы системы ограничений, в котором имеется хотя бы один положительный элемент. Если нарушить это условие при выборе разрешающего элемента, в правой части системы появятся отрицательные величины.
Используя данное условие, можно найти начальное опорное решение.
Аналогичное условие может быть использовано при переходе от одного опорного решения к другому.
Пусть система уравнений-ограничений путем выбора разрешающих элементов приведении к равносильной разрешенной так, что правые части системы сохранились неотрицательными, и имеет вид:
Тогда базисное решение
является допустимым и опорным решением
с базисом из единичных векторов
Для перехода от этого опорного решения к новому необходимо использовать соотношение:
при
(2.1.5)
где k – номер вектора,
вводимого в базис; l –
номер вектора, выводимого из базиса;
-
координаты опорного решения;
-
коэффициенты разложения вектора
по базису опорного решения.