Анализ оптимального решения на чувствительность

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

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

Задачи, решаемые методами анализа на чувствительность, очень разнообразны. Рассмотрим возможности анализа на чувствительность для задач, аналогичных примеру 2.1 (т.е. для задач, где требуется определить оптимальные объемы производства нескольких изделий при ограничениях на ресурсы).

Статус ресурсов

По статусу ресурсы делятся на дефицитные и недефицитные. Если для реализации оптимального решения ресурс расходуется полностью, то он называется дефицитным, если не полностью - недефицитным. Статус ресурсов определяется по значениям остаточных переменных. В примере 2.1 алюминий и пластмасса являются дефицитными ресурсами, так как они расходуются полностью (см. подраздел 2.2.3.4). Сталь - недефицитный ресурс, так как 90 кг стали остаются неизрасходованными (х₄= 90). Увеличение запасов дефицитных ресурсов позволяет увеличить целевую функцию (прибыль). Снижение запасов дефицитных ресурсов приводит к снижению прибыли. Увеличение запасов недефицитных ресурсов всегда нецелесообразно, так как оно приводит только к увеличению неизрасходованных остатков. Запас недефицитного ресурса можно снизить на величину его остатка; это никаким образом не влияет на оптимальное решение (в том числе на оптимальные объемы производства и на прибыль), уменьшается только неизрасходованный остаток ресурса. Если запас недефицитного ресурса снизится на величину, превышающую его остаток, то для определения нового оптимального плана производства необходимо решать задачу заново.

В примере 2.1 увеличение запасов алюминия и пластмассы позволит увеличить прибыль. Запас стали можно снизить на 90 кг (т.е. до 160 кг); эти 90 кг стали предприятие может, например, продать или использовать в другом цехе. Например, если запас стали составит не 250, а только 200 кг, то оптимальное решение задачи будет следующим: х₁=4; х₂=24; х₃=0; х₄=50; х₅=0; Е=7600 ден. ед. Таким образом, оптимальное решение не изменится (кроме снижения неизрасходованного остатка стали).

Если запас стали снизится более чем на 90 кг (т.е. составит менее 160 кг), то для определения нового оптимального плана производства необходимо решать задачу заново. Для нового оптимального решения изменятся не только значения переменных, но и состав переменных в оптимальном базисе (т.е. в оптимальный базис будут входить не переменные х₁,х₂ и х₅, а другие переменные). Значение целевой функции при этом снизится, т.е. составит менее 7600 ден. ед.

Ценность ресурсов

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

Примечание. Вместо названия «ценность ресурса» используются также названия «теневая цена», «скрытая цена».

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

Для примера 2.1 ценность алюминия равна 1,33 ден. ед./кг, ценность пластмассы- 14,67 ден. ед./кг. Это означает, например, что увеличение запаса алюминия на единицу (т.е. на 1 кг) приводит к увеличению прибыли предприятия в среднем на 1,33 ден. ед. Например, если запас алюминия увеличится на 100 кг (т.е. составит 300 кг), то прибыль составит примерно 7600+1,33*100= 7733 ден. ед. Снижение запаса алюминия приведет к соответствующему снижению прибыли.

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

Ценность недефицитного ресурса всегда равна нулю. В данном примере ценность стали равна нулю, так как увеличение ее запаса не приводит к увеличению прибыли, а снижение (не более чем на 90 кг) - не приводит к снижению прибыли.

Ценность ресурса показывает максимальную (предельную) цену, по которой выгодно закупать ресурсы. Например, в рассматриваемой задаче предприятию выгодно закупать алюминий по цене не более 1,33 ден. ед./ кг, пластмассу — по цене не более 14,67 ден. ед./кг. Закупка ресурса по цене, превышающей его ценность, означает, что затраты предприятия на закупку ресурса превышают прибыль от его использования.

 

Анализ на чувствительность к изменениям запасов ресурсов

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

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

x₁=4–0,01d

х₂=24+0,05d

х₄=90–0,13d (2.3)

Е=7600+14,67d

 

Здесь коэффициенты -0,01; 0.05; -0.13 и 14,67 взяты из столбца переменной х₅ в окончательной симплекс-таблице (табл. 2.4).

Пусть, например, запас пластмассы составляет не 500,а 600 кг. Хотя постановка задачи изменилась, для поиска нового оптимального решения не требуется решать задачу заново. Достаточно подставить в уравнения (2.3) величину d= 100 (так как запас пластмассы увеличился по сравнению с первоначальной постановкой задачи на 100 кг) Новое оптимальное решение оказывается следующим: х₁=3;х₂=29;х₄=77;Е=9067. Это означает, что в новых условиях (при запасе пластмассы 600 кг) цеху следует выпускать за смену 3 корпуса и 29 задвижек. Неизрасходованный остаток стали составит примерно 77 кг. Прибыль составит примерно 9067 ден ед. Алюминий и пластмасса будут израсходованы полностью (переменные х₃ и х₅ остаются небазисными, т.е. равными нулю).

Примечание. Так как прибыль от выпуска одного корпуса составляет 100 ден. ед., а от одной задвижки - 300 ден. ед., можно подсчитать точную величину прибыли: 100*3+300*29=9000 ден. ед. Можно также определить точную величину расхода стали на выпуск изделий: 10*3+5*29=175 кг; значит, остаток составит 250 - 175 = 75 кг. Незначительные неточности в результатах, полученных на основе анализа на чувствительность, связаны с округлениями, допускавшимися при расчетах в симплекс-таблицах.

Пусть запас пластмассы составляет не 500, а 400 кг. Для поиска нового оптимального решения достаточно подставить в уравнения (2.3) величину d = -100 (так как запас пластмассы уменьшился по сравнению с первоначальной постановкой задачи на 100 кг).

Новое оптимальное решение следующее: х₁=5;х₂=19;х₄=103;Е=6133. Это означает, что в новых условиях (при запасе пластмассы 400 кг) цеху следует выпускать за смену 5 корпусов и 19 задвижек. Неизрасходованный остаток стали составит примерно 103 кг. Прибыль составит примерно 6133 ден. ед. Алюминий и пластмасса будут израсходованы полностью (переменные х₃ и х₅ остаются небазисными, т.е. равными нулю).

Примечание. Точная величина прибыли для данного решения составляет 100*5 +300*19 = 6200 ден. ед. Точная величина остатка стали составит 250-10*5-5*19 = 105кг.

Можно также определить диапазон изменений запаса ресурса, при котором состав переменных в оптимальном базисе остается прежним. Этот диапазон находится из условия неотрицательности всех переменных. Так, для примера 2.1 диапазон допустимых изменений запаса пластмассы, не приводящий к изменению состава переменных в оптимальном базисе, находится из следующих условий:

 

х₁=4-0,01*d≥ 0

х₂=24+0,05*d≥ 0

х₄=90-0,13*d≥ 0

 

Решив эту систему неравенств, получим: —480≤ d≤ 400. Это означает, что базис оптимального решения будет состоять из переменных х₁, х₂, х₄, если запас пластмассы, заданный в постановке задачи, будет составлять от 500-480 до 500+400 кг, т.е. от 20 до 900 кг. Для любой величины запаса пластмассы, входящей в этот диапазон, новое оптимальное решение можно найти из уравнений (2.3).

Аналогично можно найти, что базис оптимального решения будет состоять из переменных х₁, х₂, х₄, если запас алюминия будет составлять от 120 до 391,5 кг. Для определения этого диапазона потребуется использовать коэффициенты из столбца переменной х₃.

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

Например, уравнения (2.3) нельзя использовать для определения нового оптимального решения, если запас пластмассы составит 1100 кг (т.е. увеличится на 600 кг). Если подставить величину d = 600 в уравнения (2.3), то переменная х₁ (количество корпусов) примет отрицательное значение, что не имеет смысла. Чтобы получить оптимальный план выпуска изделий, необходимо решить задачу заново, изменив ограничение на запас пластмассы следующим образом: 5х₁+20х2≤ 1100

Примечание. Аналогично выполняется анализ на чувствительность к изменению любых ограничений «меньше или равно», независимо от того, что они означают: ограничения на запасы ресурсов или какие-либо другие величины.

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

В задачах, аналогичных примеру 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. Решить задачу линейного программирования, составленную в лабораторной работе №1 средствами табличного процессора Ехсеl.

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

 

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

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

2. Перечислите виды анализа решения на чувствительность и их основные положения.

 

Лабораторная работа № 3

ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ КАК ЧАСТНЫЙ СЛУЧАЙ ОБЩЕЙ РАСПРЕДЕЛИТЕЛЬНОЙ

ЗАДАЧИ

Цель работы

1. Рассмотреть постановку задачи.

2. Усвоить поиск допустимого решения.

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

 

Теоретическое введение