Полшков Ю.Н. Курс лекций по экономико-математическому моделированию
Подождите немного. Документ загружается.
40
Начальный опорный план
. Значение целевой
функции:
(1)
1
15500
01016 4
00010
0004
X
⎛⎞
⎜⎟
⎜
=
⎜
⎜⎟
⎝⎠
⎟
⎟
1
(1)
1
( )4151561031624410605604884022ZX =⋅ +⋅+⋅ +⋅ +⋅+⋅ = ++ + ++ = .
Более удачным и, в тоже время, несложным является
метод минималь-
ной стоимости
. Он состоит в том, что максимально возможные поставки необ-
ходимо осуществлять для потребителей с наименьшей ценой перевозок слева
направо по строке. Остальных – удовлетворять по остаточному принципу, на-
ращивая цену.
Пример 3. По данным примера 1 составим начальный опорный план с
помощью метода минимальной стоимости (табл. 5).
Табл. 5. Метод минимальной стоимости
j
b
i
a
15 15 16 18
4 1 2 1
20
15 5
4 6 3 2
30
1 16 13
5 2 1 4
10
10
0 0 0 0
4
4
Начальный опорный план
. Значение целевой
функции:
(2)
1
0150 5
101613
10 0 0 0
4000
X
⎛⎞
⎜⎟
⎜
=
⎜
⎜⎟
⎝⎠
⎟
⎟
1
)
(2)
1
( ) 1 15 1 5 4 1 3 16 2 13 5 10 15 5 4 48 26 50 148ZX =⋅ +⋅+⋅+⋅ +⋅ +⋅ = +++ + + = .
Как и ожидалось , поэтому в дальнейшем будем ис-
пользовать только метод минимальной стоимости.
(2) (1)
1
()(ZX ZX<
41
Лекция 10. НАХОЖДЕНИЕ ОПТИМАЛЬНОГО РЕШЕНИЯ
ТРАНСПОРТНОЙ ЗАДАЧИ
План
1. Метод потенциалов и его алгоритм.
2. Практические способы реализации метода потенциалов.
1. Для решения транспортной задачи удобно использовать метод потенциалов.
Теорема (оптимальности решения транспортной задачи). Решение
транспортной задачи будет оптимальным, если найдутся такие числа
(
*
i
u
1,i= m) и (
*
j
v 1,
j
n= ), называемые соответственно потенциалами поставщи-
ков и потребителей, которые будут удовлетворять условиям:
**
ij
uv c+=
ij
ij
для ;
*
0
ij
x >
**
ij
uv c+≤ для
*
0
ij
x
=
.
Потенциалы – это двойственные оценки исходной транспортной задачи
(1)-(3) (см. предыдущую лекцию). Здесь (
i
u 1,i= m) – оценка единицы запаса
(потенциал поставщика), (
j
v
1,
j
n=
)– оценка единицы спроса (потенциал по-
требителя). Потенциалы могут быть числами любого знака.
Метод потенциалов является разновидностью симплекс-метода. Он при-
меним и для решения задач, не являющихся транспортными. Эти задачи долж-
ны записываться таблицами транспортного типа. Например, задача о назначе-
нии специалистов или задача о закреплении земельных участков под посев.
Приведём
алгоритм решения закрытой транспортной задачи методом по-
тенциалов.
1) Составляем начальный опорный план методом минимальной стоимо-
сти. Рассчитываем значение целевой функции.
2) Проверяем опорный план на оптимальность следующими действиями.
2.1) Используя заполненные клетки транспортной таблицы, рассчитаем
потенциалы по формуле , полагая
ij
uv c+=
ij 1
0u
=
.
2.2) В незаполненные клетки помещаем оценки оптимальности
ij i j ij
uvc
δ
=+−. Если для всех незаполненных клеток 0
ij
δ
≤
, то опорный план
является оптимальным и алгоритм завершается вычислением минимального
значения целевой функции. Если найдётся хотя бы одна незаполненная клетка с
0
ij
δ
> , то алгоритм продолжается.
2.3) Клетку с наибольшей положительной оценкой
ij
δ
считают перспек-
тивной
. К перспективной клетке строится цикл. Перспективной клетке соот-
ветствует
величина перераспределения груза
ρ
+
. В остальных вершинах
цикла знаки чередуются
ρ
− ,
ρ
+ и т.д. Величину перераспределения вычисля-
ем по формуле min
ij
x
ρ
= , где
ij
x
– объёмы перевозки, записанные в вершинах
цикла и отмеченные
ρ
−
, т.е. уменьшаемые объёмы перевозок.
42
2.4) Перераспределяем груз в объёме
ρ
по циклу. Получаем новый опор-
ный план. Проверяем его на оптимальность, т.е. переходим к пункту 2.1) алго-
ритма.
Замечание. После нахождения оптимального плана рассуждают следую-
щим образом. Если все оценки незаполненных клеток 0
ij
δ
<
, то оптимальный
план единственный. Если же для некоторых из них 0
ij
δ
=
, то оптимальный
план не единственный. Можно найти другие оптимальные планы, перераспре-
деляя груз по циклу в эти клетки. При этом общая стоимость перевозки не из-
менится и останется минимальной.
Пусть транспортная задача имеет оптимальных планов .
Тогда общее оптимальное решение можно записать в виде выпуклой линейной
комбинации этих планов, т.е.
k
12
, ,...,
k
XX X
*
11 2 2
...
kk
ХХХ
λλ λ
=+ ++Х,
где
12
... 1
k
λ
λλ
+++=,
12
0, 0,..., 0
k
λ
λλ
≥≥ ≥.
При наличии двух оптимальных планов пользуются записью:
*
12
(1 )ХХ
λλ
=+−Х
1
,
где 0
λ
≤≤.
2. Применим описанный алгоритм к решению конкретной транспортной задачи.
Пример 1. Табл. 1 (см. предыдущую лекцию) содержит запасы постав-
щиков (т), потребности потребителей (т) и тарифы перевозок единицы товара
(тыс. грн.). Требуется решить транспортную задачу.
Табл. 1. Условие транспортной задачи
j
b
i
a
15 15 16 18
4 1 2 1
20
4 6 3 2
30
5 2 1 4
10
Решение. Вводим фиктивного поставщика (табл. 2).
43
Табл. 2. Транспортная таблица с фиктивным поставщиком
j
b
i
a
15 15 16 18
4 1 2 1
20
4 6 3 2
30
5 2 1 4
10
0 0 0 0
4
Применим алгоритм метода потенциалов.
1) Составляем начальный опорный план методом минимальной стоимо-
сти (табл. 3). Рассчитываем значение целевой функции.
Табл. 3. Начальный опорный план
j
b
i
a
15 15 16 18
4 1 2 1
20
15 5
4 6 3 2
30
1 16 13
5 2 1 4
10
10
0 0 0 0
4
4
Итак,
и
1
0150 5
1 0 16 13
10 0 0 0
4000
X
⎛⎞
⎜⎟
⎜⎟
⎟
=
⎜
⎜⎟
⎝⎠
1
()148ZX
=
(тыс. грн.).
2) Проверяем опорный план на оптимальность.
1
X
2.1) Используя заполненные клетки табл. 3, рассчитываем потенциалы по
формуле , полагая
ij
uv c+=
ij 1
0u
=
:
44
12 1 2
14 4
24 2
21 1
23 3
31 3
41 4
1, 0 1
11
21
43
32
52
03
uv u v
uv v
uv u
uv v
uv v
uv u
uv u
+= =⇒=
⎧
⎪
+=⇒=
⎪
⎪
+=⇒=
⎪
+=⇒=
⎨
⎪
+=⇒=
⎪
+=⇒=
⎪
⎪
+=⇒ =−
⎩
Добавляем в табл. 3 строку и столбец, и записываем в них потенциалы
(табл. 4).
2.2) В незаполненные клетки табл. 4 помещаем оценки оптимальности
ij i j ij
uvc
δ
=+−, выделяя их квадратными скобками. Т.к. имеются незаполнен-
ные клетки с 0
ij
δ
> , то алгоритм продолжается.
Табл. 4. Начальный опорный план с потенциалами
j
b
i
a
15 15 16 18
i
u
4 1 2 1
1
0u =
20
[–1]
15
[0]
5
4 6 3 2
2
1u =
30
1
[–4]
16
13
5 2 1 4
3
2u =
10
10
[1] [3] [–1]
0 0 0 0
4
3u =−
4
4
[–2] [–1] [–2]
1
3v =
2
1v
=
3
2v
=
4
1v
=
j
v
2.3) Клетка (3,3) с наибольшей положительной оценкой
33
3
δ
= является
перспективной. К перспективной клетке строится цикл (рис. 1):
[(3,3); (3,1); (2,1); (2,3); (3,3)].
16
ρ
−
1
ρ
+
Рис. 1. Цикл перераспределения груза
ρ
+
10
ρ
−
45
Циклом, или замкнутым контуром, называется последовательность
клеток таблицы, соединённых замкнутой ломаной линией без самопересечений.
Количество вершин в цикле всегда чётно и повороты линий производятся толь-
ко под прямым углом.
Для нашего цикла min{10,16} 10
ρ
==.
2.4) Перераспределяем груз в объёме
10
ρ
=
(т) по циклу. Получаем но-
вый опорный план:
2
015 0 5
11 0 6 13
00100
4000
X
⎛⎞
⎜⎟
⎜⎟
=
⎜⎟
⎜⎟
⎝⎠
.
Теперь (тыс. грн.).
2
( ) 118ZX =
Проверяем опорный план на оптимальность, т.е. переходим к пункту
2.1) алгоритма. Считаем потенциалы и заносим в табл. 5. В незаполненные
клетки помещаем оценки оптимальности.
2
X
Табл. 5. Второй опорный план с потенциалами
j
b
i
a
15 15 16 18
i
u
4 1 2 1
1
0u =
20
[–1]
15
[0]
5
4 6 3 2
2
1u =
30
11
[–4]
6
13
5 2 1 4
3
1u =−
10
[–3] [–2]
10
[–4]
0 0 0 0
4
3u =−
4
4
[–2] [–1] [–2]
1
3v =
2
1v
=
3
2v
=
4
1v
=
j
v
Т.к. для всех незаполненных клеток 0
ij
δ
≤
, то опорный план является
оптимальным и
2
X
min
118Z
=
(тыс. грн.).
Незаполненная клетка (1,3) имеет оценку оптимальности 0
ij
δ
= . Поэтому
оптимальный план не единственный. К этой клетке строится цикл:
2
X
[(1,3); (1,4); (2,4); (2,3); (1,3)].
Перераспределяем груз в объёме min{5,6} 5
ρ
=
= (т) по циклу. Получаем
новый оптимальный план
46
3
015 5 0
11 0 1 18
00100
4000
X
⎛⎞
⎜⎟
⎜⎟
=
⎜⎟
⎜⎟
⎝⎠
,
для которого (тыс. грн.).
min
118Z =
Удаляем из задачи фиктивного поставщика. Имеем два оптимальных пла-
на:
*
1
015 0 5
11 0 6 13
00100
X
⎛⎞
⎜⎟
=
⎜⎟
⎜⎟
⎝⎠
; .
*
2
015 5 0
11 0 1 18
00100
X
⎛⎞
⎜⎟
=
⎜⎟
⎜⎟
⎝⎠
Общее оптимальное решение:
** *
12
01555 5
(1 ) 11 0 1 5 18 5
00 10 0
ХХ Х
λ
λ
λ
λλλ
−
⎛⎞
⎜⎟
=+− = + −
⎜⎟
⎜⎟
⎝⎠
,
где 01
λ
≤≤. Причём (тыс. грн.).
min
118Z =
47
Лекция 11. ЗАДАЧИ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
План
1. Математическая модель задачи нелинейного программирования.
2. Графический метод решения задач нелинейного программирования.
1. При решении сложных задач математического программирования может ока-
заться, что линейных функций недостаточно. Рассмотрение реальных экономи-
ческих ситуаций требует наиболее полного и точного учёта зависимостей меж-
ду факторами, влияющими на целевую функцию и ограничения задачи. Это
приводит к построению нелинейных экономико-математических моделей.
Пример 1. Предприятие выпускает два вида продукции и , на кото-
рые расходует три вида ресурсов , и (табл. 1).
1
P
2
P
1
S
2
S
3
S
С учётом брака расход ресурсов на единицу выпуска продукции состав-
ляет (
ij ij j
akx+⋅ 1, 3i = ; 1, 2j = ). Конкуренция и насыщение рынка продукцией
приводит к снижению дохода от реализации одной единицы, т.е. .
jj
clx−⋅
j
Табл. 1. Данные задачи
Расход ресурса на вы-
пуск ед. прод.
Коэфф. увеличения рас-
хода ресурса на ед. прод.
Ресурс
1
P
2
P
1
P
2
P
Запас
ресурса
1
S
11
a
12
a
11
k
12
k
1
b
2
S
21
a
22
a
21
k
22
k
2
b
3
S
31
a
32
a
31
k
32
k
3
b
Цена реа-
лиз. ед.
прод. (грн.)
1
c
2
c
Коэфф.
снижения
цены
1
l
2
l
Количество
продукции
(ед.)
1
x
2
x
Предприятие стремится выпускать такое количество продукции, чтобы
доход от реализации был максимальным. Требуется составить математическую
модель задачи.
Решение. Пусть
Z
– общий доход от реализации (грн.), тогда целевая
функция имеет вид:
1111 2 222
()( )Zclxx clxx max
=
−⋅ + −⋅ → . (1)
Запишем ограничения задачи:
48
11 11 1 1 12 12 2 2 1
21 21 1 1 22 22 2 2 2
31 31 1 1 32 32 2 2 3
()( )
()( )
()( )
akxxakxxb
akxxakxxb
akxxakxxb
+⋅ + +⋅ ≤
⎧
⎪
+⋅ + +⋅ ≤
⎨
⎪
+⋅ + +⋅ ≤
⎩
(2)
Объёмы производства должны быть неотрицательными:
0
j
x ≥ ( 1, 2j = ). (3)
Рассмотрение примера окончено.
В общем виде задача нелинейного программирования состоит в отыска-
нии такого вектора неизвестных
12
( ; ;...; )
n
Xxx x=
J
JG
, который бы приводил целе-
вую функцию к экстремальному значению:
12
(, ,..., ) max (min)
n
ZFxx x=→. (4)
Система ограничений может содержать как неравенства, так и равенства:
12 1
12 1
( , ,..., ) ( 1, )
(, ,..., ) ( 1,)
ini
ini
gxx x b i m
gxx x b i m m
⎧
≤=
⎪
⎨
==+
⎪
⎩
(5)
Среди искомых переменных могут быть отрицательные:
0
j
x ≥ (
1
1,
j
n= ); 0
j
x
<
(
1
1,
j
n=+n). (6)
Задачу (4)-(6) называют
математической моделью задачи нелинейного
программирования
, если хотя бы одна из функций или (
F
i
g 1,i= m) является
нелинейной. Для решения задач нелинейного программирования общего мето-
да нет и они решаются сложнее, чем задачи линейной оптимизации.
2. Если задача нелинейного программирования имеет две искомые переменные,
то её можно решить
графическим методом.
Пример 2. Предприятие выпускает два вида продукции и , на кото-
рые расходует три вида ресурсов , и (табл. 2).
1
P
2
P
1
S
2
S
3
S
Табл. 2. Данные задачи
Расход ресурса на выпуск единицы
продукции (
ij
a 1, 3i
=
; 1, 2j = )
Ресурс
1
P
2
P
Запас ре-
сурса
i
b
1
S
4
6
450
2
S
2
2
160
3
S
3
2
210
Цена реализ. ед. прод.
(тыс. грн.)
j
c
100 140
Коэфф. снижения це-
ны
j
l
1 1
Количество продук-
ции
j
x
(ед.)
1
x
2
x
49
Кризисные явления, конкуренция и насыщение рынка данной продукцией
приводит к снижению дохода от реализации одной единицы по формуле
. Требуется найти такой план выпуска продукции, который бы макси-
мизировал общий доход от её реализации.
jj
clx−⋅
j
Решение. Пусть
Z
– общий доход от реализации (тыс. грн.). Составим
математическую модель задачи нелинейного программирования.
11 2 2
(100 ) (140 ) maxZxx xx
=
−+− →
, (7)
12
12
12
4 6 450
2216
3 2 210
xx
xx
xx
+≤
⎧
⎪
+≤
⎨
⎪
+≤
⎩
0
(8)
0
j
x ≥ ( 1, 2j = ). (9)
ОДР (8)-(9) – это многоугольник (рис. 1) с вершинами , OABCD (0;0)O
(0;75)
A
, (15;65)
B
, и . (50;30)C (70;0)D
Рис. 1. Иллюстрация графического метода решения
Преобразуем целевую функцию (7):
22
11 2 2
100 140
Z
xx xx=−+ −;