Лекция №11 Метод потенциалов

Широко распространенным методом решения транспортных задач является метод потенциалов. Этот метод позволяет упростить наиболее трудоемкую часть вычислений – нахождение оценок свободных клеток.

Теорема 6.8 (признак оптимальности опорного решения). Если допустимое решение , i = 1, 2, ..., m; j = 1, 2, ..., n транспортной задачи является оптимальным, то существуют потенциалы (числа) поставщиков , i = 1, 2, ..., m и потребителей , j = 1, 2, ..., n, удовлетворяющие следующим условиям:

при , (6.12)

при . (6.13)

Доказательство. Используем вторую теорему двойственности (теорема 5.2). Запишем математическую модель транспортной задачи

,

, i = 1, 2, ..., m; j = 1, 2, ..., n.

Составим математическую модель двойственной задачи. Обозначим через , i = 1, 2, ..., m переменные (оценки), соответствующие первым m уравнениям системы ограничений, и через
, j = 1, 2, ..., n, переменные, соответствующие последним n уравнениям. Записываем

,

, i = 1, 2, ..., m; j = 1, 2, ..., n.

Каждое ограничение двойственной задачи содержит только две переменные, так как каждый вектор-условие системы ограничений исходной задачи имеет только две отличные от нуля (равные единице) координаты, i-ю и (m+j)-ю. Условий неотрицательности двойственная задача не имеет, так как все ограничения в исходной задаче – равенства. По второй теореме двойственности (теорема 5.2), если при подстановке в систему ограничений двойственной задачи некоторое ограничение выполняется как строгое неравенство , то соответствующая координата оптимального решения исходной задачи равна нулю . Если же оптимальным решением ограничение удовлетворяется как равенство , то соответствующая координата оптимального решения отлична от нуля,
т. е. .

Группа равенств (6.12)

при ,

используется как система уравнений для нахождения потенциалов. Нетрудно видеть, что эта система могла иметь несколько другой вид, например, или , если перед тем, как записать двойственную задачу, все уравнения одной из групп уравнений исходной задачи умножить на (-1).

Данная система уравнений имеет m+n неизвестных , i = 1, 2, ..., m и , j = 1, 2, ..., n. Число уравнений системы, как и число отличных от нуля координат невырожденного опорного решения, равно m + n - 1. Так как число неизвестных системы на единицу больше числа уравнений, то одной из них можно задать значение произвольно, а остальные найти из системы.

Группа неравенств

при

используется для проверки оптимальности опорного решения. Эти неравенства удобно записать в следующем виде

при . (6.14)

Числа называются оценками свободных клеток таблицы или векторов- условий транспортной задачи, не входящих в базис опорного решения. В этом случае признак оптимальности можно сформулировать так же, как в симплексном методе (для задачи на минимум): опорное решение является оптимальным, если для всех векторов-условий (клеток таблицы) оценки неположительные.

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

6.10. Особенности решения транспортных задач
с неправильным балансом

До сих пор рассматривались транспортные задачи с правильным балансом. Однако на практике чаще встречаются задачи с неправильным балансом. Каковы особенности их решения?

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

.

Очевидно, что в этом случае при составлении оптимального плана перевозок часть запасов поставщиков, равная

,

останется не вывезенной. Поэтому в системе ограничений транспортной задачи первую группу уравнений (6.2) следует заменить неравенствами

, i = 1, 2, ..., m. (6.15)

Вторая группа уравнений остается без изменения, так как запросы всех потребителей удовлетворяются полностью. Для приведения к канонической форме в неравенства (6.15) вводят дополнительные переменные . В результате первые m ограничений задачи принимают вид

, i = 1, 2, ..., m.

В целевую функцию дополнительные переменные не входят (входят с нулевыми коэффициентами). Математическая модель задачи принимает вид

, (6.16)

, i = 1, 2, ..., m, (6.17)

, j = 1, 2, ..., n, (6.18)

, i = 1, 2, ..., m; j = 1, 2, ..., n+1. (6.19)

Запишем необходимое и достаточное условие разрешимости задачи (теорема 6.1)

.

Отсюда получаем

.

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

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

,

часть запросов потребителей, равная

,

останется не удовлетворенной. Поэтому вторая группа уравнений системы ограничений задачи (6.3) заменяется неравенствами

, j = 1, 2, ..., n.

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

, (6.20)

, i = 1, 2, ..., m, (6.21)

, j = 1, 2, ..., n, (6.22)

, i = 1, 2, ..., m+1; j = 1, 2, ..., n. (6.23)

Для того чтобы задача имела решение, необходимо и достаточно, чтобы

.

Отсюда получаем

.

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

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

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

Порядок решения транспортных задач методом потенциалов следующий:

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

2. Строят начальное опорное решение (методом минимальной стоимости или каким-либо другим методом) и проверяют правильность его построения, для чего подсчитывают количество занятых клеток (их должно быть m + n -1) и убеждаются в линейной независимости векторов-условий (методом вычеркивания).

3. Строят систему потенциалов, соответствующих опорному решению. Для этого решают систему уравнений

при .

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

при , (6.24)

если известен потенциал , и

при , (6.25)

если известен потенциал .

4. Проверяют, выполняется ли условие оптимальности для свободных клеток таблицы. Для этого вычисляют оценки для всех свободных клеток по формуле

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

5. Переходят к новому опорному решению, на котором значение целевой функции будет меньше. Для этого находят клетку таблицы задачи, которой соответствует наибольшая положительная оценка

.

Строят цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. В клетках цикла расставляют поочередно знаки "+" и "-", начиная с "+" в клетке с наибольшей положительной оценкой. Осуществляют сдвиг (перераспределение груза) по циклу на величину . Клетка со знаком "-", в которой достигается остается пустой. Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным m + n - 1.

Далее возвращаются к пункту 3 алгоритма.

Пример 6.5. Решить транспортную задачу, исходные данные которой приведены в табл. 6.13.

Т а б л и ц а 6.13

Решение. 1. Проверяем выполнение необходимого и достаточного условия разрешимости задачи. Находим суммарные запасы поставщиков и запросы потребителей

, .

Задача с неправильным балансом. Вводим четвертого, фиктивного поставщика с запасами = 800 – 600 = 200 и нулевыми стоимостями перевозки единиц груза (табл. 6.14).

2. Составляем начальное опорное решение методом минимальной стоимости (табл. 6.14).

Т а б л и ц а 6.14

Записываем матрицу стоимостей С. Находим в этой матрице наименьшие на каждом шаге стоимости и направляем в клетку, которая соответствует этим стоимостям, максимально допустимые объемы перевозок грузов.

При этом исключаем на каждом шаге одного поставщика или потребителя. Кружочками в матрице С указаны минимальные элементы, а цифрами рядом со строками и столбцами - порядок исключения из рассмотрения поставщиков и потребителей. Напомним, что запасы фиктивного поставщика вывозятся в последнюю очередь.

Полученное решение имеет m + n - 1 = 4 + 4 -1 = 7 базисных переменных. Опорное решение является вырожденным, так как одна из его координат равна нулю. Вычислим значение целевой функции на этом опорном решении = 100 × 1 + 0 × 2 + 100 × 3 + 100 × 4 + 200 × 7 + 100 × 12 + 200 × 0 = 3400.

3. Для проверки оптимальности опорного решения необходимо найти потенциалы. По признаку оптимальности в каждой занятой опорным решением клетке таблицы транспортной задачи сумма потенциалов равняется стоимости ( при ). Записываем систему уравнений для нахождения потенциалов

Система состоит из семи уравнений и имеет восемь переменных. Система неопределенная. Одному из потенциалов задаем значение произвольно: пусть = 0. Остальные потенциалы находятся однозначно

= 0;

= 2 – 0 = 2;

= 3 – 0 = 3;

= 4 – 0 = 4;

= 1 – 2 = –1;

= 7 – 4 = 3;

= 12 – 3 = 9;

= 0 – 9 = – 9.

Значения потенциалов записываем рядом с запасами или запросами соответствующих поставщиков и потребителей в таблицу
(табл. 6.15).

Система уравнений для нахождения потенциалов достаточно проста, обычно ее решают устно, глядя на таблицу задачи, ее занятые клетки и известные потенциалы. Любой неизвестный потенциал, соответствующий занятой клетке, равен находящейся в этой клетке стоимости, минус известный потенциал, соответствующий этой же клетке (6.24), (6.25).

Т а б л и ц а 6.15

4. Проверяем опорное решение на оптимальность. С этой целью вычисляем оценки для всех незаполненных клеток таблицы (для всех занятых клеток = 0)

.

Положительные оценки записывают в левые нижние углы соответствующих клеток таблицы, вместо отрицательных просто ставим знак "–".

Начальное опорное решение не является оптимальным, так как имеются положительные оценки.

5. Переходим к новому опорному решению. Находим клетку таблицы, которой соответствует наибольшая положительная оценка. Имеем max {7, 3, 2, 2} =7 для клетки (1, 4). Для этой клетки строим цикл. Ставим в нее знак "+", присоединяем ее к занятым клеткам и применяем метод вычеркивания. После проведения вычеркиваний в таблице остаются только образующие цикл клетки. Цикл изображен в табл. 6.15. На основании теоремы 6.6 такой цикл единственный. В угловых точках цикла расставляются поочередно знаки "+" и "-", начиная с "+" в клетке (1, 4). В клетки, отмеченные знаком "+" добавляется груз q, а из клеток, отмеченных знаком минус, вычитается такой же по величине груз. Определяем величину груза q, перераспределяемого по циклу. Она равняется значению наименьшей из перевозок в клетках цикла, отмеченных знаком "–" {100, 100, 100} = 100. Осуществляем сдвиг по циклу на величину q = 100. Получаем второе опорное решение (табл. 6.16). Т а б л и ц а 6.16

В данном случае минимум перевозок в клетках, отмеченных знаком "–" достигался сразу в трех клетках, поэтому для того, чтобы число занятых клеток опорного решения было по-прежнему равно
m + n - 1 = 7, в клетки с номерами (1, 1) и (2, 3) поставлены нулевые базисные перевозки. Следует освобождать клетку с большей стоимостью перевозки, т. е. клетку (3, 4).

Вычисляем значение целевой функции на втором опорном решении

= 0 × 1 + 100 × 1 + 100 × 2 + 100 × 3 + 0 × 4 + 300 × 7 + 200 × 0 = 2700.

6. Проверяем второе опорное решение на оптимальность. Находим потенциалы и оценки. Они приведены в табл. 6.16. Решение не является оптимальным, так как имеются положительные оценки = 2, = 2, = 1 и = 2. Наибольшая из них равняется 2 одновременно для трех клеток (3, 1), (3, 2), (4, 3). В одну из них, пусть в клетку (3, 2), ставим знак "+". Для этой клетки строим цикл
(табл. 6.16), и находим величину груза для перераспределения по циклу: {100, 300} = 100. Осуществляем сдвиг по циклу на величину q = 100. Получаем третье опорное решение (табл. 6.17).

Т а б л и ц а 6.17

Вычисляем значение целевой функции на третьем опорном решении.

= 0×1 + 100×1 + 100×2 + 100×4 + 100×4 + 200×7 + 200×0 = 2500.

7. Проверяем третье опорное решение на оптимальность. Находим потенциалы и оценки. Они приведены в табл. 6.17. Решение не является оптимальным, так как имеются положительные оценки = 2 и = 2. В одну из клеток с положительной оценкой, пусть в клетку (3, 1), ставим знак "+". Для этой клетки строим цикл (см. табл. 6.17) и находим величину груза для перераспределения по циклу {100, 200} = 100. Осуществляем сдвиг по циклу на величину q = 100. Получаем четвертое опорное решение (табл. 6.18).

Таблица 6.18

Вычисляем значение целевой функции на четвертом опорном решении = 0×1 + 100×1 + 200×4 + 100×3 + 100×4 + 100×7 + 200×0 = 2300.

8. Проверяем решение на оптимальность. Находим потенциалы и оценки. Они приведены в табл. 6.18. Положительными являются оценки = 2, = 1 и = 4. Для клетки (4, 3), которой соответствует наибольшая оценка, строим цикл (табл. 6.18) и находим величину груза для перераспределения по циклу {200, 0,
100} = 0. Осуществляем сдвиг по циклу на величину q = 0. Получаем пятое опорное решение (табл. 6.19).

Т а б л и ц а 6.19

Решение является оптимальным, так как все оценки отрицательные. Значение целевой функции = = 2300.

Ответ: minZ(X) = 2300 при .

Транспортная задача с ограничениями
на пропускную способность

Пусть требуется при решении транспортной задачи ограничить перевозки от поставщика с номером l к потребителю с номером k. Возможны ограничения двух типов: 1) ; 2) , где a и b – постоянные величины.

1. Если , то необходимо прежде, чем решать задачу, сократить (уменьшить) запасы l-го поставщика и запросы k-го потребителя на величину a (зарезервировать перевозку ). После решения задачи в оптимальном решении следует увеличить объем перевозки на величину a.

2. Если , то необходимо вместо k-го потребителя с запросами ввести двух других потребителей. Один из них с номером k должен иметь запросы , а другой с номером n + 1 – запросы . Стоимости перевозок для этих потребителей остаются прежними, за исключением стоимости , которая принимается равной сколь угодно большому числу М (M >> 1). После получения оптимального решения величины грузов, перевозимых к (n + 1)-му потребителю, прибавляются к величинам перевозок k-го потребителя. Так как - самая большая стоимость перевозки, то в оптимальном решении клетка с номером (l, n+1) остается пустой и объем перевозки не превзойдет b.

Пример 6.6. Решить транспортную задачу, исходные данные которой приведены в табл. 6.20 при дополнительных условиях: объем перевозки груза от 1-го поставщика 2-му потребителю должен быть не менее 100 единиц ( ), а от 3-го 1-му не более 200 единиц ( ).

Т а б л и ц а 6.20

Решение. Для того чтобы в оптимальном решении объем перевозки был не менее 100 единиц, при решении задачи будем предполагать, что запасы 1-го поставщика и запросы 2-го потребителя меньше фактических на 100 единиц. После получения оптимального решения объем перевозки увеличим на 100 единиц.

Для того чтобы удовлетворить требованию , вместо 1-го потребителя введем двух других. Один из них под прежним первым номером имеет запросы = 200 единиц и прежние стоимости перевозок единиц груза. Другому присвоим 4-й номер. Его запросы равны = 500 -200 = 300 единиц и стоимости перевозок единиц груза те же, что и у 1-го потребителя, за исключением , которую примем равной сколь угодно большому числу М, т. е. = М. После нахождения оптимального решения задачи объемы перевозок для 4-го потребителя необходимо прибавить к соответствующим объемам перевозок для 1-го потребителя.

В результате указанных преобразований таблица исходных данных задачи будет иметь следующий вид (табл. 6.21).

Т а б л и ц а 6.21

				М

Далее задачу решаем обычным методом потенциалов. Проверяем выполнение необходимого и достаточного условий существования решения задачи. Находим суммарные запасы поставщиков и запросы потребителей.

= 100 + 300 + 500 = 900;

= 200+300+300+300 = 1100.

Задача с неправильным балансом. Вводим фиктивного поставщика с запасами = 1100 - 900 = 200 (табл. 6.22).

Составляем начальное опорное решение методом минимальной стоимости. Записываем матрицу стоимостей С. Кружочками в матрице С отмечены минимальные элементы, а цифрами рядом со строками и столбцами - порядок исключения из рассмотрения поставщиков и потребителей.

Т а б л и ц а 6.22

Полученное решение имеет m + n - 1 = 4 + 4 -1 = 7 базисных переменных. Вычислим значение целевой функции на этом опорном решении

= 100 × 1 + 100 × 2 + 200 × 2 + 300 × 7 + 200 × 8 + 100 × 0 + 100 × 0 = 4400.

Для проверки оптимальности опорного решения находим потенциалы. Записываем систему уравнений для нахождения потенциалов и решаем ее:

Система состоит из семи уравнений и имеет восемь переменных. Так как число неизвестных на единицу больше числа уравнений, то одному из потенциалов можно задать значение произвольно: пусть = 0. Остальные потенциалы однозначно находятся из системы уравнений

= 1 – 0 = 1;

= 2 – 1 = 1;

= 2 – 1 = 1;

= 0 – 1 = –-1;

= 0 – (–1) = 1;

= 8 – 1 = 7;

= 7 – 7 = 0.

Значения потенциалов приведены в табл. 6.22. Находим оценки для свободных клеток таблицы:

= 0 + 0 - 5 = -5 < 0;

= 0 + 1 - 6 = - 5 < 0;

= 0 + 1 - 1 = 0;

= 1 + 0 - 6 = -5 < 0;

= 1 + 1 - 7 = - 5 < 0;

= 7 + 1 - 3 = 5 > 0;

= 7 + 1 - M = < 0;

= -1 + 1 - 0 = 0;

= -1 + 0 - 0 = -1 < 0.

Опорное решение неоптимальное, так как имеется положительная оценка = 5 для клетки (3, 1). Отмечаем эту клетку знаком "+". Находим цикл для улучшения опорного решения (табл. 6.22). Определяем величину груза для перераспределения по циклу {100, 200, 100} = 100. Осуществляем сдвиг по циклу на величину q = 100. Получаем второе опорное решение (табл. 6.23).

Т а б л и ц а 6.23

В табл. 6.23 также записаны потенциалы и оценки для свободных клеток. Решение оптимальное, так как все оценки неположительные. Запишем оптимальное решение исходной задачи. Для этого увеличим объем перевозки на 100 единиц и объединим объемы перевозок 4-го потребителя с объемами перевозок 1-го потребителя. Получим

.

Вычислим значение целевой функции на этом решении

= 100 × 1 + 100 × 5 + 300 × 2 + 100 × 3 + 300 × 7 + 100 × 8 = 4400.

Ответ: min Z(X) = 4400 при .

В некоторых задачах требуется запретить перевозки от отдельных поставщиков отдельным потребителям. В таких случаях либо зачеркивают клетку таблицы транспортной задачи, либо назначают соответствующую этой клетке стоимость перевозки единицы груза сколь угодно большой, равной M >> 1. В остальном задача решается обычным способом. Для разрешимости данной задачи необходимо существование начального опорного решения.