Задание №3

Дано:

	В1	В2	В3	В4	В5	Наличие
А1	7	4	15	9	14	120
А2	11	2	7	3	10	150
А3	4	5	12	8	17	100
Потребность	65	90	60	70	300

Решение:

Пошагово осуществим поиск опорного плана методом северо-западного угла:

1. 

2. Потребности пункта B1 удовлетворены.

3. 

4. Запасы склада А1 исчерпаны.

5. 

6. Потребности пункта B2 удовлетворены.

7. .

8. Потребности пункта B3 удовлетворены.

9. .

10. Запасы склада А2 исчерпаны.

11. .

12. Потребности пункта B4 удовлетворены.

13. .

14. Для удовлетворения потребностей пункта B5 не хватает товара в количестве 215 единиц.

Данные полученные при поиске опорного плана методом северо-западного угла сведены в таблицу:

	В1	В2	В3	В4	В5	Наличие
А1	7	4	15	9	14	120	[55]			[0]
	[65]	[55]
А2	11	2	7	3	10	150	[115]	[55]	[0]
		[35]	[60]	[55]
А3	4	5	12	8	17	100	[85]			[0]
				[15]	[85]
Потребность	65	90	60	70	300
		[35]	[0]	[15]
	[0]	[0]		[0]	[215]

Далее добавим фиктивную строку:

	В1	В2	В3	В4	В5	Наличие
А1	7	4	15	9	14	120	[55]		[0]
	[65]	[55]
А2	11	2	7	3	10	150	[115]	[55]	[0]
		[35]	[60]	[55]
А3	4	5	12	8	17	100	[85]		[0]
				[15]	[85]
A4	17	17	17	17	17	215		[0]
					215
Потребность	65	90	60	70	300
		[35]		[15]	[215]
	[0]		[0]
		[0]		[0]	[0]

1. .

2. Потребности пункта B5 удовлетворены.

Получен начальный план перевозок, а его суммарная стоимость составила:

• 

Осуществим поиск опорного плана методом наименьшей стоимости, данные сведем в таблицу:

	В1	В2	В3	В4	В5	Наличие
А1	7	4	15	9	14	120			[0]
					^(6) [120]
А2	11	2	7	3	10	150		[60]			[0]
		^(1) [90]		^(2) [60]
А3	4	5	12	8	17	100	[35]		[10]			[0]
	^(3) [65]		^(5) [25]	^(4) [10]
A4	17	17	17	17	17	215		[180]		[0]
			^(7) [35]		^(8) [180]
Потребность	65	90	60	70	300
			[35]	[10]	[180]
	[0]	[0]	[0]	[0]	[0]

Получен начальный план перевозок, а его суммарная стоимость составила:

• 

Осуществим поиск оптимального плана перевозок с помощью метода потенциалов основываясь на опорном плане, полученном методом наименьшей стоимости:

	7	7	14
	0	2	2
	0	3	3
	5		4
	5	7	12
	5	3	8
	10	7	17
	10	7	17

Значения для свободных клеток:

	Значение
	1
	-5
	1
	-1
	12
	0
	3
	-2
	5
	8
	5
	4

Выберем наименьшее отрицательное значение и приняв его за начало цикла расставим затем знаки начиная с «» и чередуя его с «»:

	В1	В2	В3	В4	В5	Наличие
А1	7	4	15	9	14	120				[0]
		^(+)			^(6)^(–) [120]
А2	11	2	7	3	10	150		[60]				[0]
		^(1)^(–) [90]		^(2)^(+) [60]
А3	4	5	12	8	17	100	[35]		[10]				[0]
	^(3) [65]		^(5)^(+) [25]	^(4)^(–) [10]
A4	17	17	17	17	17	215		[180]			[0]
			^(7)^(–) [35]		^(8)^(+) [180]
Потребность	65	90	60	70	300
			[35]	[10]	[180]
	[0]	[0]	[0]	[0]	[0]

Выбираем минимальное число (данное число равно 10) в «» ячейках цикла и учитывая знаки цикла прибавляем это число или отнимаем, а также обновим расстановку знаков «+» и «»:

	В1	В2	В3	В4	В5	Наличие
А1	7	4	15	9	14	120
		^(+) [10]			^(–) [110]
А2	11	2	7	3	10	150
		^(–) [80]	^(+)	[70]
А3	4	5	12	8	17	100
	[65]		^(+) [35]
A4	17	17	17	17	17	215
			^(–) [25]		^(+) [190]
Потребность	65	90	60	70	300

Ячейка заполняется, а ячейкастала пустой.

Найдем значения:

	0	4	4
	0	14	14
		4	2
		5	3
		6	4
		14	12
	3	14	17
	3	14	17

Найдем значения для свободных клеток:

	Значение
	1
	1
	4
	7
	3
	5
	5
	8
	10
	9

Выбираем минимальное число (данное число равно 25) в «» ячейках цикла (согласно расстановке знаков на предыдущей стадии) и учитывая знаки цикла прибавляем это число или отнимаем:

	В1	В2	В3	В4	В5	Наличие
А1	7	4	15	9	14	120
		^(+) [35]			^(-) [85]
А2	11	2	7	3	10	150
		^(-) [55]	[25]	[70]	^(+)
А3	4	5	12	8	17	100
	[65]		^(+) [35]
A4	17	17	17	17	17	215
					[215]
Потребность	65	90	60	70	300

Ячейка заполняется, а ячейкастала пустой.

Найдем значения:

	2	2	4
	2	12	14
	0	2	2
	0	7	7
	0	3	3
	5	-1	4
	5	7	12
	5	12	17

Найдем значения для свободных клеток:

	Значение
	6
	6
	4
	12
	-2
	-2
	0
	0
	13
	10
	5
	9

Выбираем минимальное число (на данной стадии это число равно 55) в «–» ячейках цикла (согласно расстановке знаков на предыдущей стадии) и учитывая знаки цикла прибавляем это число или отнимаем:

	В1	В2	В3	В4	В5	Наличие
А1	7	4	15	9	14	120
		[90]			[30]
А2	11	2	7	3	10	150
			[25]	[70]	[55]
А3	4	5	12	8	17	100
	[65]		[35]
A4	17	17	17	17	17	215
					[215]
Потребность	65	90	60	70	300

Ячейка заполняется, а ячейкастала пустой.

Найдем значения:

	4	0	4
	4	10	14
	0	7	7
	0	3	3
	0	10	10
	5	-1	4
	5	7	12
	7	10	17

Найдем значения для свободных клеток:

	Значение
	4
	4
	2
	12
	2
	0
	0
	2
	11
	10
	3
	7

Все , задача решена.

Общие затраты на перевозку всех единиц продукции составят:

•