Методы оптимизации в технико-экономических задачах
Дипломная работа - Менеджмент
Другие дипломы по предмету Менеджмент
ых выразить через остальные (n-m) переменных, которые играют роль произвольных постоянных и называются свободными. Те m неизвестных переменных, которые выражаются через свободные, называются базисными.
Решение называется базисом, если в нем m базисных неизвестных выражены через (n-m) свободных неизвестных, и при равенстве свободных неизвестных нулю, что предполагается в базисном решении, базисные неизвестные неотрицательны.
Пронумеруем переменные таким образом, чтобы вначале шли свободные переменные (x1, … , xk), а далее базисные переменные (xk+1 , … , xn)
, x2, … , xk, xk+1, xk+2, … , xk+i, … , xn
Выразим базисные переменные и целевую функцию через свободные переменные:
+i=bi - i=1..m=c0+> max
При решении задач линейного программирования принято находить минимум целевой функции, то есть f(x) > min, где f(x)=-F(x)
Существует несколько методов решения задач линейного программирования:
1.графоаналитический метод;
2.симплекс-метод;
В графоаналитическом методе следует учитывать что переменных должно быть не более двух. Здесь сначала на основе неравенств строится область допустимых значений. Любое неравенство двух переменных делит область на два подмножества: в одном они выполняются, в другом - нет. Подмножества представляют собой полуплоскости, разделяемые прямой, которая получается, если в ограничении заменить знак неравенства на знак равенства.
Затем находится градиент, если функцию необходимо минимизировать, и антиградиент функции, если максимизировать:
Значение функции будет уменьшаться при движении по направлению антиградиента, и увеличиваться по направлению градиента.
Далее следует уловить тот момент, в котором эта линия имеет последнюю общую точку с ОДР.
Симплекс-методом получивший также в литературе название метода последовательного улучшения плана, разработанный в 1947г. американским математиком Джорджем Данцигом. Он даёт аналитическое решение задачи для любого количества переменных и удобен в использовании.
Для решения задачи линейного программирования симплекс-методом все ограничения должны иметь вид равенств.
Первый этап решения задач симплекс-методом сводится к приведению задачи к канонической форме.
Второй этап представляет собой выбор начального базиса. Обычно в качестве базисных переменных выбирают те, которые изначально заданы в неравенствах.
Третий этап заключается в выражении целевой функции через свободные неизвестные. Для этого необходимо выразить все базисные переменные через свободные, а затем, подставить их в выражение для целевой функции.
В начальном опорном решении все свободные неизвестные полагаются равными нулю.
Для более простого, быстрого и наглядного решения задач линейного программирования симплекс-методом используют специальные таблицы, которые называются симплекс-таблицами.
Пусть имеется некоторая начальная симплекс-таблица:
базисные\свободныеxsxkСвободные членыxm?ms?mk?m0xr?rs?rk?r0xl?ls?lk?l0f(x)?fs?fk?f0, xr, xl - базисные неизвестные;
xs, xk - свободные неизвестные;
?ms, ?rs, ?ls, ?fs - коэффициенты, стоящие перед свободной неизвестной хs, в выражениях для базисных неизвестных xm, xr, xl и целевой функции, соответственно;
?mk, ?rk, ?lk, ?fk -коэффициенты, стоящие перед свободной неизвестной xk, в выражениях для базисных неизвестных xm, xr, xl и целевой функции, соответственно;
?m0, ?r0, ?l0, ?f0 -свободные члены в выражениях для базисных неизвестных xm,xr, xl и целевой функции, соответственно.
После заполнения симплекс-таблицы её необходимо проанализировать. Анализ следует начинать со строки, соответствующей целевой функции. Если в этой строке все коэффициенты положительны, за исключением, может быть, свободного члена, то полученное решение оптимальное и данная симплекс-таблица последняя. Свободные неизвестные, расположенные по столбцам, равны нулю, а базисные неизвестные получаются равными своим свободным членам.
Если отрицательный коэффициент есть в строке для целевой функции, но в этом же столбце, в котором стоит отрицательный коэффициент, все остальные коэффициенты положительные, то задача не имеет решений, то есть целевая функция не имеет минимума.
Если в строке для целевой функции есть хотя бы один отрицательный коэффициент и в этом же столбце есть ещё хотя бы один отрицательный коэффициент, то целевую функцию можно уменьшить за счёт увеличения соответствующей свободной неизвестной. Это увеличение ограничено вследствие отрицательности коэффициента в выражении для базисной неизвестной. Из выражения базисной неизвестной через свободную находится предел свободной неизвестной. Например, в приведённой выше симплекс-таблице в строке для целевой функцииf(x)коэффициент ?fs > 0,акоэффициент ?fk < 0.Приэтом коэффициенты ?rk и ?lk, стоящие в столбце свободной неизвестной хk отрицательные. Для отрицательных коэффициентов найдём отношение
(i=r,l)
и выберем среди полученных значений минимальное. Допустим, что получилось
mini()=
Минимум ищется по всем значениям. xk называется увеличиваемой свободной неизвестной, i принадлежит тому множеству, для которого ?ik отрицательное.
Возможно, что в строке для целевой функции есть несколько отрицательных коэффициентов (некоторое множество отрицательных коэффициентов). В этом случае, среди отрицательных коэффициентов, находящихся в строке целевой функции, нужно найти тот, который даёт наибольшее отрицательное приращение.
После проведения