Анализ коэффициентов целевой функции

Возможно три случая анализа коэффициентов целевой функции:

а) при свободных;

б) при базисных переменных;

в) одновременного изменения всех коэффициентов.

Б.п.	СБ	А0	х1	х2	х3	х4	х5	х6	х7
			65	70	60	120	0	0	0
х4	120	500	5/12	-1/6	0	1	1/8	-1/24	0
х3	60	400	1/3	5/3	1	0	0	1/6	0
х7	0	200	-1/12	-19,6	0	0	-1/8	-7/24	1
Целевая функция		84 000	5	10	0	0	15	5	0

Случай а) . В примере свободными переменными служат х₁, х₂ и др. Поэтому разберем пределы изменения коэффициентов c ₁ и с₂. В целевой функции задачи

max Z = 65х₁ + 70*х₂ + 60*х₃ + 120*х₄,

дадим коэффициенту с₁, приращение ∆с₁. Тогда целевая функция примет вид:

max Z^/ = (65+∆с₁)*х₁ + 70*х₂ + 60*х₃ + 120*х₄.

Проделав симплексные преобразования с целевой функцией, придем к последней симплексной, в которой в индексной строке оценка ∆₁* будет заменена на ∆₁*– ∆с₁.

 

Б.п.	СБ	А0	х1	х2	х3	х4	х5	х6	х7
			65+∆с1	70	60	120	0	0	0
х4	120	500	5/12	-1/6	0	1	1/8	-1/24	0
х3	60	400	1/3	5/3	1	0	0	1/6	0
х7	0	200	-1/12	-19,6	0	0	-1/8	-7/24	1
Целевая функция		84 000	5-∆с1	10	0	0	15	5	0

 

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

5-∆с₁ ≥ 0.

Следовательно

-∞ ≤ ∆с₁ ≤ 5 (или y₄).

Вычислим пределы изменения с₁:

 

min c₁ = с₁+ min с₁ = c₁ + (-∞) = -∞;

max с₁ = с₁ + max с₁ = с₁ + y₄ = 40+5=45.

 

Т.е. в интервале (-∞, 45] все характеристики оптимального решения остаются неизменными, кроме значения дополнительной двойственной переменной у₄*, которая меняется на у₄*–∆с₁.

Т.к. с_i -– это цена единицы продукции, то с_i ≥ 0. Отсюда вывод: при изменении коэффициента в целевой функции при свободной переменной x_i, i Î R в пределах

[0; c_i + y*_m+i]

изменяется соответствующая этой переменной дополнительная двойственная переменная y*_m+i

y*_m+i= y*_m+i – ∆с_i.

Остальные, характеристики оптимального решения модели остаются без изменения.

Для примера получим:

10-∆с₂ ≥0.

Отсюда

-∞ ≤ ∆с₂ ≤ 10 (или y₅).

 

min c₂ = с₂+ min с₂ = c₁ + (-∞) = -∞;

max с₂ = с₂ + max с₂ = с₂ + y₅ = 70+10=80.

 

[0; 45] – для коэффициента с₁ и [0; 80] для коэффициента с₂.

Случай б). Для примера базисными являются переменные х₃ и x₄. Например, определим пределы изменения коэффициента с₃. В целевой функции исходной задачи заменим коэффициент с₃ на с_з + ∆с₃, получим: max Z' = 65х₁ + 70*х₂ + (60+∆с₃)*х₃ + 120*х₄. Найдя оптимальное решение, получим следующую симплексную таблицу:

 

Б.п.	СБ	А0	х1	х2	х3	х4	х5	х6	х7
			65	70	60+∆с3	120	0	0	0
х4	120	500	5/12	-1/6	0	1	1/8	-1/24	0
х3	60+∆с3	400	1/3	5/3	1	0	0	1/6	0
х7	0	200	-1/12	-19,6	0	0	-1/8	-7/24	1
Целевая функция		84 000+400∆с3	5+1/3∆с3	10+5/3∆с3	0	0	15+0*∆с3	5+1/6*∆с3	0

 

Таким образом, коэффициенты в строке целевой функции задачи, полученной из исходной путем замены коэффициента с_i у базисной переменной x_i на с_i + ∆с_i, представляют собой:

 

∆*₀=∆*₀+b_i*∆c_i

∆*_j=∆*_j+a_ii*∆c_i

 

Решение новой задачи будет оптимальным при неотрицательности оценок ∆*j индексной строки, т. е. при выполнении системы неравенств ∆*j ≥0.

Для примера получим:

 

Отсюда — -6 <∆с3 < +∞.

Пределы изменения коэффициента с3 равны:

 

min с3 = c3 + min∆с3=60-6=54;

max с3 = с3 + max ∆с3 = 60+∞=+∞.

 

Итак, при изменении с3 в пределах [54, +∞] сохраняется структура и числовые значения оптимального плана. Однако изменяется значение целевой функции и двойственных оценок, соответствующих свободным дополнительным переменным, и дополнительных двойственных оценок, соответствующих свободным основным переменным.

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

;

.

 

При изменении с_i, i Î Б в пределах [с_i + min ∆c_i, c_i + max ∆c_i] сохраняются значения всех базисных переменных, но изменяются значения целевой функции. Также изменяются значения двойственных переменных.

Например, для коэффициента с₃, используя формулы, получим:

 

;

.

 

Следовательно, получим, что при изменении c3 в пределах [54; +∞] сохраняется структура и значения оптимального плана. Значения целевой функции и оценок индексной строки можно найти как:

 

∆*₀= ∆*₀ + b_i*∆c₃ = 84 000+400*(-6)=60 000

∆*₀= ∆*₀ + b_i*∆c₃ = 84 000+400*+∞ = +∞.

 

Аналогично для других элементов индексной строки:

∆*_j=∆*_j+a_ii*∆c_i.

 

в) Общий случай (изменение всех коэффициентов в целевой функции). Как и в первых двух случаях, дадим приращение всем коэффициентам целевой функции. Составим задачу:

 

max Z= (65+∆с1)*х1 + (70+∆с2)*х2 + (60+∆с)3*х3 + (120+∆с4)*х4.

 

Решив ее симплексным методом, составим последнюю симплексную таблицу:

 

Б.п.	СБ	А0	х1	х2	х3	х4	х5	х6	х7
			65+∆с1	70+∆с2	60+∆с3	120+∆с4	0	0	0
х4	120+∆с4	500	5/12	-1/6	0	1	1/8	-1/24	0
х3	60+∆с3	400	1/3	5/3	1	0	0	1/6	0
х7	0	200	-1/12	-19,6	0	0	-1/8	-7/24	1
Целевая функция		84 000+500∆с4 +400∆с3	5-∆с1 +5/12∆с4 +1/3∆с3	10-∆с2 -1/6∆с4 +5/3∆с3	0	0	15+1/8∆с4 +0*∆с3	5-1/24∆с4 +1/6*∆с3	0

 

Чтобы сохранился исходный оптимальный план, необходимо на оценки индексной строки наложить условие неотрицательности, т. е. должна выполняться система неравенств:

 

_.

 

Решив ее, найдем взаимосвязанные пределы изменения ∆с_j.

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

1) для оценок основных переменных

;

2) для оценок дополнительных переменных