Файл: Золотарь, И. А. Экономико-математические методы в дорожном строительстве.pdf

Скачать файл (8,91Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 19.10.2024

Просмотров: 150

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Целевая функция L = 14,3.

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

ТОII р

— 1

<Пз =	0,2
+	1
с2з =	0,3	С25 = 0,7
— 1		+ 1

О	ю. о
II СО

с35 = 0,8

		+ 1					— 1
ДLai =	-	1 -0 ,4 + 1 - 0 ,2 -	1 -0,3+ 1 -0,7 + 1 - 0 ,5 -				1 -0 ,8 =	- 0 ,1 .
		с 12 = 0,1 С1з =		0,2
		— 1	+	1
		с2з =		0,3	с25 =	0 ,7
			— 1		+	1
		Сз2 = 0,2			с35 =	0 ,8
		+ 1			— 1
Д132=	-	1 - 0 ,1 + 1 -0 ,2 -	1 -0,3+ 1 -0,7 + 1 - 0 ,2 -				1-0,8 =	- 0 ,1 .

Поскольку AL31=AL32= —0,1, можно выбирать между х31 и х32. Примем, например, перевозку лщ и составим новый опорный план. Введем в клетку (3.1) перевозку, соответствующую наименьшему из чисел, записанных в опорном плане в клетках, где во вспомога тельной матрице для исчисления AL3[ стояли (— 1). Это число х35 = 3.

Переставляя число 3 в соответствии со вспомогательной матри цей для A L 31, получим новый опорный план:

5	4	0	0	= 10
0	3	0	9	0-2 —12
0	0	9	0	а3 = 1 2
*2 = 5	*з = 7	* 4 = 9	* 5 = 9

Целевая функция в данном случае составит

1 = 1 .0 ,4 + 5 -0 ,1 + 4 -0 ,2 + 3-0,3 + 9-0,7 + 3-0,5 + 9 -0 ,4 = 14,0.

Если вычислить величины А Ьц при последовательном внесении единичных перевозок в нулевые клетки этого опорного плана, то получим следующие результаты:

!>		1--L		0,6 — 1-0,4+1		0,5 — 1-0,4		=	0,3;
		II
l>	сл	II >—		0,9 — 1 -0,2+1		0,3 — 1-0,7-=			0,3;
A	+ i =		1	0,6 — 1-0,3+1		0,2 — 1-0,4		= 0,1;
Д-^22—			1 • 0 ,4 -		1-0,3 + 1 0		, 2 - 1-0,1	=	0,2;
Д ^'2 4 = =			1	0,5 — 1-0,3+1		0	, 2 - 1-0,4	+	1 -0,5 -1 0,4 =0,1;
Д-Дз2 ~			1 • 0 ,2 -		1-0,5+1	0	, 4 - 1-0,1	= 0;
> С- со со		II		0 , 6 -	1-0,5 + 1 0		, 4 - 1-0,2	= 0,3;

Д ^ 3 5 —	1 •0 ,8 - 1-0,5 + 1•0 ,4 - 1-0,2 +	1-0,3-1 •0,7 =0,1.
Так как все величины A L ^ O , то ни одна из перестановок в пла
не не даст уменьшения значения целевой		функции (транспортных
издержек).	Следовательно, последний опорный план является оп
тимальным.

Приведем еще некоторые примеры на оптимизацию решений за

дач технико-экономического характера			методами			линейного	про
граммирования.
П р и м е р	1. Имеется т мест получения	материалов			(конструкций) с запа
сами Q1, Q2,	Qu ..., Qm и качественными характеристиками материалов,						выра
жаемыми модулями деформации (упругости)		Ей Е2, E i......			Ет. Имеется п объек
тов работ с потребностью в материалах соответственно q\,					q2, ..., qj...... qn.
Подъездные пути к местам запасов материалов от каждого из объектов име
ют протяжение Ц}, а скорости движения по ним			щ 3-.	Требуется найти оптималь
ный план перевозки материалов к объектам		работ,		характеризующийся			мини
мальным объемом транспортной работы с учетом разного					качества материалов.
Потребность в материалах для каждого участка работ должна быть вначале
приведена к единому материалу (допустим, к материалу с						самым низким	моду

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

	Обозначим приведенные потребности в материалах через				q{n^ >■•	• >
q	, q *пр\ Аналогично должны быть выражены и запасы материалов Q[-np\
	В целевой функции «стоимость» перевозки каждого из материалов должна
быть определена также с учетом качества материала x ffiK				Величина	же
получается из соотношения		= x tjk\uv\ где коэффициенты приведения k\up^
будут представлять собой отношения			потребности в г-м материале к потребности
в материале с минимальным		модулем	на единичный объем	работ (например,		на
1	км).
	При характеристике транспортного процесса в тонно-километрах				различие	в

скоростях движения на подъездных путях не учитывается. Поэтому целесо образно к показателю в тонно-километрах {^l{j X ^ p } дать коэффициент, учиты

вающий это различие. Коэффициент может быть принят в виде ” 1п , где цш|П—

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

т л + 1

j м ; ” -if -

1=1}=1 ;

при обычных для транспортной задачи ограничениях:

т п -и

		2 <з("р) = 2		< р);			(v .3 0 )
		г - i	j = 1
	2	-*»yP) = Q / np); г' =		1> 2 , . .	.,	т\	(V .31)
	У“1
	т
	2 * # р) =		;' = 1. 2 , . . . ,		п,	п 4- 1;	(V .32)
	1=1
			> 0.				(V .33)
Как видно из ограничений(V.30)			и (V.31), аналогично решению предыдущей
задачи	вводится фиктивный (ге+1)-й объект			с тем, чтобы получить ограничения
в виде	равенств вместо	неравенств	типа (V.2), (V.3). Решение				задачи может

быть проведено описанным выше методом, т. е. в два этапа: составлением на первом этапе опорного плана и улучшением его на втором этапе методом потен циалов или каким-либо другим.


П р и м е р	2. Имеется п объектов работ, на которых одновременно		должны
вестись работы комплектами из т машин. Имеющиеся общие ресурсы			машино-
часов (машино-смен) ограничены и равны Ьи й2, ..., bj..... bm. Затраты			машино-
часов (машино-смен) на единичный объем работ на f-м объекте j -й			машиной
составляют а;,.	Требуется распределить машины между	объектами так, чтобы
обеспечить наибольшую производительность отряда имеющихся машин.
Обозначим искомые объемы работ, выполняемые комплектами машин на
объектах, через	xh хг, ..., xit ..., х п. Тогда ограничения	в нашей задаче запи

шутся следующим образом:
а \\х \	+ Я\|2*2 +	•■•-+- a uxi +	. . .	+	a inxn <	(V .34)
0-21*1	4- 0-22X2	. . . + anXi +	. . .	+	а-2ПХп < *2!	(V. 35)

а т \х \ + а,т2Х2 + . . . 4- amiXi 4- • ■. 4- а тпх п ^ Ьт .

(V .36)

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

т	т	т	т
L — х \ 2 a i Т" -*22 a i Т" •- ■"Т Х 12			+ •••+ ЛГЛ2 а V
; = 1	7 = 1	7 = 1	7 = 1

или, что то же самое, минимизировать целевую функцию

тп

£ —=2	а : 2	x i-	(V.37)
7 = 1	1 = 1
При ограничениях (V.34) —(V.36) и условиях неотрицательности:
x t > 0; г = 1, 2,		3 ,..., п.	(V.38)

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

Все приведенные примеры относились к так называемой транс портной задаче линейного программирования. Отличительной ее особенностью является необходимое наличие в любом плане зада чи (как опорном, так и последующих) т + п— 1 ненулевых перево зок, где п — число потребителей товаров. Как ясно из постановки транспортной задачи, общее число уравнений (ограничений) равно т + п (т ограничений по наличию материалов и п ограничений по потребности в них). Казалось бы, что и число неизвестных Xij, кото рое может быть найдено, должно равняться т + п. Однако это не так, ибо в постановке задачи используется одно условие, а именно

равенство		общих	запасов материалов общей потребности в них
( 2	ai = h	ЬЛ ■	Поэтому остается т + п— 1 независимых ограни-
\ ( = 1	) = i	/

чений и любой план задачи должен содержать точно т + п— 1 не нулевых перевозок.

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

В приводимой ниже матрице проставлены стоимостные характе ристики перевозок сц, а за полями матрицы — запасы материалов а; и потребности в них bj.

о II

0,1

0,2

0,6

0,9

= 10 тыс. м3