	Информационно-образоательный портал
	Рефераты, курсовые, дипломы, научные работы,



МЕНЮ\|

поиск

Курсовая: Курсовая по прикладной математике ГУУ

ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

Однородный продукт, сосредоточенный в 3 пунктах производства (хранения) в количествах 80; 60; 30 единиц, необходимо распределить между 4 пунктами потребления, которым необходимо соответственно 34; 40; 38; 53 единиц. Стоимость перевозки единицы продукта из пункта отправления в пункт назначения известна для всех маршрутов и равна С =

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

Потребление	b1 =34	b2 =40	b3 =38	b4 =53	b5 =5
Производство
а1 =80	2 34	7 40	2 6	3	0	p1 = 0
a2 =60	1	5 *	4 32	2 28	0	p2 = 2
a3 =30	3	4	6	1 25	0 5	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(p1, p2,., pm, q1, q2,., qn) вектор симплексных множителей или потенциалов. Тогда Дij = m Aij – cij i = (1,.,m), j = (1,.,n) откуда следует Дij = pi + qj– cij i = (1,.,m), j = (1,.,n) (1) Один из потенциалов можно выбрать произвольно, так как в системе одно уравнение линейно зависит от остальных. Положим, что р1 = 0. Остальные потенциалы находим из условия, что для базисных клеток Дij = 0. В данном случае получаем D11 = 0, p1 + q1 - c11 = 0, 0+q1 -2 = 0, q1 = 2 D12 = 0, p1 + q2 - c12 = 0, 0+q2 -7 = 0, q2 = 7 D13 = 0, p1 + q3 - c13 = 0, 0+q3 -2 = 0, q3 = 2 D23 = 0, p2 + q3 – c23 = 0, p2+2 -4 = 0, p2 = 2 D24 = 0, p2 + q4 – c24 = 0, 2+q4 -2 = 0, q4 = 0 D34 = 0, p3 + q4 – c34 = 0, p3+ 0 -1 = 0, p3 = 1 D35 = 0, p3 + q5 – c35 = 0, 1+ q5 -0 = 0, q5 = -1 Затем по формуле (1) вычисляем оценки всех свободных клеток: D21 = p2 + q1 - c21 = 2+2-1 = 3 D31 = p3 + q1 - c31 = 1+2 -3 = 0 D22 = p2 + q2 – c22 = 2+7-5 = 4 D32 = p3 + q2 – c32 = 1+7-4 = 4 D33 = p3 + q3 – c33 = 1+2-6 = 3 D14 = p1 + q4 – c13 = 0+0-3 = 3 D15 = p1 + q5 – c15 = 0+(-1) = -1 D25 = p2 + q5 – c25 = 2+(-1) = 1 Находим наибольшую положительную оценку max (Dij > 0) = 4 = D22 Для найденной свободной клетки 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	2 34	7 8	2 38	3	0 *	p1 = 0
a2 =60	1	5 32	4	2 28	0	p2 = -2
a3 =30	3	4	6	1 25	0 5	p3 = -3
	q1 = 2	q2 = 7	q3 = 2	q4 = 4	q5 = 3

Находим новые потенциалы, новые оценки. D11 = 0, p1 + q1 - c11 = 0, 0+q1 -2 = 0, q1 = 2 D12 = 0, p1 + q2 - c12 = 0, 0+q2 -7 = 0, q2 = 7 D13 = 0, p1 + q3 - c13 = 0, 0+q3 -2 = 0, q3 = 2 D22 = 0, p2 + q2 – c22 = 0, p2+7 -5 = 0, p2 = -2 D24 = 0, p2 + q4 – c24 = 0, -2+q4 -2 = 0, q4 = 4 D34 = 0, p3 + q4 – c34 = 0, p3+ 4 -1 = 0, p3 = -3 D35 = 0, p3 + q5 – c35 = 0, -3+ q5 -0 = 0, q5 = 3 Вычислим оценки свободных клеток: D21 = p2 + q1 - c21 = -2+2-1 = -1 D31 = p3 + q1 - c31 = -3+2 -3 = -4 D32 = p3 + q2 – c32 = -3+7-4 = 0 D23 = p2 + q3 – c23 = -2+2-4 = -4 D33 = p3 + q3 – c33 = -3+2-6 = -7 D14 = p1 + q4 – c13 = 0+4-3 = 1 D15 = p1 + q5 – c15 = 0+3 = 3 D25 = p2 + q5 – c25 = -2+3 = 1 Находим наибольшую положительную оценку max (Dij > 0) = 3 = D15

8-r

32+r

28-r

25+r

5-r

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

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

Страницы: 1, 2, 3

© 2003-2013
Рефераты бесплатно, курсовые, рефераты биология, большая бибилиотека рефератов, дипломы, научные работы, рефераты право, рефераты, рефераты скачать, рефераты литература, курсовые работы, реферат, доклады, рефераты медицина, рефераты на тему, сочинения, реферат бесплатно, рефераты авиация, рефераты психология, рефераты математика, рефераты кулинария, рефераты логистика, рефераты анатомия, рефераты маркетинг, рефераты релиния, рефераты социология, рефераты менеджемент.