Метод наименьшей стоимости.

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую, и в клетку, которая ей соответствует, помещают меньшее из чисел a_i, или b_j.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	x	x	x	x
x
x	x		x	x
	x	x	x	x	15 - 15 = 0
x	x	x	x
15 - 15 = 0

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

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

x₂₂ = min(46,33) = 33.

	x	x	x	x
x					46 - 33 = 13
x	x		x	x
	x	x	x	x
x	x	x	x
	33 - 33 = 0

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

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

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

	x	x	x	x
x					13 - 9 = 4
x	x		x	x
	x	x	x	x
x	x	x	x
				9 - 9 = 0

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

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

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

	x	x	x	x
x		x			4 - 4 = 0
x	x		x	x
	x	x	x	x
x	x	x	x
			53 - 4 = 49

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

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

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

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

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

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

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

	x	x	x	x
x		x
x	x		x	x
	x	x	x	x
x	x	x	x
					49 - 49 = 0
			49 - 49 = 0

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

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

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

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

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

Строим новый план.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	x	x	x	x
x
x	x		x	x
	x	x	x	x	15 - 15 = 0
x	x	x	x
15 - 15 = 0

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

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

x₂₂ = min(46,33) = 33.

	x	x	x	x
x					46 - 33 = 13
x	x		x	x
	x	x	x	x
x	x	x	x
	33 - 33 = 0

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

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

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

	x	x	x	x
x					13 - 9 = 4
x	x		x	x
	x	x	x	x
x	x	x	x
				9 - 9 = 0

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

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

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

	x	x	x	x
x		x			4 - 4 = 0
x	x		x	x
	x	x	x	x
x	x	x	x
			53 - 4 = 49

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

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

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

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

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

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

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

	x	x	x	x
x		x
x	x		x	x
	x	x	x	x
x	x	x	x
					49 - 49 = 0
			49 - 49 = 0

Полученная матрица распределения ресурсов

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

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

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

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

Строим новый план.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

	x	x	x	x
x
x	x		x	x
	x	x	x	x	15 - 15 = 0
x	x	x	x
15 - 15 = 0

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

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

x₂₂ = min(46,33) = 33.

	x	x	x	x
x					46 - 33 = 13
x	x		x	x
	x	x	x	x
x	x	x	x
	33 - 33 = 0

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

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

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

	x	x	x	x
x					13 - 9 = 4
x	x		x	x
	x	x	x	x
x	x	x	x
				9 - 9 = 0

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

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

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

	x	x	x	x
x		x			4 - 4 = 0
x	x		x	x
	x	x	x	x
x	x	x	x
			53 - 4 = 49

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

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

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

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

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

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

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

	x	x	x	x
x		x
x	x		x	x
	x	x	x	x
x	x	x	x
					49 - 49 = 0
			49 - 49 = 0

Полученная матрица распределения ресурсов

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

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

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

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

Строим новый план.

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

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

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

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

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

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

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

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

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

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

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

	x	x	x	x	21 - 21 = 0
x
x	x		x	x
	x	x	x	x
x
21 - 21 = 0

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

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

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

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

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

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

x₂₂ = min(46,33) = 33.

	x	x	x	x
x					46 - 33 = 13
x	x		x	x
	x	x	x	x
x	x	x	x
	33 - 33 = 0

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

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

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

	x	x	x	x
x					13 - 9 = 4
x	x		x	x
	x	x	x	x
x	x	x	x
				9 - 9 = 0

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

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

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

	x	x	x	x
x		x			4 - 4 = 0
x	x		x	x
	x	x	x	x
x	x	x	x
			53 - 4 = 49

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

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

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

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

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

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

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

	x	x	x	x
x		x
x	x		x	x
	x	x	x	x
x	x	x	x
					49 - 49 = 0
			49 - 49 = 0

Матрица распределения ресурсов выглядит следующим образом:

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

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

Строим новый план.

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

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

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

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

x₁₂ = min(21,33) = 21.

x		x	x	x	21 - 21 = 0
	33 - 21 = 12

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

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

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

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

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

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

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

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

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

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

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

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

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

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

x₂₁ = min(46,21) = 21.

x		x	x	x
					46 - 21 = 25
x	x		x	x
	x	x	x	x
x	x	x	x
21 - 21 = 0

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

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

x₂₂ = min(25,12) = 12.

x		x	x	x
					25 - 12 = 13
x	x		x	x
	x	x	x	x
x	x	x	x
	12 - 12 = 0

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

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

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

x		x	x	x
					13 - 9 = 4
x	x		x	x
	x	x	x	x
x	x	x	x
				9 - 9 = 0

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

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

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

x		x	x	x
		x			4 - 4 = 0
x	x		x	x
	x	x	x	x
x	x	x	x
			53 - 4 = 49

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

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

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

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

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

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

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

x		x	x	x
		x
x	x		x	x
	x	x	x	x
x	x	x	x
					49 - 49 = 0
			49 - 49 = 0

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

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

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

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

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

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

Дата добавления: 2015-09-03