Математическое моделирования, ИДЗ транспортная задача

МИНИСТЕРСТВО ОБРАЗОВАНИЯ  И НАУКИ РФ

Государственное образовательное  учреждение

высшего профессионального  образования

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ

ТОМСКИЙ ПОЛИТЕХНИЧЕСКИЙ  УНИВЕРСИТЕТ»

 

 

 

 

Институт  природных ресурсов

Специальность - Экономика и управление на предприятии

(в нефтяной  и газовой промышленности)

Кафедра -  Экономики природных ресурсов

 

 

 

Практическая  работа №3

Вариант 7

 

Выполнил  студент гр. 2э90

 

М.Л.Ким

Проверила: О.В. Марухина

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Томск 2012

 

 

 

Тема. Решение транспортной задачи

Задание. Продукция определенного вида производится в городах , и и потребляется в городах , , и .

В таблице  указаны: объем производства, спрос, стоимость перевозки единицы  продукции.

Составить оптимальный план перевозки продукции, при котором стоимость всех перевозок  будет минимальна.

Предварительно следует проверить, сбалансирована ли данная транспортная задача. Если задача не сбалансирована, то нужно ввести фиктивных потребителей или производителей, добавляя к исходной таблице столбцы или строки.

Произво-дители	Потребители				Объем производства
	7	43	39	10	41
	10	33	46	16	22
	46	17	27	47	61
Спрос	38	30	19	87

Так как  данная задача открытого типа, необходимо ее привести к задаче закрытого типа. В данном случае спрос превышает  Объем производства и в связи  с этим необходимо добавить строку, т.е. фиктивного производителя.

Построим  экономико-математическую модель данной задачи, обозначив через   объем  поставляемого товара от i -го поставщика к j- му потребителю. Чтобы запасы каждого поставщика были полностью реализованы, должны быть справедливы уравнения баланса для каждой строки таблицы поставок, т. е. выполняться равенства

 

 

Чтобы спрос  каждого из потребителей был удовлетворён, должны быть справедливы уравнения  баланса для каждого столбца  таблицы поставок, то есть

 

 

Поскольку объём  перевозимого груза величина неотрицательная, то должны выполняться ограничения  на переменные :

Суммарные затраты F на перевозку определяются указанными в таблице поставок тарифами перевозок и размерами поставок/

Решить  транспортную задачу − значит, на множестве неотрицательных решений системы ограничений найти такое решение, при котором линейная функция принимает минимальное значение.

Для нахождения начального решения используем метод  северо-западного угла:

 

Производители	Потребители				Объем производства
	7 38	43 3	39	10	41
	10	33 22	46	16	22
	46	17 5	27 19	47 37	61
A4	0	0	0	0 50	50
Спрос	38	30	19	87

Найденный опорный план записывается матрицей

X1=

F=38*7+43*3+22*33+5*17+19*27+47*37=266+129+726+85+513+1739=3458

Метод потенциалов

Для потенциалов  поставщиков  и потребителей , соответствующих занятым клеткам, справедливы равенства

Так как  занятых клеток на одну меньше, чем  число потенциалов, значение одного из потенциалов (все равно какого) назначается произвольно и может быть любым действительным числом (обычно полагают равным нулю, чтобы не усложнять вычисления остальных потенциалов).

Оценки свободных клеток таблицы поставок рассчитываются по формулам

 

_{Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.}

	1	2	3	4	Запасы
1	7[38]	43	39	10[3]	41
2	10	33	46	16[22]	22
3	46	17[30]	27[19]	47[12]	61
4	0	0	0	0[50]	50
Потребности	38	30	19	87

 

Вычислим потенциалы для занятых  клеток и результаты расчётов поместим в табл.

Производители	Потребители				Объем производства
	7[38]	43	39	10[3]	41
	10	33	46	16:[22]	22
	46	17 [30]	27[19]	47[12]	61
A4	0	0	0	0[50]	50
Спрос	38	30	19	87

Подсчитаем  число занятых клеток таблицы, их 7, а должно быть m + n - 1 = 7. Следовательно, опорный план является невырожденным.

Значение  целевой функции для этого  опорного плана равно:

Проверим  оптимальность опорного плана. Найдем предварительные потенциалы ui, vi. по занятым клеткам таблицы, в которых ui + vi = cij, полагая, что u1 = 0.

 

 

 

 

 

 

 

Производители	Потребители				Объем производства
	7[38] [-]	43	39	10[3] [+]	41	U1 = 0
	10 [+]	33	46	16:[22] [-]	22	U2 = 6
	46	17 [30]	27[19]	47[12]	61	U3 = 37
A4	0	0	0	0[50]	50	U4 = -10
Спрос	38	30	19	87
	V1 = 7	V2 = -20	V3 = -10	V4 = 10

 

Вычислим потенциалы для занятых  клеток

(1,4) U1=0, u1+v1=10. V4=10

(1,1) U1+V1=7, V1=7

(1,4) U1+V4=10, U2=6

(3,4) U3+V4=47, U3=37

(3,3) U3+V3=27, V3=-10

(3,2) U3+V2=17,V2=-20

 (4,4) U4+V4=0, U4=-10

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

 (1,2)  43-(0-20)=63>0

(1,3) 39-(0-10)=29>0

(2,1) 10-(6+7)=-3<0

(2,2) 33-(6-20)=47>0

(2,3) 46-(6-10)=50>0

(3,1) 46-(37+7)=50>0

 (4,1) 0-(-10+7)=3>0

 (4,2) 0-(-10-20)=30>0

(4,3) 0-(-10-10)=20>0

Опорный план не является оптимальным, так как  существуют оценки свободных клеток, для которых ui + vi > cij

Выбираем  максимальную оценку свободной клетки (2;1): 10

Для этого  в перспективную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки  «-», «+», «-».

Цикл приведен в таблице (2,1; 2,4; 1,4; 1,1; ).

Из грузов хij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 4) = 22. Прибавляем 22 к объемам грузов, стоящих в плюсовых клетках и вычитаем 22 из Хij, стоящих в минусовых клетках. В результате получим новый опорный план.

 

 

Производители	Потребители				Объем производства
	7[16]	43	39	10[25]	41	U1 = 0
	10[22]	33	46	16	22	U2 = 3
	46	17[30]	27[19]	47[12]	61	U3 = 37
A4	0	0	0	0[50]	50	U4 = 10
Спрос	38	30	19	87
	V1 = 7	V2 = -20	V3 = -10	V4 = 10

Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют  условию ui + vi <= cij.

Минимальные затраты составят:

F(x) = 7*16 + 10*25 + 10*22 + 17*30 + 27*19 + 47*12 + 0*50 = 2169

Все вычисления и комментарии к полученным результатам  доступны в расширенном режиме. Также  приведено решение двойственной транспортной задачи и анализ оптимального плана.