Анализ на чувствительность к изменениям коэффициентов целевой функции

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

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

Будем обозначать коэффициенты Е-строки в окончательной симплекс-таблице как F_j, j=1,…,k (где k –общее количество переменных в задаче).

Выполним анализ на чувствительность к изменению прибыли от выпуска одного корпуса для примера 2.1. Пусть эта прибыль изменилась на dден. ед. и составляет не 100, а 100 +dден. ед. Величина dможет быть как положительной (прибыль от выпуска одного корпуса увеличилась), так и отрицательной (прибыль снизилась). Если изменение прибыли не выходит за некоторый диапазон (определяемый ниже), то новые значения коэффициентов E-строки при небазисных переменных для окончательной симплекс-таблицы, а также новое оптимальное значение целевой функции можно найти следующим образом:

F₃=1,33+0,05d

F₅=14,67-0,01d (2.4)

E=7600+4d,

где F₃, F₅ новые значения коэффициентов E-строки при небазисных переменных в окончательной симплекс–таблице.

Величины 0,05; -0,01 и 4 взяты из строки переменной х₁ в окончательной симплекс-таблице (табл. 2.4). Пусть, например, прибыль от выпуска одного корпуса составляет не 100, а 120 ден. ед. Подставив в уравнения (2.4) величину d= 20 (так как прибыль увеличилась по сравнению с первоначальной постановкой задачи на 20 ден. ед.), найдем новые значения коэффициентов Е-строки в окончательной симплекс-таблице: F₃=2,33; F₅=14,47. Новое оптимальное значение целевой функции составит Е = 7680 ден. ед. Значения коэффициентов Е-строки остались неотрицательными, оптимальное решение задачи не изменяется: х₁=4; х₂=24; х₃=0; х₄₌90; х₅=0. Это означает, что в новых условиях (при увеличении прибыли от выпуска одного корпуса до 120 ден. ед.) цеху по-прежнему следует выпускать за смену 4 корпуса и 24 задвижки. Прибыль от их выпуска составит 7680 ден. ед.

Анализ на чувствительность к изменению коэффициентов целевой функции позволяет выяснить диапазоны изменений этих коэффициентов, для которых найденное решение задачи остается оптимальным. Признаком оптимальности решения являются неотрицательные значения всех коэффициентов Е-строки (см. подраздел 2.2.2.4).

Найдем диапазон изменения прибыли от выпуска одного корпуса, для которого найденное решение задачи (х₁=4;х₂=24;х₃=0;х₄=90;х₅=0) останется оптимальным. Для этого необходимо, чтобы все коэффициенты Е-строки оставались неотрицательными:

F₃=1,33+0,05d≥ 0

F₅=14,67-0,01d≥ 0

Решив эту систему неравенств, получим:—26,6≤ d≤ 1467. Это означает, что найденное для задачи решение (х₁=4;х₂=24;х₃=0;х₄=90;х₅=0) оптимально, если прибыль от выпуска одного корпуса будет составлять от 100 – 26,6 до 100 +1467 ден. ед., т.е. от 73,4 до 1567 ден. ед. Для любой величины прибыли, входящей в этот диапазон, новые значения коэффициентов Е-строки и целевой функции можно найти из уравнений (2.4).

Аналогично можно определить, что оптимальное решение задачи не изменится, если прибыль от выпуска одной задвижки будет составлять от 6,6 до 433 ден. ед. Для определения этого диапазона потребуется использовать коэффициенты из строки переменной х₂ (табл. 2.4).

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

Например, если прибыль от выпуска одного корпуса составит 1600 ден. ед. (т.е. увеличится на 1500 ден. ед.), то для получения оптимального плана выпуска изделий необходимо решить задачу заново, изменив целевую функцию следующим образом: Е= 1600х₁ + 300х₂ →max. Прежнее оптимальное решение (х₁=4;х₂=24;х₃=0;х₄=90;х₅=0) уже не является оптимальным. В этом легко убедиться, подставив величину d=1500 в систему уравнений (2.4): коэффициент Е-строки при переменной х₅ принимает значение – 0,33, т.е. становится отрицательным. В то же время прежнее решение остается допустимым, так как значения х₁=4 и х₂=24 удовлетворяют ограничениям задачи.

Порядок выполнения работы

1. Изучить теоретическую часть.

2. Решить задачу линейного программирования симплекс-методом и средствами табличного процессора Ехсеl.

3. Провести анализ полученного решения на чувствительность.

2.4 Контрольные вопросы

1. Расскажите принцип работы симплекс-метода.

2. Перечислите основные этапы реализации симплекс-метода.

3. Что называется базисом?

4. Расскажите правила определения переменных для включения в базис и исключения из базиса.

5. Перечислите правила преобразования симплекс-таблицы.

6. Какой элемент симплекс-таблицы называется ведущим?

7. Что называется анализом оптимального решения на чувствительность?