Транспортная задача

Оглавление

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

Каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Не трудно выиграть сражение, имея армию в 10 раз большую, чем у противника. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Раньше план в таких случаях составлялся “на глазок”. В середине XX века был создан специальный математический аппарат, помогающий это делать “по науке”. Соответствующий раздел математики называется математическим программированием. По-русски лучше было бы употребить слово «планирование». С программированием для ЭВМ математическое программирование имеет лишь то общее, что большинство возникающих на практике задач математического программирования слишком громоздки для ручного счета, решить их можно только с помощью ЭВМ, предварительно составив программу1.

 Временем рождения  линейного программирования принято  считать 1939 г., когда была напечатана брошюра Леонида Витальевича Канторовича “Математические методы организации и планирования производства”.

Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Постановка задачи и ее математическая модель

 Транспортная задача — одна из наиболее распространенных задач математического программирования (обычно — линейного). В общем виде ее можно представить так: требуется найти такой план доставки грузов от поставщиков к потребителям, чтобы стоимость перевозки (или суммарная дальность, или объем транспортной работы в тонно-километрах) была наименьшей. Следовательно, дело сводится к наиболее рациональному прикреплению производителей к потребителям продукции (и наоборот).

Задача ставится следующим образом. Найти объемы перевозок для каждой пары "поставщик — потребитель " так, чтобы:

1) мощности всех поставщиков были реализованы;

2) опросы всех потребителей были удовлетворены;

3) суммарные затраты на перевозку были бы минимальны. 3

В исследовании операций под транспортной задачей обычно понимают задачу выбора плана перевозок некоторого товара (изделий, груза) от m источников (пунктов производства, поставщиков) к n стокам (станциям назначения, пунктам сбыта), обеспечивающего минимальные транспортные затраты. При этом предполагают, что:

а) мощность i-го источника (объем поставок товара от i-го источника) равна

б) мощность j-го стока (объем поставок товара к j-му стоку) равна

в) стоимость перевозки единицы товара (в условных денежных единицах) от i-го источника к j-му стоку равна - коэффициент затрат.

Далее под объемом товара будем понимать его количество в фиксированных единицах измерения.

Для математического описания транспортной задачи вводят переменные xij, обозначающие объемы поставок товара от i-го источника к j-му стоку. В этом случае — общий объем поставок товара от i-го источника, т.е. мощность этого источника; — общий объем поставок товара к j-му стоку, т.е. мощность этого стока; — суммарная стоимость перевозок товара от источников к стокам. Тогда система ограничений имеет вид:    

          

Особенности экономико-математической модели транспортной задачи:

• система ограничений есть система уравнений (т.е. транспортная задана в канонической форме);

• коэффициенты при переменных системы ограничений равны единице или нулю;

• каждая переменная входит в систему ограничений два раза.

Линейная функция в данном случае:

 

Математическая формулировка транспортной задачи в общей постановке будет следующей: на множестве неотрицательных (допустимых) решений системы ограничений (1), (2) найти решение

, при котором значение линейной функции (3) минимально.

С учетом этого рассматриваемая задача может быть представлена в следующем виде:

                                                                (4)

 

Произвольное допустимое решение системы ограничений (1), (2) назовем распределением поставок.

Целью транспортной задачи является обеспечение получения (доставки) продукции (товара) потребителю в нужное время и место при минимально возможных совокупных затратах трудовых, материальных, финансовых ресурсов.

Цель транспортной деятельности считается достигнутой при выполнении шести условий:

1. нужный товар;
2. необходимого качества;
3. в необходимом количестве доставлен;
4. в нужное время;
5. в нужное место;
6. с минимальными затратами.

Объектом изучения являются материальные и соответствующие им финансовые, информационные потоки, сопровождающие производственно-коммерческую деятельность.

Определение 1.

Всякое неотрицательное решение системы линейных уравнений (1), и (2), определяемое матрицей , называется планом транспортной задачи.

Определение 2.

План , , при котором функция принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Замечание 1. Один из важнейших теоретических результатов исследования операций может быть сформулирован следующим образом: если выполнены условия

 

то среди всех оптимальных решений транспортной задачи (4) по край ней мере одно оптимальное решение удовлетворяет условиям целочисленности. В дальнейшем условия  (5) выполнимы. Введение дополнительного ограничения

 

не может повлиять на оптимальное значение целевой функции.

Определение 3.

В исследовании операций полностью целочисленную задачу (4), (6) называют классической транспортной задачей.

Введем матрицу переменных модели (4), (6)

 

Для наглядности классическую транспортную задачу (4), (6) удобно представлять в виде таблицы 1, которую называют транспортной таблицей.

 

 

 

 

 

Таблица 1.

Пункт производства	Пункт потребления
	1	…	j	…	n	Поставки
1 … i … m	…   …	… … … … …	…   …	… … … … …	…   …	…   …
Спрос		…		…

Эта таблица соответствует матрице переменных модели , в которую добавлен один столбец (поставки) и одна строка (спрос), а в правой половине клетки, соответствующей каждому переменному , вписано соответствующее значение . 

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

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

 

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

Замечание 2. Затраты, связанные с производством единицы товара, как правило, не одинаковы для различных пунктов производства. В случае необходимости учета разности этих затрат при постановке транспортных задач следует включить эти величины в коэффициенты .

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

Замечание 4. В ряде случаев возникает необходимость учета ограничений, связанных с пропускной способностью той или иной ориентированной дуги сети, при постановке транспортной задачи

        (7)4

.

Транспортную задачу исследования операций при наличии ограничений пропускных способностей дуг (7) называют транспортной задачей с ограничениями по пропускной способности.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Модели транспортной задачи

2.1.  Закрытая модель транспортной задачи

 

Определение 5.

Если суммарная мощность поставщиков равна суммарной мощности потребителей, т е.

 

то такая транспортная задача называется закрытой.

 

Теорема 1. Любая транспортная задача, у которой суммарный объем запасов совпадает с суммарным объемом потребностей, имеет решение.

 

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

Доказательство. Пусть   = M > 0 . 

Тогда   величины  (i = 1,2,3, ... m; j = 1,2,3, ..., n)                                являются планом, так как они удовлетворяют системе ограничений

( 2 ) и ( 3 ) .

 Действительно, подставляя  значения  в  (2) и (3) , находим 

     = si ,

    = dj .

Выберем из значений  Cij  наибольшее  C¢ = max Cij и заменим в линейной функции ( 1 ) все коэффициенты  на C¢  тогда, учитывая ( 2 ) , получим 

   ,

Выберем из значений Cij  наименьшее C¢¢=min Cij и заменим в линейной функции все коэффициенты на C¢¢ ; тогда, учитывая ( 2 ) имеем

 

Объединяя два последних неравенства в одно двойное , окончательно получаем

¢¢¢,

т. е.  линейная функция ограничена на множестве планов транспортной задачи.

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