Опр-е нач. базисного решения в симплекс-методе. Признак опт-ти

Имея текущее базисное решение, необходимо выяснить, является ли оно оптимальным. Признак оптимальности позволяет установить статус решения и определить последующие действия. Пусть на k- й итерации получили базисное решение x^{(k )} с критерием L^(k). При смещении из этой вершины на: x^k+1_i=X^k_i-qa_ir, i=1, 2,…,m. x^k+1_r=q. Критерий:

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

Параметр Δ _r - относительная оценка переменной; показывает, как изменится значение критерия при введении единицы новой переменной (q= 1 ). Поэтому, если есть отрицательные оценки, текущее решение может быть улучшено при введении в число базисных соответствующей переменной. Если все оценки будут >= нулю, ни одна переменная не может улучшить тек. решение, условие "Δ _j ³0 - признак оптимальности. Для базисных переменных относительные оценки равны нулю: Так как базисный вектор не выражается через другие, то только один коэффициент a_rr =1, остальные =0. z_r=C_r-> Δ _r= 0. Достаточно проверять знаки оценок только небазисных переменных.

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

Если несколько переменных имеют отрицательные оценки, то выбирают переменную с наименьшей оценкой. Этапы симплекс-метода:

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

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

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

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

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

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

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