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

Лекция 4. ТРАНСПОРТНАЯ ЗАДАЧА 1. Математическая модель транспортной задачи Транспортная задача (ТЗ) – ЗЛП, в которой оптимизируются транспортные издержки при перевозке идентичного штучного груза от т поставщиков (отправителей) из пунктов А1, …, Ат п получателям (потребителям) в пунктах В1, …, Вп, если известна матрица тарифов С =  с11 ... с1п   ... ... ...  , где сij – транспортные издержки при перевозке единицы с  ... с т 1 тп   груза от i-го поставщика j-му получателю. Для решения ТЗ удобно использовать не универсальный симплекс-метод, а расчетные распределительные таблицы ai bj a1 … am … b1 с11 bn с1n … … … … сm1 стп … Решением ТЗ является план перевозок единиц груза от каждого х х1п  ...  , где хij –   хт1 ... хтп  ... 11 поставщика каждому получателю, т.е. матрица Х* =  ... ...  число единиц груза, которое будет перевезено от i-го поставщика j-му получателю, при котором общие транспортные затраты будут минимальными, т.е. целевая функция F  cij xij  min, , хij  0. (ij ) Обозначим: а1, …, аm – количество единиц однородного груза у каждого из m поставщиков в пунктах отправления; b1, …, bn – количество единиц груза, заявленных получателями в пунктах назначения. Модель ТЗ называется закрытой, если а1 + …+ аm = b1 + …+ bn, т.е. общий запас груза у поставщиков равен общей потребности получателей этого груза, или, другими словами, спрос равен предложению. Модель ТЗ называется открытой, если а1 + …+ аm  b1 + …+ bn. Открытая модель ТЗ всегда может быть сведена к закрытой: если m  ai > i 1 n  b j , то в расчетную таблицу j 1 вводится дополнительный (п + 1)-й столбец для фиктивного получателя с потребностью bn+1 = m  ai – i 1 n  b j единиц груза; если j 1 m n i 1 j 1  ai <  b j , то вводится дополнительная (т + 1)-я строка для фиктивного поставщика с запасом аm+1 = n m j 1 i 1  b j –  ai единиц груза. Тарифы перевозок для фиктивных поставщика и получателя груза равны 0. Теорема. Для разрешимости транспортной задачи необходимо и достаточно, чтобы ее математическая модель была закрытой. Составим закрытую математическую модель ТЗ: 1) хij  0; 2) ограничения по запасам – весь груз должен быть вывезен, т.е. n  хij = j 1 xi1 + xi2 + … + xin = ai, i  1, m ; 3) ограничения по потребностям – все потребности удовлетворяются, т.е. m  хij = x1j + x2j + … + xmj = bj, j  1, n ; i 1 4) целевая функция – суммарные транспортные издержки F   cij xij = (ij ) с11x11 + с12x12 + … + стпхтп  min. Т.о., общее число неизвестных хij равно т  п, а число уравнений в системе ограничений т + п. Однако если в системе ограничений закрытой модели одно из уравнений будет отсутствовать, то его можно восстановить. Так, если не задано уравнение для элементов последнего столбца матрицы Х, то оно воспроизводится в виде: x1п+ x2п+…+ xmп = m n1 i 1 j 1  ai –  b j . В силу этого число линейно независимых уравнений в системе ограничений будет не более т + п – 1. Это означает, что число неизвестных хij > 0 в базисном решении ТЗ (число отличных от нуля неизвестных в опорном плане задачи) не более т + п – 1. Если опорный план содержит ровно т + п – 1 не равных 0 значений хij, то он называется невырожденным, если меньше т + п – 1, то – вырожденным. Алгоритм решения ТЗ методом потенциалов 1. Определить, является ли модель ТЗ закрытой. Если модель ТЗ открытая, то свести модель к закрытой введением фиктивного поставщика или получателя груза. 2. Построить начальный опорный план методом северо-западного угла, методом двойного предпочтения, методом наименьшего элемента, методом аппроксимации Фогеля и выбрать опорный план с наименьшим значением целевой функции F. 3. Найти потенциалы поставщиков i и получателей j из системы m + n – 1 уравнений j – i = cij, составленных для заполненных клеток, при этом считать, что 1= 0. 4. Проверить план перевозок на оптимальность: если все оценки свободных клеток ij = j – i – cij  0, то план оптимален, и в ответ следует записать оптимальную матрицу перевозок X* и минимальное значение транспортных издержек F*. Если же хотя бы одна оценка свободной клетки ij > 0, то, используя цикл пересчета, составить новый план перевозок и перейти к п. 3. Методы построения опорного плана ТЗ А) Метод северо-западного угла. Заполнение расчетной таблицы начинается с левой верхней клетки (1, 1) и продолжается последовательно вдоль строки, пока не будет исчерпан ресурс а1, после чего заполняется вторая строка и т.д. Количество х11 равно предельно возможной перевозке с учетом значений а1 и b1, т.е. х11 = min{а1, b1}. После заполнения клетки насыщенная строка или насыщенный столбец вычеркивается. Следующей предельно возможной перевозкой заполняется либо соседняя клетка справа той же строки, если ресурс а1 не исчерпан, либо соседняя клетка в следующей строке, если ресурс а1 исчерпан, и т.д. до заполнения последней клетки (m, n). Если при заполнении клетки, не являющейся последней в таблице, предельно возможной перевозкой насыщаются одновременно и строка и столбец, то прежде чем их вычеркнуть, следует сделать дополнительную 0поставку в клетку, смежную с заполненной последней: справа или под ней в зависимости от того, где тариф меньше. Клетка с 0-поставкой считается заполненной. В результате опорный план будет представлять m + n – 1 заполненных клеток расчетной таблицы. В) Метод двойного предпочтения. В каждом столбце и каждой строке расчетной таблицы отмечается минимальный тариф. В результате некоторые тарифы, минимальные как по строке, так по столбцу, будут иметь двойную отметку. Далее расчетная таблица последовательно заполняется предельно возможными поставками (после заполнения клетки насыщенная строка или насыщенный столбец вычеркивается). Сначала заполняются клетки с двойной отметкой. Затем заполняются клетки с одной отметкой в той очередности, в какой возрастают тарифы в этих клетках. Наконец заполняются клетки без отметок в той же последовательности. Если при заполнении клетки, не являющейся последней в таблице, предельно возможной перевозкой насыщаются одновременно и строка и столбец, то прежде чем их вычеркнуть, следует сделать дополнительную 0-поставку в не вычеркнутую ранее клетку с минимальным тарифом в строке и столбце, которые предстоит вычеркнуть. В результате опорный план будет представлять m + n – 1 заполненных клеток расчетной таблицы. С) Метод наименьшего элемента. Расчетная таблица последовательно заполняется по принципу: «Самая дешевая поставка выполняется в первую очередь», т.е. находится клетка с наименьшим тарифом и в нее записывается предельно возможная поставка; после заполнения клетки насыщенная строка или насыщенный столбец вычеркивается; следующей предельно возможной перевозкой заполняется клетка с минимальным тарифом из оставшихся и т.д. Если клеток с минимальным тарифом несколько, то выбирается та из них, заполнение которой обеспечит наибольший объем груза, поставляемый по данному тарифу. Если при заполнении клетки, не являющейся последней в таблице, предельно возможной перевозкой насыщаются одновременно и строка и столбец, то прежде чем их вычеркнуть, следует сделать дополнительную 0поставку по методу двойного предпочтения. В результате опорный план будет представлять m + n – 1 заполненных клеток расчетной таблицы. D) Метод аппроксимации Фогеля. По каждой строке и каждому столбцу находится разность между двумя наименьшими в них тарифами. Полученные разности фиксируются справа от таблицы для строк и под таблицей для столбцов. Находится наибольшая разность и в соответствующей строке или столбце заполняется клетка с минимальным тарифом предельно возможной поставкой. После заполнения клетки насыщенная строка или насыщенный столбец вычеркивается. Снова рассчитываются разности между минимальными тарифами с учетом отсутствия вычеркнутой строки или столбца, и процесс заполнения клеток продолжается по тем же признакам. Если максимальных разностей одного значения несколько, то заполняется клетка с наименьшим тарифом в соответствующих столбцах или строках. Если клеток для заполнения с одинаковым минимальным тарифом несколько, то заполняется та, для которой больше вторая максимальная разность. Если при заполнении клетки, не являющейся последней в таблице, предельно возможной перевозкой насыщаются одновременно и строка и столбец, то прежде чем их вычеркнуть, следует сделать дополнительную 0поставку по методу двойного предпочтения. В результате опорный план будет представлять m + n – 1 заполненных клеток расчетной таблицы. Е) Цикл пересчета. Цикл пересчета строится для получения нового опорного плана и представляет замкнутую ломаную, звенья которой параллельны строкам и столбцам, а вершины, в которых ломаная меняет направление по перпендикуляру, находятся в заполненных клетках таблицы. Исключением является одна свободная клетка в вершине цикла, та, для которой получена максимальная положительная оценка ij. Клетки в вершинах цикла поочередно помечаются знаками « + » и « – », начиная с « + » в указанной свободной клетке. Определяется наименьшая из поставок, расположенных в вершинах цикла со знаком «–». На эту поставку в клетках с « – » поставки сокращаются, а в клетках с « + » увеличиваются. Если в вершинах цикла со знаком « – » две и более одинаковые минимальные поставки, то одна из них с наибольшим тарифом остается свободной, а остальные заполняются 0-поставками. Алгоритм решения ТЗ методом дифференциальных рент 1. Дополнить расчетную таблицу столбцом справа для графы «Оценка» и строкой снизу для графы «Рента». 2. В каждом столбце пометить дугой минимальный тариф. 3. Клетки с помеченными тарифами заполняются предельно возможными поставками, причем, в первую очередь, заполняются клетки в тех столбцах или строках таблицы, в которых помечен только один тариф (при определении очередной клетки для заполнения, помеченные тарифы в ранее заполненных клетках уже исключаются из рассмотрения). 4. Находятся оценки поставщиков (алгебраическая сумма всех этих оценок всегда должна быть равна 0), которые указываются в столбце «Оценка»:  строка, соответствующая поставщику, запас которого не исчерпан, имеет положительную оценку, равную разности его запаса и вывезенного груза, распределенного по строке; соответствующая строка называется положительной;  строка, соответствующая поставщику, запас которого исчерпан, а потребности потребителей, клетки которых в соответствующей строке имеют помеченный тариф, не удовлетворены с учетом всех записанных поставок от других поставщиков, имеют отрицательную оценку, равную недостающему грузу у данного поставщика для удовлетворения их потребностей; соответствующая строка называется отрицательной;  строка, соответствующая поставщику, запас которого исчерпан, а потребности потребителей, клетки которых в соответствующей строке имеют помеченный тариф, удовлетворены с учетом всех записанных поставок от других поставщиков, имеют нулевую оценку. 5. Если имеются 0-оценки поставщиков, то поставить перед 0 знак « + » или « – »: в случае, когда в строке с нулевой оценкой есть помеченные тарифы, связанные по столбцу с помеченными тарифами в отрицательной строке, перед 0-оценкой ставится знак « – », если это не приводит к резкому сокращению числа помеченных тарифов, в остальных случаях – знак « + »; в зависимости от знака перед 0-оценкой строка будет или отрицательной, или положительной. 6. Для каждого столбца, имеющего помеченный тариф в отрицательной строке, определяется разность между минимальным тарифом в положительной строке (отмеченным или нет, не имеет значения) и помеченным тарифом в отрицательной строке. Полученные разности заносятся в графу «Рента». Если в столбце отсутствует помеченный тариф в отрицательной строке, или указанная разность равна 0, то клетка соответствующего столбца в графе «Рента» остается пустой. 7. Среди полученных разностей, отличных от нуля, определяется минимальная, называемая промежуточной рентой. 8. Строится новая расчетная таблица: все тарифы в положительных строках прежней таблицы переписываются в новую без изменений, а – в отрицательных строках увеличиваются на величину промежуточной ренты. 9. Если в результате заполнения таблицы все запасы поставщиков исчерпаны, а получатели груза полностью удовлетворены, т.е. все оценки поставщиков равны 0, то получен оптимальный план поставок и следует записать ответ: оптимальную матрицу перевозок X* и минимальное значение транспортных издержек F*, причем при расчете F* следует оптимальные поставки умножать на исходные тарифы, а не на тарифы последней расчетной таблицы, измененные промежуточными рентами. 2. Решение ТЗ методом потенциалов Пример. У трех поставщиков имеются одинаковые холодильники «Морозко» в количестве: а1 = 15, а2 = 25, а3 = 20, соответственно. Трем магазинам требуются такие холодильники, их потребности: b1 = 10, b2 = 15, b3 = 35. Затраты на доставку одного холодильника от каждого поставщика в эти магазины заданы матрицей тарифов в условных единицах: С =  1 3 2  4 5 7  . Найти оптимальный план поставок с  6 2 4   минимальными общими транспортными затратами. Решение. 1. Проверяем, является ли модель ТЗ закрытой. Поскольку 25 + 20 = 60, b j = 10+ 15 + 35 = 60, т.е.  аi =  аi b j  = 15 + модель ТЗ является закрытой. 2. Находим начальный опорный план. А) Метод северо-западного угла. Заполнение расчетной таблицы начинается с левой верхней клетки и продолжается последовательно вдоль строки, пока не будет исчерпан запас первого поставщика, после чего заполняется вторая строка и т.д. Клетки заполняются предельно возможной поставкой. После каждого заполнения клетки насыщенная строка или насыщенный столбец вычеркивается. Заполненных клеток должно быть 3 + 3 – 1 = 5. bj 10 ai 15 15 1 25 4 5 20 6 2 10 3 I цифрами (римскими указана 35 2 5 7 10 4 III  II 15 20 V  IV V последовательность вычеркивания строк/столбцов расчетной таблицы) F1 = 101 + 53 + 105 + 157 + 204 = 260. В) Метод двойного предпочтения. В каждом столбце и каждой строке расчетной таблицы отмечается минимальный тариф. В результате некоторые тарифы, минимальные как по строке, так по столбцу, будут иметь двойную отметку. Далее расчетная таблица последовательно заполняется предельно возможными поставками (после заполнения клетки насыщенная строка или насыщенный столбец вычеркивается). Сначала заполняются клетки с двойной отметкой. Затем заполняются клетки с одной отметкой в той очередности, в какой возрастают тарифы в этих клетках. Наконец, заполняются клетки без отметок в той же последовательности. bj 10 ai 15 25 20 15 35 1 3 4 5 7 6 2 4 2 bj 10 ai 35 4 2 4 5 7 6 2 15 1 25 20 15 10 I 15 II 4 5  III 25 V 5  IV V F2 = 101 + 52 + 257 + 152 + 54 = 245. С) Метод минимального элемента. Расчетная таблица последовательно заполняется по принципу: «Самая дешевая поставка выполняется в первую очередь», т.е. находится клетка с наименьшим тарифом и в нее записывается предельно возможная поставка; после заполнения клетки насыщенная строка или насыщенный столбец вычеркивается; следующей предельно возможной перевозкой заполняется клетка с минимальным тарифом из оставшихся и т.д. Если клеток с минимальным тарифом несколько, то, в первую очередь, заполняется та из них, которая включает наибольшую поставку единиц груза по данному тарифу. bj 10 ai 15 35 3 2 4 5 7 6 2 15 1 25 20 10 I 4 15 II 5  III 25 V 5  IV V F3 = 101 + 52 + 257 + 152 + 54 = 245. D) Метод аппроксимации Фогеля. По каждой строке и каждому столбцу находится модуль разности между двумя наименьшими в них тарифами. Полученные разности фиксируются в конце соответствующих строк и столбцов. Для наибольшей разности в соответствующей строке или столбце заполняется клетка с минимальным тарифом предельно возможной поставкой. После заполнения клетки насыщенная строка или насыщенный столбец вычеркивается. Снова находятся указанные разности с учетом отсутствия вычеркнутой строки или столбца, и процесс заполнения клеток продолжается. Если максимальных разностей одного значения несколько, то заполняется соответствующая клетка с минимальным тарифом. Если таких минимальных тарифов несколько, заполняется клетка с возможно большей поставкой. bj 10 ai 15 1 25 4 10 15 35 3 2 5 7 5 1 1 1 II 25 1 2 2V 6 20 2 4 15 1 1 III 3 I 5 2 2 5 V 2 2 2 IV F4 = 101 + 52 + 257 + 152 + 54 = 245. 3. Проверяем опорный план с наименьшим значением целевой функции на оптимальность. Каждому поставщику присваивается потенциал , каждому получателю – потенциал  с указанием соответствующих порядковых номеров. Эти потенциалы i и j находятся из системы m + n – 1 уравнений j –  i = cij, составленных для заполненных клеток, при этом одна неизвестная – свободная, поэтому будем считать, что  1= 0. По найденным значениям потенциалов рассчитываются оценки свободных клеток ij = j – i – cij . Если все оценки ij  0, то план – оптимальный и следует записать ответ: оптимальную матрицу перевозок X* и минимальное значение транспортных издержек F*. Если же хотя бы одна оценка свободной клетки ij > 0, то, план не оптимальный, и находится другой опорный план. Выполняем расчеты для плана: bj ai 1 15 2 25 3 20 1 2 3 10 15 35 3 2 4 5 7 6 2 1 10 15 4 5 25 5 Для заполненных клеток: 1 – 1 = 1; 3 – 1 = 2; 3 – 2 = 7; 2 – 3 = 2;  1 = 0; 2 = – 5; 3 = –2; 1 = 1; 2 = 0; 3 = 2. 3 – 3 = 4; Для свободных клеток: 12 = 2 – 1 – с12 = 0 – 0 – 3 = – 3; 21 = 1 – 2 – с21 = 1 + 5 – 4 = + 2; 22 = 2 – 2 – с22 = 0 + 5 – 5 = 0; 31 = 1 – 3 – с31 = 1 + 2 – 6 = – 3 4. Поскольку имеется положительная оценка 21, то план не оптимальный. Строим цикл пересчета для клетки с этой положительной оценкой (если положительных оценок несколько, то цикл пересчета строится для клетки с наибольшей положительной оценкой). Цикл пересчета представляет замкнутую ломаную, звенья которой параллельны строкам и столбцам, а вершины, в которых ломаная меняет направление по перпендикуляру к прежнему звену, находятся в заполненных клетках таблицы. Началом и концом цикла является свободная клетка, для которой этот цикл строится. Для каждой свободной клетки возможен единственный цикл пересчета. bj ai 1 15 2 25 3 20 1 4 6 1 2 3 10 15 35 – 10 + 3 2 5 7– 25 2 4 15 +5 5 Клетки в вершинах цикла поочередно помечаются знаками « + » и « – », начиная с « + » в свободной клетке. Определяется наименьшая из поставок, расположенных в вершинах цикла со знаком « – ». На эту поставку поставки в клетках с « – » сокращаются, а в клетках с « + » увеличиваются. При этом свободная клетка заполняется, а клетка с наименьшей поставкой в отрицательной клетке становится свободной. Т.о., в новом опорном плане весь груз поставщиков вывозится, все получатели удовлетворяют свои потребности, число заполненных клеток остается равным m + n – 1. Получаем новый опорный план с 5-ю заполненными клетками: bj ai 1 15 2 25 3 20 1 2 3 10 15 35 1 3 2 15 4 5 7 10 6 15 2 4 15 5 5. Проверяем новый опорный план на оптимальность. Для заполненных клеток: 3 – 1 = 2; 2 – 3 = 2; 1 – 2 = 4; 3 – 3 = 4; 1 = 0; 1 = – 1; 2 = – 5; 2 = 0; 3 = –2; 3 = 2. 3 – 2 = 7;  Для свободных клеток: 11 = 1 – 1 – с11 = – 1 – 0 – 1 = – 2; 12 = 2 – 1 – с12 = 0 – 0 – 3 = – 3; 22 = 2 – 2 – с22 = 0 + 5 – 5 = 0; 31 = 1 – 3 – с31 = – 1 + 2 – 6 = – 5. Поскольку среди оценок свободных клеток нет положительных, то полученный план оптимальный. Поскольку среди оценок есть 0, то полученный план не единственный, т.е. существует альтернативный оптимальный план. Находим транспортные расходы для оптимального плана F* = 152 + 104 + 157 + 152 + 54 = 225.  0 0 15  Ответ: Х* = 10 0 15  , F* = 225. #  0 15 5    Пример. Построить опорный план для ТЗ bj 10 ai 20 20 10 10 20 10 1 3 8 2 10 4 5 4 5 6 7 4 а) методом северо-западного угла; б) методом минимального элемента. Решение а) bj 10 ai 20 20 10 1 10 3 10 10 20 8 2 5 4  II 10 4 5 10 6 I 20 7 II 4  III  III 10  IV IV В таблице 6 заполненных клеток, F1 = 101 + 103 + 205 + 104 = 180. б) bj 10 ai 20 20 10 1 10 3 10 10 20 8 10 5 10 6 I 2 4 5 10  III 4  IV 4 V 10 7 10 V II  II В таблице 6 заполненных клеток, F2 = 101 + 102 + 104 + 105 + 107 = 190. # 2. Если в цикле пересчета 0-поставка отмечена знаком « – », т.е. если 0 является минимальной поставкой в отрицательной вершине цикла, то 0 переместится по циклу в свободную клетку, при этом целевая функция полученного опорного плана окажется равной прежнему значению. Тем не менее, новый план следует проверить на оптимальность. Если предыдущий план был не оптимальный, то новый может оказаться оптимальным. 3. Если в вершинах цикла две или более отрицательных вершин находятся в клетках с минимальной поставкой, то только одна из этих клеток станет свободной – та, которая имеет максимальный тариф. Остальные такие клетки заполняются 0-поставками. 3. Решение ТЗ методом дифференциальных рент При решении ТЗ методом потенциалов сначала строится произвольный начальный опорный план перевозки всего груза, и далее он последовательно улучшается. При решении ТЗ методом дифференциальных рент сначала наилучшим образом распределяется между получателями часть груза, имеющегося у поставщиков, и далее последовательно вывозится остальная часть груза, причем распределение всего груза означает достижение оптимального плана поставок. Решим методом дифференциальных рент ТЗ, приведенную в примере п. 2. Решение ТЗ методом дифференциальных рент находится в следующей последовательности: 1. Расчетная таблица дополняется справа столбцом с графой «Оценка» и снизу строкой с графой «Рента». 2. В каждом столбце помечается минимальный тариф. 3. Клетки с помеченными тарифами заполняются предельно возможными поставками, причем, в первую очередь, заполняются те свободные клетки, которые являются единственными в столбце или строке таблицы с помеченным тарифом. 4. Находятся оценки поставщиков, которые указываются в столбце «Оценка» (алгебраическая сумма всех этих оценок всегда должна быть равна 0):  строка, соответствующая поставщику, запас которого не исчерпан, имеет положительную оценку, равную разности его запаса и вывезенного груза, распределенного по строке; соответствующая строка считается положительной;  строка, соответствующая поставщику, запас которого исчерпан, а потребности получателей, клетки которых в соответствующей строке имеют помеченный тариф, не удовлетворены с учетом всех записанных поставок от других поставщиков, имеют отрицательную оценку, равную недостающему грузу у данного поставщика для удовлетворения их потребностей; соответствующая строка считается отрицательной;  строка, соответствующая поставщику, запас которого исчерпан, а потребности получателей, клетки которых в соответствующей строке имеют помеченный тариф, удовлетворены с учетом всех записанных поставок от других поставщиков, имеют нулевую оценку. 5. Если имеются 0-оценки поставщиков, то поставить перед 0 знак « + » или « – »: в случае, когда в строке с нулевой оценкой есть помеченные тарифы, связанные по столбцу с помеченными тарифами в отрицательной строке, то перед 0-оценкой ставится знак « – », если это не приводит к резкому сокращению числа помеченных тарифов, в остальных случаях – знак « + ». 6. Для каждого столбца, имеющего помеченный тариф в отрицательной строке, определяется разность между минимальным тарифом в положительной строке (отмеченным или нет, не имеет значения) и помеченным тарифом в отрицательной строке. Полученные разности заносятся в графу «Рента». Если в столбце отсутствует помеченный тариф в отрицательной строке, или указанная разность равна 0, то клетка соответствующего столбца в графе «Рента» остается пустой. 7. Среди полученных разностей, отличных от нуля, определяется минимальная, называемая промежуточной рентой. 1) bj ai 10 15 35 Оценка 3 2 4 5 7 + 25 6 2 4 +5 15 1 25 20 Рента 10 15 – 3 5 – 30 2 Поскольку в 1-й таблице есть положительные оценки, то строим новую расчетную таблицу: все тарифы в положительных строках прежней таблицы переписываются в новую без изменений, а – в отрицательных строках увеличиваются на величину промежуточной ренты. Для новой таблицы повторяем все действия, что и для предыдущей. bj 10 ai 2) 15 5 4 4 5 7 6 2 15 3 25 20 Рента 10 15 3 1 4 35 Оценка 5 – 25 + 25 5 3 –0 Поскольку во 2-й таблице есть положительные оценки, то строим новую расчетную таблицу и продолжаем расчет. bj 10 ai 3) 15 4 25 4 20 7 Рента  10 15 6 5 5 7 3 15 2 – 5 35 Оценка 15 – 15 + 15 5 2 –0 Поскольку в 3-й таблице есть положительные оценки, то строим новую расчетную таблицу и продолжаем расчет. bj 10 ai 4) 15 6 25 4 20 9 15 8 10 5 5 7 15  7 7 35 Оценка 15  20 Рента 8. В результате заполнения 4-й таблицы все запасы поставщиков исчерпаны, а получатели груза полностью удовлетворены, т.е. все оценки поставщиков равны 0. Т.о., получен оптимальный план поставок. В ответ записываем оптимальную матрицу перевозок X* и минимальное значение транспортных издержек F*, (при расчете F* следует оптимальные поставки умножать на исходные тарифы, а не на тарифы последней расчетной таблицы): F* = 152 + 104 + 155 + 204 = 225. Как видим, получен альтернативный план с тем же значением целевой функции, что и при решении задачи методом потенциалов.  0 0 15  Ответ: Х* = 10 15 0  , F* = 225. #  0 15 20   