3. Третья задача анализа на чувствительность. В каких пределах допустимо изменение коэффициентов целевой функции ?

Разобьём этот вопрос на два подвопроса.

Каков диапазон изменения того или иного коэффициента целевой функции, при котором не происходит изменение оптимального решения? Представим целевую функцию в виде F = c₁x₁ + c₂x₂ . Из рис.4 видно, что при увеличении с₁ или уменьшении с₂ прямая, представляющая целевую функцию F, вращается вокруг точки В по часовой стрелке. Если же с₁ уменьшается или с₂ увеличивается, то эта прямая вращается против часовой стрелки. Таким образом, точка В будет оставаться оптимальной точкой, пока наклон прямой не выйдет за пределы , определяемые наклонами прямых для ограничений (2) и (3). Когда наклон прямой F станет равным наклону прямой (2), получим две альтернативные оптимальные угловые точки В и С . Наличие альтернативных оптимумов говорит, что одно и то же оптимальное значение F может достигаться при различных значениях переменных.

Рис. 4

Найдём, например, допустимый интервал изменения с₁ , при котором точка В остаётся оптимальной. Исходное значение коэффициента с₂ = 2 оставим неизменным. Из рис.4 видно, что значение с₁ можно увеличивать, пока прямая F не совпадёт с прямой (3), или уменьшать, пока прямая F не совпадёт с прямой (2). Эти крайние значения коэффициента с₁ можно определить из равенства наклонов прямой F и прямой (3) (максимальное значение с₁) и равенства наклонов прямой F и прямой (2) (минимальный с₁). Т. к. тангенс угла наклона для прямой F равен , для прямой (3) 1, а для прямой (2) соответственно -, то минимальное с₁ определяем из равенства = -, откуда min с₁ = -1, а максимальное значение с₁ из равенства = 1, откудаmax c₁ = 2.

Значит, интервал изменения с₁ , в котором точка В остаётся единственной оптимальной точкой, определяется неравенством -1<с₁<2. При с₁ = 2 оптимальными угловыми точками будут точки В и С. Как только коэффициент с₁ станет больше 2, оптимум сместится в точку С , а если с₁ < -1, оптимум сместится в точку А.

2. Насколько следует изменить тот или иной коэффициент целевой функции, чтобы сделать некоторый недефицитный ресурс дефицитным, и наоборот, дефицитный ресурс сделать недефицитным ?

Можно заметить, что как только коэффициент с₁ станет больше 2, то ресурс (2) становится недефицитным, а ресурс (1) – дефицитным. Если же с₁ < -1, то недефицитным станет ресурс (3).

2.Аналитическое решение задачи лп.

Решим задачу F= 4x₁+6x₂→maxаналитически, с помощью симплекс

метода по следующему алгоритму:

1. Задачу ЛП приводят к каноническому виду и находят исходный опорный план.

2. Составляют исходную симплекс – таблицу.

3. Определяют, есть ли хотя бы одно отрицательное число Δj в (m + 1)-й строке. Если нет, то найденный опорный план оптимален.

4. Находят наименьшее отрицательное Δj и соответствующий столбец обозначают как разрешающий. Если в разрешающем столбце среди чисел a_ij нет положительных, то целевая функция не ограничена сверху, а задача ЛП не имеет решения.

5. Находят отношение b_i к положительным a_ij разрешающего столбца. Минимальное из этих отношений определяет разрешающую строку.

6. На пересечении разрешающих строки и столбца определяют разрешающий элемент.

7. Все элементы разрешающей строки делят на разрешающий элемент.

8. Все элементы разрешающего столбца (кроме разрешающего элемента) заменяют нулями.

9. Остальные элементы рассчитываются по правилу прямоугольника и фиксируется введение в базис новой переменной. Переходим к пункту 3.

Итак представим задачу в каноническом : F= 4x₁+ 6x₂→max

x₁-2x₂ +x₃=2

2x₁+x₂+x₄= 3

x₁+x₂+ x₅= 7

x₂+ x₆= 3

x_j≥ 0j= 1..6

Исходный опорный план x = { 0, 0, 2, 3,7, 3 }.

Т. о. Базисные переменные x₃, x₄, x₅, x_6, а свободные x₁, x₂ .

Составим симплекс-таблицу. Для расчета данной задачи воспользуемся программой Simplex позволяющей рассчитывать задачи ЛП с помощью прямого и обратного симплекс – методов. Решим систему уравнений относительно базисных переменных: x₃, x₄, x₅ Полагая, что свободные переменные равны 0, получим первый опорный план: X1=(0,0,2,0,7,3,3) Базисное решение называется допустимым, если оно неотрицательно.

Базис	B	x1	x2	x3	x4	x5	x6	x7
x3	2	1	-2	1	0	0	0	0
x7	3	2	1	0	-1	0	0	1
x5	7	1	1	0	0	1	0	0
x6	3	0	1	0	0	0	1	0
F(X0)	-3M	-4-2M	-6-M	0	M	0	0	0

Итерация №0.

Базис	B	x1	x2	x3	x4	x5	x6	x7
x3	^1/2	0	^-5/2	1	^1/2	0	0	^-1/2
x1	^3/2	1	^1/2	0	^-1/2	0	0	^1/2
x5	^11/2	0	^1/2	0	^1/2	1	0	^-1/2
x6	3	0	1	0	0	0	1	0
F(X1)	6	0	-4	0	-2	0	0	2+M

Итерация №1. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

Базис	B	x1	x2	x3	x4	x5	x6	x7
x3	8	5	0	1	-2	0	0	2
x2	3	2	1	0	-1	0	0	1
x5	4	-1	0	0	1	1	0	-1
x6	0	-2	0	0	1	0	1	-1
F(X2)	18	8	0	0	-6	0	0	6+M

Итерация №2. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэфициенты

Базис	B	x1	x2	x3	x4	x5	x6	x7
x3	8	1	0	1	0	0	2	0
x2	3	0	1	0	0	0	1	0
x5	4	1	0	0	0	1	-1	0
x4	0	-2	0	0	1	0	1	-1
F(X3)	18	-4	0	0	0	0	6	M

Итерация №3. 1. Проверка критерия оптимальности. Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты.

Базис	B	x1	x2	x3	x4	x5	x6	x7
x3	4	0	0	1	0	-1	3	0
x2	3	0	1	0	0	0	1	0
x1	4	1	0	0	0	1	-1	0
x4	8	0	0	0	1	2	-1	-1
F(X4)	34	0	0	0	0	4	2	M