Метод Фогеля

Читайте также:

1. Используя метод Фогеля, построим первый опорный план транспортной задачи. Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строе или столбце, и поместим их в соответствующем дополнительном столбце или строке.

Данный метод состоит в следующем:

1. на каждой итерации находят разности между двумя наименьшими тарифами во всех строках и столбцах, записывая их в дополнительные столбец и строку таблицы;

2. находят максимальную разность и заполняют клетку с минимальной стоимостью в строке (столбце), которой соответствует данная разность.

Находим разности по строкам.

Для строки N=1 первый минимальный элемент min¹₁ = 13, второй минимальный элемент min²₁ = 21. Их разность равна d = min²₁ - min¹₁ = 8.

Для строки N=2 первый минимальный элемент min¹₂ = 22, второй минимальный элемент min²₂ = 25. Их разность равна d = min²₂ - min¹₂ = 3.

Для строки N=3 первый минимальный элемент min¹₃ = 12, второй минимальный элемент min²₃ = 26. Их разность равна d = min²₃ - min¹₃ = 14.

Для строки N=4 первый минимальный элемент min¹₄ = 17, второй минимальный элемент min²₄ = 29. Их разность равна d = min²₄ - min¹₄ = 12.

Для строки N=5 первый минимальный элемент min¹₅ = 16, второй минимальный элемент min²₅ = 21. Их разность равна d = min²₅ - min¹₅ = 5.

Для строки N=6 первый минимальный элемент min¹₆ = 0, второй минимальный элемент min²₆ = 0. Их разность равна d = min²₆ - min¹₆ = 0.

Находим разности по столбцам.

Для столбца N=1 первый минимальный элемент min¹₁ = 13. второй минимальный элемент min²₁ 17. Их разность d = min²₁ - min¹₁ = 4.

Для столбца N=2 первый минимальный элемент min¹₂ = 21. второй минимальный элемент min²₂ 25. Их разность d = min²₂ - min¹₂ = 4.

Для столбца N=3 первый минимальный элемент min¹₃ = 12. второй минимальный элемент min²₃ 21. Их разность d = min²₃ - min¹₃ = 9.

Для столбца N=4 первый минимальный элемент min¹₄ = 24. второй минимальный элемент min²₄ 26. Их разность d = min²₄ - min¹₄ = 2.

Для столбца N=5 первый минимальный элемент min¹₅ = 16. второй минимальный элемент min²₅ 25. Их разность d = min²₅ - min¹₅ = 9.

Вычислив все эти разности, видим, что наибольшая из них соответствует строке (3). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (3) и столбца (3).

	Запасы	Разности по строкам






Потребности
Разности по столбцам

Искомый элемент равен 12

Для этого элемента запасы равны 22, потребности 41. Поскольку минимальным является 22, то вычитаем его.

x₃₃ = min(22,41) = 22.


			x
x	x		x	x	22 - 22 = 0
	x	x	x	x	x
			x
			x
		41 - 22 = 19	x

Находим разности по строкам.

Находим разности по столбцам.

Для столбца N=3 первый минимальный элемент min¹₃ = 21. второй минимальный элемент min²₃ 37. Их разность d = min²₃ - min¹₃ = 16.

Для столбца N=4 первый минимальный элемент min¹₄ = 24. второй минимальный элемент min²₄ 29. Их разность d = min²₄ - min¹₄ = 5.

Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу (3). В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки (1) и столбца (3).

	Запасы	Разности по строкам


		-



Потребности
Разности по столбцам

Искомый элемент равен 21

Для этого элемента запасы равны 21, потребности 19. Поскольку минимальным является 19, то вычитаем его.

x₁₃ = min(21,19) = 19.

				21 - 19 = 2
x	x	x	x	x
		x
	x	x
	x	x
		x
	19 - 19 = 0	x

Находим разности по строкам.

Для строки N=5 первый минимальный элемент min¹₅ = 16, второй минимальный элемент min²₅ = 24. Их разность равна d = min²₅ - min¹₅ = 8.

Находим разности по столбцам.

Вычислив все эти разности, видим, что наибольшая из них соответствует строке (4). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (4) и столбца (1).

		Запасы	Разности по строкам


			-



Потребности
Разности по столбцам	-

Искомый элемент равен 17

Для этого элемента запасы равны 15, потребности 36. Поскольку минимальным является 15, то вычитаем его.

x₄₁ = min(15,36) = 15.


	x
	x
	x		x	x	15 - 15 = 0
	x	x	x	x	x
	x
36 - 15 = 21	x

Находим разности по строкам.

Находим разности по столбцам.

Для столбца N=1 первый минимальный элемент min¹₁ = 13. второй минимальный элемент min²₁ 22. Их разность d = min²₁ - min¹₁ = 9.

Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу

(5). В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки (5) и столбца (5).

		Запасы	Разности по строкам


			-
			-


Потребности
Разности по столбцам	-

Искомый элемент равен 16

Для этого элемента запасы равны 8, потребности 17. Поскольку минимальным является 8, то вычитаем его.

x₅₅ = min(8,17) = 8.


					x
					x
					x
x	x		x		8 - 8 = 0
	x	x	x	x	x
				17 - 8 = 9	x

Находим разности по строкам.

Находим разности по столбцам.

Для столбца N=4 первый минимальный элемент min¹₄ = 29. второй минимальный элемент min²₄ 53. Их разность d = min²₄ - min¹₄ = 24.

Для столбца N=5 первый минимальный элемент min¹₅ = 25. второй минимальный элемент min²₅ 51. Их разность d = min²₅ - min¹₅ = 26.

Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу (5). В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки (2) и столбца (5).

		Запасы	Разности по строкам


			-
			-
			-

Потребности
Разности по столбцам	-

Искомый элемент равен 25

Для этого элемента запасы равны 46, потребности 9. Поскольку минимальным является 9, то вычитаем его.

x₂₅ = min(46,9) = 9.

			x
				46 - 9 = 37
x	x	x	x	x
				x
				x
				x
			9 - 9 = 0	x

Находим разности по строкам.

Находим разности по столбцам.

Вычислив все эти разности, видим, что наибольшая из них соответствует столбцу (4). В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки (2) и столбца (4).

			Запасы	Разности по строкам


				-
				-
				-

Потребности
Разности по столбцам	-	-

Искомый элемент равен 29

Для этого элемента запасы равны 37, потребности 53. Поскольку минимальным является 37, то вычитаем его.

x₂₄ = min(37,53) = 37.


x	x			x	37 - 37 = 0
	x	x	x	x	x
				x
				x
				x
			53 - 37 = 16	x

Находим разности по строкам.

Находим разности по столбцам.

Для столбца N=1 первый минимальный элемент min¹₁ = 13. второй минимальный элемент min²₁ 13. Их разность d = min²₁ - min¹₁ = 0.

Для столбца N=2 первый минимальный элемент min¹₂ = 21. второй минимальный элемент min²₂ 21. Их разность d = min²₂ - min¹₂ = 0.

Для столбца N=4 первый минимальный элемент min¹₄ = 53. второй минимальный элемент min²₄ 53. Их разность d = min²₄ - min¹₄ = 0.

Вычислив все эти разности, видим, что наибольшая из них соответствует строке (1). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (1) и столбца (1).

			Запасы	Разности по строкам

				-
				-
				-
				-

Потребности
Разности по столбцам	-	-

Искомый элемент равен 13

Для этого элемента запасы равны 2, потребности 21. Поскольку минимальным является 2, то вычитаем его.

x₁₁ = min(2,21) = 2.

	x		x		2 - 2 = 0
	x	x	x	x	x
	x
	x
	x
	x
21 - 2 = 19	x

Находим разности по строкам.

Находим разности по столбцам.

Для столбца N=1 первый минимальный элемент min¹₁ = 0. второй минимальный элемент min²₁ 0. Их разность d = min²₁ - min¹₁ = 0.

Для столбца N=2 первый минимальный элемент min¹₂ = 0. второй минимальный элемент min²₂ 0. Их разность d = min²₂ - min¹₂ = 0.

Для столбца N=4 первый минимальный элемент min¹₄ = 0. второй минимальный элемент min²₄ 0. Их разность d = min²₄ - min¹₄ = 0.

Вычислив все эти разности, видим, что наибольшая из них соответствует строке (6). В этой строке минимальный тариф записан в клетке, находящейся на пересечении строки (6) и столбца (1).

			Запасы	Разности по строкам
				-
				-
				-
				-
				-

Потребности
Разности по столбцам	-	-

Искомый элемент равен 0

Для этого элемента запасы равны 68, потребности 19. Поскольку минимальным является 19, то вычитаем его.

x₆₁ = min(68,19) = 19.


	x
	x
	x
	x
	x				68 - 19 = 49
19 - 19 = 0	x	x	x	x	x

Находим разности по строкам.

Находим разности по столбцам.

				Запасы	Разности по строкам
					-
					-
					-
					-
					-

Потребности
Разности по столбцам	-	-	-

Искомый элемент равен 0

Для этого элемента запасы равны 49, потребности 33. Поскольку минимальным является 33, то вычитаем его.

x₆₂ = min(49,33) = 33.


	x
	x
	x
	x
	x			49 - 33 = 16
33 - 33 = 0	x	x	x	x

Находим разности по строкам.

Находим разности по столбцам.

					Запасы	Разности по строкам
						-
						-
						-
						-
						-

Потребности
Разности по столбцам	-	-	-	-

Искомый элемент равен 0

Для этого элемента запасы равны 16, потребности 16. Поскольку минимальным является 16, то вычитаем его.

x₆₄ = min(16,16) = 16.


			x
			x
			x
			x
			x	16 - 16 = 0
x	x	16 - 16 = 0	x	x

Матрица распределения запасов

						Запасы
	13[2]		21[19]
				29[37]	25[9]
			12[22]
	17[15]
					16[8]
	0[19]	0[33]		0[16]
Потребности

Сведем все вычисления в одну таблицу.

Запасы

d₁

d₂

d₃

d₄

d₅

d₆

d₇

d₈

13[2]

21[19]

29[37]

25[9]

12[22]

17[15]

16[8]

0[19]

0[33]

0[16]

Потребности

d₁

d₂

d₃

d₄

d₅

d₆

d₇

d₈

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

2. Подсчитаем число занятых клеток таблицы, их 10, а должно быть m + n - 1 = 10. Следовательно, опорный план является невырожденным.

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

F(x) = 13*2 + 21*19 + 29*37 + 25*9 + 12*22 + 17*15 + 16*8 + 0*19 + 0*33 + 0*16 = 2370

Сравнение значений целевой функции для опорных планов, полученных методом:

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

F(x) = 13*2 + 21*19 + 29*37 + 25*9 + 12*22 + 17*15 + 16*8 + 0*19 + 0*33 + 0*16 = 2370

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

F(x) = 13*21 + 22*15 + 25*31 + 38*2 + 12*20 + 51*15 + 21*6 + 24*2 + 0*51 + 0*17 = 2633

· Метод наименьших стоимостей: Значение целевой функции для этого опорного плана равно:

F(x) = 21*21 + 22*21 + 25*12 + 29*4 + 25*9 + 12*22 + 17*15 + 16*8 + 0*19 + 0*49 = 2191

Наименьшее значение целевой функции получено методом наименьших стоимостей. В дальнейшем будет использоваться матрица распределения ресурсов полученная именно этим планом.

Этап II. Улучшение опорного плана.

Проверим оптимальность опорного плана. Найдем предварительные потенциалы u_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

u₁ + v₂ = 21; 0 + v₂ = 21; v₂ = 21

u₂ + v₂ = 25; 21 + u₂ = 25; u₂ = 4

u₂ + v₁ = 22; 4 + v₁ = 22; v₁ = 18

u₄ + v₁ = 17; 18 + u₄ = 17; u₄ = -1

u₂ + v₄ = 29; 4 + v₄ = 29; v₄ = 25

u₆ + v₄ = 0; 25 + u₆ = 0; u₆ = -25

u₆ + v₃ = 0; -25 + v₃ = 0; v₃ = 25

u₃ + v₃ = 12; 25 + u₃ = 12; u₃ = -13

u₂ + v₅ = 25; 4 + v₅ = 25; v₅ = 21

u₅ + v₅ = 16; 21 + u₅ = 16; u₅ = -5

	v₁=18	v₂=21	v₃=25	v₄=25	v₅=21
u₁=0		21[21]
u₂=4	22[21]	25[12]		29[4]	25[9]
u₃=-13			12[22]
u₄=-1	17[15]
u₅=-5					16[8]
u₆=-25			0[19]	0[49]

Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u_i + v_i > c_ij

(1;1): 0 + 18 > 13; ∆₁₁ = 0 + 18 - 13 = 5

(1;3): 0 + 25 > 21; ∆₁₃ = 0 + 25 - 21 = 4

max(5,4) = 5

Выбираем максимальную оценку свободной клетки (1;1): 13

Для этого в перспективную клетку (1;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».

						Запасы
	13[+]	21[21][-]
	22[21][-]	25[12][+]		29[4]	25[9]
			12[22]
	17[15]
					16[8]
			0[19]	0[49]
Потребности

Цикл приведен в таблице (1,1; 1,2; 2,2; 2,1;).

Из грузов х_ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (1, 2) = 21. Прибавляем 21 к объемам грузов, стоящих в плюсовых клетках и вычитаем 21 из Х_ij, стоящих в минусовых клетках. В результате получим новый опорный план.

						Запасы
	13[21]
	22[0]	25[33]		29[4]	25[9]
			12[22]
	17[15]
					16[8]
			0[19]	0[49]
Потребности

u₁ + v₁ = 13; 0 + v₁ = 13; v₁ = 13

u₂ + v₁ = 22; 13 + u₂ = 22; u₂ = 9

u₂ + v₂ = 25; 9 + v₂ = 25; v₂ = 16

u₂ + v₄ = 29; 9 + v₄ = 29; v₄ = 20

u₆ + v₄ = 0; 20 + u₆ = 0; u₆ = -20

u₆ + v₃ = 0; -20 + v₃ = 0; v₃ = 20

u₃ + v₃ = 12; 20 + u₃ = 12; u₃ = -8

u₂ + v₅ = 25; 9 + v₅ = 25; v₅ = 16

u₅ + v₅ = 16; 16 + u₅ = 16; u₅ = 0

u₄ + v₁ = 17; 13 + u₄ = 17; u₄ = 4

	v₁=13	v₂=16	v₃=20	v₄=20	v₅=16
u₁=0	13[21]
u₂=9	22[0]	25[33]		29[4]	25[9]
u₃=-8			12[22]
u₄=4	17[15]
u₅=0					16[8]
u₆=-20			0[19]	0[49]

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u_i + v_i <= c_ij.

Минимальные затраты составят:

F(x) = 13*21 + 25*33 + 29*4 + 25*9 + 12*22 + 17*15 + 16*8 + 0*19 + 0*49 = 2086

Дата добавления: 2015-09-03; просмотров: 104 | Нарушение авторских прав

<== предыдущая страница	\|	следующая страница ==>
Метод северо-западного угла	\|	СХЕМА ЭЛЕКТРОСНАБЖЕНИЯ

mybiblioteka.su - 2015-2024 год. (0.061 сек.)