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.

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


 

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

23652. Экспертная система по составлению учебных расписаний 59 KB
  При составлении расписаний лучше исходить не из заданной цели к тому же трудно сформулировать какое расписание €œлучше€ а из возможностей комбинирования учебных дисциплин. Далее можно попытаться оценить относительную ценность полученных расписаний их уже будет не так много с точки зрения быстрейшего и полного освоения дисциплин специализации в необходимой пропорции с факультативными и общеобразовательными курсами. Представим что студенту желающему специализироваться в конкретной области предоставлена возможность самостоятельного...
23653. Логическое программирование задачи поиска пути на конечных графах пространства состояний 680 KB
  Рассмотрим ориентированный ациклический граф: Наличие ориентированной связи двух соседних вершин отображается в программе в виде фактовпредикатов edgex y. edgeac. edgecf. edgefh.
23654. Разработка графического интерфейса и базы данных каскадной системы регулирования температуры, расхода и концентрации в процессе ректификации стирола 3.53 MB
  Листинг программы unit Unit1; interface uses Windows Messages SysUtils Variants Classes Graphics Controls Forms Dialogs Grids ComCtrls ExtCtrls DBCtrls DBGrids StdCtrls Buttons DB DBTables ImgList ToolWin Mask TeEngine Series TeeProcs Chart DbChart Animate GIFCtrl; type TForm1 = classTForm PageControl1: TPageControl; TabSheet1: TTabSheet; TabSheet3: TTabSheet; PageControl2: TPageControl; TabSheet5: TTabSheet; DBNavigator1: TDBNavigator; DBGrid1: TDBGrid; BitBtn1: TBitBtn;...
23655. Управление качеством электронных средств 423 KB
  Непрерывной случайной величиной СВ называется величина которая при испытании может принять любое значение из заданного диапазона. Любое распределение характеризуется определенными характеристиками важнейшими из которых являются среднее значение и дисперсия. Несмещенной является оценка среднее значение которой совпадает со средним значением генерал ной совокупности. Здесь оценка истинное значение характеристики – оператор усреднения.
23656. Семантические сети 170 KB
  Семантические сети Семантической сетью является структура данных имеющая определенный смысл как сеть. Стандартного определения семантической сети не существует но обычно под ней подразумевают следующее: Семантическая сеть это система знаний имеющая определенный смысл в виде целостного образа сети узлы которой соответствуют понятиям и объектам а дуги отношениям между объектами. Следовательно всевозможные сети можно рассматривать как сети входящие в состав семантической сети. Поэтому в контексте знакомства с СОЗ семантические сети...
23657. Продукционные модели. ЕСЛИ - ТО (явление - реакция) 166 KB
  Эти две отличительные черты и определили широкое распространение методов представления знаний правилами. Программные средства оперирующие со знаниями представленными правилами получили название продукционных систем или систем продукции и впервые были предложены Постом в 1941 году. Общим для систем продукции является то что они состоят из трех элементов: Набор правил используемых как БЗ его еще называют базой правил; Рабочая память где хранятся предпосылки касающиеся отдельных задач а также результаты выводов получаемых на основе...
23658. Представление знаний с применением фреймов 143.5 KB
  Понятие фрейма и слота В сложных семантических сетях включающих множество понятий процесс обновления узлов и контроль связей между ними становится затруднительным. В каждом узле понятия определяются набором атрибутов и их значениями которые содержатся в слотах фрейма. Слот это атрибут связанный с узлом в системе основанной на фреймах. Слот является составляющей фрейма.
23659. Стратегии поиска в СОЗ 105.5 KB
  7 Начальныесостояния Цель конечные состояния Реализует возможность выбора Выполняет шаги от начального состояния к новым более близким к цели Исходные посылки и факты Поиск Стратегия поиска B A C C A B A B C A B C C B A B C A B A C C A B A B C C A B B A C A B C A C B 8. Стратегии поиска в СОЗ 8. Поиск в СОЗ Причем поиск конечного состояния выполняется автоматически на основе реализованной в СОЗ стратегии поиска которая: реализует возможность выбора; позволяет выполнять шаги от начального...
23660. Нечеткие множества в системах основанных на знаниях 462.5 KB
  Для ее решения вводится два показателя: П АiФ = sup min фu Aiu это возможность что нечеткое множество Ф принадлежит значению Аi атрибута Ã. Рассмотрим геометрическую интерпретацию определения ПА1Ф: min фu A1u – представляет собой треугольник SQR т. sup min фu A1u – это точка Q т. Тогда ПА1Ф = min {max 0 min 1 1 m1 m2 1 2 max 0 min 1 1 m2 m1 2 1 }.