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

Федеральное агентство по образованию

ГОУ ВПО 

ВСЕРОССИЙСКИЙ ЗАОЧНЫЙ ФИНАНСОВО-ЭКОНОМИЧЕСКИЙ  ИНСТИТУТ

Факультет __________________

Специальность ___________________________ 
 
 

РЕФЕРАТ

по  дисциплине «Экономико-математические методы и прикладные модели»

на  тему: «Транспортная  задача» 
 
 

Выполнил:

Студент Курбатов Сергей Михайлович

Курс

Группа

Личное  дело

  Преподаватель 
 
 
 
 

Липецк  2012

СОДЕРЖАНИЕ 

1. Постановка транспортной  задачи. Транспортная  таблица 3

2. Сведение открытой  транспортной задачи  к закрытой 5

3. Первоначальный план  перевозок 5

3.1.Составление  первоначального  плана перевозок  с помощью метода  северо-западного  угла 6

3.2. Составление первоначального  плана перевозок  с помощью метода  наименьшей стоимости 7

4. Вырожденные планы.  Циклы и пополнение  плана 9

5. Проверка оптимальности  плана и перераспределение  поставок c помощью метода потенциалов 11

5.1. Вычисление потенциалов 11

5.2. Проверка оптимальности  плана 11

5.3. Перераспределение  поставок 12

6. Пример решения  типовой транспортной  задачи 15

Список  использованной литературы 21 
 
 
 
 

 

1. Постановка транспортной задачи. Транспортная таблица

       Рассмотрим  следующую задачу, называемую транспортной задачей. Имеется m поставщиков A₁, A₂,..., A_m, у которых сосредоточены запасы одного и того же груза в количестве a₁, a₂,..., a_m единиц соответственно. Этот груз нужно доставить n потребителям B₁, B₂,..., B_n, заказавшим b₁, b₂,..., b_n единиц этого груза соответственно. Известны также все тарифы перевозок груза c_ij (стоимость перевозок единицы груза) от поставщика A_i к потребителю B_j.

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

       Условие транспортной задачи удобно записать в виде следующей транспортной таблицы (Таблица 1).

Таблица 1

       Транспортная  таблица

 

       Обозначим суммарный запас груза у всех поставщиков символом a, а суммарную потребность в грузе у всех потребителей – символом b.

       Тогда

       

.

       Транспортная  задача называется закрытой, если a = b. Если же a ≠ b , то транспортная задача называется открытой.

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

       В случае открытой задачи при a < b весь груз будет вывезен, однако будут недопоставки груза экономически невыгодным потребителям. При a > b, наоборот, будут удовлетворены все потребители, но часть груза останется на складах экономически невыгодных поставщиков.

       Пусть x_ij (x_ij ≥ 0) – количество груза, отправляемого поставщиком A_i потребителю B_j . Тогда суммарные затраты z на перевозки будут вычисляться по формуле:

       

       Матрица X с неотрицательными элементами x_ij называется планом перевозок. Функция z называется целевой функцией. Математическая формулировка транспортной задачи заключается в нахождении плана перевозок

X = {xij },

который удовлетворяет  системе ограничений

             (1.1)

и доставляет минимум  целевой функции z.

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

       Смысл первой группы равенств в системе  ограничений (1.1) состоит в том, что суммарное количество груза, отправленное всем потребителям каждым поставщиком, равно запасу груза у этого поставщика. Вторая группа равенств в системе ограничений (1.1) показывает, что суммарное количество груза, полученное каждым потребителем от всех поставщиков, равно заказу этого потребителя.

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

       Решение транспортной задачи начинается с выяснения  вопроса о том, является ли задача открытой или закрытой.

       Если  задача является открытой, то необходимо провести процедуру закрытия задачи. С этой целью при a < b добавляем фиктивного поставщика A`<sub>m+1</sub> с запасом груза a`_m+1 = b - a.

       Если  же a > b , то добавляем фиктивного потребителя B`<sub>n+1</sub> с заказом груза b`_n+1 = a - b.

       В обоих случаях соответствующие  фиктивным объектам тарифы перевозок  c'_ij полагаем равными нулю. В результате суммарная стоимость перевозок z не изменяется.

3. Первоначальный план  перевозок 

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

         1. Составление первоначального  плана перевозок;

         2. Последовательные  улучшения плана перевозок (перераспределение

         поставок) до тех  пор, пока план перевозок не станет оптимальным.

       Решение ОЗЛП начинается с нахождения опорного плана. Для транспортной задачи такой план всегда существует. Опишем два метода составления опорного плана (первоначального плана перевозок). При этом ненулевые элементы xij плана перевозок будем записывать в соответствующие пустые клетки транспортной таблицы с исходными данными задачи, а символом (i, j) будем обозначать клетку таблицы, содержащую информацию о перевозках груза от поставщика A_i к потребителю B_j.

3.1.Составление  первоначального  плана перевозок  с помощью метода северо-западного угла

 

       Составление первоначального плана перевозок начнем с перевозки запасов поставщика A₁. Будем за счет его запасов максимально возможно удовлетворять заказы сначала потребителя B₁, затем B₂ и так далее. Таким образом, мы будем заполнять таблицу, начиная с клетки (1,1), и двигаться вправо по строке до тех пор, пока остаток запасов поставщика A₁ не окажется меньше заказа очередного потребителя. Для выполнения этого заказа используем остатки запаса первого поставщика, а недостающую часть добавим из запасов поставщика A₂ , то есть переместимся на следующую строку таблицы пo столбцу, соответствующему указанному потребителю. Далее аналогичным образом распределим запасы поставщика A₂ , затем A₃ и так далее.

       Проиллюстрируем это на следующем примере (Таблица 2):

       Таблица 2

        

       Распределяя запасы поставщика A₁ сначала потребителю B₁ , а затем B₂, получаем: x₁₁ = 100 , x₁₂ = 40. После этого у поставщика A₁ остается еще 20 единиц груза, а потребителю B₃ нужно 80 единиц. Удовлетворим спрос потребителя B₃ , отправив ему 20 единиц груза, оставшихся у поставщика A₁ , 30 единиц груза от поставщика A₂ и 30 единиц груза от A₃ . Следовательно, x₁₃ = 20, x₂₃ = 30 и x₃₃ = 30, причем у поставщика A₃ остается 60 последних единиц груза. Этот груз и отправим потребителю B₄. Таким образом, x₃₄ = 60, все запасы груза вывезены и все потребители удовлетворены. Теперь мы можем подсчитать общую стоимость всех перевозок по данному плану:

       z = 4 ×100 + 8 × 40 +10 × 20 + 2 ×30 + 6 ×30 + 5 ×  60 = 1460 .

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

3.2. Составление первоначального  плана перевозок  с помощью метода наименьшей стоимости