19810

Економіко-математична модель транспортної задачі

Доклад

Информатика, кибернетика и программирование

Транспортная задача ставится следующим образом: имеется m пунктов отправления А1 А2 ... Аm в которых сосредоточены запасы какихто однородных грузов в количестве соответственно а1 а2 ... аm единиц. Имеется n пунктов назначения В1 В2 ... Вn подавшие заявки соответственно на...

Украинкский

2013-07-17

17.89 KB

1 чел.

Транспортная задача ставится следующим образом: имеется m пунктов отправления А1, А2 , ..., Аm , в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно а1, а2, ... , аm единиц. Имеется n пунктов назначения В1 , В2 , ... , Вn подавшие заявки соответственно на b1 , b2 , ... , bn единиц груза. Известны стоимости Сi,j перевозки единицы груза от каждого пункта отправления Аi до каждого пункта назначения Вj . Все числа Сi,j, образующие прямоугольную таблицу заданы. Требуется составить такой план перевозок (откуда, куда и сколько единиц поставить), чтобы все заявки были выполнены, а общая стоимость всех перевозок была минимальна.

Задача о перевозках, в которой сумма запасов ровна сумме заявок:

 аi =  bj ( где i=1,...,m ; j=1,...,n ) (4)

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

Баланс транспортной задачи может нарушаться в 2-ух направлениях:

1. Сумма запасов в пунктах отправления превышает сумму поданных заявок

 аi >  bj ( где i=1,...,m ; j=1,...,n );

2. Сумма поданных заявок превышает наличные запасы

 аi <  bj ( где i=1,...,m ; j=1,...,n );

Условимся первый случай называть "Транспортной задачей с избытком запасов", а второй — "Транспортной задачей с избытком заявок”.

Транспортная задача с избытком запасов.

В пунктах A1, A2, ... , Am имеются запасы груза a1, a2, ... , am; пункты B1, B2, ... , Bn подали заявки b1, b2, ... , bn, причём

 аi >  bj ( где i=1..m ; j=1..n ).

Сверх имеющихся n пунктов назначения В1, B2, ... , Bn, введём ещё один, фиктивный, пункт назначения Bn+1, которому припишем фиктивную заявку, равную избытку запасов над заявками

bn+1 =  аi -  bj ( где i=1,...,m ; j=1,...,n ) ,

а стоимость перевозок из всех пунктов отправления в фиктивный пункт назначения bn+1 будем считать равным нулю. Введением фиктивного пункта назначения B n+1 с его заявкой b n+1 мы сравняли баланс транспортной задачи и теперь его можно решать как обычную транспортную задачу с правильным балансом.

Транспортная задача с избытком заявок .

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

Решение транспортной задачи начинается с нахождения опорного плана. Для этого существуют различные способы. Например, способ "северо-западного угла”, метод минимального элемента и метод Фогеля. Клетки таблицы, в которых стоят ненулевые перевозки, являются базисными. Их число должно равняться m + n - 1.

Очевидно, при переносе любого числа единиц по циклу равновесие между запасами и заявками не меняется: по прежнему сумма перевозок в каждой строке равна запасам этой строки, а сумма перевозок в каждом столбце — заявке этого столбца. Таким образом при любом циклическом переносе, оставляющем перевозки неотрицательными допустимый план остаётся допустимым. Стоимость же плана при этом может меняться: увеличиваться или уменьшатся. Назовём ценой цикла увеличение стоимости перевозок при перемещении одной единицы груза по означенному циклу. Очевидно цена цикла ровна алгебраической сумме стоимостей, стоящих в вершинах цикла, причём стоящие в положительных вершинах берутся со знаком "+”, а в отрицательных со знаком "-".

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

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


 

А также другие работы, которые могут Вас заинтересовать

83777. Банки как субъекты налогового права. Иные участники налоговых отношений 49.16 KB
  Иные участники налоговых отношений. 9 НК РФ к участникам налоговых отношений регулируемых законодательством о налогах и сборах фактически они таковыми являются и обладают специальным налоговоправовым статусом. Банки являются субъектами налоговых правоотношений обеспечивающими налоговые изъятия и наделенными в связи с этим соответствующими правами и обязанностями. Участие банков в налоговых отношениях носит более сложный по сравнению с иными участниками налоговых отношений регулируемых законодательством о налогах и сборах характер.
83778. Правовой статус налоговых органов. Их права и обязанности. Обязанности должностных лиц налоговых органов 43.23 KB
  Обязанности должностных лиц налоговых органов. Правовой статус налоговых органов РФ объем и характер прав и обязанностей системы налоговых органов России строго определенных законодательством. Правовое положение налоговых органов обусловлено их местом в системе органов государственного управления страны наделением их над ведомственными полномочиями по отношению к организационно неподчиненным объектам управления по контролю за соблюдением налогового законодательства правильностью их исчисления полнотой и своевременностью внесения в...
83779. Правовой статус таможенных органов, финансовых органов, органов внутренних дел, следственных органов 44.78 KB
  Таможенные органы пользуются правами и несут обязанности налоговых органов по взиманию налогов при перемещении товаров через таможенную границу Таможенного союза в соответствии с таможенным законодательством ТС и законодательством РФ о таможенном деле. При исполнении указанных функций таможенные органы и их должностные лица реализовывают в пределах своей компетенции права и обязанности налоговых органов ст. В ходе проведения контрольных мероприятий таможенные органы вправе: запрашивать документы и сведения в том числе в форме электронных...
83780. Исполнение обязанности по уплате налогов и сборов. Объекты налогообложения. Принципы определения цены товаров, работ или услуг для целей налогообложения 44.19 KB
  Сущность исполнения налоговой обязанности заключается в уплате налога или сбора. Налоговая обязанность возникает с момента возникновения установленных налоговым законодательством обстоятельств предусматривающих уплату конкретного налога или сбора. Так вот обстоятельствами с которыми налоговое законодательство связывает возникновение налоговой обязанности являются следующие: вопервых это наличие объекта конкретного налога или сбора; вовторых это наличие непосредственной связи между этим объектом и субъектом налогоплательщиком. И...
83781. Исполнение обязанности по уплате налогов и сборов. Основания возникновения, изменения и прекращения обязанности по уплате налогов и соборов; порядок исчисления налогов; взыскание налога за счет денежных средств и иного имущества налогоплательщика 46.34 KB
  Основания возникновения изменения и прекращения обязанности по уплате налогов и соборов; порядок исчисления налогов; взыскание налога за счет денежных средств и иного имущества налогоплательщика. Возникновение обязанности по уплате налогов и сборов связано с несколькими обстоятельствами: с наличием конституционноправовой обязанности по уплате налогов по нормам законодательства о налогах и сборах в которых детализируется реализация обязанности по уплате налогов объектами налогообложения.  Основанием возникновения налогового обязательства...
83782. Изменение срока уплаты налога и сбора: общие условия изменения срока уплаты; обстоятельства исключающие изменение срока уплаты, органы, уполномоченные принимать решение об изменении сроков уплаты 41.84 KB
  Изменением срока уплаты налога и сбора признается перенос установленного срока уплаты налога и сбора на более поздний срок. Срок уплаты налога и или сбора может быть изменен в отношении всей подлежащей уплате суммы налога и или сбора либо ее части с начислением процентов на сумму задолженности. Изменение срока уплаты налога и сбора осуществляется в форме отсрочки рассрочки инвестиционного налогового кредита.
83783. Порядок и условия предоставления отсрочки и рассрочки по уплате налога и сбора. Инвестиционный налоговый кредит. Порядок и условия его предоставления 48.98 KB
  Отсрочка или рассрочка по уплате налога представляет собой изменение срока уплаты на срок не превышающий один год соответственно с единовременной или поэтапной уплатой суммы задолженности. Отсрочка или рассрочка может быть предоставлена заинтересованному лицу если имеются достаточные основания полагать что возможность уплаты указанным лицом такого налога возникнет в течение срока на который предоставляется отсрочка или рассрочка при наличии хотя бы одного из следующих оснований: 1 причинение этому лицу ущерба в результате стихийного...
83784. Требование об уплате налогов и сборов. Способы обеспечения исполнения обязанностей по уплате налогов и сборов 48.4 KB
  Требованием об уплате налога признается извещение налогоплательщика о неуплаченной сумме налога а также об обязанности уплатить в установленный срок неуплаченную сумму налога. Требование об уплате налога направляется налогоплательщику при наличии у него недоимки. Направляется налогоплательщику независимо от привлечения его к ответственности за нарушение законодательства о налогах и сборах. Требование об уплате налога должно содержать сведения о сумме задолженности по налогу размере пеней начисленных на момент направления требования сроке...
83785. Зачет и возврат излишне уплаченных или излишне взысканных сумм 39.45 KB
  В НК для налогоплательщиков плательщиков сборов налоговых агентов установлены единые правила зачета излишне уплаченных или взысканных налогов сборов и соответствующих пеней ст. Налоговый орган обязан сообщить налогоплательщику плательщику сбора налоговому агенту о каждом ставшем известным налоговому органу факте излишней уплаты и сумме излишне уплаченного взысканного в течение 10 дней со дня обнаружения такого факта. В случае обнаружения фактов свидетельствующих о возможной излишней уплате по предложению налогового органа или...