Решение задач линейного программирования

Заметим, что если базисные переменные (все) образуются в результате приведения задачи к каноническому виду, то целевая функция задачи остается без изменений, а если переменные добавляются искусственно к основным ограничениям, имеющим вид равенств, то из целевой функ ции вычитается их сумма, умноженная на М, т.е. (так называемый модифицированный симплекс-метод). Мы не будем рассматривать задачи, относящиеся к модифицированному симплекс-методу. Для практической рабо - ты по нахождению решения задачи линейного программирования (по варианту простого симплекс-метода) будут использоваться алгоритм итерационного (многошагового) процесса нахождения решения и два типа оперативных оце - нок, позволяющих делать переходы от одного шага к другому, а также показы - вающих, когда итерационный процесс остановится и результат будет найден.

Первая оценка - это дельта-оценка, для переменной х j она имеет вид: (1.4) Здесь выражение i B означает, что в качестве коэффициентов целевой функ - ции, представленных в сумме выражения (1.4), используются коэффициенты переменных, входящих в базис на данном шаге итерационного процесса. Пере - менными а ij являются множители матрицы коэффициентов А при основных ог - раничениях, рассчитанные на данном шаге итерационного процесса.

Дельта-оценки рассчитываются по всем переменным х i , имеющимся в задаче.

Следует отметить; что дельта-оценки базисных переменных равны нулю. После нахож - дения дельта-оценок из них выбирается наибольшая по модулю отрицательная оценка, переменная х k , ей соответствующая, будет вводиться в базис.