В. 33 Обоснование критерия оптимальности в ПСМ

Ax = b, в развёрнутом виде:

Мы считаем, что именно первые m переменных – базисные.

Умножим 1 стр. на 1 столбец: . Аналогично: и .

Этим мы выразили базисные переменные через небазисные. Сделаем следующее: возьмём Ц.Ф. и разобьем на 2 части:

() .

Раскрываем скобки: () (вынесем за скобку ) (где - старое значение Ц.Ф.), а остальные переменные = 0).

Мы получили выражение для значения Ц.Ф. через оценки и не базисных переменные.

Значения ц.ф. зависят от оценок не базисных переменных. Если все оценки ≤0 (задача оптимально решена), то какую бы небазисную переменную мы не увеличили, z будет расти, а у нас задача на min и надо, чтобы она убывала.

Если оценка «+», то уменьшается. Если существует хоть одна «+» оценка, то переменная, которой она соответствует, может уменьшить значения ц.ф. Чем > значение оценки, тем больше уменьшится ц.ф. Именно поэтому мы выбираем max «+» оценку, хотя это делать не обязательно. Теоретически, можно брать любую «+» оценку, на практике – max.

Замечания:

Если бы задача была на max, то критерием оптимальности было бы то обстоятельство, что все оценки ≥ 0, а для выбора ведущего столбца нужно искать max по модулю «-» оценку.

Date: 2015-12-12; view: 556; Нарушение авторских прав