Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Транспортная задача.
Постановка задачи и математическая модель.
Предположим, что существуют N потребителей и M поставщиков некоторого однородного груза, у каждого из поставщиков определенный запас этого груза (Ai единиц, i=1,2,…,M), а каждому из потребителей требуется Bj единиц груза (j=1,2,…, N). Известны также затраты cij на перевозку единицы груза от поставщика Ai к потребителю Bj. Требуется составить такой план перевозок от поставщиков к потребителям, чтобы суммарные затраты на перевозки оказались минимальными (при этом должны быть по возможности вывезены все запасы поставщиков и удовлетворены все запросы потребителей).
В случае, когда суммарные запасы совпадают с суммарными запросами, задача называется задачей с правильным балансом, а ее модель - закрытой. В противном случае говорят о задаче с неправильным балансом и об открытой модели. Существуют специальные приемы приведения открытой модели к закрытой (они будут рассмотрены позже).
Данные транспортной задачи обычно записываются в виде таблицы, заголовки строк которой содержат информацию о запасах, заголовки столбцов – информацию о запросах, а в нижнем правом углу каждой ячейки указывается стоимость перевозки единицы груза (затраты на перевозку единицы груза).
При составлении математической модели через xij обозначается количество единиц груза, который будет перевезен от поставщика Ai к потребителю Bj (объем перевозок от Ai к Bj). Эти значения будут вноситься в центр соответствующей ячейки.
С учетом сказанного целевая функция принимает вид
(просуммированы все произведения затрат на соответствующий объем перевозок). Ограничения связаны с вывозом запасов и удовлетворением запросов, поэтому математическая модель имеет вид:
|
Пример 1. Транспортная задача задана с помощью таблицы 1, из которой видно, что на складах трех поставщиков A1, A2, A3 сосредоточены соответственно 30, 190 и 250 единиц груза, потребители B1, B2, B3, B4 нуждаются соответственно в 70, 120, 150, 130 единицах груза, а стоимости перевозок указаны непосредственно в таблице. |
В А 70 120 150 130 30 4 7 2 3 190 3 1 2 4 250 4 6 3 7 Таблица 1. |
Заметим, что суммарные запасы (30+190+250=470) равны суммарным запросам (70+120+150+130=470). Разместим в основной (незаштрихованной) части таблицы искомые объемы перевозок xij и перейдем к составлению математической модели. Заметим, что нумерация соответствует привычной нумерации элементов в матрицах (i – номер строки, j – номер столбца). Итак, целевая функция принимает вид
(1)
(просуммировали произведения стоимостей на объемы перевозок по всем строкам). При построении системы ограничений сначала суммируем объемы перевозок по каждому столбцу (удовлетворяем все запросы), а потом суммируем объемы перевозок по каждой строке (вывозим все запасы). Учтем также неотрицательность значений xij и получаем следующие условия:
(2)
Итак, мы построили математическую модель предложенной задачи с целевой функцией (1) и системой ограничений (2).
Транспортная задача сводится к задаче линейного программирования, однако для ее решения существуют специальные алгоритмы. При этом сначала задача сводится к закрытой, затем строится начальное решение, а затем оно оптимизируется с помощью метода потенциалов. В связи с этим всюду далее алгоритмы излагаются в общем виде для закрытой задачи.
Построение начального опорного решения.
Рассмотрим два основных приема для задач с правильным балансом. Первый из них имеет более простой алгоритм, а второй дает решение, более близкое к оптимальному.
Метод северо-западного угла. Основная идея заключается в том, вычисление значений xij начинается с верхней левой клетки (северо-западный угол таблицы). Из значений запасов и запросов, ей соответствующих (A1 и B1) выбираем минимальное – это и будет объем перевозок x11. При этом либо удовлетворены все запросы (и тогда из рассмотрения исключается потребитель, при этом в таблице в оставшихся ячейках соответствующего столбца ставятся прочерки, а объем запасов в соответствующей строке уменьшается на это значение), либо вывезены все запасы (из рассмотрения исключается поставщик, прочерки ставятся в строке и уменьшается объем запросов). В случае, когда A1=B1, вычеркивается либо строка, либо столбец (но не строка и столбец одновременно!) Далее действия повторяются со следующей ячейкой, которая оказалась верхней левой – и так до момента, пока не окажется, что все запасы вывезены, а все запросы удовлетворены. При этом клетки, в которые попали значения xij,, называются занятыми.
Внимание! Во избежание ошибок необходимо убедиться в том, что число занятых клеток равно M+N-1; в противном случае построенное начальное решение не будет опорным. При этом необходимо помнить, что, в силу сформулированного правила выбора объема перевозок, в занятых клетках могут оказаться значения, равные нулю!
Пример 2. Ниже в таблицах 2-7 приводится пошаговое построение методом северо-западного угла начального опорного решения для закрытой задачи из примера 1; объемы перевозок внесены в таблицы жирным курсивным шрифтом.
|
В А 70 120 150 130 30 30 4 - 7 - 2 - 3 190 3 1 2 4 250 4 6 3 7 Таблица 2. |
В А 70 120 150 130 30 30 4 - 7 - 2 - 3 190 40 3 1 2 4 250 - 4 6 3 7 Таблица 3. |
|
В А 70 120 150 130 30 30 4 - 7 - 2 - 3 190 40 3 120 1 2 4 250 - 4 - 6 3 7 Таблица 4. |
В А 70 120 150 130 30 30 4 - 7 - 2 - 3 190 40 3 120 1 30 2 - 4 250 - 4 - 6 3 7 Таблица 5 |
|
В А 70 120 150 130 30 30 4 - 7 - 2 - 3 190 40 3 120 1 30 2 - 4 250 - 4 - 6 120 3 7 Таблица 6. |
В А 70 120 150 130 30 30 4 - 7 - 2 - 3 190 40 3 120 1 30 2 - 4 250 - 4 - 6 120 3 130 7 Таблица 7. |
Итак, заняты 6 ячеек: (1;1), (2;1), (2;2), (2;3), (3;3) и (3;4) (здесь, как и всюду далее, в «адресе» ячейки первым указан номер строки, вторым – номер столбца, заголовки в нумерации не учитываются). Количество занятых ячеек совпадает с числом M+N-1=3+4-1=6. Мы построили начальное опорное решение X1, остается найти значение целевой функции для этого опорного решения (в свободных клетках, т.е. клетках с прочерками, значение объема перевозок считается равным нулю и потому на результат вычисления не влияет): .
Метод минимальной стоимости. Основная идея этого подхода - последовательная расстановка объемов перевозок в клетки с наименьшей стоимостью среди незаполненных. В случае, когда есть несколько клеток с одинаковой стоимостью, первой рассматривается та, в которую можно записать наибольший объем перевозок. Правило выбора значения из соответствующих запаса и запроса сохраняется, как сохраняется и обязательное количество занятых строк, и возможность появления в занятой клетке нулевого значения.
Пример 3. В таблицах 8-13 приводится пошаговое построение начального опорного решения методом минимальной стоимости для закрытой задачи из примера 1. Обратите внимание, что первый выбор сделать легко, а в таблице 8 видно, что в ячейках (2;3) и (1;3) одинаковая стоимость затрат (равная 2). Поскольку в ячейку (2;3) можно записать объем перевозок, равный 70, а в ячейку (1;3) – равный 30, выбираем ячейку с большим объемом, т.е. (2;3) – см. таблицу 9.
|
В А 70 120 150 130 30 4 - 7 2 3 190 3 120 1 2 4 250 4 - 6 3 7 Таблица 8. |
В А 70 120 150 130 30 4 - 7 2 3 190 - 3 120 1 70 2 - 4 250 4 - 6 3 7 Таблица 9. |
|
В А 70 120 150 130 30 - 4 - 7 30 2 - 3 190 - 3 120 1 70 2 - 4 250 4 - 6 3 7 Таблица 10. |
В А 70 120 150 130 30 - 4 - 7 - 2 - 3 190 - 3 120 1 70 2 - 4 250 4 - 6 50 3 7 Таблица 11 |
|
В А 70 120 150 130 30 - 4 - 7 30 2 - 3 190 - 3 120 1 70 2 - 4 250 70 4 - 6 50 3 7 Таблица 12. |
В А 70 120 150 130 30 - 4 - 7 30 2 - 3 190 - 3 120 1 70 2 - 4 250 70 4 - 6 50 3 130 7 Таблица 13 |
В итоге, как и положено, построенному начальному опорному решению X2 соответствуют 6 занятых клеток. При этом значение целевой функции меньше, чем найденное в примере 2, т.е. решение X2 ближе к оптимальному.
Открытую модель необходимо сначала свести к закрытой, для чего вводится фиктивный поставщик (с запасами, равными разности между запасами и запросами) или фиктивный потребитель (с аналогично определяемыми запросами). Стоимости перевозок в соответствующих строке или столбце равны нулю, но в методе минимальной стоимости они учитываются в последнюю очередь. В ответе фиктивная строка (столбец) не учитывается.
|
Пример 4. Для предложенной транспортной задачи (таблица 14) составить начальные опорные решения методами северо-западного угла и минимальной стоимости и сравнить значения целевой функции. |
В А 30 60 30 1 3 20 2 5 50 4 2 Таблица 14 |
Решение. Прежде всего очевидно, что суммарные запасы равны 100, а суммарные запросы – 90. Поэтому необходимо ввести фиктивного потребителя, запросы которого равны 10 (это дополнительный столбец, значения стоимостей в котором будут равны 0) – см. таблицу 15, с которой начнем построение начального решения методом северо-западного угла. На первом шаге для ячейки (1;1) значения запасов и запросов одинаковы и равны 30, поэтому объема перевозок равен 30, вычеркиваем, например, строку (при этом запросы в соответствующем столбце становятся равными 0). На следующем шаге (см. таблицу 16) в ячейку (2;1) ставится значение объема перевозок 0 – как минимальное из чисел 0 и 20, при этом вычеркивается первый столбец.
|
В А 30 60 10 30 30 1 - 3 - 0 20 2 5 0 50 4 2 0 Таблица 15. |
В А 30 60 10 30 30 1 - 3 - 0 20 0 2 5 0 50 - 4 2 0 Таблица 16. |
|
В А 30 60 10 30 30 1 - 3 - 0 20 0 2 20 5 - 0 50 - 4 2 0 Таблица 17. |
В А 30 60 10 30 30 1 - 3 - 0 20 0 2 20 5 - 0 50 - 4 40 2 0 Таблица 18. |
|
В А 30 60 10 30 30 1 - 3 - 0 20 0 2 20 5 0 50 - 4 40 2 10 0 Таблица 19. |
При получении таблиц 17-19 действовали по стандартной схеме. Занятыми оказались, как и положено, 5 клеток (3+3-1=5), остается найти значение целевой функции для найденного опорного решения: |
Проведем теперь построение начального опорного решения методом минимальной стоимости (таблицы 20-24).
|
В А 30 60 10 30 30 1 - 3 - 0 20 2 5 0 50 4 2 0 Таблица 20. |
В А 30 60 10 30 30 1 - 3 - 0 20 2 5 0 50 - 4 50 2 - 0 Таблица 21. |
|
В А 30 60 10 30 30 1 - 3 - 0 20 0 2 5 0 50 - 4 50 2 - 0 Таблица 22. |
В А 30 60 10 30 30 1 - 3 - 0 20 0 2 10 5 0 50 - 4 50 2 - 0 Таблица 23. |
|
В А 30 60 10 30 30 1 - 3 - 0 20 0 2 10 5 10 0 50 - 4 50 2 - 0 Таблица 24. |
Опять заняты 5 клеток, находим значение целевой функции для найденного опорного решения: Замечание. При записи ответа (начального опорного решения) последние столбцы в таблицах 19 и 24 не учитываются. |
Проверка оптимальности решения. Метод потенциалов.
Для проверки оптимальности решения введем потенциалы строк (ui, i=1,2,…,M) и столбцов (vj, j=1,2,…,N) – числа, которые определяются системой уравнений , составленных по занятым клеткам. Заметим, что занятых клеток M+N-1, поэтому мы имеем систему из M+N-1 уравнений с M+N неизвестными потенциалами. Это неопределенная система, нас интересует любое частное решение, поэтому любому из потенциалов можно на первом шаге дать значение, равное нулю. Далее последовательно находятся все потенциалы, которые записываются в дополнительный правый столбец и в дополнительную нижнюю строку таблицы транспортной задачи (общую схему см. в таблице 25).
|
B A |
B1 |
B2 |
… |
BM |
Потенциалы строк |
|
A1 |
с11 |
с12 |
… |
с1N |
u1 |
|
A2 |
с21 |
с22 |
… |
с2N |
u2 |
|
… |
… |
… |
… |
… |
… |
|
AM |
сM1 |
сM2 |
cMN |
uM |
|
|
Потенциалы столбцов |
v1 |
v2 |
… |
vN |
Таблица 25
После определения потенциалов находим оценки для свободных клеток по правилу , записываем их в верхнюю часть каждой свободной клетки. Решение является оптимальным, если все найденные оценки неположительны (меньше или равны 0).
Пример 5. Проверить оптимальность решения, построенного в примере 4 (см. таблицу 24).
Решение. Сначала по таблице 24 определяем потенциалы.
|
Занятыми являются клетки (1;1), (2;1), (2;2), (2;3), (3;2). С учетом стоимостей, записанных в этих клетках, составляем систему уравнений |
В А 30 60 10 ui 30 30 1 - 3 - 0 0 20 0 2 10 5 10 0 1 50 - 4 50 2 - 0 -2 vj 1 4 -1 Таблица 26. |
Пусть . Далее последовательно: из первого уравнения , из второго уравнения , из третьего , из четвертого , из пятого . Результаты собраны в таблице 26.
Расчет оценок проводится по формуле непосредственно в таблице 27, с учетом найденных выше потенциалов
|
В А |
30 |
60 |
10 |
ui |
|
30 |
30 1 |
0+4-3=1>0 - 3 |
0+(-1)-0=-1<0 - 0 |
0 |
|
20 |
0 2 |
10 5 |
10 0 |
1 |
|
50 |
-2+1-4=-5<0 - 4 |
50 2 |
-2+(-1)-0=-3<0 - 0 |
-2 |
|
vj |
1 |
4 |
-1 |
Таблица 27.
Итак, видно, что в ячейке (1;2) оценка положительна, т.е. предложенное решение не является оптимальным.
Оптимизация решения.
Одним из основных понятий в этом пункте является цикл – последовательность клеток таблицы транспортной задачи, в которой две и только две соседние клетки расположены в одной строке или в одном столбце, причем первая и последняя клетки также находятся в одной строке или в одном столбце. Известно, что в таблице транспортной задачи, содержащей опорное решение, для любой свободной клетки можно построить единственный цикл, содержащий эту клетку и часть занятых.
Если решение не оптимальное, то среди положительных оценок выбираем наибольшую (в случае равенства наибольших оценок – выбираем ячейку с наименьшей стоимостью). Для выбранной ячейки строим цикл, включающий эту клетку и часть занятых клеток, причем свободная клетка получает знак «+», а далее знак чередуется. Для попавших в цикл ячеек определяем величину
.
Перемещаем перевозки по циклу в соответствии с правилом: в ячейках со знаком «+» добавляется к значению xij, а в ячейках со знаком «-» из xij вычитается. При этом клетка, в которой изначально находился объем перевозок, равный , становится пустой, а свободная с выбранной «плохой» оценкой - занятой.
Замечание. Если минимальное значение достигается в нескольких клетках, то только одна из них становится пустой, а в остальных объем перевозок выставляется равным 0; это позволяет сохранить необходимое количество занятых клеток.
После перемещения груза по циклу новое решение проверяется на оптимальность, и в случае необходимости процесс повторяется.
Пример 6. Найти оптимальное решение для транспортной задачи из примера 4.
Решение. Условия были приведены в таблице 14. Задача была открытой, поэтому сначала был введен фиктивный потребитель. Начальное опорное решение, построенное методом минимальной стоимости – в таблице 24. Таблица 27 (с потенциалами и оценками) свидетельствует, что построенное решение не оптимальное, а ячейка (1;2) – единственная ячейка с положительной оценкой. С нее и начнем строить цикл. По таблице 27 видно, что его образуют ячейки (1;2), (2;2), (2;1), (1;1). В силу сказанного выше ячейки
|
В А 30 60 10 30 20 1 10 3 - 0 20 10 2 - 5 10 0 50 - 4 50 2 - 0 Таблица 28. |
(1;2) и (2;1) будут иметь знак «+», ячейки (2;2) и (1;1) – знак «». Объем перевозок в ячейке (2;2) равен 10, в ячейке (1;1) 30, минимальное значение =10. Таким образом, в ячейках (1;2) и (2;1) объем перевозок будет увеличен на 10, а в ячейках (2;2) и (1;1) уменьшен на 10, при этом ячейка (2;2) освободится. Новое опорное решение приведено в таблице 28. |
Проверим оптимальность этого плана. По занятым клеткам составим систему уравнений для определения потенциалов и решим ее, полагая . Затем запишем потенциалы (см. таблицу 29) и в этой же таблице высчитаем оценки свободных клеток.
|
В А |
30 |
60 |
10 |
ui |
|
30 |
20 1 |
10 3 |
0+(-1)-0<0 - 0 |
0 |
|
20 |
10 2 |
1+3-5<0 - 5 |
10 0 |
1 |
|
50 |
-1+1-4<0 - 4 |
50 2 |
-1+(-1)-0<0 - 0 |
-1 |
|
vj |
1 |
3 |
-1 |
Таблица 29.
Все оценки отрицательны, значит, найденное опорное решение является оптимальным. Для завершения решения отбрасываем столбец с фиктивным
|
В А 30 60 30 20 1 10 3 20 10 2 - 5 50 - 4 50 2 Таблица 30. |
потребителем, записываем итоговую таблицу 30, соответствующую исходному условию, и находим для построенного оптимального плана значение целевой функции: Заметим, что на втором складе осталось 10 единиц продукции, но это связано с тем, что задача была открытой. |
Алгоритм полного решения транспортной задачи.
Подводя итог сказанному выше, определим порядок действий при решении транспортной задачи с M поставщиками и N потребителями.
1) Определить, является ли задача закрытой или открытой; в последнем случае ввести фиктивного потребителя или поставщика и построить новую таблицу.
2) Построить начальное опорное решение X1 (рекомендуется метод минимальной стоимости) и убедиться, что занято необходимое число клеток (M+N-1).
3) Найти потенциалы с помощью занятых клеток из неопределенной системы ((i;j) – адреса занятых клеток), а затем – оценки для свободных клеток (здесь (i;j) – адреса свободных клеток).
4) В случае, когда все оценки , опорный план является оптимальным, и остается найти значение целевой функции f(X1). Если же среди оценок оказались положительные, то выбираем ячейку с наибольшей положительной оценкой, строим для нее цикл и переходим к новому опорному решению X2. При этом должно выполняться неравенство f(X2) f(X1). Затем возвращаемся к п. 3) алгоритма.
5.6. Транспортная задача с ограничениями. Значительное количество экономических задач (порой не имеющих ничего общего с транспортировкой грузов) могут быть сведены к модели транспортной задачи. При этом величины cij могут означать стоимость, расстояние, время, производительность (см., например, [4, раздел D, п.6.14]). В то же время в самой транспортной задаче возникают различные ограничения (например, по критерию времени, при наличии особо важного потребителя – в открытой задаче это означает, что его запросы должны быть удовлетворены полностью). Ниже для примера рассматривается ситуация, когда вводятся ограничения на пропускную способность. При этом необходимо учитывать следующие правила.
Правило 1 (для ограничения ). Перед решением задачи необходимо уменьшить запасы i-го поставщика и запросы j-го потребителя на величину a (резервируется перевозка ). После решения задачи в оптимальном плане найденный объем перевозок увеличивается на величину a.
Правило 2 (для ограничения ). Перед решением задачи необходимо вместо j-го потребителя ввести двух потребителей. Первый, с номером j, будет иметь запрос a, второй, с номером N+1 (в таблицу добавляем новый, последний столбец) будет иметь запрос Bj-a. Стоимости в новом столбце совпадут с исходными за исключением i-й строки (в ней стоимость принимается равной сколь угодно большому положительному числу – это обеспечивает «не появление в ней перевозок»). После решения задачи в оптимальном плане объемы перевозок j-го и N+1-го потребителей суммируются.
|
Пример 5.7. Решить транспортную задачу с таблицей 5.31 и ограничениями: , |
В А 100 50 50 50 1 2 4 70 3 5 1 80 2 6 3 Таблица 5.31 |
Решение. Задача изначально является закрытой (и запасы, и запросы равны 200). В соответствии со сказанным выше запасы во второй строке и запросы в первом столбце уменьшаются на 30 (учтено условие ). Далее во втором столбце запросы остаются равными 40, а мы достраиваем новый столбец с запросами 50-40=10. Стоимости в этом столбце совпадут с исходными, кроме ячейки в первой строке, куда запишем сколь угодно большое положительное число M. В результате нам нужно будет решать обычным способом (см. п. 5.5) транспортную задачу с таблицей 5.32. В таблице 5.33 приводится ее начальное опорное решение, найденное методом минимальной стоимости (читатель может провести построение сам).
|
В А 70 40 50 10 50 1 2 4 М 40 3 5 1 5 80 2 6 3 6 Таблица 5.32 |
В А 70 40 50 10 50 50 1 2 4 М 40 3 5 40 1 5 80 20 2 40 6 10 3 10 6 Таблица 5.33 |
При нахождении потенциалов удобно считать, что . Тогда оставшиеся значения быстро находятся из системы уравнений (по занятым клеткам)
|
В А |
70 |
40 |
50 |
10 |
ui |
|
50 |
50 1 |
6+(-1)-2=3>0 2 |
3+(-1)-4<0 4 |
6+(-1)-M<0 М |
-1 |
|
40 |
2+(-2)-3<0 3 |
6+(-2)-5<0 5 |
40 1 |
6+(-2)-5<0 5 |
-2 |
|
80 |
20 2 |
40 6 |
10 3 |
10 6 |
0 |
|
vj |
2 |
6 |
3 |
6 |
Таблица 5.34
Результаты вычислений, а также расчет оценок в свободных клетках приведены в таблице 5.34. В ней в ячейке (1;2) находится положительная оценка, значит, решение не оптимальное. Цикл для перехода будем строить, начиная с этой ячейки (других «кандидатов» просто нет). В цикл войдут ячейки (1;2), (3;2), (3;1), (1;1). При этом у ячеек (1;2) и (3;1) знак «+», у ячеек (3;2) и (1;1) знак «-». Из значений в «отрицательных» ячейках (50 и 40) наименьшее 40, это и будет перемещаемый объем перевозок .
|
|
В А 70 40 50 10 50 10 1 40 2 4 М 40 3 5 40 1 5 80 60 2 6 10 3 10 6 Таблица 5.35 |
|
В А |
70 |
40 |
50 |
10 |
ui |
|
50 |
10 1 |
40 2 |
3+(-1)-4<0 4 |
6+(-1)-M<0 М |
-1 |
|
40 |
2+(-2)-3<0 3 |
3+(-2)-5<0 5 |
40 1 |
6+(-2)-5<0 5 |
-2 |
|
80 |
60 2 |
3+0-6<0 6 |
10 3 |
10 6 |
0 |
|
vj |
2 |
3 |
3 |
6 |
Таблица 5.36
|
Итак, найденное решение оптимально (все оценки неположительны) – для задачи с таблицей 5.32. Теперь нужно вернуться к исходной задаче, в соответствии с правилами 1 и 2. Для этого объединим объемы перевозок из второго и четвертого столбца; запасы второй строки и запросы первого столбца увеличим на 30 (т.е. вернем в исходное состояние) и объем перевозок в ячейке (1;1) также увеличим на 30 (он был равен 0, поэтому получили 30). |
В А 100 50 50 50 10 1 40 2 4 70 30 3 5 40 1 80 60 2 10 6 10 3 Таблица 5.37 |
Оптимальный план исходной задачи дан в таблице 5.37 (обратите внимание, что за счет объединения столбцов и появления ненулевого объема перевозок в ячейке (2;1) количество занятых клеток больше числа N+M-1, равного в данной задаче 3+3-1=5). Итак, остается найти оптимальное значение целевой функции: .