Основы анализа на чувствительность (анализ модели после нахождения оптимального решения)

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

В связи с этим представляется логичным выяснить:

1. На сколько можно увеличить запас некоторого вида сырья для улучшения полученного оптимального значения целевой функции?

2. На сколько можно снизить запас некоторого вида сырья при сохранении полученного оптимального значения целевой функции?

3. Увеличение объемов какого вида сырья наиболее выгодно?

4. Каков диапазон изменения того или иного коэффициента целевой функции, при котором не происходит изменения оптимального решения?

Прежде чем ответить на первые два вопроса, классифицируем ограничения на активные и неактивные. Прямая, представляющая активное ограничение, должна проходить через оптимальную точку. В противном случае соответствующее ограничение будет неактивным. На рис.1 активными ограничениями являются (1) и (3), т.е. те, которые лимитируют запасы сырья S1 и S3.

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

Рассмотрим вначале сырье S1 (ограничение 1). Из рис.1 видно, что при увеличении запаса этого вида сырья прямая (1) (отрезок СД) перемещается вверх параллельно самой себе, постепенно стягивая в точку треугольник СКД. В точке К становятся активными ограничения (2) и (3). Оптимальному решению при этом будет соответствовать точка К, в которой ограничение (1) становится неактивным. Поэтому дальнейший рост запаса сырья S1 не следует увеличивать сверх того предела, когда ограничение становится неактивным (избыточным).

Этот предельный уровень определяется путем подстановки координат точки К(11/3;5/3) в левую часть ограничения (1). В результате получим

1×11/3 + 1×5/3 = 16/3,

F(K) = 3×11/3 + 4×5/3 = 53/3.

Аналогично рассматривается вопрос о целесообразности увеличения запаса дефицитного сырья S3. Из рис.1 видно, что при увеличении этого вида сырья прямая (3) (отрезок BС) перемещается вверх параллельно самой себе. В точке L ограничение (3) становится неактивным, поэтому объем сырья S3 не следует увеличивать сверх этого предела. Этот предельный уровень определяется путем подстановки координат точки L(0;5) в левую часть ограничения (3). В результате получим

1×0 + 2×5 = 10,

F(L) = 3×0 +4×5 = 20.

Рассмотрим теперь вопрос об уменьшении запаса недефицитного сырья S2 (ограничение 2). Из рис.1 видно, что не изменяя оптимального решения прямую (2) (отрезок КЕ) можно перемещать параллельно самой себе до пересечения с точкой С. Уменьшение запаса сырья S2 до величины 8 (2×3 + 1×2 = 8) никак не повлияет на оптимальность полученного ранее решения.

Результаты проведенного анализа помещены в таблице 2.

Таблица 2

Сырье	Тип сырья	Максимальное изменение запаса	Максимальное изменение прибыли
S1	дефицитное	16/3 - 5 = 1/3	53/3 - 51/3 = 2/3
S2	недефицитное	9 - 8 = 1	17 - 17 = 0
S3	дефицитное	10 - 7 = 3	20 - 17 = 3

Для ответа на третий вопрос введем характеристики ценности каждой дополнительной единицы сырья. Обозначим ценность дополнительной единицы i-го вида сырья через Yi, где

Yi ={ максимальное приращение F() / максимальное изменение запаса сырья Si}.

Тогда Y1 = 2, Y2 = 0, Y3 = 1.

Полученные результаты свидетельствуют о том, что дополнительные вложения в первую очередь следует направлять на закупку сырья S1 и лишь затем - на закупку сырья S3.

При выяснении вопроса относительно величины диапазона изменения того или иного коэффициента целевой функции, в котором не происходит изменения оптимального решения опять обратимся к рис.1. Из него видно, что при небольшом изменении коэффициентов целевой функции с1 и с2 прямая F() =17 вращается вокруг точки С. Таким образом, точка С будет оставаться оптимальной до тех пор пока прямая F() не выйдет за пределы, определяемые первым и третьим ограничениями {пока вектор будет находиться между нормалями к первому и третьему ограничениям}.

Определим сначала диапазон изменения коэффициента с1 при фиксированном коэффициенте с2 (с2 = 4). Тангенсы углов наклона для векторов , , соответственно равны: tg() = c2/c1, tg( 1) = 1, tg ( 3) = 2.

Поэтому диапазон изменения коэффициента с1 в целевой функции определится из соотношения 1£ c2/c1 £ 2, т.е. 2 £ c1 £ 4.

Диапазон изменения коэффициента c2 при фиксированном c1 (c1 = 3) определяется аналогично, т. е. 3 £ c2 £ 6.

Симплекс-метод решения задачи производственного планирования

Все точные методы решения общей задачи линейного программирования (ОЗЛП) косвенные, т.е. не непосредственно решаем ОЗЛП, а решаем некоторую другую задачу и на основе ее делаем вывод о решении ОЗЛП. Такой косвенной задачей в ЛП является каноническая задача линейного программирования (КЗЛП).

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

F() = () max (min) (1)

A = (2)

0 (3)

rang (A) = m < n, (4)

где = (c1, c2,..., cn)^T, = (X1,X2,..., Xn)^T,

A = (aij) m, n = (, ,..., ), = (b1, b2,..., bm)^T, 0.

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

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

Канонический вид, рассмотренной в параграфе 1.2, задачи производственного планирования будет следующим:

F() = 3×X1 + 4×X2 + 0×X3 + 0×X4 + 0×X5 max

при ограничениях

X1 + X2 + X3 = 5

2×X1 + X2 + X4 = 9

X1 + 2×X2 +X5 = 7

Xj 0, j = 1,..., 5.

 

Рис. 1 Геометрическая интерпретация задачи производственного планирования

Каждую точку пространства решений можно определить с помощью переменных X1, X2, X3, X4, X5. Увеличение переменных X3, X4, X5 будет соответствовать смещению допустимых точек с границ пространства решений в его внутреннюю область. Нас интересует прежде всего алгебраическое представление вершин допустимого множества. Анализируя рисунок можно записать:

 

Вершина	нулевые переменные (свободные)	ненулевые переменные (базисные)
A B C Д E	x1, x2 x1, x5 x3, x5 x3, x4 x2, x4	x3, x4, x5 x2, x3, x4 x1, x2, x4 x1, x2, x5 x1, x3, x5

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

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

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

Матрица K^(S) может быть получена следующим образом:

.

Тогда

.

В нашей задаче

,

, , .

 

K⁽⁰⁾ определяет исходный опорный план. Это вершина А на рис. 1. Приведем решение, рассмотренной выше, задачи в симплекс-таблице.

Таблица 1

номер итерации								=
			-3	-4				F(X) = 0
			1/2 3/2 1/2				-1/2 -1/2 1/2	3/2 11/2 7/2
			-1					F(X) = =14
					-3 -1		-1
								F(X) = =17

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

а) оптимальное решение.

Используя данные симплекс-таблицы основные результаты можно представить в следующем виде:

= (3, 2, 0, 1, 0),

X1 = 3 - объем производства продукции вида А1,

X2 = 2 - объем производства продукции вида А2,

F()= 17 - прибыль от реализации продукции.

б) статус видов сырья.

Сырье S1 - дефицитное, так как значение остаточной переменной X3 равно нулю. Сырье S2 - недефицитное, так как значение остаточной переменной X4 равно единице. Положительное значение остаточной переменной указывает на неполное использование соответствующего вида сырья. Сырье S3 - дефицитное, так как значение остаточной переменной X5 равно нулю. Увеличение запасов сырья S1 и S3 позволит улучшить найденное решение.

в) ценность сырья.

Ценность различных видов сырья характеризуется величиной улучшения оптимального значения F(), приходящегося на единицу прироста соответствующего вида сырья:

, .

Как следует из теории линейного программирования ценность видов сырья можно определить по формуле:

, , где

- номер единичного столбца с единицей на i-м месте в матрице ,

- коэффициент при переменной в целевой функции,

- симплексная разность при переменной в последней итерации.

В нашем примере:

Y1 = = 2 + 0 = 2

Y2 = = 0 + 0 = 0

Y3 = = 1 + 0 = 1.

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

Предположим, что запас первого вида сырья изменился на , т.е. теперь он составляет 5+ единиц. Введение скажется только на правой части симплекс-таблицы. Все же изменения правой части можно непосредственно определить по данным симплекс-таблицы. А именно, коэффициенты при в правых частях ограничений будут равны коэффициентам при первой остаточной переменной, т.е. при переменной X3. Так как изменение запаса сырья может повлиять на допустимость базисного решения, то величина должна быть ограничена решением системы неравенств:

-3/2 1/3 или ().

В данном диапазоне изменения запаса сырья S1 переменные X1, X4, X2 остаются базисными и определяют оптимальное базисное решение. В этом случае остаются неизменными виды производственной деятельности.

При исследовании чувствительности базиса к изменению запасов сырья S2 и S3 поступим аналогично. Соответственно получим:

,

,

, .

Так как изменение запасов сырья может повлиять только на допустимость решения, то интервалы изменения запасов сырья в общем случае определятся из соотношений:

× ,

Þ .

д) чувствительность оптимального плана к вариациям коэффициентов целевой функции.

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

F()=

Симплексные разности при базисных переменных X1, X4, X2 останутся равными нулю. Коэффициенты при в симплексных разностях небазисных переменных X3 и X5 будут равны коэффициентам при этих переменных в уравнении соответствующем базисной переменной X1, так как именно при этой переменной изменился коэффициент. Таким образом получим

, .

Аналогично для случая

F() =

получим

, .

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

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

.

= .

,

,

,

,

,

Þ .