Транспортно-производственная модель с целочисленными и непрерывными переменными

           для всех s

           для всех i

 

 

3.a. Пример 1: Необходимо произвести прогноз размещения производства однородного продукта и определить объём его перевозок потребителям с учётом минимизации общей суммы производственных и транспортных расходов. Возьмем два предприятия, по каждому из которых разработана два альтернативных варианта их развития, и три потребителя. Объёмы производства по вариантам, потребность в продукции потребителей, а также удельные производственные и транспортные расходы представлены в таблице №1.

Таблица 1 - Исходные данные для однопродуктовой производственнотранспортной задачи в дискретной постановке.

Предприятия	Варианты их развития	Объем производства продукции	Удельные производственные затраты, ден.ед.	Потребители
				1	2	3
				Потребность в продукции, ед
				259	162	97
				Удельные транспортные расходы, ден.ед.
1	1	222()	81,4	33	18	9
	2	296()	62,9	33	18	9
2	1	148()	85,1	2,4	56	67
	2	222()	81,4		56	67

 

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

.

 

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

которой мы и приступили.

 

 

 

 

 

 

 

 

 

 

 

 

^{0 или 1}

 

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

Для решения подобных задач можно  использовать два подхода.

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

На втором шаге нецелочисленное  решение доводится до целочисленного методом, основывающимся на идеях дельта-метода А.Г.Аганбегяна. Этот метод особенно эффективен, когда количество переменных в задаче значительно превосходит количество ограничений. Теоретически доказывается, что количество целочисленных решений гарантируется для (п- т) переменных, где п - число переменных, а m - число ограничений.

 

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

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

Результат решения задачи: X*=(0;1;0;1;0;0;0;37;162;97;0;0;0;222;0;0), f(X*)=42231,8

Представим эти результаты в табличной форме.

Таблица 2 - Объемы производства продукции  на двух предприятиях и ее распределение по потребителям

предприятия	Варианты	Объём	Величина	поставки	продукции	Всего
	развития	производства	потребителям, ед.			поставляется,
		продукции,	1	2	3	ед.
		ед.
1	2	296	37	162	97	296
2	2	222	222	-	-	222
итого		518	259	162	97	518

 

Как видно, получено не только оптимальное, но и целочисленное решение. Оба предприятия целесообразно развивать по второму варианту. Причем первое предприятие должно поставить продукцию всем потребителям соответственно 37, 162 и 97 ед., а второе - только первому - 222 ед. Относительная эффективность первого предприятия выше второго в 3,5 раза. Об этом можно судить по величине двойственных оценок 8-го и 9-го ограничений задачи, имеющих в данных условиях рентный характер.

 

 

 

 

 

 

Таблица 4 - Расширенная модель однопродуктовой производственно - транспортной задачи в дискретной постановке.

Переменные               Ограничения	Предприятие и варианты их развития							Варианты прикрепления предприятий
	Варианты развития первого предприятия			Варианты развития второго предприятия				Первое предприятие
								Возможные прикрепления по:
	1	2		1		2		1 варианту развития					2 вариату развития
	X11	X12		X21		X22		X111		X121		X131	X112		X122	X132
1)согласование объемов производства  и сбыта продукции	222							-1		-1		-1
2) согласование объемов производства  и сбыта продукции		296											-1		-1	-1
3)согласование объемов производства  и сбыта продукции				148
4)согласование объемов производства  и сбыта продукции						222
5)удовлетворение потребностей  потребителей в продукции								1					1
6)удовлетворение потребностей  потребителей в продукции										1					1
7)удовлетворение потребностей  потребителей в продукции												1				1
8) ограничение целочисленности вариантов развития первого предприятия	1	1
9)ограничение целочисленности вариантов развития первого предприятия				1		1
Затраты по производству и транспортировке  продукции ден.ед.	18071	18618		12595		18071		33		18		9	33		18	9
Переменные               Ограничения	Варианты прикрепления предприятий													Объемы и типы ограничений
	Второе предприятие
	Возможные прикрепления по:
	1 варианту развития						2 вариату развития
	X111		X121		X131		X112		X122		X132
1)согласование объемов производства  и сбыта продукции														≥0
2) согласование объемов производства  и сбыта продукции														≥0
3)согласование объемов производства  и сбыта продукции														≥0
4)согласование объемов производства  и сбыта продукции	-1		-1		-1									≥0
5)удовлетворение потребностей  потребителей в продукции							-1		-1		-1			≥259
6)удовлетворение потребностей  потребителей в продукции														≥162
7)удовлетворение потребностей  потребителей в продукции	1						1							≥97
8) ограничение целочисленности вариантов развития первого предприятия			1						1					=1
9)ограничение целочисленности вариантов развития первого предприятия					1						1			=1
Затраты по производству и транспортировке  продукции ден.ед.	2,4		56		67		2,4		56		67			min

 

 

 

Содержание транспортно-производственной модели с непрерывными переменными рассмотрим на примере трехэтапной задачи прогноза развития, размещения и специализации производства продукции отрасли с одновременной оптимизацией перевозок сырья и готовой продукции.

 

i - номер предприятия - поставщика сырьевых ресурсов (i = 1-т)

j - номер завода, перерабатывающего сырьё i-х поставщиков (j = 1- п);

 р - номер потребителя продукции j-х заводов (р = 1-и);

k - номер вида продукции, поставляемой j -ми заводами р-м потребителям (к=1-r);

Q_i - максимально возможный объём производства сырья i -м предприятием;

В_j - минимальная, максимально - возможная или фиксированная мощность j-го завода;

a_kij - выход k-й продукции из 1 ед. сырья, поставляемого i-м поставщиком j-му заводу;

D_pk - прогнозируемая потребность р-го потребителя в k-ом продукте;

С_i^pk - затраты на производство 1 ед. продукции у i-го поставщика;

d_ijⁱ - транспортные расходы на доставку 1 ед. сырья от i -го поставщика до j -

го завода;

q_ij -себестоимость переработки 1 ед. сырья, поставляемого i -м предприятием  j-му заводу;

F_jpk - транспортные расходы на доставку 1 ед. к -го продукта j -м заводам p-му потребителю;

X_i - искомый объём производства (добычи) сырьевых ресурсов i-м предприятием;

Y_ij - искомый объём переработки сырья j-м заводом поставляемого i-м предприятием;

Z_ipk- искомый объём поставки К-го продукта j -м заводом р-му потребителю;

 

В принятых обозначениях при постановке задачи на минимум затрат она сводится к следующему: определить такие значения переменных X_i, Y_ij и

Z_ipk, при которых минимизируется величина целевой функции

 

и выполняется  условия:

X_i≤Q_i  (i=1-m)

- ограничение объёмов производства сырья на i -х предприятиях;

 

- ограничения мощности j- х заводов;

 

- ограничения  по увязке объёмов производства (добыча) и переработке сырья

 

 

- ограничения по увязке объёмов производства продукции и её поставке потребителям

 

- ограничение  по удовлетворению потребностей  потребителей в продукции j -х заводов;

X_i,Y_ij,Z_ipk≥0

-ограничения неотрицательности переменных величин.

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

 

3.б. Пример 2: Двум сахарным заводам могут поставлять сырье трём сельскохозяйственным предприятия. Первый - завод действующий. Его, мощность (6200 т перерабатываемой сахарной свеклы) необходимо сохранить. Предусматривается возможность расширения мощности данного завода. Второй завод может быть построен, если окажется невыгодным расширять мощность первого завода. Производимая заводами продукция (песок сахарный и патока) поставляется двум потребителям, потребности которых строго ограничены.

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

Себестоимость переработки 1 т сахарной свеклы на сахарных заводах - существенно зависит  от содержания сахара в сырье и  от сроков его переработки. Чем выше процентное содержание сахара в свекле, тем меньше ее нужно переработать для получения 1 т сахара. Это окажет прямое влияние на снижение удельных производственных затрат.

Таблица 5 - Объемы производства сырья, затраты на его производство, переработку  и доставку потребителям.

 

Сельхоз предприятия	Объём производства сахарной свёклы	Себестоимость производства сахарной свёклы	Потребители сырья, удельные затраты на его перевозку, ден.ед./т		Себестоимость переработки 1 т. сырья, поставляемого i-предприятием, ден. ед./т
			1	2	1-й завод	2-й завод
1	3000	23,13	4,85	5,3	32,1	29,9
2	2100	18,4	5,6	4,9	24,1	22,4
3	4178	26,1	5,1	6,1	32,4	30,1

 

Таблица 6 - Выход k-ой продукции из 1 т сырья i-x поставщиков и удельные транспортные расходы на ее доставку потребителям.

 

заводы	Вид продукции	Выход конечной продукции поставщиков, %		из сырья i -х	Удельные транспортные расходы на перевозку продукции потребителям, ден./т
		1-й поставщик	2-й поставщик	3-й поставщик	1-й потребитель	2-й потребитель
1	Песок	11,2	17,7	10,2	7,82	8,4
	сахарный патока	5,1	5,6	4,7	8,3	9,3
2	Песок	12,0	19,0	11,0	8,1	9,1
	сахарный патока	5,5	6,0	5,0	8,9	10,0