Шурко Введение в системный анализ
.pdf21
2.МЕТОД МИНИМАЛЬНОГО ЭЛЕМЕНТА (МИНИМАЛЬНОГО ТАРИФА)
Объемы про- |
|
|
Запросы потребителей |
|
|
|||
изводства |
41 |
49 |
53 |
57 |
||||
|
|
30 |
|
24 |
|
20 |
|
22 |
63 |
41 |
|
7 |
|
|
|
15 |
|
|
|
12 |
|
14 |
|
8 |
|
10 |
95 |
|
|
|
|
53 |
|
42 |
|
|
|
16 |
|
15 |
|
16 |
|
17 |
42 |
|
|
42 |
|
|
|
|
|
Таблицу заполняют по возрастанию стоимости перевозок. Этот метод позволяет получить достаточно экономичный план, сокращая количество последующих итераций по его оптимизации.
Так как в обоих случаях
m+n-1=3 + 4 - 1 = 6,
то полученные планы невырождены.
Наиболее распространенным методом решения транспортных задач является метод потенциалов.
Состоит он в следующем:
Вводятся потенциалы ui и vj -оценки единицы продукта в каждом пункте потребления и производства.
По заполненным (базисным) клеткам составляется система уравнений ui + vj = cij
В нашей задаче
u1 + v1 = 30 u1 + v2 = 24 u1 + v4 = 22 u2 + v3 = 8 u2 + v4 = 10 u3 + v2 = 15.
22
Поскольку потенциалы определяются с точностью до постоянного слагаемого, один из них можно выбрать произвольно. Это соответствует выбору начала отсчета. Полагаем u1 = 0 и находим остальные потенциалы
v1 = 30
v2 = 24
v3 = 14
v4 = 22
u2 = -12
u3 = -9.
Проверяется выполнение условий оптимальности для небазисных клеток
ij = ui + vj - cij 0
(для базисных клеток ij =0).
13 = u1 + v3 - c13 = 0 + 20 - 20 = 0
21 = u2 + v1 - c21 = -12 + 30 + 12 = 6 0
22 = u2 + v2 - c22 = -12 + 24 - 14 = -2 0
31 = u3 + v1 - c31 = -9 + 30 - 16 = 5 0
33 = u3 + v3 - c33 = -9 + 20 - 16 = -5 0
34 = u3 + v4 - c34 = -9 + 22 - 17 = -4 0
Так как среди полученных оценок имеются положительные, то полученный план неоптимален. Для того, чтобы его улучшить, введем в него перевозку в объеме между вторым предприятием и первым потребителем (т.к. именно оценка 21 = 6 - положительная ).
Введение дополнительной перевозки нарушает сбалансированность плана,
поэтому приходится изменить объемы перевозок и между некоторыми другими пунктами. В результате этих изменений получаем такой сбалансированный план:
23
Объемы |
|
|
Запросы потребителей |
|
|
||||
про-ва |
41 |
49 |
53 |
|
57 |
||||
|
|
|
|
|
|
|
|
|
|
|
|
30 |
|
24 |
|
20 |
|
|
22 |
|
|
|
|
|
|
|
|
|
|
63 |
41- |
|
7 |
|
|
|
|
15 + |
|
|
|
|
|
|
|
|
|
|
|
|
|
12 |
|
14 |
|
8 |
|
|
10 |
|
|
|
|
|
|
|
|
|
|
95 |
|
|
|
|
53 |
|
|
42 - |
|
|
|
|
|
|
|
|
|
|
|
|
|
16 |
|
15 |
|
16 |
|
|
17 |
|
|
|
|
|
|
|
|
|
|
42 |
|
|
42 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Величину выгоднее выбирать как можно большей, но при этом объемы перевозок не могут быть отрицательными. (Если посчитать затраты L2 по реализации нового плана, то L2 = L1 - 6 * = L2 - 21 * ).
Отсюда следует, что = 41.
При этом получаем такой новый план перевозок:
Объемы |
|
|
Запросы потребителей |
|
|
|||
про-ва |
|
|
|
|
|
|
|
|
41 |
49 |
53 |
57 |
|||||
|
|
|
|
|
|
|
|
|
|
|
30 |
|
24 |
|
20 |
|
22 |
|
|
|
|
|
|
|
|
|
63 |
|
|
7 |
|
|
|
56 |
|
|
|
|
|
|
|
|
|
|
|
|
12 |
|
14 |
|
8 |
|
10 |
|
|
|
|
|
|
|
|
|
95 |
41 |
|
|
|
53 |
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
16 |
|
15 |
|
16 |
|
17 |
|
|
|
|
|
|
|
|
|
42 |
|
|
42 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
На этом закончен первый этап улучшения плана - первая итерация.
Далее выполняем вторую итерацию.
По заполненным базисным клеткам составляем систему уравнений: ui + vj = cij
24
u1 + v2 = 24 u2 + v1 = 12 u1 + v2 = 22 u2 + v4 = 10 u3 + v2 = 15 u2 + v3 = 8 u1 + v2 = 24 u1 + v4 = 22 u2 + v1 = 12 u2 + v3 = 8 u2 + v4 = 10 u3 + v2 = 15.
Пологая u1= 0, найдем остальные потенциалы: v1 = 24
v2 = 24
v3 = 20
v4 = 22
u2 = -12
u3 = -9.
Проверим выполнение условий оптимальности для небазисных клеток:
ij = ui + vj - cij 0
11 = u1 + v1 - c11 = 0 + 24 - 30 = -6 < 0
13 = u1 + v3 - c13 = 0 + 20 - 20 = 0
22 = u2 + v2 - c22 = -12 + 24 - 14 = -2 0
31 = u3 + v1 - c31 = -9 + 24 - 16 = -1 0
33 = u3 + v3 - c33 = -9 + 20 - 16 = -5 0
34 = u3 + v4 - c34 = -9 + 22 - 17 = -1 0.
25
Так как все оценки ij 0, то полученный план - оптимален.
Lmin = 7*24 + 56*22 + 41*12 + 53*8 + 1*10 + 42*15 = 168 + 1232 + 492 + +424 + 10 + 630 = 2956.
Проверка: L1 - Lmin = 6*41 = 246.
Замечание. Экономическое содержание признака оптимальности следующее:
пусть: ui - оценка единицы продукта на i-м предприятии,
|
vj - оценка единицы продукции у j-го потребителя. |
Тогда: |
vj ui + cij |
Если какая-то перевозка осуществляется, то цена в пункте потребления равна цене в пункте производства плюс затраты на транспортировку.
В любом пункте потребления оценка vj не может быть больше, чем ui + cij, так как по такой цене можно было бы получить в j - м пункте потребления продукт,
привезя его из i - го пункта производства с затратами cij.
Следовательно, всегда в оптимальном плане vj ui + cij , то есть разность цен не превышает затрат на транспортировку.