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