3 Численный метод решения задачи лп
3.1. Симплекс – метод
Рассмотрим задачу ЛП в канонической форме:
(5)
……………………… (6)
(77)
Будем предполагать,
что
(иначе, умножим соответствующее уравнение
на -1), уравнения системы (6) линейно
независимы, m<n
и система (6) -(7) совместна.
При сделанных
предположениях можно выбрать m
неизвестных (к примеру
)
таких, чтобы определитель, составленный
из коэффициентов при этих неизвестных,
не обращался в ноль. Тогда задача (5) -
(7) может быть приведена к виду, который
называется специальной
формой задачи ЛП:
…………………………………….. (8)
Одно из допустимых
решений этой задачи можно найти, если
переменные
положить равными нулю. Такое решение
называется допустимым
базисным решением.
Оно имеет вид:
Этому решению
соответствует значение целевой функции
.
Переменные
называют базисными,
набор переменных
называют базисом,
а переменные
называют небазисными
или свободными.
Число возможных базисов в задаче
размерности n
с m
ограничениями не превосходит величину
.
Известно, что каждому допустимому базисному решению соответствует вершина многоугольника допустимых решений и оптимальное решение задачи (при условии его существования) достигается в одной из вершин многоугольника. Поэтому оптимальное решение задачи ЛП находится среди допустимых базисных решений. Существуют рациональные способы последовательного перебора допустимых базисных решений, которые позволяют рассматривать не все допустимые базисные решения, а их минимальное число. К таким методам относится симплекс-метод [1,2,3].
3.2. Алгоритм симплекс-метода для задачи на минимум
Шаг 0 Подготовительный этап. Приводим задачу ЛП к специальной форме (15).
Шаг 1 Составляем симплекс-таблицу, соответствующую специальной форме:
|
B |
|
… |
|
… |
|
L |
|
|
… |
|
… |
|
|
|
|
… |
|
… |
|
.. |
.. |
………… |
||||
|
|
|
… |
|
… |
|
.. |
.. |
………… |
||||
|
|
|
… |
|
… |
|
Заметим, что этой
таблице соответствует допустимое
базисное решение
задачи (15). Значение целевой функции на
этом решении
Шаг 2 Проверка на оптимальность.
Если среди элементов
индексной строки симплекс – таблицы
нет ни одного положительного элемента
то
,
оптимальное
решение
задачи ЛП найдено:
.Алгоритм
завершает работу.
Шаг 3 Проверка на неразрешимость.
Если среди
есть положительный элемент
,
а в соответствующем столбце
нет ни одного положительного элемента
,
то целевая функция L
является неограниченной снизу на
допустимом множестве. В этом случае
оптимального
решения не существует.
Алгоритм завершает работу.
Шаг 4 Выбор ведущего столбца q.
Среди элементов
выбираем максимальный положительный
элемент
.Этот
столбец объявляем ведущим
(разрешающим).
Шаг 5 Выбор ведущей строки p.
Среди положительных
элементов столбца
находим элемент
,
для которого выполняется равенство:
Строку p объявляем ведущей (разрешающей). Элемент объявляем ведущим (разрешающим).
Шаг 6 Преобразование симплексной таблицы.
Составляем новую симплекс-таблицу, в которой:
а) вместо базисной переменной записываем , вместо небазисной переменной записываем ;
б)
ведущий элемент заменяем на обратную
величину
;
в)
все элементы ведущего столбца (кроме
)
умножаем на
;
г)
все элементы ведущей строки (кроме
)
умножаем на
;
д) оставшиеся элементы симплексной таблицы преобразуются по следующей схеме «прямоугольника».
Из элемента вычитается произведение трех сомножителей:
первый - соответствующий элемент ведущего столбца;
второй - соответствующий элемент ведущей строки;
третий
- обратная величина ведущего элемента
.
Преобразуемый элемент и соответствующие ему три сомножителя как раз и являются вершинами «прямоугольника».
Шаг 7 Переход к следующей итерации осуществляется возвратом к шагу 2.