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.

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


 

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

48960. Измерительные сигналы 637.5 KB
  Измерительный сигнал – это материальный носитель информации, содержащий количественную информацию об измеряемой физической величине и представляющий собой некоторый физический процесс, один из параметров которого функционально связан с измеряемой физической величиной...
48961. Розробка обчислювального пристрою, що виконує ділення чисел у форматі з фіксованою комою 786 KB
  Пристрій призначений для виконання операції ділення над числами з фіксованою комою в доповняльному коді.Виконувана операція ділення без відновлення залишку. ВИКОНАННЯ ОПЕРАЦІЇ ДІЛЕННЯ ДВІЙКОВИХ ЧИСЕЛ БЕЗ ВІДНОВЛЕННЯ ЗАЛИШКІВ 2.Методи ділення двійкових чисел Ділення двійкових чисел багато в чому аналогічно діленню десяткових чисел.
48962. ИСПОЛЬЗОВАНИЕ ВНЕШНЕГО ФОТОЭФФЕКТА ДЛЯ ИЗМЕРЕНИЯ ФИЗИЧЕСКИХ ВЕЛИЧИН 365.5 KB
  Внешний фотоэффект Внешним фотоэффектом называется испускание электронов веществом под действием электромагнитных излучений. Сила фототока зависит от числа электронов вылетающих из катода электронов или от их начальной скорости а также от разности потенциалов между катодом и анодом. Рисунок 3 – Зависимость I от U При напряжении U равном 0 некоторые из фотоэлектронов долетают до анода поэтому I ≠ 0 при U = 0.
48963. Свойства 4−фенил−5,6−ди(этоксикарбонил)−3,4−ди− гидропиримидин−2(1Н)−на 1.72 MB
  Образуется при реакции бензальдегида мочевины и диэтилового эфира 2−оксобутандиовой кислоты в кислой среде. В данном механизме предпологается для подобной реакции три возможных промежуточных соединения образующихся из исходных веществ: бензальдимочивена диэтиловый эфир 2−карбамидобут−2−ендиовой кислоты диэтиловый эфир...
48964. Проект установки для наплавлення 1.46 MB
  Наплавлення – це процес нанесення за допомогою зварювання шару металу на поверхню виробу. Шляхом наплавлення можна отримати вироби зі зносостійкими жароміцними антифрикційними властивостями. Наплавлення застосовують при виготовленні нових та відновленні зношених деталей. При ремонтному відновленні наплавлення ефективне завдяки тому що відновлена деталь часто коштує в декілька разів менше нової деталі і при правильному виборі технології відновлення не поступається їй за працездатністю.
48965. Расчет структуры электромагнитных полей 623.5 KB
  Олемской Задание На курсовую работу Расчет структуры электромагнитных полей по курсу Теория Поля Студент Волошин С. Группа...
48966. Расчет возможных потерь от испарения нефти из резервуара на примере РВС 5000 (№4 в резервуарном парке) ЛПДС «Субханкулово» Туймазинского нефтепроводного управления 657.5 KB
  Кроме того потери нефти и нефтепродуктов при авариях разливах и утечках загрязняют почву грунтовые воды и водоёмы. Многократные перевалки нефтепродуктов и хранение нефти и нефтепродуктов в резервуарах ведут к потерям от испарения. Потери нефти и нефтепродуктов обусловливаются как специфическими их свойствами так и условиями перекачки хранения приёма отпуска техническим состоянием средств транспорта и хранения а также внимательностью и добросовестностью обслуживающего персонала.
48968. Теплообмінник «труба в трубі» 464 KB
  Стабільність роботи теплообмінника досягається деяким збільшенням простору теплообміну в порівнянні з розрахованою що забезпечує стійкі показники роботи теплообмінника в умовах поступового забруднення стінок труби. Опис та обґрунтування вибраної конструкції теплообмінника Опис конструкції основних складальних одиниць та деталей теплообмінника Апарат являє собою вертикальну раму на яку кріпляться елементи труба в трубіâ€ внутрішні труби яких з´єднуються між собою калачами а зовнішні – патрубками перехід з одного ряду до другого...