Моделирование и оптимизация задач экономики средствами симплексного метода и теории двойственности

12 Первую группу переменных определим как небазисные, вторую – базисные, в этом случае получившееся решение назовем базисным. При этом если все переменные удовлетворяют условию неотрицательности, то решение называем допустимым, в противном случае – недопустимым. Замечание. Абстрактным аналогом понятия вершины ОДР является понятие опорного плана или БДР. Сформулируем алгоритм решения ЗЛП симплексным методом в базовой форме: 1) Привести ЗЛП к каноническому виду, т.е. ввести дополнительные переменные, удовлетворяющие условию неотрицательности. Замечание. Переменные являются базисными, если они линейно независимы и соответствуют единичным векторам: 0...0011nx, 0...0102nx, ... 2) Разбить переменные на две группы: базисные (основные, отличные от нуля) и небазисные (неосновные, свободные, равные нулю). Для этого на 1 шаге решения ЗЛП выбираются такие m переменных (если это возможно), каждая из которых входит только в одно из m уравнений системы ограничений, и при этом отсутствуют уравнения, в которые не входит ни одна из этих переменных. Замечание. Если дополнительные переменные были введены с положительными коэффициентами, то составляем из них определитель. Если он отличен от нуля, то на первом шаге решения дополнительные переменные принимаются за базисные, а все остальные переменные считаются небазисными. 3) Выражаем базисные переменные через небазисные и получаем решение 1X ЗЛП. В случае, если все компоненты 1X удовлетворяют условию неотрицательности, 1X является ДБР, и его необходимо проверить на оптимальность. Замечание. Если базисная переменная равна нулю, то имеем вырожденное базисное решение. 4) Для проверки на оптимальность ДБР 1X следует: