Транспортная задача

Различают два типа транспортных задач: по критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени). Рассмотрим экономико-математическую модель транспортных задач по критерию стоимости прикрепления пунктов отправления к пунктам назначения. Имеются m пунктов отправления груза и объемы отправления по каждому пункту a1, a2 ,...,am . Известна потребность в грузах b1, b2 ,...,bn по каждому из n пунктов назначения. Задана матрица стоимостей доставки по каждому варианту cij , i=1…m, j=1…n. Необходимо рассчитать оптимальный план перевозок, т.е. определить, сколько груза должно быть отправлено из каждого i-го пункта отправления (от поставщика) в каждый j-ый пункт назначения (до потребителя) xij с минимальными транспортными издержками. В общем виде исходные данные представлены в таблице Запасы (объемы отправлен ия) Потребители В1 В2 … Вn Поставщики А1 А2 … с11 х11 c22 x22 … … а1 х1n c21 x21 с1n … х12 … c2n а2 x2n … cm1 Аm cm2 … … … cmn am xm1 Потребность с12 b1 xm2 b2 xmn … bn Строки транспортной таблицы соответствуют пунктам отправления (в последней клетке каждой строки указан объем запаса продукта ai), а столбцы — пунктам назначения (последняя клетка каждого столбца содержит значение потребности bj). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i-го пункта в j-й: в правом верхнем углу находится цена перевозки единицы продукта, а в левом нижнем — значение объема перевозимого груза для данных пунктов. Транспортная задача называется закрытой, если суммарный объем отправляемых грузов равен суммарному объему потребности в этих грузах по пунктам назначения: Если такого равенства нет (потребности выше запасов или наоборот), задачу называют открытой. Определить, является транспортная задача закрытой или открытой Определить, является транспортная задача закрытой или открытой Определить, является транспортная задача закрытой или открытой Определить, является транспортная задача закрытой или открытой Определить, является транспортная задача закрытой или открытой Определить, является транспортная задача закрытой или открытой Для написания модели необходимо все условия (ограничения) и целевую функцию представить в виде математических уравнений. Все грузы из i-х пунктов должны быть отправлены.  x 11  x 12    x 1 n  a 1 ,   x 21  x 22    x 2 n  a 2 , .  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . ,  x  x    x mn  a m m2  m1 Все j-е пункты (потребители) должны быть обеспечены грузами в плановом объеме.  x 11  x 21    x m 1  b1 ,   x 12  x 22    x m 2  b 2 ,  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . ,  x  x    x  bn . 2n mn  1n Суммарные объемы отправления должны равняться суммарным объемам назначения. Должно выполняться условие неотрицательности переменных. Перевозки необходимо осуществить с минимальными транспортными издержками (функция цели): m Z  n  i 1 j 1 c ij x ij  min Когда в исходных условиях дана открытая задача, то ее необходимо привести к закрытой форме. В случае, если потребности по пунктам назначения превышают запасы пунктов отправления, то вводится фиктивный поставщик с недостающим объемом отправления; Если запасы поставщиков превышают потребности потребителей, то вводится фиктивный потребитель с необходимым объемом потребления. Варианты, связывающие фиктивные пункты с реальными, имеют нулевые оценки. После введения фиктивных пунктов задача решается как закрытая. Транспортные задачи могут решаться симплекс-методом. Однако перечисленные особенности позволяют для транспортных задач применять более простые методы решения. Допустимым решением транспортной задачи является опорный план, который используется в качестве начального базисного решения при нахождении оптимального решения. Существует три метода нахождения опорных планов: метод северо-западного угла, метод минимального элемента и метод Фогеля. «Качество» опорных планов, полученных этими методами, различается: в общем случае метод Фогеля дает наилучшее решение (зачастую оптимальное), а метод северо-западного угла– наихудшее. Все существующие методы нахождения опорных планов отличаются только способом выбора клетки для заполнения. Само заполнение происходит одинаково независимо от используемого метода. Методы составления начального опорного плана. Опорный план составляется последовательно, в несколько шагов (точнее, m + n - 1 шагов). На каждом из этих шагов заполняется одна клетка, притом так, что, либо полностью удовлетворяется один из заказчиков (тот, в столбце которого находится заполняемая клетка), либо полностью вывозится весь запас груза с одной из баз (с той, в строке которой находится заполняемая клетка). В первом случае мы можем исключить столбец, содержащий заполненную на этом шаге клетку, и считать, что задача свелась к заполнению таблицы с числом столбцов, на единицу меньшим, чем было перед этим шагом, но с тем же количеством строк и с соответственно измененным запасом груза на одной из баз (на той базе, которой был удовлетворен заказчик на данном шаге). Во втором случае исключается строка, содержащая заполняемую клетку, и считается, что таблица сузилась на одну строку при неизменном количестве столбцов и при соответствующем изменении потребности заказчика, в столбце которого находится заполняемая клетка. Начиная с первоначально данной таблицы и повторив (m + n - 2) раз описанный шаг, мы придем к «таблице», состоящей из одной строки и одного столбца (иначе говоря, из одной пустой клетки). Другими словами, мы пришли к задаче с одной базой и с одним потребителем, причем потребности этого единственного заказчика равны запасу груза на этой единственной базе. Заполнив последнюю клетку, мы освобождаем последнюю базу и удовлетворяем потребность последнего заказчика. В результате, совершив (m + n - 1) шагов, мы и получим искомый опорный план. Метод северо-западного угла. При этом методе на каждом шаге построения первого опорного плана заполняется левая верхняя клетка (северо-западный угол) оставшейся части таблицы. При таком методе заполнение таблицы начинается с клетки неизвестного x11 и заканчивается в клетке неизвестного xmn , т. е. идет как бы по диагонали таблицы перевозок. Составить опорный план методом северо – западного угла Составить опорный план методом северо–западного угла Составить опорный план методом северо –западного угла Метод наименьшей стоимости. При построении опорного плана этим методом на каждом шаге построения первой заполняется та клетка оставшейся части таблицы, которая имеет наименьший тариф. Если такая клетка не единственная, то заполняется любая из них. Составить опорный план методом наименьшей стоимости Составить опорный план методом наименьшей стоимости Составить опорный план методом наименьшей стоимости Метод Фогеля. Суть его состоит в следующем: В распределительной таблице по строкам и столбцам определяется разность между двумя наименьшими тарифами. Отмечается наибольшая разность. Далее в строке (столбце) с наибольшей разностью заполняется клетка с наименьшим тарифом. Строки (столбцы) с нулевым остатком груза в дальнейшем в расчет не принимаются. На каждом этапе загружается только одна клетка. Распределение груза производится, как и ранее. Проверку найденного решения на оптимальность можно произвести так называемым, методом потенциалов. Припишем каждой базе Ai, некоторое число Ui, и каждому потребителю Bj некоторое число Vj : так что Ui + Vj = cij , где cij – тарифы, соответствующие клеткам, заполненным базисными неизвестными. Эти числа Ui, и Vj называются потенциалами соответствующих поставщиков и потребителей. Потенциалы можно найти из системы равенств, рассматривая их как систему (m + n - 1) уравнений с m+n неизвестными. Так как неизвестных здесь на единицу больше, чем уравнений, то, по крайней мере, один из потенциалов мы можем выбрать произвольно, положив, например, U1 = 0; тогда остальные потенциалы легко определяются из системы уравнений. В случае если алгебраические суммы оценок для всех свободных клеток положительны, мы имеем единственное оптимальное решение. Для перехода от одного базиса к другому при решении транспортной задачи используются так называемые циклы. Циклом пересчета или короче, циклом в таблице перевозок называется последовательность неизвестных, удовлетворяющая следующим условиям: 1.Одно из неизвестных последовательности свободное, а все остальные – базисные. 2.Каждые два соседних в последовательности неизвестных лежат либо в одном столбце, либо в одной строке. 3. Три последовательных неизвестных не могут находиться в одном столбце или в одной строке. 4. Если, начиная с какого-либо неизвестного, мы будем последовательно переходить от одного к следующему за ним неизвестному то, через несколько шагов мы вернемся к исходному неизвестному. Если каждые два соседних неизвестных цикла соединить отрезком прямой, то будет получено геометрическое изображение цикла – замкнутая ломаная из чередующихся горизонтальных и вертикальных звеньев, одна из вершин которой находится в свободной клетке, а остальные - в базисных клетках. Можно доказать, что для любой свободной клетки таблицы перевозок существует один и только один цикл, содержащий свободное неизвестное из этой клетки, и что число вершин в цикле всегда четно. Очевидно, если снабдить вершины цикла поочередно знаками "+" и "–", приписав вершине в свободной клетке знак "+", то можно сказать, что в вершинах со знаком "+" число x прибавляется к прежнему значению неизвестного, находящегося в этой вершине, а в вершинах со знаком "–" это число x вычитается из прежнего значения неизвестного, находящегося в этой вершине. Пример. На трех заводах изготавливается шлакоблок, соответственно – Q1=100, Q2=150, Q3=50 тысяч штук. Шлакоблок поставляется на четыре строительные площадки, потребность которых соответственно – П1=75, П2=80, П3=90, П4=85 тысяч штук. Цена доставки (тариф) с каждого iго завода на каждую j-ю площадку задана матрицей – С: 6 7 3 5 С  1 2 5 6 8 10 20 1 Необходимо составить экономикоматематическую модель, позволяющую создать оптимальный план перевозки. При решении задачи рассмотреть различные варианты решения. Решение: Представим исходную информацию в виде таблицы. Потребители В1 В2 В3 Запасы (объемы отправления) В4 Поставщики А1 А2 А3 Потребность 6 7 3 1 2 5 5 100 150 6 8 75 10 80 20 90 1 85 50 300 330 Потребители В1 В2 В3 Запасы (объем отправления) В4 Поставщики А1 6 7 3 5 100 А2 1 2 5 6 150 8 10 20 А3 1 50 А4 30 330 Потребность 75 80 90 85 330 Потребители Поставщики В1 В2 6 В3 7 Запасы (объемы отправлен ия) В4 3 5 А1 100 75 25 1 А2 2 А4 Потребность 5 6 150 8 А3 10 20 1 50 30 75 80 90 85 330 330 Потребители Поставщики В1 В2 6 В3 7 Запасы (объемы отправлен ия) В4 3 5 А1 100 75 25 1 А2 2 А4 Потребность 5 6 150 55 90 8 А3 5 10 20 1 50 75 30 80 90 85 330 330 Потребители Поставщики В1 В2 6 В3 7 Запасы (объемы отправлен ия) В4 3 5 А1 100 75 25 1 А2 2 А4 Потребность 5 6 150 55 90 8 А3 5 10 20 1 50 75 50 80 30 30 90 85 330 330 Z= 1265 Потребители Поставщики А1 V1 А2 V2 А3 V3 А4 V4 Потребность В1 u1 В2 u2 6 75 В3 u3 7 25 150 1 50 50 80 6 20 100 5 75 5 10 5 90 8 3 2 55 В4 u4 1 Запасы (объемы отправлени я) 30 30 90 85 330 330 u1+ V1=6 V1+ u2=7 V2+ V2+ V2+ V3+ V4+ u2=2 u3=5 u4=6 u4=1 u4=0 u1+ V1=6 V1+ u2=7 V2+ u2=2 V2+ u3=5 V2+ u4=6 V3+ u4=1 V4+ u4=0 u1=-5 u2=-4 u3=-1 u4=0 V1=11 V2=6 V3=1 V4=0 -7 -6 cij Vi Uj xij 35 (11+ 11 -1) X13 X14 -7 -6 12 13 20 1 5 4 cij Vi Uj xij 35 1 8 10 20 (11+ 11 6 1 1 1 -1) -5 -5 -4 -1 -1 -5 -4 X13 X14 X21 X31 X32 X33 X43 X41 X42 Потребители Поставщики А1 V1 А2 V2 В1 u1 В2 u2 6 7 В4 u4 3 5 100 + 75 25 _ 1 2 5 6 150 - 55 + 8 А3 V3 В3 u3 Запасы (объемы отправле ния) 90 5 10 20 1 50 А4 V4 Потребность 75 50 80 30 30 90 85 330 330 Потребители Поставщики А1 V1 А2 V2 В1 u1 В2 u2 6 7 В4 u4 3 5 100 75 25 1 2 5 6 150 80 65 8 А3 V3 В3 u3 Запасы (объемы отправле ния) 5 10 20 1 50 А4 V4 Потребность 75 50 80 30 30 90 85 330 330 F=1090 Потребители Поставщики А1 V1 А2 V2 В1 u1 В2 u2 6 7 В4 u4 3 5 100 75 25 1 2 5 6 150 80 65 8 А3 V3 В3 u3 Запасы (объемы отправле ния) 5 10 20 1 50 А4 V4 Потребность 75 50 80 30 30 90 85 330 330 V1+ u1 =6 V1=4 u1=2 V1+ u3=3 V2=6 u2=-4 V2 + u2=2 V3=1 u3=-1 V2+ u3=5 V4=0 u4=0 V2+ u4=6 V3+ u4=1 V4+ u4=0 cij Vi Uj xij 7 1 -7 7 5 1 4 4 6 -4 2 X12 X14 X21 5 13 8 10 1 1 2 -4 X31 X32 20 1 -2 4 20 1 -1 -1 2 -4 X33 X43 X41 X42 Потребители Поставщики А1 V1 А2 V2 В1 u1 В2 u2 6 7 В4 u4 3 5 100 75 - 25 + 1 2 5 6 150 0 + 80 65 - 8 А3 V3 В3 u3 Запасы (объемы отправлен ия) 10 5 20 1 50 А4 V4 Потребность 75 50 80 30 30 90 85 330 330 Потребители Поставщики А1 V1 А2 V2 В1 u1 В2 u2 6 7 В4 u4 3 5 100 10 90 1 2 5 6 150 65 80 8 А3 V3 В3 u3 Запасы (объемы отправлен ия) 5 10 20 1 50 А4 V4 Потребность 75 50 80 30 30 90 85 330 330 F =635 V1+ u1 =6 V1=11 u1=-5 V1+ u3=3 V2=6 u2=-4 V2 + u2=2 V3=1 u3=-8 V2+ u1=1 V4=0 u4=0 V2+ u4=6 V3+ u4=1 V4+ u4=0 cij Vi Uj xij 7 11 -4 X12 -6 7 5 5 11 6 -8 X14 X23 Потребители Поставщики А1 V1 А2 V2 А3 V3 А4 V4 Потребность В1 u1 В2 u2 6 В3 u3 7 Запасы (объемы отправлени я) В4 u4 3 5 100 90 1 10 2 75 75 5 8 6 150 10 20 1 50 5 75 50 80 30 25 90 85 330 330 F= 595 U3+ V1=3 V1+ u4=5 V2+ u1=1 V2+ u2=2 V3+ u4=1 V4+ u2=0 V4+ u4=0 V4=0 u4=0 U3+ V1=3 V1=5 u1=-1 V1+ u4=5 V2=2 u2=0 V2+ u1=1 V3=1 u3=-2 V2+ u2=2 V4=0 u4=0 V3+ u4=1 V4+ u2=0 V4+ u4=0 2 cij Vi Uj xij 6 5 -1 X11 cij Vi Uj xij 2 6 5 -1 X11 2 7 5 X12 cij Vi Uj xij 2 6 5 -1 X11 2 5 4 8 9 21 1 2 7 5 6 8 10 20 5 2 2 1 1 1 -2 -1 -2 -1 -2 X12 X23 X24 X31 X32 X33 X41 X43 Метод наименьших затрат Потребители Поставщики В1 В2 6 А1 7 2 5 5 6 150 75 10 20 1 50 50 А4 3 100 8 А3 В4 1 А2 В3 Запасы (объемы отправления) 30 330 Потребность 75 80 90 85 330 Потребители Поставщики В1 В2 В3 В4 7 А1 5 6 3 90 100 2 А2 1 Потребность 150 75 8 А4 6 5 75 А3 Запасы (объемы отправления ) 10 1 20 50 50 30 75 80 90 85 330 330 Потребители Поставщики В1 В2 6 А1 7 75 100 10 5 6 150 10 20 1 50 А4 5 8 А3 3 2 75 В4 90 1 А2 В3 Запасы (объемы отправления) 50 30 5 25 330 Потребность 75 80 90 85 330