Научная электронная библиотека

Монографии, изданные в издательстве Российской Академии Естествознания

Прикладные методы оптимизации

Шукаев Д. Н.,

3.1. Структура задачи и основные положения

Транспортная задача первоначально (1941) была поставлена американским ученым Ф. Хичкоком [60] и детально разобрана Т. Купмансом [65]. Формулировка ее как задачи линейного программирования и методы решения были даны Л.В. Канторовичем и М.К. Гавуриным [18].

Транспортной задачей называется линейная задача построения схемы перевозок между m заданными пунктами отправления, в которых находятся соответствующие количества однородных грузов ai (i = 1, 2, …, m) и n пунктами назначения, куда эти грузы должны быть доставлены соответственно в количестве bj, (j = 1, 2, …, n). Стоимость перевозки единицы продукции из i-го пункта отправления в j-й пункт назначения равна cij и известна для каждого из m×n возможных маршрутов. Задача заключается в определении таких величин xij для всех маршрутов, при которых суммарная стоимость перевозок была бы минимальной. Предполагается, что соблюдается условие баланса

(3.1)

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

Математическая модель закрытой транспортной задачи имеет следующий вид

i = 1, 2, …, m;

j = 1, 2, …, n;

x_ij ≥ 0, i = 1, 2, …, m; j = 1, 2, …, n.

Как видно из этой модели транспортная задача является задачей линейного программирования с m + n ограничениями и m×n переменными. Специфичная структура математической модели транспортной задачи позволили на основе детализации симплексного алгоритма построить более эффективные в вычислительном отношении методы. Учитывая прикладную направленность предлагаемой книги приведем без строгих доказательств ряд теорем, послуживших основой для разработки методов решения транспортной задачи.

Теорема 3.1. [9, 25] «Для любой закрытой транспортной задачи имеется решение».

Действительно приняв за решение задачи

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

где

видим, что ограничения задачи выполняются

Теорема 3.2. [9] «Если параметры ai и bj целые числа, то в любом решении базисные переменные целые числа».

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

Теорема 3.3. [9] «Для транспортной задачи существует решение, содержащее не более чем m + n – 1 положительных переменных».

Очевидность данного утверждения вытекает из того факта, что система ограничений транспортной задачи содержит m + n уравнений, которые не являются независимыми в силу условия (3.1), поэтому невырожденное базисное решение транспортной задачи содержит m + n – 1 положительных значений перевозок xij.

Процесс решения транспортной задачи удобно оформлять в виде последовательности табл. 3.1.

Таблица 3.1