Мат. методы (Новичихин)

1

Конспект лекций по дисциплине «Экономико-математические методы

в организации транспортного производства»

Основная литература:

1 Алесинская Т.В. Учебно-методическое пособие по курсу «Экономикоматематические методы и модели. Линейное программирование» / Т.В. Алесинская, В.Д. Сербин, А.В. Катаев. – Таганрог: Изд-во ТРТУ, 2001. – 79 с.

2Балашевич В.А., Андронов А.М. Экономико-математическое моделирование производственных систем / В.А. Балашевич, А.М. Андронов. – Мн.: БГУ, 1995.

3Васильков Ю.В. Компьютерные технологии вычислений в математическом моделировании / Ю.В. Васильков, Н.Н. Василькова. – М., 1999.

4Воскресенская Т.П. Решение транспортных задач линейного программирования: Методические указания к практическим занятиям / Т.П. Воскресенская. – Новокузнецк: СибГИУ, 1998 г.

5Воскресенская Т.П. Использование транспортной задачи для маршрутизации автомобильных перевозок: Методические указания к практическим занятиям / Т.П. Воскресенская. – Новокузнецк: СибГИУ, 1998 г.

6Глухов В.В. Математические методы и модели для менеджмента. 2-е изд., испр. и доп. / В.В. Глухов, М.Д. Медников, С.Б. Коробко. – СПб.: Изд. «Лань», 2005.

–528 с.

7Поттосина С.А. Экономико-математические модели и методы: Учеб. пособие / С.А. Поттосина, В.А. Журавлев. – Мн.: БГУИР, 2003. – 94 с.

8Экономико-математическое моделирование: учебник / под общ. ред. И.Н. Дрогобыцкого. – 2- е изд., стереотипное. – М: Издательство «Экзамен», 2006. – 798 с.

Дополнительная литература:

1Акулиничев В.М. Математические методы в эксплуатации железных дорог. –

М.: Транспорт, 1981. – 223 с.

2Белов И.В. Математические методы в планировании на железнодорожном транспорте / И.В. Белов, А.В. Каплан. – М.: Транспорт, 1972. – 248 с.

3Калихман И.Л. Войтенко М.А. Динамическое программирование в примерах и задачах / И.Л. Калихман, М.А. Войтенко. – М.: Высшая школа, 1979. – 125 с.

4Кожин А.П. Математические методы в планировании и управлении грузовыми автомобильными перевозками / А.П. Кожин, В.Н. Мезенцев. – М.: Транпорт, 1994. – 304 с.

2

Введение

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

Широкие возможности эффективного использования экономикоматематических моделей в практике плановой работы возникают в связи с созданием на производстве автоматизированных систем управления (АСУ).

Основными функциями АСУ являются:

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

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

∙прогнозирование и разработка оптимальных планов на перспективу.

1 КРИТЕРИЙ И ПОКАЗАТЕЛИ ОПТИМАЛЬНОСТИ ПРИ ПЛАНИРОВАНИИ ТРАНСПОРТА 1.1 Критерий оптимальности

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

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

Критерий оптимальности плана (решения) должен обеспечивать наилучшее отражение интересов народного хозяйства.

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

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

3

1.2 Показатели оптимальности

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

∙обеспечивать в плане сочетание экономических интересов одноцелевой сферы производства и государства в целом;

∙достоверно отражать все требования критерия и их меру, которые могут варьироваться по вариантам в зависимости от характера решаемых задач и условий, для которых выбирается оптимальное решение;

∙предусматривать возможность соизмерения и сопоставимость меры показателей по элементам затрат и операциям производственного процесса;

∙гарантировать правильность приведения друг к другу различных по своей природе стоимостных затрат;

∙при решении любой конкретной задачи оптимум с использованием математических методов и ЭВМ показатель оптимальности должен быть единственным

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

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

Целевая функция в этом случае имеет общий вид:

F = ∑∑cij xij → min

(1)

i j

cij - затраты в стоимостном или натуральном выражении на перевозку единицы груза из пункта i в пункт j;

xij – количество груза в тех же единицах, доставляемое из i в j.

Часто показателем оптимальности, используемым при планировании перевозок, принимается кратчайшее расстояние. Целевая функция в этом случае имеет вид:

F = ∑∑lij xij → min	(2)
i j

lij - расстояние следования грузов по путям сообщения из пункта i в пункт j. Оптимальным будет план, который имеет минимальную транспортную работу

по всем перевозкам этого плана.

4

Совокупным показателем, в котором возможно отразить важнейшие характеристики критерия оптимальности, могут быть только стоимостные:

1.cij = Cij

Cij - эксплуатационные расходы транспорта, зависящие от объёма перевозок.

2.cij = Cij + (kij + M ij )× Ен

kij - удельные капитальные вложения в подвижной состав;

Mij - удельная потребность хозяйства в оборотных средствах на грузы в пути; Eн - нормативный коэффициент эффективности капитальных вложений.

3.cij = Dij

Dij - полная тарифная плата за перевозку груза.

Наиболее полно критерий оптимальности выражается в показателе «приведенные затраты». Целевая функция имеет вид:

F = ∑∑[cij + (kij + M ij )Eн]xij → min (3) i j

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

2 ТРАНСПОРТНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

2.1 Экономико-математическая формулировка транспортной задачи

Рационализация транспортных связей одна из важных задач народного хозяй-

ства.

Удельный вес транспортных затрат в цене отдельных видов продукции составляет от 40 до 20%.

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

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

Для задач линейного программирования характерны три следующих условия:

5

1.наличие системы взаимосвязанных факторов;

2.строгое определение критерия оптимальности;

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

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

ипотребностей.

Открытые транспортные задачи – это задачи прикрепления поставщиков к потребителям в условиях несбалансированных ресурсов и потребностей. С помощью транспортных задач открытого типа находят оптимальные варианты размещения производства с учетом транспортного фактора.

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

Имеется m отправителей и n получателей однородного или взаимозаменяемого вида ресурсов. Заданы размеры ресурсов отправителей и потребности в ресурсах потребителей. Требуется составить такой план перевозок этой продукции (ресурсов), чтобы общая сумма затрат на её транспортирование была бы минимальной.

В математической форме записывается это следующим образом: - составляется матрица (таблица 1)

Таблица 1

Потреб.

ai

Постав.

P1

P2

Pj

…

P

n

R1

x11

c11

c12

c1j

…

…

x1n

c1n

a1

x12

x1j

R2

x21

c21

c22

c2j

…

…

x2n

c2n

a2

x22

x2j

Ri

xi1

ci1

ci2

cij

…

…

xin

cin

ai

xi2

xij

Rm

xm1

cm1

cm2

cmj

…

…

xmn

cmn

am

xm2

xmj

bj

b1

b2

bj

…

bn

∑ i

= ∑

j

i a

j b

где R1, R2,…,R

i,…,R

m – отправители ресурсов (поставщики), общее число ко-

торых «m»;

P1, P2,…,P j,…,P

n – потребители ресурсов, общее число которых «n»;

ai

–

размеры ресурсов у поставщиков;

bj

–

размеры потребностей ресурсов у потребителей;

cij

–

величина затрат на перемещение единицы ресурсов между i-м поставщи-

ком и j-м потребителем;

xij

–

размер перемещения ресурсов от i-го поставщика j-му потребителю.

6

Индексы обозначают номера поставщиков и потребителей. Размерность величин xij и ai и bj должны быть в одних и тех же единицах.

Составить экономико-математическую модель – это значит выразить количественно в математической форме через систему уравнений и неравенств взаимосвязь факторов и условий рассматриваемого экономического процесса.

По данным табл.1 составляются следующие уравнения

x11 + x12 + ... + x1 j + x1n = a1
x21 + x22 + ... + x2 j + x2n = a2
xi1 + xi 2 + ... + xij + xin = ai
+	xm2	+ ... +	xmj	+	xmn	=
xm1							am

Система уравнений, показывающая взаимосвязь факторов и ограничений по ресурсам каждого поставщика.

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

x11 + x21 + ... + xi1 + ... + xm1 = b1
x12 + x22 + ... + xi 2 + ... + xm2 = b2
xij + x2 j + ... + xij + ... + xmj = bj
xin + x2n + ... + xin + ... + xmn = bn

Система ограничения по потребностям. Эти уравнения можно записать в виде:

∑ xij = ai ,	j=1,2….n
j
∑ xij = bj ,	i=1,2….m
i

В этой системе число уравнений (m+n), а число неизвестных равно (mn). Такая система имеет бесконечное множество решений. Нас интересуют только те из них, в

которых xij не принимает отрицательных значений, т.е. x11 ³ 0 ; x21 ³ 0 или в общем виде: xij ³ 0 (i=1,2…m; j=1, 2…n).

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

F = c11 x11 + c12 x12 + ... + cij xij + ... + cmn xmn ® min

Это выражение называется целевой функцией и кратко записывается:

7

m n
F = ∑∑cij xij ® min ,
i=1 j =1
при условиях xij ³ 0 , ∑ai	= ∑bj
i	j

Все записанные формулы в совокупности представляют собой математическую формулировку (модель) транспортной задачи закрытого типа.

Широкое применение в практике перспективного планирования находят открытые транспортные задачи. Их решение возможно при приведении к задачам закрытого типа.

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

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

1. Методы последовательного улучшения плана.

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

2. Методы, основанные на сокращении невязок.

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

2.2Способы составления исходного (начального) плана при решении задачи методами последовательного улучшения плана

8

Начальный план в методах последовательного улучшения плана должен быть допустимым, т.е. удовлетворять ограничениям:

∑ xij = bj ; ∑ xij = ai

i

j

Существует ряд способов составления исходного (начального) плана:

а) способ северо-западного угла (диагональный)

Рассмотрим пример на матрице (табл.2)

							Таблица 2
Ri	Pj						ai
		P1	P2	P3	P4	P5
R1		140	60				200
R2			200	100			300
R3				130	140	80	350
R4						150	150
bj		140	260	230	140	230	1000

Заполнение плана начинаем с северо-западной клетки без учета показателей оптимальности. Поток в клетке выбирается минимальным из двух (P1 или R1). В примере - P1. Затем загружаем клетку (1-2) для балансирования строчки R1, и т.д. до тех пор, пока все ресурсы не будут распределены по потребителям.

б) способ наименьшего значения показателя оптимальности

При ручном решении для составления начального плана по названному способу находим клетку с наименьшим значением показателя и загружаем её потоком (min из ресурсов Ri или потребностей Pj).Эта операция производится до полного составления начального плана (табл.3).

												Таблица 3
Ri	Pj											ai
		P1		P2		P3		P4		P5
R1			4		4	190	5		6	10	7	200
R2			7	260	1	40	3		8		11	300
R3		140	2		4		8		5	210	9	350
R4			10		7		9	140	3	10	10	150
bj		140		260		230		140		230		1000

Как и предыдущий план, этот план (табл.3) является реально осуществимым.

в) способ «двойного предпочтения»

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

9

отмеченные дважды, имеют минимальное значение показателя оптимальности по строке и по столбцу. Помещаем в них максимально возможные корреспонденции, исключая из рассмотрения после каждой записи xij, соответственно, строку или столбец. Далее в оставшейся части матрицы записываем максимально возможные перевозки в клетки, отмеченные одним знаком «*». Затем, в оставшиеся клетки для балансирования ресурсов и потребностей (см. табл. 4).

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

												Таблица 4
Ri	Pj											ai
		P1		P2		P3		P4		P5
R1			4		4		5		6	200	7	200
			*		*						*
R2			7	260	1	40	3		8		11	300
					**		*
R3		140	2		4	190	8		5	20	9	350
			**
R4			10		7		9	140	3	10	10	150
									**
bj		140		260		230		140		230		1000

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

Однако, нередки случаи, когда сумма ресурсов равна сумме потребностей не только по матрице в целом, но и по части столбцов и строк, а поэтому число загруженных клеток получается меньше, чем (m+n-1).

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

«Искусственный ноль» вводится в одну из клеток матрицы:

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

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

10

2.3 Решение транспортной задачи методом потенциалов

Метод потенциалов для решения транспортной задачи был впервые разработан акад. Л.В. Канторовичем в 1939г. Позднее близкий метод был предложен Д. Данцигом и получил название модифицированного распределительного метода (МОДИ).

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

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

Допустимый план оптимален тогда и только тогда, когда каждому по-

ставщику Ri (i=1,2,…,m) и каждому потребителю Pj (j=1,2,…,n) могут быть присвоены некоторые числа Ui и Vj, называемые потенциалами, для которых соблюдается условие:

V j -U i £ cij при xij = 0

V j -U i = cij при xij ³ 0 .

Для определения значений потенциалов строк и столбцов из потенциала одной произвольной строки или столбца пользуются равенствами:

V j = cij +U i ; U i =V ij - cij

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

Составляем исходный план. В примере – способом северо-западного угла

(табл. 5)

													Таблица 5
			V1=17		V2=17		V3=19		V4=16		V5=20
	Ri	Pj	P1		P2		P3		P4		P5		ai
U1=13	R1		140	4	60	4	+1	5		6		7	200
				-		+
U2=16	R2			7	200	1	100	3		8		11	300
						-		+
U3=11	R3		+4	2	+2	4	130	8	140	5	80	9	350
			+					-
U4=10	R4			10		7		9	+3	3	150	10	150
	bj		140		260		230		140		230		1000