Исходные данные для решения задачи

Ресурсы	Затраты ресурсов на единицу продукции	Наличие ресурсов
А	Б
Труд	2	4
Сырье
Оборудование
Прибыль на единицу продукции

Экономико-математическая модель задачи будет иметь вид:

f( )=40х₁+60х₂→мах

2х₁+4х₂≤2000,

4х₁+4₂≤1400,

2х₁+х₂≤800,

х_1,2≥0.

В результате решения задачи симплексным методом был получен следующий оптимальный план:

Х=(200; 400; 0; 200; 0)

f( )=40х₁+60х₂=40 ´ 200 + 60 ´ 400=32000,

Y = (40/3; 0; 20/3),

g( )=2000у₁ + 1400у₂ + 800у₃=2000*40/3+800*20/3=32000

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

1. Увеличение объемов какого вида ресурсов наиболее выгодно?

2. На сколько можно увеличить запас сырья для улучшения полученного оптимального значения целевой функции?

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

4. Целесообразность включения в план новых изделий. Постараемся последовательно ответить на все поставленные вопросы.

Ценность ресурсов.В примере 3 объективно обусловленные оценки ресурса «труд» равны 40/3 (у₁ = 40/3): «сырье» — 0 (у₂ = 0): «оборудование» — 20/3 (y₃ = 20/3). Дефицитный ресурс, полностью используемый в оптимальном плане ( ), имеет положительную оценку (у > 0); недефицитный, не полностью используемый ресурс (для которого ), имеет нулевую оценку (y_i = 0). В примере «сырье» не является дефицитным ресурсом:

4х₁+х₂ ≤ 1400,

4 ´ 200 + 400 = 1200 < 1400 = b₂,

y₂ = 0;

а «труд» и «оборудование» — дефицитные ресурсы:

2х₁+4х₂<2000,

2*200+4*400=2000=b₁, y₁=40/3,

2х₁+х₂≤800,

2*200+400=800=b₃, y₃=20/3/

Чем выше величина оценки y₁, тем острее дефицитность i-гoресурса.

В примере «труд» более дефицитен, чем «оборудование»: 40/3>20/3. Наиболее выгодно увеличение объемов ресурса труда.

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

Чувствительность решения к изменению запасов сырья.

Предположим, что запас сырья ресурса «труд» изменился на 12 единиц, т.е. теперь он составляет 2000 + 12 = 2012 единиц. Из теоремы об оценках ∆f ( ) = у, •∆b_i, известно, что колебание величины bi приводит к увеличению или уменьшению f( ). Оно определяется величиной у_i в случае, когда при изменении величин b_i значения переменных y_i в оптимальном плане соответствующей двойственной задачи остаются неизменными. Поэтому необходимо найти такие интервалы изменения каждого из свободных членов системы ограничений исходной задачи линейного программирования, в которых оптимальный план двойственной задачи не менялся бы.

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

Рассмотрим модель исходной задачи (3.1) - (3.3) в матричной форме:

f( ) = С ´ X → max,

А´ Х<В,

Х≥0,

где X = (x₁,x₂,...,x_n) — вектор неизвестных;

С = (c₁,c₂, … ,c_n) — вектор коэффициентов при неизвестных в целевой функции;

B = (b₁, b₂,…, b_n) – вектор свободных членов ограничений исходной задачи;

- матрица коэффициентов в системе ограничений.

Приведем задачу к канонической форме, введем т дополнительных переменных. Задача примет вид:

f( ) = С * X → max,

где вектор неизвестных переменных X будет теперь иметь размерность п+т. Размерность матрицы А также изменится и будет равна m • (п+т).

Пусть известен оптимальный план. Разобьем вектор X на два подвектора: X* > 0 и Х° = 0. В первый включены неизвестные, вошедшие в базис оптимального решения (т.е. ненулевые в оптимальном плане). Соответственно матрицу А разобьем на две подматрицы: А*(размерность m*n) и А° (размерность m*m). Первую из них сформируют те столбцы матрицы А, которые соответствуют ненулевым неизвестным в оптимальном плане. Тогда А*Х* + А°Х° = В. Так как А°Х°=0, то А X* = В. Умножив обе части последнего равенства на матрицу, обратную матрице А*, получим А^*-1 А*Х* = А^*-1 В . Так как А^*-1 А* = Е, где Е — единичная матрица, то X* = А^*-1 В. Обозначим А^*-1 через D, тогда Х* = DB.

Матрица D характеризует влияние ресурсов на величину выпуска продукции X. Изменим размер выделяемых ресурсов, т.е. дадим приращение ∆В вектору В. Тогда

X + АХ = D(B + ∆В) = DB + D∆B. С учетом X = DB можно записать

АХ = D∆B.

Это соотношение определяет величину структурных сдвигов в выпуске продукции при изменении ограничений исходной задачи. Из соотношений второй теоремы двойственности видно, что двойственные оценки (переменные двойственные задачи) тесным образом связаны с оптимальным планом простой задачи. Всякое изменение исходных данных прямой задачи может оказать влияние как на ее оптимальный план (АХ = D∆B), так и на систему оптимальных двойственных оценок. Поэтому чтобы проводить экономический анализ с использованием двойственных оценок, нужно знать их интервал устойчивости.

Второе свойство двойственных оценок означает, что изменение значений величины b_i приводит к увеличению или уменьшению f( ). Это изменение, как выше уже отмечено, определяется величиной y_i и может быть определено лишь тогда, когда при изменении величин значения b_i переменных y_i в оптимальном плане соответствующей двойственной задачи остаются неизменными. Поэтому необходимо определить такие интервалы изменения каждого из свободных членов системы линейных уравнений АХ=В, в которых оптимальный план двойственной задачи не меняется. Это имеет место тогда, когда среди компонент вектора X=DB нет отрицательных.

Исходя из этого получаем следующие оценки нижних и верхних пределов устойчивости двойственных оценок при изменении каждого ограничения в отдельности. Пределы уменьшения (нижняя граница) определяются по тем x_k (k = 1,..., m), для которых соответствующие d_ki >0:

для d_ki>0 (3.14)

Пределы увеличения (верхняя граница) определяются по тем х_k, для которых dki <0:

для d_ki>0 (3.15)

Ослабление какого-либо i-гo ограничения приводит к тому, что с определенного момента оказывается возможным изменить структуру (набор векторов) в базисе плана, что ведет к скачкообразному уменьшению величины оценки. Так продолжается до тех пор, пока i-й ресурс вообще перестанет быть дефицитным и его оценка обратится в нуль.

Определим интервалы устойчивости двойственных оценок в примере 3. Матрица А имеет вид:

После приведения задачи к канонической форме матрица А примет следующий вид:

С ненулевыми значениями в оптимальный план вошли = 200, ⁼ 400 и = 200, следовательно, матрица А* будет составлена из первого, второго и четвертого столбцов матрицы А:

Для вычисления интервалов устойчивости необходимо найти матрицу D = А^*-1:

При вычислении интервалов устойчивости по формулами (3.14) и (3.15) примем = 200 = х_k₌₁, ⁼ 400 = x_k₌₂ и = 200 = x_k₌₃. интервалы устойчивости первого ресурса – «труд»:

min ;

При изменении запасов ресурса «труд» в пределах от 1400 до 3200 единиц двойственная оценка его не изменится.

Интервалы устойчивости второго ресурса - «сырье»: этот ресурс в оптимальном плане используется не полностью и поэтому не имеет верхней границы интервалов устойчивости; нижняя граница определяется следующим образом:

;

b₂= .

Интервалы устойчивости третьего ресурса – «оборудование»:

;

В нашем примере определим величину изменения объема прибыли от реализации продукции при увеличении ресурса «труд» на 12 единиц. Эти изменения находятся в интервалах устойчивости двойственных оценок, поэтому можно воспользоваться теоремой об оценках:

Объем прибыли увеличится на 160 единиц.

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

=198,

=404,

Структурных сдвигов в программе не произошло, но значения переменных в плане изменились: продукции вида А может быть выпущено на 2 единицы меньше, а продукции вида Б — на 4 больше. Значение целевой функции при новых ограничениях увеличится на 160 единиц.

Чувствительность решения к изменению коэффициентов целевой функции.

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

для d_ik>0;

для d_ik<0.

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

для второго коэффициента:

Таким образом, найденный оптимальный план выпуска продукции не будет меняться при изменении прибыли на единицу продукции А в диапазоне от 30 до 120 и прибыли на единицу второй продукции Б в диапазоне от 20 до 80.

Целесообразность включения в план новых изделий.

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

Эту задачу можно решить на основании свойства 3 двойственных оценок: в оптимальный план задачи на получение максимума прибыли может быть включен лишь тот вариант, для которого прибыль, недополученная из-за отвлечения дефицитных ресурсов, т.е. величина , покрывается полученной прибылью с_j. Таким образом, характеристикой того или иного варианта служит разность

при этом если , то вариант выгоден; если невыгоден.

Таблица 3.4

⇐ Предыдущая 1 2 3 45