X5 выводим из базиса;

Таким образом, Б₁={x₁, x₂, x₄}. В результате получаем табл. 3.

Таблица 3

Базис	Св. член	x1	x2	x3	x4	x5
x1	2	1	0	2/3	0	-1/3
x2	1	0	1	-1/3	0	2/3
x4	5	0	0	-2/3	1	-5/3
f	3	0	0	1/3	0	1/3

Из табл. 3 следует, что БР₁={x₁=2, x₂=1, x₄=5}. БР₁ является допустимым и, следовательно, оптимальным решением.

Таким образом, задача ЛП

имеет решение x*=(2, 1), при этом f(x*)=3.

4.2. Анализ моделей на чувствительность

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

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

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

Рассматривают три задачи анализа на чувствительность:

1. На сколько можно увеличить или сократить запасы ресурсов?

2. Увеличение запаса какого из ресурсов наиболее выгодно?

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

Методику графического анализа чувствительности проиллюстрируем на примере следующей задачи ЛП:

(1)

(2)

(3)

.

Графическое решение данной задачи приведено на рис. 1.

Рис. 1

На рис. 1 видно, что задача ЛП имеет решение x*=(2, 1), при этом f(x*)=3. Ограничения (1) и (3) являются связывающими, а ограничение (2) – несвязывающим. Соответственно, 1-й и 3-й ресурсы являются дефицитными, а 2-й ресурс – недефицитным.

Первая задача анализа на чувствительность

В рамках первой задачи анализа модели на чувствительность определяются:

1) предельно допустимое увеличение запаса дефицитного ресурса, позволяющее улучшить найденное оптимальное решение;

2) предельно допустимое снижение запаса недефицитного ресурса, не изменяющее найденное оптимальное решение.

Методика определения предельно допустимого увеличения запаса дефицитного ресурса заключается в следующем.

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

2. Определяют координаты точки , в которой i-е ограничение становится несвязывающим.

3. Подставляют координаты точки в левую часть i-го ограничения и вычисляют:

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

Координаты точки являются решением системы уравнений

x₁+2x₂=4 [прямая(3)];

x₂=0 [прямая(4)].

В результате получаем =(4, 0).

Подставляя координаты точки в левую часть ограничения (1), вычисляем максимально допустимый запас 1-го ресурса:

p₁( )=2×4+0=8.

Рис. 2

Целевая функция при этом равна

f( )=4+0=4.

На рис. 3 видно, что при увеличении запаса 3-го ресурса прямая (3) перемещается по направлению градиента до её предельного положения (3′), проходящего через точку , являющуюся новым оптимальным решением.

Координаты точки являются решением системы уравнений

2x₁+x₂=5 [прямая(1)];

3x₁ +4x₂=15 [прямая(2)].

В результате получаем =(1, 3).

Подставляя координаты точки в левую часть ограничения (3), вычисляем максимально допустимый запас 3-го ресурса:

P₃( )=1+2×3=7.

Целевая функция при этом равна

f( )=1+3=4.

Методика определения предельно допустимого уменьшения запаса недефицитного ресурса заключается в следующем.

Рис. 3

1. Перемещают прямую, соответствующую i-му несвязывающему ограничению, до пересечения с оптимальной точкой x*.

2. Подставляют координаты точки x* в левую часть i-го ограничения и вычисляют:

Из рис. 1 следует, что при уменьшении запаса 2-го ресурса прямая (2) перемещается против направления градиента. При этом оптимальное решение не изменится, если перемещение происходит до пересечения с оптимальной точкой x*=(2, 1).

Подставляя координаты точки x* в левую часть ограничения (2), вычисляем минимально допустимый запас 2-го ресурса:

p₂(x*)=3×2+4×1=10.