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

Далее процесс повторяется, исключая те строки и столбцы, ресурсы которых исчерпаны. Указанные выше вычисления продолжаются до получения допустимого плана.

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

Б.к. = m + n -1

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

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

Таблица 4       (Метод Фогеля)

Пункт отправ-ления	Gi	Пункт назначения										Поле разности по строкам
		B1		B2		B3		B4		Bф
		Gj
		90		110		120		105		45
А1	150							120		30		11	6	30	79	100
			21		51	27			10		100
А2	210			110		70				30		3	3	53	100	100
			47		12		9		17		100
А3	110	60								50		2	1	1	86	100
			14		15		19		12		100
Поле разности по столбцам		7		3		10		2		0
		7		3		10		-		0
		7		3		-		-		0
		7		-		-		-		0
		-		-		-		-		0

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

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

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

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

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

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

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

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

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

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

7 = 3 + 5 – 1

План невырожденный.

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

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

Вывод: после составления трех планов разными методами и сравнения функций целей выяснил, что по методу Фогеля функция цели получила меньшее значение.

1.5. Проверка плана на оптимальность методом потенциалов

План считается оптимальным, если выполняется условие для базисных клеток

α_i + β_j = C_ij

для свободных клеток

α_i + β_j ≤ C_ij

где   α_i + β_j  - соответственно потенциалы строк и столбцов.

Принимаем α₁=0.

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

1.  В первоначальный допустимый план водятся дополнительные строки и столбцы;

2.  Рассчитываются потэнцыалы строк и столбцов из условия

α_i + β_j = C_ij

3.  рассчитывается потенциал свободных клеток из условия

α_i + β_j ≤ C_ij

4.  Если условие не выполняется то строится контур переноса ресурсов;