Табличный симплекс-метод
Для упрощения процесса решения исходные данные задачи линейного программирования при решении ее симплекс методом записываются в специальные симплекс-таблицы. Поэтому одна из модификаций симплекс метода получила название табличный симплекс метод. Задача линейного программирования в каноническом виде:
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
.......................................
am,1x1+am,2x2+...am,nxn+xn+m=bm
Исходная таблица для задачи имеет следующий вид:
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 |
... | ... | ... | ... | ... | ... | ... |
xn+m | am,1 | am,2 | ... | am,n-1 | am,n | bm |
x1, x2, xn - исходные переменные, xn+1, xn+2, xn+m - дополнительные переменные. Все дополнительные переменные мы приняли как базисные, а исходные переменные как небазисные (дополнительные записаны в первый столбец симплекс-таблицы а исходные в первую строку). При каждой итерации элементы симплекс-таблицы пересчитывают по определенным правилам.
|
|
Алгоритм симплекс-метода.
Подготовительный этап
Приводим задачу ЛП к каноническому виду
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
.......................................
am,1x1+am,2x2+...am,nxn+xn+m=bm
В случае если в исходной задаче необходимо найти минимум - знаки коэффициентов целевой функции F меняются на противоположные a0,n=-a0,n. Знаки коэффициентов ограничивающих условий со знаком "≥" так же меняются на противоположные. В случае если условие содержит знак "≤" - коэффициенты запишутся без изменений.
Шаг 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 |
... | ... | ... | ... | ... | ... | ... |
xn+m | am,1 | am,2 | ... | am,n-1 | am,n | bm |
Шаг 1. Проверка на допустимость.
Проверяем на положительность элементы столбца b (свободные члены), если среди них нет отрицательных то найдено допустимое решение (решение соответствующее одной из вершин многогранника условий) и мы переходим к шагу 2. Если в столбце свободных членов имеются отрицательные элементы то выбираем среди них максимальный по модулю - он задает ведущую строку k. В этой строке так же находим максимальный по модулю отрицательный элемент ak,l - он задает ведущий столбец - l и является ведущим элементом. Переменная, соответствующая ведущей строке исключается из базиса, переменная соответствующая ведущему столбцу включается в базис. Пересчитываем симплекс-таблицу согласноправилам
.Если же среди свободных членов есть отрицательные элементы - а в соответствующей строке - нет то условия задачи несовместны и решений у нее нет.
|
|
Если после перерасчета в столбце свободных членов остались отрицаетельные элементы, то переходим к первому шагу, если таких нет, то ко второму.