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

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

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

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

shukaev143.wmf (3.1)

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

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

shukaev144.wmf

shukaev145.wmf i = 1, 2, …, m;

shukaev146.wmf j = 1, 2, …, n;

shukaev147.wmf

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

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

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

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

shukaev148.wmf i = 1, 2, …, m; j = 1, 2, …, n,

где

shukaev149.wmf

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

shukaev150.wmf

shukaev151.wmf

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

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

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

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

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

Таблица 3.1

c11

            x11

c12

             x12

...

c1n

       x1n

a1

c21

          x22

c22

         x22

...

c2n

       x2n

a2

...

...

...

...

...

cm1

          xm2

cm2

          xm2

...

cmn

        xmn

am

b1

b2

...

bn

 

 


Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074