Практикум по дискретной математике в среде виртуальной лаборатории системы ДО ИТМО (стр. 10 )

220	110				0
	60		150	60	0
		210		140	0
0	0	0	0	0	b\a

С суммарной оценкой стоимости перевозок:

С= 220*10 + 110*12 + 60*22 + 210*35 + 140*63 +150*66+ 60*320 =ед.

2.7.3.  Метод потенциалов

Данный метод служит для оптимизации опорного плана. Проверка плана на оптимальность осуществляется по критерию оптимальности.

Критерий оптимальности:

Для оптимального решения транспортной задачи необходимо и достаточно, чтобы существовала система чисел Ti и Hj, удовлетворяющая условиям :

Ti + Hj = cij - для занятых клеток; ( * )
Ti + Hj cij - для свободных клеток. (**)

Здесь:

i - номер пункта поставки;

j - номер пункта потребления;

cij - стоимость перевозки из i-го пункта поставки в j-й пункт потребления;

Ti - потенциал пункта потребления;

Hj - потенциал пункта поставки.

Следствие: Если хотя бы для одной из свободных клеток сумма потенциалов превосходит соответствующую стоимость, то план не является оптимальным.

Таблица потенциалов строится в соответствии с формулой (**) и Т1=0.

T1 + H1 =10 => H1 =10

T1 + H2 =12 => H1 =12

T2 + H2 =22 => T2 =10

T2 + H3 =49 => H3 =39

T2 + H5 =32 => H5 =22

T3 + H3 =35 => T3 =-4

T3 + H4 =67 => H4 =71

	H1 =10	H2 =12	H3 =39	H4 =71	H5 =22
T1 =0	10 00	12 10	24	50	42
T2 =10	13	22 0	49 0	66	32 00
T3 =-4	25	27	35 00	67 50	63

После построения таблицы потенциалов необходимо проверить план на оптимальность по критерию оптимальности, т. е. должны выполняться условия (*) и (**). Если условия не выполняются, то необходимо построить оптимальный план, например, методом потенциалов.

Пример: Составляем цикл перераспределения перевозок следующим образом [15]: выбираем свободные клетки, для которых не выполняется условие (4) (Ti + Hj >= cij) и из этих клеток выбираем клетку с max { cij -(Ti+Hj)}. Если их несколько, то выбираем ту, у которой меньше cij.

Из выбранной клетки прошагаем "шахматной ладьей" по занятым клеткам так, чтобы вновь вернуться в исходную клетку, причем, после каждого шага надо поворачивать с горизонтали на вертикаль и наоборот. Исходная клетка помечается знаком "+". Потом знак клеток будет чередоваться. Вот результат таблицы потенциалов для нашего примера:

	H1=10	Н2=12	Н3=39	Н4=71	Н5=22
Т1=0	10 200	- 12 110	24	+ 50	42
Т2=10	13	+ 22 60	- 49 10	65	32 200
Т3=-4	25	27	+ 35 200	- 67 150	63

Среди вершин с отрицательным знаком выберем клетку с наименьшей по величине перевозкой. В примере это клетка со стоимостью с23 (min{110,150,10}=10).

Перераспределяем груз в выбранной клетке цикла по cледующему правилу: в клетках цикла имеющих знак "+" прибавляем тот груз, который находится в выбранной клетке (т. е. 10 тонн), а в клетках, имеющих знак "-" вычитаем этот груз.

После этого перераспределения строим новую таблицу потенциалов. Проверяем по критерию оптимальности вновь построенную таблицу потенциалов. Если план удовлетворяет критерию, то план оптимален, иначе приступаем вновь к выполнению описанной процедуры.

В результате вычислений получился следующий оптимальный план:

10 150	12 30	24	50 150	42
13 70	22	49	65	32 200
25	27 140	35 210	67	63

2.8.  Тема № 8 «Задача линейного назначения»

2.8.1. Венгерский алгоритм

Данный метод основан на построении системы независимых нулей и состоит из предварительного этапа и не более (n-2) последовательно повторяющихся итераций.

Систему нулевых элементов матрицы, обладающую тем свойством, что никакая пара из них не лежит одновременно в одной строке или одном столбце, называют системой независимых нулей.

Как только число независимых нулей становится равным n, задача назначения считается решенной: оптимальный план определяется местоположением независимых нулей в последней из матриц.

Шаги алгоритма:

1)  Произведем предварительные расчеты:

a)  В матрице Сn*n находим максимальный элемент dj:
dj = max{cij}, для всех j=1,2, ... ,n.

b)  Формируем новую матрицу С'n*n, где с'ij = dj - cij ³0; a dj = max { cij } для всех i=1,..., n. Эта матрица имеет в каждом столбце по крайней мере один нуль. При этом преобразовании за счет изменения знака элементов матрицы эффективности переходим к задаче минимизации целевой функции, оптимальный план которой совпадает с исходной задачей максимизации.

c)  Создаем матрицу C0n*n, где с0ij = cij - ti = - cij + dj - ti, a ti = min {cij} для всех j=1,...,n.

d)  Образуем первоначальную систему независимых нулей. Для этого отыскиваем и помечаем звездочкой произвольный нуль в первом столбце матрице С0. Просматриваем элементы второго столбца, и если обнаруживаем нуль, не лежащий в одной строке с ранее отмеченным нулем, то его тоже помечаем звездочкой. Такие операции осуществляем для всех последующих столбцов матрицы. Полученная система помеченных звездочкой нулей является исходной для дальнейшего решения.

2)  Подсчитываем число (k) независимых нулей полученной матрицы. Если k=n, то решение получено, в противном случае - переходим к следующему этапу.

3)  Столбцы, содержащие нуль со звездочкой(0*), выделим знаком плюс.

4)  Проверяем, есть ли среди невыделенных столбцов матрицы хотя бы один нуль. Если да, то переходим к п. 5, в противном случае - к п. 6.

5)  Проверяем, содержит ли строка с невыделенным нулем также и 0*. Если да, то переходим к п. 7, в противном случае - к п. 8.

6)  Формируем новые невыделенные нули. Для этого среди невыделенных элементов матрицы Сk выбираем минимальный и вычитаем его из элементов, расположенных в невыделенных строках, и прибавляем к элементам, лежащим в выделенных столбцах. Получаемая матрица Сk' является эквивалентом матрицы Сk. Переходим к п. 5.

7)  Найденный невыделенный нуль отмечаем штрихом (0'), а содержащую этот нуль строку - знаком "+". Снимаем знак выделения "+" над столбцом, в котором расположен 0*, лежащий в только что выделенной строке. Переходим к п. 4.

8)  Невыделенный нуль отмечаем штрихом.

9)  Подготавливаем информацию для оценки возможности увеличения числа независимых нулей (0*) в матрице эффективности. Для этого, начиная с 0', в одной строке с которым нет 0*, осуществляем построение цепочки элементов матрицы Сk по следующему правилу: выбираем исходный 0', в цепочку включаем 0*, лежащий с 0' в одном столбце (если такой найдется). К нему прибавляем опять 0', лежащий в одной строке с предшествующим 0* и т. д. Построение цепочки по правилу осуществляется однозначно. Число нулей в такой цепочке всегда нечетно, причем 0' находятся на нечетных местах, а 0* - на четных. Может случиться, что в одном столбце с исходным 0' нет 0*. Тогда цепочка нулей получается вырожденной и состоит из одного исходного элемента.

10)  Меняем знаки у нулей в построенной цепочке, причем звездочки у нулей уничтожаем, а штрихи заменяем на звездочки. Так как такая цепочка обязательно должна заканчиваться 0', а число элементов в ней нечетно, то при замене 0' на 0* происходит увеличение числа последних на единицу. Возвращаемся к п.2.

Пример: Исходная матрица эффективности С для n=4 [15]:

3	5	7	11
1	4	6	3
5	8	12	7
1	4	3	4

Определяем максимальный элемент в каждом из столбцов матрицы С:

5

8

12

11

Преобразуем матрицу С в матрицу С ' согласно п.1,б) и затем определяем минимальные элементы в каждой строке полученной матрицы:

2	3	5	0		0
4	4	6	8		4
0	0	0	4		0
4	4	9	7		4

Преобразуем матрицу С ' в матрицу С0 согласно п.1,в) и строим по ней первоначальную систему независимых нулей согласно п 1,г) :

2	3	5	0*
0*	0	2	4
0	0*	0	4
0	0	5	3

Подсчитываем число (k) полученных независимых нулей в матрице С0.

Так как k=3< n, то переходим к коррекции полученного решения.

Выделим «+» столбцы, содержащие 0*:

+	+		+
2	3	5	0*
0*	0	2	4
0	0*	0	4
0	0	5	3

Не выделен столбец с номером j=3. В этом столбце существует невыделенный нуль. Переходим к п.5 алгоритма. Строка с невыделенным нулем содержит также и 0*. Переходим к п.7 алгоритма. Отмечаем невыделенный нуль штрихом. Снимаем знак выделения над вторым столбцом (j=2). Выделяем 3-ю строку знаком плюс. Возвращаемся к п.4 алгоритма.