2015-08-21
228
Пусть стоит задача максимизации (минимизации)
при условиях
где Aj (j=1,...,n), B - m-мерные векторы.
Обозначения симплекс-таблицы:
Строку 
рассчитывают по формуле
Критерий 1 (критерий оптимальности). Если все Δk >= 0, то выбранный план для задачи максимизации является оптимальным (для задачи на минимум признак оптимальности - неположительность всех Δk).
Критерий 2. Если обнаруживается некоторое Δk < 0 (для задачи минимизации Δk>0) и хотя бы одно из значений Zjk >0, то переход к новому опорному плану увеличит (уменьшит) значение целевой функции. При этом в базис будет вводиться новый вектор, выбор которого определяется по критерию максимального по модулю произведения Θ*Δk. Ес-ли к тому же учесть, что число положительных (базисных) компонент опорного плана должно оставаться равным m, то одну из m базисных компонент исходного плана обращаем в нуль выбором
где Xjo- компоненты опорного плана;
Zjk- коэффициенты при k-й переменной в ограничениях задачи.
При переходе к новому опорному плану X(Θ), в котором k-я компонента равна Θ>0 (станет базисной), значение целевой функции изменится и будет равно
Критерий 3. Если обнаруживается некоторое Δk < 0, но все Zjk<=0, то линейная форма задачи не ограничена по максимуму (неограничен-ность по минимуму устанавливается аналогично при Δk>0 и всех Zjk <=0).
Переход к очередной симплексной таблице сводится к тому, чтобы выразить Xk из уравнения, соответствующего минимуму для Θ, и исключить из остальных уравнений (в итоге получаем единичный вектор при новой базисной компоненте и тем самым сохраняется единичная подматрица при базисных векторах):
1. Строку, соответствующую вектору, выводимому из базиса (главная строка), делим на коэффициент (главный элемент), находящийся на пересечении этой строки и столбца, соответствующего вектору, вводимому в базис (главный столбец).
2. От всех остальных строк вычитаем преобразованную главную строку, умноженную на элемент, находящийся на пересечении искомой строки и главного столбца.
