Итерация 3.

Поставщик	Потребитель					Запас
	B 1	B 2	B 3	B 4	B 5
A 1	150 - 40 32	+40 -2 20	34	40	50 24	200
A 2	40 28	18	24	110 34	21	150
A 3	10 + 40 26	40 - 40 16	50 22	32	30	100
Потребность	200	40	50	110	50

Получили новое решение

Поставщик	Потребитель					Запас
	B 1	B 2	B 3	B 4	B 5
A 1	110 32	40 20	34	40	50 24	200
A 2	40 28	18	24	110 34	21	150
A 3	50 26	16	50 22	32	30	100
Потребность	200	40	50	110	50

---

Общая сумма доставки продукции:

S = 12860 + Δ₁₂ * 40 = 12860 -2 * 40 = 12780 ден. ед.

Найдем оценки незадействованных маршрутов: A1B3 :   Δ13 = c13 - ( u1 + v3 ) = 34 - ( 0 + 28 ) = 6 A1B4 :   Δ14 = c14 - ( u1 + v4 ) = 40 - ( 0 + 38 ) = 2 A2B2 :   Δ22 = c22 - ( u2 + v2 ) = 18 - ( -4 + 20 ) = 2 A2B3 :   Δ23 = c23 - ( u2 + v3 ) = 24 - ( -4 + 28 ) = 0 A2B5 :   Δ25 = c25 - ( u2 + v5 ) = 21 - ( -4 + 24 ) = 1 A3B2 :   Δ32 = c32 - ( u3 + v2 ) = 16 - ( -6 + 20 ) = 2 A3B4 :   Δ34 = c34 - ( u3 + v4 ) = 32 - ( -6 + 38 ) = 0 A3B5 :   Δ35 = c35 - ( u3 + v5 ) = 30 - ( -6 + 24 ) = 12

Нет отрицательных оценок – решение оптимально
Ответ:



S_min = 12780 ден. ед.

Метод аппроксимации Ролля

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

Поставщик	Потребитель						Запас		d1		d2		d3		d4		d5
	B 1	B 2	B 3	B 4	B 5
A 1	150 32	20	34	40	50 24	200		4		8		2		8		-
A 2	40 28	18	24	110 34	21	150		3		3		4		6		6
A 3	10 26	40 16	50 22	32	30	100		6		4		4		6		6
Потребность	200	40	50	110	50
d1	2	2	2	2	3
d2	2	-	2	2	3
d3	2	-	2	2	-
d4	2	-	-	2	-
d5	2	-	-	2	-

---

Значение целевой функции опорного плана равно:
S = 32*150 + 24*50 + 28*40 + 34*110 + 26*10 + 16*40 + 22*50 = 12860

---

Смотрите также файлы

• Контрольная работа по истории. 7 класс. Общее число заданий в работе.docx

• Алгоритм асиеттері Алгоритмді талдау.docx

• Нетрадиционные и возобновляемые источники энергии.pdf

• Влияние бега на организм человека.docx

• Отчет по практике по организации детельности детей младшего школьного возраста в учреждениях дополнительного образования.docx