Научная электронная библиотека

Монографии, изданные в издательстве Российской Академии Естествознания

Прикладные методы оптимизации

Шукаев Д. Н.,

2.3.2. Улучшение неоптимального базисного допустимого решения

Если среди относительных оценок c_j канонической формы (2.5) имеются отрицательные, то можно, при условии невырожденности (когда все b_j ≥ 0), построить новое базисное допустимое решение с меньшим значением целевой функции чем f = f₀. Это решение может быть получено путем увеличения значения одной из небазисных переменных x_s и соответствующего изменения базисных переменных. В качестве xs выбирается переменная с индексом s выбранном из условия

c_s = min c_j < 0. (2.7)

Используя каноническую форму (2.4) и (2.5) построим решение, в котором xs принимает некоторое положительное значение, значения всех других небазисных переменных остаются по-прежнему нулями, а базисные переменные, включая и f, преобразуются в зависимости от увеличения xs по формулам

x₁ = b₁ – a_1sx_s;

x₂ = b₂ – a_2sx_s;

…………………;

x_m = b_m – a_msx_s;

f = f₀ + c_sx_s (c_s < 0). (2.8)

Поскольку cs было выбрано отрицательным, то значение xs нужно сделать как можно большим, чтобы значение f стало как можно меньше. Единственное, что помешает сделать xs бесконечно большим – это то, что одна из базисных переменных может стать отрицательной. Однако если все a_is ≤ 0, то xs можно брать сколь угодно большим. Следовательно справедлива следующая теорема 2.4 «Если в канонической системе для некоторого s все коэффициенты ais неположительны и cs отрицательно, то можно построить класс допустимых решений, для которого множество значений f не будет ограничено снизу».

С другой стороны, если хоть одно из a_is положительно, то невозможно бесконечно увеличивать значение x_s, потому что как только будет

так x_i станет отрицательным. Если ais положителен более чем для одного i, то наименьшее из таких отношений, номер строки которого будем обозначать через r, определит наибольшее возможное значение х, и при этом базисные переменные будут неотрицательны. Наибольшим значением xs, допустимым при этом предположении, будет

для ∀a_is > 0.

В случае, когда минимум достигается для нескольких i, выбор r является произвольным.

Определение. «Базисное решение является вырожденным, если значение хотя бы одной базисной переменной равно нулю». В этом случае из (2.8) следует, что для некоторого ais > 0 соответствующее значение bi для базисной переменной окажется нулевым, и нельзя увеличить xs так, чтобы базисные переменные остались неотрицательными, и поэтому f не будет уменьшаться. Таким образом, улучшение неоптимального базисного решения констатируется следующей теоремой 2.5 [13] «Если в канонической системе для некоторого s относительная оценка cs отрицательна и по крайней мере один коэффициент ais положителен, то из невырожденного базисного допустимого решения можно построить новое базисное допустимое решение с меньшим значением целевой функции». Новое базисное допустимое решение можно снова испытать на оптимальность, проверив выполнение неравенства

c_s = min c_j ≥ 0.

Симплекс-алгоритм состоит в повторении этого цикла снова и снова. Этот процесс заканчивается только тогда, когда получим либо

а) множество допустимых решений, для которых f → –∞; либо

б) оптимальное базисное допустимое решение (все c_j ≥ 0).

Теорема 2.6 [13]. «В предположении, что ни на одной итерации нет вырожденности, симплекс-алгоритм закончится за конечное число итераций»