Есть т пунктов отправления (поставщиков) груза А^, А^, ..., А^^, в которых сосредоточены запасы некоторой однородной про дукции в объемах соответственно Лр «2,..., а^, и п пунктов назна чения (потребителей груза) В^, В^,.,,, В^, которые требуют данную продукцию в объемах соответственно /?р Ъ^,.--, Ъ^. Воз можности поставщиков ограничены некоторыми числами, харак теризующими количество единиц имеющейся у данного постав щика продукции. Соответственно потребности потребителей описываются некоторыми числами (указывающими количество единиц необходимой продукции). Продукция однородна, поэто му любой поставщик может предложить ее любому потребите лю. Предполагается, что транспортировка продукции возможна от любого поставщика А. к любому потребителю В. и известны транспортные издержки е.. перевозки единицы груза по маршру ту Afi.. Стоимости таких перевозок составляют матрицу транс портных издержек. Нужно так организовать транспортировку продукции (груза) от поставщиков к потребителям, чтобы сум марные транспортные расходы были минимальными. Задача предполагается разрешимой в том смысле, что общий объем воз можных поставок груза не должен быть меньше общего объема потребностей потребителей. Экономико-математическая модель транспортной задачи в матричной постановке формулируется следующим образом. Пусть с. - стоимость перевозки единицы продукции от /-го поставщика ку-му потребителю, а г- максимальный объем возмож ных поставок /-Г0 потребителя и Ъ. - объем потребностей у-го по ставщика, / = 1,2,..., т;у = 1,2,..., и. Обозначим через л., величину объема перевозок оту-го поставщика к /-му потребителю. Найти такие значения объема перевозок грузов, т.е. план пе ревозок - матрицу Z = (х..), 1 = 1,т; j = hn, удовлетворяющую оп ределенным условиям (2). Математическая модель транспортной задачи имеет вид сле дующей задачи линейного программирования: 739 т п ^=iy=l (1) при условиях: ^xij=bj, 7 = 1,2,..., А?, п '=1 Y.Xii=ai, i = l,2,'",^, (2) х^у>0 / = 1,2,...,w; 7 = 1,2,...,«. В задачах больших размерностей, связанных с планировани ем перевозок однородных массовых грузов (например, нефтепро дуктов, угля, гравия, зерна и т.д.), как правило, имеются десятки пунктов отправления и сотни пунктов потребления данного гру за. Если планирование перевозок осуществлять на основе клас сической транспортной задачи в матричной постановке, то по требуется предварительно рассчитать затраты с.., связанные с перевозкой единицы груза из каждого пункта отправления А. в каждый пункт потребления В., и соответствующая матрица удель ных затрат будет содержать тысячи элементов, что усложняет процедуру подготовки исходных данных при решении практи ческих задач. Между тем реальные перевозки массовых грузов осуществляются по автомобильным, железнодорожным или вод ным транспортным сетям. Число коммуникационных участков в таких сетях обычно лишь немногим превосходит число связыва емых пунктов. Поэтому естественно использовать информацию о затратах по перевозке единицы груза по каждому участку сети. Тогда при тех же десятках пунктов отправления груза и порядка сотни пунктов потребления исходная информация об удельных затратах будет содержать немногим более сотни величин. Кроме того, при использовании экономико-математической модели транспортной задачи в матричной постановке не учиты ваются: • ограничения по пропускным способностям отдельных ком муникаций; • возможность перевозки груза в обоих направлениях между пунктами; • наличие транзитных пунктов, через которые груз может перевозиться, хотя эти пункты не требуют этот груз. 740 в сетевой постановке ограничения и особенности такого рода учитываются. В частности, рассматривается перевозка однород ного груза в транспортной сети, содержащей п пунктов (вершин, узлов), которые соединены г коммуникациями_(дорогами). Введем обозначения: к - номер пункта, А: = 1,«, который с дру гими пунктами соединен коммуникациями (дорогами); s - номер дороги, 5 = 1, г (перевозка груза возможна в обоих направлениях движения по дороге); 6^ - потребность к-то пункта в грузе (при этом если bf^ < О, то груз вывозится из этого пункта; если Z?^ > О, то в пункт к ввозится груз в количестве 6^; если же 6^ = О, то это транзитный пункт; С^ - стоимость перевозки единицы груза по 5-й дороге, 5 = 1,г-^^ - пропускная способность 5-й дороги, т.е. по этой дороге нельзя провезти больше указанного количества, 5 = 1, г. Аналогично может быть поставлена задача, в которой требу ется составить план перевозок, который бы минимизировал сум марные транспортные издержки. Обозначим допустимый план такой задачи х = {х^,Х2 ,..., x^.,...,x^), где л:^.- количество груза, которое везется по 5-й дороге. В этом случае экономико-математическая модель транспортной задачи в сетевой постановке имеет следующий вид: г '^^^) - S ^s^s ~^ min; ^=1 S ^ л ~ ^ ^j, =bk,k = ln, где j^, - все дороги, которые входят в пункт к; /\. - все дороги, которые выходят из пункта к; x,<q,, 5 = 1,г, Х^, >0, 5 = 1, г. Для решения транспортной задачи предложено много различ ных методов. По-видимому, наиболее эффективным среди них является так называемый метод потенциалов, который основан на теории двойственности (см. Двойственная задача в линейном программировании).
Ви переглядаєте статтю (реферат): «ТРАНСПОРТНАЯ ЗАДАЧА» з дисципліни «Теорія систем і системний аналіз в управлінні організаціями»
