Выбор оптимальной схемы доставки грузов. Метод северо-западного угла. План двойного предпочтения. Метод Фогеля, страница 2

План вырожденный. Для устранения вырожденности в матрицу вводится условно занятая клетка с нулевым значением массы перевозок. Эта клетка считается базисной.  Х_1;2 = 0 ; Х_2;4 = 0

3 + 5 – 1 = 7

Определяем функцию цели:

F = 60*21+90*51+20*12+70*9+120*17+110*100 = 19760 т.руб.

1.3. Метод двойного предпочтения

Алгоритм решения методом двойного предпочтения:

1.  Составляется исходная матрица;

2.  В каждой строчке находим минимальный элемент транспортной ставки и помечаем звездочкой;

3.  В каждой столбце находим минимальный элемент транспортной ставки и помечаем звездочкой;

4.  Заполнение матрицы начинается с клетки помеченной двумя звездочками, одной звездочкой, без звездочек по принципу минимума:

X_{i j} = min {A_i ; B_j }

5.  План проверяется на невырождаемость

Б.к. = m + n -1

6. План проверяется на ограничения;

7. Определяется функция цели:

Таблица 3     (Метод двойного предпочтения)

Пункт отправ-ления	Gi	Пункт назначения
		B1		B2		B3		B4		BФ
		Gj
		60		110		70		120		110
A1	150	-	* 21	51				120	**	30	*
							27		10		100
A2	210	-		110	**	70		-		30
			47		12		9		17		100
A3	110	60	**	-		-		* 12		50
			14		15		19				100

Заполняем матрицу:

2.3 Х_2.3 = min {210; 70} = 70 т.т

1.4 Х_1.4 = min {150; 120} = 120 т.т

2.2 Х_2.2 = min {210-70; 110} = 110 т.т

3.1 Х_3.1 = min {110; 60} = 60 т.т

3.5 Х_3.5 = min {110-60; 110} = 50 т.т

1.5 Х_1.5 = min {150-120; 110-50} = 30 т.т

2.5 Х_2.5 = min {210-110-70; 110-50-30} = 30 т.т

Проверяем план на невырожденность:

3 + 5 – 1 = 7 -  план не вырожденный.

Определяем функцию цели:

F = 60*14+110*12+120*10+70*9+30*100*2+50*100=14990 т.руб.

1.4.  Метод Фогеля

Алгоритм решения методом Фогеля:

1.  Составляется исходная матрица;

2.  Составляется начальный план методом аппроксимации Фогеля. По каждой строке и каждому столбцу матрицы находится разность между двумя наименьшими элемент транспортной ставки. Эти разности записываются в специальные "поля" разностей по строкам и столбцам, которые достраиваются к исходной матрице справа и снизу. Затем из всех полученных разностей выбирается наибольшее значение. Если это наибольшее значение разностей получилось в столбце, то для анализа выбирается этот столбец, в котором загружается клетка с наименьшим значением транспортной ставки и исходя из минимума:

X_{i j} = min {A_i ; B_j }

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