–PAGE_BREAK–3-я итерация
cj
p0
x0
x1
х2
х3
х4
х5
х6
х7
0
х4
0.6
0.0
0.0
0.0
1.0
-0.1
-0.6
0.4
8
х1
26.3
1.0
0.0
0.0
0.0
-0.2
-0.3
0.4
15
х2
24.3
0.0
1.0
0.0
0.0
0.1
-0.3
0.0
10
х3
3.6
0.0
0.0
1.0
0.0
-0.1
0.4
-0.6
Zj — Cj
537.2
0.0
0.0
0.0
0.0
-1.7
-1.2
-1.9
Подставив значения неизвестных в исходные неравенства, получаем:
1 * 26,3 + 1 * 24,3 + 0 * 3,6 ? 50
4 * 26,3 + 1 * 24,3 + 3 * 3,6 ? 140
1 * 26,3 + 4 * 24,3 + 1 * 3,6 ? 127
0 * 26,3 + 3 * 24,3 + 2 * 3,6 ? 80
Стоимость сырья при этом будет минимальной и составит:
F= 8 * 26,3 + 12 * 24,3 + 12 * 3,6 = 537,2
ЗАДАЧА 3
Составить оптимальный план перевозок пищевых продуктов от 4-х поставщиков к 6-ти потребителям. Поставщики (П), потребители (М), объемы вывоза и завоза, кратчайшие расстояния между пунктами вывоза и завоз приведены в таблице.
Поставщики
Потребители
Объемы вывоза, т
М1
М2
М3
М4
М5
М6
П1
24
30
42
15
39
21
144
П2
9
24
30
33
27
29
148
П3
24
22
20
45
21
23
76
П4
11
36
27
40
30
8
132
Объемы завоза, т
92
84
80
112
96
36
Решение задачи начинается с распределения у имеющихся у поставщиков объемов вывоза между потребителями с учетом объемов завоза. Для первоначального распределения используются способы: северо-западного угла, наименьшего элемента по строке, наименьшего элемента по столбцу, наименьшего элемента матрицы.
Способ северо-западного угла состоит в том, что распределение объемов вывоза производится, начиная с верхнего левого угла таблицы и кончая нижним углом ее. Результаты распределения показаны в таблице.
Поставщики и объемы вывоза, т
Потребители и объемы завоза
Потенциалы строк
М1
М2
М3
М4
М5
М6
92
84
80
112
96
36
П1
144
24
30
42
15
39
21
0
92
52
П2
148
9
24
30
33
27
29
-6
32
80
36
П3
76
24
22
20
45
21
23
6
76
0
П4
132
11
36
27
40
30
8
15
96
36
Потенциалы столбцов
24
30
36
39
15
-7
Проверка плана на оптимальность. Когда исходный план получен и рассчитана соответствующая ему суммарная тонно-километровая работа, определяют, является ли этот план оптимальным. Для проверки плана на оптимальность применяется метод потенциалов.
Сущность метода потенциалов состоит в том, что для каждой строки и каждого столбца таблицы (матрицы) определяют специальные числа, называемые потенциалами. С помощью этих потенциалов можно установить, нужно ли заполнять свободную клетку матрицы или ее нужно оставить незаполненной.
Для решения задач методом потенциалов исходный план должен иметь количество заполненных клеток m + n – 1 (m — число строк, n — число столбцов). Если план не отвечает этим требованиям, то не для всех строк и столбцов можно рассчитать потенциалы, а без них нельзя проверить план на оптимальность.
Потенциалы строк и столбцов определяются по заполненным клеткам, находящимся на их пересечении.
Элемент заполненной клетки должен равняться сумме потенциалов строки и столбца, на пересечении которых находится эта заполненная клетка.
Для начала вычислений первый потенциал для строки или столбца принимается условно равным нулю, все остальные потенциалы определяются с помощью элементов заполненных клеток.
Обозначив потенциалы строк ui, потенциалы столбцов Vj, элементы заполнения клеток , можно записать порядок расчета потенциалов для общего случая.
Из основного требования = ui+ Vj вытекает:
ui = – Vj; Vj = – ui
Из этих выражений видно, что для расчета потенциала строки необходимо иметь заполненную клетку, в столбце которой потенциал уже определен, а для расчета потенциала столбца нужна заполненная клетка, имеющая потенциал в строке.
Потенциалы показаны в таблице.
После того, как по строкам и столбцам определены потенциалы, с их помощью выясняется, является ли план оптимальным, и если нет, то как его можно улучшить. С этой целью для каждой свободной клетки вычисляется сумма потенциалов строк и столбцов, на пересечении которых находится эта клетка.
Сравнение суммы потенциалов с величиной элемента в свободных клетках позволяет определить, нужно ли заполнять эту клетку или ее нужно оставить свободной.
При решении задач на минимум функционала (в нашем случае на минимум тонно-километровой работы) не заполняются те свободные клетки, в которых сумма потенциалов меньше величины элемента (в нашем случае — расстояния).
Иными словами, если характеристика, значение которой равно разности – (ui+ Vj), положительная, то свободная метка не заполняется при решении задачи на минимум функции.
Свободные клетки, имеющие нулевое значение характеристики, показывают на то, что их заполнение приведет к перераспределению поставок, но объем работ (значение функционала) останется неизменным.
Суммы потенциалов, значения элементов и характеристики для незаполненных клеток приведены в таблице.
Шифры клеток
П1-М3
П1-М4
П1-М5
П1-M6
П2-М1
П2-М5
П2-М6
П3-М1
П3-М2
П3-М3
П3-М6
П4-М1
П4-М2
П4-М3
П4-М4
Суммы потенциалов
36
39
15
-7
18
9
-13
30
36
42
-1
39
45
51
54
Значение элементов
42
15
39
21
9
27
29
24
22
20
23
11
36
27
40
Характеристики
6
-24
24
28
-9
18
42
-6
-14
-22
24
-28
-9
-24
-14
В первоначальном плане шесть клеток имеют положительные характеристики, в девяти клетках характеристики отрицательные.
Так как задача решается на минимум целевой функции, то именно эти отрицательные клетки должны быть заполнены поставщиками. Но заполнение свободной клетки и связанное с ним перераспределение поставок производится не изолированно, а в связи с несколькими заполненными клетками. Эта связь выявляется путем построения замкнутых многоугольников, вершинами которых являются клетки таблицы. Одна вершина многоугольника находится в свободной клетке, а все остальные — в заполненных клетках. Многоугольник, или как его называют цепь, имеет прямые углы и четное число вершин.
В результате перераспределения в каждой вершине (клетке) цепи происходит изменение величины поставок: в одних клетках они увеличиваются, в других — уменьшаются.
Те клетки цепи, у которых поставки увеличиваются, называются положительными, а те, у которых поставки уменьшаются — отрицательными. Каждая цепь имеет одинаковое число положительных и отрицательных вершин (клеток). Положительные и отрицательные вершины чередуются. Если свободную клетку, в которую предполагается произвести запись, принять как положительную (поскольку изменение произойдет в сторону увеличения), то следующая клетка будет отрицательной, затем опять положительной, снова отрицательной, и т.д.
Из свободных клеток для заполнения выбирают обычно клетку, которая имеет наибольшую отрицательную характеристику. В нее записывают самую наименьшую величину из отрицательных вершин цепи.
+П4М1 -П1М1 +П1М2 -П2М2 +П2М4 -П3М4 +П3М5 -П4М5
Поставщики и объемы вывоза, т
Потребители и объемы завоза
Потенциалы строк
М1
М2
М3
М4
М5
М6
92
84
80
112
96
36
П1
144
24
30
42
15
39
21
0
60
84
П2
148
9
24
30
33
27
29
-6
80
68
П3
76
24
22
20
45
21
23
6
44
32
П4
132
11
36
27
40
30
8
15
32
64
36
Потенциалы столбцов
24
30
36
39
15
-7
Шифры
клеток
П1-М3
П1-М4
П1-М5
П1-М6
П2-М1
П2-М2
П2-М5
П2-М6
П3-М1
П3-М2
П3-М3
П3-М6
П4-М2
П4-М3
П4-М4
Суммы
потенциалов
36
39
15
-7
18
24
9
-13
30
36
42
-1
45
51
54
Значение
элементов
42
15
39
21
9
24
27
29
24
22
20
23
36
27
40
Характеристики
6
-24
24
28
-9
0
18
42
-6
-14
-22
24
-9
-24
-14
+П2М5 -П4М5 +П4М1 -П1М1 +П1М4 -П2М4
Поставщики и объемы вывоза, т
Потребители и объемы завоза
Потенциалы строк
М1
М2
М3
М4
М5
М6
92
84
80
112
96
36
П1
144
24
30
42
15
39
21
0
16
84
44
П2
148
9
24
30
33
27
29
18
80
68
П3
76
24
22
20
45
21
23
-22
76
П4
132
11
36
27
40
30
8
-13
76
20
36
Потенциалы столбцов
24
30
12
15
43
21
Шифры
клеток
П1-М3
П1-М5
П1-М6
П2-М1
П2-М2
П2-М5
П2-М6
П3-М1
П3-М2
П3-М3
П3-М4
П3-М6
П4-М2
П4-М3
П4-М4
Суммы
потенциалов
12
43
21
42
48
61
39
2
8
-10
-7
-1
17
-1
2
Значение
элементов
42
39
21
9
24
27
29
24
22
20
45
23
36
27
40
Характеристики
30
-4
0
-33
-24
-34
-10
22
14
30
52
24
19
28
38
+П2М5 -П4М5 +П4М1 -П1М1 +П1М4 -П2М4
Поставщики и объемы вывоза, т
Потребители и объемы завоза
Потенциалы строк
М1
М2
М3
М4
М5
М6
92
84
80
112
96
36
П1
144
24
30
42
15
39
21
0
84
60
П2
148
9
24
30
33
27
29
18
80
52
16
П3
76
24
22
20
45
21
23
12
76
П4
132
11
36
27
40
30
8
21
92
4
36
Потенциалы столбцов
-10
30
12
15
9
-13
Шифры
клеток
П1-М1
П1-М3
П1-М5
П1-М6
П2-М1
П2-М2
П2-М6
П3-М1
П3-М2
П3-М3
П3-М4
П3-М6
П4-М2
П4-М3
П4-М4
Суммы
потенциалов
-10
12
9
-13
8
30
5
2
42
24
27
-1
51
33
36
Значение
элементов
24
42
39
21
9
24
29
24
22
20
45
23
36
27
40
Характеристики
34
30
30
34
1
-6
24
22
-20
-4
18
24
-15
-6
4
+П3М2 -П1М2 +П1М4 -П2М4 +П2М5 -П3М5
Поставщики и объемы вывоза, т
Потребители и объемы завоза
Потенциалы строк
М1
М2
М3
М4
М5
М6
92
84
80
112
96
36
П1
144
24
30
42
15
39
21
0
32
112
П2
148
9
24
30
33
27
29
-2
80
68
П3
76
24
22
20
45
21
23
-8
52
24
П4
132
11
36
27
40
30
8
1
92
4
36
Потенциалы столбцов
10
30
32
15
29
7
Шифры
клеток
П1-М1
П1-М3
П1-М5
П1-М6
П2-М1
П2-М2
П2-М4
П2-М6
П3-М1
П3-М3
П3-М4
П3-М6
П4-М2
П4-М3
П4-М4
Суммы
потенциалов
10
32
29
7
8
28
13
5
2
24
7
-1
31
33
16
Значение
элементов
24
42
39
21
9
24
33
29
24
20
45
23
36
27
40
Характеристики
14
10
10
14
1
-4
20
24
22
-4
38
24
5
-6
24
продолжение
–PAGE_BREAK–