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

ТЕМА 6. ТРАНСПОРТНАЯ ЗАДАЧА В МАТРИЧНОЙ ПОСТАНОВКЕ Транспортная задача линейного программирования получила в настоящее время широкое практическое применение на транспорте и в промышленности для составления наиболее экономичного плана перевозок однородного продукта или взаимозаменяемых продуктов. Кроме того, транспортную модель можно применять при рассмотрении ряда практических ситуаций, связанных с управлением запасами, планированием производства и другими задачами. Огромное количество возможных вариантов перевозок затрудняет получение достаточно экономного плана эмпирическим и экспертным путем. Поэтому внедрение математических методов и вычислительной техники в планирование перевозок дает большой экономический эффект. 6.1. Постановка задачи и ее математическая модель Классическая транспортная задача формулируется следующим образом. Имеется m пунктов производства  A1, А2 ,...... Аm  однородного продукта и n пунктов потребления B1, B2 ,......Bn  . Известны объемы производства (мощность поставщика) ai i  1, m каждого пункта производства и размеры спроса (мощность потребителя) b j  j  1, n  каждого пункта потребления. Перевозка единицы груза из пункта А в пункт В связана с «транспортными издержками» (расходами) сij . В термин «транспортные издержки» не всегда вкладывается непосредственный экономический смысл. «Транспортные издержки» в различных задачах могут означать стоимость, расстояние, тариф, время, расход топлива и т.д. Требуется составить план перевозок, обеспечивающий удовлетворение спроса всех пунктов потребления за счет реализации продукта, произведенного всеми пунктами производства при минимальных общих транспортных издержках. Обозначим xij  количество единиц груза, запланированное к перевозке от iтого поставщика к j-тому потребителю. Тогда транспортные издержки на перевозку xij единиц груза от i-того поставщика к j-тому потребителю составят сij xij единиц, а суммарные транспортные издержки на перевозку продукта из всех пунктов производства во все пункты потребления выражаются суммой   m n   cij xij . i 1 j 1 Систему ограничений получаем из следующих условий задачи: а) весь продукт, произведенный в каждом пункте производства, должен быть вывезен в пункты потребления, это означает, что n  xij  ai ,  i  1, m ; j 1 б) спрос потребителей должен быть полностью удовлетворен, это означает, что m  xij  b j ,  j  1, n ; i 1 в) объемы перевозок – неотрицательные числа, т.е. xij  0  j  1, n,  i  1, m . Таким образом, математическая модель транспортной задачи имеет следующий вид: m n f x     cij xij  min, i 1 j 1 n  xij  ai ,  i  1, m, j 1 m  xij  b j , i 1  j  1, n, xij  0  j  1, n,  i  1, m. Условия транспортной задачи удобно формализовать в виде матрицы (таблицы). Пункты потребления B1 c12 c11 x11 A2 c21 … x12 c22 … x21 Am c1n a1 x1n c2n a2 x22 x2 n … cm1 cm 2 b1 … xm 2 xm1 Объем потребления Объем производства Bn … b2 … Ai A1 … B2 … Пункты производства Bj cmn am xmn bn В рассмотренной модели предполагается, что суммарное производство продукта совпадает с суммарными потребностями, т.е. m n i 1 j 1  ai   b j . Такая модель называется закрытой (замкнутой) или сбалансированной, транспортной моделью. 6.2. Особенности транспортной модели Ограничения и целевая функция транспортной модели являются линейными, поэтому она относится к классу задач линейного программирования. Но есть некоторые особенности, которые заставляют говорить о задаче особо: – все коэффициенты в системе ограничений равны единице; – каждая переменная задачи входит только в два ограничения – одно по поставщику, другое по потребителю. 6.3. Открытая модель транспортной задачи В реальных условиях не всегда объем производства равен спросу. В этом случае имеем открытую или несбалансированную транспортную модель. Для открытой модели может быть два случая: а) из пунктов производств вывозится не весь произведенный продукт, т.е. m n i 1 j 1  ai   b j . В этом случае баланс производства и потребления может быть нарушен и ограничения типа «равно» заменяются ограничениями в виде неравенств. n  xij  ai ,  i  1, m ; j 1 б) суммарный объем производства меньше суммарного объема потребления, т.е. m n i 1 j 1  ai   b j . В этом случае полное удовлетворение всех пунктов потребления невозможно и ограничения типа «равно» заменяются ограничениями в виде неравенств. m  xij  b j ,  j  1, n . i 1 В обоих случаях открытую модель можно сбалансировать. В случае а) следует ввести фиктивный пункт потребления bn 1 с объемом потребления m n i 1 j 1 bn 1   ai   b j и дополнительные переменные xi , n 1 , i  1, m, приводящие ограничения-неравенства к виду равенств и понимаемые как фиктивные перевозки из пунктов производства в фиктивный пункт потребления. Величина bn 1 определяет суммарный объем нереализованного продукта. Размеры остатков xi , n 1 в пунктах производства можно регулировать в зависимости от введенного штрафа ci , n 1 за единицу не вывезенного продукта из пункта А. При равных транспортных издержках на перевозку единицы груза от поставщиков к фиктивному потребителю в оптимальном плане ему направляется груз от наименее выгодных поставщиков. Если по условию задачи нереализованная продукция не штрафуется, штрафы ci , n 1 за фиктивные перевозки обычно полагаются равными 0. В случае б) следует ввести фиктивный пункт производства с объемом n m j 1 i 1 производства am 1   b j   ai и дополнительные переменные xm 1, j , j  1, n . В этом случае транспортные издержки cm 1, j можно интерпретировать как штраф за недоставку единицы груза j-тому потребителю. Прежде, чем решать какую-либо транспортную задачу, необходимо проверить, к какой модели она принадлежит. В случае необходимости привести к закрытой модели и только после этого приступать к решению задачи. 6.4. Построение начального опорного плана транспортной задачи 6.4.1. Свойства и признаки опорного плана Из общей теории задач линейного программирования известно, что допустимое решение (план) задачи называется опорным, если столбцы матрицы условий при ненулевых компонентах плана линейно независимы. Из определения следует, что число ненулевых компонентов опорного плана не должно превышать ранга системы ограничений. Система ограничений транспортной задачи содержит m  n уравнений, но одно из них (любое) линейно зависит от остальных, что подтверждается, например, так: разность суммы первых m ограничений и суммы n последних ограничений в силу условия m n i 1 j 1  ai   b j обращается в тождество. Можно показать, что ранг системы ограничений равен m  n  1 . Итак, число ненулевых компонент опорного плана не должно превосходить m  n  1 . Если в опорном плане число ненулевых перевозок равно m  n  1 , план называется невырожденным. Его ненулевые компоненты являются базисными переменными. Если число ненулевых перевозок меньше m  n  1 , план называется вырожденным. Часть его базисных переменных принимают нулевые значения. Проверка линейной независимости является неоправданно трудоемкой. Для транспортной задачи существует более простой способ проверки опорности плана, основанный на геометрических свойствах матрицы перевозок. Рассмотрим эти свойства. Назовем ситуацией i, j  совокупность i -того пункта производства и j -того пункта потребления. Ситуации i, j  соответствует клетка транспортной таблицы и переменная xij плана транспортной задачи. Ситуация называется основной, если объем перевозок по ней положителен, xij  0 . Последовательность ситуаций, где каждая последующая ситуация сохраняет поочередно номер пункта производства или пункта потребления предыдущей, называется маршрутом. Замкнутый маршрут называется циклом. Геометрически в транспортной таблице (матрице перевозок) цикл – это замкнутая ломаная линия, удовлетворяющая следующим условиям: – все вершины ломаной находятся в клетках таблицы; – ребра ломаной расположены по строкам или по столбцам; –к каждой вершине подходят ровно два ребра, причем одно по строке, другое по столбцу. Примеры циклов изображены на рисунке (рис.6.1.). Рис.6.1. В описанных выше понятиях условие опорности плана задает следующая теорема. Теорема. Для того, чтобы план транспортной задачи являлся опорным, необходимо и достаточно, чтобы из его основных ситуаций невозможно было составить замкнутый маршрут. Другими словами, план является опорным, если он ацикличен, т.е. нельзя построить ни одного цикла, вершины которого лежат в клетках с положительными перевозками. 6.4.2. Общая процедура построения начального опорного плана Опорный план транспортной задачи можно построить по описываемой ниже процедуре. Коротко сущность ее состоит в последовательной максимальной загрузке произвольно выбираемых ситуаций. 1) Обозначим I  1,2,..., m – множество номеров пунктов производства, J  1,2,..., n – множество номеров пунктов потребления. Изначально полагаем, что все поставки равны нулю, т.е. xij  0, i  I , j  J . i, j , i  I , j  J и назначаем по ней максимально возможный объем перевозок xij  min ai , b j . 2) Выбираем произвольную ситуацию 3) Корректируем объемы производства и потребления на величину выбранной перевозки, вычисляя остатки мощности и потребности ~ a~i  ai  xij , b j  b j  xij . 4) Вычеркиваем в транспортной таблице строку или столбец с нулевым объемом производства или потребления: – если a~i  0 , вычеркиваем строку i ; ~ – если b j  0 , вычеркиваем столбец j . 5) Повторяем процесс с пункта 2) в сохраненной части таблицы до тех пор, пока не будут вычеркнуты все строки или столбцы таблицы. Замечание 1. В случае вырожденности опорного плана при выполнении процедуры остаются неопределенными номера нулевых базисных компонент. Для последующего же улучшения плана обычно требуется иметь полную информацию о его базисе. С целью полной конкретизации базиса можно предложить следующую модификацию пункта 4). В случае аi  b j  0 вычеркивается только строка или только столбец, причем, если в текущей таблице остается несколько столбцов и только одна строка, вычеркивается j-тый столбец. Если остается несколько строк и один столбец, вычеркивается i-тая строка. При такой модификации все назначенные в пункте 3) компоненты плана, в том числе и нулевые, являются базисными, а их общее число равно m  n  1 . Замечание 2. В случае вырожденности уже полученного по процедуре опорного плана недостающие до m  n  1 базисные компоненты могут быть выбраны среди нулевых компонент произвольно, но так, чтобы в совокупности с ранее назначенными они не образовывали цикла. Рассмотренная процедура оставляет свободу в выборе ситуации i, j , i  I , j  J . Этой свободой желательно распорядиться так, чтобы полученный опорный план был, возможно, более близок по критерию к оптимальному. В зависимости от способа выбора очередной ситуации различают различные методы построения начального опорного плана. Рассмотрим некоторые из них. 6.4.2.1. Метод северо-западного угла Процедура будет представлять метод северо-западного угла, если очередная ситуация i, j , i  I , j  J в пункте 2) выбирается в левой верхней клетке сохраненной части таблицы, т.е. в северо-западном углу таблицы. Пример. Найти методом северо-западного угла начальный опорный план транспортной задачи Заводы A1 A2 A3 A4 Мощности b j B1 1,2 3 1,5 1 Хранилища B2 1,8 1 2,5 2 B3 1 0,8 1,2 1 4 8 7 Мощности ai 6 5 6 2 Задача является замкнутой, так как суммарная мощность поставщиков 4  ai  6  5  6  2  19 i 1 3 совпадает с суммарной мощностью  b j  4  8  7  19 j 1 Последовательно на итерациях метода получаем. ~ 1) (i, j )  (1,1), x11  min( 6;4)  4, a~1  6  4  2, b1  4  4  0. Исключаем из рассмотрения первый столбец. 1,2 1,8 1 4 3 6-4=2 1 0,8 5 1,5 2,5 1,2 6 1 2 1 2 4-4=0 8 7 ~ 2) (i, j )  (1,2), x12  min( 2;8)  2, aˆ1  2  2  0, b2  8  2  6 Исключаем первую строку. 1,2 1,8 4 3 1 2 1 2-2=0 0,8 5 1,5 2,5 1,2 6 1 2 1 2 4-4=0 8-2=6 7 3) (i, j )  (2,2), x22  min( 5;6)  5, a~2  5  5  0, bˆ2  6  5  1. Исключаем вторую строку. потребителей 1,2 1,8 4 3 1 2 1 2-2=0 0,8 5 1,5 2,5 5-5=0 1,2 6 1 2 1 2 4-4=0 6-5=1 7 ~  6  1  5, bˆ  1  1  0 . 4) (i, j )  (3,2), x32  min( 6;1)  1, a 3 2 Исключаем второй столбец. 1,2 1,8 4 3 1 2 1 2-2=0 0,8 5 1,5 2,5 5-5=0 1,2 1 1 2 6-1=5 1 2 4-4=0 1-1=0 7 ~ 5) (i, j )  (3,3), x33  min( 5;7)  5, aˆ3  5  5  0, b3  7  5  2 . Исключаем третью строку. 1,2 1,8 4 3 1 2 1 2-2=0 0,8 5 1,5 2,5 5-5=0 1,2 1 1 2 5 5-5=0 1 2 4-4=0 1-1=0 7-5=2 6) Для оставшейся ситуации (i, j )  (4,3), x43  2, aˆ 4  2  2  0, bˆ3  2  2  0 . 1,2 1,8 4 3 1 2 1 2-2=0 0,8 5 1,5 2,5 5-5=0 1,2 1 1 2 4-4=0 5 5-5=0 2 2-2=0 1 1-1=0 2-2=0 4  0 Получили невырожденный опорный план X     0 2 5 1 0  0 . 5  2  Количество занятых клеток m  n  1  4  3  1  6 . Соответствующее значение целевой функции f x   1,2  4  1,8  2  1 5  2,5 1  1,2  5  1 2  23,9 . 6.4.2.2. Метод минимальной стоимости (минимального элемента в матрице) До сих пор при выборе ситуации i, j , i  I , j  J никак не использовались удельные затраты (тарифы), что не могло не сказаться на качестве плана. Естественно рассматривать в первую очередь наиболее дешевые ситуации. В этом и состоит особенность метода: в качестве очередной ситуации i, j , i  I , j  J в пункте 2) процедуры выбирается клетка с минимальным тарифом сij в сохраненной части таблицы. Применим метод минимального элемента к задаче, рассмотренной выше в примере: 1) Выбираем наиболее дешевую ситуацию i, j   2,3, x23  min( 5,7)  5, a2  5  5  0, b3  7  5  2. Исключаем вторую строку. 1,2 1,8 1 6 3 1 0,8 5 1,5 2,5 5-5=0 1,2 6 1 2 1 2 4 8 7-5=2 2) В сокращенной матрице min cij   c13  1. Рассматриваем ситуацию i, j   1,3. x13  min 6;2  2, a~1  6  2  4, bˆ3  2  2  0 . Исключаем третий столбец 1,2 1,8 3 1 1 1,5 2 6-2=4 5 5-5=0 0,8 2,5 1,2 6 1 2 1 2 4 3) min cij   c41  1. 8 2-2=0 i, j   4,1, ~ x41  min 2;4  2, a~4  2  2  0, b1  4  2  2 . Исключаем четвертую строку. 1,2 1,8 3 1 1 1,5 2 6-2=4 5 5-5=0 0,8 2,5 1,2 6 1 2 1 2-2=0 2 4-2=2 8 2-2=0 4) min cij   c11  1,2 . i, j   1,1, x11  min 4;2  2, aˆ1  4  2  2, bˆ1  2  2  0. Исключаем первый столбец 1,2 1,8 1 2 3 1 1,5 2 4-2=2 5 5-5=0 0,8 2,5 1,2 6 1 2 1 2-2=0 2 2-2=0 8 2-2=0 5) min cij   c12  1,8 i, j   1,2, x12  min 8;2  2, a1  2  2  0, b~2  8  2  6. Исключаем первую строку. 1,2 1,8 2 3 1 2 1 1,5 2 2-2=0 5 5-5=0 0,8 2,5 1,2 6 1 2 1 2-2=0 2 2-2=0 8-2=6 2-2=0 6) c32  2,5 . i, j   3,2, x32  6. Получили опорный план. 1,2 1,8 2 3 1 2 1 1,5 2 2-2=0 5 5-5=0 0,8 2,5 1,2 6 1 2 6-6=0 1 2-2=0 2 2-2=0 6-6=0 2-2=0 f x   1,2  2  1,8  2  1 2  0,8  5  2,5  6  1 2  29 . Несмотря на рассмотрение локально наиболее выгодных ситуаций, качество плана оказалось хуже, чем в методе северо-западного угла (29>23,9). Хотя данная ситуация является нетипичной, она подтверждает, что даже «хороший» метод определения опорного плана (не гарантирующий, кончено, его оптимальности) может дать решение хуже произвольно выбранного. 6.5. Метод потенциалов решения транспортных задач Метод потенциалов – первый точный метод решения транспортной задачи – был предложен в 1949 г. Л.В. Канторовичем и М.К. Гавуриным. Метод позволяет, отправляясь от некоторого опорного плана (первоначального распределения), построить оптимальное решение транспортной задачи за конечное число итераций (шагов). Численный анализ транспортной задачи существенно опирается на результаты теории двойственности. Сформулируем задачу, двойственную к транспортной задаче. m n f x     cij xij  min, i 1 j 1 n  xij  ai , i  1,m, m n i 1 j 1 F  y    ai  ui    b j v j  max,  ui  0 i  1, m, j 1 m  xij  в j , j  1,n, vj   0 j  1, n, i 1 xij  0, i  1, m, j  1, n.  ui  v j  cij , i  1, m, j  1, n. Поставим в соответствие ограничениям по поставщикам переменные  ui  , а ограничениям по потребителям переменные v j . Тогда согласно общему правилу построения двойственных задач, получим задачу, двойственную к транспортной задаче. Критерий оптимальности плана транспортной задачи может быть получен на основе теорем двойственности и формируется следующим образом. Замечание. В классической литературе при рассмотрении метода потенциалов обычно ограничениям по поставщикам ставятся в соответствие переменные ui произвольного знака. Именно отсутствие ограничения на знак переменной дает возможность поставить в соответствие переменные  ui  . Данная замена, обусловлена упрощением восприятия экономического смысла потенциалов. Теорема. Для оптимальности плана X  xij  транспортной задачи необходимо и достаточно существование чисел v1 , v2 ,..., vn и u1 , u2 ,..., um таких, что v j  ui  cij ui  cij  v j , причем ui  cij  v j , если xij  0, i  1,m, j  1,n. Числа ui и v j обычно называют потенциалами соответственно пунктов отправления и пунктов назначения. Экономический смысл двойственных переменных: ui – стоимость продукта у поставщика; v j – стоимость продукта у потребителя. Согласно теореме опорный план будет оптимальным, если выполнены следующие условия: а) для каждой занятой клетки транспортной таблицы ui  cij  v j , (*) б) для каждой свободной клетки ui  cij  v j . (**) Если хотя бы одна свободная клетка не удовлетворяет условию (**), то опорный план не оптимальный и его можно улучшить, вводя в базис переменную, соответствующую клетке, для которой нарушается условие оптимальности (т.е. в клетку нужно переместить некоторое количество единиц груза). Сформулированная теорема позволяет построить алгоритм метода потенциалов. 6.5.1. Алгоритм метода потенциалов Шаг 1. Нахождение системы потенциалов. Пусть одним из рассмотренных методов найден опорный план транспортной задачи. Для каждой базисной переменной (занятой клетки транспортной таблицы) этого плана потенциалы удовлетворяют условию ui  cij  v j . Так как число потенциалов равно m  n , а система (*) состоит из m  n  1 уравнения, для нахождения какого-либо решения этой системы необходимо одному из потенциалов придать произвольное значение (обычно полагается равным 0 некоторое ui ). Вывод. Потенциалы расставляют по занятым клеткам, используя равенство ui  cij  v j , при этом начинают с того, что некоторой строке присваивают нулевой потенциал (лучше выбирать строку с наибольшим количеством занятых клеток). Шаг 2. Проверка выполнения условия оптимальности. Для каждой свободной клетки проверяется условие ui  cij  v j : – если условие выполнено для всех клеток, то рассматриваемый план является оптимальным. – если же для некоторой свободной клетки ui  cij  v j , то план не является оптимальным и его можно улучшить включением в него соответствующей переменной. В клетках, в которых не выполнено условие оптимальности проставляют улучшение ij  v j  ui  cij . Шаг 3. Выбор переменной для включения в базис. Обычно, для включения в базис выбирается переменная, соответствующая наибольшему  ij . В соответствующую клетку необходимо выполнить поставку. Шаг 4. Построение ломаной (цикла) и определение величины перераспределения груза. Делая поставку в выбранную клетку, мы нарушаем баланс строк и столбцов распределительной таблицы. Поэтому следует изменить объемы поставок в других занятых клетках. Для этого строится цикл (ломаная), начальной вершиной которого будет выбранная для поставки свободная клетка. Все остальные вершины цикла (ломаной) должны располагаться в базисных (занятых) клетках. При правильном построении опорного плана для любой свободной клетки можно построить только один цикл. Указанная ломаная обладает свойствами: – так как клетка закрывает либо строку, либо столбец, то обязательно либо в строке, либо в столбце существует занятая клетка, которую можно соединить с нашей клеткой отрезком, а значит рано или поздно мы придем в занятую клетку. Вывод: любые две занятые клетки могут быть соединены ломаной; – ломаная не образует циклов внутри себя (рис.6.1); закрывает строку закрывает столбец закрывает столбец закрывает строку закрывает столбец Рис. 6.1 закрывает строку – ломаная единственная; – если к множеству занятых клеток добавить пустую, то обязательно возникнет цикл, причем единственный (рис.6.2). Рис. 6.2 Каждой клетке цикла (вершине ломаной) присвоим определенный знак. Свободной клетке соответствует знак плюс, далее по вершинам ломаной знаки чередуются. В клетках с "+" поставки будем увеличивать, а в клетках с «–» – уменьшать. Найдем величину  , определяющую сколько единиц груза можно перераспределить по найденному циклу. Так как в клетках с «–» поставки должны остаться неотрицательными, величина  определяется из условия:   min xij , где хij рассматриваются для клеток со знаком «–». Шаг 5. Перераспределение поставок по циклу. Начинаем со свободной клетки цикла. Поставка в свободную клетку  . Далее идем по вершинам ломанной. Число  прибавляем к поставкам в клетках с «+» и вычитаем из поставок в клетках с «–». В клетках, не принадлежащих циклу, поставки не изменяются. Клетка, которая раннее была свободной, становится занятой, а минусовая клетка, в которой поставка совпадала с числом  становится свободной. В результате определяется новый опорный план. Следует отметить, что если в минусовых клетках имеется две (или более) одинаковые минимальные поставки, то для сохранения количества базисных переменных освобождают лишь одну клетку, а остальные считают занятыми нулевыми поставками. Шаг 6. Построение нового опорного плана. В результате перехода к новому опорному плану значение целевой функции уменьшается на величину F  ij  , где  – величина передвигаемой по циклу поставки,  ij – оценка свободной клетки, для которой строится цикл. Шаг 7. Полученный опорный план вновь проверяют на оптимальность, повторяя все шаги алгоритма, начиная с 1. Процесс продолжается до получения оптимального решения. 6.5.2. Пример реализации алгоритма метода потенциалов Рассмотрим реализацию алгоритма на примере транспортной задачи из примера. Пусть найдено исходное опорное решение. 1,2 1,8 2 3 1 2 1 1,5 2 2-2=0 5 5-5=0 0,8 2,5 1,2 6 1 2 6-6=0 1 2-2=0 2 2-2=0 6-6=0 2-2=0 f x   1,2  2  1,8  2  1 2  0,8  5  2,5  6  1 2  29 . 1. Поставим в соответствие строкам таблицы (пунктам отправления) – потенциалы ui , а столбцам (пунктам назначения) – потенциалы v j . vj v1  1,2 v2  1,8 v3  1 1,2 1,8 1 ui u1  0 2 3 2 1 2,5 u3  0,7 6 5 5 0,8 u2  0,2 1,5 2 1,2 6 6 1 u4  0,2 2 1 2 4 2 8 7 Пусть u1  0 , тогда, согласно условию ui  cij  v j , находим: v1  u1  c11  0  1,2  1,2 ; v2  u1  c12  0  1,8  1,8 ; v3  u1  c13  0  1  1. Рассматриваем клетку (2;3) v3  u2  c23  1  u2  0,8  u2  0,2. Рассматриваем клетку (3;2) v2  u3  c32  1,8  u3  2,5  u3  0,7. Рассматриваем клетку (4;1) v1  u4  c41  1,2  u4  1  u4  0,2. В итоге каждая строка и каждый столбец имеют свой потенциал. 2. Проверим условия оптимальности для свободных клеток транспортной таблицы: клетка 2;1 u2  c21  v1 0,2  3  1,2  оптимальна ; клетка 2;2 u2  c22  v2 0,2  1  1,8  не оптимальна , 22  1,8  0,2  1  0,6 ; клетка 3;1 u3  c31  v1  0,7  1,5  1,2  не оптимальна, 31  1,2   0,7  1,5  0,4; клетка 3;3 u3  c33  v3  0,7  1,2  1  не оптимальна, 33  1   0,7  1,2  0,5; клетка 4;2 u4  c42  v2 0,2  2  1,8  оптимальна; клетка 4;3 u4  c43  v3 0,2  1  1  оптимальна. Заключаем улучшения в рамки и записываем в каждую неоптимальную свободную клетку. vj v1  1,2 v2  1,8 v3  1 1,2 1,8 1 ui u1  0 2 2 3 1 2 6 5 5 0,8 u2  0,2 0,6 1,5 2,5 u3  0,7 1,2 6 6 0,4 1 u4  0,2 0,5 2 1 2 2 4 8 7 Первоначальный план не является оптимальным. Необходимо произвести улучшение. 3. Наибольшее значение 22  0,6 соответствует свободной клетке (2;2). 4. Начинаем построение цикла со свободной клетки (2;2), помечаем ее знаком "+". Все остальные клетки цикла должны быть занятые. Перечислим клетки цикла: + – + – (2;2) (2;3) (1;3) (1;2) Найдем   min 5,2  2 vj v1  1,2 v2  1,8 v3  1 1,2 1,8 1 ui u1  0 2 2 3 – 1 u2  0,2 2+ 6 5– 5 0,8 + 0,6 u3  0,7 1,5 2,5 1,2 6 6 0,4 1 u4  0,2 0,5 2 1 2 4 2 8 7 5. Выполнив перераспределение поставок по циклу, получим новый план. 1,2 1,8 1 2 3 1 6 3 5 0,8 2 1,5 4 2,5 1,2 6 1 6 2 1 2 2 4 8 7 Для полученного плана f x   1,2  2  1 4  1 2  0,8  3  2,5  6  1 2  27,8  29 . 3 Осуществляем контроль: количество занятых клеток шесть,  xij  ai , i  1,4, j 1 4  xij  b j , j  1,3 . i 1 Производим проверку полученного плана на оптимальность, предположив, что u1  0 . vj v1  1,2 v2  1,2 v3  1 1,2 1,8 1 ui u1  0 u2  0,2 u3  1,3 2 3 1 + 2,5 1 u4  0,2 5 + 6 1,1 2 1 2 4 3– 1,2 6– 1 6 0,8 2 1,5 4 2 8 7 План не является оптимальным, поэтому снова производим улучшение. Выбираем максимальное улучшение 33  1,1 , которое соответствует клетке (3;3). Начинаем построение цикла со свободной клетки (3;3), помечаем ее знаком «+». Все остальные клетки цикла должны быть занятые. Перечислим клетки цикла: + – + – (3;3) (2;3) (2;2) (3;2) Найдем   min 3,6   3 . 6. Перераспределение поставок по циклу дает новый план. 1,2 1,8 1 2 3 1 6 3 5 0,8 2 1,5 4 2,5 1,2 6 1 6 2 1 2 2 4 8 7 Для полученного плана f x   1,2  2  1 4  1 5  2,5  3  1,2  3  1 2  24,5  27,8 . 3 Осуществляем контроль: количество занятых клеток шесть,  xij  ai , i  1,4, j 1 4  xij  b j , j  1,3 . i 1 Проверяем на оптимальность, предположив что u1  0 . vj v1  1,2 v2  2,3 v3  1 1,2 1,8 1 ui u1  0 2 + 4– 6 0,5 u2  1,3 u3  0,2 3 1 0,8 5 5 1,5 2,5 1,2 3 1 u4  0,2 – 3+ 2 1 2 2 0,1 4 6 8 7 План не является оптимальным, поэтому снова производим улучшение. Выбираем максимальное улучшение 12  0,5 , которое соответствует клетке (1,2). Начинаем построение цикла со свободной клетки (1,2), помечаем ее знаком "+". Все остальные клетки цикла должны быть занятые. Перечислим клетки цикла: + – + – (1;2) (1;3) (3;3) (3;2) Найдем   min 3,4  3 . 7. Перераспределение поставок по циклу дает новый план. 1,2 1,8 2 3 1 3 1 1 0,8 5 1,5 2,5 5 1,2 6 1 2 6 1 2 2 4 6 8 7 Для полученного плана f x   1,2  2  1,8  3  1  1  1  5  1,2  6  1  2  23  24,5 . 3 Осуществляем контроль: количество занятых клеток шесть,  xij  ai , i  1,4, j 1 4  xij  b j , j  1,3 . i 1 Производим проверку на оптимальность, предположив, что u1  0 vj v1  1,2 v2  1,8 v3  1 1,2 1,8 1 ui u1  0 2 3 3 1 u2  0,8 1 0,8 5 5 1,5 2,5 1,2 u3  0,2 6 1 u4  0,2 2 6 1 2 4 6 2 8 7 Для всех свободных клеток выполнено условие оптимальности. Получено оптимальное решение.  2 3 1   0 5 0   Ответ. Х  , f X    23 .  0 0 6  2 0 0   6.6. Алгоритм решения транспортной задачи 1. Составить методом северо-западного угла или методом минимальной стоимости план задачи. 1.1. Определить потенциалы строк и столбцов ui , v j по занятым клеткам. 1.2. Задать ui  0 для произвольной строки (лучше там, где больше занятых клеток). 1.3. Вычислить потенциалы по формуле v j  ui  cij (стоимость товара потребителя равна стоимость товара поставщика «+» стоимость перевозки). 2. Оценка оптимальности плана, проводится по свободным клеткам. Проверяется условие ui  cij  v j . 2.1. Если оно выполняется для всех свободных клеток, оптимальное решение задачи получено. Переходим к шагу 5. 2.2. Если существует свободная клетка, для которой выполняется условие ui  cij  v j , то план может быть улучшен. В клетке выписать насколько может быть улучшен план и перейти к шагу 4. 3. Улучшение плана. 3.1. Выбрать клетку с максимальным улучшением. 3.2. Найти цикл пересчѐта (ломаную пересчѐта). 3.3. Отметить свободную клетку знаком «+», далее при движении по вершинам ломаной чередуем знаки «+» и «–». 3.4. Вычислить коэффициент пересчѐта по клеткам со знаком «–»:   minxij . "" 3.5. Произвести пересчѐт: для клеток со знаком «+» ~ x  x   , для клеток со ij "" ij знаком «–» ~ xij  xij    0 , остальные поставки без изменения. При этом одна из клеток окажется пустой, еѐ исключить из плана. Если таких клеток несколько, то исключить только одну любую, оставив остальные с фиктивной нулевой поставкой. 3.6. Перейти к шагу 2. 4. По занятым клеткам вычислить значение целевой функции.