Транспортная задача - задача об оптимальном плане перевозок продукта (-ов) из пунктов наличия в пункты потребления. Разработка и применение оптимальных. - презентация

1

2 Транспортная задача - задача об оптимальном плане перевозок продукта (-ов) из пунктов наличия в пункты потребления. Разработка и применение оптимальных схем грузовых потоков позволяют снизить затраты на перевозки. Транспортная задача является по теории сложности вычислений NP-сложной или входит в класс сложности NP. В качестве вводных примеров транспортной задачи для студентов по линейному программированию в рамках Исследования Операций (ИО) предлагается следующий набор доступных задач и подходов их решения: Транспортная задача (классическая) - задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи). Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).

3 Задача о максимальном потоке в сети изучается уже более 60 лет. Интерес к ней подогревается огромной практической значимостью этой проблемы. Методы решения задачи применяются на транспортных, коммуникационных, электрических сетях, при моделировании различных процессов физики и химии, в некоторых операциях над матрицами, для решения родственных задач теории графов, и даже для поиска Web-групп в WWW. Исследования данной задачи проводятся во множестве крупнейших университетов мира. 60 лет назад, эта задача решалась simplex методом линейного программирования, что было крайне не эффективно. Форд и Фалкресон предложили рассматривать для решения задачи о максимальном потоке ориентированную сеть и искать решение с помощью итерационного алгоритма. В течение 20 лет, все передовые достижения в исследовании данной задачи базировались на их методе.

4 В 1970г. наш соотечественник, Диниц, предложил решать задачу с использованием вспомогательных бесконтурных сетей и псевдомаксимальных потоков, что намного увеличило быстродействие разрабатываемых алгоритмов. А в 1974 Карзанов улучшил метод Диница, введя такое понятие как предпоток. Алгоритмы Диница и Карзанова, как и исследования Форда и Фалкерсона, внесли огромный вклад в решение данной проблемы. На основе их методов 15 лет достигались наилучшие оценки быстродействия алгоритмов. В 1986г. появился третий метод, который также без раздумий можно отнести к фундаментальным. Этот метод был разработан Голдбергом и Таряном, и получил название Push- Relabel метода. Для нахождения максимального потока, он использует предпотоки и метки, изменяемые во время работы алгоритма. Push- Relabel алгоритмы очень эффективны, и исследуются до сих пор. И, наконец, в 1997г. Голдберг и Рао предложили алгоритм, присваивающий дугам неединичную длину. Это самый современный из всех известных мне алгоритмов. Асимптотическая оценка его быстродействия превзошла O(nm), о такой скорости многие годы можно было только мечтать. Уверен, что за прошедшие годы алгоритм Голдберга и Рао тщательно изучался и улучшался.

5 Имеется ряд пунктов производства с объемами производства в единицу времени (месяц, квартал), равными соответственным пунктам потребления потребляющие за тот же промежуток времени соответственно продукции. В случае, если решается закрытая (сбалансированная) задача, сумма объемов производства на всех т пунктах-поставщиках равна сумме объемов потребления на всех n пунктах-получателях: Тогда наиболее рациональным прикреплением поставщиков к потребителям будет такое, при котором суммарные затраты на транспортировку будут наименьшими:

6 При этом каждый потребитель получает нужное количество продукта: и каждый поставщик отгружает весь произведенный им продукт: Как и во всех подобных случаях, здесь также оговаривается неотрицательность переменных: поставка от какого-то пункта производства тому или иному пункту потребления может быть равна нулю, но отрицательной, т. е. следовать в обратном направлении, быть не может. Поскольку принято, что затраты на перевозки растут здесь пропорционально их объему, то перед нами задача линейного программирования одна из задач распределения ресурсов.

7 Несбалансированную (открытую) транспортную задачу приводят к виду, показанному выше, искусственно: в модель вводятся так называемые фиктивный поставщик или фиктивный потребитель, которые балансируют спрос и потребление. В настоящее время разработано множество различных алгоритмов решения транспортной задачи: распределительный метод, метод потенциалов, дельта-метод, венгерский метод, метод дифференциальных рент, различные сетевые методы и т. д. Они относительно просты, по ним составлены десятки программ для вычислительных машин. Задачи эти часто усложняются разного рода дополнительными условиями: например, в них включается расчет не только себестоимости перевозок, но и себестоимости производства продукции (производственно-транспортная задача), оптимизируется совместно доставка взаимозаменяемых видов продукции (скажем, различных кровельных материалов), оптимизируется доставка грузов с промежуточными базами (складами). Кроме того, следует учитывать, что математическая модель транспортной задачи позволяет описывать множество ситуаций, весьма далеких от проблемы перевозок, в частности, находить оптимальное размещение заказов на производство изделий с разной себестоимостью. Ниже (гл. 6) рассматривается решение транспортной задачи на графах методом потенциалов.

8 Распределительные задачи связаны с распределением ресурсов по работам, которые необходимо выполнить. Задачи этого класса возникают тогда, когда имеющихся в наличии ресурсов не хватает для выполнения каждой работы наиболее эффективным образом. Поэтому целью решения задачи, является отыскания такого распределения ресурсов по работам, при котором либо минимизируются общие затраты, связанные с выполнением работ, либо максимизируется получаемый в результате общий доход.

9 Таблица 1 Ресурсы Работы, которые нужно выполнитьОбъем имеющихся ресурсов j1j1 J2J2 …JiJi …JnJn R1R1 C 1.1 C 1. 2 …C 1.j …C1.nB1B1 R2R2 C 2.1 C 2. 2 …C 2.j …C 2.n B2B2 …………………… RiRi C i.1 C i.2 …C i.j …C i.n BiBi …………………… RmRm C m.1 C m.2 …C m.j …C m.n BmBm Объём требуемых ресурсов A1A1 A2A2 …AiAi...AnAn

10 Большинство распределительных задач можно представить в виде матриц, приведенных в таблице 1. Элементы Сi,j стоящие в клетках матрицы, соответствуют затратим или доходу, отвечающим выделению, одной единицы ресурса Ri на работу Jj. Величины _Сi,j могут быть независимыми или зависимыми. Так например, затраты, обусловленные назначением одной автомашины на некоторый маршрут доставки грузов, не зависят от того какие машины назначены на обслуживание других маршрутов. В то же время при распределении средств между подразделениями фирмы доход от затрат определенного количества денег одним ее подразделением (скажем производством) обычно зависит от того, какие средства будут затрачены другими подразделениями (скажем отделом сбыта). В теории распределения рассматриваются преимущественно задачи с независимыми затратами и доходами. Это объясняется не тем, что такие задачи более важны, а лишь тем, что для них значительно легче строить модели и получать решения.

11 Если затраты (или доход), определяемые объемом Хi,j ресурса I, выделенного на выполнение работы Jj, ровны Xi,j,. Сi,j, то имеем линейную распределительную задачу. Распределительные задачи с независимыми линейными функциями затрат (или дохода) стали объектом, наиболее интенсивных исследований, в виду того что для их решения были развитые эффективные, итеративные методы линейного программирования. Однако имеются также методы решения некоторых нелинейных распределительных задач, в том числе методы основанные на линейной аппроксимации. Распределение ресурсов для одного периода времени может влиять на распределения ресурсов для последующих периодов, а может не оказывать на них никакого влияния. Если каждое из последовательности распределений не зависит от всех остальных, то такая задача называется статистической, в противном случае имеем динамическую распределительную задачу. Статистические задачи исследованы в большей степени, чем динамические, но для решения некоторых типов динамических задач успешно применяются методы линейного динамического и динамического программирования. Для решения некоторых динамических задач применяют методы стохастического программирования. В таких задачах принятие решений основано на вероятностных оценках будущих значений параметров, имеющих фиксированное распределение вероятностей.

12 Основные метода решения распределительных задач, в частности линейного программирования, построены на допущении, что объёмы, имеющихся в наличии ресурсов (Bi), требуемые объёмы (аi) и затраты (Сi,j) точно известны. Если общий объём наличных ресурсов Sbi (i=l...m) равен общей потребности в них Sai(j=l...n), то имеет место сбалансированная (закрытая) распределительная задача: Если же Sаj ¹ Sbi, то задача называется несбалансированной (открытой). Если ресурсы можно разделить между работами, то некоторые работы можно выполнять с помощью различных комбинаций ресурсов. Если работы и ресурсы измеряются в единицах одной и той же шкалы, то такие задачи обычно называют транспортными или задачами разложения. Если же работы и ресурсы выражаются в различных единицах измерениях, то задача называется общей распределительной задачей. Таким образом транспортная задача является частным случаем общей распределительной задачи.

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

14 Для того, чтобы некоторый допустимый план X={xi,j}m.n транспортной задачи был оптимальным необходимо и достаточно, чтобы ему соответствовала система из m+n чисел U1, U2,..., Um; V1, V2,..., Vn, удовлетворяющих условиям Vj-Ui 0 имело бы место строгое равенство Vj-Ui=Cij (2). Числа Ui, Vi называются потенциалами соответственно пунктов отправления, а условия (1) (2) называются условиями потенциальности системы. Теорема. Для оптимальности плана транспортной задачи необходимо и достаточно, чтобы он был потенциальным. Алгоритм метода потенциалов состоит из предварительного и повторяющегося общего шага. Предварительный план состоит из следующих операций:

15 1. составление первоначального ациклического плана перевозок; 2. построение для полученного плана системы m+n чисел U1,U2,..., Um; V1, V2, …, Vn таких, чтобы выполнялись условия Vj-Ui=Cij для всех базисных клеток; 3. проверка построенной системы на потенциальность. Если система нe потенциальна, т.е. план Х не оптимален, переходим к общему шагу. Общий шаг повторяется до тех пор, пока система не станет потенциальной. Он состоит из следующих операций: 1) улучшение плана, т.е. замена плана Х новым планом X' со стоимостью перевозок, не превышающей стоимость плана X; 2) построение для X' новой системы потенциалов U'i, V'j путем перестроения старой; 3) проверка системы U'i, V'j на потенциальность. Предложенный алгоритм сходится за конечное число шагов.

16 В предыдущих случаях рассматривалась только такая задачу о перевозках, в которой сумма запасов равна сумме заявок: Sai=Sbj (где i=1,.., m; j=1,...,n) (3) Это классическая транспортная задача, иначе называемая, транспортной задачей с правильным балансом. Встречаются такие варианты транспортной задачи, где условие (3) нарушено. В этих случаях говорят о транспортной задаче с неправильным балансом. Баланс транспортной задачи может нарушаться в 2-ух направлениях: 1. Сумма запасов в пунктах, отправлении превышает сумму поданных заявок Sai>Sbj (гдеi=1,...,m; j=1,...,n); 2. Сумма поданных заявок превышает наличные запасы Sai S bj, (где i=1, m ; j=1, n).

17 Требуется найти такой план перевозок (X), при котором все заявки будут выполнены, а общая стоимость перевозок минимальна. Очевидно при этой постановке задачи некоторые условия-равенства транспортной задачи превращаются в условия-неравенства, а некоторые остаются равенствами. Xi,j £ ai (i=1 …, m ). Xi,j = bi (j=1 …, n ). Mы умеем решать задачу линейного программирования, в какой бы форме равенств или неравенств ни были бы заданы её условия. Поставленная задача может бытъ решена, например, обычным симплекс- методом. Однако, задачу можно решить проще, если искусственным приемом свести её к ранее рассмотренной транспортной задаче с правильным балансом. Для этого, сверх имеющихся n пунктов назначения B1, В2,..., Вn, введём ещё один, фиктивный, пункт назначения Вn+1 которому припишем фиктивную заявку, равную избытку запасов над заявками Bn+1 = S аi, - S bj, (где i=1, …, m ; j=l,..., n),

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

19 Решение транспортной задача начинается с нахождения опорного плана. Для этого существуют различные способы. Например, способ "северо- западного угла", способ минимальной стоимости по строке, способ минимальной стоимости по столбцу и способ минимальной стоимости таблицы. Способ "северо-западного угла". Будем заполнять таблицу перевозками постепенно начиная с левой верхней ячейки ( ceвеpo-западного угла таблицы ). Будем рассуждать при этом следующим образом. пункт B1 подал заявку на 18 единиц груза. Удовлетворим эту заявку за счёт запаса 48, имеющегося в пункте A1, и запишем перевозку 18 в клетке (1,1). После этого заявка пункта B1 удовлетворена, а в пункте A1 осталось ещё 30 единиц груза. Удовлетворим засчёт них заявку пункта В2, (27 единиц), запишем 27 в клетке (1,2);

20 оставшиеся 3 единицы пункта а1 назначим пункту В3. В составе заявки пункта В3 остались неудовлетворенными 39 единиц. Из них 30 покроем за счет пункта А2, чем его запас будет исчерпан, и еще 9 возьмём из пункта Аз. Из оставшихся 18 единиц пункта Аз 12 выделим пункту В4; оставшиеся 6 единиц назначим пункту В5, что вместе со всеми 20 единицами пункта А4 покроет его заявку. За этом распределение запасов закончено; каждый пункт назначения получил груз согласно своей заявки. Это выражается в том, что сумма перевозок в каждой строке равна соответствующему запасу, а в столбце заявке. Таким образом, нами сразу же составлен клан перевозок, удовлетворяющий балансовым условиям. Полученное решение является опорным решением транспортной задачи: Составленный нами план перевозок, не является оптимальным по стоимости, так как при его построении мы совсем не учитывали стоимость перевозок Сi,j.

21 Другой способ способ минимальной стоимости по строке основан на том, что мы распределяем продукцию от пункта Аi, не в любой из пунктов Вj, а в тот, к которому стоимость перевозки минимальна. Если в этом пункте заявка полностью удовлетворена, то мы убираем его из расчетов м находим минимальную стоимость перевозки из оставшихся пунктов Вj. Во всем остальном этот метод схож с методом "северо-западного угла". Способ минимальной стоимости по столбцу аналогичен предыдущему способу. Их отличие состоит в том, что во втором способе мы распределяем продукцию от пунктов Bi к пунктам Аj, по минимальной стоимости Cj.i. Опорный план, составленный способами минимальных стоимостей, обычно боже близок к оптимальному решению. Клетки таблицы, в которых стоят ненулевые перевозки, являются базисными. Их число должно равняться m + n - 1. Необходимо отметить также, что встречаются такие ситуации, когда количество базисных клеток меньше чем m + n - 1. В этом случае распределительная задача называется вырожденной. И следует в одной из свободных клеток поставить количество перевозок равное нулю. Составляя план по способам минимальных стоимостей в отличии от плана по способу "северо-западного угла" мы учитываем стоимости перевозок Сi.j, но все же не можем утверждать, что составленный нами план является оптимальным.