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

 

Министерство  образования и науки Российской Федерации

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

«Санкт-Петербургский  государственный университет»

 

 

 

 

 

 

 

Курсовая  работа

 

 

по учебной  дисциплине «Математические методы в экономике»

 

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

 

 

 

 

 

 

 

 

 

 

Выполнил студент:

Группы:                                                                                                                               

Подпись___________

 

Проверил:

Дата_______________

Оценка____________

 

 

 

 

 

 

                                                                                

 

 

Санкт-Петербург

2012

 

Содержание:

Введение………………………………………………………………………….3

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

Пример решения  транспортной задачи………………………………………10

Заключение……………………………………………………………………..15

Список литературы…………………………………………………………....16

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

Кроме того, к задачам транспортного  типа сводятся многие другие задачи линейного  программирования - задачи о назначениях, сетевые, календарного планирования.

Формальным  признаком транспортной задачи является то, что каждая переменная входит лишь в два ограничения, причем с коэффициентами, равными единице. Если при этом критерий оптимальности (сумма расходов) прямо  пропорционален значениям переменных (транспортных потоков), возникает линейная транспортная задача. В других случаях  рассматривается нелинейная транспортная задача, решаемая другими методами.

 

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

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

Пусть имеется m пунктов отправления (ПО): , в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно единиц. Также имеется n пунктов назначения (ПН): , подавших заявки соответственно на единиц груза. Считаем, что сумма всех заявок равна сумме всех запасов (сбалансированная транспортная задача):

 

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

Экономико-математическая модель задачи имеет вид задачи линейного  программирования. Обозначим  – количество единиц груза, отправляемого из i-го ПО в j-й ПН . Совокупность чисел () будем называть планом перевозок, а сами величины – перевозками.

Необходимо  найти такой план перевозок (), при котором целевая функция (суммарная стоимость перевозок) будет минимальной:

 

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

1) Суммарное количество груза, направляемого  из каждого ПО во все ПН  должно быть равно запасу груза  в данном пункте:

 

2) Суммарное количество груза, доставляемого в каждый ПН из всех ПО, должно быть равно заявке, поданной данным пунктом:

 

3) Условие неотрицательности:

 

 

 

Решение транспортной задачи разбивается на два этапа:

  1. определение исходного опорного решения;
  2. построение последовательных итераций – приближение к оптимальному решению.

Обычно, для решения транспортной задачи используют ее табличную модель, в  которой ячейкам поставлены в  соответствие перевозки – переменные , при заполнении таблицы задаются значения неизвестных:

 

 

ПН

    

…

  

ПО

      

…

  
           

…

    
           
           

…

    
           

…

…

…

  

…

  

…

…

  
           

…

    
           

 

Определение исходного опорного решения.

Существует  несколько способов, наиболее популярными  являются:

- метод северо-западного угла,

- метод минимального элемента,

- метод аппроксимации Фогеля.

Они перечислены в порядке усложнения алгоритма, но при этом получаемое решение, как правило, меньше отличается от оптимального.

В каждом методе на любом шаге в выбранную  ячейку () таблицы помещается максимальная допустимая перевозка – минимальное из того, что есть у соответствующего поставщика (ПО) и требуется соответствующему потребителю (ПН) . При этом каждый раз «закрывается» строка таблицы, если у соответствующего поставщика (ПО) больше нет груза, или «закрывается» столбец, если соответствующему потребителю (ПН) больше не надо груза. Методы отличаются лишь способом построения последовательности заполнения ячеек таблицы.

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

В методе минимального элемента заполнение начинается с ячейки с минимальной стоимостью. Каждый раз переходят к следующей свободной ячейке (расположенной в «незакрытых» сроках и столбцах) с минимальной стоимостью.

Пример. Метод северо-западного угла.

Последовательность  заполнения таблицы:

 

Стоимость перевозок:

 

 

 

ПН

      

ПО

  

10

65

25

 

30

  

6

  

3

  

2

10

  

20

      
 

20

  

2

  

1

  

5

   

20

      
 

50

  

3

  

4

  

1

   

25

  

25

  

 

Пример. Метод минимального элемента

Последовательность  заполнения таблицы:

 

Стоимость перевозок:

 

 

 

ПН

      

ПО

  

10

65

25

 

30

  

6

  

3

  

2

   

30

      
 

20

  

2

  

1

  

5

   

20

      
 

50

  

3

  

4

  

1

10

  

15

  

25

  

 

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

Метод потенциалов получения оптимального решения.

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

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

Для каждой свободной клетки вычисляется  числовая характеристика – косвенная стоимость: .

Критерий  оптимальности плана перевозок:

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

1) , если (для заполненных клеток),

2) (для свободных клеток).

Т.е. если все косвенные стоимости  неотрицательные, то решение оптимальное, в противном случае его можно  улучшить.

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

Если  данный план перевозок не оптимальный, то в свободную ячейку, которой  соответствует наименьшая отрицательная  косвенная стоимость , помещают перевозку l и составляют цикл пересчета (замкнутая ломанная линия, состоящая из горизонтальных и вертикальных отрезков прямых, первая вершина которой находится в свободной ячейке с перевозкой l, а остальные в базисных (заполненных) ячейках). Заметим,  что в новом плане суммы элементов по строкам и столбцам должны остаться прежними,  поэтому изменение значения в одной клетке цикла повлечет за собой соответствующие изменения значений во всех остальных клетках этого цикла.  Так как в свободной клетке значение будет увеличено, то проставим знак  «плюс». Теперь пройдем по всей ломаной цикла, проставляя поочередно знаки «плюс» и «минус».  По циклу пересчета восстанавливается баланс, нарушенный ненулевой перевозкой l (см. рис. 1)

Значение l определяется как максимально возможное, сохраняющее неотрицательность всех перевозок, т.е. по соотношениям вида l.

На рис. 1: l.

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

Рис. 1


 

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

Алгоритм  применения метода потенциалов:

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

2) Составить систему уравнений  для заполненных клеток. При найти потенциалы всех поставщиков и потребителей .

3) Определить  косвенные стоимости свободных  ячеек по формуле: 

4) Если все косвенные стоимости  неотрицательны, то план перевозок  оптимальный.

5) Если есть отрицательные косвенные  стоимости, то в свободную ячейку  с наименьшей отрицательной косвенной  стоимостью поместить перевозку l и составить цикл пересчета.

6) Найти максимальное значение l при условии сохранения неотрицательности всех перевозок, составить новый опорный план, рассчитать стоимость перевозок.

7) Перейти к п.2.

Пример. Провести одно улучшение опорного плана методом потенциалов:

 

ПН

      

ПО

  

10

65

25

 

30

-l

6

+l

3

  

2

10

  

20

      
 

20

  

2

  

1

  

5

   

20

      
 

50

l

3

-l

4

  

1

   

25

  

25

  

 

Решение:

Составим  систему уравнений  для заполненных клеток:

 или 

Пусть , найдем потенциалы всех поставщиков и потребителей :

 

Определить  косвенные стоимости свободных  ячеек:

 

 

 

 

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

lllll

Найдем максимальное значение l, сохраняющее неотрицательность всех перевозок: l (если взять значение l больше, то в ячейке будет отрицательная перевозка).

Пересчитаем новый план перевозок:

 

ПН

      

ПО

  

10

65

25

 

30

  

6

  

3

  

2

   

30

      
 

20

  

2

  

1

  

5

   

20

      
 

50

  

3

  

4

  

1

10

  

15

  

25

  

 

Стоимость перевозок:  

 

 

 

 

 

 

 

 

 

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

Имеется три поставщика хлебобулочной продукции: ОАО «Заря», ОАО «Хлебный дом» и ОAО «Каравай» у каждого из них имеются запасы однородных грузов:

ОАО «Заря» − 150 единиц хлебобулочной продукции,

ОАО «Хлебный дом» − 300 единиц хлебобулочной продукции,

ОAО «Каравай» − 250 единиц хлебобулочной продукции, которая должна быть доставлена потребителям: OOO «Пятерочка», OOO «Семья» и ООО «Полушка» в количестве:

OOO «Пятерочка» − 200 единиц,

OOO «Семья» − 250 единиц,

ООО «Полушка» − 250 единиц.

Стоимость доставки единицы продукции от поставщика ОАО «Заря» к указанным потребителям равна:

10 руб. – для OOO «Пятерочка»,

13 руб. – для OOO «Семья»,

11 руб. – для ООО «Полушка».

Стоимость доставки единицы продукции от поставщика ОАО «Хлебный дом» к указанным потребителям равна:

10 руб. − для OOO «Пятерочка»,

12 руб. − для OOO «Семья»,

10 руб. − для ООО «Полушка».

Стоимость доставки единицы продукции от поставщика ОAО «Каравай» к указанным потребителям равна:

11 руб. − для OOO «Пятерочка»,

12 руб. − для OOO «Семья»,

12 руб. − для ООО «Полушка».

Требуется найти оптимальное решение доставки продукции от поставщиков к потребителям, минимизирующие стоимость доставки.

Решение:  

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

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

В нашем случае, потребность всех потребителей - 700 единиц хлебобулочной продукции равна запасам всех поставщиков.

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

 

 

Потребители

ООО «Пятерочка»

ООО «Семья»

ООО «Полушка»

Поставщики

  

200

250

250

ОАО «Заря»

150

  

10

  

13

  

11

150

х11

 −

х12

 −

х13

ОАО «Хлебный дом»

300

  

10

  

12

  

10

50

х21

 −

х22

250

х23

ОАО «Каравай»

250

  

11

  

12

  

12

0

х31

250

х32

 −

х33


 

Последовательность  заполнения таблицы:

(х11 = 150) → (х21 = 50) → (х23 = 250) → (х32 = 250) → (х31 = 0)

Распишем последовательность заполнения таблицы:  

1) Минимальный элемент матрицы тарифов находится в ячейке х11  и равен 10, т.е. из незадействованных маршрутов, маршрут доставки продукции от поставщика ОАО «Заря» к потребителю OOO «Пятерочка» наиболее рентабельный.

Запасы  ОАО «Заря» составляют 150 единиц продукции. Потребность OOO «Пятерочка» составляет 200 единиц продукции. Следовательно, от ОАО «Заря» к OOO «Пятерочка» будем доставлять 150 единиц хлебобулочной продукции.

Разместим в ячейку х11 значение равное 150.

Мы полностью израсходoвали запасы ОАО «Заря». Вычеркиваем строку 1 таблицы, т.е. исключаем ее из дальнейшего рассмотрения.

2) Следующий минимальный элемент матрицы тарифов находится в ячейке х21 и равен 10, т.е. из незадействованных маршрутов, маршрут доставки продукции от ОАО «Хлебный дом» к OOO «Пятерочка» наиболее рентабельный.

Запасы  ОАО «Хлебный дом» составляют 300 единиц продукции. Потребность OOO «Пятерочка» составляет 50 единиц продукции. Следовательно, от ОАО «Хлебный дом» к OOO «Пятерочка» будем доставлять 50 единиц хлебобулочной продукции.

Разместим в ячейку х21 значение равное 50.

Мы  полностью удовлетворили потребность  OOO «Пятерочка». Вычеркиваем столбец 1 таблицы, т.е исключаем его из дальнейшего рассмотрения.

3) Следующий минимальный элемент матрицы тарифов находится в ячейке х23 и равен 10, т.е. из незадействованных маршрутов, маршрут доставки продукции от ОАО «Хлебный дом» к ООО «Полушка» наиболее рентабельный.

Запасы  ОАО «Хлебный дом» составляют 250 единиц продукции. Потребность ООО «Полушка» составляет 250 единиц продукции.

Следовательно, от ОАО «Хлебный дом» к ООО «Полушка» будем доставлять 250 единиц хлебобулочной продукции.

Разместим в ячейку х23 значение равное 250.

Таким образом, мы полностью израсходoвали запасы ОАО «Хлебный дом», а также мы полностью удовлетворили потребность ООО «Полушка». Вычеркиваем строку 2 и столбец 3 таблицы, т.е исключаем их из дальнейшего рассмотрения.

4) Следующий минимальный элемент матрицы тарифов находится в ячейке х32 и равен 12, т.е. из незадействованных маршрутов, маршрут доставки продукции от ОAО «Каравай» к OOO «Семья» наиболее рентабельный.

Запасы  ОAО «Каравай» составляют 250 единиц продукции. Потребность OOO «Семья» составляет 250 единиц продукции. Следовательно от ОAО «Каравай» к OOO «Семья» будем доставлять 250 единиц хлебобулочной продукции.

Разместим в ячейку х32 значение равное 250.

Мы  полностью израсходoвали запасы ОAО «Каравай». Вычеркиваем строку 3 таблицы, т.е исключаем ее из дальнейшего рассмотрения.

5) Заполненные нами ячейки будем называть базисными, остальные - свободными.

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

m + n - 1, где

m - количество строк в таблице,

n - количество столбцов в таблице.

У нас количество базисных ячеек равно 4. Требуется, чтобы было 5. Следовательно, в свободную ячейку х31 запишем ноль, как в ячейку не образующую цикл (понятие цикл см. ниже) с базисными ячейками и имеющую наименьший тариф.

Будем считать, что от ОAО «Каравай» к OOO «Пятерочка» доставляем 0 единиц хлебобулочной продукции.

Теперь  количество базисных ячеек (задействованных маршрутов) равно 5, что и требовалось.

Мы  нашли начальное решение, т.е израсходовали  все запасы поставщиков и удовлетворили  все потребности потребителей.

 F = 10 * 150 + 10 * 50 + 10 * 250 + 12 * 250 = 7500 руб., где

 F – стоимость перевозок.

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

Дальнейшие  наши действия состоят в следующем:

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

Потребители

ООО «Пятерочка»

ООО «Семья»

ООО «Полушка»

Ui

Поставщики

  

200

250

250

ОАО «Заря»

150

  

10

  

13

  

11

u1 =10

150

х11

 2

х12

 1

х13

ОАО «Хлебный дом»

300

  

10

  

12

  

10

u2 =10

50

х21

 1

х22

250

х23

ОАО «Каравай»

250

  

11

  

12

  

12

u3 =11

0

х31

250

х32

 1

х33

Vj

v1 = 0

v2 = 1

v3 = 0

  

 

Каждому поставщику ставим в соответствие некоторое число - ui, называемое потенциалом поставщика.

Каждому потребителю ставим в соответствие некоторое число - vj, называемое потенциалом потребителя.

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

(ui + vj = тариф  клетки).

 

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

 

Примем v1 = 0.


v1 + u1 = x11

v1 + u1 = 10

u1 = 10 - 0 = 10


v1 + u2 = x21

v1 + u2 = 10

u2 = 10 - 0 = 10


v3 + u2 = x23

v3 + u2 = 10

v3 = 10 - 10 = 0


v1 + u3 = x31

v1 + u3 = 11

u3 = 11 - 0 = 11


v2 + u3 = x32

v2 + u3 = 12

v2 = 12 - 11 = 1


Найдем оценки свободных ячеек  следующим образом (в таблице  они располагаются в нижнем левом  углу ячейки):

∆12 = x12 - ( u1 + v2 ) = 13 - ( 10 + 1 ) = 2

∆13 = x13 - ( u1 + v3 ) = 11 - ( 10 + 0 ) = 1

∆22 = x22 - ( u2 + v2 ) = 12 - ( 10 + 1 ) = 1

∆33 = x33 - ( u3 + v3 ) = 12 - ( 11 + 0 ) = 1

Составим матрицу оценок:

0

2

1

0

1

0

0

0

1


 

Все оценки свободных ячеек положительные, следовательно, найдено оптимальное  решение.