Кошак Ж.В, Минина Е.М. Применение ЭВМ в отрасли
Подождите немного. Документ загружается.
41
Таблица 11 – Матрица рисков
Варианты возможных решений (или
состояния природы)
Средний риск
i
r
Стратегия
статистика
A
i
П
1
П
2
П
3
A
1
r
11
r
12
r
13
1
r
A
2
r
21
r
22
r
23
2
r
A
3
r
31
r
32
r
33
3
r
Вероятность
данных
событий q
j
q
1
q
2
q
3
макс. по
столбцам β
j
Оптимальной по критерию Сэвиджа считается та чистая стратегия Аi, при
которой миниминизируется величина rij максимального риска, т.е. обеспечивается
min
i
max
j
r
ij
. Таким образом, критерий Сэвиджа советует ориентироваться не на
выйгрыш, а на риск. Это критерий крайнего пессимизма, но здесь пессимизм
понимается по другому: рекомендуется избегать большого риска при принятии
решения. Иначе говоря за оптимальную стратегию статистика принимается
чистая стратегия A
i
, при которой минимизируется средний риск, т.е.
обеспечивается
ii
rr min=
При этом средний риск расчитывается
∑
=
==
n
j
jiji
miqrr
1
),1(
(49)
Критерий Гурвица является критерием пессимизма-оптимизма. За
оптимальную принимается та стратегия, для которой выполняется соотношение
h= max
i
(λmin
j
a
ij
+(1-λ)max
j
a
ij
)=max
i
h
i,
т.е. выбирается максимальное значение h
i
из таблицы 12.
Параметр λ изменяется в диапазоне [0;1]. Выбирается из субъективных
соображений.
При λ=0 имеем критерий крайнего оптимизма, когда рекомендуется
выбирать стратегию, обеспечивающую самый большой выигрыш, а при λ=1 –
критерий Гурвица превращается в критерий пессимизма Вальда. При 0<λ<1
получается нечто среднее между тем и другим. Чем ответственнее ситуация, тем
больше стремление подстраховаться в ней и не рисковать без должных
оснований, тем ближе к единице выбирается коэффициент пессимизма λ.
Все промежуточные результаты заносятся в таблицу 12.
Таблица 12
П
1
П
2
П
3
min
j
a
ij
λmin
j
a
ij
max
j
a
ij
(1-λ)max
j
a
ij
h
i
А
1
А
2
А
3
42
На основании критериев Баейеса, Вальда Сэвиджа и Гурвица делается
вывод об оптимальной стратегии.
Задания по теме «Критерии принятия решения» в приложении Д.
7 ТРАНСПОРТНАЯ ЗАДАЧА
7.1 Постановка транспортной задачи по критерию стоимости
Транспортная задача (Т3) формулируется следующим образом: некоторый
однородный продукт, сосредоточенный у m поставщиков А
i
, в количестве а
i
(i=1,m) единиц соответственно, необходимо доставить n потребителям В
j
в
количестве b
j
( j=1,n) единиц. Известна стоимость c
ij
, перевозки единицы груза от
поставщика А
i
; к потребителю В
j
. Необходимо составить план перевозок,
позволяющий вывезти все грузы от поставщиков A
i
, полностью удовлетворить
потребности потребителей В
j
и имеющий минимальную стоимость. Для
построения экономико-математической модели ТЗ рассмотрим матрицу X
X=
mnmm
n
n
xxx
xxx
xxx
K
KKKK
K
K
21
22221
11211
где х
ij
(i=1,m; j=1,n) обозначает количество единиц груза, которое
необходимо доставить от поставщика А
i
потребителю В
j
. Матрица Х=[х
ij
]
называется матрицей планирования или планом перевозок. Предполагается, что
все х
ij
>=0.
Тарифы перевозок c
ij
единицы груза от поставщика А
i
к потребителю В
j
запсывается в виде матрицы С=[c
ij
]
m*n
:
C=
mnmm
n
n
ccc
ccc
ссс
K
K
K
21
22221
11211
,
которая называется матрицей тарифов. Условия задачи представляется в виде
таблицы 13, которая называется распределительной.
Таблица 13 – Распределительная таблица
Потребители
Поставщики
B
1
B
2
K
B
N
Запасы
A
1
с
11
х
11
с
12
х
12
K
с
1n
х
1n
a
1
A
2
С
21
Х
21
С
22
х
22
K
С
2n
х
2n
a
2
K
K
K
K
K
K
A
m
С
m1
х
m1
с
m2
х
m2
K
с
mn
х
mn
a
m
Потребности
b
1
b
2
K
b
m
43
Экономико-математическая модель ТЗ должна отражать все условия и цель
задачи: переменные x
ij
должны удовлетворять ограничениям по запасам,
потребностям и условиям неотрицательности. Эти условия можно записать
следующим образом:
≥
==
==
∑
∑
=
=
0
),1(
),1(
1
1
y
j
m
j
y
i
n
j
y
x
njbx
miax
(50)
Суммарная стоимость перевозок выражается суммой
F= →
∑∑
==
y
m
i
n
j
y
xc
11
min
(51)
План перевозок Х=[x
ij
] называется допустимым, если он удовлетворяет
системе ограничений (50). Допустимый план перевозок, доставляющий минимум
ЦФ (51) называется оптимальным. Модель ТЗ называется закрытой, если
суммарный объём груза, имеющегося у поставщиков, равен суммарному спросу
потребителей:
∑∑
==
=
n
j
j
m
i
i
ba
11
(52)
Если выполняется одно из условий
∑∑
==
>
n
j
j
m
i
i
ba
11
или
∑∑
==
<
n
j
j
m
i
i
ba
11
(53)
то модель задачи называется открытой.
Теорема (о существовании допустимого плана).
Для того, чтобы ТЗ имела допустимые планы, необходимо и достаточно
выполнение условия
∑∑
==
=
n
j
j
m
i
i
ba
11
7.2 Построение начального опорного плана
Допустимый план, являющийся крайней точкой области допустимых
планов, будем называть опорным. В силу основной теоремы линейного
программирования целевая функция достигает своего экстремума в крайней точке
области допустимых планов, поэтому будем искать оптимальное решение среди
опорных планов. Рассмотрим сначала закрытую модель задачи.
Построение опорных планов, а также преобразование их проводятся
непосредственно в распределительной таблице. Если в плане перевозок
переменная х
ik
равна числу отличному от нуля, то это число записывается в
соответствующей клетке (i;k) и она считается занятой или базисной. Если же
44
х
ik
=0, то клетка (i;k) остается свободной. При этом число базисных клеток,
должке быть равно m+n-1, а соответствующий опорный план называется
невырожденным.
Дня построения начального опорного плана можно использовать методы
o метод северо-западного угла;
o метод Фогеля;
o метод минимального элемента.
Рассмотрим метод минимального элемента. Сущность этого метода состоит
в следующем. В первую очередь заполняется клетка с минимальным значением
тарифа. При этом в клетку записывается максимально возможное значение
поставки. Из рассмотрения исключают строку, соответствующую поставщику,
запасы которого полностью израсходованы, или столбец. соответствующий
потребителю, спрос которого полностью удовлетворен. После этого из
оставшихся клеток таблицы снова выбирают клетку с наименьшим тарифом.
Процесс распределения заканчивается, когда все запасы поставщиков исчерпаны,
а спрос потребителей полностью удовлетворен. В результате получим опорный
план, который должен содержать m+n-1 базисных клеток. Если же число занятых
клеток окажется меньше, чем m+n-1, то план называется вырожденным. Для
дальнейшего решения задачи в свободную клетку, которая не образует замкнутых
циклов с ранее занятыми клетками, нужно поместить число 0 — нуль-поставку и
эта клетка считается занятой.
7.3 Метод потенциалов
Поставим в соответствие каждому поставщику числа u
i
(i=1,m), а
потребителю - числа v
i
(j=1,n), которые называются потенциалами. Если план
Х=[х
ij
] ТЗ является оптимальным, то ему соответствует система из m+n
потенциалов, удовлетворяющих условиям u
i
+v
j
=c
ij
для базисных клеток u
i
+v
j
>c
ij
и
для свободных клеток (I=1,m, j=1,n). Потенциалы можно найти, решив систему
уравнений u
i
+v
j
=c
ij
составленных для каждой базисной клетки. Так как система
неопределённая, то, чтобы найти решение, одному из потенциалов придаём
произвольное числовое значение, например ноль, тогда остальные потенциалы
определяются однозначно.
7.4 Условия оптимальности
Для исследования плана на оптимальность для каждой свободной клетки
определяем разность между тарифом клетки и суммой потенциалов. Число S
ij
называется оценкой свободной клетки
S
ij
=c
ij
-(u
i
+v
j
) (54)
Ecли таких клеток несколько, то наиболее перспективной для загрузки
является та клетка, для которой оценка наименьшая. Для наиболее перспективной
свободной клетки строится замкнутый цикл с вершинами в базисных клетках. В
общем случае цикл представляет собой замкнутую ломаную линию, состоящую
из звеньев, пересекающихся под прямым углом. Каждое звено соединяет две
45
клетки одной строки (или одного столбца). Цикл включает одну свободную
клетку, остальные клетки цикла должны быть занятыми.
Для свободной клетки всегда можно построить единственный цикл.
Вершинам этого цикла условно присваиваются знаки: свободной клетке — плюс,
следующей по часовой или против часовой стрелки занятой клетке — минус,
следующей – снова плюс и т.д. В клетках со знаком минус выбирается
наименьшее количество груза λ, которое перемещается по клеткам этого цикла,
т.е. в клетку со знаком плюс прибавляется груз в количестве λ единиц, а в клетке
со знаком минус – вычитается.
λ=min{x
ij0
;x
i0j
}
Рисунок 9 – Построение цикла транспортной задачи
Если из занятых клеток можно выделить хотя бы один цикл, то план
перевозок не является опорным.
Сформулируем алгоритм решения ТЗ методом потенциалов:
o построить начальный опорный план;
o вычислить потенциалы поставщиков и потребителей u
i
+v
j
;
o вычислить оценки S
ij
для свободных клеток и проверить план на
оптимальность;
o если план не оптимален, то перейти к нехудшему опорному плану.
7.5 Открытая модель транспортной задачи
Для открытой модели возможны два случая:
суммарные запасы превышают суммарные потребности:
∑∑
==
>
n
j
j
m
i
i
ba
11
(55)
суммарные потребности превышают суммарные запасы:
∑∑
==
<
n
j
j
m
i
i
ba
11
(56)
Открытая модель ТЗ решается приведением к закрытой модели. В случае
(55) вводится фиктивный потребитель В
n+1
потребности которого
b
n+1
=
∑∑
==
−
n
j
j
m
i
i
ba
11
(57)
в случае (56) вводится фиктивный поставщик A
m+1
, запасы которого
+
-
X
i0j
+
X
ij
-
X
ij0
46
a
n+1
=
∑∑
==
−
n
j
j
m
i
i
ab
11
(58)
Стоимость перевозки единицы груза, как до фиктивного потребителя, так и
от фиктивного поставщика полагают равным нулю. После преобразований задача
принимает вид закрытой модели и решается обычным способом.
Пример 1. Магазины «Форум» (В
1
), «Октябрьский» (В
2
), «ЦУМ» (В
3
),
«Континент» (В
4
) получает мясную продукцию от мясокомбинатов города
Минска (А
1
), Могилёва (А
2
) и Витебска (А
3
), которые ежедневно могут поставить
соответственно 60, 40, 35 тонн мясной продукции. Суточные потребности
магазинов составляют 40, 25, 20, 50 тонн. Известна матрица транспортных
расходов на доставку 1 тонны мясной продукции из мясокомбината каждому
магазину и себестоимость единицы продукции.
1. Методом потенциалов найти план перевозок мясной продукции при
котором минимизируются суммарные затраты по её изготовлению и доставки
потребителям при обязательном условии, что продукция пункта, в котором
себестоимость её производства наименьшая, распределяется полностью;
2. Вычислить суммарные затраты F
min
;
Стоимость перевозки 1 тонны мясной продукции задана матрицей.
C=
4537
3624
2145
Определить оптимальный план поставки мясной продукции, в каждую
торговую точку для удовлетворения потребностей, чтобы суммарные
транспортные издержки были минимальными.
1) Экономико-математическая модель задачи
Представим данные задачи в виде распределительной таблицы 14
Таблица 14 – Распределительная таблица
B
j
A
i
B
1
B
2
B
3
B
4
A
1
5
x
11
4
x
12
1
x
13
2
x
14
60
A
2
4
x
21
2
x
22
6
x
23
3
x
24
40
A
3
7
x
31
3
x
32
5
x
33
4
x
34
35
b
j
40 25 20 50 135
Так как 135
4
1
3
1
==
∑∑
== j
j
i
i
ba , то модель ТЗ закрытая. Экономико-математическая
модель задачи имеет вид:
47
==≥
=++
=++
=++
=++
=+++
=+++
=+++
4.1,3.1,0
50
20
25
40
35
40
60
342414
332313
322212
312111
34333231
24232221
14131211
jix
xxx
xxx
xxx
xxx
xxxx
xxxx
xxxx
y
Целевая функция определяется из соотношения:
F=5x
11
+4x
12
+x
13
+2x
14
+4x
21
+2x
22
+6x
23
+3x
24
+7x
31
+3x
32
+5x
33
+4x
34
→ min
2) Построение начального опорного плана
Начальный опорный план получим по методу минимального элемента. Этот
план представлен в таблице 15.
Таблица 15 – Начальный опорный план
B
j
A
i
B
1
B
2
B
3
B
4
a
i
u
i
A
1
5
4
1
20
2
40
60 0
A
2
4
+
2
25
6
3
10
40 1
A
3
7
35
3
+
5
4
35 4
b
j
40 25 20 50
v
j
3 1 1 2
Записывается начальное опорное решение
X
0
=
00035
100255
402000
и определяется соответствующее значение целевой функции
F
0
=20+2*40+4*5+2*25+3*10+7*35=445
3) Решение задачи методом потенциалов
Пусть каждому поставщику А
i
соответствуют потенциалы u
i
,а каждому
потребителю B
j
– потенциалы v
j
(i=1,m; j=1,n). Составим систему потенциалов
48
=+
=+
=+
=+
=+
=+
1
3
2
4
2
1
13
42
22
12
41
31
vu
vu
vu
vu
vu
vu
(59)
Для ее решения примем u
1
=0, тогда, решая систему (59) находим v
3
=1, v
4
=2,
u
2
=1, v
1
=3, u
3
=4, v
2
=1.
Найденные потенциалы поставщиков и потребителей указаны справа и внизу
таблицы 15.
4) Проверка условий оптимальности
Для проверки условия оптимальности находят оценки свободных клеток S
ij
S
11
=5-(3+0)=2
S
12
=4-(1+0)=3
S
23
=6-(1+1)=4
S
32
=3-(1+4)=-2
S
33
=5-(1+4)=0
S
34
=4-(2+4)=-2
Полученный план не является оптимальным, т.к. среди оценок S
ij
есть
отрицательные S
32
=S
34
=-2 .
Получены две перспективные клетки с одинаковыми значениями, поэтому
загрузим, например, клетку (3;2)
Для неё построим цикл, который включает клетки (3;2), (3;1), (2;1), (2;2).
Цикл построен в таблице 15 (выделено жирным).
В свободной клетке указанного цикла условно запишем знак плюс, в
следующей — минус и т.д. Выберем наименьшее количество груза в
отрицательных вершинах
λ=min(25;35)=25ед.
Чтобы общий баланс не изменился, в клетках цикла со знаком плюс
прибавляем 25, а из клеток со знаком минус вычитаем столько же единиц. Новый
опорный план приведён в таблице 16. Потенциалы поставщиков и потребителей
вычислены непосредственно в таблице 16.
49
Таблица 16
B
j
A
i
B
1
B
2
B
3
B
4
a
i
u
i
A
1
5
4
1
20
2
40
60 0
A
2
4
30
2
6
3
10
40 1
A
3
7
10
3
25
5
4
35 4
b
j
40 25 20 50
v
j
3 1 1 2
Записывается полученный опорный план
X
1
=
002510
100030
402000
Определяется значение целевой функци
F=20+2*40+4*30+3*10+7*10+3*25=395
Находятся оценки свободных клеток
S
11
=5-(3+0)=2
S
12
=4-(1+0)=3
S
23
=2-(1+1)=0
S
32
=6-(1+4)=4
S
33
=5-(1+4)=0
S
34
=4-(2+4)=-2
План, представленный в таблице 16, не является оптимальным, т.к. все
оценки свободных клеток положительны.
Однако, за счёт загрузки клеток (3,4) его можно улучшить. Замкнутый цикл
для клетки (3,4) построен в таблице 16. После смещения 10 единиц груза получим
новый опорный план, представленный в таблице 17.
Таблице 17
B
j
A
i
B
1
B
2
B
3
B
4
u
i
A
1
5
4
1
20
2
40
0
A
2
4
40
2
0
6
3
1
A
3
7
3
25
5
4
10
2
v
j
3 1 1 2
50
Опорный план равен
X
2
=
100250
00040
402000
Значение целевой функции равно
F=20+2*40+4*40+3*25+4*10=375
Полученный план является вырожденным, т.к. число занятых
клеток не удовлетворяет условию r=3+4-1=6. Поместим нуль,
например, в клетку (2;2) и будем считать её занятой. Потенциалы
поставщиков и потребителей определены в таблице 17.
Найдём оценки свободных клеток
S
11
=5-(3+0)=2
S
12
=4-(1+0)=3
S
23
=6-(1+1)=4
S
32
=3-(2+1)=0
S
33
=7-(3+2)=2
S
34
=5-(1+2)=2
Следовательно, план Х
2
является оптимальным, а соответствующее ему значение
целевой функции ЦФ F
min
=375.
7.6 Реализация транспортной задачи с помощью поиска решения
в электронных таблицах Excel
При решении транспортной задачи при помощи поиска решения в Excel
исходные данные представляются в виде формы, в которую заносятся количество
продукции у поставщиков (производителей), потребности в продукции
потребителей и матрица тарифов.
Рассмотрим заполнение расчетной формы на следующем примере.
Пример 2. Три поставщика А1, А2, А3 поставляют соответственно 25, 43,
69 т продукции для обеспечения торговых точек В1, В2, В3, В4. потребности
торговых точек соответственно равны 28, 32, 40, 37 т. стоимость перевозки 1т
продукции задана матрицей:
=
94811
151275
5693
с
Определить оптимальный план поставки продукции в каждую торговую
точку для удовлетворения потребностей, чтобы суммарные издержки были
минимальными.
Исходные данные необходимо представить в виде таблицы 18: