Реферат: Математическое программирование 2
bi = min bk
ais 0 aks 0 +
где s0 - номер выбранного разрешающего столбца, то он является разрешающим.
4. Алгоритм симплекс-метода (по минимизации).
1) систему ограничений и целевую функцию ЗЛП приводим к симплексной форме;
2) составим симплекс-матрицу из коэффициентов системы и целевой функции в симплексной форме;
3) проверка матрицы на выполнение критерия оптимальности; если он выполняется, то решение закончено;
4) при невыполнении критерия оптимальности проверяем выполнение критерия отсутствия оптимальности; в случае выполнения последнего решение закончено - нет оптимального плана;
5) в случае невыполнения обоих критериев находим разрешающий элемент для перехода к следующей матрице, для чего :
а) выбираем разрешающий столбец по наибольшему из положи тельных элементов целевой строки;
б) выбираем разрешающую строку по критерию выбора разрешающего элемента; на их пересечении находится разрешающий элемент;
6) c помощью разрешающего элемента и симплекс-преобразований переходим к следующей матрице;
7) вновь полученную симплекс-матрицу проверяем описанным выше способом (см. п. 3)
Через конечное число шагов, как правило получаем оптимальный план ЗЛП или его отсутствие
Замечания.
1) Если в разрешающей строке (столбце) имеется нуль, то в соответствующем ему столбце (строке) элементы остаются без изменения при симплекс-преобразованиях.
2) преобразования - вычисления удобно начинать с целевой строки; если при этом окажется, что выполняется критерий оптимальности, то можно ограничиться вычислением элементов последнего столбца.
3) при переходе от одной матрицы к другой свободные члены уравнений остаются неотрицательными; появление отрицатель
ного члена сигнализирует о допущенной ошибке в предыдущих вычислениях.
4) правильность полученного ответа - оптимального плана - проверяется путем подстановки значений базисных неизвестных в целевую функцию; ответы должны совпасть.
5. Геометрическая интерпретация ЗЛП и графический метод решения (при двух неизвестных)
Система ограничений ЗЛП геометрически представляет собой многоугольник или многоугольную область как пересечение полуплоскостей - геометрических образов неравенств системы. Целевая функция f = c1 x1 + c2 x2 геометрически изображает семейство параллельных прямых, перпендикулярных вектору n (с1 ,с2 ).
Теорема. При перемещении прямой целевой функции направлении вектора n значения целевой функции возрастают, в противоположном направлении - убывают.
На этих утверждениях основан графический метод решения ЗЛП.
6. Алгоритм графического метода решения ЗЛП.
1) В системе координат построить прямые по уравнениям, соответствующим каждому неравенству системы ограничений;
2) найти полуплоскости решения каждого неравенства системы (обозначить стрелками);
3) найти многоугольник (многоугольную область) решений системы ограничений как пересечение полуплоскостей;
4) 
построить вектор n (с1 ,с2 ) по коэффициентам целевой функции f = c1 x1 + c2 x2 ;
5) в семействе параллельных прямых целевой функции выделить одну, например, через начало координат;