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.

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


 

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

41281. ФОРМАЛИЗАЦИЯ И АЛГОРИТМИЗАЦИЯ ПРОЦЕССОВ ФУНКЦИОНИРОВАНИЯ СИСТЕМ 163 KB
  Методика разработки и машинной реализации моделей систем Сущность машинного моделирования системы состоит в проведении на вычислительной машине эксперимента с моделью которая представляет собой некоторый программный комплекс описывающий формально и или алгоритмически поведение элементов системы в процессе ее функционирования т. Требования пользователя к модели Основные требования предъявляемые к модели процесса функционирования системы: 1. Полнота модели должна предоставлять пользователю возможность получения необходимого набора оценок...
41283. ОСНОВЫ АЛГЕБРЫ ЛОГИКИ 56.5 KB
  Алгебра логики или алгебра высказываний разработана Джорджем Булем в 1854 г. Отсюда второе название "Булева алгебра". Логическая функция – закон соответствия между логическими переменными (функция дискретная). Логическая переменная либо есть, либо ее нет. Логическая функция может иметь произвольное число логических переменных. Область определения насчитывает значений, где n – количество переменных.
41284. Політичне і соціально-економічне становище українських земель у складі Австро-Угорщини 48.5 KB
  У Галичині тривав початий ще значно раніше процес полонізації на Закарпатті мадяризації на Буковині румунізації. Перші дві парові машини в Галичині зявилися лише в 1843 р. Велике феодальне землеволодіння було домінуючим на Закарпатті та в Галичині. Кількість сільської буржуазії становила 11 в Галичині та 8 на Буковині.
41285. Політичне і соціально-економічне становище українських земель у складі Російської імперії 85 KB
  в Україні сталося 104 масових антиурядових виступи кріпаків. Найзначнішими на Правобережній Україні були виступи селян у 24 селах і містечках Черкаського повіту на Київщині в 1803 р. Однак це не зупинило антикріпосницький рух в Україні. Особливо широкого розмаху він набрав на Правобережній Україні у звязку з проведенням інвентарної реформи 18471848 рр.
41286. Суспільно-політичний розвиток західноукраїнських земель 16.42 KB
  Вона маніфестувала нескореність духу українського народу що мало неабияке значення у справі пробудження національної самосвідомості мас. Яхимовичем взяла на себе роль представника інтересів українського населення Галичини перед центральним урядом і виконувала її протягом 18481851 рр. Руські ради стали організаторами боротьби українського населення за відокремлення Східної Галичини заселеної переважно українцями від західної польської та надання їй національнотериторіальної автономії за запровадження навчання в усіх освітніх закладах...
41287. Три поділи Польщі 47 KB
  Відтоді почався австрійський період історії Львова та краю тривав він до 1 листопада 1918 року. Відкрите втручання Росії в польські справи підтримка православних дисидентів спонукали шляхту утворити 29 лютого 1768 року в містечку Бар на Поділлі нову конфедерацію що спиралася на підтримку Австрії та Франції. Протягом липнясерпня 1768 року було розгромлено більшість гайдамацьких загонів. Але попри значну міжнародну підтримку 1772 року головні сили шляхти було розбито російськими військами під командуванням Суворова.
41289. Україна в Першій світовій війні 92.5 KB
  Невдала для балканських слов'ян війна 1912-1913 рр. зміцнила становище Австро-Угорщини. Вона створила нову державу — Албанію, яка позбавила Сербію виходу до Адріятицького моря. Відносини між слов'янами і урядом цісаря Франца-Йосифа щораз більше напружувались.