Задачи линейного программирования канонического вида метод симплекса


,Основные понятия теории симплекс-метода



бет4/6
Дата11.06.2022
өлшемі489.26 Kb.
#268043
түріСамостоятельная работа
1   2   3   4   5   6
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 базисных переменных.
Исходя из приведенных рассуждений, рассмотрим алгоритм симплекс-метода.


Достарыңызбен бөлісу:
1   2   3   4   5   6




©melimde.com 2022
әкімшілігінің қараңыз

    Басты бет
Сабақтың тақырыбы
бойынша жиынтық
жиынтық бағалау
Сабақ тақырыбы
Сабақтың мақсаты
ғылым министрлігі
тоқсан бойынша
бағдарламасына сәйкес
бағалауға арналған
Сабақ жоспары
Реферат тақырыбы
жиынтық бағалауға
сәйкес оқыту
арналған тапсырмалар
Қазақстан республикасы
білім беретін
оқыту мақсаттары
бағалау тапсырмалары
рсетілетін қызмет
Жалпы ережелер
жиынтық бағалаудың
республикасы білім
бекіту туралы
тоқсанға арналған
Қазақстан тарихы
Қазақстан республикасының
мерзімді жоспар
арналған жиынтық
қызмет стандарты
болып табылады
жалпы білім
арналған әдістемелік
бағалаудың тапсырмалары
Мектепке дейінгі
оқыту әдістемесі
Қазақ әдебиеті
нтізбелік тақырыптық
пәнінен тоқсанға
Зертханалық жұмыс
Инклюзивті білім
Әдістемелік кешені
республикасының білім
білім берудің
туралы жалпы
Қазақстанның қазіргі
Қысқа мерзімді
Жұмыс бағдарламасы
қазақ тілінде
қазіргі заман
туралы хабарландыру
атындағы жалпы