пр4 (Автосохраненный)

Пункт отправления	Пункты назначения					Запасы
	B1	B2	B3	B4	B5
A1	7 110	9 40	10	6	5	150/40/0
A2	12	8 140	6 30	5 50	13	220/80/50/0
A3	6	2	8	2 130	4 50	180/50/0
Потребности	110/0	180/140/0	30/0	180/130/0	50/0	550

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

Заполним клетку А1В1:

Х11=110, то есть полностью удовлетворяем потребность В1 и удаляем из рассмотрения столбец 1.

Запасы на складе А1=150-110=40.

Заполним клетку А1В2:

Х12=40, т е запасы со склада А1 вывезли, удаляем из рассмотрения строку 1, а потребность: В2=180-40=140

Заполним клетку А2В2:

Х22=140, то есть полностью удовлетворяем потребность В2 и удаляем из рассмотрения столбец 2.

Запасы на складе А2=220-140=80.

Заполним клетку А2В3:

Х23=30, то есть полностью удовлетворяем потребность В3 и удаляем из рассмотрения столбец 3.

Запасы на складе А2=80-30=50.

Заполним клетку А2В4:

Х24=50, т е запасы со склада А2 вывезли, удаляем из рассмотрения строку 2, а потребность: В4=180-50=130

Заполним клетку А3В4:

Х34=110, то есть полностью удовлетворяем потребность В4 и удаляем из рассмотрения столбец 4.

Запасы на складе А3=180-130=50.

Заполним клетку А3В5:

Х35=50, т е запасы со склада А3 вывезли, удаляем из рассмотрения строку 3, а потребность: В5=50-50=0

Получаем опорный план:

110 40 0 0 0

Х = ( 0 140 30 50 0 )

0 0 0 130 50

ОБЩАЯ СТОИМОСТЬ ПЕРЕВОЗОК РАВНА:

S=7*110+9*40+8*140+6*30+5*50+2*130+4*50=3140

Метод минимального элемента

На каждом шаге выбирается клетка с оставшимся минимальным тарифе.

1)Минимальный тариф = 2 и находится в клетке А3В2.

Х32= 180, то есть вывозим весь запас со склада А3 и исключаем 3 строку из рассмотрения, а потребность равна В2=180-180=0.

2)Минимальный тариф = 5 и находится в клетке А1В5.

Х15=50, то есть удовлетворяем потребность В5 и исключаем из рассмотрения 5 столбец. Запасы в А1: 150-50=100.

3)Минимальный тариф = 5 и находится в клетке А2В4.

Х24=180, т е удовлетворяем потребность и исключаем из рассмотрения 4 столбец. Запасы в А2 равны 220-180=40.

4)Минимальный тариф = 6 и находится в клетке А2В3.

Х23=30, т е потребности удовлетворены и исключаем из рассмотрения 3 столбец. Запасы в А2 равны 40-30=10.

5)Минимальный тариф = 7 и находится в клетке А1В1.

Х11= 100, то есть вывозим весь запас со склада А1 и исключаем 1 строку из рассмотрения, а потребность равна В1=110-100=10.

6)Минимальный тариф = 8 и находится в клетке А2В2.

Х22=0, то есть удовлетворяем потребность В2 и исключаем из рассмотрения 2 столбец. Запасы в А2: 10-0=10.

7)Минимальный тариф = 12 и находится в клетке А2В1.

Х21=10, то есть удовлетворяем потребность В1 и исключаем из рассмотрения 1 столбец. Запасы в А2: 10-10=0.

Получаем опорный план:

100 0 0 0 50

Х = ( 10 0 30 180 0 )

0 180 0 0 0

ОБЩАЯ СТОИМОСТЬ ПЕРЕВОЗОК РАВНА:

S=7*100+5*50+12*10+30*6+5*180+2*180= 700+250+120+180+900+360=2510

Пункты отправления	Пункты назначения						Разность по строкам
	В1	В2	В3	В4	В5	Запасы
А1	7 100	9	10	6	5 50	150/100/0		1	1	1	-	-	-	-
А2	12 10	8 0	6 30	5 180	13	220/40/10/0		1	1	1	1	2	4	0
А3	6	2 180	8	2	4	180/0		0	-	-	-	-	-	-
Потребности	110/10/0	180/0	30/0	180/0	50/0	550
Разницы по столбцам	1	6	2	3	1
	5	1	4	1	8
	5	1	4	1	-
	0	0	0	0	-
	0	0	0	-	-
	0	0	-	-	-
	0	-	-	-	-

Метод аппроксимации Фогеля:

Для каждой строки и для каждого столбца найдем разность между 2мя минимальными тарифами.

1. А1=6-5=1

А2=6-5=1

А3=2-2=0

В1=7-6=1

В2=8-2=6

В3=8-6=2

В4=5-2=3

В5=5-4=1

Максимальная разность между ними соответствует столбцу В2. Минимальный тариф в этом столбце равен 2 – клетка А3В2.

Х32=180, то есть то есть вывозим весь запас со склада А3 и исключаем 3 строку из рассмотрения, а потребность равна В2=180-180=0.

2. А1=6-5=1

А2=6-5=1

В1=12-7=5

В2=9-8=1

В3=10-6=4

В4=6-5=1

В5=13-5=8

Максимальная разность между ними соответствует столбцу В5. Минимальный тариф в этом столбце равен 5 – клетка А1В5.

Х15=50, то есть удовлетворяем потребность В5 и исключаем из рассмотрения 5 столбец. Запасы в А1: 150-50=100.

3. А1=7-6=1

А2=6-5=1

В1=12-7=5

В2=9-8=1

В3=10-6=4

В4=6-5=1

Максимальная разность между ними соответствует столбцу В1. Минимальный тариф в этом столбце равен 7 – клетка А1В1.

Х11= 100, то есть вывозим весь запас со склада А1 и исключаем 1 строку из рассмотрения, а потребность равна В1=110-100=10.

А2=6-5=1

В1=12-12=0

В2=8-8=0

В3=6-6=0

В4=5-5=0

Максимальная разность между ними соответствует строке А2. Минимальный тариф в этом столбце равен 7 – клетка А2В4.

Х24=180, т е удовлетворяем потребность и исключаем из рассмотрения 4 столбец. Запасы в А2 равны 220-180=40.

5. А2=8-6=2

В1=12-12=0

В2=8-8=0

В3=6-6=0

Максимальная разность между ними соответствует строке А2. Минимальный тариф в этом столбце равен 6 – клетка А2В3.

Х23=30, т е потребности удовлетворены и исключаем из рассмотрения 3 столбец. Запасы в А2 равны 40-30=10

А2=12-8=4

В1=12-12=0

В2=8-8=0

Максимальная разность между ними соответствует строке А2. Минимальный тариф в этом столбце равен 8 – клетка А2В2.

Х22=0, то есть удовлетворяем потребность В2 и исключаем из рассмотрения 2 столбец. Запасы в А2: 10-0=10.

А2=12-12=0

В1=12-12=0

Максимальная разность между ними соответствует строке А2. Минимальный тариф в этом столбце равен 12 – клетка А2В1.

Х21=10, то есть удовлетворяем потребность В1 и исключаем из рассмотрения 1 столбец. Запасы в А2: 10-10=0.

Получаем опорный план:

100 0 0 0 50

Х = ( 10 0 30 180 0 )

0 180 0 0 0

ОБЩАЯ СТОИМОСТЬ ПЕРЕВОЗОК РАВНА:

S=7*100+5*50+12*10+30*6+5*180+2*180= 700+250+120+180+900+360=2510