Действия над матрицами

 

Наибольшая  сумма констант приведения равна (22 + 0) = 22 для ребра (5,6), следовательно, множество разбивается на два подмножества (5,6) и (5*,6*).

Нижняя граница  гамильтоновых циклов этого подмножества:

H(5*,6*) = 49 + 22 = 71

i  j	2	3	5	6
3	13	M	5	0	0
4	M	7	0	0	0
5	41	22	M	M	22
6	0	0	0	M	0
	0	0	0	0	22

 

В результате получим  другую сокращенную матрицу (3 x 3), которая  подлежит операции приведения.

Сумма констант приведения сокращенной матрицы:

 После операции приведения сокращенная матрица будет иметь вид:

i  j	2	3	5
3	13	M	5	5
4	M	7	0	0
6	0	0	M	0
	0	0	0	5

 

Нижняя граница  подмножества (5,6) равна:

H(5,6) = 49 + 5 = 54  <  71

Чтобы исключить  подциклы, запретим следующие переходы: (4,2),

Поскольку нижняя граница этого подмножества (5,6) меньше, чем подмножества (5*,6*), то ребро (5,6) включаем в маршрут.

Шаг №4.

Определяем  ребро ветвления  и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).

i  j	2	3	5
3	8	M	0(8)	8
4	M	7	0(7)	7
6	0(8)	0(7)	M	0
	8	7	0	0

 

Наибольшая  сумма констант приведения равна (8 + 0) = 8 для ребра (3,5), следовательно, множество разбивается на два подмножества (3,5) и (3*,5*).

Нижняя граница  гамильтоновых циклов этого подмножества:

H(3*,5*) = 54 + 8 = 62

i  j	2	3	5
3	8	M	M	8
4	M	7	0	0
6	0	0	M	0
	0	0	0	8

 

В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.

Сумма констант приведения сокращенной матрицы:

После операции приведения сокращенная матрица  будет иметь вид:

	2	3
4	M	7	7
6	0	0	0
	0	0	7

 

Нижняя граница  подмножества (3,5) равна:

H(3,5) = 54 + 7 = 61  <  62

Поскольку нижняя граница этого подмножества (3,5) меньше, чем подмножества (3*,5*), то ребро (3,5) включаем в маршрут.

В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (4,3) и (6,2).

В результате по дереву ветвлений гамильтонов цикл образуют ребра:

(1,4), (4,3), (3,5), (5,6), (6,2), (2,1),

Длина маршрута равна 

 

11. Транспортная задача. Из трех холодильников A_i (i =1,3), вмещающих мороженную рыбу в количествах a_i (тонн), необходимо последнюю доставить в пять магазинов B_j (j =1,5) в количествах b_j (тонн). Стоимости перевозки 1 тонны рыбы из холодильника A_i в магазин B_j заданы в виде матрицы C=((c_ij)) (3x5). Написать математическую модель задачи и спланировать перевозки так, чтобы их общая стоимость была минимальной.

а₁ = 320, а₂ = 280, а₃ = 250,

b₁ = 150, b₂ = 140, b₃ = 110, b₄ = 230, b₅ = 220,

Решение

 

	20	23	20	15	24	320
	29	15	16	19	29	280
	6	11	10	9	8	250
	150	140	110	230	220

 

Проверим условия  задачи  на сбалансированность

150+140+110+230+220=850

320+280+250=850

Общая сумма  потребностей совпадает с суммой запасов, значит задача является закрытой. Найдем начальное решение методом  минимального элемента. Для этого составим транспортную таблицу

Найдем опорный  план методом минимального элемента. Найдем клетку с минимальной стоимостью, это клетка (3,1) Ищем min между 150 и 250. В клетку (3,1 ) поместим 150. Переходим к следующей, ищем минимальную стоимость, она равна 8.  Выберем клетку (3,5) и найдем min{220,250-150}=100. Поместим в клетку(3,5) =100. Перейдем в клетку (2,2) , в которой стоимость 15. Выберем min{110;280}=140. В клетку (2,2) поместим 140

Выбираем клетку с минимальной стоимостью равной 15, выбираем клетку (1,4) ищем min{230,320}=230. Следующая минимальная цена 3 в ячейке (3,2) ищем min{10-6;90}=4.

Следующая минимальная  цена 16 в ячейке (2,3) ищем min{110;280-140}=110. Ставим в клетку (2,3) =110. Остается, что в клетку (1,5) нужно поставить 90 и в ячейку (2,5) 30. Получили опорный план.

				230	90	320
		140	110		30	280
	150				100	250
	150	140	110	230	220

 

В результате получен  первый опорный план, который является допустимым, так как все грузы  из баз вывезены, потребность магазинов  удовлетворена, а план соответствует системе ограничений транспортной задачи.

Проверим полученный опорный план на невырожденность. Количество заполненных клеток N должно удовлетворять условию N=n+m-1 . В нашем случае N=7, n+m=3+5=8 , что удовлетворяет условию невырожденности плана.

Значение целевой  функции для этого опорного плана  равно:

Проведем поэтапное улучшение  начального решения, используя метод потенциалов.

Составим вспомогательную рабочую  матрицу затрат. Она строится из исходной матрицы издержек путем  переноса только тех ячеек P_ij которые соответствуют заполненным клеткам транспортной таблицы. Остальные ячейки остаются пустыми. 
Кроме того, введем вспомогательный столбец в который внесем значения неизвестных и вспомогательную строку в которую внесем значения неизвестных Эти n+m неизвестных должны для всех (i,j), соответствующих загруженным клеткам, удовлетворять линейной системе уравнений . Пусть тогда

				230	90	320
		140	110		30	280
	150				100	250
	150	140	110	230	220

Для свободных клеток определим  значения оценок (разность между прямыми  и косвенными тарифами)

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

			230	90
	140	110		30
150				100

 

получим план

90			230
	140	110		30
60				190

 

Для свободных клеток определим  значения оценок (разность между прямыми  и косвенными тарифами)

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

90			230
	140	110		30
60				190

 

получим план

120			200
	140	110	30
30				220

 

. проверим полученный план на  оптимальность.

Для свободных клеток определим  значения оценок (разность между прямыми  и косвенными тарифами)