Барабаш С.Б. Экономико-математические методы и модели
Подождите немного. Документ загружается.
линии уровня целевой функции. Вектор, компоненты которого являются
коэффициентами целевой функции при переменных х
1
и х
2
, называют
градиентом целевой функции и обозначают grad Z. В нашем примере
grad Z = (215, 250). Вектор grad Z показывает направление возрастания
функции Z и перпендикулярен ее линиям уровня.
Целевая функция может возрастать до тех пор, пока линии уровня,
соответствующие возрастающим значениям этой функции, пересекают
область допустимых решений. Точка пересечения области допустимых
решений и линии уровня, соответствующей максимально возможному
значению целевой функции, и будет точкой максимума.
На рис. 1.2 видно, что оптимальное решение соответствует точке С,
лежащей на пересечении прямых (1) и (2). Поэтому ее координаты
находятся как решение системы линейных уравнений, задающих эти
прямые:
3х
1
+ 5х
2
= 1500,
2.5х
1
+ 2х
2
= 860.
Решая систему, находим
, . При этом значение
целевой функции
x
1
200
*
= x
2
180
*
=
88000180250200215250215
*
2
*
1
*
=×+×=+= xxZ
.
Полученное решение означает, что предприятию необходимо
ежемесячно производить 200 единиц продукции А и 180 единиц
продукции В, что позволит ему получать максимальную месячную
выручку в размере 88000 руб.
1.3. Построение двойственной задачи
Оптимальное решение задачи линейного программирования
определяется теми значениями параметров модели, которые они имели в
момент ее формирования и построения. В реальной экономике значения
параметров, формирующих модель, с течением времени или под
воздействием каких-либо обстоятельств могут меняться. В связи с этим
особый интерес представляют методы, позволяющие определить
изменения в оптимальном решении, обусловленные изменениями значений
параметров модели. Одним из источников таких методов является теория
двойственности, результаты которой позволяют также проводить
экономический анализ оптимальных решений экономико-математических
моделей.
Будем называть исходную задачу линейного программирования
прямой. Двойственная задача — это некоторая задача линейного
программирования, формулируемая на основе определенных правил
непосредственно из прямой задачи. Перепишем построенную выше
математическую модель оптимизации производственной программы:
Z = 215x
1
+ 250x
2
→ max,
3x
1
+ 5x
2
≤ 1500,
2.5x
1
+ 2x
2
≤ 860,
x
1
+ 2x
2
≤ 800,
х
1
≥ 0, х
2
≥ 0,
и будем считать ее прямой задачей. Правила построения двойственной
задачи сводятся к следующему.
1.
Каждому ограничению прямой задачи (кроме ограничений х
1
≥ 0,
х
2
≥ 0) соответствует неотрицательная переменная двойственной задачи. В
нашем примере три ограничения. Следовательно, в двойственной задаче
будет три переменных. Обозначим их через u
1
, u
2
, u
3
, где u
1
соответствует
первому ограничению, u
2
— второму, u
3
— третьему.
2.
Каждой переменной прямой задачи соответствует ограничение
двойственной. Следовательно, в нашем примере двойственная задача будет
иметь два ограничения.
3.
Коэффициенты при какой-либо переменной в ограничениях прямой
задачи и коэффициент целевой функции при этой переменной становятся
соответственно
• коэффициентами того ограничения двойственной задачи, которое
соответствует этой переменной, и
• правой частью формируемого ограничения двойственной задачи.
В нашем примере переменной х
1
соответствует первое ограничение
двойственной задачи; коэффициенты 3, 2.5 и 1 при х
1
являются
коэффициентами первого ограничения двойственной задачи, а
коэффициент целевой функции прямой задачи при х
1
, т.е. 215, становится
правой частью первого ограничения, записываемого со знаком “≥”. Таким
образом, первое ограничение двойственной задачи примет вид
3u
1
+ 2.5u
2
+ u
3
≥ 215.
4.
Коэффициентами целевой функции двойственной задачи являются
правые части ограничений прямой задачи, причем ищется минимум этой
функции. Следовательно, в нашем примере целевая функция двойственной
задачи примет вид
W = 1500u
1
+ 860u
2
+ 800u
3
→ min.
Применение этих правил к задаче оптимизации производственной
программы приводит к следующей двойственной задаче:
найти неизвестные значения переменных u
1
, u
2
, u
3
, удовлетворяющие
ограничениям:
3u
1
+ 2.5u
2
+ u
3
≥ 215,
5u
1
+ 2u
2
+ 2u
3
≥ 250,
u
1
≥ 0, u
2
≥ 0, u
3
≥ 0,
и доставляющие минимальное значение целевой функции
W = 1500u
1
+ 860u
2
+ 800u
3
→ min.
1.4. Нахождение оптимального решения двойственной задачи
Главное место в теории двойственности занимают теоремы
двойственности. Для их формулировки нам потребуются записи прямой и
двойственной задач в следующем общем виде.
Прямая задача
Двойственная задача
Найти неизвестные значения
переменных х
1
, х
2
, ..., х
n
,
удовлетворяющие ограничениям
, i = 1, …, m, (4) ax b
ij j
j
n
i
=
∑
≤
1
x
j
≥ 0, j = 1, …, n, (5)
и доставляющие максимальное
значение целевой функции
. (6) Zcx
jj
j
n
=→
=
∑
1
max
Найти неизвестные значения
переменных u
1
, u
2
, ..., u
m
,
удовлетворяющие ограничениям
au c
ij i
i
m
j
=
∑
≥
1
, j = 1, …, n, (7)
u
i
≥ 0, i = 1, …, m, (8)
и доставляющие минимальное
значение целевой функции
Wb
. (9)
u
ii
i
m
=→
=
∑
1
min
Задача (4) – (6) является обобщением рассматриваемой нами задачи
оптимизации производственной программы, в которой для производства n
видов продукции х
1
, х
2
, ..., х
n
используется m видов ресурсов в объемах b
1
,
b
2
, ..., b
m
при затратах i-го ресурса на выпуск единицы j-й продукции в
количестве a
ij
и выручке от реализации единицы произведенной продукции
j-го вида в размере с
j
, j = 1, …, n.
Для задач (4) – (6) и (7) – (9) теоремы двойственности формулируются
следующим образом.
Теорема 1 (первая теорема двойственности). Если одна из задач
(4) – (6), (7) – (9) имеет оптимальное решение, то и другая задача имеет
оптимальное решение. При этом оптимальные значения целевых функций
совпадают, т.е. max Z = min W.
Если значения целевой функции одной из задач не ограничены в
области допустимых решений (в прямой задаче сверху, а в двойственной
— снизу), то другая задача вообще не имеет допустимых решений.
Теорема 2 (вторая теорема двойственности). Допустимые решения
X = (x
1
, x
2
, ..., x
n
), U = (u
1
, u
2
, ..., u
m
) прямой и двойственной задач
оптимальны тогда и только тогда, когда выполняются следующие условия:
, i = 1,…, m, (10) ub ax
ii ijj
j
n
(−
=
∑
1
0)=
)
, j = 1,…, n. (11)
xauc
jiji
i
m
j
(
=
∑
−=
1
0
Заметим, что условия (10) – (11) часто называют «условиями
дополняющей нежесткости».
Теорема 2 может быть использована для нахождения оптимального
решения U
*
двойственной задачи при известном оптимальном решении X
*
прямой задачи. Для этого известные значения компонент , , ...,
вектора X
x
1
*
x
2
*
x
n
*
*
подставляются в соотношения (10) – (11). В результате такой
подстановки получается система линейных уравнений относительно
неизвестных величин u
1
, u
2
, ..., u
m
, решение которой позволяет получить
оптимальные значения , , ...,
u
. Для рассматриваемой нами задачи
соотношения (10) – (11) будут иметь вид:
u
1
*
u
2
*
m
*
uxx
112
1500 3 5 0(−− =)
,
0)2155.23(
3211
=
−+
+
uuux
,
uxx
212
860 2 5 2 0(. )−−=
,
0)250225(
3212
=−
+
+
uuux
.
0)2800(
213
=
−
− xxu
,
Подставляя в них найденные значения
x
1
200
*
=
, , получим:
x
2
180
*
=
так как
x
1
200
*
=
≠ 0, то
3 2 5 2 215 0
123
uuu
+
+
−
=
.
;
так как
x
2
180
*
=
≠ 0, то
5 2 250 0
123
uuu
+
+
−
=
;
так как 800 – –2 = 800 – 2·× 200 – 2 × 180 = 230 ≠ 0, то u
x
1
*
x
2
*
3
= 0.
Таким образом, получаем систему уравнений:
2155.23
321
=
+
+
uuu
,
250225
321
=
+
+
uuu
,
u
3
= 0.
Решая данную систему, находим оптимальные значения переменных
двойственной задачи:
u
1
30
*
=
,
u
2
50
*
=
,
u
3
0
*
=
.
Вычислим оптимальное значение целевой функции двойственной
задачи: , т.е.
880008008601500
*
3
*
2
*
1
*
=×+×+×= uuuW
Z
W
**
==88000, что
соответствует первой теореме двойственности.
1.5. Экономическая интерпретация переменных и оптимального
решения двойственной задачи
В то время как экономическая интерпретация задачи (4) – (6) ясна,
содержательный смысл двойственной к ней задачи (7) – (9), а также ее
переменных не столь очевиден. Можно показать, что единица измерения
двойственной переменной u
i
имеет вид
⎥
⎦
⎤
⎢
⎣
⎡
ресурсаго-единица
руб.
i
. Поэтому
естественно интерпретировать переменные двойственной задачи как
стоимостные оценки используемых ресурсов, а ее целевую функцию —
как суммарную стоимостную оценку этих ресурсов.
Сама двойственная задача может быть сформулирована следующим
образом: какую оценку u
i
следует назначить единице каждого ресурса,
чтобы при заданных объемах используемых ресурсов b
i
и заданных
размерах выручки с
j
от реализации единицы продукции минимизировать
общие затраты ресурсов, вычисленные в оценках u
i
?
Переменные u
i
в разных источниках именуются по-разному.
Например, их называют учетными, неявными, теневыми ценами ресурсов.
Из теории двойственности следует, что оптимальное значение переменной
u
i
равно приросту оптимального значения целевой функции в прямой
задаче в том случае, когда наличный объем i-го ресурса увеличился на
единицу, а объемы остальных ресурсов остались неизменными. Таким
образом, оценка i-го ресурса характеризует ценность или, как говорят,
предельную полезность единицы этого ресурса только с позиций
увеличения целевой функции.
Это означает, что интерпретация оптимального значения переменной
u
i
как цены i-го ресурса носит условный характер, а значение u
i
непосредственно зависит от всех параметров модели: запасов ресурсов b
i
,
норм затрат a
ij
и выручки c
j
. Один и тот же ресурс может иметь разные и
весьма далекие друг от друга оценки u
i
в моделях с различными
значениями параметров b
i
, a
ij
, c
j
.
Для исследуемой задачи оптимизации производственной программы
получим:
u
1
— стоимостная оценка сырья, ее размерность [руб./кг];
u
2
— стоимостная оценка времени работы оборудования, ее
размерность [руб./ст.-час];
u
3
— стоимостная оценка трудовых ресурсов, ее размерность [руб./чел.-
час];
30
*
1
=u
означает, что при увеличении месячного размера
используемого сырья на единицу с 1500 (кг) до 1501 (кг) увеличение
максимальной суммарной выручки составит =30 (руб.), а при
уменьшении сырья на единицу выручка уменьшится на
u
=30 (руб.);
u
1
*
1
*
u
2
50
*
=
означает, что при увеличении месячного фонда времени
работы оборудования на единицу с 860 (ст.-час) до 861 (ст.-час)
увеличение максимальной суммарной выручки составит = 50 (руб.), а
при уменьшении фонда времени на единицу выручка уменьшится на
= 50
u
2
*
u
2
*
(руб.);
u
3
0
*
=
означает, что ни увеличение, ни уменьшение трудовых
ресурсов не приведет к изменению оптимального значения суммарной
выручки. Этот вывод имеет достаточно простое объяснение.
Действительно, использование трудовых ресурсов для выпуска
оптимальных объемов продукции
x
1
200
*
=
, составит
x
2
180
*
=
5603602002
*
2
*
1
=+=+ xx
(чел.-час), а на предприятии может быть
задействовано 800 (чел.-час). Следовательно, 800 – 560 = 240 (чел.-час)
трудовых ресурсов остаются не занятыми. Поэтому прирост трудовых
ресурсов или их сокращение (но не более, чем на 240 чел.-час) не приведет
к изменению оптимальной программы выпуска и, следовательно, к
изменению оптимального значения суммарной выручки.
Найденные значения
u
1
30
*
=
,
u
2
50
*
=
,
u
3
0
*
=
позволяют сделать
следующие выводы:
• предприятию выгодно приобретение дополнительного сырья, если
его рыночная цена не превышает 30 руб. за кг.;
• предприятию выгодна установка дополнительного оборудования,
если затраты, связанные с установкой и эксплуатацией этого
оборудования, не превышают 50 руб. за один станко-час;
• предприятию целесообразно сократить используемые при
производстве изделий А и В трудовые ресурсы, но не более, чем на
240 чел.-час.
Задача 2. Математическая модель оптимизации производства с
использованием кредита
Пусть T = 40, а остальные исходные данные задачи имеют
числовые значения, представленные в следующей таблице:
Нормы затрат ресурсов
Наименование
ресурсов
А В
Объем
ресурсов
Сырье (кг)
Оборудование (станко-час)
Трудовые ресурсы (чел.-час)
3
6
8
5
4
2
1500
1560
?
Цена изделия (руб.) 1259 766
2.1. Построение математической модели оптимизации
Для построения модели введем следующие обозначения:
x
1
— объем выпуска продукции А,
x
2
— объем выпуска продукции В,
S — потребность в трудовых ресурсах,
t — почасовая ставка оплаты труда,
V — размер кредита,
Z — выручка от реализации произведенной продукции,
P — прибыль предприятия.
Выразим в математической форме основные условия и ограничения
рассматриваемой задачи.
Ограничения по использованию сырья:
3x
1
+ 5x
2
≤ 1500.
Ограничения по использованию оборудования:
6x
1
+ 4x
2
≤ 1560.
Потребность в трудовых ресурсах S определяется необходимыми
затратами труда для выпуска продукции в объемах х
1
и х
2
:
S = 8x
1
+ 2x
2
.
Размер необходимого кредита определяется исходя из потребности в
трудовых ресурсах S и почасовой ставки оплаты труда t, т.е.
V = tS = t
(8x
1
+ 2x
2
).
Выручка от реализации произведенной продукции:
Z = 1259x
1
+ 766x
2
.
Сумма расходов по обслуживанию кредита определяется размером
возвращаемого кредита и процентов по нему, т.е. равна
VVVVV 1.11.0
%100
3
12
%40
=+=
⎟
⎠
⎞
⎜
⎝
⎛
×+ .
Прибыль предприятия определяется как разность между выручкой и
расходами по обслуживанию кредита, т.е.
P = Z – 1.1V.
Подставляя в эту формулу выражения для Z и V, получим
P = (1259x
1
+ 766x
2
) – 1.1t(8x
1
+ 2x
2
) = (1259 – 8.8t)x
1
+ (766 – 2.2t)x
2
.
Следовательно, математическая модель оптимизации выпуска
продукции принимает следующий вид: найти неизвестные значения
объемов выпуска x
1
, x
2
, удовлетворяющие ограничениям
3x
1
+ 5x
2
≤ 1500, (1)
6x
1
+ 4x
2
≤ 1560, (2)
x
1
≥ 0, x
2
≥ 0 (3)
и доставляющие максимальное значение целевой функции
P = (1259 – 8.8
t)x
1
+ (766 – 2.2t)x
2
→ max. (4)
При этом необходимый размер кредита V определяется по формуле:
V = tS = 8t
xt
12
2
**
x
+
,
где ( , ) — оптимальное решение задачи (1) – (4). Отметим, что модель
(1) – (4) представляет собой задачу так называемого параметрического
линейного программирования, так как в ее условиях содержится параметр
t, от значения которого будет зависеть оптимальное решение.
x
1
*
x
2
*
2.2. Определение оптимальной программы выпуска продукции
При ставке оплаты труда t = 10 коэффициенты целевой функции
равны: с
1
= 1259 – 8.8×10 = 1171 и с
2
= 766 – 2.2×10 = 744.
Следовательно, математическая модель (1) – (4) примет вид:
P = 1171x
1
+ 744x
2
→ max.
3x
1
+ 5x
2
≤ 1500,
6x
1
+ 4x
2
≤ 1560,
x
1
≥ 0, x
2
≥ 0,
Графическое решение задачи изображено на рис. 2.1. Множество
допустимых решений представляет собой четырехугольник ОАВС.
Вектор-градиент целевой функции P обозначен через grad P(10);
штриховыми линиями проведены линии уровня целевой функции,
соответствующие ее нулевому и оптимальному значению. Из рисунка
видно, что точкой максимума является точка С с координатами ,
.
260
*
1
=x
0
*
2
=x
Максимальный размер прибыли:
P
P
*
= 1171×260 + 744×0 = 304460 (руб.),
потребность в трудовых ресурсах:
208028
*
2
*
1
*
=+= xxS
(чел.-час).
размер необходимого кредита:
V
*
= tS
*
= 10×2080 = 20800 (руб.),
сумма уплаченных процентов:
0.1V
*
= 0.1×20800 = 2080 (руб.),
500
300
390
0
6х
1
+ 4х
2
= 1560
B
А
С
P = 0
P = 304460
grad P(10)
точка максимума
,
260
*
1
=x
0
*
2
=x
3х
1
+ 5х
2
= 1500
260
x
2
x
1
Рис. 2.1. Иллюстрация графического решения при t = 10
2.3. Нахождение функции спроса на трудовые ресурсы
Потребность в трудовых ресурсах S
*
для обеспечения оптимального
плана выпуска определяется соотношением:
),(
*
2
*
1
*
xxX =
S
*
= S
*
(Х
*
) = 8 + 2 .
*
1
x
*
2
x
Но, как отмечалось выше, оптимальный план выпуска Х
*
зависит от
почасовой ставки оплаты труда t. Следовательно, величина S
*
также
зависит от t, т.е. потребность в трудовых ресурсах S
*
есть некоторая
функция от параметра t.
Найдем эту функцию при 10 ≤ t ≤ 40. Для этого определим c
помощью графического метода в задаче (1) – (4) оптимальные планы
выпуска =( , ) при различных значениях t. Отметим, что при
изменении параметра t множество допустимых решений остается
прежним; меняются только коэффициенты целевой функции. Последнее
означает, что изменяется направление ее градиента, а, следовательно, и
угол наклона линий уровня.
*
X
*
1
x
*
2
x
Сначала найдем решение задачи при t = 40. Она имеет следующий
вид:
3x
1
+ 5x
2
≤ 1500,
6x
1
+ 4x
2
≤ 1560,
x
1
≥ 0, x
2
≥ 0,
P = 907x
1
+ 678x
2
→ max.
500
300
390
Р = 253420
x
2
x
1
0
grad P(40)
6х
1
+ 4х
2
= 1560
B
240
100
А
С
260
3х
1
+ 5х
2
= 1500
Р
= 0
точка максимума
100
*
1
=x
,
240
*
2
=x
Рис. 2.2. Иллюстрация графического решения при t = 40
Из рисунка видно, что оптимальное решение задачи изменилось. Им
теперь является точка В с координатами , , которые
находятся из системы двух линейных уравнений:
100
*
1
=x 240
*
2
=x
3x
1
+ 5x
2
= 1500,
6x
1
+ 4x
2
= 1560.
Максимальный размер прибыли:
P
P
*
= 907×100 + 678×240 = 253420 (руб.),
потребность в трудовых ресурсах:
Sxx
** *
=
+
=
8 2 1280
12
(чел.-час).
размер необходимого кредита:
V
*
= tS
*
= 40×1280 = 51200 (руб.),
сумма уплаченных процентов:
0.1 V
*
= 0.1×51200 = 5120 (руб.)
На рис. 2.3 показаны положения вектора-градиента и линий уровня
целевой функции, соответствующие крайним значениям параметра t.
Таким образом, при увеличении t от 10 до 40 вектор grad P(t), а, значит, и
линии уровня целевой функции поворачиваются против часовой стрелки.
Сначала, когда отклонение параметра от своего первоначального значения
t = 10 мало, оптимальное решение задачи (точка С) будет оставаться
прежним. Но по мере увеличения параметра настанет момент t = t
*
, когда
вектор grad P(t
*
) окажется перпендикулярен граничной прямой (2). Тогда
линии уровня целевой функции будут параллельны этой прямой. Это
означает, что линия уровня, соответствующая максимальному значению
целевой функции, совпадет с прямой (2); и, следовательно, все точки
отрезка ВС будут оптимальными решениями задачи.
Рис. 2.3. Графическая иллюстрация изменения решения
при увеличении t от 10 до 40
500
300
390
x
2
x
1
0
grad P(40)
B
А
С
260
grad P(10)
grad P(t
*
)
линии уровня
целевой функции
6х
1
+ 4х
2
= 1560 (2)
3х
1
+ 5х
2
= 1500 (1)
Поскольку при дальнейшем увеличении параметра вектор grad P(t)
будет продолжать поворачиваться против часовой стрелки, то ясно, что
при всех значениях t, таких, что t
*
< t ≤ 40 решением задачи будет точка В.
Для нахождения значения параметра t = t
*
используем тот известный
факт, что если две прямые на плоскости параллельны, то их коэффициенты
при одинаковых переменных пропорциональны.
Так как граничная прямая (2) задается уравнением
6х
1
+ 4х
2
= 1560,
а линия уровня целевой функции — уравнением
(1259 – 8.8t)x
1
+ (766 – 2.2t)x
2
= h,