Метод северо-западного угла

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

План начинается заполняться с верхнего левого угла.

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

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

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

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

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

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

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

	x	x	x	x
					46 - 15 = 31
x
x
x
15 - 15 = 0

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

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

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

	x	x	x	x
		x	x	x	31 - 31 = 0
x
x
x
	33 - 31 = 2

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

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

x₃₂ = min(22,2) = 2.

	x	x	x	x
		x	x	x
x					22 - 2 = 20
x	x
x	x
	2 - 2 = 0

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

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

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

	x	x	x	x
		x	x	x
x			x	x	20 - 20 = 0
x	x
x	x
		41 - 20 = 21

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

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

x₄₃ = min(15,21) = 15.

	x	x	x	x
		x	x	x
x			x	x
x	x		x	x	15 - 15 = 0
x	x
		21 - 15 = 6

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

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

x₅₃ = min(8,6) = 6.

	x	x	x	x
		x	x	x
x			x	x
x	x		x	x
x	x				8 - 6 = 2
		6 - 6 = 0

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

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

x₅₄ = min(2,53) = 2.

	x	x	x	x
		x	x	x
x			x	x
x	x		x	x
x	x			x	2 - 2 = 0
			53 - 2 = 51

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

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

x₆₄ = min(68,51) = 51.

	x	x	x	x
		x	x	x
x			x	x
x	x		x	x
x	x			x
					68 - 51 = 17
			51 - 51 = 0

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

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

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

	x	x	x	x
		x	x	x
x			x	x
x	x		x	x
x	x			x
					17 - 17 = 0
				17 - 17 = 0

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

						Запасы
	13[21]
	22[15]	25[31]
		38[2]	12[20]
			51[15]
			21[6]	24[2]
				0[51]	0[17]
Потребности

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

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

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

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

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