Лекции по Экономической кибернетике

Подождите немного. Документ загружается.

.,...,1,0,0

;,..,1,

;

max

jjjs

ijsijs

QsKX

njK

bXa

















Задача на минимум затрат станочного времени

при заданной производственной программе

Для решения данной задачи преобразуем основные ограничения по фонду

времени работы оборудования i-ой группы в управления путем ввода

дополнительных неизвестных Zi, которые показывают резервный фонд времени

i-ой группы оборудования в плане загрузки станков.

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

.,...,1,0,0

;,...,1,

;

ПjKX

QsTX

bZXa

jjs

jjjs

iijsijs















Общий расход полезного времени и его недоиспользовании при заданном

фонде времени работы оборудования каждой группы связаны взаимно

однозначным соответствием: минимуму затрат станочного времени

соответствует максимум свободного резерва и наоборот. В связи с этим целевая

функция, обеспечивающая минимуму станочного времени на выполнение

заданной производственной программы, будет:

miiZ

,...,1max,)(







Одним из направлений в математическом моделировании экономических

задач является использование свойств двойственной задачи, которая может

быть сформулирована для любой задачи на оптимум. Хорошо разработанный

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

получать с помощью эффективных вычислительных процедур оптимальный

план, но также сделать ряд экономически содержательных выводов,

основанных на свойствах задачи, двойственной к исходной задаче линейного

программирования (ЗЛП).

Постановка двойственной задачи

Прямая задача Двойственная задача

 

max







xCxf

(7.1)

 

minyg 



(7.4)

bxa 



1

(7.2)

CYa 



1

(7.5)

0

(7.3)

0

(7.6)

Согласно теории линейного программирования каждой ЗЛП вида (7.1) -

(7.3) соответствует двойственная ей ЗЛП (7.4) - (7.6). Основные утверждения о

взаимно двойственных задачах содержится в двух следующих теоремах:

Первая теорема двойственности

Для взаимодвойственных задач вида (7.1-7.3) и (7.4-7.6) возможен один

из взаимоисключающих случаев:

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

решения, при этом значения целевых функций на оптимальных решениях

совпадают, то есть f(x)=g(Y).

2. В прямой задаче допустимое множество не пусто, а целевая

функция на этом множестве не ограничена сверху. При этом у двойственной

задачи будет пусто допустимое множество.

3. В двойственной задаче допустимое множество не пусто, а

целевая функция на этом множестве не ограничена снизу. При этом у

прямой задачи допустимое множество оказывается пустым.

4. Обе рассматриваемые задачи имеют пустые допустимые

множества.

Вторая теорема двойственности.

(теорема о дополняющей не жесткости)

Пусть вектор

=(х

, х

, ..., х

) допустимое решение прямой задачи (7.1-

7.3), а Y=(y

, y

, ..., y

) – допустимое решение двойственной задачи (7.4-7.6).

Для того, чтобы они были оптимальными решениями, необходимо и

достаточно, чтобы выполнялись следующие соотношения:





















ijij

bxaY

(7.7)





















jiij

CyaX

(7.8)

Условия (7.7) и (7.8) позволяют, если известно решение одной из взаимно

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

Теорема об оценках

Значения переменных Y

в оптимальном решении двойственной задачи

представляет собой оценки влияния свободных членов b

системы ограничений

- неравенств прямой задачи на величину ∆f(x):

∆ f (x) = ∆ b

(7.9)

Решая ЗЛП (7.1-7.3), симплексным методом, мы одновременно решаем и

двойственную задачу ЗЛП (7.4-7.6). Переменные двойственной задачи Y

называется объектно-обусловленными оценками.

Экономическая интерпретация двойственной задачи

Рассмотрим экономическую интерпретацию двойственной задачи на

следующих примерах.

Пример №1. Задача оптимального использования ресурсов

Для составления плана выпуска четырех видов продукции Р1-Р4 на

предприятии используют три вида сырья S1-S3. Объемы выделенного сырья,

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

вида продукции, приведем в следующей таблице 7.1.

Составим экономико-математическую модель задачи оптимального

использования на максимум прибыли. В качестве неизвестных примем Xj -

объем выпуска продукции j-го вида, где j=1,...,4.

Таблица 7.1.

Вид сырья Запасы

сырья

Вид продукции.

Р1 Р2 Р3 Р4

S1 35 4 2 2 3

S2 30 1 1 2 3

S3 40 3 1 2 1

ПРИБЫЛЬ 14 10 14 11

Модель задачи:















4023

3032

353224

max11141014)(

4321

xxxx

xxxxxf

функциональные условия

≥ 0, j=1,…,4 - прямые ограничения.

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

решила закупить все ресурсы рассматриваемого предприятия. При этом

необходимо установить оптимальную цену на приобретаемые ресурсы у

, у

исходя из двух условий:

1. покупающая организация старается минимизировать общую стоимость

ресурсов;

2. за каждый вид ресурсов надо уплатить не менее той суммы, которую

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

Согласно первому условию общая стоимость сырья выражается величиной:

g(Y) = 35Y

+ 30Y

+ 40Y

→ min

Согласно второму требованию вводятся ограничения: на единицу первого

вида продукции Р1 расходуются четыре единицы первого ресурса S1 ценой Y1,

одна единица второго ресурса ценой Y2 и три единицы третьего ресурса ценой

Y3. Стоимость всех ресурсов, расходуемых на производство единицы первого

вида продукции, равна 4Y

+ Y

+ 3Y

и должна составлять не менее 14, то есть

+ Y

+ 3Y

≥ 14.

В результате аналогичных рассуждений относительно производства

остальных (2,3) видов продукции система неравенств примет следующий вид:

+ Y

+ 3Y

≥ 14

+ Y

≥ 10

+ 2Y

≥ 14

+ 3Y

+ Y

≥ 11

Цены ресурсов, естественно, должны быть неотрицательные:

Y1≥0;Y2≥0;Y3≥0.

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

производственной программы

(х

,х

,…,х

) и при любом векторе оценок

=(Y

,…,Y

) выполняется неравенство

)yg()xf( 

, то есть ценность всей

выпущенной продукции не превосходит суммарной оценки имеющихся

ресурсов. Значит, величина

)xf(-)yg(

характеризует производственные потери

в зависимости от рассматриваемой производственной программы и выбранных

оценок ресурсов.

Из первой теоремы двойственности следует, что при оптимальных

производственной программе и векторе оценок ресурсов, производственные

потери равны нулю.

Согласно второй теоремы, предъявляются следующие требования:

;,...,1 , о т,0 если

mibXaY

iji







;,...,1 ,0 о т, если

miYbXa

iij







(7.10)

;,...,1j , о т,0 если

nCYaX

ijj







.,...,1j ,0 о т, если

nXCYa

jji







(7.11)

Условия (7.10) можно интерпретировать так: если оценка Yi единицы

ресурса i-го вида положительна, то при оптимальной производственной

программе этот ресурс используется полностью. Если же ресурс используется

не полностью, то его оценка равна нулю. Из условия (7.11) следует, что если j-й

вид продукции вошел в оптимальный план, то он в оптимальных оценках

неточен, если же j-й вид продукции убыточен, то он не войдет в план, не будет

выпуска.

Пример №2. Планирование выпуска продукции пошивочным

предприятием

Намечается выпуск двух видов костюмов – мужских и женских.

На женский костюм потребуется 1 метр шерсти, 2 метра лавсана и 1

человеко-день трудозатрат.

На мужской костюм – 3,5 метра шерсти, 0,5 метра лавсана и 1 человеко-

день трудозатрат.

Всего имеется 300 метров шерсти, 240 метров лавсана и 150 человеко-дней

трудозатрат.

Требуется определить оптимальное число костюмов каждого вида,

обеспечивающее максимальную прибыль предприятию, если прибыль от

реализации женского костюма составляет 10 денежных единиц, а от мужского

20 денежных единиц. При этом следует иметь ввиду, что необходимо сшить не

менее 60 мужских костюмов и обеспечить прибыль не менее 1400 денежных

единиц.

Модель задачи:

Введем обозначения:

и Х

– число соответственно женских и мужских костюмов. Прибыль от

реализации женских костюмов составляет 10Х

, а от реализации мужских

костюмов 20Х

, то есть необходимо максимизировать целевую функцию

f(x)=10Х

+20Х

max.

Ограничения задачи имеют вид:

+3.5Х

≤350

2Х

+0.5Х

≤240

+Х

≤ 150

10Х

+20Х

≥1400

≥ 60, Х

,Х

≥0

1. Необходимо привести все неравенства системы ограничений исходной

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

линейной формы, то все неравенства системы ограничений необходимо

привести к виду «≤».

Поэтому неравенства, в которых данное требование не выполняется, следует

умножить на (-1), в результате получим:

≥60 - Х

≤60

10Х

+20Х

≥1400 -10Х

-20Х

≤-1400

2. Выписываем матрицу А коэффициентов при переменных исходной

задачи и транспонируем ее:



















2010

5.02

5.31



















20115.05.3

100121

3. Составить систему ограничений двойственной задачи, для чего

коэффициенты при переменных взять компоненты транспортированной

матрицы Ат:

+2 Y

+ Y

- 10Y

≥10

3.5Y

+0.5 Y

+ Y

– Y

-20Y

≥ 20

1, 2, 3, 4, 5

≥0.

4.Составить линейную форму двойственной задачи, взяв

коэффициентами при неизвестных Y свободные члены системы ограничений

исходной задачи:

g(Y) =350Y

+240Y

+ 150Y

– 60Y

+1400Y

–

двойственная оценка ресурса «шерсть», которая может быть «ценой»

шерсти;

–

двойственная оценка ресурса «лавсан», которая может быть «ценой»

лавсана;

–

двойственная оценка ресурса «трудозатраты», которая может быть «ценой»

трудозатрат;

–

двойственная оценка заказа по выпуску женских и мужских костюмов;

–

двойственная оценка задания по прибыли.

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

Х= (70, 80, 0, 60, 0, 40, 900)

У= (4,0, 6, 0, 0, 0, 0)

f(x) = g(y )=2300.

Таким образом, максимальная прибыль составила 2300 денежных единиц,

при производстве 70 женских и 80 мужских костюмов.

Дополнительные переменные х

=0, х

=40, х

=900 показывают, что шерсть и

трудовые ресурсы использованы полностью (х

и х

=0), лавсана осталось 60 м

=х

, плановые задания перевыполнены по числу костюмов х

=40 и по прибыли

=900. Решение двойственной задачи указывает на дефицитность ресурсов

«шерсть» (У

=4) и «трудозатраты» (У

=6).

Пример №3. Размещение производственных заказов

В планируемом периоде необходимо обеспечить производство 300000

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

предприятия. Для освоения этого нового вида изделий нужны определенные

капитальные вложения. Разработанные для каждого филиала предприятия

проекты освоения нового вида изделия характеризуются величинами единицы

продукции удельных капиталовложений и себестоимостью единицы продукции

(Табл. 7.2.).

Предположим, что на все филиалы предприятия для освоения 300 тысяч

новых изделий может выделить 18 миллионов тенге.

Таблица 7.2.

Показатель

Филиал предприятия

1 2 3 4

Себестоимость производства

изделия, тенге

Удельные капиталовложения,

тенге

120

Необходимо найти такой вариант распределения объемов производства

продукции и капитальных вложений по филиалам, при котором суммарная

стоимость изделий будет минимальной.

Введем обозначения:

i - номер филиала (i=1,…,4);

– объем выпускаемой продукции в

i-ом филиале предприятия;

T – суммарная потребность в изделиях (Т=300000 штук);

K – выделяемые капиталовложения (К=18 млн. тенге);

– себестоимость производства продукции в

i-ом филиале;

- удельные капиталовложения на 1 продукции в i-ом филиале.

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

 

min







xCxf

;

Tx 





;

KxK







≥ 0 ; i=1,…,n , с учетом имеющихся данных.

f(x)=83Х

+ 89Х

+95Х

+98Х

→ min

+ Х

≥300000 штук

12Х

+80Х

+50Х

+40Х

≤ 18 млн. тенге

, x

≥ 0.

Сформулируем экономико-математическую модель двойственной задачи.

Введем обозначения переменных двойственной задачи Y

и Y

двойственная оценка выпускаемой продукции, которая может быть

ценой изделия;

- двойственная оценка капитальных вложений, которая может быть

представлена как коэффициент эффективности капитальных вложений.

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

g(Y)=T

- K

→ max

- K

≤ C

i=1,…,4

≥ 0; Y

≥ 0.

Целевая функция g(Y) означает, что необходимо максимизировать

разность между стоимостью произведенной продукции (T

) и величиной

капитальных вложений, соизмеренной во времени с выпуском заданного

объема продукции (K

). Разность между ними соответствует суммарному

«выигрышу» от вложенных капиталовложений на изготовление 300000

изделий.

Цена продукции Y

и коэффициент эффективности Y

взаимосвязаны.

Цена одного изделия, выпускаемого в каждом из филиалов, не может быть

больше, чем все производственные затраты, включающие в себя в данном

случае себестоимость С

и приведенные к текущим издержкам через

коэффициент эффективности капиталовложения K

Двойственная модель в числах запишется следующим образом:

g(Y)=300000

–18000000

→ max

–120

≤ 83

– 80

≤

– 50

≤95

– 40

≤ 98

≥0; Y

≥ 0.

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

= (0; 100000; 200000; 0);

= (105; 0; 2);

   

ygxf 

= 279 млн.

Которые говорят о том, что в первом и четвертом филиалах размещать

заказы по выпуску новых изделий невыгодно (x

=0 и x

=0). Выпуск следует

наладить во втором и третьем филиалах. При этом суммарная себестоимость

выпускаемых изделий составит 279 миллионов.

Тема 11. Экономико-математический анализ полученных оптимальных

решений

Экономико-математический анализ - важный этап моделирования

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

экономический процесс, и это упрощение сказывается как на исходной

информации, так и на получаемых результатах. В связи с этим невозможно

рассматривать процесс выборки решений как одноразовое аналитическое

действие.

Экономико-математический анализ решений осуществляется в двух

основных направлениях:

- вариантные расчеты по моделям с сопоставлением различных вариантов

плана;

- анализ каждого из полученных решений с помощью двойственных

оценок.

Вариантные расчеты могут осуществляться при постоянной структуре

самой модели, но с изменением величины конкретных показателей модели или

при варьировании элементов самой модели: - изменение критерия

оптимальности, добавление новых ограничений на ресурсы или на способы

производства, расширение множества вариантов и так далее.

Одно из эффективных средств экономико-математического анализа -

объективно обусловленные оценки оптимального плана. Такого рода анализ

базируется на свойствах двойственных оценок. Мы установили общие

математические свойства двойственных оценок для задач на оптимум любой

экономической природы. Однако экономическая интерпретация этих оценок

может быть совершенно различной для разных задач.

Экономические свойства оценок Y

оптимального плана:

1. Оценки как мера дефицитности ресурсов.

2. Оценки как мера влияния ограничения на функционал.

3. Оценки - инструмент определения эффективности отдельных

вариантов.

4. Оценки - инструмент балансирования суммарных затрат и результатов.

Таблица 7.3

Ресурсы

Затраты ресурсов на

единицу продукции

Наличие

ресурсов

А В

Труд 2 4 2000

Сырье 4 1 1400

Оборудование 2 1 800

Прибыль на единицу

продукции

40 60

На основании информации в таблице 7.3. составим план производства,

максимизирующий объем прибыли и проиллюстрируем свойства.

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

оптимальный план:

X = (200; 400;0; 200; 0)

f(X) = 40X

+ 60X

= 32000

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

g(Y) = 2000y

+ 1400y

+ 800y

= 32000

Свойство 1. Оценки как мера дефицитности ресурсов

Объективно обусловленные оценки выражают степень дефицитности,

ограниченности факторов производства по отношению к потребностям,

заданным целевой функции. Количественно степень дефицитности находит

выражение в предельных оценках эффективности факторов производства и

эффективности с точки зрения их вклада в целевую функцию. Все факторы, не

лимитирующие производство, получат нулевые оценки.

В нашем примере: объективно обусловленные оценки труда Y

= 40/3,

оборудования сырья Y

= 0, Y

= 20/3. Это свойство вытекает из второй теоремы

двойственности.

если Y

> 0, то

jij

bXa 





если

jij

bXa 



1

, то Y

= 0, i = 1, ..., m

Дефицитный ресурс, полностью используемый в оптимальном плане (

jij

bXa 





) имеет положительную оценку Y

> 0; не дефицитный, не

полностью используемый ресурс (для которого

jij

bXa 



1

) имеет нулевую

оценку Y

= 0.

В нашем примере сырье не является дефицитным ресурсом:

+ X

≤ 1400

200+ 400=1200<1400=b

1200 < 1400

=0.

Тогда как ресурсы, «труд» и «оборудование» используются полностью.