Метод потенциалов

В п. 2.2.5 сформулирована задача по перевозке грузов, которая называется транспортной задачей и заключается в определении оптимального плана перевозок некоторого однородного груза из т пунктов отправления A ,, А₂,..., А_т в п пунктов потребления ?,, В₂,..., В„.

Рассмотрим транспортную задачу, где критерием оптимальности является стоимость перевозок всех грузов, которая должна быть минимальной.

Экономико-математическая модель транспортной задачи (и. 2.2.5) содержит системы линейных уравнений (2.1) и (2.2), условие неотрицательности переменных Хц (2.3) и целевую функцию (2.4).

Следует иметь в виду следующее.

• 1. Всякое неотрицательное решение системы линейных уравнений, определяемое матрицей X = (ху), i = ,m;j = 1, гг, называется допустимым планом транспортной задачи.
• 2. Ранг матрицы, составленный из коэффициентов при неизвестных системы линейных уравнений транспортной задачи, на единицу меньше числа уравнений, т.е. равен (т + гг - 1).

Следовательно, число линейно независимых уравнений равно (т + п - 1), они образуют базис, а соответствующие им (т + п - 1) переменные будут являться базисными.

• 3. Допустимый план транспортной задачи, имеющий не более (т + п - 1) отличных от нуля величин Хф называется опорным.
• 4. Если в опорном плане число отличных от нуля компонент равно в точности (т + п - 1), то план является невырожденным, если меньше, то план называется вырожденным.
• 5. План X = (Xij) (i = ,т] = 1, п), при котором функция (2.4) принимает свое минимальное значение, называется оптимальным планом транспортной задачи.
• 6. Для решения транспортной задачи необходимо и достаточно, чтобы суммарные запасы груза в пунктах отправления были равны сумме заявок пунктов назначения

7. Модель транспортной задачи, удовлетворяющая условию (2.17), называется закрытой. Если же указанное условие не выполняется, то модель называется открытой. Так, например, в случае превышения запаса над заявками

вводится фиктивный (/7 + 1) пункт назначения с Потребности п

тью b_n+{ = Yjdi - Z bj, соответствующие тарифы считаются

j-1 _

равными нулю: c,;_w+ = 0, i = 1 ,т.

т п

При Yjd ^< S bj ВВОДИТСЯ фиктивный (/77+1) пункт от-

''-¹ т п

правления с запасом груза а_т+ =?//;- X я, и cootbctctbv-

1 j=i _e _

ющие тарифы принимаются равными нулю: с_т+ ,? = О J = 1, п.

8. Наилучшим элементом матрицы тарифов С называется наименьший тариф, если задача поставлена на минимум, наибольший тариф — если задача поставлена на максимум целевой функции.

Рассмотрим один из методов построения первого опорного плана — метод наименьших тарифов (стоимости).

Алгоритм построения первого опорного плана методом наименьшей стоимости включает следующие этапы: а) среди тарифов находится наименьший;

• б) клетка с выбранным тарифом заполняется величиной, равной максимально возможному объему груза с учетом ограничений по строке и столбцу. При этом либо весь груз вывозится от соответствующего поставщика, либо полностью удовлетворяется заявка потребителя. Строка или столбец таблицы вычеркиваются и в дальнейшем распределении не участвуют;
• в) из оставшихся тарифов вновь находится наилучший (наименьший), и процесс продолжается до тех пор, пока не будет распределен весь груз.

Если модель транспортной задачи открытая и введены фиктивный поставщик или потребитель, то распределение осуществляется сначала для действительных поставщиков и потребителей и в последнюю очередь нераспределенный груз направляется от фиктивного поставщика или к фиктивному потребителю.

9. Дальнейшее улучшение первого опорного плана и получение оптимального плана производим методом потенциалов, который основан на теории двойственности.

План X = (Ху) транспортной задачи будет являться оптимальным, если существует система т + п чисел а„ (3у, называемых потенциалами, удовлетворяющая условиям:

I. F(X) — min

II. F(X) — max

Потенциалы а, и (3j являются переменными двойственной транспортной задачи и обозначают оплату перевозки единицы груза в пунктах отправления (поставщиками) и назначения (потребителями) соответственно, поэтому их сумма равна транспортному тарифу а, + (3, = с,у, а условия (2.18), (2.19) получены на основании второй теоремы двойственности.

Введем обозначение оценки свободной клетки таблицы

Если среди оценок Ау нет положительных (задача поставлена на минимум), то опорный план является оптимальным.

Алгоритм оценки оптимальности плана методом потенциалов включает следующие этапы.

• 1. Построение первого опорного плана.
• 2. Проверка вырожденное™ плана. Потенциалы а, и ру могут быть рассчитаны только для невырожденного плана. Если число занятых клеток в опорном плане меньше, чем (т + п - 1), то не хватит количества уравнений для определения потенциалов, поэтому вносим нуль в одну из свободных клеток таблицы так, чтобы общее число занятых клеток стало равным (т + п - 1). Нуль вводят в клетку с наименьшим тарифом, например в клетку одновременно вычеркиваемых строки и столбца таблицы при составлении нового плана. При этом фиктивно занятая нулем клетка не должна образовывать замкнутого прямоугольного контура с другими клетками таблицы.
• 3. Определение значения функции цели путем суммирования произведений тарифов (удельных затрат) на объем перевозимого груза по всем занятым клеткам таблицы.
• 4. Проверка условия оптимальности. Определяем потенциалы а, и Ру. Для каждой занятой клетки таблицы записываем уравнение а, + р_; = Су (i = i,m;j= 1, п). Получим систему (т + п - 1) уравнений с (т + п) переменными.

Так как число переменных больше числа уравнений (т + п > т + п - 1), то система является неопределенной и имеет бесконечное множество решений. Поэтому одному из неизвестных потенциалов а,-, ру задают произвольное значение, например для простоты вычислений полагаем оц = 0. Тогда остальные потенциалы определяются из приведенных соотношений. В транспортную таблицу добавляются дополнительная строка и столбец, куда заносятся потенциалы.

Определяем оценки свободных клеток А,у.

Если все Д/у < 0 (задача решается на минимум целевой функции) либо все А у > 0 (задача решается на максимум целевой функции), то оптимальный план найден. Если хотя бы одна оценка свободной клетки Ау > 0 (задача поставлена на минимум) или Ау < 0 (задача поставлена на максимум), план не является оптимальным, его можно улучшить, осуществив перераспределение груза.

5. Построение нового опорного плана. Из всех положительных оценок свободных клеток выбираем наибольшую (если задача поставлена на минимум), из отрицательных — наибольшую по абсолютной величине (если задача поставлена на максимум). Клетку, которой соответствует наибольшая оценка, следует заполнить, т.е. направить груз. Заполняя выбранную клетку, необходимо изменить объемы поставок, записанных в ряде других занятых и связанных с заполняемой так называемым циклом.

Циклом, или прямоугольным контуром, в таблице условий транспортной задачи называется ломаная линия, вершины которой расположены в занятых клетках таблицы, а звенья — вдоль строк и столбцов, причем в каждой вершине цикла встречаются ровно два звена, одно из которых находится в строке, другое — в столбце. Если ломаная линия, образующая цикл, пересекается, то точки пересечения не являются вершинами. Для каждой свободной клетки таблицы можно построить единственный цикл.

Вершинам цикла, начиная от вершины, находящейся в свободной клетке, присваиваем поочередно знаки «+» и «-».

Из объемов груза, стоящих в минусовых клетках, выбираем наименьшее и обозначим его у. Перераспределяем величину у по циклу, прибавляя у к соответствующим объемам груза, стоящим в плюсовых клетках, и вычитая у из объемов груза, находящихся в минусовых клетках таблицы. В результате клетка, которая ранее была свободной, становится занятой, а одна из занятых клеток цикла становится свободной.

Полученный новый опорный план проверяется на оптимальность, т.е. возвращаемся к четвертому этапу алгоритма.

Примечания.

• 1. Если в минусовых клетках построенного цикла находятся два (или несколько) одинаковых минимальных значения Хф то при перераспределении объемов груза освобождаются две (или несколько) клеток и план становится вырожденным. Для продолжения решения необходимо одну или несколько освобождающихся клеток таблицы занять нулем, причем предпочтение отдается клетке с наименьшим тарифом. Нулей вводится столько, чтобы во вновь полученном опорном плане число занятых клеток было равно (т + п - 1).
• 2. Если в оптимальном плане транспортной задачи оценка свободной клетки равна нулю (А,-, = 0), то задача имеет множество оптимальных планов. Для клетки с нулевой оценкой можно построить цикл и перераспределить груз. В результате полученный оптимальный план будет иметь такое же значение целевой функции.
• 3. Значение целевой функции па каждой итерации можно рассчитать следующим образом:

F(Xk) = - уАу (задача поставлена на минимум);

F(X*) = F(Xk-1) + уА у (задача поставлена на минимум), где у — величина перемещаемого по циклу объема груза; у у — оценка свободной клетки, ^которую направляется груз при переходе к новому плану; F(Xf_{) — значение целевой (|)ункции на k-й итерации; F(XAi) — значение целевой функции на предыдущей итерации.

Пример 2.11. На три базы А, А₂, Аз поступил однородный груз в количествах, соответственно равных 6,8,10 сд. Этот груз требуется перевезти в четыре магазина В_ь В₂, В₃, В₄ соответственно в количествах 4, 6, 8, 8 ед. Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов (тыс. руб. за единицу груза)

Надо составить план перевозок однородного груза с минимальными транспортными издержками.

Проверим необходимое и достаточное условие разрешимости задачи

Как очевидно, суммарная потребность груза в пунктах назначения превышает запасы груза на трех базах. Следовательно, модель исходной транспортной задачи является открытой.

Чтобы получить закрытую модель, введем дополнительную, фиктивную базу Л₄ с запасом груза, равным 2 ед. (26 - 24). Тарифы перевозки единицы груза из этой базы Л₄ во все магазины полагаем равны нулю.

Занесем исходные данные в распределительную табл. 2.13.

1. Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

Среди тарифов из всей таблицы наименьшим является Сц = 1, поэтому в клетку АВ направляем максимально возможный груз. Он равен min {6, 4} = 4. Тогда Хц = 4 и из базы А не вывезен груз в размере 2 ед., а потребность магазина В_{ удовлетворена полностью. Столбец таблицы В_{ выходит из рассмотрения. Из оставшихся тарифов строки наименьший с₂ ⁼ 2. В клетку АВ₂ направляем максимально возможный груз, равный min {2, 6} = 2. Тогда строка А| выходит из рассмотрения, поскольку из базы А вывезен весь груз, а потребность второго магазина не удовлетворена на 4 ед. Из оставшихся тарифов наилучший с₂₂ = 3 и С34 = 3. В клетку А₂В₂ направляем груз, равный min {8, 4} = 4. При этом вычеркивается столбец В₂ из рассмотрения. Из оставшихся тарифов наименьший С34 = 3.

В клетку Л3В4 направляем груз, равный min {10,8} = 8. При этом потребность четвертого магазина удовлетворена, а из третьей базы не вывезены 2 ед. Этот нераспределенный груз направляем в клетку Л3В3, Х33 = 2. Потребность третьего магазина не удовлетворена на 2 ед. Направим от фиктивного поставщика — базы Л₄ — 2 ед. в клетку Л4В3, т.е. Х(₃ = 2.

В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.

• 2. Подсчитаем число занятых клеток таблицы, их 7, а должно быть га + я-1=4 + 4-1=7. Следовательно, опорный план является невырожденным.
• 3. Определяем значение целевой функции первого опорного плана.

4. Проверим оптимальность опорного плана. Найдем потенциалы а,, р, по запятым клеткам таблицы, в которых а, + р_; = c_ijt полагая, что а] = 0, решим систему уравнений

Занесем найденные значения потенциалов в табл. 2.13 и вычислим оценки свободных клеток Ajj = (Р,- + а,) - с,„ причем для оптимального плана Ау < О

Первый опорный план не является оптимальным, так как А₁₃ > О и А₁₄ > 0, поэтому переходим к его улучшению.

5. Выбираем максимальную оценку свободной клетки — А₁₃ = 3. Для клетки АВз построим цикл перераспределения груза. Для этого в перспективную клетку АВ^ поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «—». Цикл приведен в табл. 2.13.

Из грузов^-, стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min {2,4} = 2. Прибавляем 2 к объемам грузов, стоящих в плюсовых клетках, и вычитаем 2 из Хф стоящих в минусовых клетках. В результате получим новый опорный план И, приведенный в табл. 2.14.

6. Определяем значение целевой функции

• 7. Количество занятых клеток в плане II — 7, следовательно, план невырожденный.
• 8. Проверяем оптимальность плана методом потенциалов, для этого находим потенциалы а„ р, но занятым клеткам, где а + Pi = Сф полагая, что оц = О

Таблица 2.14

Затем рассчитываем оценки свободных клеток

План, полученный в табл. 2.14, не оптимальный, так как Д₂₁ > О

И Дз] > 0.

9. Проводим улучшение плана II путем перераспределения грузов. В качестве перспективной клетки для загрузки выбираем А₂В, в которую записываем «+», затем строим цикл перераспределения, приведенный в табл. 2.14.

В построенном цикле определяем величину у = min(4, 2) = 2. Перераспределив груз, получаем новый план III, приведенный в табл. 2.15.

10. Количество занятых клеток 7 и должно быть т + п - 1 = 7, следовательно, план III невырожденный.

И. Вычислим значение целевой функции

Таблица 2.15

12. Проверяем оптимальность плана III методом потенциалов. Находим потенциалы по занятым клеткам

Рассчитываем оценки свободных клеток

План не оптимальный, так как A₂i > 0 и Д₂4 > 0.

13. Проводим улучшение плана III перераспределения груза.

В качестве перспективной клетки для загрузки выбираем А₂В_Ху в которую записываем «+», затем строим цикл перераспределения в табл. 2.15.

Определяем величину у = min (2; 2) = 2. После проведения операции перераспределения получаем план IV, приведенный в табл. 2.16.

14. План получается вырожденным, поскольку в минусовых клетках цикла находятся два одинаковых минимальных объема груза, равные 2, и при перераспределении две клетки А_ХВ_Х и А₂В₂

Таблица 2.16

оказались свободными, поэтому число занятых клеток будет меньше, чем т + п — 1 = 7. Для продолжения решения в одну из освободившихся клеток — в клетку АВ_Ь так как тариф с меньше с₂з, записываем нуль, т.е. загружаем ее.

15. Вычисляем значение целевой функции

16. Проверяем оптимальность плана IV методом потенциалов. Находим потенциалы по занятым клеткам

Рассчитаем оценки свободных клеток

Поскольку все оценки не превышают нуля, то план IV является оптимальным, тогда решение задачи можно представить следующим образом:

Таким образом, с первой базы необходимо весь груз направить в третий магазин, со второй базы направить в первый и второй магазины в количестве 2 и 6 ед., а груз с третьей базы следует вывозить в первый и четвертый магазины в количестве 2 и 8 ед. соответственно. При этом потребность третьего магазина В₃ остается неудовлетворенной в объеме 2 ед. Общая стоимость доставки груза потребителям будет минимальной и составляет 78 тыс. руб., экономия составила 10 тыс. руб. Так как оценка свободной клетки Д₂₄ = 0, то задача имеет множество оптимальных планов.

Контрольные вопросы и задания

• 1. Сформулируйте транспортную задачу.
• 2. Как составляется первый опорный план в транспортной задаче?
• 3. Поянитс сущность метода потенциалов. Как с его помощью проверяется опорный план транспортной задачи на оптимальность?
• 4. Как решаются транспортные задачи с нарушенным балансом между спросом и предложением?
• 5. Как разрешается проблема вырождения в транспортной задаче?

Задачи

Поставщики товара — оптовые коммерческие предприятия А_х, А_2у А_т имеют товаров соответственно в количестве а_у а₂, а_т (i = 1, т). Розничные торговые предприятия B_h В₂,..., В_п подали заявку на закупку товаров в объемах соответственно Ь_х, Ь_2у ..., b_n {j = 1, п). Тарифы перевозок единицы груза с каждого из пунктов поставки в соответствующие пункты потребления заданы в виде матрицы С= ||с,у|| (/ = 1, mj = 1, п).

Найдите такой план перевозки груза от поставщиков к потребителям, чтобы совокупные затраты на перевозку были минимальными.

3. Фирма «Союз» обеспечивает доставку видео- и аудиокассет с четырех складов, расположенных в разных точках города, в четыре магазина.

Запас кассет, имеющихся на складах, а также объемы заказов магазинов и тарифы на доставку представлены в транспортной таблице.

Определите объемы перевозок, обеспечивающих их минимальные затраты.

4. Московский филиал фирмы The Coca-Cola Company, выпускающей газированные напитки Sprite, Coca-Cola, Fanta, складируемые в разных местах, должен поставить продукцию в четыре крупных московских супермаркета: «Рам- стор-1», «Рамстор-2», «Седьмой Континент», «Арбатский».

Каждая упаковка содержит шесть емкостей по 2 л. Тарифы на доставку товара, объемы запасов и заказы на продукцию приведены в таблице.

Определите оптимальный план поставок газированных напитков в супермаркеты города, а также вид транспортного средства для доставки продукции и затраты на перевозку.

5. Автотранспортная компания «Астрада» обеспечивает доставку шин Bridgestone с трех оптовых складов, расположенных в Москве, Нижнем Новгороде и Покрове, в пять магазинов в Чебоксарах, Нижнем Новгороде, Вязниках, Набережных Челнах и Казани. Объемы запасов шин на складах, объемы заявок магазинов и тарифы на перевозку приведены в транспортной таблице.

Составьте оптимальный план, обеспечивающий минимальные транспортные расходы перевозок.

6. Фирма «Московия» заключила контракт с компанией АЛРОСА («Алмазы России —Саха») на покупку промышленного золота для его реализации в пяти городах в объемах:

Самара — 80 кг, Москва — 260 кг, Ростов-на-Доиу — 100 кг, Санкт-Петербург — 140 кг, Нижний Новгород — 120 кг.

Компания располагает тремя месторождениями — «Мирное», «Удачный» и «Полевое», которые планируют за год выработать соответственно 200, 250 и 250 кг золота.

Определите минимальную стоимость фрахта специализированного транспорта, обеспечивающую полное удовлетворение заявок покупателей, при заданной матрице тарифов.

7. Составьте оптимальный план перевозки автомобилей из городов Ижевска, Казани, Тольятти в города Москву, Саранск и Ульяновск. Стоимость перевозки одного автомобиля составляет 10 руб. за километр. Расстояние между городами и объемы заявок представлены в таблице.

Составьте оптимальный план перевозок, обеспечивающий минимальные затраты на перевозку.

8. Составьте оптимальный план перевозки лекарств с минимальными затратами из аптечных складов в пять аптек города: больницу № 15, городские клинические больницы № 7, 23 и 50 и госпиталь им. Н. Н. Бурденко. Запасы лекарств на складах, заявки потребителей и тарифы перевозок представлены в таблице.

9. Составьте оптимальный план перевозки угля с минимальными транспортными расходами из шахт «Воргашорская» (В), «Западная» (3) и «Комсомольская» (К), еженедельно добывающих соответственно 26 тыс., 32 тыс. и 17 тыс. т. Покупатели угля расположены в разных городах (Л, В, С и D), заявки которых составляют 28 тыс., 19 тыс., 12 тыс. и 16 тыс. т соответственно. Тарифы, определяющие стоимость перевозки 1 тыс. т между поставщиками и потребителями, представлены в транспортной таблице.

10. Составьте оптимальный план завоза хлебобулочной продукции с минимальными транспортными расходами из трех пекарен фирмы «Колос» в четыре булочные города — Л, В, С, D. Заказы на поставку хлебобулочных изделий, производительность пекарен и транспортные тарифы представлены в транспортной таблице.

11. Сельскохозяйственный кооператив «Ласточка» в области имеет три филиала — Ф_ь Ф₂ и Ф₃, которые обеспечивают поставками подсолнечных семян в соответствии с заявками пять заводов — производителей подсолнечного масла — Л, В, С, D и Е. Объемы запасов семян, объемы заказов на поставку и тарифы на перевозку приведены в транспортной таблице.

Постройте оптимальный план перевозки подсолнечных семян с минимальными транспортными расходами.

Автор: Фомин Геннадий