работа по дисциплине "Прикладная математика" (стр. 3 из 4)

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

Для решения транспортной задачи чаще всего применяется метод потенциалов.

Общий объем производства åа_i =80+60+30=170 больше, чем требуется всем потребителям åb_i = 34+40+38+53 =165, т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 170-165 = 5 единиц, причем тарифы на перевозку в этот пункт условимся считать равными нулю, помня, что переменные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами.

Первое базисное допустимое решение легко построить по правилу ²северо-западного угла².

Потребление	b1 =34	b2 =40	b3 =38	b4 =53	b5 =5
Производство
а1 =80	234	740	26	3	0	p1 = 0
a2 =60	1	5 *	432	228	0	p2 = 2
a3 =30	3	4	6	125	05	p3 = 1
q1 = 2	q2 = 7	q3 = 2	q4 = 0	q5 = -1

Общая стоимость всех перевозок для первого базисного допустимого решения:

L= 34* 2 + 40*7 + 6*2 + 32*4 + 28*2+25 =569

Обозначим через

m(p₁, p₂,…, p_m, q₁, q₂,…, q_n)

вектор симплексных множителей или потенциалов. Тогда

Д_ij = m A_ij – c_ij i = (1,…,m), j = (1,…,n)

откуда следует

Д_ij = p_i + q_j– c_ij i = (1,…,m), j = (1,…,n) (1)

Один из потенциалов можно выбрать произвольно, так как в системе одно уравнение линейно зависит от остальных. Положим, что р₁ = 0. Остальные потенциалы находим из условия, что для базисных клеток Д_ij = 0. В данном случае получаем

D₁₁ = 0, p₁ + q₁ - c₁₁ = 0, 0+q₁ -2 = 0, q₁ = 2

D₁₂ = 0, p₁ + q₂ - c₁₂ = 0, 0+q₂ -7 = 0, q₂ = 7

D₁₃ = 0, p₁ + q₃ - c₁₃ = 0, 0+q₃ -2 = 0, q₃ = 2

D₂₃ = 0, p₂ + q₃ – c₂₃ = 0, p₂+2 -4 = 0, p₂ = 2

D₂₄ = 0, p₂ + q₄ – c₂₄ = 0, 2+q₄ -2 = 0, q₄ = 0

D₃₄ = 0, p₃ + q₄ – c₃₄ = 0, p₃+ 0 -1 = 0, p₃ = 1

D₃₅ = 0, p₃ + q₅ – c₃₅ = 0, 1+ q₅ -0 = 0, q₅ = -1

Затем по формуле (1) вычисляем оценки всех свободных клеток:

D₂₁ = p₂ + q₁ - c₂₁ = 2+2-1 = 3

D₃₁ = p₃ + q₁ - c₃₁ = 1+2 -3 = 0

D₂₂ = p₂ + q₂ – c₂₂ = 2+7-5 = 4

D₃₂ = p₃ + q₂ – c₃₂ = 1+7-4 = 4

D₃₃ = p₃ + q₃ – c₃₃ = 1+2-6 = 3

D₁₄ = p₁ + q₄ – c₁₃ = 0+0-3 = 3

D₁₅ = p₁ + q₅ – c₁₅ = 0+(-1) = -1

D₂₅ = p₂ + q₅ – c₂₅ = 2+(-1) = 1

Находим наибольшую положительную оценку max (D_ij > 0) = 4 = D₂₂

Для найденной свободной клетки 22 строим цикл пересчета - замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные - в занятых клетках. Это будет 22-12-13-23. Производим перераспределение поставок вдоль цикла пересчета

40	6	40-r	6+r	8	38
32		r	32-r	32	0

= 32

Получаем второе базисное допустимое решение:

Потребление	b1 =34	b2 =40	b3 =38	b4 =53	b5 =5
Производство
а1 =80	234	78	238	3	0 *	p1 = 0
a2 =60	1	532	4	228	0	p2 = -2
a3 =30	3	4	6	125	05	p3 = -3
q1 = 2	q2 = 7	q3 = 2	q4 = 4	q5 = 3

Находим новые потенциалы, новые оценки.

D₁₁ = 0, p₁ + q₁ - c₁₁ = 0, 0+q₁ -2 = 0, q₁ = 2

D₁₂ = 0, p₁ + q₂ - c₁₂ = 0, 0+q₂ -7 = 0, q₂ = 7

D₁₃ = 0, p₁ + q₃ - c₁₃ = 0, 0+q₃ -2 = 0, q₃ = 2

D₂₂ = 0, p₂ + q₂ – c₂₂ = 0, p₂+7 -5 = 0, p₂ = -2

D₂₄ = 0, p₂ + q₄ – c₂₄ = 0, -2+q₄ -2 = 0, q₄ = 4

D₃₄ = 0, p₃ + q₄ – c₃₄ = 0, p₃+ 4 -1 = 0, p₃ = -3

D₃₅ = 0, p₃ + q₅ – c₃₅ = 0, -3+ q₅ -0 = 0, q₅ = 3

Вычислим оценки свободных клеток:

D₂₁ = p₂ + q₁ - c₂₁ = -2+2-1 = -1

D₃₁ = p₃ + q₁ - c₃₁ = -3+2 -3 = -4

D₃₂ = p₃ + q₂ – c₃₂ = -3+7-4 = 0

D₂₃ = p₂ + q₃ – c₂₃ = -2+2-4 = -4

D₃₃ = p₃ + q₃ – c₃₃ = -3+2-6 = -7

D₁₄ = p₁ + q₄ – c₁₃ = 0+4-3 = 1

D₁₅ = p₁ + q₅ – c₁₅ = 0+3 = 3

D₂₅ = p₂ + q₅ – c₂₅ = -2+3 = 1

Находим наибольшую положительную оценку max (D_ij > 0) = 3 = D₁₅

8			*		8-r			r		3			5
32		28			32+r		28-r			37		23
		25	5				25+r	5-r				30

= 5

Получаем третье базисное допустимое решение:

Потребление	b1 =34	b2 =40	b3 =38	b4 =53	b5 =5
Производство
а1 =80	234	73	238	3 *	05	p1 = 0
a2 =60	1	537	4	223	0	p2 = -2
a3 =30	3	4	6	130	0	p3 = -3
q1 = 2	q2 = 7	q3 = 2	q4 = 4	q5 = 0

Находим новые потенциалы, новые оценки.

D₁₅ = 0, p₁ + q₅ – c₁₅ = 0, 0+ q₅ -0 = 0, q₅ = 0

Вычислим оценки свободных клеток:

D₂₁ = p₂ + q₁ - c₂₁ = -2+2-1 = -1