Материал: УП - Методы оптимальных решений

Теорема.

Пусть исходная задача решается на max. Если для некоторого опорного плана все оценки Δ_j (j = ) не отрицательны (больше или равны 0), то такой план оптимален.

_{Доказательство: Так как Z = ΔO и Δj  0, то Z достигает max, когда = 0, а это возможно, если хm+1 = 0, хm+2} = 0, ..., хn = 0, т. е. опорный план (В₁, В₂, …, В_m, 0, …, 0) – оптимален.

Теорема.

Если исходная задача решается на min и для некоторого опорного плана все оценки Δ_j (j = ) не положительны (меньше или равны 0), то такой план оптимален.

Пример 9. Решить задачу линейного программирования.

Система ограничений задачи имеет предпочтительный вид: базисом являются переменные х₂,х₄,х₁. Заносим условие задачи в симплексную таблицу (табл. 18):

Таблица 18

3.3. Переход к нехудшему опорному плану

Пусть решается задача линейного программирования с системой ограничений в предпочтительном виде

(i = ), (5)

ее начальный опорный план = (В₁, В₂, …, В_m, 0, …, 0). Значение целевой функции Z( ) = = Δ_O.

Рассмотрим задачу на mах: если все Δ_j  0, то опорный план опти­мален. Пусть существует j_O, для которого Δj_O < 0. Вектор столбец , для которого Δj_O < 0, называется разрешающим, а соответствующая пе­ременная x_jo – перспективной. Попытаемся, не изменяя нулевых значений свободных переменных х_m+1, х_m+2, …, х_n, кроме x_jo увеличить значение целевой функции Z за счет увеличения переменной x_jo > 0. Однако увеличивать x_jo надо осторожно, так как выбор влияет на значения х₁, ..., х_m, которые должны быть  0. Имеем: х₁  0, х₂  0, ..., х_m  0, х_m+1 = 0,..., x_jo-1 = 0, x_jo > 0, x_jo+1 = 0, ..., x_n = 0 и из (5) имеем

x_i = B_I – – (i = ). (6)

При значительном увеличении может случиться, что для некоторого i соответствующее B_I < , значит получим х_i < 0, что недопустимо. В случае, если (i = ), такого нарушения не произойдет.

Итак, x_jo можно увеличивать до тех пор, пока B_i – x_jo  0, не на­рушая общности, можно считать > 0, тогда  . Найдем среди отношений наименьшее. Пусть оно называется наименьшим симплексным отношением и обозначается Q.

x_jo = min = = Q,

Заполним индексную строку (Z_j – с_j): ,

Δ_O = – 1  1,5 – 2  2 + 2  0,5 = – 4,5,

Δ₁ = – 1 0 – 2  0 + 2  1 – 2 = 0,

Δ₂ = – 1 1 – 20 + 20 – (–1) = 0,

Δ₃ = – 1 0,5 – 2 + 2  (– 0,5) – 3= – 6,5,

Δ₄ = – 1 0 – 21 + 20 – (– 2) = 0,

Δ₅ = – 1 0,5 – 2  0 + 2  0,5 – 1 = – 0,5.

Начальный опорный план = (0,5; 1,5; 0;2; 0), Z ( ) = – 4,5. Так как все оценки индексной строки Δ_j не положительны, а задача на min, то план – оптимален х* = (0.5: 1.5: 0: 2: 0); Z (х*) = – 4,5.

(если это условие выполняется при нескольких i, то в качестве i_O можно выбрать любое) Cтроку называют разрешающей, элемент – разрешающим. Переменная , присутствующая в базисе, является неперспективной и ее выводят из базиса:

x_m+1 = 0, …, = 0, = Q,

= 0, …, x_n = 0, а из равенства (6) находим: x₁ = B₁ – Q, …,

= – Q, = 0, = – Q, …,

x_m = Q.

Новый базис будет состоять из переменных х₁, , , , ..., x_m, а соответствующий ему опорный план примет вид, X₁ = (B₁ – Q; B₂ – Q; …; – Q; 0; – Q; …; Q; 0; …; Q; 0; …; 0).

В результате преобразований получен новый опорный план , в котором переменная заменена на , причем Z(X₁) = Δ₀ – Δ_j0Q = Z(X₀) – Δ_j0Q, но Δ_j0 < 0, поэтому Z(X₁)  Z(X₀), то есть новый план не хуже начального .

Практика показывает, что в случае решения задачи на max число шагов уменьшается, если разрешающий столбец выбрать по правилу max (Δ_j  0), т. е. в базис вводить переменную, которой соответствует max по абсолютной величине оценки.

В случае задачи на min разрешающий столбец нужно выбирать по правилу mах Δ_j (Δ_j > 0).

Далее процесс повторяется. Проверяем, является ли план оптимальным, если да, то задача решена. Если нет, то перехо­дим к нехудшему опорному плану и т. д.

Шаг симплексного метода, позволяющий перейти от одного опорного плана к другому нехудшему, называется итерацией.

Симплексные преобразования нового базиса выполняются по правилу:

1. Элементы строки i_O новой таблицы равны соответствующим элементам разрешающей строки старой таблицы, деленным на разре­шающий элемент: , , (j = ).

2. Элементы разрешающего столбца j₀ новой таблицы равны 0, за исключением = 1.

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

4. По 3 пункту вычисляются и элементы индексной строки.

Для контроля вычислений они могут быть рассчитаны по формулам ,

Пример 10. Найти max Z = 14х₁ – 5х₂ + 2х₃ – х₄ + 8х₅, если

Решение.

Так как задача имеет предпочтительный вид, то занесем ее условия в симплексную табл. 19 (итерация 0).

Таблица 19