8. Сутність процесу переходу від одного опорного плану до іншого опорного плану, його економічна інтерпретація в термінах задачі раціонального використання ресурсів. Зміст оцінок оптимального плану.

Выполнив все указанные преобразования для вектора и , удовлетворящего , получим план , который может содержать m+1 положительных компонентов, и, следовательно, в этом случае не будет опорным. Для того, чтобы был опорным, необходимо, но не достаточно, обратить в ноль хотя бы одну из его компонент. Выберем из условия Очевидно, что это можно сделать только в том случае, когда т.е. среди коэффициентов разложения по базису хотя бы один положительный.

Предположим, что минимум в достигается при i=k. Это означает, что и . При подстановке в k-я компонента его обратится в ноль, т.е. .

Таким образом, получим план , содержащий не более m положительных компонент. Он будет опорным, если векторы линейно независимы.

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

Условие, позволяющее ввести в базис вектор , состоит в том, чтобы хотя бы один из его коэффициентов разложения по базису был положительным: В противном случае план всегда будет содержать m+1 положительных компонент и не будет опорным. Выбирая различные , можно построить различные планы.

По оценкам векторов проверяется оптимальность плана. Если все оценки , то, как следует из теоремы о достаточном признаке оптимальности опорных невырожденных планов, план оптимальный. Если среди оценок есть положительные, то, как следует из теоремы о признаке неоптимальности невырожденных опорных планов, план неоптимальный. При этом необходимо перейти к новому опорному плану, т.е. к новому базису, причем в большинстве случаев наиболее целесообразно вводить в базис вектор с наибольшей положительной оценкой.

9. Характеристика симплексної таблиці. Чому в першій симплексній таблиці в стовпцях Aj залишуються компоненти відповідних векторів.

Симплексным методом удобно решать ЗЛП с помощью так называемых симплексных таблиц.

В столбцах записываются: Б – векторы, составляющие ортонормированный базис; - коэффициенты целевой функции при базисных переменных; – коэффициенты целевой функции; – коэффициенты разложения вектора по векторам базиса.

Так как базис ортонормированный, то в первой симплексной таблице в столбце записываются свободные члены, а в - коэффициенты при переменных в основной системе ограничений.

Строка называется индексной. В ней записываются: на пересечении со столбцом - значение целевой функции плана , которое равно сумме произведений элементов столбца на соответствующие им элементы столбца , т.е.: ; на пересечении со столбцами - оценки векторов , которые равны сумме произведений элементов столбца на соответствующие им элементы столбца без коэффициента целевой функции , т.е.: