2014-02-18
555
Таблица 24.
Таблица 23.
Таблица 22.
Таблица 21.
Таблица 20.
Таблица 19.
Таблица 18.
Таблица 17.
Таблица 16.
Таблица 15.
Таблица 13
Таблица 12.
Таблица 11
Таблица 10.
Таблица 9.
Таблица 8.
Таблица 7.
Таблица 6.
Таблица 5
Таблица 4.
Таблица 3.
Таблица 2.
Таблица 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; объемы перевозок внесены в таблицы жирным курсивным шрифтом.
|
| ||||||||||||||||||||||||||||||||||||||||
|
|
|
|
Итак, заняты 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.
|
|
|
|
|
|
В итоге, как и положено, построенному начальному опорному решению X2 соответствуют 6 занятых клеток. При этом значение целевой функции 
меньше, чем найденное в примере 2, т.е. решение X2 ближе к оптимальному.
Открытую модель необходимо сначала свести к закрытой, для чего вводится фиктивный поставщик (с запасами, равными разности между запасами и запросами) или фиктивный потребитель (с аналогично определяемыми запросами). Стоимости перевозок в соответствующих строке или столбце равны нулю, но в методе минимальной стоимости они учитываются в последнюю очередь. В ответе фиктивная строка (столбец) не учитывается.
|
|
|
| Пример 4. Для предложенной транспортной задачи (таблица 14) составить начальные опорные решения методами северо-западного угла и минимальной стоимости и сравнить значения целевой функции. |
|
Решение. Прежде всего очевидно, что суммарные запасы равны 100, а суммарные запросы – 90. Поэтому необходимо ввести фиктивного потребителя, запросы которого равны 10 (это дополнительный столбец, значения стоимостей в котором будут равны 0) – см. таблицу 15, с которой начнем построение начального решения методом северо-западного угла. На первом шаге для ячейки (1;1) значения запасов и запросов одинаковы и равны 30, поэтому объема перевозок равен 30, вычеркиваем, например, строку (при этом запросы в соответствующем столбце становятся равными 0). На следующем шаге (см. таблицу 16) в ячейку (2;1) ставится значение объема перевозок 0 – как минимальное из чисел 0 и 20, при этом вычеркивается первый столбец.
|
| ||||||||||||||||||||||||||||||||
|
| ||||||||||||||||||||||||||||||||
| При получении таблиц 17-19 действовали по стандартной схеме. Занятыми оказались, как и положено, 5 клеток (3+3-1=5), остается найти значение целевой функции для найденного опорного решения:
|
Проведем теперь построение начального опорного решения методом минимальной стоимости (таблицы 20-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 |
