пользователей: 21244
предметов: 10456
вопросов: 177505
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ


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

Пример.

Необходимо перевезти грузы из 3-х пунктов отправления (А1, А2, А3) к 4-м пунктам назначения (В1, В2, В3, В4). В трех пунктах отправления имеются грузы в объемах: в первом – 400 т, во втором – 700 т, в третьем – 1200 т. Потребности четырех пунктов назначения следующие: первого – 700 т, второго – 200 т, третьего – 600 и четвертого – 800 т.

Известны стоимости перевозок грузов от каждого пункта отправления к каждому пункту назначения (Таблица 1).

Таблица 1 - Стоимость перевозки грузов, ден. ед.

 

Пункты отправления.

Пункты назначения

В1

В2

В3

В4

А1

18

12

13

7

А2

17

10

11

13

А3

15

11

10

9

 

 

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

Пункт, отправляющий груз, называют поставщиком, а пункт, принимающий груз, -   потребителем.

Составим экономико-математическую модель задачи.

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

5.JPG

Возможности поставщиков и потребности потребителей в данной задаче равны и составляют 2300 т. Задача является закрытой.

Далее оформляют задачу в виде специальной таблицы (Таблица 2)

Таблица 2 – Таблица транспортной задачи.

2300

700

200

600

800

400

18

х11

12

х12

13

х13

7

х14

700

17

х21

10

х22

11

х23

13

х24

1200

15

х31

11

х32

10

х33

9

х34

 

 

 

 

 

 

 

 

 

 

Целевая функция: 

Z = 18х1+ 12х12+ 13х13+ 7х14+ 17х21+ 10х22+ 11х23+

+ 13х24+ 15х31+ 11х32+ 10х33+ 9х34   → min

 

Ограничения:

1. Груз, расположенный в каждом пукнте отправления должен быть вывезен в полном объеме. 

х11+ х12 + х13 + х14  = 400

х21+ х22 + х23 + х24 = 700

х31 + х32+ х33 + х34 = 1200

 

2. Потребности каждого пункта назначения дожны быть удовлетворены в полном объеме.

     х11 + х21 + х31  = 700

х12 + х22 + х32  = 200

х13 + х23+ х33  = 600

х14 + х24+ х34  = 800

3. Условие неотрицательности переменных.

image002.gif

Построим первый базисный план методом наименьшего элемента в таблице.

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

Далее среди оставшихся оценок находят минимальный элемент и делают   туда поставку. Это клетка (3:4) с оценкой  9. Объем поставки составляет 400, и так далее делают распределение, не нарушая балансы по строкам и столбцам (Таблица 3). 

Таблица 3 – Первая транспортная таблица

2300

700

200

600

800

400

18

 

12

 

13

 

7

400

700

17

500

10

200

11

 

13

 

1200

15

200

11

 

10

600

9

400

 

Проверяют число занятых клеток: (m+n-1)=4+3-1= 6.

Подсчитывают значение Z, т.е. величину затрат:

Z = 7*400 + 17*500 + 10*200 + 15*200 + 10*600 + 9*400 =

= 2800 + 8500 + 2000 + 3000 + 6000 + 3600 = 25900 т/км

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

Для них вычисляют характеристики, для чего строят замкнутые контуры. Одно вершина контура находится в свободной клетке, другие -  в занятых вершинах. Вершину в свободной клетке помечают знаком «+», а остальные вершины поочередно знаками «-», «+».

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

Вычисленные характеристик должны удовлетворять условию:

lij.  0.

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

Так, в таблице с первым базисным планом первая свободная клетка (1:1). Вычисляем для нее характеристику:

l11 = 18-7+9-15 = 5

Далее для других свободных клеток:

l12 = 12-7+9-15+17-10 = 6

l13 = 13-7+9-10 = 5

l23 = 11-10+15-17 = -1

l24 = 13-9+15-17 = 2

l32 = 11-15+17-10 = 3

В клетке (2:3) нарушается условие, поэтому в эту клетку необходимо сделать перераспределение.

8.JPG

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

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

2300

700

200

600

800

400

18

 

12

 

13

 

7

400

700

17

 

10

200

11

500

13

 

1200

15

700

11

 

10

100

9

400

 

Подсчитывают значение целевой функции при новом плане:

Z = 7*400 + 10*200 + 11*500 + 15*700 + 10*100 + 9*400 =

= 2800 + 2000 + 5500 + 10500 + 1000 + 3600 = 25400 т/км

 

Проверяют новый план на оптимальность.

l11 = 18-7+9-15 = 5

l12 = 12-7+9-10+11-10 = 5

l13 = 13-7+9-10 = 5

l21 = 17-11+10-15 = 1

l24 = 13-9+10-11 = 3

l32 = 11-10+11-10 = 2.

Все характеристики являются положительными. Следовательно, на этом этапе получен оптимальный план.

Решение данной задачи будет следующим:

х14 = 400

х22 = 200

х23 = 500

х31 = 700

х33 = 100

х34 = 400

Z = 25400 т/км


хиты: 4041
рейтинг:0
Точные науки
математика
теория графов
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь