Полный текст:
Ежегодная
потребность в материалах для строительства составляет 3200 т. Стоимость
подачи заказа – 230 у.е. Затраты на хранение одной тонны материалов на
складе составляют 0,9 у.е. в сутки. Время доставки материалов на
строительную площадку составляет 17 дней, максимально возможное время
задержки в поставке составляет 2 дня. Определить оптимальную стратегию
управления запасами и дать графическое представление модели.
РЕШЕНИЕ
Суточная потребность в материалах
3200/360=8,89 т.
Отсюда по формуле Уилсона оптимальный
размер заказа:
т.
Определим параметры модели
управления запасами с фиксированным размером заказа:
Ожидаемое потребление 8,89
т./день;
Время расходования запаса
67,4/8,89=7,6 (7) дней;
Потребление за время поставки
17*8,89=151,13 т.;
Максимальное потребление за время
поставки (17+2)*8,89=168,91 т.;
Страховой запас 17,78 т.;
Пороговый уровень 168,91 т.;
Максимально желаемый уровень
запаса 186,69 т.
Решить
транспортную задачу методом потенциалов. Начальное решение Х0
найти методом наименьшей стоимости.
13
4
13
2
5
100
1
15
5
6
7
130
15
6
4
5
5
140
4
6
13
4
11
220
50
160
130
10
210
РЕШЕНИЕ
Начнём расстановку с наименьшего
элемента – это элемент 2, 1 со стоимостью перевозки 1. Далее назначаем
перевозку в ячейке 1, 4. Затем в ячейки 3, 3 и 1, 2. Далее назначаем перевозки
в ячейки 4, 1, 2, 5 и 4, 5.
13
4
90
13
2
10
5
100
1
50
15
5
6
7
80
130
15
6
4
130
5
5 10
140
4
6
70
13
4
11 120
220
50
160
130
10
210
Произвели распределение товара
между всеми потребителями, при этом часть товара осталась нераспределённой, 30
единиц в четвёртой строке. Это говорит о том, что данная транспортная задача
является открытой.
Стоимость плана перевозок:
С=1*50+4*90+2*10+7*80+4*130+6*70+5*10+11*120=3300.
Произведём улучшение плана
перевозок методом потенциалов. Введём
потенциалы для каждой строки и каждого столбца. Затем вычислим оценки
потенциалов для ячеек с нулевыми перевозками и, в случае если оценки
потенциалов для нулевых перевозок окажутся положительными, перемещаем перевозки
в ранее незадействованные ячейки. Затем расставляем новые потенциалы и
вычисляем новые оценки потенциалов для ячеек с нулевыми перевозками.
2
13 –10
4 90
13 –5
2 10
5 +4
100
0
1 50
15 –13
5 +1
6 –6
7 80
130
–2
15 –14
6 –4
4 130
5 –7
5 10
140
4
4 +1
6 70
13 –3
4 0
11 120
220
50
160
130
10
210
Ui
1
2
6
0
7
Vj
Произведём перемещение 90 единиц
товара из ячейки 1, 2 в ячейку 1, 5, а из ячейки 4, 5 в ячейку 4, 5.
0
13 –14
4 –4
13 –9
2 10
5 90
100
2
1 50
15 –13
5 +1
6 –2
7 80
130
0
15 –16
6 –6
4 130
5 –3
5 10
140
6
4 +1
6 160
13 –3
4 +4
11 30
220
50
160
130
10
210
Ui
–1
0
4
2
5
Vj
Стоимость улучшенного плана
перевозок: С=1*50+6*160+4*130+2*10+7*80+5*90+5*10+11*30=2940.
Производим следующее улучшение
плана перевозок и расставляем новые оценки потенциалов:
0
13 –14
4 –4
13 –9
2 10
5 90
100
2
1 50
15 –13
5 +1
6 –2
7 80
130
0
15 –16
6 –6
4 130
5 –3
5 10
140
6
4 +1
6 160
13 –3
4 +4
11 30
220
50
160
130
10
210
Ui
–1
0
4
2
5
Vj
Производим следующее улучшение
плана перевозок и расставляем новые оценки потенциалов:
2
13 –10
4 90
13 –5
2 10
5 +1
100
0
1 50
15 –13
5 +1
6 –6
7 80
130
–2
15 –14
6 –4
4 130
5 –7
5 10
140
4
4 +1
6 70
13 –3
4 0
11 120
220
50
160
130
10
210
Ui
1
2
6
0
7
Vj
Производим следующее улучшение
плана перевозок и расставляем новые оценки потенциалов:
2
13 –10
4 –4
13 –9
2 10
5 90
100
0
1 50
15 –13
5 +1
6 –2
7 80
130
0
15 –16
6 –6
4 130
5 –3
5 10
140
6
4 +1
6 160
13 –3
4 +4
11 30
220
50
160
130
10
210
Ui
–1
0
4
2
5
Vj
Производим следующее улучшение
плана перевозок и расставляем новые оценки потенциалов:
0
13 –14
4 –4
13 –9
2 –4
5 90
100
2
1 50
15 –13
5 +1
6 –6
7 80
130
0
15 –16
6 –6
4 130
5 –7
5 10
140
6
4 +1
6 160
13 –3
4 +4
11 30
220
50
160
130
10
210
Ui
–1
0
4
–2
5
Vj
Производим следующее улучшение
плана перевозок и расставляем новые оценки потенциалов:
0
13 –13
4 –4
13 –9
2 –4
5 100
100
1
1 50
15 –14
5 80
6 –7
7 –1
130
0
15 –15
6 –6
4 50
5 –7
5 90
140
6
4 +2
6 160
13 –3
4 10
11 20
220
50
160
130
10
210
Ui
0
0
4
–2
5
Vj
Производим следующее улучшение
плана перевозок и расставляем новые оценки потенциалов:
0
13 –13
4 –2
13 –10
2 –2
5 100
100
2
1 30
15 –11
5 80
6 –4
7 20
130
0
15 –15
6 –4
4 50
5 –5
5 90
140
4
4 20
6 160
13 –6
4 10
11 –2
220
50
160
130
10
210
Ui
0
2
3
0
5
Vj
Производим следующее улучшение
плана перевозок и расставляем новые оценки потенциалов:
0
13 –13
4 –2
13 –9
2 –2
5 100
100
1
1 30
15 –12
5 100
6 –5
7 –1
130
0
15 –15
6 –4
4 30
5 –5
5 110
140
4
4 20
6 160
13 –6
4 10
11 –2
220
50
160
130
10
210
Ui
0
2
4
0
5
Vj
Полученный план перевозок
оптимален, так как не содержит положительных оценок потенциалов.
Стоимость оптимального плана
перевозок: С=1*30+4*20+6*160+5*100+4*30+4*10+5*100+5*110=2780.
а)
Решить задачу о назначениях с помощью венгерского алгоритма на минимум.
б) Решить задачу коммивояжера
методом ветвей и границ.
4
1
5
3
4
2
26
14
3
15
15
12
12
23
5
23
20
9
16
19
4
25
23
11
22
17
5
19
15
15
22
15
3
9
9
14
РЕШЕНИЕ
а) Решить
задачу о назначениях с помощью венгерского алгоритма на минимум.
4
1
5
3
4
2
26
14
3
15
15
12
12
23
5
23
20
9
16
19
4
25
23
11
22
17
5
19
15
15
22
15
3
9
9
14
Ведём решение по стандартной
процедуре венгерского алгоритма: приводим матрицу к «нулевому» виду, а затем
будем помечать нули, строки и столбцы, а также вычёркивать строки и столбцы с
целью изменения элементов, стоящих в них, до тех пор пока во всех строках и
столбцах не будет хотя бы по одному нулю.
di
4
1
5
3
4
2
1
26
14
3
15
15
12
3
12
23
5
23
20
9
5
16
19
4
25
23
11
4
22
17
5
19
15
15
5
22
15
3
9
9
14
3
3
0
4
2
3
1
23
11
0
12
12
9
7
18
0
18
15
4
12
15
0
21
19
7
17
12
0
14
10
10
19
12
0
6
6
11
dj
3
0
0
2
3
1
0
0
4
0
0
0
V
20
11
0
10
9
8
V
4
18
0
16
12
3
V
9
15
0
19
16
6
V
14
12
0
12
7
9
V
16
12
0
4
3
10
V
0
0
7
0
0
0
V
17
8
0
7
6
5
1
15
0
13
9
0
V
6
12
0
16
13
3
V
11
9
0
9
4
6
13
9
0
1
0
7
V
0
0
10
0
0
0
V
14
5
0
4
3
2
1
15
3
13
9
0
V
3
9
0
13
10
0
V
8
6
0
6
1
3
13
9
0
1
0
7
V
V
0
0
10
0
0
0
V
13
4
0
3
2
2
0
14
4
12
8
0
2
8
0
12
9
0
V
7
5
0
5
0
3
V
13
9
4
1
0
8
V
V
0
0
12
0
1
1
12
3
0
2
2
1
0
14
4
12
9
0
2
8
1
12
10
0
7
4
0
4
0
2
13
8
4
0
0
7
Теперь во всех строках и столбцах
имеются нули, следовательно, данная система назначений оптимальна. Получили
оптимальную систему назначений с наименьшей суммарной стоимостью 51 единица.
б) Решить задачу коммивояжера
методом ветвей и границ.
-
1
5
3
4
2
26
-
3
15
15
12
12
23
-
23
20
9
16
19
4
-
23
11
22
17
5
19
-
15
22
15
3
9
9
-
Осуществим
приведение матрицы по строкам, определив минимальное значение в каждой строке (ui)
Города
1
2
3
4
5
6
ui
1
-
1
5
3
4
2
1
2
26
-
3
15
15
12
3
3
12
23
-
23
20
9
9
4
16
19
4
-
23
11
4
5
22
17
5
19
-
15
5
6
22
15
3
9
9
-
3
Вычтем минимальные элементы из соответствующих
строк и определим сумму минимальных значений
Города
1
2
3
4
5
6
1
-
0
4
2
3
1
2
23
-
0
12
12
9
3
3
14
-
14
11
0
4
12
15
0
-
19
7
5
17
12
0
14
-
10
6
19
12
0
6
6
-
Осуществим приведение матрицы по
столбцам, определив минимальное значение в каждом столбце (vj)
Города
1
2
3
4
5
6
1
-
0
4
2
3
1
2
23
-
0
12
12
9
3
3
14
-
14
11
0
4
12
15
0
-
19
7
5
17
12
0
14
-
10
6
19
12
0
6
6
-
vj
3
0
0
2
3
0
Вычтем минимальные элементы из
соответствующих столбцов и определим сумму минимальных значений
Города
1
2
3
4
5
6
1
-
0
4
0
0
1
2
20
-
0
10
9
9
3
0
14
-
12
8
0
4
9
15
0
-
16
7
5
14
12
0
12
-
10
6
16
12
0
4
3
-
.
Константа приведения:
Найдём степени нулей для приведённой матрицы. Для этого
выберем минимальные элементы в строке и столбце, где расположен нуль, и
просуммируем их.
Города
1
2
3
4
5
6
1
-
012
4
04
03
1
2
20
-
09
10
9
9
3
09
14
-
12
8
01
4
9
15
09
-
16
7
5
14
12
010
12
-
10
6
16
12
03
4
3
-
Наибольшая степень
нулевого элемента равна двенадцати и соответствует связи (1,2). Разобьём
множество гамильтоновых контуров на два подмножества и .
Матрицу множества получаем вычёркиванием
первой строки и второго столбца приведённой матрицы. Элемент (2,1) заменим на
бесконечность.
Города
1
3
4
5
6
2
-
0
10
9
9
3
0
-
12
8
0
4
9
0
-
16
7
5
14
0
12
-
10
6
16
0
4
3
-
Осуществим приведение полученной матрицы по 4 и 5 столбцам и
определим нижнюю грань множества: .
Матрицу множества получим путём замены
элемента (1,2) на бесконечность.
Города
1
2
3
4
5
6
1
-
-
4
0
0
1
2
20
-
0
10
9
9
3
0
14
-
12
8
0
4
9
15
0
-
16
7
5
14
12
0
12
-
10
6
16
12
0
4
3
-
Осуществим приведение полученной матрицы по 2 столбцу и
определим нижнюю грань множества:
Будем отображать проделанные действия на дереве ветвления
(рис. в конце).
Для дальнейшего исследования выбираем множество , так как ему соответствует меньшая нижняя граница: Множество подвергаем дальнейшему
ветвлению.
Находим степени нулей матрицы множества .
Города
1
3
4
5
6
2
-
06
6
6
9
3
09
-
8
5
07
4
9
07
-
13
7
5
14
08
8
-
10
6
16
00
06
05
-
Ячейка (3,1) содержит наибольшую степень нуля. Разобьём
множество на два подмножества и . Матрицу подмножества получаем из матрицы
множества вычёркиванием в
последней третьей строки и первого столбца. Кроме того, дуги (1,2) и (3,1),
введённые в маршрут, могут породить изолированный контур, поэтому в клетку
(2,3) поместим бесконечность.
Города
3
4
5
6
2
-
6
6
9
4
0
-
13
7
5
0
8
-
10
6
0
0
0
-
Приведём матрицу по шестому столбцу (минимальное значение
равно 7).
Нижняя грань множества:
Матрицу множества получаем из матрицы
множества заменой значения
элемента (3,1) на бесконечность.
Города
1
3
4
5
6
2
-
0
10
9
9
3
-
-
12
8
0
4
9
0
-
16
7
5
14
0
12
-
10
6
16
0
4
3
-
Приведём матрицу по первому столбцу (минимальное значение
равно 9).
Нижняя грань множества:
Так как то дальнейшему ветвлению подвергнем множество .
Определим степени нулей матрицы множества .
Города
3
4
5
6
2
-
6
6
2
4
00
-
13
02
5
03
8
-
3
6
00
06
06
-
Теперь имеется два
варианта ветвления, так как два элемента имеют наибольшие и одинаковые степени
нуля.
Рассмотрим их по отдельности.
Матрицу получаем из матрицы
множества вычёркиванием шестой
строки и четвёртого столбца и заменой элемента (4,6) на бесконечность.
Матрицу получаем из матрицы
множества вычёркиванием шестой
строки и четвёртого столбца и заменой элемента (5,6) на бесконечность.
Матрицу получаем из матрицы
множества заменой элемента (6,4)
на бесконечность.
Матрицу получаем из матрицы
множества заменой элемента (6,5)
на бесконечность.
Как показывают расчёты, матрицы , и одинаково увеличивают
нижнюю грань множества – на 6 единиц, а матрица – на 8 единиц. Каждая из матриц , и также потом даёт неединственные равные по увеличению нижней
грани ветвления. Однако в конечном итоге (вычисления здесь не приводятся в силу
громоздкости) наилучший (оптимальный) вариант даёт ветвление матрицы
Города
3
4
6
2
-
0
2
4
0
-
0
5
0
2
3
Нижняя грань множества:
Определим степени нулей матрицы множества
Города
3
4
6
2
-
04
2
4
00
-
02
5
02
2
-
Далее ветвление будем производить по элементу, имеющему
наибольшую степень нуля – это элемент (2,4).
Матрица множества получается вычёркиванием второй строки и четвёртого столбца и
удалении изолированного контура заменой элемента (4,3) на бесконечность.
Города
3
6
4
-
0
5
0
-
В данной матрице все строки и столбцы содержат нулевые
элементы, поэтому нижняя грань множества остаётся равной 53. .
Матрица множества получается заменой элемента (2,4) на бесконечность.
Города
3
4
6
2
-
-
2
4
00
-
02
5
02
2
-
Приведём матрицу по второму столбцу (минимальное значение
равно 2). В этом случае нижняя грань множества увеличится по сравнению с.
Окончательно назначаем в матрице перемещения (4,6) и
(5,3).
Таким образом, в полученный гамильтонов контур Г входят
связи (1,2), (3,1), (6,4), (2,4), (4,6), (5,3). После их упорядочивания
получаем маршрут: 1 – 2 – 4 – 6 – 5 – 3 – 1. Длина гамильтонова контура: L=1+15+11+9+5+12=53 км.
Так как нижняя граница оборванных множеств больше
полученного значения, следовательно, найденный контур даёт оптимальное решение.