Табличный симплекс-метод
Для упрощения процесса решения исходные данные задачи линейного программирования при решении ее симплекс методом записываются в специальные симплекс-таблицы. Поэтому одна из модификаций симплекс метода получила название табличный симплекс метод. Задача линейного программирования в каноническом виде: F=a01x1+a02x2+ .a0nxn +b0 → max
Исходная таблица для задачи имеет следующий вид:
, x2, xn - исходные переменные, xn+1, xn+2, xn+m - дополнительные переменные. Все дополнительные переменные мы приняли как базисные, а исходные переменные как небазисные (дополнительные записаны в первый столбец симплекс-таблицы а исходные в первую строку). При каждой итерации элементы симплекс-таблицы пересчитывают по определенным правилам. Алгоритм симплекс-метода. Подготовительный этап Приводим задачу ЛП к каноническому виду F=a01x1+a02x2+ .a0nxn +b0 → max
В случае если в исходной задаче необходимо найти минимум - знаки коэффициентов целевой функции F меняются на противоположные a0,n=-a0,n. Знаки коэффициентов ограничивающих условий со знаком "≥" так же меняются на противоположные. В случае если условие содержит знак "≤" - коэффициенты запишутся без изменений. Шаг 0. Составляем симплексную таблицу, соответствующую исходной задаче :
Перейти на страницу: 1 2
|