Решение задачи линейного программирования симплекс-методом — страница 5

  • Просмотров 461
  • Скачиваний 9
  • Размер файла 179
    Кб

экстремальной точки к другой, пока не будет найдена точка оптимального решения. Обозначим: – общее количество переменных в ЗЛП, представленной в канонической форме; - количество исходных переменных; - количество ограничений, - количество дополнительных переменных, тогда . Каждая вершина многогранника решений имеет - ненулевых переменных и () - нулевых переменных. Ненулевые переменные называются базисными, нулевые переменные –

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

только в одной строке с коэффициентом, равным 1. При выборе начального допустимого базиса для составления симплекс-табли-цы на первом шаге СТ(0) исходные переменные приравниваются к нулю и являются небазисными, среди введённых дополнительных переменных выбираются переменные с коэффициентами равными единице. Переменные в равенствах (2) - (4) являются базисными и в - строку входят с коэффициентами, равными 0. Для заполнения

симплекс-таблицы необходимо целевую функцию преобразовать к виду . Таким образом, окончательно получаем: (1) (2) (3) (4) При составлении симплекс-таблицы придерживаются следующих правил: в крайнем левом столбце располагаются базисные переменные и ; в крайнем правом столбце располагаются правые части ограничений; в первой строке располагаются переменные в определённом порядке: сначала , потом небазисные переменные, базисные

переменные располагаются в последних столбцах перед правой частью (ПЧ). Запишем коэффициенты в СТ(0): ПЧ 1 - - 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 Оптимальность любой из вершин определяется коэффициентами при небазисных переменных в – строке текущей симплекс-таблицы: Для задачи максимизации данная вершина является оптимальной, если все коэффициенты при небазисных переменных в – строке являются неотрицательными (>0); Для задачи минимизации

данная вершина является оптимальной, если все коэффициенты при небазисных переменных в – строке являются неположительными (< 0). Если в задаче максимизации (минимизации) у одной небазисной переменной в – строке коэффициент <0(>0), то текущая точка не является оптимальной и необходимо изменить базис. Для этого выбирают небазисную переменную, имеющую максимально отрицательный (положительный) коэффициент в – строке. Выбранная