Математическое программирование — страница 2

последнего b0, то соответствующий этой матрице план оптимален, т.е. сj £ 0 (j = r+1, n) => min f (b1, ... ,b2,0, ... ,0) = b0. Критерий отсутствия оптимальности. Если в симплекс-матрице имеется столбец (S-й), в котором последний элемент сs > 0, a все остальные элементы неположительны, то ЗЛП не имеет оптимального плана, т.е. сs > 0, ais £ 0 ( i= 1,r ) => min f = -¥. Если в симплекс-матрице не выполняются оба критерия, то в поисках оптимума надо переходить к

следующей матрице с помощью некоторого элемента ais > 0 и следующих преобразований (симплексных): 1) все элементы i-й строки делим на элемент a+is; 2) все элементы S-го столбца, кроме ais=1, заменяем нулями; 3) все остальные элементы матрицы преобразуем по правилу прямоугольника, что схематично показано на фрагменте матрицы и дано в формулах: akl` = akbais - ailaks = akl - ailaks; ais ais bk` = bkais - biaks; cl` = clais - csail ais ais Определение. Элемент ais+ называется

разрешающим, если преобразование матрицы с его помощью обеспечивает уменьшение (невозрастание) значения, целевой функции; строка и столбец, на пересечении которых находится разрешающий элемент, также называются разрешающими. Критерий выбора разрешающего элемента. Если элемент ais+ удовлетворяет условию bi = min bk ais0 aks0+ где s0 - номер выбранного разрешающего столбца, то он является разрешающим. 4. Алгоритм симплекс-метода (по

минимизации). 1) систему ограничений и целевую функцию ЗЛП приводим к симплексной форме; 2) составим симплекс-матрицу из коэффициентов системы и целевой функции в симплексной форме; 3) проверка матрицы на выполнение критерия оптимальности; если он выполняется, то решение закончено; 4) при невыполнении критерия оптимальности проверяем выполнение критерия отсутствия оптимальности; в случае выполнения последнего решение

закончено - нет оптимального плана; 5) в случае невыполнения обоих критериев находим разрешающий элемент для перехода к следующей матрице, для чего : а) выбираем разрешающий столбец по наибольшему из положи тельных элементов целевой строки; б) выбираем разрешающую строку по критерию выбора разрешающего элемента; на их пересечении находится разрешающий элемент; 6) c помощью разрешающего элемента и симплекс-преобразований

переходим к следующей матрице; 7) вновь полученную симплекс-матрицу проверяем описанным выше способом (см. п. 3) Через конечное число шагов, как правило получаем оптимальный план ЗЛП или его отсутствие Замечания. 1) Если в разрешающей строке (столбце) имеется нуль, то в соответствующем ему столбце (строке) элементы остаются без изменения при симплекс-преобразованиях. 2) преобразования - вычисления удобно начинать с целевой строки;