Двойственные оценки. 2

План

1. Двойственные оценки как мера дефицитности ресурсов продукции……...2     1.1.Двойственные оценки как мера влияния ограничений на функционал..7

    1.2.Двойственные оценки как инструмент определения эффективности

отдельных вариантов……………………………………………………………..9

2. Задача 2.4……………………………………………………………………..10
3. Задача 4.4.…………………………………………………………………….16
4. Список использованной литературы……………………………………….18

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Двойственные оценки как мера дефицитности ресурсов продукции.

В 1975 г. наш соотечественник Л.В. Канторович (1912 – 1986) был удостоен Нобелевской премии по экономике (совместно с американским экономистом Т. Купмансом) за разработку теории оптимального использования ресурсов.

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

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

 

 

 

 

 

 

 

Пусть в качестве исходной дана задача:

= c1x1 + c2x2 + ... + cnxn → max;
a11x1 + a12x2 + ... + a1nxn ≤ b1,  a21x1 + a22x2 + ... + a2nxn ≤ b2, ...             am1x1 + am2x2 + ... + amnxn ≤ bm;	(2.4)
xj ≥ 0,

 

Задача линейного программирования, двойственная задаче (2.4), будет иметь  вид:

= b1y1 + b2y2 + ... + bmym → min;
a11y1 + a21y2 + ... + am1ym ≥ c1,  a12y1 + a22y2 + ... + am2ym ≥ c2, ...             a1ny1 + a2ny2 + ... + amnym ≥ cn;	(2.5)
yi ≥ 0,   .

Можно сформулировать правила получения двойственной задачи из задачи исходной.

1. Если в исходной задаче  ищется максимум целевой функции,  то в двойственной ей - минимум. 

2. Коэффициенты при переменных  в целевой функции одной задачи  являются свободными членами  системы ограничений другой задачи.

3. В исходной ЗЛП все функциональные ограничения - неравенства вида “≤”, а в задаче, двойственной ей, - неравенства вида “≥”.

4. Коэффициенты при переменных  в системах ограничений взаимно  двойственных задач описываются  матрицами, транспонированными относительно  друг друга. 

5. Число неравенств в  системе ограничений одной задачи  совпадает с числом переменных  в другой.

6. Условие неотрицательности переменных сохраняется в обеих задачах.

Связь между оптимальными планами взаимно двойственных задач  устанавливают теоремы двойственности.

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

.

(2.6)

Если целевая  функция одной из двойственных задач  не ограничена, то условия другой задачи противоречивы.

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

	(2.7)

 

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

Теорема об оценках. Значения переменных в оптимальном решении двойственной задачи представляют собой оценки влияния свободных членов b_i в системе ограничений прямой задачи на величину целевой функции :

(2.8)

Компоненты оптимального решения двойственной задачи принято называть двойственными оценками. Часто употребляется также термин «объективно обусловленные оценки».

На свойствах двойственных оценок базируется экономико-математический анализ распределения ресурсов. В  пределах устойчивости двойственных оценок имеют место свойства, рассмотренные  ниже.

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

Формулировка прямой (исходной) задачи:

= 2x1 + 4x2 → max;
4x1 + 6x2 ≤ 120,  2x1 + 6x2 ≤ 72,  x2 ≤ 10;
x1 ≥ 0,   x2 ≥ 0.

Получим двойственную задачу.

= 120y1 + 72y2 + 10y3 → min;
4y1 + 2y2 ≥ 2,  6y1 + 6y2 + y3 ≥ 4,
y1 ≥ 0,   y2 ≥ 0, y3 ≥ 0.

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

= (24, 4); = (1/3, 1/3, 0).

Легко убедиться, что при  подстановке оптимальных планов в целевые функции задач оба  получаемых значения равны 64.

Двойственные оценки отражают сравнительную дефицитность факторов производства. Чем выше величина оценки , тем выше дефицитность i-го ресурса. Факторы, получившие нулевые оценки, не являются дефицитными и не ограничивают производство.[3]

В нашем примере нулевую  оценку получил третий ресурс ( = 0), поэтому он не является дефицитным, т.е., с точки зрения задачи, фонд рабочего времени на участке С не ограничивает производство. Напротив, первый (участок А) и второй (участок В) ресурсы являются дефицитными, причем ограничивают производство в одинаковой степени ( = = 1/3).

Последнее утверждение легко  подтвердить, подставив  и в ограничения исходной задачи:

 

424 + 64 = 120,  224 + 64 = 72,  4 < 10.

Откуда видно, что при  реализации оптимального плана фонд рабочего времени участка С, действительно, расходуется не полностью

1. Двойственные оценки как мера влияния ограничений на функционал.

Объективно обусловленные (оптимальные) оценки — одно из основных понятий линейного программирования, введенное Л. В. Канторовичем. Это оценки продуктов, ресурсов, работ, выступающих в качестве ограничений в условиях решаемой оптимизационной задачи. Их называют также двойственными оценками, разрешающими множителями, множителями Лагранжа и целым рядом других терминов. Будучи элементами двойственной задачи линейного программирования, они показывают, насколько изменится значение критерия оптимальности в соответствующей прямой задаче при приращении данного ресурса на единицу (т. е. имеют предельный характер).Оценки выступают, следовательно, как мера дефицитности ресурсов и продукции, как мера влияния ограничений на функционал; их можно использовать далее как инструмент определения эффективности отдельных технологических способов с позиций общего оптимума и, наконец, как инструмент балансирования суммарных затрат и результатов.[4]

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

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

Объективно обусловленные оценки применяются в оптимизационных расчетах: при решении задач размещения производства, наиболее рационального прикрепления поставщиков к потребителям, оптимального раскроя материалов и др. В перспективном планировании эти оценки могут использоваться в качестве ориентировочных цен, характеризующих будущие соотношения ресурсов и потребностей общества. (Эта их роль хорошо отражена в термине, принятом в западной литературе, — “теневые цены”.) При этом учитываются следующие закономерности. С течением времени Объективно оптимальные оценки имеют тенденцию к снижению. При развитии народного хозяйства по оптимальной траектории оптимальная оценка стремится к нормальной оценке, которая складывается из прямых затрат и затрат обратной связи, возникающих вследствие ограниченности капитальных вложений. Эти закономерности объясняются тем, что на долговременном отрезке развития дефицитность воспроизводимых ресурсов будет выравниваться в результате соответствующего распределения капитальных вложений. Оптимальные оценки, таким образом, определяются всей совокупностью условий общественного производства и потребления, учитываемых при составлении плана (прогноза).

На основе Объективно обусловленных  оценок были выработаны многообразные методы экономико-математического анализа хозяйственных процессов. Ставился вопрос об их использовании и в ценообразовании[1]

 

2. Двойственные оценки как инструмент определения  эффективности отдельных вариантов.

Оценки как инструмент определения эффективности отдельных  хозяйственных решений. С помощью двойственных оценок можно определить выгодность выпуска новых изделий, эффективность новых технологических способов производства. При этом эффективным может считаться тот вариант производства, для которого сумма прибыли, недополученной из-за отвлечения дефицитных ресурсов, будет меньше прибыли получаемой. Разница между этими величинами (Δ_j) вычисляется как:

(2.9)

В том случае, если Δ_j ≤ 0, вариант производства является выгодным, если Δ_j > 0 – вариант невыгоден.

Пример: Пусть предприятие планирует к выпуску новый вид изделий: бейсбольные биты. Для производства одной биты необходимо затратить 3 часа работы на участке А, 4 часа работы на участке В и 1 час работы на участке С. Прибыль, получаемая от продажи одной биты, составляет $3. Выгодно ли предприятию выпускать новую продукцию?

Для ответа на вопрос рассчитаем Δ_j по формуле (2.9):

Δ_j = 3ּ + 4ּ + 1ּ - 3 = 3ּ1/3 + 4ּ1/3 + 1ּ0 - 3 = -2/3,

Δ_j < 0, значит производить бейсбольные биты выгодно.[2]

 

 

 

Задача 2.4.

На имеющихся у фермера 400 га земли он планирует посеять  кукурузу и сою. Сев и уборка кукурузы требуют на каждый гектар 200 ден. ед. затрат, а сои 100 ден. ед. На покрытие расходов, связанных с сеном и уборкой, фермер получил ссуду в 60 тыс. ден. ед. Каждый гектар, засеянный кукурузой, принесет 30 центнеров, а каждый гектар, засеянный соей, — 60 центнеров. Фермер заключил договор на продажу, по которому каждый центнер кукурузы принесет ему З ден. ед., а каждый центнер сои —6 ден. ед. Однако согласно этому договору фермер обязан хранить убранное зерно в течение нескольких месяцев на складе, максимальная вместимость которого равна 21 тыс. центнеров.

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

Построить экономико-математическую модель задачи, дать необходимые комментарии  к ее элементам и получить решение  графическим методом. Что произойдет, если решать задачу на минимум, и почему?

Решение:

Площадь земли	Тип культуры
	Кукуруза х1	Соя х2	400
Расходы на посев и уборку	200	100	60000
Вместимость склада	30	60	21000
	3. 30	6. 60

 

Пусть х₁ гектаров нужно засеять кукурузы, х₂ – сои.

Первое ограничение  задачи – по площади –  имеет  вид:   х₁+ х₂ ≤ 400, т.к. у фермера всего имеется 400 га земли. 

Второе ограничение  – по общим затратам на сев и  уборку: 200х₁+100х₂ ≤ 60 000, т.к. фермер получил на расходы ссуду в 60 тыс. ден.

Третье ограничение  – по объему собранного зерна: 30х₁+60х₂ ≤ 21 000, т.к. вместимость склада составляет 21 тыс. центнеров.

Прибыль фермера: 30х₁∙3+60х₂∙6 = 90x₁+120x₂ (ден. ед.)

Построим экономико-математическую модель задачи:

max f(X) = 90x₁+120x₂

х₁+ х₂ ≤ 400

200х₁+100х₂ ≤ 60 000

30х₁+60х₂ ≤ 21 000

x_1,2 ³ 0

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

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

Остальные три – функциональные ограничения.

1. Определим область допустимых решений первого неравенства. Оно состоит из решения уравнения и строгого неравенства. Решением уравнения служат точки прямой x₁+x₂=400. Построим прямую a по двум точкам (0;400) и (400;0), которые легко получить в результате последовательного обнуления одной из переменных.

Область решений  строгого неравенства — одна из полуплоскостей, на которую делит плоскость построенная прямая. Какая из них является искомой, можно выяснить при помощи одной контрольной точки. Если в произвольно взятой точке, не принадлежащей прямой, неравенство выполняется, то оно выполняется и во всех точках той полуплоскости, которой принадлежит контрольная точка, и не выполняется во всех точках другой полуплоскости. В качестве такой точки удобно брать начало координат. Подставим координаты (0; 0) в неравенство x₁+x₂≤400, получим 0 ≤ 400, т.е. оно выполняется. Следовательно, областью решения неравенства служит нижняя полуплоскость.

Аналогичным образом  построим области решения двух других неравенств

200x₁+100x₂=60 000

2 x₁+ x₂ = 600

x₁ = 0, x₂ = 600

x₁ = 300, x₂ = 0

По точкам (0;600), (300;0) построим прямую b.

200х₁+100х₂ ≤ 60 000 при x₁ = x₂ = 0;

0 ≤ 60 000  выполняется, берется левая полуплоскость.

30x₁+60х₂=21 000

x₁ = 0, x₂ = 350

x₁ = 700, x₂ = 0

По точкам (0;350) и (700;0) построим прямую c.

30х₁+60х₂ ≤ 21 000 при x₁ = x₂ = 0;

0 ≤ 21 000 выполняется, берется нижняя полуплоскость.

Выделим общую  область для всех неравенств. Обозначим вершины области латинскими буквами и определим их координаты, решая систему уравнений двух пересекающихся соответствующих прямых. Например, определим координаты точки C, являющейся точкой пересечения первой и второй прямой:

x₁+x₂=400,         x₁ = 200; x₂ = 200

2 x₁+ x₂ = 600.

Аналогично поступим для  других точек, являющихся вершинами области АВСDO, представляющей собой область допустимых решений рассматриваемой ЗЛП. Координаты этих вершин имеют следующие значения: А(0;350), В(100;300), С(200;200), D(300;0), О(0;0).

2. Построим вектор-градиент  , координаты которого являются частными производными функции f(X), т.е. =(90;120). Чтобы построить этот вектор, нужно соединить точку (90;120) с началом координат. При максимизации целевой функции необходимо двигаться в направлении вектора-градиента, а при минимизации — в противоположном направлении.

3. Приравняем целевую функцию постоянной величине а:

90x₁+120x₂ = а.

Это уравнение  является множеством точек, в котором  целевая функция принимает значение, равное а. Меняя значение а, получим семейство параллельных прямых, каждая из которых называется линией уровня. Пусть а=0, вычислим координаты двух точек, удовлетворяющих соответствующему уравнению 90x₁+120x₂ = 0. В качестве одной из этих точек удобно взять точку О(0;0), а так как при x₁ = 4   x₂ = -3, то в качестве второй точки возьмем точку E(4;-3).

Через эти две  точки проведем линию уровня f(Х)= 90x₁+120x₂ = 0.

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

Решение исходной ЗЛП:

Вычислим значение целевой функции в точке  B (100;300):

f(Х)= 90x₁+120x₂=90∙100 + 120∙300 = 45000.

max f(Х) =45000,  достигается при x₁ = 100, x₂=300.

Следовательно, чтобы получить максимальную прибыль, фермер должен засеять 100 га земли кукурузой, 300 га – соей. При этом прибыль составит 45 000  ден. ед.

Если поставить  задачу минимизации функции f(Х) = 90x₁+120x₂ при тех же ограничениях, линию уровня необходимо смещать параллельно самой себе в направлении, противоположном вектору-градиенту. В нашем случае минимум функции будет в точке О(0;0). Это означает, что фермер не получит ни чего, если не засеет поле зерновыми культурами.

 

 

 

 

 

 

 

 

 

 

 

 

Задача 4.4.

На станке производятся детали в количестве 20 тыс. штук в месяц. Эти детали используются для производства продукции на другом станке с интенсивностью 5000 шт. в месяц. По оценкам специалистов компании, издержки хранения составляют 5 руб. в год за одну деталь. Стоимость производства одной детали равна 2,50 руб.,а затраты на подготовку производства составляют 1000 руб. Каким должен быть размер партии деталей, производимой на первом станке и с какой частотой следует запускать производство этих партий?

Постройте график общих  годовых затрат.

Решение:

К = 1000 шт.,

V = 5000 шт. в месяц или 60000 шт. в год,

S = 5 руб. в год за деталь,

= 20000 шт. в месяц или 240000 шт. в год.

     Найдем размер  партии деталей, производимой  на первом станке по формуле  Уилсона:

в год

 

      Частота  запускания партий в производство:

года или 1,08 месяцев

 

      Общие затраты  на управление запасами:

                         руб. в год

 

Рис.3  График общих годовых  затрат.

 

 

 

 

 

Список использованной литературы:

1. http://slovari.yandex.ru
2. http://emm.ostu.ru/lect/lect2_3.html#vopros5
3. Орлова И.В. Экономико-математическое моделирование: Практическое пособие по решение задач. – М.: Вузовский учебник, 2004.
4. Орлова И.В. Половников В.А. Экономико-математические методы и модели: компьютерное моделирование: Учебное пособие. – М.:Вузовский учебник, 2007.