Файл: Тихомиров В.И. Линейное программирование в организации и планировании путевого хозяйства конспект лекций для студентов специальности Стр-во ж. д., путь и путевое хоз-во учеб. пособие.pdf

пути, перешивка пути, зачистка заусенцев. Объемы работ за­ даны в табл. 29.

Таблица 29

П р и м е ч а в и е. В числителе — трудоемкость при работе на перего­ не, в знаменателе — трудоемкость на станции.

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

Л Е К Ц И Я 4

ТРАНСПОРТНЫЕ ЗАДАЧИ ЛИНЕЙНОГО

ПРОГРАММИРОВАНИЯ

§ 1. Постановка транспортной задачи линейного программирования

Развитие общественного производства предъявляет все возрастающие требования к транспорту, как отрасли народно­ го хозяйства, осуществляющей производственные связи между районами страны.

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

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

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

В табл. 30 приведены данные о количестве вариантов, из которых надо сделать Bbi6qp. лучшего при решении транспорт­ ной задачи методами классического анализа (по расчетам А. В. Канторовича [11]).

75

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

Основной математической моделью, используемой для со­ ставления оптимальных планов перевозок, является так назы­ ваемая «транспортная задача» линейного программирования.

Сформулируем эту транспортную задачу.

Имеется т пунктов отправления, в каждом из которых со­ средоточено определенное количество единиц однородного продукта, предназначенного к отправке: в первом пункте от­ правления имеется аг единиц этого продукта, во втором—а2 единиц, в г-том — а, единиц и, наконец, /тг-ном пункте — ат единиц продукта. Этот продукт следует доставить в п пунктов

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

П

(36)

которому должны удовлетворять заданные числа а1 и bj.

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

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

76

тп

2 = V. 2 С; xij‘

/-1 /=1

Представим модель транспортной задачи в развернутом виде, основываясь па матричной записи:

7 7

1= ьп

*1/1 + A's/j "Г • ■+ *Ш/1

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

Так ,например, bj могут показывать число станков /-того вида, а числа а,—число деталей i-того класса. Тогда числа си могут обозначать затраты, связанные с обработкой одной детали i-того класса на станке /-того вида. Это могут быть нетолько денежные затраты, но и временные. В такой постанов­ ке целью решения задачи является такое распределение дета­ лей между станками (по одной детали на каждый станок),, которое минимизирует суммарные затраты.

В более общей постановке эту задачу можно сформулиро­ вать следующим образом.

Пусть столбцы табл. 31 означают различные виды каналов, обслуживания, а строки — различные классы заявок. Каждое число bj при этом показывает, сколько каналов содержит данный вид, а числа а, — сколько имеется заявок класса /.

Числа с,у могут характеризовать время обслуживания заявки i-того класса каналом обслуживания /-того вида или: любые другие издержки, связанные с этим обслуживанием.

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

Транспортная задача, как это следует из приведенной вы­ ше математической формулировки, является задачей линзйно-

78

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

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

тп

Втакой постановке транспортная задача называется за­ крытой.

Вэкономических расчетах немалую роль играют и так на­ зываемые открытые задачи (модели), в которых указанное ра­ венство не соблюдается. При этом возможны два случая: или

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

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

П

при условиях V (t= 1. 2 , . . . . т)

/=1

т

2 хи = Ь, ( / = 1 , 2......... п) (=1

Му>0.

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

п+1

S хи = а‘

/~1

7 9 -