10. Оптимизация транспортных систем приближенными методами

Постановка задачи А. Имеется т пунктов производства (ремонта, об­служивания) изделий А_1,, А₂..., А_т и п пунктов использования (эксплуата­ции) этих изделий В₁ В₂,..., В„. Известны затраты на доставку изделия из каждого i-го пункта производства (ремонта, обслуживания) в каждый i-ый пункт использования (эксплуатации) - Су. Известны количество изделий a_i в каждом i-ом пункте производства (ремонта, обслуживания) и количество изделий bj,которые необходимо доставить в каждый j-ый пункт использо­вания (эксплуатации). Требуется определить, какое количество изделий Ху необходимо перевезти из каждого i-го пункта производства (ремонта, об­служивания) в каждый j-ый пункт использования (эксплуатации), чтобы:

1/ вывезти продукцию всех отправителей;

2/ удовлетворить всех потребителей;

3/ минимизировать суммарные затраты на доставку всех изделий.

Постановка задачи С. Имеется т складов некоторой продукцииА,, А₂,..., А_т и п потребителей этой продукции В), В₂,..., В_п. Известны затраты на доставку единицы груза из каждого i-го склада в каждый j-ый пункт по­требления - Су. Известны объемы продукции - а, в каждом i-ом складе и объемы продукции - bj,которые необходимо доставить в каждый j-ый пункт потребления. Требуется определить, какое количество продукции x_ij необходимо перевезти из каждого i-го склада в каждый j-ый пункт потреб­ления, чтобы вывезти продукцию всех складов; удовлетворить всех потре­бителей; минимизировать суммарные затраты на доставку всей продукции.

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

1. Объем работ (величина пробега транспорта) в т, 1м³, км и др. Этот крите­рий рекомендуется использовать при условии осуществления перевозок од­нородного или взаимозаменяемого груза одним видом транспорта. Объем перевезенного груза ( величина пробега) оказывает существенное влияние на размер издержек. Этот критерий удобен для расчетов, т.к. объем работ (вели­чина пробега) определяется легко и точно для любого направления;

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

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

4) Себестоимость перевозок. Этот критерий характеризует затраты непосредственно транспортных организаций на перевозку различными видами транспорта. Он позволяет делать более обоснованные выводы о целесообразности переключения тех или иных перевозок с одного вида транспорта на другой. Недостаток критерия себестоимости - сложность определения участковых показателей;

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

6) Приведенные затраты. Является основным комплексным критерием, определяется по сумме издержек на производство и транспорт.

Рассмотрим на конкретном примере решение задач данного класса.

Постановка задачи. В городе N имеется четыре (т = 4) домостроительных комбината (ДСК) А_и А₂, А₃, А₄ и строятся четыре (n = 4) микрорайона на В1 В2, В₃, В₄. Известны производственные мощности ДСК – а_i, и потребность в комплектах унифицированных изделий каждого микрорайона - j. Ресурсы отправителей и ресурсы потребителей известны (табл. 5.1 последний столбец и нижняя строка). Известны также затраты - - С_ij, связанные с доставкой одного комплекта унифицированных изделий из А_i ДСК в каждый строящийся микрорайон Bj.Требуется так распределить продук­те домостроительных комбинатов по строящимся микрорайонам, чтобы суммарные приведенные затраты, связанные с доставкой всей продукции т комбинатов до микрорайонов, были минимальны.

Таблица 5.1

ДСК Аi	Строящиеся микрорайоны Д							Производст­венные мощ­ности аi,
	В1		В2		Вз	В4
	Затраты на транспортировку Сij
А1	70	38		24		92	14
A2	58	18		56		72	20
Аз	19	10		100		30	26
А4	3	36		121		8	41
Объем работ bJ в микрорайоне	30	22		15		34

Выявление основных особенностей взаимосвязей и количествен­ных закономерностей. Количество комплектов унифицированных изде­лий, выпускаемых A_i-ым ДСК обозначим через а_i, количество комплектов унифицированных изделий, потребляемых j-м микрорайоном, обозначим через bj.Предположим, что общий объем производства унифицированных изделий на всех ДСК равен общему объему потребления этих изделий в строящихся микрорайонах

В нашей задаче сумма производственных мощностей ДСК равна сум­ме объемов работ на строящихся микрорайонах.

14 + 20 + 26 + 41 = 30 + 22 + 15 + 34= 101.

Обозначим через x_ij искомую переменную, которая равна количеству комплектов унифицированных изделий, поставляемых i-м ДСК j-му микро­району. Значения x_ij проставляются в левых нижних углах клеток таблицы.

Введем определенные ограничения в задаче:

1. необходимо полностью использовать производственные мощности ДСК. Это ограничение можно записать в таком виде

Для нашей задачи эта система ограничений будет выглядеть так:

x₁₁+x₁₂+x₁₃+x₁₄=14,

x₂₁+х₂₂+x₂₃+x₂₄=20

x₃₁+x₃₂+x₃₃+x₃₄=26

x₄₁+x₂₄+x₃₄+x₄₄=41.

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

Для нашей задачи эта система ограничений будет выглядеть так:

x₁₁+x₁₂+x₁₃+x₁₄=14,

x₂₁+х₂₂+x₂₃+x₂₄=20

x₃₁+x₃₂+x₃₃+x₃₄=26

x₄₁+x₂₄+x₃₄+x₄₄=41.

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

x_tj>0, (i = 1,2,….., т, j= 1,2,..., n).

Построение математической модели. Обозначим через Су приведен- е затраты на доставку единицы продукции из ДСК А, в микрорайон Bj. В качестве критерия оптимизации примем суммарные приведенные затраты доставку всей продукции из всех ДСК во все микрорайоны, которые можно записать в таком виде

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

Данная задач относится к классу задач линейного программирования, как ограничения и целевая функция имеют линейный вид, т.е. искомые личины находятся в первой степени. Задачи такого вида называют транспортными задачами.

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

Рассмотрим наиболее распространенные способы определения начального допустимого решения - начального плана. В качестве исходных данных используем данные табл. 5.1.

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

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

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

Таблица 5.2

ДСК Аi	Строящиеся микрорайоны Д							Производст­венные мощ­ности аi,
	В1		В2		Вз	В4
	Затраты на транспортировку Сij
А1		38		24		92	14
A2	58	18		56		72	20
Аз	19	10		100		30	26
А4	3	36		121		8	41
Объем работ bJ в микрорайоне	30	22		15		34

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

Y = 14-70 + 16-58 + 4-18 + 18-10 + 8-100 + 7-121 + 34-8 = 4079.

Способ наименьшего элемента в столбце (строке). Поочередно в столбцах табл. 5.3, в которых находится клетка с минимальным элементом затрат, распределяют максимально возможное количество ресурсов. В наш­ей задаче в первом столбце (строке) это клетка A₄Bi,которая имеет мини­мальный элемент равный 3, Следовательно, распределяем в нее макси­мально возможное количество ресурсов 30. Если спрос по столбцу (строке) не удовлетворен, то находится следующая клетка с минимальным элемен­том в этом столбце (строке), куда и распределяются оставшиеся ресурсы и так до удовлетворения спроса по столбцу. И если спрос полностью удовле­творен по столбцу, то переходят к соседнему столбцу А4В4 и т.д. Результа­ты определения начального допустимого решения начального плана пере­возки ресурсов способом наименьшего элемента в столбце (строке) пред­ставлены в табл. 5.3.

ДСК Аi	Строящиеся микрорайоны Д							Производст­венные мощ­ности аi,
	В1		В2		Вз	В4
	Затраты на транспортировку Сij
А1		38		24		92	14
A2	58	18		56		72	20
Аз	19	10		100		30	26
А4	3	36		121		8	41
Объем работ bJ в микрорайоне	30	22		15		34

В результате построения начального допустимого решения начального на способом наименьшего элемента в столбце величина критерия опти- зации (целевой функции) будет равна

Y= 14-24+ 1-56+ 19-72+ 22-10+ 4-30+ 30-3+ 11-8 = 2278.

Способ наименьшего элемента в таблице. Этот способ дает, как пра- “о, лучшие результаты, особенно в крупных таблицах, но его использо- ие требует большего внимания. В табл. 5.4 ищется клетка с минималь- м элементом в нее распределяется максимально возможное количество ■урсов. В нашей задаче такой клеткой является клетка A₄B_hв которую мещается максимально возможное количество ресурсов равное 30. Затем ^гтся клетки со следующими по величине минимальными затратами, ку- и помещаются оставшиеся ресурсы и т.д.

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

ДСК Аi	Строящиеся микрорайоны Д							Производст­венные мощ­ности аi,
	В1		В2		Вз	В4
	Затраты на транспортировку Сij
А1		38		24		92	14
A2	58	18		56		72	20
Аз	19	10		100		30	26
А4	3	36		121		8	41
Объем работ bJ в микрорайоне	30	22		15		34

В результате построения начального допустимого решения начального плана способом наименьшего элемента в таблице величина критерия опти­мизации (целевой функции) будет равна

Y = 14-24 + 1-56+ 19-72 + 22-10 + 4-30 + 30-3 + 11-8= 2278.

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

Таблица 5.5

ДСК Аi	Строящиеся микрорайоны Д							Производст­венные мощ­ности аi,
	В1		В2		Вз	В4
	Затраты на транспортировку Сij
А1		38		24		92	14
A2	58	18		56		72	20
Аз	19	10		100		30	26
А4	3	36		121		8	41
Объем работ bJ в микрорайоне	30	22		15		34

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

Y= 14-24+ 1-56+ 19-72+ 22-10+ 4-30+ 30-3 + 11-8 = 2278.

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

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

ДСК Аi				Строящиеся микрорайоны Д											Производст­венные мощ­ности аi,					Номер итерации
				В1			В2			Вз		В4								1			2			3			4			5
				Затраты на транспортировку Сij											Строки разностей
А1						38			24			92		14
A2				58		18			56			72		20
Аз				19		10			100			30		26
А4				3		36			121			8		41
Объем работ bJ в микрорайоне				30		22			15			34
Номер итерации	1	Строки разностей
	2
	3
	4
	5

Из всех разностей, как по строкам, так и по столбцам ищем максимальную. В нашем примере максимальная разность равна 38 и находится в оке А₂. Отметим ее звездочкой. В клетку, где находится наименьшая стоимость равная 18 (отправитель А₂, потребитель В₂ - клетка А₂В₂) помещаем максимально возможное количество ресурсов. Оно равно 20, т.е. все- наличию ресурса отправителя А₂ (табл. 5.6). Поскольку все ресурсы отправителя А₂ исчерпаны, строку А₂ исключаем из дальнейших расчетов, [ чего отметим все клетки этой строки звездочками.

После этого снова вычисляем разности по столбцам и строкам, не при- лая во внимание стоимости в клетках, имеющих ресурсы, и клетках со звёздочкой (исключенную строку или столбец), и определяем максималь­но разность в строке или в столбце. На второй итерации в нашей задаче максимальная разность принадлежит потребителю В₃ и равна 76. Дальше ем минимальный элемент в столбце В₃. Он равен 24 (клетка А _}В₃) и в данную клетку направляем максимально возможное количество ресурса и . Результаты определения начального допустимого плана перевозки ре- сов способом аппроксимации Фогеля представлены в табл. 5.7.

В результате построения начального допустимого плана способом аппроксимации Фогеля величина критерия оптимизации будет равна

Y = 14-24 + 20-18 + 23-19 + 2-10 + 1-100 + 7-3 + 34-8 = 1546.

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

Таблица 5.7

ДСК Аi				Строящиеся микрорайоны Д											Производст­венные мощ­ности аi,					Номер итерации
				В1			В2			Вз		В4								1			2			3			4			5
				Затраты на транспортировку Сij											Строки разностей
А1						38			24			92		14
A2				58		18			56			72		20
Аз				19		10			100			30		26
А4				3		36			121			8		41
Объем работ bJ в микрорайоне				30		22			15			34
Номер итерации	1	Строки разностей
	2
	3
	4
	5

Для эффективного выполнения необходимых расчетов целесообразно иметь соответствующее программное обеспечение. Ниже представлена ФОРТРАН-программа TRANSF.FOR (прогр. 5.1).