Признак оптимальности. Основные этапы симплекс-метода

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

Он легко выводится из связи смежных решений. Пусть на k- й итерации получили базисное решение x^{(k )} с критерием L^(k). При смещении из этой вершины на ребро (см. рис.1 -а) решение изменяется согласно (11):

x^k+1_i=X^k_i-qa_ir, i=1, 2,…,m.

x^k+1_r=q.

Используя приведенные соотношения, определим критерий в новом решении:

или, введя обозначения

(14)

(15)

получаем

(16)

Параметр Δ _r называют относительной оценкой переменной. Ее смысл очевиден, если вспомнить, что q - значение новой переменной. Δ _r показывает, как изменится значение критерия при введении единицы новой переменной (q= 1 ). Поэтому, если есть отрицательные оценки, текущее решение может быть улучшено при введении в число базисных соответствующей переменной.

Если же все оценки будут больше или равны нулю, то тогда ни одна переменная не может улучшить текущее решение, следовательно,

условие "Δ _j ³0 и является признаком оптимальности.

Покажем, что для базисных переменных относительные оценки равны нулю. Так как базисный вектор не выражается через другие, то только один коэффициент a_rr =1, остальные равны нулю. Из (14) следует z_r=C_r, а из (15) - Δ _r= 0. Таким образом, достаточно проверять знаки оценок только небазисных переменных.

Полученным формулам можно дать экономическую интерпретацию.

Пусть рассматривается задача планирования, в которой Х _j – количество продукции j- го вида, C_j – стоимость единицы произведенной продукции.

Тогда X ^{(0 )} – план производства, включающий первые m видов продукции. Попытаемся изменить этот план. Включим в него еще один вид продукции r. Так как ресурсы не меняются, это возможно только при одновременном уменьшении продукции, входящей в план X ⁽⁰⁾. Величина этого изменения определяется коэффициентами a_ir Действительно, как следует из (11), a_ir показывает, насколько должно измениться производство продукции i- го вида при введении в план единицы продукции r. В экономической литературе такой показатель называют маргинальной нормой замещения. Значит, объем выпуска каждого вида продукции сокращается на a_ir, а суммарная стоимость на величину Поэтому Z_r трактуют как маргинальную цену (снижение стоимости произведенной продукции на каждую единицу продукции r). В то же время, единица продукции r дает прирост стоимости С_r, называемый маргинальным доходом. Очевидно, что если C_r > Z_r, то есть Δ _r< 0, то такая корректировка плана выгодна.

Если несколько переменных имеют отрицательные оценки, то возникает необходимость выбора из них самой перспективной. Очевидно, что наибольшее улучшение критерия на очередном шаге даст переменная, для которой произведение q₀ Δ _j минимально. Однако такой выбор требует большого объема вычислений, так как для каждой переменной с отрицательной оценкой требуется находить q₀, а таких переменных в реальной задаче могут быть тысячи. Поэтому обычно выбирают переменную с наименьшей оценкой.

Таким образом, укрупненно можно выделить следующие этапы симплекс-метода:

1. Построение начального неотрицательного базисного решения.

2. Анализ оценок. При этом возможны три ситуации:

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

б) имеются отрицательные оценки, но, по крайней мере, одной их них (например, Δ _j) соответствует вектор, для которого все коэффициенты разложения неположительны (" a_ij £0). В этом случае q не ограничено сверху и, как следует из (16), критерий неограниченно возрастает. Решение прекращается.

в) для каждой отрицательной оценки есть a_ij >0. Решение может быть улучшено выполнением 3 этапа.

3. Переход к новому базисному решению путем введения переменной с минимальной оценкой и выводом переменной, на которой достигается минимум в (12).

Этапы 2 и 3 повторяются до выполнения одного из условий останова.

Из перечисленных этапов не раскрытым остался первый этап, рассматриваемый ниже.

Дата добавления: 2014-01-11