30. Теорема оптимальности плана задачи линейного программирования следствие из теоремы оценки оптимальности при решении задач симплекс методом.

Теорема 1: Если для некоторого вектора Ā_j в системе

Х₁       + а_1m+1X_m+1 + а_1m+2X_m+2 + … + а_1nX_n = a₁

Х₂ + а_2m+1X_m+1 + а_2m+2X_m+2 + … + а_2nX_n = a₂

…………………………………………………..

     X_m + а_mn+1X_m+1 + а_mn+2X_m+2 + … + а_mnX_n = a_m

Выполняется соотношение Z_j – c_j > 0, то план Х_Б0 не является оптимальным и можно перейти к плану Х_Б1 такому, что Z (Х_Б1) ≤ Z (Х_Б0).

Здесь Z_j = (С, Ā_j) – скалярное произведение векторов.

С – вектор, состоящий из коэффициентов при базисных переменных целевой функции Z

Ā_j – вектор, состоящий из коэффициентов разложения соответствующего вектора по векторам базиса.

c_j – коэффициент целевой функции Z при переменной Х_j

Следствие из теоремы: Если для всех векторов Ā₁, Ā₂, …, Ā_n некоторого опорного плана Х выполняется соотношение Z_j – c_j < 0, то опорный план Х является оптимальным. Величины (Z_j – c_j) – называются оценками оптимальности соответствующих векторов.

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

Замечание. В теореме и следствии предполагается, что задача находится в канонической форме с целевой функцией на минимум. Однако симплекс-методом моно решать и задачи с целевой функцией на максимум. В этом случае при анализе значений оценок используется их противоположный смысл, то есть план будет оптимальным, если все оценки оптимальности будут не отрицательными (положительным или отрицательным).

Выбор вектора, вводящегося в базис и выводящегося из базиса. Симплексное отношение.

Для перехода к новому опорному плану необходимо один из свободных векторов ввести в базис, а какой-то из базисных векторов вывести. Для введения в базис выберем вектор, имеющий хотя бы одну положительную координату. Пусть таким вектором будет вектор А m+1 .

Разложению –

 соотв. вектор, кот. будет являться опорным планом, если его координаты будут неотрицательными, а кол-во положительных координат будет равняться m.

Координаты вектора Х1 должны быть неотрицательными, т.е. .

Если  , то эта координата будет неотрицательной.

Пусть минимум в соотношении (5) был получен при i =1, тогда если взять

то первая координата вектора 1 х станет равной нулю.

Соотношение (6) называется симплексным отношением. Таким образом, мы перешли от исходного опорного плана 0 х (базисные векторы А1,А2,…Аm) к опорному плану 1 х (базисные векторы А2,А3,…,Аm,Am+1).

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