Маслов А.В., Григорьева А.А. Математическое моделирование в экономике и управлении: Учебное пособие. Гриф УМО
Подождите немного. Документ загружается.
.
.
a'
k1
.
.
.
a'
r1
.
.
0
.
.
.
0
.
.
0
.
.
.
0
.
.
0
.
.
.
1
.
.
a'
ks
.
.
.
a'
rs
.
.
a'
kn
.
.
.
a'
rn
.
.
d
ik
.
.
.
d
ir
- c
1
... - c
i1
... - c
i2
... - c
ir
... - c
s
... - c
n
0
Таблица 4.6
Приведённая к базису
r
iii
AAA ,...,,
21
симплекс-таблица
x
1
..
.
x
i1
... x
i2
... x
ir
... x
s
... x
n
a'
11
a'
21
.
.
.
a'
r1
1
0
.
.
.
0
0
1
.
.
.
0
0
0
.
.
.
1
a'
1s
a'
2s
.
.
.
a'
rs
a'
1n
a'
2n
.
.
.
a'
rn
d
i1
d
i2
.
.
.
d
ir
1
..
.
i1
...
i2
...
ir
...
s
...
n
0
2. Для оптимального опорного решения задачи линейного
программирования в канонической форме всегда существует базис, все
оценки которого неположительны.
3. Предположим, что симплекс-таблица для задачи линейного
программирования в канонической форме приведена к базису
некоторого опорного решения. Если среди оценок этого базиса имеется
положительная оценка
s
, а все остальные элементы s-го столбца
таблицы неположительны, то целевая функция не ограничена снизу на
допустимом множестве. (Условие неограниченности нулевой функции –
особый случай).
Пример 4.5. Рассмотрим опорное решение
=(1;0;0;0) задачи:
min6910
4321
xxxxf
,12
,13
4321
321
xxxx
xxx
,0
j
x
j = 1,2,3,4.
Приведём симплекс-таблицу для этой задачи к базису
21
, AA
опорного решения
.
Таблица 4.7
Ход преобразований по симплекс-методу для примера 4.5
x
1
x
2
x
3
x
4
x
1
x
2
x
3
x
4
x
1
x
2
x
3
x
4
61
1
2
3
5
4
6
1 1 3 0 1
1 1 3 0 1
1 0 1 1 1
1 -1 -1 2 1 0 -2 -4 2 0 0 1 2 -1 0
10 -1 9 -6 0 10 -1 9 -6 0 10 -1 9 -6 0
x
1
x
2
x
3
x
4
1 0 1 1 1
0 1 2 -1 0
0 0 1 -17 -10
Среди оценок базиса
21
, AA
есть положительная оценка
1
3
.
Значит, утверждать на этом этапе, что
– опорное решение, мы не
можем.
С другой стороны, возьмем базис
31
, AA
того же опорного решения
. Приведя симплекс-таблицу к этому базису (таблица 4.8), получим,
что все оценки базиса
31
, AA
неположительны. Следовательно,
оптимальное решение данной задачи.
Таблица 4.8
Приведённая к базису
31
, AA
симплекс-таблица
x
1
x
2
x
3
x
4
1
-1
/
2
0
3
/
2
1
0
1
/
2
1
-1
/
2
0
0
-1
/
2
0
-33
/
2
-10
Решение задач линейного программирования симплекс-методом
Если известно некоторое опорное решение задачи линейного
программирования в канонической форме, то её можно решать
симплекс-методом. Симплекс-метод – это направленный перебор
опорных решений, при котором значение целевой функции на каждом
последующем опорном решении меньше, чем на предыдущем (для задачи
минимизации).
Для решения симплекс-методом задачи линейного
программирования в канонической форме необходимо выполнить ряд
последовательных шагов. На каждом шаге либо возникает базис нового
опорного решения, причём на новом опорном плане значение целевой
функции обязательно меньше, чем на предыдущем (для задачи
минимизации), либо меняется базис исходного опорного решения.
Если на очередном шаге удаётся установить оптимальность
опорного решения или неограниченность целевой функции на
допустимом множестве, то следующий шаг не выполняется.
Предположим, что перед выполнением очередного шага симплекс-
таблица для задачи (4.7) приведена к базису
62
1
2
3
5
4
6
rkkk
iiiii
AAAAA ,...,,,,...
111
(4.8)
некоторого опорного решения
. Можно считать, что среди оценок
этого базиса есть положительные оценки (в противном случае
-
оптимальное решение). Выберем любую из положительных оценок,
например,
.0
s
В симплекс-таблице, приведённой к базису (4.8),
рассмотрим элементы
////
1
,...,,...,,...,
ssss
rkl
aaaa
(4.9)
s-го столбца и соответствующие свободные члены
rkl
dddd ,...,,...,,...,
1
(4.10)
Можно считать, что среди элементов (4.9) есть положительные элементы (в противном случае
целевая функция не ограничена снизу на допустимом множестве). В этом случае необходимо
рассматривать все отношения вида
/
s
l
l
a
d
, где
0
/
s
l
a
,
(4.11)
т. е. отношение свободного члена к соответствующему элементу s-го
столбца (4.9) при условии, что последний положителен. Среди
отношений (4.11) выбираем наименьшее.
Если
0min
/
//
s
ss
l
l
l
k
k
a
a
d
a
d
, то симплекс-таблицу приводим к новому базису
,,...,,,,...,
111 rkk
iisii
AAAAA
(4.12)
т.е. из базиса (4.8) исключаем вектор
,
k
i
A
а вместо него вводим вектор
.
s
A
Если
0
(так заведомо случится, если исходное опорное решение
не вырождено), то базис (4.12) является базисом нового опорного
решения
такого, что
)()(
ff
. Если же
0
, то (4.12) является
новым базисом исходного опорного решения
.
Конечность симплекс-метода
Если задача линейного программирования в канонической форме
не имеет вырожденных опорных решений, то через конечное число
шагов симплекс-метода она будет решена.
При решении задачи, у которой есть вырожденные опорные
решения, может случиться, что, перебирая базисы одного и того же
опорного решения, через несколько шагов мы вернёмся к исходному
базису, т. е. произойдет зацикливание.
Для предотвращения зацикливания необходимо уточнить правило
перехода к новому базису. Это сделать можно, например, следующим
образом. Среди оценок базиса (4.8) выбираем положительную оценку с
наименьшим номером. Если
s
- такая оценка, а наименьшее из
63
1
2
3
5
4
6
отношений (4.11) определено неоднозначно, то берём наименьшее
отношение
/
s
k
k
a
d
с наименьшим номером k.
Пример 4.6.
Для изготовления продукции используют 3 вида сырья. При этом
можно применять любой из четырех способов производства. Запасы
сырья, расход и количество производимой продукции за 1 час работы по
каждому способу приведены в таблице 4.9.
Таблица 4.9
Условия задачи линейного программирования примера 4.6
Способ произ-
водства
Сырьё
1 2 3 4 Запас
сырья
1 1 2 1 0 18
2 1 1 2 1 30
3 1 3 3 2 40
Выпуск продукции 12 7 18 10
Требуется найти план производства, при котором будет выпущено
наибольшее количество продукции. Обозначим через
j
x
время
использования j-го способа производства (j=1,2,3,4), получим задачу
линейного программирования:
max1018712
4321
xxxxf
.40233
,302
,182
4321
4321
321
xxxx
xxxx
xxx
,0j
.4,...,1j
Эту задачу сведём к канонической задаче минимизации:
min1018712
4321
/
xxxxf
.7,...,1,0
40,= 233
30,= 2
18,= 2
74321
64321
5321
jx
xxxxx
xxxxx
xxxx
j
Cоставим симплекс-таблицу. Симплекс-таблица оказывается
приведённой к базису
765
,, AAA
опорного решения
40;30;18;0;0;0;0
1
(табл. 4.10).
Выбираем положительную
12
1
и составляем следующие
отношения:
.
1
40
,
1
30
,
1
18
Так как наименьшее среди них
,
1
18
то
необходимо перейти к базису
.,,
761
AAA
Для этого достаточно
выполнить жорданово преобразование всей таблицы с ведущим
элементом
11
a
.
64
1
2
3
5
4
6
Таблица 4.10
Приведённая к базису
765
,, AAA
симплекс-таблица
x
1
x
2
x
3
x
4
x
5
x
6
x
7
1 2 1 0 1 0 0 18
1 1 2 1 0 1 0 30
1 3 3 2 0 0 1 40
12 7 18 10 0 0 0 0
Таблица 4.11
Приведённая к базису
761
,, AAA
симплекс-таблица
x
1
x
2
x
3
x
4
x
5
x
6
x
7
1 2 1 0 1 0 0 18
0 -1 1 1 -1 1 0 12
0 1 2 2 -1 0 1 22
0 -17 6 10 -12 0 0 -216
Базис
761
,, AAA
является базисом опорного решения
2
=(18;0;0;0;0;12;22). При этом
,216)(
2
/
f
в то время, как
0)(
1
/
f
.
Выбираем оценку
010
4
и составляем отношения
.
2
22
,
1
12
Наименьшим среди них является
2
22
. Следовательно, переходим к
базису
.,,
641
AAA
Получим таблицу 4.12.
Таблица 4.12
Приведённая к базису
641
,, AAA
симплекс-таблица
x
1
x
2
x
3
x
4
x
5
x
6
x
7
1 2 1 0 1 0 0 18
0 -3/2 0 0 -1/2 1 -1/2 1
0 1/2 1 1 -1/2 0 1/2 11
0 -22 -4 0 -7 0 -5 -326
Все оценки базиса
641
,, AAA
неположительны. Следовательно,
)0;1;0;11;0;0;18(
3
оптимальное решение канонической задачи
минимизации. Поэтому
)11;0;0;18(
оптимальное решение
исходной задачи. При этом f(β)=326. Таким образом, для того чтобы
выпустить наибольшее количество продукции при имеющихся запасах
сырья, необходимо в течение 18 ч использовать первый способ
производства и в течение 11 ч – четвёртый. В результате будет
произведено 326 единиц продукции.
Метод искусственного базиса
65
1
2
3
5
4
6
для отыскания начального опорного решения
Для того чтобы решить задачу линейного программирования в
канонической форме, необходимо предварительно найти некоторое
начальное опорное решение этой задачи. Сделать это можно методом
искусственного базиса.
Рассмотрим задачу линейного программирования в канонической
форме:
n
j
jj
xcf
1
min,
n
j
jjij
mibxa
1
,...,2,1,
,
(4.13)
njx
j
,...,2,1,0
.
Без ограничения общности можно считать, что
.,...,1 ,0 mib
i
Для
отыскания опорного решения задачи (4.13) строим вспомогательную
задачу:
m
i
i
y
1
min
mibyxa
iij
n
j
ij
,...,2,1 ,
1
,
(4.14)
miynjx
ij
,...,2,1,0;,...,2,1,0
.
Свойства вспомогательной задачи.
1. Вспомогательная задача (4.14) всегда имеет опорное решение.
2. Вектор
);...;;;0;...;0;0(
21 m
bbb
является опорным решением
задачи (4.14).
Таким образом, принимая вектор
за начальное опорное решение,
вспомогательную задачу можно решить симплекс-методом. Пусть
);...;;;;...;;(
**
2
*
1
**
2
*
1
*
mn
yyyxxx
оптимальное опорное решение задачи (4.14).
Если
,0...
**
2
*
1
m
yyy
то
);...;;(
**
2
*
1 n
xxx
опорное решение
исходной задачи (4.13). Если же среди чисел
**
2
*
1
,...,,
m
yyy
есть
положительные, то исходная задача (4.13) имеет пустое допустимое
множество.
Таким образом, всегда можно либо найти опорное решение
исходной задачи либо установить её неразрешимость.
Двойственность в линейном программировании
Понятие двойственности. С каждой задачей линейного
программирования тесно связана другая линейная задача, называемая
двойственной. Первоначальная задача называется исходной.
66
1
2
3
5
4
6
Связь исходной и двойственной задач состоит в том, что
коэффициенты
j
с
целевой функции исходной задачи являются
свободными членами системы ограничений двойственной задачи,
свободные члены
i
b
системы ограничений исходной задачи служат
коэффициентами функции цели двойственной задачи, а матрица
коэффициентов системы ограничений двойственной задачи является
транспонированной матрицей коэффициентов системы ограничений
исходной задачи. Решение двойственной задачи может быть получено из
решения исходной и наоборот.
В качестве примера рассмотрим задачу использования ресурсов.
Пусть предприятие имеет m видов ресурсов в количестве
i
b
(i=1,2,…,m)
единиц, из которых производится n видов изделий. Для производства
одной единицы j-й продукции расходуется
ij
a
единиц i-го ресурса, а её
стоимость составляет
j
с
единиц. Составить план выпуска продукции,
обеспечивающий её максимальный выпуск в стоимостном выражении.
Обозначим через
),...,2,1( njx
j
количество единиц j-й продукции.
Тогда исходную задачу сформулируем так:
найти вектор
),...,,(
21 n
xxxX
, который удовлетворяет ограничениям
),...,2,1(0
),...,2,1(
1
njx
mibxa
j
n
j
ijij
и доставляет максимальное значение линейной функции
n
j
jj
xcZ
1
.
Оценим ресурсы, необходимые для изготовления продукции. За
единицу стоимости ресурсов примем единицу стоимости выпускаемой
продукции. Обозначим через
),...,2,1( miy
i
стоимость единицы i-го
ресурса. Тогда стоимость всех затраченных ресурсов, идущих на
изготовление единицы j-й продукции, равна
m
i
iij
ya
1
. Стоимость
затраченных ресурсов не может быть меньше стоимости
окончательного продукта (не может появиться из "ничего"), поэтому
должно выполняться неравенство
m
i
jiij
njcya
1
.,...,2,1,
Стоимость
всех имеющихся ресурсов выразится величиной
m
i
ii
yb
1
.
Итак,
двойственную задачу можно сформулировать следующим образом:
найти вектор двойственных оценок
),...,,(
21 m
yyyY
, который
удовлетворяет ограничениям
),...,2,1(0
),...,2,1(
1
miy
njcya
i
m
i
jiij
67
1
2
3
5
4
6
и доставляет минимальное значение линейной функции
.
1
m
i
ii
ybf
Рассмотренные исходная и двойственная задачи могут быть
экономически интерпретированы так.
Исходная задача. Сколько и какой продукции
),...,2,1( njx
j
необходимо произвести, чтобы при заданных стоимостях
),...,2,1( njc
j
единицы продукции и размерах имеющихся ресурсов
),...,2,1( mib
i
максимизировать выпуск продукции в стоимостном
выражении?
Двойственная задача. Какова должна быть цена единицы каждого
из ресурсов, чтобы при заданных количествах ресурсов
i
b
и величинах
стоимости единицы продукции
j
c
минимизировать общую стоимость затрат?
Переменные
i
y
называются двойственными оценками или
учётными, неявными ценами. В работах Немчинова В.С., Новожилова
В.В., Аганбегяна А.Г. их называют объективно обусловленными
оптимальными оценками (о.о.о.о.). Им посвящено много работ,
поскольку их экономический смысл в этих математических моделях
очень важен для экономического анализа производственной ситуации.
Например, в нашей задаче использования ресурсов эти оценки
показывают степень дефицитности ресурсов. Более того, величина
данной двойственной оценки показывает, на сколько возрастёт
максимальное значение целевой функции прямой задачи при
увеличении количества сырья соответствующего вида на 1 кг.
В результате решения задачи линейного программирования
найдётся некий оптимальный план. При подстановке этого решения в
задачу обнаружится, что некоторые ресурсы используются полностью, а
некоторые останутся неиспользованными. Двойственные оценки
соответствующих ресурсов будут положительными и нулевыми.
Последнее будет наблюдаться там, где ресурсы не используются
полностью. Причём самое узкое место – наиболее дефицитный ресурс –
будет иметь двойственную оценку с наибольшим положительным
значением. Знание этого "узкого" места уже может влиять на принятие
какого-либо управленческого решения. Эти двойственные оценки имеют
ещё несколько экономических интерпретаций, например, как средство
балансировки между суммарными затратами и результатами.
Многие задачи линейного программирования первоначально
ставятся в виде исходных или двойственных задач, поэтому имеет
смысл говорить о паре двойственных задач линейного
программирования.
В зависимости от вида ограничений исходные задачи линейного
программирования двойственные задачи могут быть несимметричными
68
1
2
3
5
4
6
и симметричными. В несимметричных двойственных задачах система
ограничений исходной задачи задаётся в виде неравенств, причём в
последней переменные могут быть и отрицательными. Для простоты
постановку задачи условимся записывать в матричной форме.
Исходная задача. Найти матрицу-столбец
),...,,(
21 n
xxxx
, который
удовлетворяет ограничениям
0, xBAx
и минимизирует линейную
функцию
.Cxz
Двойственная задача. Найти матрицу-строку
),,...,,(
21 m
yyyY
которая удовлетворяет ограничениям
CYA
и максимизирует
линейную функцию
.YBf
В обеих задачах
),...,,(
21 n
cссС
матрица-строка,
),...,(
1 m
bbB
матрица-столбец,
)(
ij
aA
матрица коэффициентов системы
ограничений. Связь между оптимальными планами пары двойственных
задач устанавливают следующие теоремы двойственности:
1)(первая теорема двойственности). Если из пары двойственных
задач одна обладает оптимальным планом, то и другая имеет решение,
причём для экстремальных значений линейных функций выполняется
соотношение
.maxmin fz
Если линейная функция одной из задач не
ограничена, то другая не имеет решения.
2)(вторая теорема двойственности). План
),...,,(
**
2
*
1
*
n
xxxX
исходной задачи и план
),...,,(
**
2
*
1
*
m
yyyY
двойственной задачи
являются оптимальными планами этих задач тогда и только тогда, когда
для любого j=1,2,…,n выполняется равенство
0
*
1
*
j
m
i
jiij
xcya
. Эти
теоремы позволяют при решении одной из двойственных задач
находить оптимальный план другой.
Разновидностью двойственных задач линейного программирования
являются двойственные симметрические задачи, в которых система
ограничений как исходной, так и двойственной задач задаётся
неравенствами, причём на двойственные переменные налагается
условие неотрицательности.
Исходная задача. Найти матрицу-столбец
),,...,,(
21 n
xxxx
которая
удовлетворяет системе ограничений
0 , xBAX
и минимизирует
линейную функцию
.CXZ
Двойственная задача. Найти матрицу-строку
),,...,,(
21 m
yyyY
которая удовлетворяет системе ограничений
0, YCYA
и
максимизирует линейную функцию f=YB.
Систему неравенств с помощью дополнительных переменных
можно преобразовать в систему уравнений, поэтому всякую пару
69
1
2
3
5
4
6
симметричных двойственных задач можно преобразовать в пару
несимметричных.
Используя симметричность, можно выбрать задачу, более удобную
для решения симплекс-методом. Объём задачи, решаемой с помощью
ЭВМ, ограничен числом включаемых строк, поэтому задача, довольно
громоздкая в исходной постановке, может быть упрощена в
двойственной формулировке. При вычислениях без помощи машин
использование двойственности упрощает вычисления.
Виды математических моделей двойственных задач
На основании рассмотренных несимметричных и симметричных
двойственных задач можно заключить, что математические модели
пары двойственных задач могут иметь один из следующих видов:
Несимметричные задачи.
(4.15) Исходная Двойственная (4.16) Исходная Двойственная
задача задача задача задача
Симметричные
задачи.
(4.17) Исходная Двойственная (4.18) Исходная Двойственная
задача задача задача задача
Таким образом, прежде чем записать двойственную задачу для
данной исходной, систему ограничений исходной задачи необходимо
привести к соответствующему виду.
На примерах рассмотрим алгоритм составления двойственной задачи.
Пример 4.7. Исходная задача. Найти минимальное значение
линейной функции
321
52 xxxZ
при ограничениях
.632
,55
,4
321
321
321
xxx
xxx
xxx
)3,2,1(0 jx
j
.
Рассмотренная задача относится к симметричным двойственным
задачам на отыскание минимального значения линейной функции. Для
того чтобы можно было записать двойственную задачу, её модель
должна иметь вид (4.17). Переход осуществляется умножением первого
неравенства на –1.
70
0
min
X
BAX
CXZ
CYA
YBf
max
0
max
X
BAX
CXZ
CYA
YBf
min
0
max
Y
CYA
YBf
0
max
X
BAX
CXZ
0
min
X
BAX
CXZ
0
min
Y
CYA
YBf
1
2
3
5
4
6