Патудин В.М., Блем А.Г. Математическая экономика
Подождите немного. Документ загружается.
31
Шаг 1. Получение начального решения.
Выбираются
m
переменных, называемых базисными и обладающих
следующим свойством: они входят с коэффициентом 1 только в одно уравне-
ние и с коэффициентом 0 в остальные уравнения системы (2.5.2).
Остальные
m
n
−
переменных называют свободными.
Все свободные переменные полагаются равными 0, а базисные пере-
менные – равные правым частям соответствующих ограничений системы
(2.5.2).
Пусть
m
базисных переменных – это переменные
m
xxx
,...,,
21
(в против-
ном случае переменные всегда можно перенумеровать). Тогда начальное ре-
шение
0
X
имеет следующий вид:
}0,...,0,,...,,{
122110
======
+ nmmm
xxbxbxbxX
.
Если все
mib
i
,1,0 =≥
, то начальное решение является допустимым. Пе-
реходят к шагу 2. В противном случае используют алгоритм нахождения на-
чального решения.
Шаг 2. Выражение функции
f
только через свободные переменные.
∑
+=
=
n
mj
jj
xcf
1
(Значения коэффициентов
nmjc
j
,1, +=
, естественно, отличны от зна-
чений коэффициентов в формуле (2.5.1), но для простоты обозначены той же
буквой.)
Переход к шагу 3.
Шаг 3. Проверка решения на оптимальность.
Составляется симплекс-таблица (табл. 2.5.1).
Таблица 2.5.1
Коэффициенты при переменных Б
азисные
перемен-
ные
Сво-
бодные
чле-
ны
1
x
2
x
…
q
x
…
m
x
f
1
b
2
b
…
q
b
…
m
b
0
В левой колонке симплекс-таблицы находятся базисные переменные, в
колонке свободных членов – правые части соответствующих ограничений. В
i
-й строке,
j
-м столбце стоит коэффициент при
j
-й переменной в
i
-м огра-
ничении (2.5.2),
njmi
,1,,1 ==
. В последней строке (
f
-строке) стоит коэффици-
ент с противоположным знаком при
j
-й переменной в целевой функции
f
. В
32
последнем столбце последней строки стоит значение свободного члена, вхо-
дящего в целевую функцию.
Для проверки решения на оптимальность просматривается последняя
f
-строка. Если коэффициенты, стоящие при свободных переменных неотри-
цательны, то полученное решение оптимально. Полученное решение единст-
венно, если все эти коэффициенты положительны. Если среди неотрицатель-
ных коэффициентов встречается хотя бы один нулевой, то задача имеет бес-
конечное множество решений. Если в последней строке есть хотя бы один от-
рицательный коэффициент, а в соответствующем этому коэффициенту столб-
це нет ни одного положительного элемента, то целевая функция
f
не ограни-
чена на области допустимых решений. Если хотя бы один из коэффициентов,
стоящих при свободных переменных, отрицательный и в соответствующем
ему столбце есть хотя бы положительный элемент, то полученное решение
может быть улучшено.
Переход к шагу 4.
Шаг 4. Получение нового решения.
Шаг 4.1. Выбор переменной, вводимой в список базисных перемен-
ных.
Просматривается последняя строка симплекс-таблицы. Среди элемен-
тов этой строки выбирается максимальный по абсолютной величине отрица-
тельный элемент. Столбец, в котором стоит этот элемент, называется разре-
шающим. Пусть, например, это
p
-й столбец. Переменная
p
x
, стоящая в этом
столбце, вводится в список базисных переменных.
Шаг 4.2. Выбор переменной, выводимой из списка базисных перемен-
ных.
Находят отношение элементов столбца свободных членов к элементам
разрешающего столбца. При делении на отрицательный элемент и 0 результат
полагают равным
∞
+
. Среди этих отношений находят минимальное. Строка,
соответствующая минимальному отношению, называется разрешающей.
Пусть, например, это
q
-я строка. Базисная переменная
q
x
, стоящая в этой
строке, выводится из списка базисных переменных. Элемент симплекс-
таблицы
qp
a
, стоящий на пересечении разрешающей строки и разрешающего
столбца, называется разрешающим элементом.
Шаг 4.3. Выполнение симплекс-преобразования и переход к новой
симплекс-таблице.
Элемент
ij
a
новой симплекс-таблицы вычисляется с помощью сле-
дующего симплекс-преобразования:
=
−=
+=+=
≠−
=
=
+
+
iin
jjm
qpqjipij
qpqj
ba
ca
njmi
qiaaaa
qiaa
aij
1
1
;
;1,1,1,1
;,/
;,/
(2.5.4)(2.5.5)
33
Таким образом, при переходе к новой симплекс-таблице все элементы
разрешающей строки делятся на разрешающий элемент (2.5.4), а все осталь-
ные элементы симплекс-таблицы, включая коэффициенты целевой функции и
свободные члены, пересчитываются по формуле (2.5.5).
Новое решение имеет следующий вид: все свободные переменные в
нем полагаются равными 0, а все базисные переменные – свободным членам,
стоящим в одной строке с ними.
После построения новой симплекс-таблицы следует перейти к шагу 3.
Поясним на примерах некоторые шаги алгоритма.
Пример 2.5.1
max32
21
→−= xxf
≥≥≥≥
=+−−
=++−
0,0,0,0
;735
;62
4321
421
321
xxxx
xxx
xxx
Базисные переменные:
43
,
xx
.
Свободные переменные:
21
, xx
.
}7,6,0,0{
43210
=====
xxxxX
.
Симплекс-таблица имеет следующий вид (табл. 2.5.2):
Таблица 2.5.2
Коэффициенты при перемен-
ных
Ба-
зисные пере-
ме
н
ные
1
x
x
3
x
4
x
Свободные
члены
3
x
4
x
f
-
1
-
5
2
-
3
3
1
0
0
0
1
0
6
7
0
Значение
f
можно увеличить, увеличивая значение переменной
1
x
, так
как ей соответствует положительный коэффициент в формуле для
f
и, соот-
ветственно, отрицательный коэффициент в последней строке симплекс-
таблицы. Из системы ограничений видно, что при любом увеличении значения
1
x
можно подобрать значения
3
x
,
4
x
, при которых будет выполняться система
ограничений. Следовательно, функция
f
будет бесконечно возрастать и не
будет ограниченной на области допустимых решений.
Пример 2.5.2
max325
321
→+−=
xxxf
≤+−
≤+
≤−+
2082
;73
;1533
21
31
321
xx
xx
xxx
Запишем задачу в каноническом виде, вводя дополнительные пере-
менные
4
x
,
5
x
,
6
x
.
34
=≥
=++−
=++
=+−+
.6,5,4,3,2,1,0
;2082
;73
;1533
621
531
4321
jx
xxx
xxx
xxxx
j
Начальное решение:
}20,7,15,0,0,0{
6543210
======= xxxxxxX
Функция
321
325 xxxf +−=
уже выражена через свободные переменные,
поэтому можно перейти к составлению симплекс-таблицы (табл. 2.5.3).
Таблица 2.5.3
Коэффициенты при переменных Базис-
ные перемен-
ные
Сво-
бодные члены
4
x
5
x
6
x
f
2
1
15
7
20
0
Ввод переменной в список базисных переменных означает, что ей при-
писывается отличное от 0 положительное значение, т.е. ее значение увеличи-
вается. Из формулы для целевой функции
321
325 xxxf +−=
видно, что увели-
чение значения
2
x
приводит только к уменьшению
f
, т.е. переменную
2
x
бес-
смысленно вводить в список базисных переменных. Увеличение переменных
1
x
и
3
x
приводит к увеличению значения
f
при этом на большую величину
значение изменяется с увеличением
1
x
, следовательно, переменная
1
x
должна
стать базисной переменной. Максимальное значение коэффициента при
1
x
в
формуле для
f
соответствует максимальному по абсолютной величине отри-
цательному элементу в последней строке симплекс-таблицы, следовательно,
понятен выбор новой базисной переменной.
Для определения переменной, выводимой из списка базисных пере-
менных, надо в соответствии с алгоритмом симплекс-метода найти отношения
элементов столбца свободных членов к элементам разрешающего столбца и
среди них выбрать минимальное.
5};7;5{}2/20;1/7;3/15min{
=
+∞
=
−
,
следовательно, из списка базисных переменных надо вывести
4
x
,
стоящую в первой строке симплекс-таблицы, и разрешающий элемент
3
11
=a
.
Поясним этот выбор. Если перейти от симплекс-таблицы к ограниче-
ниям, то это значит, что
1
x
надо выразить из первого уравнения через осталь-
ные переменные, включая
4
x
, и, подставив его во второе и третье уравнения,
исключить оттуда
4
x
. Проделаем это ниже, а сейчас поясним, почему выбор
пал именно на
4
x
.
35
Попробуем вывести из списка базисных другую переменную, напри-
мер
5
x
. Для этого выразим
1
x
через
5
x
и остальные переменные из второго
уравнения и подставим в остальные.
531
37 xxx −−=
Подставив
1
x
в первое уравнение, получим
.63103
;153)37(3
5432
43253
−=−+−
=
+
−
+
−
−
xxxx
xxxxx
Подставив
2
x
во второе уравнение, получим
34268
;208)37(2
6532
6253
=+++
=
+
+
−
−
−
xxxx
xxxx
Окончательно получим
34268
;73
;63103
6532
531
5432
=+++
=++
−
=
−
+
−
xxxx
xxx
xxxx
1
x
,
4
x
,
6
x
– базисные переменные, поэтому решение имеет вид
}34,6,0,0,7{
643211
=−===== xxxxxX
В этом решении
4
x
=-6, что противоречит условию задачи
0
4
≥x
, сле-
довательно,
1
X
не является допустимым решением, и, таким образом, пере-
менную
5
x
нельзя вывести из списка базисных переменных.
Вывод из списка базисных переменных переменной
6
x
означает, что
1
x
надо выразить через
6
x
из последнего уравнения исходной системы ограниче-
ний. Получившаяся при этом правая часть уравнения будет являться значени-
ем базисной переменной
1
x
в новом решении.
Выразив
1
x
через
6
x
, получим
.102/4
;2082
621
621
−=−−
=
+
+
−
xxx
xxx
Следовательно, в новом решении
1
x
=-10, что противоречит условию
неотрицательности
1
x
, поэтому на шаге 4.2 пренебрегают делением на отрица-
тельное число, полагая равным
∞
+
результат от деления.
2.6.Пример расчета экономико-математической модели
Предприятие рекламирует свою продукцию с использованием четырех
источников массовой информации: телевидения, радио, газет и расклейки объ-
явлений. Анализ рекламной деятельности в прошлом показал, что эти средства
приводят к увеличению прибыли соответственно на 10, 5, 7 и 4 усл. ед., в рас-
чете на 1 усл. ед., затраченную на рекламу. На рекламу выделено 50000 усл.
ед. Администрация предприятия не намерена тратить на телевидение более
40%, а на радио и газеты – более 50% от общей суммы выделенных средств.
Как следует предприятию организовать рекламу, чтобы получить максималь-
ную прибыль?
Решение.
36
Составим математическую модель задачи.
Цель – максимизация прибыли.
Параметрами являются все числа, приведенные в условии задачи.
Управляющие переменные:
1
x
– количество средств, вложенных в рекламу на телевидение;
2
x
– количество средств, вложенных в рекламу на радио;
3
x
– количество средств, вложенных в рекламу в газетах;
4
x
– количество средств, вложенных в рекламу, организованную с по-
мощью расклейки объявлений.
Область допустимых решений имеет, вид
≥≥≥≥
≤+
≤
≤+++
0;0;0;0
;25000
;20000
;50000
4321
32
1
4321
xxxx
xx
x
xxxx
(2.6.1)
Она содержит ограничения по общей сумме выделенных средств, по
количеству средств, предусмотренных на рекламу по телевидению, на радио и
в газетах, и условия неотрицательности управляющих переменных.
Критерий оптимальности записывается следующим образом:
max47510
4321
→+++= xxxxP
(2.6.2)
(2.6.1), (2.6.2) – математическая модель задачи организации рекламной
деятельности.
Целевая функция и ограничения линейны по управляющим перемен-
ным, следовательно, это задача линейного программирования.
Приведем задачу к каноническому виду, добавив дополнительные пе-
ременные к левым частям ограничений (2.6.1). Получим
≥≥≥≥
=++
=+
=++++
.0;0;0;0
;25000
;20000
;50000
4321
732
61
54321
xxxx
xxx
xx
xxxxx
(2.6.3)
Задача (2.6.1), (2.6.3) может быть решена симплекс-методом. Решение.
Шаг 1. Получение начального решения.
Базисные переменные:
5
x
,
6
x
,
7
x
.
Свободные переменные:
1
x
,
2
x
,
3
x
,
4
x
.
Начальное решение:
}25000;20000;50000;0;0;0;0{
76543210
======== xxxxxxxX
.
Шаг 2. Функция
4321
47510 xxxxP +++=
уже выражена через свободные
переменные.
Шаг 3. Проверка решения на оптимальность. Составляем симплекс-
таблицу (табл. 2.6.1).
Таблица 2.6.1
37
Решение неоптимально, так как последняя строка содержит отрица-
тельные числа.
Шаг 4. Получение нового решения.
Максимальное по абсолютной величине отрицательное число послед-
ней строки – это -10; следовательно, первый столбец является разрешающим и
переменная
1
x
вводится в список базисных переменных. Найдем переменную,
выводимую из списка базисных переменных. Для этого подсчитаем отноше-
ния элементов столбца свободных членов к элементам разрешающего столбца
и выберем среди них минимальное
20000}
0
25000
;
1
20000
;
1
50000
min{ =
Вторая строка является разрешающей, и переменная
6
x
должна быть
выведена из списка базисных переменных.
Разрешающий элемент
1
21
=a
.
Составим новую симплекс-таблицу.
Для подсчета элементов новой симплекс-таблицы по формулам (2.5.4,
2.5.5) удобно использовать правило треугольника, наглядно отображающее
указанные формулы.
Правило треугольника. Для получения элемента новой симплекс-
таблицы надо от элемента предыдущей симплекс-таблицы, стоящего на том
же месте, отнять следующее выражение: произведение элемента разрешаю-
щей строки, стоящего в одном столбце с данным элементом, на элемент дан-
ной строки, стоящий в одном столбце с разрешающим элементом, деленное на
разрешающий элемент. Это выражение как бы соответствует треугольнику.
В качестве примера в табл. 2.6.1 нарисованы треугольники, исполь-
зующиеся для расчета
12
a
и
35
a
.
Таким образом, все элементы разрешающей строки делятся на разре-
шающий элемент. Остальные элементы пересчитываются по правилу тре-
угольника.
Новая симплекс-таблица имеет следующий вид (табл. 2.6.2):
Таблица 2.6.2
Коэффициенты при переменных Базисные пе-
ременные
Сво-
бодные члены
5
x
1
300
00
6
x
200
00
7
x
250
P
5
7
4
0
200
000
Коэффициенты при переменных Базисные пе-
ременные
1
x
2
x
3
x
4
x
5
x
6
x
7
x
Свободные
члены
5
x
1 1 1 1 1 0 0 50000
6
x
1 0 0 0 0 1 0 20000
7
x
0 1 1 0 0 0 1 25000
P
-
10
-
5
-
7
-
4
0
0
0
0
38
Новое решение имеет вид
}25000;0;30000;0;0;0;20000{
76543211
======== xxxxxxxX
200000
1
=P
Таким образом, прибыль увеличилась на 200000 усл. ед.
Это решение неоптимально, так как последняя строка содержит отри-
цательные числа.
Продолжаем оптимизацию.
Разрешающий столбец – третий, так как ему соответствует максималь-
ное по абсолютной величине отрицательное число -7.
25000}
1
25000
;
0
20000
;
1
30000
min{ =
Следовательно, третья строка является разрешающей.
Разрешающий элемент:
33
a
=1.
Перейдем к новой симплекс-таблице (табл. 2.6.3).
Таблица 2.6.3
Коэффициенты при переменных Базисные пе-
ременные
Сво-
бодные члены
5
x
1
1
500
0
6
x
200
00
7
x
250
P
4
0
375
000
}0;0;5000;0;25000;0;20000{
76543212
======== xxxxxxxX
375000
2
=P
Прибыль выросла, но решение
2
X
неоптимально, так как в последней
строке еще осталось отрицательное число.
Получим новое решение.
Разрешающий столбец – четвертый, следовательно, переменная
4
x
вводится в список базисных переменных.
5000}
0
25000
;
0
20000
;
1
5000
min{ =
Разрешающая строка – первая, и переменная
5
x
выводится из списка
базисных переменных.
Новая симплекс-таблица имеет следующий вид (табл. 2.6.4):
Таблица 2.6.4
Коэффициенты при переменных Базисные пе-
ременные
Сво-
бодные члены
5
x
1
1
500
0
6
x
200
00
7
x
250
P
6
395
000
39
Последнее решение является оптимальным, поскольку все числа,
стоящие в последней строке, неотрицательны. Это решение единственно, так
как все элементы последней строки, соответствующие свободным перемен-
ным
2
x
,
5
x
,
6
x
,
7
x
строго положительны.
}0;0;0;5000;25000;0;20000{*
7654321
======== xxxxxxxX
395000*
=
P
Таким образом, для получения максимальной прибыли в размере
395000 усл. ед. надо распределить средства следующим образом: 20000 усл.
ед. вложить в рекламу на телевидении; 20000 усл. ед. вложить в рекламу в га-
зетах и 5000 усл. ед. вложить в рекламу, организованную с помощью расклей-
ки объявлений. Рекламу на радио организовывать не следует.
Изложенные выше вычисления проводились для случая, когда началь-
ное решение является допустимым. Если в начальном решении существуют
0<
i
b
, то допустимое начальное решение можно найти по следующему алго-
ритму.
Шаг 1. Выражение функции
f
через свободные переменные.
Шаг 2. Составление симплекс-таблицы.
Шаг 3. Выбор переменной, вводимой в список базисных переменных.
Просматривается строка, содержащая максимальный по абсолютной
величине отрицательный свободный член, и по максимальному по абсолютной
величине отрицательному элементу этой строки выбирается разрешающий
столбец, например столбец с номером
p
. Переменная, стоящая в этом столбце,
вводится в список базисных переменных. Если просматриваемая строка не со-
держит отрицательных элементов, то система ограничений несовместна, ис-
ходная задача решений не имеет.
Шаг 4. Выбор переменной, выводимой из списка базисных перемен-
ных.
Находят отношения элементов столбца свободных членов к элементам
разрешающего столбца. Рассматривают отношения, в которых числитель и
знаменатель отрицательные, и среди них выбирают минимальное. Строка, со-
ответствующая выбранному отношению, например
q
-я, является разрешаю-
щей, и переменная, стоящая в этой строке, выводится из списка базисных пе-
ременных. Элемент
qp
a
, стоящий на пересечении разрешающей строки и раз-
решающего столбца, является разрешающим элементом.
Шаг 5. По формулам (2.5.4) и (2.5.5) проводят симплекс-
преобразование и переходят к новой симплекс-таблице. Если в новой таблице
все свободные члены неотрицательны, то найденное решение является допус-
тимым и следует перейти к шагу 3 алгоритма симплекс-метода, в противном
случае – к шагу 2 рассматриваемого алгоритма.
Заметим, что существуют различные программы, реализующие сим-
плекс-метод на персональном компьютере. Исследователю нужно только по-
строить линейную модель и ввести исходные данные. Все расчеты, изложен-
40
ные выше, на персональном компьютере осуществятся в течение нескольких
секунд.
После изучения данного раздела целесообразно решить задачу 2 кон-
трольной работы № 3.
2.7. Двойственная задача линейного программирования. Экономи-
ческая интерпретация
Рассмотрим задачу линейного программирования следующего вида:
max...
2211
→+++=
nn
xcxcxcf
(2.7.1)
≥≥≥
≤+++
≤+++
≤+++
0,...,0,0
;...
...............................................
;...
;...
21
2211
22222121
11212111
n
mnmnmm
nn
nn
xxx
bxaxaxa
bxaxaxa
bxaxaxa
(2.7.2)
В задаче требуется максимизировать целевую функцию; все ограниче-
ния являются неравенствами со знаком
≤
, все переменные
n
xxx ,...,,
21
неотри-
цательны. Задача содержит
n
управляющих переменных и
m
ограничений.
Коэффициенты при переменных в целевой функции:
n
ccc ,...,,
21
; свободные
члены:
m
bbb ,...,,
21
.
Двойственная задача линейного программирования имеет вид
min...
2211
→+++=
mm
ybybybg
(2.7.3)
≥≥≥
≥+++
≥+++
≥+++
0,...,0,0
;...
.............................................
;...
;...
21
2211
22222112
11221111
m
nmmnnn
mm
mm
yyy
cyayaya
cyayaya
cyayaya
(2.7.4)
В двойственной задаче требуется найти минимум целевой функции,
ограничения – неравенства со знаком
≥
, управляющие переменные
m
yyy ,...,,
21
неотрицательны. Задача содержит
m
управляющих переменных и
n
ограниче-
ний. Коэффициенты целевой функции задачи
m
bbb ,...,,
21
являются свободными
членами исходной ЗЛП, а свободные члены двойственной задачи
n
ccc ,...,,
21
–
коэффициентами целевой функции исходной ЗЛП. Матрица коэффициентов
двойственной задачи транспонирована, т.е. строки заменены столбцами, а
столбцы – строками.
Задачи (2.7.1), (2.7.2) и (2.7.3), (2.7.4) называются парой взаимно двой-
ственных задач линейного программирования.
Для двойственных задач верна следующая теорема.
Теорема двойственности: если одна из взаимно двойственных задач
имеет оптимальное решение х*, то другая также имеет оптимальное решение