Технические темы
1 1 1 1 1 1 1 1 1 1 Рейтинг 4.00 (1 Голос)

Транспортные задачи с решением

 

 Одноэтапная транспортная задача

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

Классическая постановка транспортной задачи звучит так: имеется продукт, сосредоточенный у m поставщиков Аi в количестве аi соответственно, необходимо доставить этот продукт n потребителям Вj в количестве bj.

Известна стоимость Сij перевозки единицы груза от i-го поставщика j-му потребителю. Перевозку следует организовать так, чтобы полностью удовлетворить поставщиков и потребителей, минимизировав при этом транспортные расходы.

На практике суммарные возможности поставщиков и потребности потребителей не совпадают. Возможны два варианта:

1. Поставщики могут поставить товара больше, чем могут приобрести потребители:. При этом поставка i-го поставщика будет больше, чем сумма приходящихся на него заявок .

2. Поставщики могут поставить товара меньше, чем могут приобрести потребители:. При этом j-му потребителю достанется груза меньше, чем он может приобрести .

Таким образом, существуют две модели:

и ,

(1) первая из которых соответствует избытку груза, а вторая – дефициту.

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

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

- если поставки превышают потребности, то факт поставок должен быть меньше либо равен поставкам по условию, а факт потребностей – больше либо равен потребностям по условию;

- если потребности превышают возможные поставки, то факт поставок должен быть больше либо равен поставкам по условию, а факт потребностей – меньше либо равен потребностям по условию.

Одноэтапная транспортная  Задача № 1

Хозяйство транспортирует молоко с трех ферм, производящих в сутки молоко в количестве: Ферма 1 – 3680кг.; Ферма 2 – 5430кг.; Ферма 3 – 3080кг.

Молокозаводы готовы принять молоко в количестве: Завод 1 – 2520кг., Завод 2 – 2890кг., Завод 3 – 2560кг., Завод 4 – 2110кг., Завод 5 – 1100кг. Стоимость перевозки 1кг. молока на молокозаводы различна из-за их различной их удаленности от ферм и составляет:

Стоимость перевозки единицы груза (тариф), грн.

 

 

 

Завод 1

Завод 2

Завод 3

Завод 4

Завод 5

 

Ферма 1

0,03

0,04

0,06

0,05

0,01

 

Ферма 2

0,02

0,03

0,05

0,04

0,02

 

Ферма 3

0,01

0,02

0,04

0,04

0,03

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

 Решение транспортной задачи

1. На Листе Excel составим транспортную таблицу тарифов и поставок:

 

B

C

D

E

F

G

H

5

Стоимость перевозки единицы груза (тариф), грн

   

6

 

Завод 1

Завод 2

Завод 3

Завод 4

   

7

Ферма 1

0,03

0,04

0,06

0,05

   

8

Ферма 2

0,02

0,03

0,05

0,04

 

Стоимость

9

Ферма 3

0,01

0,02

0,04

0,04

 

СУММПРОИЗВ(C7:F9;C11:F13)

10

Распределение груза

Факт

Поставки

11

Ферма 1

0

0

0

0

СУММ(C11:F11)

3680

12

Ферма 2

0

0

0

0

СУММ(C12:F12)

5430

13

Ферма 3

0

0

0

0

СУММ(C13:F13)

3080

14

Факт

СУММ

(C11:C13)

СУММ

(D11:D13)

СУММ

(E11:E13)

СУММ

(F11:F13)

0

12190

15

Заявки

2520

2890

2560

2110

10080

 

В ячейке G15 – сумма заявок по условию.

В ячейке Н14 – сумма поставок по условию.

В ячейке Н9 – функция цели - сумма произведений поставляемого груза на его тариф для каждой пары Ферма-Завод: СУММПРОИЗВ(C7:F9;C11:F13).

Начальные значения поставок приравниваем 0.

2. Вызываем надстройку «Поиск решения…».

Целевая ячейка – Н9 стремится к минимуму.

Изменяемые ячейки – матрица С11:F13.

Ограничения вводим по правилу избытка поставок, так как сумма поставок (ячейка Н14) превышает сумму заявок (ячейка G15): 12190>10080:

- фактические поставки не превышают возможности i-го поставщика (G11:G13<=Н11:Н13);

- фактические потребности j-го потребителя не меньше его заявки (С14:F14>=С15:F15);

- все переменные назначаем целыми (рис.1, 2).

3. Вызываем окно «Параметры», в котором указываем «Линейная модель», «Неотрицательные переменные».

 

Рис.1.


Рис.2.

4. Запускаем программу на выполнение и получаем оптимальный план перевозок:

 

Завод 1

Завод 2

Завод 3

Завод 4

   

Ферма 1

0.03

0.04

0.06

0.05

   

Ферма 2

0.02

0.03

0.05

0.04

 

Стоимость

Ферма 3

0.01

0.02

0.04

0.04

 

334.4

Распределение груза

Факт

Поставки

Ферма 1

1570

0

0

0

1570

3680

Ферма 2

0

2890

430

2110

5430

5430

Ферма 3

950

0

2130

0

3080

3080

Факт

2520

2890

2560

2110

10080

12190

Заявки

2520

2890

2560

2110

10080

 

Минимальная стоимость транспортных расходов составила 334,4грн. При этом все заявки удовлетворены, а фактическая поставка с Фермы 1 на 2110кг. молока меньше планируемой. Для этой фермы следует, очевидно, искать другой завод-потребитель.

Следует отметить, что оптимальных целочисленных решений может быть более одного.

 

 

 

Двухэтапная транспортная задача с решением

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

Постановка двухэтапной транспортной задачи звучит так: имеется продукт, сосредоточенный у m поставщиков Аi в количестве аi соответственно, необходимо доставить этот продукт n потребителям Вj в количестве bj.

Весь продукт проходит через р складов Dk, емкость которых dk.

Известна стоимость Сik перевозки единицы груза от i-го поставщика на k-й склад и стоимость Сkj перевозки с k-го склада j-му потребителю. Перевозку следует организовать так, чтобы полностью удовлетворить поставщиков и потребителей, минимизировав при этом транспортные расходы.

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

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

Из-за расхождений между спросом и предложением существуют две модели:

и, ,

(2) первая из которых соответствует избытку груза, а вторая – дефициту.

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

Задача  транспортная № 2

Хозяйство транспортирует зерно с трех полей в количестве: Поле1 – 28,0т/сутки; Поле2 – 16,4т/сутки; Поле3 – 18,2т/сутки.

Зерно транспортируется на токи, способные переработать зерно в количестве: Ток1 – 35,6т/сутки; Ток2 – 21,8т/сутки; Ток3 – 31,0т/сутки.

С токов зерно транспортируется на элеваторы, принимающие зерно в количестве: Элеватор1 – 24,7т/сутки; Элеватор2 – 19,7т/сутки; Элеватор3 – 29,8т/сутки; Элеватор4 – 16,4т/сутки.

Тарифы перевозок (грн/тонну):

 

Ток1

Ток2

Ток3

Поле1

6

5

2

Поле2

3

4

4

Поле3

7

8

5

Элеватор1

15

18

10

Элеватор2

13

11

18

Элеватор3

12

13

15

Элеватор4

17

11

15

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

Решение двухэтапной транспортной задачи

1. На Листе Excel составим транспортную таблицу тарифов и поставок:

 

C

D

E

F

G

H

I

J

K

3

 

Ток1

Ток2

Ток3

         

4

Поле1

6

5

2

         

5

Поле2

3

4

4

         

6

Поле3

7

8

5

Элеватор1

Элеватор2

Элеватор3

   

7

     

Ток1

15

13

12

   

8

     

Ток2

18

11

13

   

9

     

Ток3

10

18

15

   

10

       

Сумма общая

   

11

 

Ток1

Ток2

Ток3

 

0

 

Факт

Поставка

12

Поле1

0

0

0

     

0

28,3

13

Поле2

0

0

0

     

0

16,4

14

Поле3

0

0

0

Элеватор1

Элеватор2

Элеватор3

0

18,2

15

Ток1

0

   

0

0

0

0

35,6

16

Ток2

 

0

 

0

0

0

0

21,8

17

Ток3

   

0

0

0

0

0

31,0

18

 

0

0

0

0

0

0

0

62,9

19

 

35,6

21,8

31,0

24,7

19,7

29,8

74,2

 

2. Запишем в ячейки Листа формулы из системы ограничений (2.8):

- ячейка D18=СУММ(D12: D17);

- копируем суммирование ячейки D18 для ячеек E18, F18, G18, H18, I18;

- ячейка J12=СУММ(D12: I12);

- копируем суммирование ячейки J12 для ячеек J13, J14, J15, J16, J17;

- ячейка J19=СУММ(G19: I19) – сумма заявок;

- ячейка К18=СУММ(К12: К14) – сумма поставок;

- ячейка Н11=СУММПРОИЗВ(D4: I9;D12:I17) – целевая функция – сумма произведений поставок на их тарифы.

3. Вызываем надстройку «Поиск решения…» (рис.3):

- целевая ячейка Н11, стремится к минимуму;

- изменяемые ячейки D12:F14; D15; E16; F17; G15:I17;

 
 

 

Рис.3.

- вводим ограничения:

D18:F18=D19:F19 и J15:J17=K15:K17 – условие баланса для складов;

G18:I18<=G19:I19 – фактическая сумма заявок не превышает планируемую сумму (алгоритмическое правило в условиях дефицита, то есть превышении спроса над предложением: спрос=742, предложение=629);

J12:J14>=K12:K14 – фактическая сумма поставок не меньше планируемой (алгоритмическое правило для дефицита);

- в окне «Параметры» указываем «Линейная модель» и «Неотрицательные значения».

4. После нажатия кнопки «Выполнить» получаем на экране окно «Результаты поиска решения» (рис.4) с сообщением о том, что решение найдено, указываем в этом окне на необходимость вывода отчета «Устойчивость» и нажимаем кнопку «ОК».

 
 

 

Рис.4.

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

Результат решения транспортной задачи:

 

C

D

E

F

G

H

I

J

K

3

 

Ток1

Ток2

Ток3

         

4

Поле1

6

5

2

         

5

Поле2

3

4

4

         

6

Поле3

7

8

5

Элеватор1

Элеватор2

Элеватор3

   

7

     

Ток1

15

13

12

   

8

     

Ток2

18

11

13

   

9

     

Ток3

10

18

15

   

10

       

Сумма общая

   

11

 

Ток1

Ток2

Ток3

 

945,8

 

Факт

Поставка

12

Поле1

0

8,4

19,9

     

28,3

28,3

13

Поле2

16,4

0

0

     

16,4

16,4

14

Поле3

13,4

0

4,8

Элеватор1

Элеватор2

Элеватор3

18,2

18,2

15

Ток1

5,8

   

0

0

29,8

35,6

35,6

16

Ток2

 

13,4

 

0

8,4

0

21,8

21,8

17

Ток3

   

6,3

24,7

0

0

31,0

31,0

18

 

35,6

21,8

31,0

24,7

8,4

29,8

 

62,9

19

 

35,6

21,8

31,0

24,7

19,7

29,8

74,2

 

Фрагмент отчета по устойчивости: таблица коэффициентов увеличения расходов по направлениям транспортировки:

Ячейка

Имя

Результ. Значение

Нормир. стоимость

Целевой Коэффициент

$D$12

Поле1 Ток1

0

2

6

$F$13

Поле2 Ток3

0

3

4

$G$15

Элеватор1

0

7

15

$H$15

Элеватор2

0

1

13

$G$16

Элеватор1

0

11

18

$I$16

Элеватор3

0

2

13

$H$17

Ток3 Элеватор2

0

4

18

$I$17

Ток3 Элеватор3

0

1

15

В результате получено решение, которое предусматривает поставки не по всем направлениям, имеющимся в условии задачи (поставки по этим направлениям равны 0 и выделены в таблице цветом). А отчет по устойчивости показывает, что поставки именно по этим направлениям приведут к росту стоимости всех перевозок (нормированная стоимость больше 0).

Транспортные задачи - 4.0 out of 5 based on 1 vote

Добавить комментарий


Защитный код
Обновить

Google