Транспортная задача линейного программирования

Размещено на http://www.allbest.ru/

Транспортная задача линейного программирования

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

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

Производственные мощности предприятий

вариант - 6(95:10=9ост.5+1=6)

Мощности аi по производству запасных частей, т.	Пункты производства Аi
	А1	А2	А3	А4	А5
	450	600	840	760	620

Потребности в запасных частях.

Вариант - 6 (95:6=15ост.5+1=6)

Потребности bj пунктов потребления, т.	Пункт потребления Bj
	В1	В2	В3	В4	В5	В6	В7	В8	В9	В10
	360	410	230	390	100	250	310	350	220	100

Размещение пунктов отправления и назначения на транспортной сети.

Вариант - 4 (95:4=23 ост3+1=4)

Номера узлов	1-2	1-3	1-4	2-3	2-6	2-10	3-5	3-7	3-8	4-5
Расстояние, км	110	75	90	160	69	130	150	170	130	98
Номера узлов	5-8	5-9	6-7	6-10	7-8	7-11	8-9	8-12	9-12	9-13
Расстояние, км	49	112	125	98	117	135	100	95	110	113
Номера узлов	10-11	10-14	11-12	11-14	12-13	12-15	13-15	14-15	14-16	15-16
Расстояние, км	95	117	150	105	190	170	200	140	79	130

Номера узлов размещения мощностей - индексы i:

1, 5 , 6, 11, 16.

Номера узлов размещения потребителей - индексы j:

2 , 3, 7, 8, 9, 10, 12, 13, 14, 15.

Решение:

1. Постановка задачи и формулировка экономико-математической модели.

Железнодорожный транспорт в больших объемах потребляет разнообразные запасные части для поддержания активной части своих производственных фондов в работоспособном состоянии. Запасные части для предприятий железнодорожного транспорта изготавливаются на заводах по ремонту подвижного состава и производству запасных частей и других специализированных предприятиях. Снижение издержек, связанных с обеспечением предприятий железнодорожного транспорта запасными частями весьма актуально. Учитывая большую протяженность железных дорог России, эта задача должна решаться комплексно как для производственной, так и для транспортной составляющей затрат.

Нам известно, сколько груза отправляется из каждого пункта и сколько груза должно поступить в пункт назначения. Причём безразлично, какой именно отправитель будет доставлять груз тому или иному получателю

Требуется так организовать перевозки, чтобы обеспечить минимальный общий пробег груза, т. е. минимизировать затраты на транспортировку.

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

а_i - производственные мощности предприятий по производству запасных частей по пунктам размещения i;

b_j - потребности в запасных частях в пунктах j;

x_ij - объемы перевозок запасных частей между пунктами производства и пунктами потребления i, j;

З_i - затраты на производство единицы (удельные затраты) запасных частей у предприятий по пунктам i;

с_ij - затраты на транспортировку единицы запасных частей между пунктами производства и потребления;

а_i^' - загрузка производственных мощностей предприятий по производству запасных частей по пунктам размещения i.

Тогда экономико-математическая модель может быть сформулирована следующим образом: найти совокупность переменных а_i^', минимизирующих целевую функцию F:

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

2. Определение показателей производственных мощностей.

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

З₁=40,5+ руб.

З₂=40,5+ руб.

З₃=40,5+ руб.

З₄=40,5+ руб.

З₅=40,5+ руб.

3. Расчет затрат на транспортировку единицы запасных частей между пунктами производства и потребления.

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

Расчет кратчайших расстояний между пунктами производства и потребления:

А1 - В1: 110 км

А1 - В2: 75 км

А1 - В 3: 75+170=245 км

А1 - В4: 75+130=205 км;

А1 - В5: 130 км;

А1 - В6: 110+130=240 км;

Аналогично рассчитываем расстояния по каждому пункту потребления.

А2 - В1: 150+160=310 км

А2 - В2:150 км

А2 - В3: 49+117=166 км

А2 - В4: 130+117+79=326 км

А2 - В5: 112 км



Аналогично рассчитываем расстояния по каждому пункту потребления.

А3 - В1: 69 км

А3 - В2: 69+160=229 км

А3 - В3: 125 км

А3 - В4: 125+117=242 км

А3 - В5: 125+117+100=342 км

Аналогично рассчитываем расстояния по каждому пункту потребления.

А4 - В1: 95+130=225 км

А4 - В2: 135+170=305 км

А4 - В3: 135 км

А4 - В4: 135+117=252 км

Аналогично рассчитываем расстояния по каждому пункту потребления.

А5 - В1: 79+117+130=326 км

А5 - В2: 79+105+135+170=484 км

А5 - В3: 79+105+135=319 км

А5 - В4: 79+105+150+95=429 км

Рисунок 1



Таблица 1.

Пункты произв-ва и их мощ-ности	Потребители и их спрос
	B1	B2	B3	B4	B5	B6	B7	B8	B9	B10
	360	410	230	390	100	250	310	350	220	100
A1	450		110		75		245		205		337		240		300		450		357		470
A2	600		310		150		166		49		112		389		144		225		399		314
A3	840		69		229		125		242		342		98		337		527		215		355
A4	760		225		305		135		252		260		95		150		340		105		245
A5	620		326		484		319		429		443		196		300		330		79		130

Затраты на транспортировку одной тонны запасных частей рассчитываем по формуле:

где е - расходная ставка на 10 ткм. Для рассматриваемого рода груза принимается равной 4 руб.; L - минимальное расстояние, рассчитываемое для заданного полигона между пунктами производства и потребления, км.

С₁₁=4*110/10=44;С₁₂=4*75/10=30;С₁₃=4*245/10=98;С₁₄=4*205/10=82; С₁₅=4*337/10=135; С₁₆=4*240/10=96; С₁₇=4*300/10=120;

С₁₈=4*450/10=180; С₁₉=4*357/10=143; С₁₁₀=4*470/10=188.

С₂₁=4*310/10=124; С₂₂=4*150/10=60; С₂₃=4*166/10=66; С₂₄=4*49/10=20;

С₂₅=4*112/10=45; С₂₆=4*389/10=156; С₂₇=4*144/10=58; С₂₈=4*225/10=90;

С₂₉=4*399/10=160; С₂₁₀=4*314/10=126.

С₃₁=4*69/10=28; С₃₂=4*229/10=92; С₃₃=4*125/10=50; С₃₄=4*242/10=97;

С₃₅=4*342/10=137; С₃₆=4*98/10=39; С₃₇=4*337/10=135; С₃₈=4*527/10=211;

С₃₉=4*215/10=86; С₃₁₀=4*355/10=142.

С₄₁=4*225/10=90; С₄₂=4*305/10=122; С₄₃=4*135/10=54; С₄₄=4*252/10=101; С₄₅=4*260/10=104; С₄₆=4*95/10=38; С₄₇=4*150/10=60; С₄₈=4*340/10=136;

С₄₉=4*105/10=42; С₄₁₀=4*245/10=98.

С₅₁=4*326/10=130;С₅₂=4*484/10=194;С₅₃=4*319/10=128;С₅₄=4*429/10=172;

С₅₅=4*443/10=177; С₅₆=4*196/10=78; С₅₇=4*300/10=120; С₅₈=4*330/10=132; С₅₉=49*79/10=32; С₅₁₀=4*130=52.

Результаты представлены в матрице:

Номера пунктов производства	Номера пунктов потребления j
	B1	B2	B3	B4	B5	B6	B7	B8	B9	B10
A1	44	30	98	82	135	96	120	180	143	188
A2	124	60	66	20	45	156	58	90	160	126
A3	28	92	50	97	137	39	135	211	86	142
A4	90	122	54	101	104	38	60	136	42	98
A5	130	194	128	172	177	78	120	132	32	52

Построение расчетной матрицы.

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

Размещено на http://www.allbest.ru/

Затраты на транспортировку и производство запасных частей:

C₁₁=109+44=153;С₁₂=109+30=139;С₁₃=109+98=207;С₁₄=109+82=191; С₁₅=109+135=244; С₁₆=109+96=205; С₁₇=109+120=229;

С₁₈=109+180=289; С₁₉=109+143=252; С₁₁₀=109+188=297.

С₂₁=92+124=216; С₂₂=92+60=152; С₂₃=92+66=158; С₂₄=92+20=112;

С₂₅=92+45=137; С₂₆=92+156=248; С₂₇=92+58=150; С₂₈=92+90=182;

С₂₉=92+160=252;С₂₁₀=92+126=218.

С₃₁=77+28=105;С₃₂=77+92=169;С₃₃=77+50=127;С₃₄=77+97=174;

С₃₅=77+137=214;С₃₆=77+39=116;С₃₇=77+135=212;С₃₈=77+211=288;

С₃₉=77+86=163; С₃₁₀=77+142=219.

С₄₁=81+90=171; С₄₂=81+122=203; С₄₃=81+54=135;С₄₄=81+101=182; С₄₅=81+104=185; С₄₆=81+38=119; С₄₇=81+60=141; С₄₈=81+136; С₄₉=81+42=123; С₄₁₀=81+98=179.

С₅₁=91+130=221; С₅₂=91+194=285; С₅₃=91+128=219; С₅4=91+172=263; С₅₅=91+177=268;С₅₆=91+78=169;С₅₇=91+120=211;С₅₈=91+132=223;

С₅₉=91+32=123; С₅₁₀=91+52=143.

Матрица, отражающая особенности решаемой задачи, принимает вид:

Транспортная таблица

Пункты произв-ва и их мощ-ности	Потребители и их спрос
	B1	B2	B3	B4	B5	B6	B7	B8	B9	B10	ФВ
	360	410	230	390	100	250	310	350	220	100	550
A1	450		153		139		207		191		244		205		229		289		252		297		0
A2	600		216		152		158		112		137		248		150		182		252		218		0
A3	840		105		169		127		174		214		116		212		288		163		219		0
A4	760		171		203		135		182		185		119		141		217		123		179		0
A5	620		221		285		219		263		268		169		211		223		123		143		0



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

Расчет оптимального плана транспортной задачи для расчетной матрицы.

Сформулированная таким образом задача решается с помощью «Поиска решения» в MS Excel.

Результаты решения транспортной задачи целесообразно представить в виде таблицы:

Матрица поставок

Пункты произв-ва и их мощ-ности	Потребители и их спрос
	B1	B2	B3	B4	B5	B6	B7	B8	B9	B10	ФВ
	360	410	230	390	100	250	310	350	220	100	550
A1 450		153		139		207		191		244		205		229		289		252		297		0
		0		410		0		0		0		0	0	0		0	0	40
A2 600		216		152		158		112		137		248		150		182		252		218		0
		0		0	0	390	100	0	0	110	0	0	0
A3 840		105		169		127		174		214		116		212		288		163		219		0
	360	0	230	0	0	250	0	0	0	0	0
A4 760		171		203		135		182		185		119		141		217		123		179		0
	0	0	0	0	0	0	310	240	0	0	210
A5 620		221		285		219		263		268		169		211		223		123		143		0
	0	0	0	0	0	0	0	0	220	100	300

F=367 550 руб.

Расчет показателей оптимального плана загрузки производственных мощностей.

Анализ результатов решения показывает следующее. Предприятие А₁ оправляет реальному потребителю В₂ - 410 т. запасных частей, а остальные 40 т приходятся на фиктивного потребителя. Это говорит о том, что мощности А₁ востребованы не полностью. Следовательно, загрузка А₁ составляет 410 т., т.е. 91%.

Предприятие А₂ отправляет предприятиям В₄, В₅ и В₈ по 390, 100 и 110 т. соответственно, что в сумме составляет - 600 т. Мощности предприятия А₂ полностью вошли в оптимальный план, следовательно загрузка А₂ составляет 100%.

То же самое имеет место и для предприятия А_3. Потребители В₁, В₃ и В₆ получают от данного предприятия по360, 230 и 250 т. соответственно, что сумме составляет 840 т. Иначе говоря, мощности предприятия А₃ полностью вошли в оптимальный план, следовательно загрузка составляет 100% .

Предприятие А₄ поставляет потребителям В7 - 310 т., В₈ -240 т., что в сумме составляет 550 т., а 210 т. запасных частей приходятся на фиктивного потребителя, следовательно мощности А₄ востребованы не полностью и загрузка предприятия составляет 72,4%.

Предприятие А₅ отправляет реальным потребителям В₉ - 250 т. и В₁₀ - 100т. запасных частей, что в сумме составляет 350 т. Оставшиеся 300 т. не востребованы. Следовательно, загрузка предприятия А₅ составляет 48,4%.

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

Производственные расходы:

410109+60092+84077+55081+35091=240 970руб.

Транспортные расходы составляют:

367 550 -240 970=126 580 руб.

Из данных расчетов следует, что на транспортную составляющую приходится 34,4% (126580*100/367550=34,4).

Высокий удельный вес транспортной составляющей, свыше 5% свидетельствует о том, что транспортный фактор оказывает существенное значение на загрузку производственных мощностей для данной транспортной сети.



Список литературы

1. Афанасьев, М.Ю. Исследование операций в экономике: модели, задачи, решения: учеб. пособие для экономических вузов / - М. : ИНФРА-М, 2003.

2. Вентцель, Е.С. Исследование операций: задачи, принципы, методология [Текст] : учеб. пособие для вузов / Е.С. Вентцель. - 4-е изд., стер. - М. : Дрофа, 2006. - 206 с. - (Высшее образование).

3. Курицкий, Б.Я. Поиск оптимальных решений средствами Excel 7.0 / Б.Я. Курицкий. - СПб. : BHV-Санкт-Петербург, 1997.

4. Орлова, И.В. Экономико-математические методы и модели: компьютерное моделирование : учеб. пособие / И.В. Орлова, В.А. Половников. - М. : Вузовский учеб., 2009.

5. Экономико-математические методы и модели [Текст] : учеб. пособие для вузов / Н.И. Холод [и др.] ; под общ. ред. А.В. Кузнецова. - 2-е изд. - Минск : БГЭУ, 2000.

Размещено на Allbest.ru

...