2.2. Многопродуктовая транспортная задача

ПОСТАНОВКА ЗАДАЧИ:

По условиям контракта торгово-посредническая фирма должна поставить каждому из покупателей l видов товаров в количестве по цене за единицу товара. Эти товары можно закупить у производителей по цене за единицу товара. Известны количества товара , имеющегося у производителя , а также стоимости перевозки единицы товара от производителя к покупателю .

ТРЕБУЕТСЯ:

1. Построить математическую модель поставленной задачи, максимизирующую прибыль фирмы от реализации всех сделок в виде задачи линейного программирования.

2. Методом потенциалов найти оптимальный план закупок, перевозок и поставок по каждому товару от каждого производителя к каждому покупателю и сумму прибыли.

Приведем пример решения задачи при l = 2, m = 2, n = 3.

Исходные данные:

a11	a12	a21	a22	a31	a32	s11	s12
245	245	445	105	295	55	5	4

s21	s22	s31	s32	b11	b12	b21	b22
2	1	4	5	305	175	795	205

c111	c112	c121	c122	c211	c212	c221	c222
3	4	5	3	5	3	4	4

c311	c312	c321	c322	p11	p12	p21	p22
4	2	2	3	15	16	16	17

Решение.

1) Для составления математической модели введем неизвестные

– количество товара , покупаемое у производителя для перевозки

потребителю . Индексы: i = 1, 2, 3 – номер производителя продукции;

j = 1, 2 – номер потребителя продукции; k = 1, 2 – номер товара. Найдем тарифы , т.е. прибыли на одну единицу товара , покупаемое у производителя для продажи потребителю . Эти прибыли состоят из цены продажи 1 единицы товара за вычетом цены покупки и стоимости перевозки, т.е. . Для примера приведем вычисление : , т. е. f₃₁₂ = 16 – 5 – 2 = 9. Значения всех полученных коэффициентов приведены в таблице:

fijk	f111	f112	f121	f122	f211	f212	f221	f222	f311	f312	f321	f322
тариф	7	8	6	10	8	12	10	12	7	9	10	9

Прибыль фирмы представляется выражением , где сумма берется по всем возможным значениям индексов i, j, k. По условию, выражение F следует максимизировать, т.е. F является целевой функцией поставленной задачи. Так как операции над товарами и можно производить по отдельности и выражение F представляется в виде суммы двух слагаемых , сгруппированных по товарам , , то поставленная задача сводится к решению двух оптимизационных задач. Ограничения для неизвестных диктуются наличием соответствующих товаров у производителей и потребностью в них покупателей. В результате приходим к двум задачам линейного программирования, которые относятся к задачам транспортного типа:

Задача 1 (по товару )

≥ 0.

Задача 2 (по товару )

≥ 0.

Как видно, решение поставленной задачи сводится к решению двух задач транспортного типа. В общем случае (при k > 2) мы получим k таких задач.

2) Для решения задач 1, 2 методом потенциалов, сопоставим суммарное наличие каждого товара у производителей и суммарные потребности покупателей.

= 245 + 445 + 295 = 985, = 305 + 795 = 1100.

Потребности покупателей превышают наличие товара T₁ .Вводим фиктивного производителя A₄ с количеством товара a₄₁ = 1100 – 985 = 115.

= 245 + 105 + 55 = 405, = 175 + 205 = 380.

По товару вводим фиктивного покупателя с потребностью = 25.

Получаем закрытые модели двух транспортных задач. Для их решения составляем две таблицы. В верхних правых углах клеток выписаны тарифы и . Для фиктивных производителей и покупателей тарифы равны нулю. Последние строки и столбцы таблиц служат для записи потенциалов.

Таблица 2.2.1 (к задаче 1)

Производители	Покупатели		ai1	ui
	B1	B2
A1	7 245	6 7	245	7
A2	8 10	10 445	445	10
A3	7 10	10 295	295	10
A4	0 60	0 55	115	0
bj1	305	795	1100	–
vj	0	0	–	–

Начальные планы распределения товаров определены по методу максимальной прибыли, т.е. в первую очередь заполнялись по максимуму клетки с наибольшими тарифами. Более конкретно, просматривая таблицу 2.2.1, замечаем, что максимальные тарифы 10 стоят в клетках и . В эти клетки ставим числа 445 и 295. При этом запасы производителей и исчерпаны. Далее, в клетку ставим 245 так как . При этом товар производителей полностью распределён. Распределяем теперь товар от фиктивного производителя, т.е. в клетки и ставим 60 и 55.

Таблица 2.2.2 (к задаче 2)

Производители	Покупатели
	B1	B2	B3	ai2	ui
A1	8 120	10 100	0 25	245	0
A2	12 10	12 105	0 2	105	2
A3	9 55	9 11	0 1	55	1
bj2	175	205	25	405	–
vj	8	10	0	–	–

Полученный начальный план проверим на оптимальность. План невырожденный, так как число занятых клеток (5) равно m + n – 1 (m и n – число строк и столбцов распределительной матрицы). Обозначим через и потенциалы строк и столбцов. Для их нахождения отметим, что в занятых клетках сумма потенциалов строки и столбца должна равняться тарифу клетки. Получаем в данном случае 5 уравнений с 6-ю неизвестными:

, , , , .

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

Аналогично, таблица 2.2.2 заполнена в следующей последовательности:

– 105, – 100, – 55, – 120, – 25. Полученный план невырожденный, так как содержит 3 + 3 – 1 = 5 занятых клеток. Проверим его на оптимальность. Выпишем систему уравнений для нахождения потенциалов: , , , , .

Полагая , последовательно находим:

, , , , .

Для свободной клетки сумма потенциалов = 8 + 2 = , т.е. клетка является перспективной.

Составляем цикл пересчета, одной из вершин которого является эта клетка: , , , . В свободную клетку условно запишем знак (+), в следующую (по часовой стрелке) – знак (–), в следующую – знак (+) и т.д. В отрицательных клетках выбираем наименьшее число (105). В клетки со знаком (+) прибавляем это число, а из клеток со знаком (–) – вычитаем:

Таблица 2.2.3 (к задаче 2)

Произво-дители	Покупатели
	B1	B2	B3	ai2	ui
A1	8 15	10 205	0 25	245	0
A2	12 105	12 14	0 4	105	4
A3	9 55	9 11	0 1	55	1
bj2	175	205	25	405	–
vj	8	10	0	–	–

120 (-)

→

100 (+)

↑ ↓

0 (+)

←

105 (-)

Осуществляя сдвиг

по циклу, получаем

таблицу 3.

План распределения товара T₂, заданный таблицей 2.2. 3, оптимален.

Сумма прибыли = (7∙245 + 10∙445 + 10∙295) + (8∙15 + 10∙205 +12∙105 + 9∙105) = 3865 + 9115 = 12980.

Ответ:

= 245, = 445, = 295, = 15, = 205, = 105,

= 55. Остальные = 0. Максимальная прибыль равна 12980.