Преобразование канонической модели в симплексную. Основная идея симплекс-метода
Рассмотрим ЗЛП в канонической форме записи:
Для определенности будем считать, что число неизвестных больше числа уравнений, то есть Напомним некоторые сведения из теории систем линейных алгебраических уравнений. В системе (1) все переменные можно разделить на две группы: базисные (основные) и свободные (неосновные). Базисные переменные- это любые n переменных, определитель из коэффициентов которых в системе (1) не равен нулю. Остальные переменные в этой системе являются свободными. Естественно, выбор базиса в такой системе не является единственным. Решение системы (1) называется допустимым, если при этом выполняются ограничения (2), то есть все компоненты вектора решения неотрицательны. Решение системы (1) называется базисным, если в нем все свободные переменные равны нулю. Допустимое базисное решение называется опорнымпланом. Эквивалентными Гауссовыми преобразованиями всякая каноническая форма приводится к симплексной форме, позволяющей получить исходное опорное решение:
В системе (4) переменные
Если в системе ограничений (4) все свободные члены сохранили свою неотрицательность, то задача в форме (4)-(5) называется симплексной моделью ЗЛП. следует отметить, что единого метода получения симплексной модели в форме (4)-(5) не существует. Во многих случаях прийти к такой записи невозможно, и приходится применять искусственные приёмы. Однако здесь будем считать, что нам такую запись получить удалось. Обнулим в системе (4) все свободные переменные, получим базисное решение в виде Чтобы удовлетворить неравенствам (2) и получить допустимое решение, надо выполнить преобразования Гаусса так, чтобы все свободные члены остались неотрицательными. Поэтому алгоритм Гаусса требует некоторого уточнения, и для этого приведем некоторые дополнительные сведения. Определение. Если в системе уравнений (1) все свободные члены неотрицательны, то допустимым отношением к выбранному k - му ключевому столбцу называется число
в противном случае Теорема (о допустимых отношениях). Если в любой очередной итерации гауссовых преобразований системы (1) с При подготовке очередной итерации преобразования матрицы системы по методу Гаусса нужно выбрать элемент, который будет превращен в единицу, а остальные элементы этого же столбца обнуляются. В классическом методе Гаусса роль такого элемента выполняет один из диагональных элементов матрицы. В симплекс-методе в роли такого элемента выступает ведущий элемент, полученный с помощью выбора минимального допустимого отношения. Очень важной для понимания смысла решения ЗЛП является следующее утверждение. Теорема. Опорное решение задачи (1)-(3) и угловая точка ОДР этой задачи эквивалентны. Отсюда следует, что на каждой итерации мы получаем опорный план, который по своему геометрическому смыслу является одной из угловых точек ОДР задачи. Теорема. (Достаточное условие оптимальности опорного решения) Если в симплексной модели ЗЛП в целевой функции (5) все коэффициенты при свободных переменных Теперь сформулируем главную идею симплекс-метода: Найти исходное опорное решение ЗЛП (то есть угловую точку ОДР). Модифицированными гауссовыми преобразованиями поэтапно улучшать решение до получения оптимального варианта, если он существует. Поэтапный процесс конечен, так как конечно число угловых точек. Если ОДР не ограничена, то алгоритм симплекс-метода также достаточно быстро определяет это.
|