О САЙТЕ
Добро пожаловать!

Теперь вы можете поделиться своей работой!

Просто нажмите на значок
O2 Design Template

ФЭА / АИТ / ОТЧЕТ по дисциплине «Моделирование» на тему: «Линейное программирование. Симплексный метод» Задача №5

(автор - student, добавлено - 25-01-2014, 16:36)

 

 

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

 

 

ОТЧЕТ

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

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

Задача №5

 

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

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

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

                                    (1),

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

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

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

                               (2)

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

                                 (3)

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

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

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

                        (3),

где

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

l = g0 + gr+1xr+1+…+gnxn                                             (4).

Теперь, полагая все свободные переменные равными нулю, найдём значения базисных переменных: x1=b’1, x2=b’2,…, хr=b’r. Таким образом, решение  системы (b’1,  b’2,…,  b’r,  0,…,0) является  допустимым – оно называется  базисным. Подставляя в линейную форму l значения базисных переменных, получим базисное значение линейной формы Bl. Для полученного базисного решения  lB=g0

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

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

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

 

 

Задание

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

 

Решение.

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

 

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

         В качестве базисных переменных выбираем x4, х5, х6 и выражаем их и целевую функцию через свободные x1, х2, х3.

 

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

 

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

 

Свободные переменные x1, х2, х4.

 

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

 

            Свободные переменные x1, х4, х5.

 

 

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


Ключевые слова -


ФНГ ФИМ ФЭА ФЭУ
Copyright 2018. Для правильного отображения сайта рекомендуем обновить Ваш браузер до последней версии!