2. Изменение значений правых частей ограничений.

Правые части ограничений выражают ограниченные объемы ресурсов или минимальные нормы потребления и т.п. Предположим правые части ограничений изменились на . Другими словами, встает задача найти новый оптимальный план, при b’ = b + . Можно ли использовать результаты уже решенной задачи? Если задача была решена для прежнего значения b, то известными являются обращенный базис В^-1 и симплекс - множители . При этом при определении В^-1 и значения b никак не учитывались, эти значения влияют лишь на оптимальное значение целевой функции. Следовательно, новые значения целевой функции и переменных можно получить по формулам

F’(x) = -

Замечание. Указанный прием можно использовать лишь при небольших изменениях в b, то есть базисное решение должно остаться допустимым (неотрицательным). Таким образом, если для базисных переменных получено хотя бы одно отрицательное значение, то решение задачи можно продолжить двойственным симплекс-методом.

Пример.

3. Изменение значений коэффициентов целевой функции.

Коэффициенты целевой функции выражают цены реализации, стоимость затрат и т.п. Если изменения произошли в коэффициентах целевой функции, можно ли воспользоваться решением задачи с прежними коэффициентами? То есть, если

C_j’ = C_j + , а изменений в b не произошло, то и оптимальный план не изменится, а изменятся лишь оптимальные значения целевой функции и ее коэффициентов. В исходной таблице целевая функция имеет вид

F(x) = -C₁x₁ – C₂x₂ - … - C_nx_n

Пусть в оптимальной таблице базисными оказались первые m переменных, следовательно, коэффициенты перед ними в оптимальной таблице должны быть равны нулю, исключим эти переменные из выражения целевой функции. Чтобы получить выражение целевой функции оптимальной таблицы в общем виде, используют оптимальную таблицу.

Умножим все уравнения системы соответственно на С₁, С₂, … , С_n и сложим с выражением целевой функции исходной таблицы в общем виде. Получим

0х₁ + … +0х_m + = F’(x) +

Полученное выражение представляет оптимальное выражение целевой функции. При этом оптимальность таблицы также определятся коэффициентами целевой функции. Заметим, что С_j не влияют на ограничения задачи. Если изменить С_j, то изменятся условия оптимальности:

- если для С_j^’ коэффициента целевой функции окажутся неотрицательными, то найденное

решение сохранится, то есть если , , то решение не изменится

х_б^’ = х_б, F^’(x) = - .

- если хотя бы один коэффициент окажется меньше нуля, то следует перейти к другому базисному решению, то есть продолжить решение обычным симплекс-методом.

Пример.

4. Включение дополнительных переменных.

Каждая переменная ЗЛП, если она не является уравновешивающей или искусственной, определяет план производства некоторой продукции, объем потребления и т.п. Предположим, поступило предложение выпускать новый вид продукции или использовать новую технологию. Стоит ли менять уже налаженное производство? Будет ли увеличение прибыли (сокращение расходов) весомым?

Пусть объем нового вида продукции х_n+1, технологические коэффициенты известны

Р = ( _1(n+1), _2(n+1), … , _m(n+1))^T, предполагаемая прибыль от реализации единицы продукции С_n+1. Все остальные условия остаются прежними. Чтобы учесть эти изменения, не решая задачу с самого начала, необходимо дополнительные данные записать в оптимальную таблицу. Новая «исходная» матрица коэффициентов A’ = A P, чтобы привести ее к виду оптимальной таблицы, необходимо умножить ее на В^-1. Таким образом, в оптимальной таблице добавляется еще один столбец Р* = В^-1Р. При этом свободные члены не изменяются. Осталось записать коэффициент целевой функции, это можно сделать с помощью симплекс - множителей. Умножим коэффициенты Р на соответствующие симплекс - множители и прибавим к коэффициенту целевой функции в стандартном виде:

- C_n+1 + = C_n+1*.

Если C_n+1* , то х_n+1 останется свободной ( то есть равной нулю), так как сохранится признак оптимальности. Следовательно, план менять не стоит.

Если C_n+1* < 0, то следует улучшить решение, а именно х_n+1 ввести в базисные переменные. Следовательно, план изменится. При этом решение продолжается обычным симплекс-методом.

Пример.