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.

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


 

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

35616. ШКОЛА ТВОРЧЕСКОЙ ЖИЗНИ. ПРОЕКТ 221 KB
  По его вине Древо Жизни утратило крону. ПРОЕКТ ШКОЛА ТВОРЧЕСКОЙ ЖИЗНИ Принцип устойчивости экодеревни Проблемы экодеревень ПУТИ РЕАЛИЗАЦИИ ПРОЕКТА: Экономическая деятельность в поселении Природные виды деятельности Виды деятельности связанные с информационными технологиями Научная деятельность Искусство Народные ремёсла Медицина Туризм Строительство Малые производства Культура Образование Безопасная интеграция в природную среду Топология экологического поселения Проект...
35617. Шарлотка. Творческий проект 68.02 KB
  Тема: Шарлотка. Но от салата я отказалась И решила приготовить пирог шарлотка. Шарлотка фр. Классическая шарлотка это французское сладкое блюдо приготовленное из белого хлеба заварного крема фруктов и ликёра.
35618. Мой выбор. Творческий проект 33.32 KB
  Правильный выбор профессии позволит мне так построить свою будущую карьеру чтобы достичь выдающихся успехов. Можно выделить следующие подпроблемы: Проблемное поле анализа профессиональной деятельности Изучение алгоритма выбора профессии Выявление и анализ личностных и психофизиологических характеристик Изучение требований...
35619. Акустическая система. Творческий проект по технологии 570.93 KB
  ТБ при работе Правила техники безопасности при выполнении ручных работ: Быть внимательной Аккуратно пользоваться ножом и ножницами чтобы не порезаться Технология выполнения изделия Последовательность изготовления звуковой колонки: Приготовить 2 бутылки и картонный рулон Аккуратно разрезать ножом бутылки оставив только донышки Вырезать ножницами входы для картонного рулона Вырезать ножницами в картонном рулоне вход для телефона Раскрасить картонный рулон черной краской добавляя надписи чтобы украсить звуковую колонку Вставить...
35620. Творческий проект «Оформление рамок» 1.29 MB
  Рамка с повторяющимися узорами подчеркивала картину являясь зачастую не только украшением но и идейным продолжением сюжета картины. Аналоговые работы Материалы инструменты приспособления Малика: Рамка с вязаным цветком: Готовая рамка 2 шт. Пряжа синяя Крючок Бисер стеклярус синий Клей Ножницы Нелли: Рамка с розочками из лент: Лента 2 шт.
35621. Композиция Маки. Творческий проект 516.11 KB
  Так как мои цветы должны быть плотными красивыми и немаркими то я буду использовать шерсть красивого цвета и притом она должна иметь низкую себестоимость. Шерсть овец падала на пол пропитывалась влагой а они еще и топтались по ней копытами. Для изготовления маков понадобится шерсть мыльная вода. Так как я решила что мои цветы должны быть немаркими и плотными то я выбрала шерсть красного цвета.
35622. Ночная сорочка. Творческий проект 24.2 KB
  Задачи 1 Провести исследование и разработать эскиз моего проектного изделия. 4 Изготовить выкройку швейного изделия. 5 Подобрать ткань для изделия. Критерии выбора идеи изделия 1 Технология изготовления соответствует программе 7 класса.
35623. ИЗГОТОВЛЕНИЕ полки для цветов. ТВОРЧЕСКИЙ ПРОЕКТ 48.09 KB
  РАЗДЕЛЫ ПРОЕКТА 1. Обоснование выбора данного проекта 2. Описание собственной работы над проектом разработка эскизов шаблонов ознакомление с литературой подготовка материалов инструментов выполнение теоретической части проекта выполнение практической части проекта оформление проекта защита проекта 5. Достоинства проекта 6.
35624. Оформление бутылки в технике декупаж. Творческий проект 1.1 MB
  Исследование выявление традиций истории стеклянной бутылки. Как только человек научился лить стекло едва ли не первыми предметами стекольного производства стали бутылки. Прошло немало времени пока бутылки приобрели современную стройность и благородную стать.