Специальные задачи линейного программирования

2. Специальные задачи линейного программирования 2.1 Транспортная задача Общая постановка транспортной задачи состоит в определении оптимального плана перевозок однородного груза из N пунктов отправления A 1 ,…, A N в М пунктов потребления B 1 , B 2 ,…, B M . При этом в качестве критерия оптимальности обычно берется минимальная стоимость перевозок всего груза. Мощности поставщиков и запросы потребителей, а также затраты на перевозку единицы груза для каждой пары «поставщик-потребитель» будем сводить в таблицу поставок. Рассмотрим, к примеру, следующую задачу. Имеется N карьеров, где добывается песок и М потребителей песка (кирпичные заводы, растворобетонные узлы и т.д.). В i-ом карьере ежесуточно добывается а i тонн песка, а j-му потребителю ежесуточно требуется b j тонн песка. Стоимость перевозки одной тонны песка с i-го карьера на j-ый пункт потребления равна с ij . Требуется составить план перевозок песка таким образом, чтобы все пункты потребления были снабжены требуемым количеством песка, на карьерах не должно создаваться запасов добытого песка, а стоимость перевозок была бы минимальной. Предположим xij - это количество тонн сырья, которое было перевезено с i-го карьера на j-ый пункт потребления. Суммарная стоимость перевозок, будет равна N M f = ∑ ∑ сij x ij , i =1 j =1 (2.1) при этом на j-ый пункт потребления должно быть доставлено b j количество песка, т.е. N ∑ xij = b j , i =1 а с i-го карьера вывезено а i , тонн песка, т.е., M ∑ xij = ai . j =1 Потребуем также, чтобы все x ij ≥ 0. Итак, получили следующую задачу: N M f = ∑ ∑ сij x ij → min . i =1 j =1 Найти минимальное значение f при выполнении условий: N ∑ xij = b j (j = 1, M ) , i =1 (2.2) M ∑ xij = ai (i = 1, N ) , j =1 xij ≥ 0, ( i = 1, N ; j = 1, M ) . (2.3) Как мы видим, это задача линейного программирования, и поиск оптимального плана транспортной задачи можно вести с помощью симплекс-метода. Однако, в силу некоторых свойств этой задачи (каждая неизвестная входит лишь в два уравнения-ограничения и коэффициенты при неизвестных в ограничениях равны единице), она может проще решаться специальными методами. ПРИМЕЧАНИЕ. Термин "транспортная задача" (в дальнейшем ТЗ) возник в 30-х годах. Это была одна из самых первых задач, которую стали решать с помощью методов линейного программирования. Множество проблем, совершенно не связанных с перевозкой грузов могут иметь своей математической моделью "транспортную задачу". Перейдем к рассмотрению способов решения транспортной задачи. ОПРЕДЕЛЕНИЕ 2.1 Транспортная задача, в которой сумма запасов равна сумме потребностей, называется закрытой. В противном случае задача − открытая. 2 В случае если транспортная задача является открытой, невозможно удовлетворить всех потребителей (если сумма потребностей больше суммы запасов) или вывезти все грузы от поставщиков (если сумма запасов больше, чем сумма потребностей). В этом случае поступают следующим образом: а) если сумма запасов больше суммы потребностей N M i =1 j =1 ( ∑ ai > ∑ b j ) , то введем в таблицу еще одного потребителя, потребность которого определим, как N M i =1 j =1 ∑ ai − ∑ b j . Так как грузы к новому потребителю (фиктивному) отправляться не будут, то тарифы на перевозку грузов фиктивному потребителю положим равными нулю; б) если сумма запасов меньше суммы потребностей N M i =1 j =1 ( ∑ ai < ∑ b j ) , то вводим в таблицу еще одного поставщика (фиктивного), запасы груза у которого определим, как M N j =1 i =1 ∑ b j − ∑ ai , тарифы на перевозку грузов от фиктивного поставщика потребителям положим равными нулю из тех же соображений, что и в первом случае (цены в новом столбце проставим равными нулю). Из чего следует, что в дальнейшем можем рассматривать только закрытые задачи. Приведем без доказательства теорему. 3 ТЕОРЕМА 2.1. Необходимым и достаточным условием разрешимости транспортной задачи является ее закрытость. Так как транспортная задача является задачей линейного программирования, то и схема нахождения оптимального решения остается той же: находится первоначальный опорный план, проверяется на оптимальность и, если он не оптимален, то переходим к другому опорному плану, улучшающему целевую функцию в смысле оптимума (например, уменьшающему значение целевой функции). Вернемся к общей постановке транспортной задачи (2.1)−(2.3). Мы имеем M х N неизвестных x ij при i = 1, N и j = 1, M и M + N уравнений. Система ограничений (2.2) линейно зависима. Сложив первые M уравнений системы (2.2), получим: M N M ∑ ∑ xij = ∑ b j . j =1 i =1 j =1 Сумма последних N уравнений дает N M N i =1 j =1 i =1 ∑ ∑ xij = ∑ ai . Но для закрытой транспортной задачи N M i =1 j =1 ∑ ai = ∑ b j , N M откуда следует M N ∑ ∑ xij = ∑ ∑ xij . i =1 j = 1 j =1 i =1 Следовательно, она может быть разрешена относительно не более чем M+N-1 неизвестной (можно доказать, что ранг системы ограничений (2.2) в точности равен M+N−1), то есть опорный план может иметь не более M+N−1 отличных от нуля неизвестных. 4 ОПРЕДЕЛЕНИЕ 2.2. Опорный план, содержащий M+N−1 отличных от нуля значений неизвестных, называется невырожденным, а в противном случае − вырожденным. 2.2 Поиск начального опорного плана Для нахождения опорного плана существуют несколько методов (метод северо-западного угла, метод минимального элемента, метод аппроксимации Фогеля). Рассмотрим методы северо - западного угла и минимального элемента. 2.2.1 Метод северо-западного угла В верхнюю левую клетку (северо-западный угол) таблицы поставок записываем наименьшее из чисел b 1 и а 1 , пересчитываем запасы и потребности и столбец, с исчерпанным запасом, или строку с удовлетворенной потребностью исключаем из дальнейшего расчета. В оставшейся части таблицы снова находим северо-западный угол, заполняем эту клетку, вычеркиваем строку или столбец и опять обращаемся к северо-западному углу и так далее. Важнейшим условием построения опорного плана является назначение в выбранной клетке наибольшего возможного плана перевозки. Пример 2.1. Три песчано-гравийных карьера добывают в сутки 140, 180 и 160 условных единиц гравия. Для строительства пяти дорог необходимо гравия в количестве 60, 70, 120, 130 и 100 условных единиц соответственно. Стоимость перевозок (тарифов) из одного карьера на один объект (строящуюся дорогу) приведена в таблице 2.1 в условных денежных единицах (например, чтобы перевезти 1 условную единицу гравия с карьера №1 на дорогу №1 надо затратить две условные денежные единицы). Составим таблицу 2.1. 5 Таблица 2.1 Карьер Дорога №1 №2 №3 №4 №5 Запасы Карьер №1 2 /60 3 4 2 4 140 Карьер №2 8 5 1 4 1 180 Карьер №3 9 8 4 7 2 160 Потребности 60 70 120 130 100 480/480 В северо-западную клетку поместим число 60 (дороге №1 требуется 60 условных единиц гравия). После такого распределения карьер №1 может поставить еще 80 условных единиц (140−60=80), а первую строку в дальнейшем не рассматриваем (дорогу №1 мы уже обеспечили). Переходим к следующей "северо-западной" клетке − это клетка (дорога №2; карьер №1). В нее поместим 70 единиц (min (80;70)=70, где 80 − оставшийся запас на карьере №1, а 70 − потребность дороги №2). "Вычеркнув" вторую строку, перейдем к клетке (дорога №3; карьер №1). В эту клетку мы сможем поместить только 10 единиц, так как у карьера №1 осталось всего 10 единиц (140−60−70). После этого переходим к клетке (дорога №3; карьер №2), предварительно "вычеркнув" первый столбец и так далее. В результате получаем таблицу 2.2. Таблица 2.2 Карьер Дорога №1 №2 №3 №4 №5 Запасы 6 Карьер №1 2 /60 3/70 4 /10 2 4 140 Карьер №2 8 5 1 /110 4 /70 1 180 Карьер №3 9 8 4 7 /60 2 /100 160 Потребности 60 70 120 130 100 480 /480 Найдем затраты на перевозки при составленном плане: f = 2·60+8·0+9·0+3·70+5·0+8·0+4·10+1·110+4·0+ +2·0+4·70+ 7·60+4·0+1·0+2·100=1380 условных денежных единиц. Приведем свойство опорного плана, который получен с помощью метода северо − западного угла. ТЕОРЕМА 2.2. Число положительных компонент в опорном плане (число заполненных клеток в таблице) меньше или равно N+M−1. Действительно: пусть имеем M потребителей и N поставщиков. В процессе построения опорного плана на каждом шаге вносим в одну клетку (i, j) положительное число. При этом либо в одной строке, либо в одном столбце потребности или запасы после пересчета становятся равными нулю. При заполнении последней клетки после пересчета и в столбце и в строке запасы и потребности становятся равными нулю. Итак, мы получили M нулей в пересчитанном столбце потребностей и N нулей в пересчитанной строке запасов. Так как ноль в строке или (возможно «и») столбце мы получаем в результате заполнения одной клетки, а при заполнении последней клетки мы получаем сразу два нуля, то число заполненных клеток равно M+N−1 или меньше. Если в процессе построения плана встретится клетка (кроме последней), после заполнения которой запасы и потребности столбца и строки становятся равными нулю, то число неизвестных будет меньше N+M−1. И мы будем иметь вырожденный опорный план. 2.2.2 Метод минимального элемента Алгоритм нахождения начального опорного плана. 1. В клетку с минимальной единичной стоимостью (минимальным тарифом) записывают наибольшее возможное количество груза для поставки. 2. Производится корректировка оставшихся запасов и потребностей. 7 3. Выбирается следующая клетка с наименьшим тарифом, в которую планируется наибольшее возможное количество груза для поставки и т.д. до тех пор, пока оставшиеся запасы и оставшиеся потребности не станут равными нулю. 4. Если наименьший тариф соответствует более чем одной клетке, выбор осуществляется случайным образом. Для предыдущего примера начальный опорный план, построенный методом наименьшей стоимости, приводится в таблице 2.3. Таблица 2.3 Карьер Дорога №1 №2 №3 №4 №5 Запасы Карьер №1 2/60 3 4 2/80 4 140 Карьер №2 8 5 1/120 4 1/60 180 Карьер №3 9 8 /70 4 7/50 2/40 160 Потребности 60 70 120 130 100 480/480 2.2.3 Решение транспортной задачи методом потенциалов Изложенный ниже метод потенциалов решения транспортной задачи реализуется для невырожденных опорных решений. Поэтому, если начальный опорный план окажется вырожденным (заполнено меньше, чем M+N−1 клеток), то для соответствующего потребителя требуется ввести дополнительно нулевую поставку (или сколь угодно малую) от следующего поставщика, увеличив тем самым число формально занятых клеток. Это может случиться в силу того, что при составлении опорного плана на каких-то этапах из рассмотрения выпадали одновременно строка и столбец (удовлетворены потребности и использованы запасы). Исследуем опорный план задачи на оптимальность. Вначале припишем каждому потребителю величину 8 v j , j = 1, M -потенциал j-го потребителя, который при данном опорном плане характеризует затраты на размещение одной единицы поставляемой продукции указанному потребителю. Каждому поставщику припишем величину u i , i= 1, N - потенциал i-го поставщика, который при данном опорном плане характеризует затраты на поставку одной единицы продукции от указанного поставщика. Очевидно, что величина v j – u i − характеризует затраты на поставку от i-гo поставщика j-му потребителю. Определим ее из условия v j – u i = с ij для занятых клеток. Тогда разность (v j – u i ) – с ij , найденная для свободных клеток, будет характеризовать изменение затрат на транспортировку одной единицы груза, при изменении маршрута транспортировки в соответствующую свободную клетку при найденном распределении потенциалов. Величину v j – u i – с ij будем называть теневой ценой по перемещению единицы груза от i-го поставщика j-му потребителю. Если теневая цена для свободной клетки меньше нуля, то перемещение по маршруту i→j может лишь привести к увеличению затрат, что нецелесообразно. Если же теневая цена для свободной клетки больше нуля, то перемещение по маршруту приведет к уменьшению затрат. В итоге можно сформулировать условия оптимальности опорного плана. ТЕОРЕМА 2.3. Если для некоторого опорного плана транспортной задачи будут выполняться условия v j –u i – с ij =0 для клеток с х ij >0 и v j –u I –с ij ≤ 0 для клеток с x ij =0 , то этот план является оптимальным. Проверим оптимальность полученного плана в приведенной выше задаче. Сначала найдем потенциалы u i и v j . Установим соответствие: K 1 => j=1; K 2 => j=2; K 3 => j=3; Дорога № 1=> i=1,…, дорога № 5=> i=5. Тогда клетки, в которых х ij >0 будут следующие: (1,1)=60; (2,1)=70; (3,1)=10; (3,2)=110; (4,2)=70; (4,3)=60; (5,3)=100. Составим уравнения для нахождения u i и v j : 9 v1 – u 1 – 2 = 0 (2 - цена (тариф) для клетки (1,1)) v1 – u2 – 3 = 0 v1 – u3 – 4 = 0 v2 – u3 – 1 = 0 v2 – u 4 – 4 = 0 (2.4) v3 – u4 – 7 = 0 v3 – u5 – 2 = 0. Получили систему из семи уравнений с восемью неизвестными (в общем случае M+N−1 уравнение по числу заполненных клеток) и M+N неизвестных (по числу потенциалов). Такая система уравнений имеет бесчисленное множество решений. Придавая одной из переменных какое-то значение (например, u 1 =0) определяем остальные потенциалы из решения системы u 1 =0; v 1 =2; u 2 =−1; u 3 =−2; v 2 =−1; u 4 =−5; v 3 =2; u 5 =0. Теперь проверяем наш план на оптимальность, то есть проверяем условие v j − u i − с ij ≤ 0 для незаполненных клеток: (1,2): –1 – 0 – 8 = – 9 ≤ 0 (1,3): 2 – 0 – 9= –7 ≤ 0 (2,2): –1– (–1) – 5 = –5 ≤ 0 (2,3): 2– (–1) – 8 = –5 ≤ 0 (3.3): 2– (–2) – 4 = 0 (4,1): 2 – (–5) – 2 = 5 (5,1): 2– 0 – 4 = – 2 ≤ 0 (5,2): –1– 0 – 1 = –2 ≤ 0. Итак, мы получили клетку (4,1), которая не удовлетворяет условию оптимальности плана. Путем перераспределения перевозок будем улучшать полученный план. Для этого выберем клетку с наибольшей разностью (v j –u i –с ij >0). Начиная с этой клетки (4,1) построим цикл пересчета. ОПРЕДЕЛЕНИЕ 2.3. Циклом пересчета в таблице транспортной задачи назовем ломаную линию, вершины которой находятся в заполненных клетках, в клетке пере10 счета эта линия имеет начало и конец, а звенья линии располагаются вдоль строк и столбцов таблицы. Таблица 2.4 Карьер Дорога №1 №2 №З №4 №5 Карьер №1 Карьер №2 Карьер №З 2 3 4 2 4 8 5 1 4 1 9 8 4 7 2 – + 60 70 10 + – 10 70 60 100 В цикл, образованный этой клеткой войдут клетки (3,1); (3,2); (4,2) (таблица 2.4). Начиная с выбранной клетки, (клетки пересчета) будем отмечать вершину ломаной линии знаками "+" и "−" по часовой стрелке. Причем клетки пересчета (4,1) и (3,2) со знаком "+" назовем "плюсовые клетки", а клетки (3,1) и (4,2) со знаком "−" − "минусовые клетки". В клетку пересчета записывают меньшее из чисел x ij , стоящих в "минусовых" клетках. Одновременно это число прибавляют к числам, стоящим в "плюсовых" клетках и вычитают из чисел, стоящих в "минусовых" клетках. "Минусовая" клетка, содержащая это наименьшее число, освобождается (таблица 2.5). Таблица 2.5 Карьер Карьер №1 Карьер №2 Карьер №3 Дорога vj 2 4 7 №1 2 60 8 9 №2 3 70 5 8 №3 4 1 120 4 №4 2 10 4 60 7 60 №5 4 1 2 100 ui –1 3 5 Клетка (3,1) стала свободной, в (4,1) записано 10, в (3,2) – 120 (110+10), а в (4,2) – 60 (70 – 10). Суммарные затраты на перевозку равны: 11 2·60 + 3·70 +1·120 + 2·10 + 4·60 +7·60+2·100 =1330. Итак, затраты снизились на 1380 – 1330 = 50 единиц. Вновь возвращаемся к нахождению потенциалов для нового плана. Для упрощения записи не будем выписывать систему уравнений, а все расчеты проведем в таблице, для чего введем в нее строку v j и столбец u i . Записываем в столбец "u" в первой строке нуль (то есть u 1 =0). Ищем в первой строке заполненные клетки и из выражения v j =с ij +u i находим v 1 =с 11 +u 1 =2+0=2 (заполнена клетка (1,1)). Больше в первой строке нет заполненных клеток. Переходим ко второй строке (заполнена клетка (2,1)). Для этой клетки в выражении u 2 =v l –с 21 известны v 1 и с 21 , следовательно, u 2 =2−3=−1. В третьей строке заполнена клетка (3,2), но для нее неизвестны потенциалы v 2 и u 3 , поэтому перейдем к следующей строке. Здесь есть три клетки (4,1), (4.2) и (4,3) из равенства u 4 =v 1 −с 41 =2−2=0, найдем u 4 =0. Тогда v 2 =u 4 +с 42 (для клетки (4,2)) равно 4, а v 3 =u 4 +с 43 =7. Теперь, возвращаясь к клетке (3,2), можно найти u 3 =v 2 –с 32 =4–1=3. Наконец, для клетки (5,3) u 5 =v 3 –с 53 =5. Проверим план на оптимальность. (1,2): 4 – 0 – 8 = – 4 ≤ 0 (2, 2): 4 – 5 – (–1) = 0 ≤ 0 (3,1): 2 – 3 – 4 = – 5 ≤ 0 (5,1): 2 – 5 – 4 = – 7 ≤ 0 (1,3): 7 – 0 – 9 = –2 ≤ 0 (2,3): 7 – (–1) – 8 =0 ≤ 0 (3,3): 7 – 3 – 4 = 0 ≤ 0 (5, 2): 4 – 1– 5 = – 2 ≤ 0 . Итак, условие оптимальности опорного плана выполняется. Ненулевые компоненты оптимального опорного плана перевозок следующие: x 11 =60; х 21 =70; х 41 =10; х 32 =120; х 42 =60; х 43 =60; х 53 =100. При этом плане получим минимальную стоимость перевозок, равную 1330 условных денежных единиц. В заключение опишем алгоритм решения транспортной задачи методом потенциалов: а) находим первоначальный "невырожденный" опорный план одним из известных методов; 12 б) вычисляем потенциалы u i и v j ; в) проверяем все незаполненные клетки на потенциальность (то есть выполнение условия v j – u i – с ij ≤ 0). Если для всех клеток это неравенство справедливо, переходим к п. з), иначе к п. г); г) среди положительных разностей (v j –u i –с ij ) ищем максимальную, клетка, содержащая эту максимальную разность - клетка пересчета; д) отмечаем клетку пересчета знаком "+" и строим цикл пересчета, последовательно присваивая клеткам цикла знаки "–" и "+", начиная с клетки пересчета; е) в клетках, помеченных знаком "–" находим наименьшую поставку и отнимаем ее от клеток "–", а к клеткам "+" прибавляем. При этом клетка, содержащая наименьшую поставку, освобождается; ж) после получения нового распределения возвращаемся к п. б); з) получен оптимальный план перевозок, конец решения. 2.3 Анализ чувствительности Итоговое распределение перевозок, а также значения теневых цен, соответствующих пустым клеткам, позволяет проанализировать модель на чувствительность. А именно, выяснить, в каких пределах можно варьировать тарифы в незанятых клетках, чтобы это не привело к изменению оптимального плана перевозок. Поскольку теневая цена показывает, на какую максимальную (по модулю) величину можно уменьшить тариф на перевозку, чтобы включение клетки в план перевозок не привело бы к улучшению значения целевой функции. Например, в рассмотренной задаче теневая цена клетки (Д№1,K№2) равна 4–0–8=−4, из чего следует, что уменьшение тарифа в этой клетке в пределах от 8 до 4 не приведет к изменению оптимального плана. Изменение тарифов в заполненных клетках в сторону уменьшения делает целесообразным увеличение плана в таких клетках, если это возможно. Если же тариф, стоящий в заполненной клетке, возрастает, то при 13 определенном его значении использование этой клетки становится нежелательным. Иллюстрируем это соображение примером. Рассмотрим заполненную клетку (Д№1,K№1). Если тариф на перевозку станет больше "1", то обратим внимание на циклы, в которых задействована эта клетка. Имеется один такой цикл со свободной клеткой (Д№1,К№2). Теневая цена для (Д№1,K№1) – (–4). В указанном цикле клетка (Д№1,K№1) помечена знаком "–", и любое увеличение тарифа в этой клетке повлечет за собой снижение по модулю теневой цены свободной клетки. Изменение оптимального плана перевозок будет иметь место в том случае, если тариф для клетки (Д№1,K№1) возрастет на величину, большую чем модуль теневой цены свободной клетки, то есть на 4 единицы и превысит 6 единиц. При этом теневая цена клетки (Д№1,K№2) станет положительной и использование этой клетки в плане станет выгодным. Таким образом, можно указать промежутки устойчивости оптимального плана по изменению тарифов для любых клеток − свободных и занятых. Примечание. Если перевозка от какого-то поставщика какому–либо потребителю невозможна, то в алгоритме решения задачи это ограничение учитывается назначением достаточно большого тарифа. 14