3,Основные понятия теории симплекс-метода
ЗЛП, представленная в канонической форме (5.1)-(5.3), имеет m уравнений и n
неизвестных (под n в дальнейшем будет подразумеваться все переменные задачи (5.1)-
(5.3), включая и дополнительные), причем число уравнений меньше числа неизвестных.
Общее количество неизвестных задачи (5.1)-(5.3) можно разделить на два множества:
• (n-m) – множество переменных, которые положим равными нулю;
• m – множество переменных, отличных от нуля, значения которых можно
определить путем решения системы m уравнений с m неизвестными.
Известно, что если система, состоящая из m уравнений и m неизвестных, линейно
независима, то множество переменных m является единственным решением системы. Тогда будем называть множество переменных m базисными, через которые можно выразить все остальные переменные (n-m), являющиеся соответственно небазисными или свободными. Результирующая совокупность базисных и свободных переменных является одним из решений ЗЛП (5.1)-(5.3). Если все переменные являются неотрицательными, то решение называют допустимым решением задачи (или опорным планом), в противном случае – недопустимым решением (псевдопланом). Таким образом, допустимым решением называют решение, соответствующее заданному базису (переменные m), полученное из условия равенства нулю свободных переменных (n-m). Ненулевых компонент может быть не более m.
Примеры. Пусть рассматриваются следующие системы уравнений:
Тогда множество переменных (1,1,-1) для системы (5.4) (m=2 и n=3) будет являться
псевдопланом, так как переменная х3 отрицательна; для системы (5.5) множество
переменных (0,1,1) будет являться опорным планом и число ненулевых компонент равно
2. Для последней системы (5.5) множество переменных (0,1,0) будет также опорным
планом, но число ненулевых компонент меньше, чем m.
Если в опорном плане число ненулевых компонент меньше, чем m, то он называется
вырожденным. Исходя из вышесказанного, можно сделать вывод о том, что оптимальное решение ЗЛП, представленной в канонической форме, можно получить путем простого перебора всех допустимых решений или опорных планов. Тогда возникает следующая проблема: нельзя ли процедуру перебора всех возможных решений сделать более эффективной, то есть найти оптимальное решение кратчайшим путем? Тем более, как было показано ранее, понятие оптимизации само по себе предполагает такую процедуру выбора оптимального решения из множества возможных, которая позволяет избежать полного перебора и оценивания всех возможных вариантов.
Отсюда вытекает и основная идея симплекс-метода, предложенного в 1949 году
Дж. Данцигом (в 1939 году – Канторовичем для решения транспортной задачи), которая
заключается в последовательном переборе опорных решений, каждое из которых
соответствует угловой точке многоугольника (многогранника) ОДР, при этом переход от
одной угловой точке к другой производится в соответствии с улучшением значения
целевой функции. Таким образом, общая схема алгоритма симплекс-метода может быть представлена следующим образом.
Пусть есть следующая ЗЛП в канонической форме:
Следовательно, в первом опорном плане переменные (x4,x5,x6) являются
базисными (ненулевыми), а переменные (x1,x2,x3) – свободными (нулевыми). Значение целевой функции на первом шаге будет соответственно равно нулю:
Согласно основной идее симплекс-метода надо попытаться найти новое опорное
решение, которое должно улучшить значение целевой функции (фактически уменьшить значение F). Возможны следующие ситуации:
А) все коэффициенты сj являются положительными, тогда задача решена, так как
значение целевой функции улучшить нельзя (увеличение любого положительного
коэффициента приведет к возрастанию целевой функции, а не убыванию);
Б) не все коэффициенты сj являются положительными, тогда полученное на
текущем шаге значение целевой функции можно улучшить путем увеличения некоторой
свободной переменной. А для этого нужно сделать одну из текущих базисных
переменных нулевой (вывести из базиса) и ввести вместо нее требуемую свободную
переменную (сделать ее ненулевой). Такая замена необходима, чтобы выполнить условие, что опорный план должен содержать m базисных переменных.
Исходя из приведенных рассуждений, рассмотрим алгоритм симплекс-метода.
Достарыңызбен бөлісу: |
