Алгоритм метода искусственного базиса
Алгоритм метода искусственного базиса.
Подготовительный этап
Приводим задачу ЛП к каноническому виду
F=a0,1x1+a0,2x2+...a0,nxn +b0 → max
a1,1x1+a1,2x2+...a1,nxn+xn+1=b1
a2,1x1+a2,2x2+...a2,nxn+xn+2=b2
.........................................
ai,1x1+ai,2x2+...ai,nxn+Ri=bi
.......................................
am,1x1+am,2x2+...am,nxn+xn+m=bm
В случае если в исходной задаче необходимо найти минимум - знаки коэффициентов целевой функции F меняются на противоположные a0,n=-a0,n. Знаки коэффициентов ограничивающих условий со знаком "≥" так же меняются на противоположные. В случае если условие содержит знак "≤" или "=" - коэффициенты запишутся без изменений. К каждому условияю-неравенству, при переходе к каноническому виду добавляем дополнительную переменную, xn+m , к каждому i-му условию-равенству добавляем искусственную переменную Ri.
Шаг 0. Составляем симплексную таблицу, соответствующую исходной задаче
| x1 | x2 | ... | xn-1 | xn | b | |
| F | -a0,1 | -a0,2 | ... | -a0,n-1 | -a0,n | -b0 |
| xn+1 | a1,1 | a1,2 | ... | a1,n-1 | a1,n | b1 |
| xn+2 | a2,1 | a2,2 | ... | a2,n-1 | a2,n | b2 |
| Ri | ai,1 | ai,2 | ... | ai,n-1 | ai,n | bi |
| ... | ... | ... | ... | ... | ... | ... |
| xn+m | am,1 | am,2 | ... | am,n-1 | am,n | bm |
| M | -∑ai,1 | -∑ai,2 | ... | -∑ai,n-1 | -∑ai,n | -∑bi |
Шаг 1. Проверка на допустимость.
Проверяем на положительность элементы столбца b (свободные члены), если среди них нет отрицательных то найдено допустимое решение (решение соответствующее одной из вершин многогранника условий) и мы переходим к шагу 2. Если в столбце свободных членов имеются отрицательные элементы то выбираем среди них максимальный по модулю - он задает ведущую строку k. В этой строке так же находим максимальный по модулю отрицательный элемент ak,l - он задает ведущий столбец - l и является ведущим элементом.Переменная, соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис. Пересчитываем симплекс-таблицу согласноправилам.
Если же среди свободных членов есть отрицательные элементы - а в соответствующей строке - нет то условия задачи несовместны и решений у нее нет.
Если после перерасчета в столбце свободных членов остались отрицаетельные элементы, то переходим к первому шагу, если таких нет, то ко второму.
Шаг 2. Проверка на оптимальность.
На предыдущем этапе найдено допустимое решение. Проверим его на оптимальность Если среди элементов симплексной таблицы, находщихся в строках M и F(не беря в расчет элемент b0 - текущее значение целевой функции и элемент -∑bi) нет отрицательных, то найдено оптимальное решение.
Положительность строки M
Если в строке M есть отрицательные элементы то решение требует улучшения. Выбираем среди отрицательных элементов строки M максимальный по модулю (исключая -∑bi)
l - столбец в котором он находится будет ведущим. Для того, что бы найти ведущую строку, находим отношение соответсвующего свободного члена и элемента из ведущего столбца, при условии, что они неотрицательны.
bk/ak,l=min {bi/ai,l} при ai,l>0, bi>0
k - cтрока, для которой это отношение минимально - ведущая. Элемент ak,l - ведущий (разрешающий). Переменная, соответствующая ведущей строке (xk) исключается из базиса, переменная соответствующая ведущему столбцу (xl) включается в базис.
Пересчитываем симплекс-таблицу по формулам. Если в новой таблице после перерасчета в строке M остались отрицательные элементы переходим к шагу 2
Если невозможно найти ведущую строку, так как нет положительных элементов в ведущем столбце, то функция в области допустимых решений задачи не ограничена - алгоритм завершает работу.
Если в строке M и в столбце свободных членов все элементы положительные, то переходим к шагу 2.2.
Положительность строки F
Проверяем на положительность элементы строки F. Если имеются отрицательные элементы ( не считая b0), выбираем среди отрицательных элементов строки F максимальный по модулю.
-a0,l=min{-a0,i}
l - столбец в котором он находится будет ведущим. Для того, что бы найти ведущую строку, находим отношение соответсвующего свободного члена и элемента из ведущего столбца, при условии, что они неотрицательны.
bk/ak,l=min {bi/ai,l} при ai,l>0, bi>0
k - cтрока, для которой это отношение минимально - ведущая. Элемент ak,l - ведущий (разрешающий). Переменная, соответствующая ведущей строке (xk) исключается из базиса, переменная соответствующая ведущему столбцу (xl) включается в базис.
Пересчитываем симплекс-таблицу по формулам. Если в новой таблице после перерасчета в строке F остались отрицательные элементы переходим к шагу 2.2
Если невозможно найти ведущую строку, так как нет положительных элементов в ведущем столбце, то функция в области допустимых решений задачи не ограничена - алгоритм завершает работу.
Если в строке F и в столбце свободных членов все элементы положительные, то найдено оптимальное решение.
Правила преобразований симплексной таблицы
При составлении новой симплекс-таблицы в ней происходят следующие изменения: