Важный частный случай задач линейного программирования — транспортные задачи. Это математические модели разнообразных прикладных задач по оптимизации перевозок. Распространенность в приложениях задач транспортного типа оправдывает неослабевающее внимание к ним. Транспортные задачи решаются методом потенциалов, который является усовершенствованием симплекс-метода, примененного к данному более узкому типу задач. В этом параграфе мы приведем постановку транспортной задачи, методы отыскания исходной крайней точки, решение задачи методом потенциалов, двойственную к транспортной задаче, обоснование метода потенциалов, задачу о назначении, примеры.
Метод “Северо-западного угла”
Зададим транспортную задачу замкнутого типа в виде платежной матрицы.
Построим по методу “Северо-западного угла” первоначальный план перевозок. Назначим максимально возможную перевозку равную 10 из пункта отправления A1 в пункт назначения B1. То есть заполняем верхний левый элемент матрицы X первоначального плана перевозок. При этом из пункта отправления A1 весь груз окажется вывезенным. В пункт назначения B1 остается привести 30 единиц груза. В дальнейшем при нахождении первоначального плана перевозок выводим из рассмотрения первую строку матрицы 3 × 4 и рассматриваем только оставшуюся матрицу 2 × 4.
Назначим максимально возможную перевозку равную 30 из пункта отправления A2 в пункт назначения B1. То есть заполняем верхний левый элемент оставшейся матрицы X. При этом пункт назначения B1 окажется полностью обслуженным. В пункте отправления A2 останется 50 единиц груза. Выводим из рассмотрения первый столбец матрицы 2 × 4 и рассматриваем только оставшуюся матрицу 2 × 3.
Назначим максимально возможную перевозку равную 15 из пункта отправления A2 в пункт назначения B2. То есть заполняем верхний левый элемент оставшейся матрицы 2 × 3. При этом пункт назначения B2 окажется полностью обслуженным. В пункте отправления A2 останется 35 единиц груза. Выводим из рассмотрения первый столбец матрицы 2 × 3 и рассматриваем только оставшуюся матрицу 2 × 2.
Назначим максимально возможную перевозку равную 35 из пункта отправления A2 в пункт назначения B3. То есть заполняем верхний левый элемент матрицы 2 × 2. При этом из пункта отправления A2 весь груз оказался вывезенным. В пункт назначения B3 остается привезти 7 единиц груза, которые привозятся из пункта отправления A3. После этого в пункте отправления A3 остается 13 единиц груза, который перевозится в пункт назначения B4.
Для краткости в матрице плана перевозок не пишем нулевые значения небазисных перевозок. Число ненулевых элементов в первоначальном плане перевозок m + n − 1 = 3 + 4 − 1 = 6. Суммарная стоимость перевозок будет ⟨c, x ⟩ = 2 · 10 + 4 · 30 + 3 · 15 + 4 · 35 + 7 · 7 + 8 · 13 = 478.