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

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

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

cs = min cj < 0. (2.7)

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

x1 = b1 – a1sxs;

x2 = b2 – a2sxs;

…………………;

xm = bm – amsxs;

f = f0 + csxs (cs < 0). (2.8)

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

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

shukaev049.wmf

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

shukaev050.wmf для ∀ais > 0.

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

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

cs = min cj ≥ 0.

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

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

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

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


Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074