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

Лекция 1 Транспортная задача линейного программирования Универсальным методом для решения задач линейного программирования является симплексный метод и его модификации (метод искусственного базиса и двойственный симплекс-метод). Однако существуют такие классы задач, которые могут быть решены более простыми методами. К числу таких задач следует отнести транспортные, получившие свое название в связи с тем, что методы их решения были разработаны применительно к организации перевозок грузов. 1.1. Постановка транспортной задачи и ее математическая модель. Сущность транспортной задачи состоит в следующем. Имеются m пунктов производства однородной продукции А1, А2,…, Am. Объем производства пункта Ai равен ai единиц продукта. Произведенный продукт потребляется в n пунктах потребления B1, B2,…, Bn. Объем потребления пункта Bj равен bj единиц продукта. Требуется организовать снабжение пунктов Bj (j = 1, 2,…, n) из пунктов Ai (i = 1, 2,…, m) так, чтобы суммарные транспортные издержки были минимальными. Предполагается, что перевозки могут быть организованы из любого пункта производства в любой пункт потребления. Рассмотрим идеальный случай, когда суммарный объем производства равен суммарному объему потребностей, т.е. m n a  b i 1 i j 1 j (1.1) Транспортная задача, в которой выполняется условие (1.1), называется задачей закрытого типа. Она характеризуется тем, что весь произведенный продукт потребляется, и все потребности удовлетворяются, т.е. производство и потребление сбалансированы. Формальное описание задачи требует следующих обозначений. Пусть xij – количество единиц продукта, перевозимое из i-го пункта производства в j – й пункт потребления. Известна стоимость сij перевозки единицы груза из Аi в Bj . Так как от i-го поставщика к j – му потребителю запланировано к перевозке xij единиц груза, то стоимость перевозки по данному маршруту составит сijxij. Стоимость же суммарных транспортных расходов будет получена при суммировании данного выражения (сijxij) по всем поставщикам m и всем потребителям, т.е. она выразится двойной суммой n c i 1 j 1 ij x ij , которая в соответствии с постановкой задачи должна быть обращена в минимум, т.е. функция цели транспортной задачи имеет вид: Z  m n  c i 1 j 1 ij xij  min (1.2) Систему ограничений получаем из следующих условий задачи: а) Из пункта производства Ai (i = 1, 2,…, m) вывозится во все n пунктов потребления ai единиц продукта – величина, равная объему производства пункта Ai, т.е. n x j 1 ij _____  ai ; i  1, m (1.3) b) В пункт потребления Bj (j = 1, 2,…, n) поставляется из всех m пунктов производства bj единиц продукта – величина, равная объему потребления в пункте Bj, т.е. m  xij  b j ; ____ j  1, n (1.4) i 1 c) Величина перевозимого груза не может быть отрицательной, или, иначе, перевозки осуществляются только из пунктов производства в пункты потребления, обратных перевозок нет, т.е. _____ xij  0; i  1, m ; ____ j  1, n (1.5) Модель (1.2) – (1.5) представляет собой математическую модель транспортной задачи линейного программирования закрытого типа. Следует отметить, что большинство практических задач таково, что условие (1.1) не выполняется, т.е. либо суммарный объем производства превышает суммарный объем потребностей (перепроизводство продукции) m n a  b , i 1 i j 1 (1.6) j либо суммарный объем потребностей превышает суммарный объем производства (недопроизводство продукции – спрос превышает предложение) m n a  b , i 1 i j 1 (1.7) j Транспортные задачи, в которых выполнены условия (1.6) или (1.7) называются задачами открытого типа (в них производство и потребление не сбалансированы). Для этих случаев также может быть поставлена задача о нахождении плана перевозок с минимальными транспортными расходами. В случае выполнения условия (1.6) (когда суммарный объем запасов превышает суммарный объем потребностей, т.е. часть продукции остается невостребованной) вводят фиктивный (n + 1) – й пункт потребления Bn+1 с m n i 1 j 1 потребностью bn 1   ai   b j и полагают стоимости перевозок грузов в этот пункт равными нулю: ci,n+1 = 0 (i = 1, 2,…, m). Полученная задача является уже задачей закрытого типа, т.к. для нее выполняется равенство n 1 m  a   b . Аналогично, при выполнении условия (1.7) (когда суммарный i 1 i j 1 j объем потребностей превышает суммарный объем запасов, т.е. часть потребностей остается неудовлетворенной) вводят фиктивный (m + 1) – й пункт производства Am+1 с объемом a m 1  n m b  a j 1 j i 1 i и со стоимостями перевозок продукции cm+1,j = 0 (j = 1, 2,…, n). Полученная задача также является транспортной задачей закрытого типа, т.к. для нее выполнено m 1 условие: n a  b i i 1 j 1 j . Итак, любую транспортную задачу открытого типа можно свести к задаче закрытого типа. В дальнейшем (не нарушая общности) мы будем рассматривать транспортные задачи, в которых производство и потребление сбалансированы, т.е. суммарный объем производства (запасов) равен суммарному объему потребностей. После постановки задачи и записи математической модели, встает вопрос о существовании ее решения. Ответ на этот вопрос дает следующая теорема. 1.2. Теорема о разрешимости транспортной задачи. Теорема Любая транспортная задача закрытого типа имеет решение. Доказательство. Транспортная задача (1.2) – (1.5) является задачей линейного программирования. Известно, что существует всего два случая, когда задача линейного программирования не имеет решения: 1. система ограничений задачи противоречива, т.е. область допустимых решений пуста; 2. функция цели задачи не ограничена. Поэтому, теорема будет доказана, если мы установим, что область допустимых решений транспортной задачи не пуста и функция цели Z ограничена. Докажем вначале, что область допустимых решений транспортной задачи, т.е. область, заданная условиями (1.3) – (1.5), не пуста, т.е. существует хотя бы один план перевозок {xij}, удовлетворяющий ограничениям задачи. Согласно условию теоремы, сумма запасов совпадает с суммой потребностей. Обозначим эту величину через P, т.е. m n a  b i i 1 j 1 j P0 (1.8) Утверждается, что величины xij = aibj / P (1.9) образуют план транспортной задачи, т.е. удовлетворяют ограничениям (1.3) – (1.5). Используя представление (1.9) проверим выполнение условий (1.3). В процессе преобразований воспользуемся условием (6.8) и тем, что за знак суммы можно выносить величины, не зависящие от индекса суммирования. n x j 1 n  ij ai b j ai n a   b j  i P  ai , P P j 1 P j 1 т.е. переменные xij удовлетворяют ограничениям (1.3). Проверим выполнение ограничений (1.4): m m ai b j i 1 P  xij   i 1 т.е. переменные  bj P удовлетворяют xij m bj i 1 P  ai  P  bj , ограничениям (1.4). Учитывая положительность величин ai, bj и P, легко видеть, что xij, вычисляемые по формуле (1.9) удовлетворяют ограничениям (1.5). Итак, существует план перевозок {xij}, удовлетворяющий ограничениям задачи, т.е. область допустимых решений не пуста. Докажем теперь, что функция цели транспортной задачи ограничена на множестве планов. Возьмем c = min{cij}; c = max{cij}. Выбирая план (1.9) и используя ограничения (1.3) – (1.4),получим: m  n  Z    cij xij  c   xij   c  ai  cP i 1 j 1 i 1  j 1 i 1  m n m m  n  Z    cij xij  c   xij   c ai  cP i 1 j 1 i 1  j 1 i 1  m n m Объединив два неравенства в одно двойное, получим: cP  Z  cP, т.е. функция цели транспортной задачи ограничена на множестве планов. Теорема доказана полностью. Учитывая, что открытую транспортную задачу всегда можно свести к закрытой, на основании доказанной теоремы делаем вывод: любая транспортная задача имеет решение. 1.3. Построение первоначального опорного плана транспортной задачи. Как и при решении задачи линейного программирования симплексным методом, определение оптимального плана транспортной задачи начинают с нахождения какого либо ее опорного плана. Рассмотрим систему ограничений (1.3) – (1.4), содержащую mn неизвестных и m+n уравнений, связанных соотношением (1.1). Если сложить отдельно все m уравнений системы (1.3), затем сложить отдельно все n уравнений системы (1.4), то получим два одинаковых уравнения. Наличие в системе ограничений двух одинаковых уравнений свидетельствует о ее линейной зависимости. Если одно из этих уравнений исключить, то система ограничений будет содержать m + n – 1 уравнений. Таким образом, невырожденный опорный план транспортной задачи содержит m + n – 1 положительных компонент или перевозок. Все условия транспортной задачи сводятся в табличную форму, называемую матрицей транспортной задачи (табл. 1.1). Таблица 1.1 Потребители В1 В2 … Вn-1 Вn Запасы Поставщики А1 с12 c11 x11 x12 … … c1,n-1 x1,n-1 c1n x1n a1 А2 c21 x21 … … … Аm Потребности В матрице cm1 c22 x22 … … cm2 … … … … … c2,n-1 x2,n-1 … … cm,n-1 c2n … … … cmn xm1 xm2 … xm,n-1 xmn b1 b2 … bn-1 bn экономико-математической a2 x2n am ai=bj задачи по строкам записываются ограничения по наличию продукции у поставщиков, а по столбцам – ограничения по спросу потребителей. В правом верхнем углу клеток (i, j) помещаются величины cij – стоимости перевозок единицы продукта от i-го поставщика к j – му потребителю. Если каким – либо способом получен невырожденный опорный план транспортной задачи, то в матрице {xij} (i = 1, 2,…, m; j = 1, 2,…, n) значений его компонент положительными являются только m + n – 1, а остальные равны нулю. Клетки, в которых находятся отличные от нуля перевозки, называются занятыми, остальные незанятыми (или пустыми). Занятые клетки соответствуют базисным неизвестным, и для невырожденного плана их количество равно m + n – 1. Существует несколько простых схем построения первоначального опорного плана транспортной задачи. Пример 1. Рассмотрим следующую транспортную задачу. Имеются три животноводческих комплекса. На первом из них хранится 400т, на втором – 250т и на третьем 350т органических удобрений. Удобрения необходимо развезти по пяти полям. Потребность в органических удобрениях для первого поля 200т, для второго – 170т, для третьего – 230т, для четвертого – 225т и для пятого – 175т. Стоимость перевозки 1 тонны органических удобрений от животноводческих комплексов к полям заданы таблицей. Таблица 1.2. Комплекс Поля ы 1 2 3 1 8 4 15 2 20 14 22 3 7 12 11 4 11 15 12 5 18 17 19 Требуется определить такой план перевозок, который бы обеспечил минимальные транспортные расходы. На примере данной задачи рассмотрим построение первоначального опорного плана несколькими способами. Так как сумма запасов равна сумме 5  3   a  потребностей   i  b j  1000m . j 1  i 1  Метод северо-западного угла. Этот метод получил свое название потому, что распределение поставок начинается с клетки, расположенной в левом верхнем углу матрицы, что соответствует северо-западу на географической карте. Таблица 1.3. Потребители Поставщики А1 А2 А3 Потребности В1 В2 8 200 20 170 4 – В3 14 – 15 7 30 11 В5 11 – 12 200 22 В4 18 – 15 17 – 50 12 19 – – – 175 175 200 170 230 225 175 Запасы 400 250 350 1000 Приступаем к заполнению таблицы с клетки (1, 1), которая соответствует первому поставщику и первому потребителю. Начинаем удовлетворение потребностей потребителя В1 за счет запасов поставщика А1. Для этого сравниваем а1 = 400 с b1 = 200; a1 > b1. Меньший из объемов, т.е. 200т записываем в клетку (1, 1). Наименьший из объемов запасов и потребностей берется потому, что в противном случае либо не хватит запасов поставщика, либо потребитель получит продукцию в объеме, превышающем его потребности. В нашем случае, помещая в клетку (1, 1) 200т груза видим, что потребности первого потребителя удовлетворены полностью, поэтому остальные клетки первого столбца прочеркиваем (т.е. первый потребитель не будет получать груз ни от второго, ни от третьего поставщика в силу того, что его потребности удовлетворены за счет первого поставщика). Из оставшейся таблицы (после исключения первого столбца) вновь выбираем северо-западный угол, т.е. клетку (1, 2), ей соответствует первый поставщик и второй потребитель. Начинаем удовлетворение потребностей второго потребителя за счет оставшихся запасов поставщика А1. Для этого сравниваем b2 = 170т с остатком запасов поставщика А1: 400 – 200 = 200т. Меньший из объемов, т.е. 170т записываем в клетку (1, 2) и закрываем (прочеркиваем) второй столбец, т.к. потребности второго потребителя удовлетворены полностью. В оставшейся таблице (после исключения первых двух столбцов) вновь выбираем северо-западный угол, т.е. клетку (1,3), ей соответствует третий потребитель и первый поставщик. У первого поставщика осталось 400 – 200 – 170 = 30т груза, потребности же третьего потребителя равны 230т. Меньший из объемов, т.е. 30т записываем в клетку (1, 3) и закрываем (прочеркиваем) первую строку, т.к. запасы первого поставщика израсходованы полностью. В оставшейся таблице северо-западному углу соответствует клетка (2, 3). Начинаем удовлетворение потребностей третьего потребителя за счет В3 за счет запасов поставщика А2. Для этого сравниваем а2 = 250т с величиной неудовлетворенного спроса потребителя В3: 230 – 30 = 200т. Меньший из объемов, т.е. 200т записываем в клетку (2, 3) и закрываем третий столбец, т.к. потребности В3 удовлетворены полностью. В оставшейся таблице северозападному углу соответствует клетка (2, 4). У второго поставщика осталось 250 – 200 = 50т груза, потребности же четвертого потребителя равны 225т. Меньший из объемов, т.е. 50т записываем в клетку (2, 4) и закрываем (прочеркиваем) вторую строку, т.к. запасы второго поставщика полностью израсходованы. Далее заполняем клетку (3, 4), соответствующую третьему поставщику и четвертому потребителю. Для этого сравниваем а 3 = 350т с величиной неудовлетворенного спроса потребителя В4: 225 – 50 = 175т. В последнюю незаполненную клетку (3, 5) помещаем 175т груза: в последней клетке ввиду сбалансированности суммарными объемами запасов и потребностей, величина оставшихся запасов всегда совпадает с величиной неудовлетворенного спроса. На этом построение первоначального опорного плана заканчивается. При построении первоначального опорного плана методом северозападного угла не учитывается стоимость перевозки единицы груза, поэтому построенный план далек от оптимального, получение которого связано с большим объемом вычислительных работ. Построенный план является опорным и невырожденным (количество занятых клеток равно m + n – 1 = 3 + 5 – 1 = 7). Определим величину суммарных транспортных расходов как сумму произведений объемов перевозок на соответствующие стоимости: Z = 2008 + 17020 + 307 + 20012 + 5015 + 17512 + 17519 = 13785 руб. Метод минимальной стоимости. Суть этого метода состоит в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают максимально возможное количество груза (т.е. наименьшее из чисел ai и bj). Затем закрывают либо строку (если запасы соответствующего поставщика полностью израсходованы), либо столбец (если потребности соответствующего потребителя полностью удовлетворены). Из оставшейся части таблицы стоимостей вновь выбирают наименьшую стоимость и процесс распределения запасов продолжают до тех пор, пока все запасы не будут распределены, а потребности – удовлетворены. Составим с помощью этого метода опорный план уже рассмотренной задачи. Таблица 1.4 Потребители В1 Поставщики 8 А1 – 200 15 А3 Потребности в В3 20 – 4 А2 Выбираем В2 7 230 14 50 22 В4 11 170 12 – В5 18 – 15 – 11 17 – 12 120 – 55 175 200 170 230 225 175 наименьшую 400 250 19 – таблице Запасы стоимость 350 1000 (это стоимость, помещенная в клетке (2, 1)). Так как а2 = 250, b1 = 200, то помещаем в эту клетку 200т груза и исключаем из рассмотрения первый столбец. В оставшейся таблице стоимостей наименьшей является стоимость, расположенная в клетке (1, 3). Так как а1 = 400, b3 = 230, то меньший из объемов, т.е. 230 записываем в клетку (1, 3) и закрываем третий столбец, т.к. потребности потребителя В3 полностью удовлетворены. В оставшейся таблице наименьшая стоимость в клетке (1, 4) соответствует первому поставщику и четвертому потребителю. Остаток запасов первого поставщика 400 – 230 = 170т, объем потребностей четвертого потребителя – 225т. Меньший из объемов, т.е. 170т записываем в клетку (1, 4) и закрываем первую строку, т.к. запасы первого поставщика полностью израсходованы. Далее в клетку с наименьшей стоимостью (клетку (3, 4)) помещаем 55т (величину неудовлетворенного спроса потребителя В4) и закрываем четвертый столбец. Далее в клетку (2, 2) помещаем 50т и закрываем вторую строку, в клетку (3, 5) помещаем 175т и, наконец, в клетку (3, 2) – 120т. В результате получен план, помещенный в таблице 5.4. План является опорным и невырожденным (количество занятых клеток равно m + n – 1 = 3 + 5 – 1 = 7). Величина суммарных транспортных расходов Z = 2307 + 17011 + 2004 + 5014 + 12022 + 5512 + 17519 = 11605руб. Как видим, величина расходов существенно меньше, чем в плане, построенном по методу северо – западного угла. Метод двойного предпочтения. В каждой строке знаком «v» отмечаем клетку с наименьшей стоимостью. Затем то же проделываем в каждом столбце. В результате некоторые клетки имеют отметку «vv» (в них находится минимальная стоимость, как по строке, так и по столбцу). В эти клетки помещаем максимально возможные объемы перевозок, каждый раз исключая из рассмотрения соответствующие строки или столбцы. Затем заполняем клетки, отмеченные знаком «v». В оставшейся части таблицы перевозки распределяют по минимальной стоимости. Применим метод двойного предпочтения к рассмотренной задаче. Таблица 1.5 Первоначальный опорный план транспортной В4 В5 задачи, построенный методом двойного предпочтения. Потребители Поставщики А1 А2 А3 Потребности В1 В2 8 20 – – vv4 v14 200 15 В3 vv.7 230 50 22 V11 170 12 – 15 – V11 18 – V17 – 12 19 – 120 – 55 175 200 170 230 225 175 Запасы 400 250 350 1000 Вначале заполняем клетки (1, 3) и (2, 1) затем клетки (1, 4) и (2, 2). В оставшейся части таблицы последовательно заполняем клетки по минимальной стоимости: (3, 4),(3, 5) и (3, 2). Как видим, найденный план совпадает с планом, построенным по методу минимальной стоимости. Рассмотренные нами методы построения первоначального опорного плана представляют первый этап решения транспортной задачи. Самым распространенным методом получения оптимального плана является метод потенциалов (модифицированный распределительный метод). 1.4. Метод потенциалов. Применение метода потенциалов основывается на следующей теореме. Теорема. (Основная теорема метода потенциалов). Если план X={xij} транспортной задачи (1.2) – (1.5) является оптимальным, то ему соответствует система из m + n действительных чисел ui и vj, удовлетворяющих условиям: ui + vj = cij для всех xij > 0 (1.10) ui + vj  cij для всех xij = 0 (1.11) Числа ui и vj называются потенциалами поставщиков и потребителей соответственно. Доказательство: для транспортной задачи (1.2) – (1.5) построим двойственную, причем каждому ограничению (1.3) поставим в соответствие двойственную переменную ui (i = 1, 2,…, m), а каждому ограничению (1.4) – двойственную переменную vj (j = 1, 2,…, n). Тогда двойственная задача примет вид: m n i 1 j 1 F   ai ui   b j v j  max ui  v j  cij _____ ____ (i  1, m ; j  1, n ) По условию теоремы X={xij} – оптимальный план транспортной задачи, тогда (в соответствии с первой основной теоремой двойственности) двойственная задача также имеет оптимальное решение, причем min Z = max F. На основании второй основной теоремы двойственности получаем, что ограничения двойственной задачи, соответствующие положительным компонентам оптимального плана исходной задачи, удовлетворяются как строгие равенства, а соответствующие нулевым компонентам, – как неравенства, т.е. ui + vj = cij для всех xij > 0 ui + vj  cij для всех xij = 0 Теорема доказана. Итак, для того, чтобы план транспортной задачи был оптимальным, требуется выполнение условий: 1) для каждой занятой клетки сумма потенциалов должна быть равна стоимости перевозки единицы груза, стоящей в этой клетке: ui + vj = cij; 2) для каждой пустой клетки сумма потенциалов не должна превышать стоимость перевозки единицы груза, стоящей в этой клетке: ui + vj  cij. Если хотя бы одна незанятая клетка не удовлетворяет условию (1.11), то опорный план не является оптимальным и его можно улучшить, помещая в клетку, для которой нарушено условие оптимальности, некоторое количество единиц груза. Рассмотрим алгоритм метода потенциалов и проиллюстрируем его применение на опорном плане, полученном в таблице 6.5. 1. Построение системы потенциалов. Для построения системы потенциалов используем условие (1.10). Значения потенциалов находятся только для невырожденного опорного плана. Этот план содержит m + n – 1 занятых клеток. Количество же неизвестных (ui и vj), подлежащих вычислению равно m + n. Уравнений (1.10) на одно меньше, чем неизвестных, поэтому система является неопределенной (имеет бесконечное множество решений). Одному неизвестному (как правило, тому, для которого в соответствующей ему строке или столбце находится наибольшее количество занятых клеток) придают нулевое значение. После этого остальные потенциалы определяются однозначно. Действительно, величины сij известны. Если для занятой клетки известен один из потенциалов, то в соответствии с (1.10) имеем тривиальную задачу: известна сумма двух слагаемых и одно из слагаемых; требуется определить другое слагаемое. Пусть известен потенциал ui, тогда из равенства (1.10) имеем: vj = cij – ui. Если же известен потенциал vj, то получим: ui = cij – vj. В таблице 1.5 построен невырожденный план (количество занятых клеток равно m + n – 1), построим для него систему потенциалов, отразив их в таблице 1.6. Таблица 1.6 Потребители В1 Поставщики А1 u1= – 1 А2 u2= – 8 А3 u3= 0 Потребности v1=12 В2 В3 В4 В5 v2=22 v3=8 v4=12 v5=19 11 18 8 20 1 - 3 + 4 –200 15 7 230 14 + 50 – 170 12 – 22 15 – 11 – 17 – 12 19 – – 120 – + 55 175 200 170 230 225 175 Запасы 400 250 350 1000 В третьей строке содержится наибольшее количество занятых клеток. Полагаем u3 = 0. В третьей строке три занятых клетки, которые связывают потенциал u3 с потенциалами v2, v4, v5. Определим эти потенциалы: v2= c32 – u3 = 22 – 0 = 22; v4 = c34 – u3 = 12 – 0 = 12; v5 = c35 – u3 = 19 – 0 = 19. С помощью u3 найти еще какой – либо неизвестный потенциал невозможно. Теперь поочередно просматриваем второй, четвертый и пятый столбцы, для которых потенциалы уже определены. Во втором столбце две занятые клетки, для одной из которых [(2, 2)] не найден потенциал: u2 = c22 – v2 = 14 – 22= – 8. Переходим к четвертому столбцу. В этом столбце имеется занятая клетка (1, 4), связывающая v4 с неизвестным потенциалом u1. Определим его: u1 = c14 – v4 = 11 – 12 = – 1. Потенциал u2 занятой клеткой (2,1) связан с неизвестным потенциалом v1. Находим его: v1 = c21 – u2 = 4 – (– 8) = 12. Потенциал u1 занятой клеткой (1, 3) связан с неизвестным потенциалом v3. Находим его: v3 = c13 – u1 = 7 – (– 1) = 8. Система потенциалов построена. 2. Проверка выполнения условия оптимальности для незанятых клеток. Просматриваем строки и каждой незанятой клетки проверяем выполнение условия (6.11). Если эти условия выполняются для всех незанятых клеток, то план является оптимальным. Если же для некоторой клетки это условие не выполняется, то в левый нижний угол этой клетки записываем разность ui + vj – cij. В нашей задаче для незанятых клеток получаем: по первой строке, для клетки (1.1): 12 – 1 > 8 или (11 – 8 = 3) – условие оптимальности для клетки (1, 1) нарушено; разность, равную 3 записываем в левый нижний угол этой клетки. Для клетки (1, 2) имеем: 22 – 1 > 20 или 21 – 20 = 1 – условие оптимальности также нарушено; разность, равную 1 записываем в эту клетку. Итак, имеются две клетки, в которых нарушено условие оптимальности. Загрузке подлежит в первую очередь клетка, которой соответствует максимальное нарушение. В нашем случае это клетка (1, 1), ее необходимо сделать занятой. 3. Построение цикла и определение величины перераспределения груза. Циклом называется замкнутая ломаная линия, вершины которой лежат в занятых клетках, а переход от одной клетки к другой осуществляется под прямым углом. Построенный опорный план обладает свойством ацикличности, т.е. в таблице нельзя построить цикл. Клетку, которую надо загрузить, помечаем знаком «+». Это означает, что в нее будет помещено некоторое количество груза, и она присоединяется к занятым клеткам. В таблице стало m + n занятых клеток, поэтому появляется цикл, причем он единственный. Строим цикл, начиная от клетки, помеченной знаком «+», поочередно проставляя знаки «–» и «+». Теперь необходимо определить сколько единиц груза  необходимо перераспределить по циклу. В клетки, помеченные знаком «+» будет прибавлена величина , а из клеток, помеченных знаком « – » будет вычтена величина . Величина  находится исходя из требования неотрицательности величин xij. Очевидно, что в результате перераспределения по циклу любой величины , клетки, помеченные знаком «+» не будут содержать отрицательных значений перевозок. Из клеток же, помеченных знаком «–» можно вычитать величину , не превосходящую минимального значения перевозки. Итак,  = min {xij¯}, где xij¯ – перевозки, стоящие в вершинах цикла, отмеченных знаком «–».  Если соответствуют несколько минимальных перевозок, то при вычитании оставляем в соответствующих клетках нулевые перевозки в таком количестве, чтобы во вновь полученном опорном плане было m + n – 1 занятых клеток. В рассматриваемом примере знаком «+» отмечаем клетку (1, 1) и строим цикл, который проходит по клеткам: (1,1)  (1, 4)  (3, 4)  (3, 2)  (2, 2)  (2, 1)  (1, 1).  = min{170, 120, 200} = 120. Поэтому по циклу будет перераспределено 120т груза, т.е. в клетки (1, 1), (3, 4) и (2, 2) будет прибавлено по 120т, а из клеток (1, 4), (3, 2) и (2, 1) – вычтено по 120т. В результате получим новый план перевозок (таблица 6.7), для которого вновь строим систему потенциалов и повторяем процесс до тех пор, пока для всех клеток не будут выполнены условия (6.10) – (6.11). Полагая в таблице 1.7 u1 = 0, найдем остальные потенциалы: v1 = 8; v3 = 7; v4 = 11. Из клетки (2, 1) находим u2 = 4 – 8 = – 4. Из клетки (3, 4) находим u3 = 12 – 11 = 1. Зная u2 из клетки (2, 2) находим v2 = 14 – (- 4) = 18; зная u3 из клетки (3, 5) находим v5 = 19 – 1 = 18. Построенная система потенциалов позволяет сделать вывод: план, приведенный в таблице 6.7 является оптимальным. Таблица 1.7 Потребители В1 Поставщики v1=8 В2 В3 В4 В5 v2=18 v3=7 V4=11 v5=18 Запасы А1 u1= 0 А2 u2= – 4 А3 u3= 1 Потребности 8 120 20 – 4 80 7 230 14 170 15 11 50 12 – 22 – 15 – 11 18 17 – 12 400 250 19 – – – 175 175 200 170 230 225 175 350 1000 Zmin = 1208 + 2307 + 5011 + 804 + 17014 + 17512 + 17519 = 11245руб. Согласно полученному решению, с первого животноводческого комплекса, где хранится 400т органических удобрений, 120т будет вывезено на первое поле, 230т – на третье и 50т – на четвертое поле; со второго комплекса 80т будет вывезено на первое поле и 170т на второе; с третьего комплекса по175т будет вывезено на третье и четвертое поля. Открытая модель транспортной задачи, как было указано выше, введением фиктивного поставщика или потребителя сводится к закрытой. В дальнейшем построенная задача решается аналогично транспортной задаче закрытого типа. Однако следует иметь в виду, что при построении первоначального опорного плана методом минимальной стоимости или методом двойного предпочтения необходимо наименьшую стоимость выбирать только среди стоимостей реальных поставщиков и потребителей, а распределять запасы фиктивного поставщика или удовлетворять потребности фиктивного потребителя следует в последнюю очередь. Пример 2. В хозяйстве имеются 4 скирды соломы. В первой из них хранится 250т, во второй – 350т, в третьей – 450т и в четвертой – 550т соломы. Солома выделена для подстилки крупному рогатому скоту, содержащемуся на пяти фермах. Потребность в соломе для первой фермы равна 100т, для второй – 200т, для третьей – 300т, для четвертой – 400т и для пятой – 500т. Известны расстояния (в км) между пунктами хранения соломы и фермами. Таблица 1.8 Расстояния между пунктами хранения соломы и фермами, км Скирда 1 2 Ферма 3 1 5 4 7 9 3 2 4 8 2 10 4 3 3 1 7 6 2 4 7 9 5 6 4 4 5 Требуется определить такой план перевозок соломы на фермы, который бы обеспечил минимальный объем грузоперевозок в тоннокилометрах. Решение: В данной задаче наличие соломы на 100т больше, чем требуется ее для ферм. В этом случае вводится фиктивный потребитель В6 с потребностью 100т. При решении задачи необходимо не только распределить солому, но и определить в какой из скирд целесообразно оставить ее излишки. Первоначальный опорный план построим методом минимальной стоимости. При этом удовлетворять потребности фиктивного потребителя будем в последнюю очередь (табл.1.9). Таблица 1.9 Потребители Поставщики А1 u1= – 3 А2 u2= – 3 А3 u3= – 4 В1 v1=7 В2 v2=5 В3 v3=5 В4 v4=6 В5 В6 v v5=6 6=0 Запасы 5 4 7 9 3 – – – – 250 – 4 8 2 10 4 50 – 300 – – – 3 1 7 6 2 + 0 200 – – – – 250 250 350 450 А4 u4= 0 Потребности 7 9 5 6 – 50 – – 400 200 300 100 400 4 2 + 100 500 100 550 1600 Порядок заполнения матрицы транспортной задачи следующий: 1. в клетку (3, 2) помещаем 200т и закрываем второй столбец; 2. в клетку (2, 3) помещаем 300т и закрываем третий столбец; 3. в клетку (3, 5) помещаем 250т и закрываем третью строку; 4. в клетку (1, 5) помещаем 250т, закрываем первую строку и пятый столбец; 5. в клетку (2, 1) помещаем 50т и закрываем вторую строку; 6. в клетку (4, 4) помещаем 400т и закрываем четвертый столбец; 7. в клетку (4, 1) помещаем 50т и закрываем первый столбец; 8. в последнюю очередь в клетку (4 ,6) помещаем 100т. Теперь необходимо построить систему потенциалов. Значения потенциалов находятся только для невырожденного опорного плана, содержащего m + n – 1 занятых клеток. В нашем случае m + n – 1 = 4 + 6 – 1 = 9. Опорный план, построенный в таблице 1.9 – вырожденный, так как не хватает одной занятой клетки. Для устранения вырожденности следует дополнить количество занятых клеток до m + n – 1, вводя нулевую перевозку. Клетки, в которые введены нулевые перевозки, называются фиктивно занятыми. В общем случае можно считать фиктивно занятой любую свободную клетку (вводя в нее нулевую перевозку и присоединяя тем самым ее к занятым клеткам) с тем условием, чтобы полученный опорный невырожденный план обладал свойством ацикличности. Можно заранее не выбирать фиктивно занятую клетку, а определить ее в процессе вычисления потенциалов. Покажем эту процедуру на нашем примере. Наибольшее количество занятых клеток содержит четвертая строка. Полагаем u4 = 0. Тогда v1 = 7,v4 = 6,v6 = 0. Зная v1 находим u2 = 4 – 7 = – 3; зная u2 находим v3 = 2 – (–3) = 5. Построение системы потенциалов прервалось; потенциалы u1, u3, v2, v5 остались неопределенными. Это произошло потому, что опорный план вырожденный (отсутствует одна занятая клетка). Чтобы определить неизвестные потенциалы необходимо сделать фиктивно занятой одну из незанятых клеток первой или третьей строки (неизвестны потенциалы u1, u3), второго или пятого столбца (неизвестны потенциалы v2, v5). Фиктивно занятой следует брать клетку, для которой найден только один потенциал. Задача решается на минимум, поэтому целесообразно сделать фиктивно занятой клетку, в которой стоит наименьшая стоимость. В нашем случае выбираем клетку (3, 1), которой соответствует с31 = 3. Записываем в эту клетку нуль и считаем ее занятой. Тогда u3= 3 – 7 = – 4. Зная u3 находим v2 = 1 – ( – 4) = 5 и v5 = 2 – ( – 4) = 6. Зная v5 определяем u1 = 3 – 6 = – 3. Система потенциалов построена. Проверяя выполнение условий оптимальности для незанятых клеток, обнаруживаем, что для клетки (4, 5) оно не выполнено: u4 + v5 = 0 + 6 > 4. Отмечаем эту клетку знаком «+» и строим цикл, который пройдет по клеткам: (4, 5)  (3, 5)  (3, 1)  (4, 1)  (4, 5). Проставив в вершинах цикла поочередно знаки «–» и «+» находим, что в клетках, помеченных знаком «–» наименьшее значение перевозки равно 50. Именно эту величину мы и перераспределяем по циклу. В результате получим новый план, в котором уже нет фиктивно занятой клетки (она попала в цикл со знаком «+» и в нее прибавлено 50 единиц) Таблица 1.10 Потребители В1 v1=5 Поставщики А1 u1= – 1 А2 u2= – 1 А3 u3= – 2 В2 v2=3 В3 v3=3 В4 v4=6 В5 v5=4 В6 5 4 7 9 3 – – – – 250 – 4 8 2 10 4 50 – 300 – – – 3 1 7 6 2 50 200 – – 200 – v6=0 Запасы 250 350 450 А4 u4= 0 Потребности 7 9 5 6 4 – – – 400 50 100 100 200 300 400 500 100 550 1600 Полагая u4 = 0, последовательно находим: v4 = 6, v5 = 4, v6 = 0, u1 = – 1, u3 = – 2, v1 = 5, v2 = 3, u2 = – 1, v3 = 3. Для построенной системы потенциалов выполнены условия оптимальности для незанятых клеток, следовательно, получен оптимальный план. Минимальный объем грузоперевозок в тонно-километрах составляет: Z = 2503 + 504 + 3002 + 503 + 2001 + 2002 + 4006 + 504 = 4900. Для достижения оптимального плана грузоперевозок необходимо, чтобы первая скирда в полном объеме (250т) была перевезена на пятую ферму. Из второй скирды, в которой хранится 350т соломы, необходимо 50т перевезти на первую ферму и 300т – на третью. Из третьей скирды, в которой хранится 450т соломы, необходимо 50т перевезти на первую ферму и по 200т на вторую и пятую фермы. Из четвертой скирды 400т следует перевезти на четвертую ферму и 50т – на пятую, при этом в ней останутся излишки соломы в количестве 100т. Алгоритм метода потенциалов применяется при решении экономических задач (так называемых задач распределительного типа), которые по своему характеру не имеют ничего общего с транспортировкой груза. Поэтому величины cij и xij могут иметь различный смысл в зависимости от конкретной задачи. Пример.3. Кормовые культуры в хозяйстве могут возделываться на четырех земельных участках с различным плодородием. Под кукурузу на силос должна быть выделена площадь в 740 га, под однолетние травы на сено – 810 га и под многолетние травы на сено – 450 га. Площадь первого участка равна 630 га, второго – 440 га, третьего – 460 га и четвертого – 470 га. Урожайности кормовых культур в центнерах кормовых единиц с одного гектара приведены в таблице 1.11. Таблица 1.11 Урожайности кормовых культур (ц корм. ед./га) на различных земельных участках. Участки Культуры Кукуруза на силос Однолетние травы на сено Многолетние травы на сено 1 32 2 40 3 38 4 36 12 10 15 12 15 14 15 12 Требуется составить такой план размещения культур по участкам, чтобы обеспечить получение максимального количества кормовых единиц. Данная задача относится к классу задач распределительного типа (необходимо распределить кормовые культуры по участкам), поэтому может быть математически формализована как транспортная. Обозначим через xij площадь в гектарах, отводимую под i – ю кормовую культуру (i = 1 – кукуруза на силос, i = 2 – однолетние травы на сено, i = 3 – многолетние травы на сено) на j – м участке (j = 1, 2, 3, 4). Обозначим через cij урожайность в ц корм.ед./га i-й кормовой культуры на j – м участке. В соответствии с постановкой задачи получим функцию цели: 3 4 Z   cij xij  max i 1 j 1 Обозначая через ai площадь, отводимую под i-ю кормовую культуру, а 3 4 i 1 j 1 через bj – площадь j-го участка и учитывая, что  a i   b j , получим: 4  xij  ai ; ____ i  1, 3; j 1 3  xij  b j ; ____ j  1, 4; i 1 xij  0; _____ i  1, 3; ____ j  1, 4. Отсюда легко усмотреть полную аналогию с транспортной задачей (1.2) – (1.5), за исключением критерия оптимальности. Впрочем, и это отличие ликвидируется, если в полученной нами функции цели все значения cij считать отрицательными, (т.е. умножить функцию цели на – 1). Иногда подобного рода задачи решают в их прямой постановке, т.е. ищут максимум функции цели Z. В этом случае процедура решения задачи сохраняется с учетом того обстоятельства, что когда речь идет об оптимальном элементе cij, то в задаче на максимум им будет не минимальный, а максимальный элемент. Кроме того, при решении задачи на максимум, условия оптимальности (1.11) принимают вид: ui + vj  cij для xij = 0 (1.11) Проиллюстрируем Первоначальный это опорный решением план построим поставленной методом задачи. максимальной стоимости. Таблица 1.12 Потребители В1 v1=12 Поставщики А1 u1=23 А2 u2=0 В2 v2=17 32 – 40 440 12 180 В3 v3=15 38 15 15 12 + 160 – 470 14 Запасы 36 – 300 1 + 10 – В4 V4=12 15 12 740 810 А3 u3=3 450 – – – 450 Потребности 630 440 460 470 2000 Выбираем в таблице наибольшую стоимость. Ей соответствует клетка (1, 2), в которую помещаем 440 единиц (максимально возможное количество) и закрываем второй столбец. Далее, в клетку (1, 3) помещаем 300 единиц и закрываем первую строку, в клетку (3, 1) помещаем 450 единиц и закрываем третью строку, в клетку (2, 3) помещаем 160 единиц и закрываем третий столбец, в клетку (2, 1) помещаем 180 единиц и, наконец, в клетку (2, 4) – 470 единиц. Полагая u2 = 0, строим систему потенциалов: v1 = 12, v3 = 15, v4 = 12, u3 = 3,u1 = 23,v2 = 17. Проверяя выполнение условий оптимальности (1.11) для незанятых клеток, обнаруживаем, что для клетки (1, 4) оно не выполнено: u1+ v4 = 23 + 12 = 35 < 36. Отмечаем эту клетку знаком «+» и строим цикл: (1, 4)  (2,4)  (2, 3)  (1, 3)  (1, 4), поочередно проставляя знаки «–» и «+». Перемещая по циклу 300 единиц (наименьшее значение из клеток, отмеченных знаком «– »), получим новый план (табл. 1.13). Таблица 1.13 Потребители В1 v1=12 Поставщики А1 u1=24 А2 u2=0 А3 u3=3 Потребности В2 v2=16 32 – В3 v3=15 40 12 38 – 440 10 – 180 15 В4 V4=12 36 300 15 460 14 12 170 15 12 450 – – – 630 440 460 470 Запасы 740 810 450 2000 Полагая u2 = 0, последовательно находим: v1 = 12, v3 = 15, v4 = 12, u3 = 3, u1 = 24, v2 = 16. Для построенной системы потенциалов выполнены условия оптимальности. Следовательно, получен оптимальный план. Максимальный объем производства кормов составляет: Z = 44040 + 30036 + 18012 + 46015 + 17012 + 45012 = 46250 ц корм. ед.