Транспортная задача линейного программирования

Транспортная задача ЛП В предыдущих темах были рассмотрены универсальные методы решения задач линейного программирования – обычный и двойственный симплекс-методы. Эти методы позволяют за конечное число шагов найти решение любой задачи линейного программирования, но число таких шагов может быть, вообще говоря, и очень большим. Поэтому наряду с общими методами в линейном программировании имеются специальные методы и модификации, которые позволяют ускорить процесс решения, учитывая специфику задачи (главным образом, структуру ограничений). К числу специальных задач, для которых созданы собственные методы решения, относится, в первую очередь, транспортная задача. Внимание к этой задаче обусловлено тем, что она: 1. Во-первых, очень часто встречается в практических работах по исследованию операций; 2. Во-вторых, к ней сводятся многие другие задачи, задачи о назначениях, задачи календарного планирования); 3. В-третьих, структура ограничений этой задачи обладает ярко выраженной спецификой, которую удается эффективно использовать при разработке вычислительных методов. В настоящее время транспортная задача ЛП широко применяется как в теоретических разработках, так и в практике планирования различных экономических процессов. Особо важное значение она имеет при решении вопросов рационализации поставок важнейших видов промышленной и сельскохозяйственной продукции, а также оптимального планирования грузопотоков и работы различных видов транспорта. 1. Постановка задачи и ее математическая модель. Рассмотрим решение однопродуктовой (однотоварной) транспортной задачи (например, задачи о перевозке угля в рамках региона). Пусть имеется m поставщиков с резервами (запасами) товара a1 , a2 , a3 , ..., am . Имеется соответственно n потребителей с потребностями b1 , b2 , ..., bn . Цена за перевозку единицы товара (например, за 1т.) известны. Именно, пусть сij - цена перевозки единицы товара от i-го поставщика j-му потребителю. Задание транспортной задачи и ее решение удобно осуществлять с помощью транспортной таблицы (матрицы) следующего вида: Потреб. bj bn b2 b1 … … Поставщики. a1 a2 x11 c21 c22 x22 … ci 2 ci1 … am x12 x 21 … … ai c12 c11 xi1 xi 2 … … cm 2 cm1 xm 2 xm1 … … c13 x13 c23 x23 … … … cij xij … ... … cmj xmj … … c1n x1n c2 n x2 n … … … cin xin … … … cmn xmn В левых верхних углах рабочих клеток таблицы записываем цены перевозок ( c11 - цена перевозки единицы товара от первого поставщика первому потребителю, cij -цена перевозки единицы товара от i-го поставщика к j-му потребителю). В самих клетках (по центру) будут размещаться планируемые перевозки. В общем случае xij обозначается планируемая перевозка объема товара от i–го поставщика j-му потребителю. Величины xij i  1, m; j  1, n нам как раз и требуется определить. Эти величины должны быть определены такими, чтобы общая стоимость перевозок была минимальной.   Обозначим общую стоимость через f , то она выражается суммой произведений каждой планируемой перевозки за соответствующую цену, т.е. m n f  c11x11  c12 x12  ...  c1 j x1 j  ...  c1n x1n  ...  cm1 xm1  ...  cmn xmn   cij xij i 1 j 1 (т.е. сумма произведений в каждой клеточке таблицы). Целью решения задачи является определение таких значений xij , при которых f принимает наименьшее из возможных значений. Исследование задачи и ее решение начинается с подсчета сумм товара, соответственно имеющегося у поставщиков m a1  a2  ...  ai  ...  am   ai i 1 и требуемого всеми потребителями n b1  b2  ...  bi  ...  bn   b j j 1 m Если эти суммы равны, т.е. n  a  b i 1 i j 1 j , то транспортная задача называется закрытой и ее можно сразу решать. Теорема 1: Любая транспортная задача, у которой суммарный объем запасов совпадает с суммарным объемом потребностей, имеет решение. m Если же n  a  b i i 1 j 1 , то задача называется открытой и для ее решения необходимо произвести j сбалансирование (уравнивание) поставок и потребностей. Делается это путем введения фиктивного поставщика или фиктивного потребителя в m зависимости от соотношения между собой сумм i 1 m 1. Если n  a и b i j 1 j : n  a  b i i 1 j 1 n m j 1 i 1 j , то вводится под номером m+1 фиктивный поставщик с поставкой am1   b j   ai m 2. Если n  a  b i 1 i j 1 m n i 1 j 1 j , то вводится под номером n+1 фиктивный потребитель с потребностью bn1   ai   b j . С введением дополнительно фиктивного поставщика или потребителя будет выполняться требование теоремы 1, и задача будет иметь решение. С введением фиктивного поставщика в транспортной таблице дополнительно появляются n рабочих клеток (дополнительная строка), если же добавлен фиктивный потребитель, то возникает дополнительно m рабочих клеток (дополнительный столбец). Какие цены присваивать дополнительным клеткам? Фиктивная строка или фиктивный столбец должны быть нейтральными по отношению к процедуре оптимального выбора плановых перевозок. Нейтральность может быть обеспечена тем, что все цены в фиктивных клетках выбираются одинаковыми. А чтобы эти цены при поставках на фиктивные клетки не влияли на значение целевой функции f их берут все равными нулю, т.е. для фиктивного поставщика cm1, 1  0,.., cm1, j  0,.., cm1, n  0 . Если же добавлен фиктивный потребитель, то c1, n1  0, c2, n1  0,.., ci , n1  0,..., cm,n  0 . После того, как обеспечили закрытость решаемой задачи (теореме 1), приступаем к построению опорного плана. Таким образом, математическая модель транспортной задачи имеет следующий вид. Найти наименьшее значение линейной функции m n F   cij xij  min (1) i 1 j 1 при ограничениях n  xij  ai ,  j 1 m  x b , ij j  i 1 xij  0 i  1, m (2)  j  1, n (3) В задаче: число неизвестных – (m*n) Число линейно независимых уравнений – (m+n-1) Число заполненных клеток в таблице – (m+n-1) Имеется целый ряд приемов по построению первого опорного плана. Некоторые из них носят формальный характер и не ориентируются на цены, другие же полностью ориентированы на цены перевозок. 1. Построение первоначального опорного плана. Как и для других задач линейного программирования, итерационный процесс по отысканию оптимального плана транспортной задачи начинают с нахождения опорного плана. Рассмотрим систему ограничений (2) и (3) транспортной задачи. Она содержит (m*n) неизвестных и (m+n) – уравнений, связанных соотношением (условием баланса) m n i 1 j 1  ai   bi (4) Если сложить почленно уравнения отдельно подсистемы (2) и отдельно подсистемы (3), то получим два одинаковых уравнения. Такое сложение равнозначно соответственно почленному сложению столбцов и почленному сложению строк таблицы. Наличие в системе ограничений двух одинаковых уравнений говорит об ее линейной зависимости. Если одно из этих уравнений отбросить, то в общем случае система ограничений должна содержать (m+n-1) линейно независимых уравнений, следовательно, невырожденный опорный план транспортной задачи содержит (m+n-1) положительных компонент или перевозок. Таким образом, если каким-либо способом получен невырожденными являются только (m+n1), а остальные равны нулю. Если условие транспортной задачи и ее опорный план записаны в виде таблицы, то клетки, в которых находятся отличные от нуля перевозки, называются занятыми, остальные – незанятыми. Занятые клетки соответствуют базисным неизвестным и их количество равно (m+n-1). Если ограничения транспортной задачи записаны в виде (2) и (3), то базисным неизвестным, включенным в опорный план, соответствует система линейно независимых векторов. Опорность плана при записи условий транспортной задачи в виде таблицы заключается в его ацикличности, т.е. в таблице нельзя построить замкнутый цикл, все вершины которого лежат в занятых клетках. Циклом называется набор клеток вид i1 j1 i2 j2   j2i2 ... j1im  , в котором две и только две соседние клетки расположены в одном столбце или одной строке таблицы, причем последняя клетка находится в той же строке или столбце, что и первая. Построение циклов начинают с какой-либо занятой клетки и переходят по столбцу (строке) к другой занятой клетке, в которой делают поворот под прямым углом и движутся по строке (столбцу) к следующей занятой клетке и т.д. пытаясь возвратиться к первоначальной клетке. Если такой возврат возможен, то получен цикл и план не является опорным. Клетки, в которых происходит поворот под прямым углом, определяют вершины цикла. В противном случае план является опорным. Всякий план транспортной задачи, содержащий более (m+n-1) занятых клеток, не является опорным, т.к. ему соответствует линейно зависимая система векторов. Если к занятым клеткам, определяющим опорный невырожденный план, следовательно, и цикличный, присоединить какую-либо незанятую клетку, то план становиться не опорным, появляется единственный цикл, все вершины которого, за исключением одной, лежат в занятых клетках. Построение первоначального опорного плана транспортной задачи рассмотрим на примерах. 2. Метод северо-западного угла. Задача 1: Пусть имеется 4 поставщика угля А1 , А2 , А3 , А4 с его запасами соответственно 100т, 250т, 200т и 300т. Имеется 5 потребителей В1 , В2 , В3 , В4 , В5 с потребностями в угле 200т, 200т, 100т, 100т, 250т соответственно. Цены за перевозку 1 тонны угля от поставщиков к потребителю составляют (в гривнах) 10 7 4 1 4     2 7 10 6 11 С  8 5 3 2 2   11 8 12 16 13    Определить план поставок с минимальными транспортными расходами. 1. Вычислим запасы поставщиков и потребности потребителей A  A1  A2  A3  A4  100  205  200  300  850 (запасы) B  B1  B2  B3  B4  B5  200  200  100  100  250  850 (потребности) 2. Сравним запасы и потребности, т.к. запасы и потребности равны, то силу теоремы 1 задача имеет решение. 3. Строим транспортную таблицу. Потребители Поставщики Запасы В1 В2 В3 В4 В5 А1 10 А2 2 А3 8 А4 11 7 4 1 4 7 10 6 11 100 100 150 5 3 50 8 2 100 12 2 50 16 13 100 250 200 300 50 250 Потребности 200 200 100 100 250 850 В таблицу заносим поставщиков и потребителей, запасы и потребности, стоимости поставки. Следующим шагом в заполнении таблицы является заполнение количества поставляемого от поставщика к потребителю: Берем клетку А1В1 для данной клетки: 1. Запасы составляют – 100т 2. Потребности составляют – 200т Поэтому для А1В1 отводим 100т, тогда для удовлетворения потребностей потребителя В1. Недостающее количество додаем от 2-го поставщика (А2). Получили, что возможности поставщика А1 использованы для потребителя В1, следовательно в остальных клетках строки А1 ставим прочерки. Для потребителя В1 поставки осуществляют А1 – 100т, А2 – 100т и его потребности полностью удовлетворены, следовательно в столбце В1 для поставщиков А3 и А4 ставим прочерки. Переходим к анализу запасов 2-го поставщика: 100т – мы использовали для потребителя В1, 250-100=150 – остаток не распределенных поставок. Анализируем потребности потребителя В2, которые составляют 200т, а наш остаток 150т, следовательно потребителю В2 отдаем остаток 150т, тогда в строке А2 в остальных колонках ставим прочерки. Потребителю В2 необходимо еще 200-150=50т и его недостающие потребности удовлетворим от поставщика А3. У поставщика А3 еще не использовано 200-50=150т потребности В3 составляют 100т – поставим ему все 100т от поставщика А3, остаток не использованных запасов 200-50-100=50т их отдадим потребителю В4. У потребителя В4 потребности составляют 100т из которых 50т он получил от поставщика А 3 недостающее дадим от поставщика А4 У поставщика А4 остаток запасов составляет 250т и потребности потребителя В5 составляют 250т, следовательно, мы их удовлетворим полностью. Проверим, является ли план – опорным. Соединим заполненные клетки линией, начиная от левого верхнего угла, т.к. линия непрерывна и соединяет все заполненные клетки, то план является опорным. Запишем опорный план: x11  100, x21  100, x22  150, x32  50, x33  100, x34  50, x44  50, x45  250, х12  х13  х14  х15  х23  х24  х25  х31  х35  х41  х42  х43  0 Найдем общую стоимость составленного плана: F  100 *10  100 * 2  150 * 7  50 * 5  100 * 3  50 * 2  50 *16  250 *13  6950 3. Метод минимальной стоимости Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел ai или bj . Затем из рассмотрения исключают либо строку, соответствующую поставщику, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены. Составим с помощью этого метода опорный план уже рассмотренной задачи (п.3). Составим таблицу Потребители Поставщики Запасы В1 В2 В3 В4 В5 10 А1 А2 7 4 1 4 11 100 2 200 7 10 6 5 3 2 50 А3 8 А4 11 2 200 8 12 16 100 250 200 13 300 150 100 50 Потребности 200 200 100 100 250 850 План не содержит циклов и состоит из семи положительных перевозок, следовательно, является вырожденным опорным планом. Определим его стоимость. F=100*1+200*2+50*7+200*2+150*8+100*12+50*13=4300 Метод аппроксимации Фогеля. При определении оптимального плана транспортной задачи методом аппроксимации Фогеля на каждой итерации по всем столбцам и по всем строкам находят разность между двумя записанными в них минимальными тарифами. Эти разности записываются в специально отведенных для этого строке и столбце в таблице условий задачи. Среди указанных разностей выбирают минимальную. В строке (или столбце), которой данная разность соответствует, заполняют на данной итерации. Если минимальный тариф одинаков для нескольких клеток данной строки (столбца), то для заполнения выбирают ту клетку, которая расположена в столбце (строке), соответствующем наибольшей разности между двумя минимальными тарифами, находящимися в данном столбе (строке). Пример. Используя метод аппроксимации Фогеля, найти опорный план транспортной задачи, исходные данные которой приведены в таблице. Пункты Пункты назначения Запасы отправления А1 А2 А3 Потребности В1 7 4 9 120 В2 8 5 2 50 В3 1 9 3 190 В4 2 8 6 110 160 140 170 470 Решение. Для каждой строки и столбца таблицы условий найдем разности между двумя минимальными тарифами, записанными в данной строке и столбце, и поместим их в соответствующем дополнительном столбце или дополнительной строке таблицы 1. Так, в строке А2 минимальный тариф равен 4, а следующий за ним равен 5, разность между ними 5 – 4 = 1. Точно так же разность между минимальными элементами в столбце В 4 равна 6 – 2 = 4. Вычислив все эти разности, видим, что наибольшая из них соответствует столбу В 4. В этом столбце минимальный тариф записан в клетке, находящейся на пересечении строки А 1 и столбца В4. Таким образом, эту клетку следует заполнить. Заполнив ее, тем самым мы удовлетворили потребности пункта В4. Поэтому исключим из рассмотрения столбец В4 будем считать Пункты пункты назначения запасы Разности по строкам запасы отправления пункта А1 равными 160 -110 = 50 ед. После этого определим следующую клетку для заполнения. Снова найдем разности между оставшимися двумя минимальными тарифами в каждой из строк и столбцов и запишем их во втором дополнительном столбце и во второй дополнительной строке таблицы 1. таблица 1. Как видно из таблицы, наибольшая указанная разность соответствует строке А 1. Минимальный тариф в этой строке записан в клетке, которая находится на пересечении ее со столбцом В 3. Следовательно, заполняем эту клетку. Поместим в нее число 50, тем самым предполагаем, что запасы в пункте А1 полностью исчерпаны, а потребности в пункте В3 стали равными 190 -50 = 140 ед. Исключим из рассмотрения строку А1 и определим новую клетку для заполнения. Продолжая итерационный процесс, последовательно заполняем клетки, находящиеся на пересечении строки А 3 и столбца В3, строки А3 и столбца В2, строки А2 и столбца В1, строки А2 и столбца В2. В результате получим опорный план Х= 120 20 0 30 50 110 140 При этом плане общая стоимость перевозок составит: S = 1*50 + 2*110 + 4*120 + 5*20 + 2*30 + 3*140 = 1330 Как правило, применение метода аппроксима ции Фогеля позволяет получить либо опорный план, близкий к оптимально му, либо сам оптимальны й план. А1 7 А2 4 А3 9 В1 В2 8 1 В3 50 5 120 Потребности Разности по столбцам 120 3 3 5 5 - 2 В4 110 9 8 3 6 140 190 2 2 6 - 110 4 - 20 2 30 50 3 3 3 3 1 6 - - - - 1 1 1 1 1 1 1 1 7 - - 160 140 170 470 Задача 2: На три базы А1, А2, А3 поступил однородный груз в количествах, соответственно равных 140, 180 и 110 ед. Этот груз требуется перевезти в пять пунктов назначения В 1, В2, В3, В4, В5, соответственно в количествах 60, 70, 120, 130 и 100 ед. Тарифы перевозок единицы груза с каждого из пунктов отправления в соответствующие пункты назначения указаны в таблице: Пункты назначения Пункты Запасы отправления В1 В2 В3 В4 В5 А1 2 3 4 2 4 140 А2 8 4 1 4 1 180 А3 9 7 3 7 2 160 Потребности 60 70 120 130 100 480 Найти план перевозок данной транспортной задачи методом северо-западного угла и методом минимального элемента. Решение методом северо-западного угла: Здесь число пунктов отправления m=3, а число пунктов назначения n=5. следовательно, опорный план задачи определяется числами 5+3-1=7, стоящими в 7-ми заполненных клетках. Составим таблицу транспортной задачи Пункты назначения Пункты Запасы отправления В1 В2 В3 В4 В5 2 3 4 2 4 А1 140 60 70 10 8 4 1 4 1 А2 180 110 70 9 7 3 7 2 А3 160 60 100 Потребности 60 70 120 130 100 480 Получаем опорный план: 0   60 70 10 0   х   0 0 110 70 0   0 0 0 60 100    Согласно данному плану перевозок, общая стоимость перевозок всего груза составляет: S=2*60+3*70+4*10+1*110+4*70+7*60+2*100=1380 Решение методом минимального элемента: Пункты отправления В1 А1 2 А2 8 А3 9 Потребности Опорный план: В2 3 Пункты назначения В3 4 2 10 В4 В5 4 1 4 1 120 7 50 60 140 130 4 3 70 70 60 7 120 2 130 Запасы 40 100 10 0 0 130 0    х   0 0 120 0 60   50 70 0 0 40   Общая стоимость перевозок: S=2*10+9*50+7*70+1*120+2*130+1*60+2*40=1480. 180 160 480 Примеры для самостоятельно решения (двумя методами). В таблицах ai - наличие товара у i-го поставщика b j - потребность j-го потребителя в этом товаре. В рабочих клетках указаны известные цены cij за перевозку единицы товара от i-го поставщика jму потребителю. Потреб. №1 запасы В1 В2 В3 В4 Поставщ. Потреб. запасы 4 5 2 10 В1 В2 В3 В4 Поставщики. А1 80 1 3 4 150 7 3 2 4 А1 А2 40 2 2 3 4 250 3 5 3 5 А2 А3 160 5 5 3 6 300 5 7 9 6 А3 А4 120 1 6 7 4 300 А4 потребности 75 125 60 140 потребности 100 400 400 100 №3 Потреб. Поставщики В1 В2 В3 В4 запасы А1 2 4 2 1 100 А2 3 1 5 6 150 А3 1 7 3 5 250 А4 5 8 6 1 500 потребности 100 400 200 300 В1 В2 В3 В4 №5 Потреб. Поставщики запасы А1 7 5 1 6 70 А2 5 3 4 9 120 А3 6 8 7 7 20 А4 4 3 5 5 40 потребности 30 70 50 100 №2 Потреб. Поставщ. В1 В2 В3 В4 запасы А1 4 3 1 70 А2 4 3 2 2 80 А3 6 3 5 5 80 А4 4 7 6 1 20 потребности 60 65 75 50 В1 В2 В3 В4 №4 Потреб. Поставщ. запасы А1 6 1 4 2 250 А2 3 5 1 3 300 А3 5 6 7 1 350 А4 2 1 8 5 100 потребности №6 400 200 200 200 4. Определение оптимального плана транспортной задачи. Для определения оптимального плана транспортной задачи разработано несколько методов. Метод потенциалов. Общий принцип определения оптимального плана задачи методом потенциалов аналогичен принципу решения задачи ЛП симплексным методом, а именно: сначала находят опорный план транспортной задачи, а затем его последовательно улучшают до получения оптимального плана. Для определения опорного плана транспортной задачи будем пользоваться одним из рассмотренных методов. Полученный план следует проверить на оптимальность. i  1, m; j  1, n Теорема 1. Если для некоторого опорного плана х   хij    транспортной задачи существуют такие числа 1 , 2 ,..., m , 1 ,  2 ,...,  n , что  j   i  cij при xij  0 и  j   i  cij   при xij  0  (1) (2)   для всех i  1, m и j  1, n , то х  хij – оптимальный план транспортной задачи. Определение: Числа  i и  j называются потенциалами соответственно пунктов назначения и пунктов потребления. Данная теорема позволяет построить алгоритм нахождения решения транспортной задачи. Он состоит в следующем: 1. одним из методов находится опорный план. 2. Для каждого из пунктов отправления и назначения определяют потенциалы  i и    j i  1, m; j  1, n . Эти числа находятся из системы уравнений  j   i  cij (3) где cij – тарифы, стоящие в заполненных клетках таблицы условий транспортной задачи. Т.к. число заполненных клеток равно n+m-1, то система (3) с n+m неизвестными содержит n+m-1 уравнений. Поскольку число неизвестных превышает на единицу число уравнений, то одно из неизвестных можно положить равным произвольному числу, например 1  0 , и найти последовательно из уравнений (3) значения остальных неизвестных. После того как все потенциалы найдены, переходим к третьему шагу. 1. Для каждой из свободных клеток определяют числа  ij   j   i  cij (4) Если все найденные числа  ij  0 , то найденный опорный план является оптимальным и задача решена. Если хотя бы одно число  ij  0 для некоторой свободной ячейки, то исходный опорный план не является оптимальным и необходимо перейти к следующему новому опорному плану. 2. Для построения нового опорного плана необходимо рассмотреть все свободные клетки, для которых  ij  0 , и среди данных чисел выбирают максимальное. Клетку, которой это число соответствует, следует заполнить. Заполняя выбранную клетку, необходимо изменить объемы поставок, записанных в ряде других занятых клеток и связанных с заполненной циклом. Определение: Циклом в таблице условий транспортной задачи называется ломаная линия, вершины которой расположены в занятых клетках таблицы, а звенья – вдоль строк и столбцов, причем в каждой вершине цикла встречается ровно два звена, одно из которых находится в строке, а другое – в столбце. Если ломаная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами. Примеры циклов: При правильном построении опорного плана для любой свободной клетки можно построить лишь один цикл. После того как для выбранной свободной клетки он построен, следует перейти к новому опорному плану. Для этого необходимо переместить грузы в пределах клеток, связанных с данной свободной клеткой. Это перемещение производят по следующим правилам: 1) каждой из клеток, связанных циклом с данной свободной клеткой, приписывают определенный знак, свободной клетке знак +(плюс), а всем остальным клеткам – поочередно знаки – (минус) и + (плюс). 1. в данную свободную клетку переносят меньшее из чисел xij , стоящих в минусовых клетках. Одновременно это число прибавляют к соответствующим числам, стоящим в плюсовых клетках. Клетка, которая ранее была свободной, становится занятой, а минусовая клетка, в которой стояло минимальное из чисел xij , считается свободной. После выполнения перемещения определяют новый опорный план транспортной задачи. Полученный опорный план проверяется на оптимальность по пункту 3. Пример: Для транспортной задачи, исходные данные которой приведены в таблице, найти оптимальный план и стоимость перевозок. Пункты назначения Пункты Запасы отправления В1 В2 В3 В4 А1 1 2 4 1 50 А2 2 3 1 5 30 А3 3 2 4 4 10 Потребности 30 30 10 20 90 Решение: Сначала, используя метод северо-западного угла, находим опорный план задачи. Для этого составляем новую таблицу. Таблица 1. Пункты Пункты назначения Запасы отправления В1 А1 1 А2 2 А3 3 В2 В3 2 30 В4 4 1 1 5 50 20 3 10 10 2 30 10 4 4 10 10 Потребности 30 30 10 20 90 Найденный опорный план проверяем на оптимальность. В связи с этим находим потенциалы пунктов отправления и назначения. Для определения потенциалов получаем систему 1   1  1  2   1  2  2   2  3 3   2  1  4   2  5  4   3  4 содержащую шесть уравнений с семью неизвестными. Пусть 1  0 , тогда 1  1 ,  2  2 ,  2  1 ,  3  0 ,  4  4 ,  3  0 . Для каждой свободной клетки вычисляем число  ij   j   i  cij 13  4 , 14  3 ,  21   32  0 ,  31  2 ,  33  4 Заключаем найденные числа в рамки и записываем их в каждую из свободных клеток. Таблица 2. Пункты назначения Пункты отправления А1 А2 В1 В2 1 2 10 2 3 3 В3 — 20 4 + 10 1 2 А3 1 + 3 -4 — 10 5 10 4 -2 Запасы В4 50 30 4 10 -4 10 Потребности 30 30 10 20 90 Т.к. среди чисел  ij имеются положительные, то построенный план перевозок не является оптимальным и надо перейти к новому опорному плану. Наибольшим среди положительных чисел  ij является 14  3 , поэтому для данной свободной клетки строим цикл пересчета (как показано линией в таблице выше) и производим сдвиг по этому циклу. Наименьшее из чисел в минусовых клетках равно 10. Клетка, в которой находится это число. Становится свободной в новой таблице. Другие числа в данной таблице получаются следующим образом: к числу 10, стоящему в плюсовой клетке табл.2, добавим 10, из числа 20 клетки и минусом табл.2 вычтем 10. клетка на пересечении строки А2 и столбца В1 становится свободной. После этих преобразований получаем новый опорный план табл.3. Таблица 3. Пункты отправления Пункты назначения Запасы В1 В2 В3 В4 1 А1 — 2 30 2 А2 3 3 20 2 10 10 -3 4 10 10 30 — 4 -1 30 50 5 +3 30 + -2 1 +1 Потребности 1 10 А3 4 20 10 90 Этот план проверяем на оптимальность. Снова находим потенциалы пунктов отправления и назначения. Для этого составляем следующую систему уравнений: 1   1  1  2   1  2  4   2  1  2   2  3 3   2  1  4   3  4 Полагаем 1  0 , получаем 1   4  1 ,  2  2 ,  3  0 ,  3  3 ,  2  1 . Для каждой свободной клетки вычисляем число  ij   j   i  cij Получаем 13  2 ,  21  0 ,  24  3 ,  31  1 ,  32  3 ,  33  1 . Т.к.  31  1 >0 и  32  3 >0 заключаем, что данный план перевозок не является оптимальным. Поэтому переходим к новому опорному плану (табл.4). Таблица 4. Пункты назначения Пункты отправления Запасы В1 1 А1 2 30 2 А2 Потребности В3 1 1 2 5 10 -3 4 -2 10 30 30 50 20 -4 20 В4 4 3 3 А3 В2 30 4 -3 -4 10 20 10 90 Сравнивая разности  j   i новых потенциалов, отвечающих свободным клеткам табл.4, с соответствующими числами сij , видим, что указанные разности потенциалов для всех свободных клеток не превосходит соответствующих чисел сij . Следовательно, полученный план  30 0 0 20     x   0 20 10 0   0 10 0 0    является оптимальным. При данном плане стоимость перевозок S=1*30+2*0+1*20+3*20+1*10+2*10=140. Задача: Для строительства трех дорог используется гравий из четырех карьеров. Запасы гравия в каждом из карьеров соответственно равны 120, 280 и 160 усл.ед. потребности в гравии для строительства каждой из дорог соответственно равны 130, 220, 60 и 70 усл.ед. Известны также тарифы перевозок 1 усл.ед. гравия из каждого из карьеров к каждой из строящихся дорог, которые задаются матрицей 1 7 9 5    L   4 2 6 8 . 3 8 1 2    Составить такой план перевозок гравия, при котором потребности в нем каждой из строящихся дорог были бы удовлетворены при наименьшей общей стоимости перевозок. Из условия задачи следует, что запасы в карьерах (120+280+160=560) больше, чем потребности в нем (130+220+60+70=480) на строящихся дорогах. Следовательно, модель исходной транспортной задачи является открытой. Чтобы получить закрытую модель, введем дополнительный пункт назначения В5 с потребностями, равными 560-480=80 усл.ед. Тарифы перевозки единицы гравия из всех карьеров в пункт В 5 полагаем равными нулю. В результате получаем закрытую модель транспортной задачи, план перевозок которой определяем методом минимального элемента (табл.1). Таблица 1. Пункты назначения Пункты отправления В1 В2 1 7 А1 40 + — 60 — 4 А2 3 А3 Потребности В3 В4 9 исвваи -2 2 -6 1 2 80 -1 — -1 + 8 220 8 В5 5 6 Запас ы +3 120 280 30 -1 60 70 130 220 60 70 +2 80 160 560 Оптимальный план находим методом потенциалов. Для определения потенциалов  1   1  1 1   2  4 1   3  3  5  1  0  2   2  2  3   3  1 4 3  2 Полагая 1  0 , находим 1  1,  5  0,  2  3,  2  5,  3  2,  3  3,  4  4 . Для каждой свободной клетки вычисляем число  ij   j   i  cij получаем систему 12  5  0  7  2 13  3  0  9  6 14  4  0  5  1  23  3  3  6  0  24  4  3  8  1  25  0  3  0  3 Заключаем найденные числа  32  5  2  8  1  35  0  2  0  2 в рамки и записываем их в соответствующие свободные клетки табл.1. Т.к. среди чисел  ij имеются положительные, то построенный план перевозок не является оптимальным и надо перейти к новому опорному плану. Наибольшим среди положительных чисел  ij :  25  3  0 и  35  2  0 является  25  3 , поэтому для данной свободной клетки строим цикл пересчета (табл.1) и производим сдвиг по этому циклу. Наименьшее число в минусовых клетках равно 60. клетка, в которой находится это число, становится свободной (табл.2). Другие числа в табл.2 получаются так: к числу 40, стоящему в плюсовой клетке табл.1 прибавим 60, вычтем 60 из числа 80, находящегося в минусовой клетке табл.1. После этих преобразований получаем новый опорный план табл.2. таблица 2 Пункты назначения Пункты отправления В1 В2 1 7 А1 + 100 — 4 9 исвваи -5 2 А2 3 — Потребности 130 20 8 -3 1 30 В5 5 6 8 В4 -6 220 -3 А3 В3 Запас ы 120 — 60 -3 2 280 -4 60 70 220 60 70 + +2 80 160 560 Найденный опорный план проверяем на оптимальность. Находим потенциалы пунктов отправления и назначения. Для определения потенциалов получаем систему:  1   1  1  2   2  2 1   3  3  5  1  0  5   2  0  3   3  1 4 3  2 Полагая 1  0 , находим 1  1,  5  0,  2  0,  2  2,  3  2,  3  3,  4  5 . Для каждой свободной клетки вычисляем число  ij   j   i  cij 12  2  0  7  5 13  3  0  9  6 14  5  0  5  0  21  1  0  4  3  24  3  0  6  3  25  5  0  8  3  32  2  2  8  4  35  0  2  0  2 Заключаем найденные числа в рамки и записываем их в соответствующие свободные клетки табл.2. Т.к. среди чисел  ij имеются положительные, то построенный план перевозок не является оптимальным и надо перейти к новому опорному плану. Наибольшим среди положительных чисел  ij :  35  2  0 , поэтому для данной свободной клетки строим цикл пересчета (табл.2) и производим сдвиг по этому циклу. Наименьшее из чисел в минусовых клетках равно 20. Клетка, в которой находится это число, становится свободной в новой табл.3. Другие числа табл.3 получаются так: к числу 100, стоящему в плюсовой клетке табл.2, добавим 20 и вычтем 20 из числа 30, находящегося в минусовой клетке табл.2. После этих преобразований получаем новый опорный план. Таблица 3. Пункты назначения Пункты отправления В1 В2 1 А1 7 -1 — 2 А2 А3 Потребности 5 6 8 В4 -2 8 -1 1 В5 120 -6 220 -1 3 9 исвваи 120 4 В3 Запас ы 60 -1 2 280 10 -6 60 70 20 130 220 60 70 80 160 560 Найденный опорный план проверяем на оптимальность. Для определения потенциалов получаем систему 1   1  1  2   2  2 5   2  0 1   3  3  3   3  1  4   3  2  5   3  0 Полагая 1  0 , находим 1  1,  5  2,  2  2,  2  0,  3  2,  3  3,  4  5 . Для каждой свободной клетки вычисляем число  ij   j   i  cij 12  0  0  1  1 13  3  0  9  6 14  5  0  5  0 15  2  0  0  2  21  1  2  4  1  23  3  2  6  1  24  5  2  8  1  32  0  2  8  6 Заключаем найденные числа в рамки и записываем их в соответствующие свободные клетки табл.3. Т.к. среди чисел  ij нет положительных чисел, то следовательно получен оптимальный план 120 0 0 0     х   0 220 0 0   10 0 60 70    При этом плане остается неиспользованным 60 усл.ед. гравия во втором карьере и 20 усл.ед. в третьем карьере, общая стоимость перевозок составляет S=1*120+3*10+2*220+1*60+2*70=790