СКАЧАТЬ:  otchet_po_modelirovaniyu_praktika.zip [52,28 Kb] (cкачиваний: 38)

ОТЧЕТ

по дисциплине «Моделирование»

на тему: «Линейное программирование. Симплексный метод»

Задача №5

Симплексный метод. Алгоритм решения

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

            Как известно, задача оптимизации критерия сводится к выбору только неотрицательного решения системы  уравнений 

                                    (1),

максимизирующего R и содержащего m отличных от нуля составляющих.

            Так как число уравнений m в системе (1) всегда меньше числа переменных m+n, эта система имеет, вообще говоря, бесчисленное множество  решений. Однако представляют интерес только неотрицательные решения, в которых лишь m значений переменных x_j отличны от нуля. Любое решение системы (1), состоящее m+n неотрицательных значений переменных x_j (j=1, …, m+n),  называется допустим. Допустимое решение, в котором ровно m составляющих отличны от нуля, называется базисным решением. Иногда базисное решение называют планом. Очевидно, что не всякое базисное решение является оптимальным.

Так называемый симплекс-метод принадлежит к числу основных  аналитических методов решения основной задачи линейного программирования. Система ограничений в вычислительных методах обычно задается  системой линейных алгебраических уравнений

                               (2)

и среди неотрицательных решений системы уравнений (2) надо найти такое,  которое бы максимизировали или минимизировали линейную функцию

                                 (3)

Алгоритм решения состоит из следующих этапов. 

Во-первых, необходимо убедиться в совместности системы линейных алгебраических уравнений (2). Если ограничительные условия заданы неравенствами, то их нужно преобразовать в равенства путем  введения новых  неотрицательных переменных, так называемых балансовых (выравнивающих).

Работа симплекс-метода начинается с выбора опорного решения, содержащего r базисных переменных и n-r свободных переменных. Так как в задаче имеется m уравнений-ограничений, то неизвестные переменные  х1,…, х_r  (r≤m) можно  выразить  через  остальные  n-r  переменные  и  уравнения-ограничения (2) могут быть преобразованы к следующему виду:

                        (3),

где

Неизвестные переменные х₁,х₂,…,х_r называются базисными, остальные - свободными. Подставляя теперь в линейную форму l вместо базисных переменных их выражения через свободные из системы (3), получим:

l = g₀ + g_r+1x_r+1+…+g_nx_n                                             (4).

Теперь, полагая все свободные переменные равными нулю, найдём значения базисных переменных: x₁=b’₁, x₂=b’₂,…, х_r=b’_r. Таким образом, решение  системы (b’₁,  b’₂,…,  b’_r,  0,…,0) является  допустимым – оно называется  базисным. Подставляя в линейную форму l значения базисных переменных, получим базисное значение линейной формы B_l. Для полученного базисного решения  l_B=g₀. 

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

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

Таким  образом, далее меняем одну из свободных переменных с таким расчётом, чтобы значение l_В уменьшалось, или, по крайней мере, не увеличивалось, если нами решается задача на нахождение min l, т.е. переходим к новому базису В' такому, что l_В< l_B'. Процесс продолжается итеративно до тех пор, пока все коэффициенты в уравнении (4) не станут положительными. Если ищется max l, то переход к новому базису В' осуществляется так, чтобы выполнялось неравенство: l_B' > l_В. Соответственно, процесс продолжается  до тех пор, пока все коэффициенты в уравнении (4) не станут отрицательными. Следует отметить, что при выборе других начальных опорных решений процедура симплекс-метода приведет к тому же оптимальному решению.

Задание

Найти оптимальные неотрицательные решения, минимизирующие линейную форму:

Решение.

Составим матрицу и определим ее ранг, а также ранг расширенной матрицы.

                Так как ранги равны, система является совместной. Следовательно, выбираем 3 базисные переменные.

         В качестве базисных переменных выбираем x₄, х₅, х₆ и выражаем их и целевую функцию через свободные x₁, х₂, х₃.

Найдем первое опорное решение.

Нужно увеличивать х₃, чтобы выполнялось условие неотрицательности х_j.

Свободные переменные x₁, х₂, х₄.

Нужно увеличивать х₂.

            Свободные переменные x₁, х₄, х₅.

Ответ.  минимум функции