Линейное и динамическое программирование (стр. 3 из 8)

Транспортная задача

Транспортная задача формулируется следующим образом. Однородный продукт, сосредоточенный в т пунктах производства (хранения) в количествах a₁, а₂,..., а_m единиц, необходимо распределить между п пунктами потребления, которым необходимо соответственно b₁, b_2,,…, b_n единиц. Стоимость перевозки единицы продукта из i-ro пункта отправления в j-й пункт назначения равна c_ij и известна для всех маршрутов. Необходимо составить план перевозок, при котором запросы всех пунктов потребления были бы удовлетворены за счет имеющихся продуктов в пунктах производства и общие транспортные расходы по доставке продуктов были минимальными.

Обозначим через x_ij количество груза, планируемого к перевозке от i-ro поставщика j-му потребителю. При наличии баланса производства и потребления

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

найти план перевозок

X=(x_ij), x_ij³0, iÎN_m, jÎN_n

минимизирующий общую стоимость всех перевозок

при условии, что из любого пункта производства вывозится весь продукт

, iÎN_m

и любому потребителю доставляется необходимое количество груза

, jÎN_n

Для решения транспортной задачи чаще всего применяется метод потенциалов. Пусть исходные данные задачи имеют вид

А(а₁,а₂,а₃)=(40;45;70); В(b₁,b₂,b₃)=(48;30;29;40); 3 6 4 3

С= 2 3 1 3

6 5 1 4

Общий объем производства Sa_i=40+45+70=155 больше, чем требуется всем потребителям Sb_j=48+30+29+40=147, т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 155-147=8 единиц, причем тарифы на перевозку в этот пункт условимся считать равными нулю, помня, что переменные, добавляемые к левым частям неравенств для превращения их в уравнения, входят в функцию цели с нулевыми коэффициентами.

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

Таблица 1

Потребл Произв	b1=48	b2=30	b3=29	b4=40	b5=8
a1=40	40 3	6	4	* 3	0	p1=0
a2=45	8 2	30 3	7 1	3	0	p2=-1
a3=70	6	5	22 1	40 4	8 0	p3=-1
q1=3	q2=4	q3=2	q4=5	q5=1

Обозначим через m(p₁, p₂,…, p_m, q₁, q₂,…, q_n) вектор симплексных множителей или потенциалов. Тогда D_ij=mA_ij-c_ij , iÎN_m, jÎN_n, откуда следует

D_ij=p_i+q_j-c_ij , iÎN_m, jÎN_n

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

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

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

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

аналогично, получим: q₂=4, р₃=-1, q₄=5, q₅=1.

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

D₁₂=p₁+q₂-c₁₂=0+4-6= -2

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

D₁₄=2; D₁₅=1; D₂₄=1; D₂₅=0; D₃₁= -4; D₃₂= -2

Находим наибольшую положительную оценку:

mах(D_ij >0)=2=D₁₄,

Для найденной свободной клетки 14 строим цикл пересчета - замкнутую ломаную линию, соседние звенья которой взаимно перпендикулярны, сами звенья параллельны строкам и столбцам таблицы, одна из вершин находится в данной свободной клетке, а все остальные - в занятых клетках. Это будет 14-34-33-23-21-11. Производим перераспределение поставок вдоль цикла пересчета:

40	*	40-r	r	33	7
8	30	7	®	8+r	7-r	®	15	30
22	40	22+r	40-r	29	33

r_max=7

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

Таблица 2

Потребл Произв	b1=48	b2=30	b3=29	b4=40	b5=8
a1=40	33 3	6	4	7 3	0	p1=0
a2=45	15 2	30 3	1	3	0	p2=-1
a3=70	6	* 5	29 1	33 4	8 0	p3=1
q1=3	q2=4	q3=0	q4=3	q5= -1

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

D₁₂= -2; D₁₃= -4; D₁₅= -1; D₂₃= -2; D₂₄= -1; D₂₅= -2; D₃₁= -2; D₃₂=0. Поскольку все D_ij£0 решение является оптимальным:

33 0 0 7

X_оpt1 = 15 30 0 0

0 0 29 33

Однако, так как оценка клетки D₃₂=0, делаем вывод о наличие другого возможного оптимального решения. Для его нахождения строим цикл пересчета клетки 32: 32-22-21-11-14-34, производим перераспределение:

Таблица 3

Потребл Произв	b1=48	b2=30	b3=29	b4=40	b5=8
a1=40	3 3	6	4	37 3	0	p1=0
a2=45	45 2	3	1	3	0	p2=-1
a3=70	6	30 5	29 1	3 4	8 0	p3=1
q1=3	q2=4	q3=0	q4=3	q5= -1

Находим новые потенциалы. Получаем р_i и q_j соответственно равные потенциалам первого базисного оптимального решения (см. табл. 2). Исходя из этого D_max=D₃₂, однако элемент с индексом 32 уже присутствует в базисе, поэтому пересчет не имеет смысла. Таким образом получаем второе и последнее базисное оптимальное решение:

3 0 0 37

X_оpt2 = 45 0 0 0

0 30 29 3

Оптимальное распределение инвестиций