Задание № 13

В пунктах производится продукция в количествах единиц. Себестоимость единицы продукции в i-м пункте равна . Готовая продукция поставляется в пункты , потребности которых составляют единиц. Стоимость перевозки единицы продукции из пункта в пункт заданы матрицей [ ].

Требуется:

1) методом потенциалов найти план перевозок продукции, при котором минимизируются суммарные затраты по ее изготовлению и доставке потребителям;

2) установить пункты, в которых остается нераспределенная продукция, и указать ее объем.

 

b1
b2
b3
b4
c11
c12
c13
c14
c21
c22
c23
c24
c31
c32
c33
c34
a1
a2
a3

 

Решение

Так как то имеем транспортную задачу открытого типа. Вводим фиктивного потребителя В₅ с потребностью . Тарифы по перевозкам и себестоимость единицы продукции для этого потребителя принимаем равными нулю. Получаем новую таблицу исходных данных.

Здесь в клетках (i,j) стоят суммы c_ij+c_i. Но так как по условию c_i не заданы, то получаем (полагаем c_i=0): c_ij+c_i=c_ij, то есть в клетках (i,j) ставим c_ij.

 

Bj Ai	B1	B2	B3	B4	В5	ai
A1
A2
A3
bj						Всего: 1150

 

Начальный опорный план находим по правилу минимального элемента.

Это правило заключается в следующем.

Просматриваются все тарифы и, в первую очередь, заполняется клетка с минимальным значением тарифа (фиктивные клетки рассматриваются в последнюю очередь). При этом в эту клетку записывается максимально возможное значение поставки. Затем из рассмотрения исключают строку, соответствующую поставщику, запасы которого полностью израсходованы, или столбец, соответствующий потребителю, спрос которого полностью удовлетворен. После этого из оставшихся клеток таблицы снова выбирают клетку с наименьшим тарифом. Процесс распределения заканчивается, когда все запасы поставщиков исчерпаны, а спрос потребителей полностью удовлетворен. В результате получаем решение, которое должно содержать m+n-1 загруженных клеток. В процессе первоначального заполнения таблицы могут быть одновременно исключены строка и столбец. Так бывает, когда полностью исчерпывается запас груза и удовлетворяется спрос. В этом случае свободную клетку, которая не образует цикла с занятыми, надо записать 0 - «нуль-загрузка», условно считая эту клетку занятой.

Заполненная таким образом таблица приведена ниже.

 

Bj Ai	B1	B2	B3	B4	В5	ai
A1	2	6	3	5	0
A2	8	7	10	5	0
A3	2	7	5	3	0
bj

 

Далее решаем задачу методом потенциалов. Для этого каждой клетке (i;j) таблицы сопоставим пару чисел (u_i; v_j). Одно из этих чисел выбирается произвольно (например, u₁=0). Остальные числа подбираются так, чтобы для занятых клеток выполнялось равенство: u_i+v_j=c_ij, где c_ij – тариф клетки (i;j) (стоит в правом верхнем углу клетки). Найденные потенциалы приведены в таблице ниже.

 

Bj Ai	B1	B2	B3	B4	В5	ai	ui
A1	2	6	3	5	0		u1=0
A2	8	7	10 250 -	5 +	0		u2=5
A3	2	7	5 150 +	3 150 -	0		u3=0
bj
vj	v1=2	v2=2	v3=5	v4=3	v5=-5

 

Оценки свободных клеток:

Так как есть отрицательные оценки s₁₃, s₂₄, то составляем цикл и строим новый план. Циклом называется ломаная линия, вершины которой расположены в занятых клетках таблицы (кроме одной вершины, которая находится в свободной клетке с наименьшей отрицательной оценкой), а звенья - вдоль строк и столбцов, причем в вершине встречается ровно два звена, одно из которых находится в строке, а другое - в столбце. Если ломаная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами. Вершине в свободной клетке присваивается знак «+», а далее по очереди в вершинах следуют знаки минус и плюс.

Для построения нового плана по клеткам цикла перемещаем минимальную величину загрузки клеток, в которых стоит знак минус. Эту величину прибавляем к загрузке клеток с «плюсом», и вычитаем из загрузки клеток с «минусом». Находим также новые потенциалы.

 

Bj Ai	B1	B2	B3	B4	В5	ai	ui
A1	2 250 -	6	3 +	5	0		u1=0
A2	8	7	10	5	0		u2=5
A3	2 50 +	7	5 300 -	3	0		u3=0
bj
vj	v1=2	v2=2	v3=5	v4=0	v5=-5

 

Оценки свободных клеток:

Так как есть отрицательная оценка s₁₃, то строим цикл и составляем новый план.

 

Bj Ai	B1	B2	B3	B4	В5	ai	ui
A1	2	6	3	5	0		u1=0
A2	8	7	10	5	0		u2=7
A3	2	7	5	3	0		u3=2
bj
vj	v1=0	v2=0	v3=3	v4=-2	v5=-7

 

Оценки свободных клеток:

Так как все оценки неотрицательны, то получен оптимальный план (пятый столбец – фиктивный):

Минимальные суммарные затраты:

д.е.

По матрице Х^* заключаем, что у поставщика А₂ останется 150 ед. нераспределённой продукции, так как она поставляется фиктивному потребителю В₅ .