Методы оптимизации в технико-экономических задачах

В начальном опорном решении все свободные неизвестные полагаются равными нулю.

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

Пусть имеется некоторая начальная симплекс-таблица:

, 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 отрицательное.

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

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