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




Построение экономико-математической модели (ЭММ) распределения запасов продукции с точки зрения минимальных транспортных затрат.

 

ЗАДАНИЕ.

Готовая продукция заводов Ai (i= 1,2,3) направляется на склады Bj(j = 1, 2, 3, 4). Заводы Ai производят аi тыс. изделий c себестоимостью единицы продукции Сi. Пропускная способность складов Bj за это время xaрактеризуется величинами bj тыс. изделий. Стои­мость перевозки с завода Ai на склад Bj одной тысячи изделий равна Сi j.

Требуется:

1. Составить экономико-математическую модель задачи, найти план перевозки готовой продукции с заводов на склады с минимальными затратами методом потенциалов. Найти величину fmin минимальныx транспортных затрат.

2. Найти оптимальный план перевозки готовой продукции на склады при дополнительном условии, что на складе Bк созданы лучшие условия для хранения готовой продукции, а поэтому он должен быть загружен полностью, (или продукция завода Ак должна быть распределена полностью), где к – номер склада, незагруженного полностью, (или номер завода с нераспределённой продукцией);

3. Найти оптимальный план перевозки готовой продукции на склады при дополнительном условии, что из пункта отправления Аp в пункт назначения Вr должно быть перевезено не менее drp ед. продукции, а из пункта отправления Аs в пункт назначения Вt должно быть перевезено не более dst ед. продукции.

  В1 В2 В3 В4 В5 В6 В7 В8 В9 В10 В11 В12 В13 В14 В15
А1                              
А2                              
А3                              
С1                              
С2                              
С3                              
В1                              
В2                              
В3                              
В4                              
С11                              
С12                              
С13                              
С14                              
С21                              
С22                              
С23                              
С24                              
С31                              
С32                              
С33                              
С34                              
P                              
r                              
drp                              
s                              
t                              
dst                              

 

  В16 В17 В18 В19 В20 В21 В22 В23 В24 В25 В26 В27 В28 В29 В30
А1                              
А2                              
А3                              
С1                              
С2                              
С3                              
В1                              
В2                              
В3                              
В4                              
С11                              
С12                              
С13                              
С14                              
С21                              
С22                              
С23                              
С24                              
С31                              
С32                              
С33                              
С34                              
P                              
r                              
drp                              
s                              
t                              
dst                              

 

Решение типового варианта В-31

 


1)Обозначим через Хij- количество единиц продукции, которое планируется перевезти с завода Аi (i=1,3) на склад Вj(j=1,4), а через f-суммарные затраты на её изготовление и доставку.

Суммарная мощность пунктов производства составляет:

400+300+500=1200.

Суммарная пропускная способность складов составляет:

350+250+150+250=1000

Замечаем, что суммарная пропускная способность складов меньше суммарной мощности пунктов производства:

1000<1200

Таким образом, условие закрытости модели не выполняется, поэтому надо вводить фиктивный склад В5 с возможным спросом:

1200-1000=200 и стоимостью перевозок Сi5=0 (i=1,3).

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

Составим распределительную таблицу 1.

Таблица 1.

  Склады Вj и их пропускная способность  
Пункты производства Аi и их мощность. В1 (350) В2 (250) В3 (150) В4 (250) В5 (200)
А1(400) 2 +2=4 Х11 6 +2=8 Х12 4+2=6 Х13 7+2=9 Х14 0+2=2 Х15
А2(300) 6+3=9 Х21 2+3=5 Х22 7+3=10 Х23 1+3=4 Х24 0+3=3 Х25
А3(500) 6+1=7 Х31 10+1=11 Х32 7+1=8 Х33   5+1=6 Х34 0+1=1 Х35
             

Где:

 
 

-стоимость изготовления и доставки единицы продукции с завода Аi (i=1,3)

на склад Вj(j=1,5).

Экономико-математическая модель задачи примет вид:


суммарные затраты:


условия полной отгрузки продукции со всех пунктов производства:

 

условия полной загрузки всех складов:


-Условия неотрицательности переменных:

Таким образом, задача сводится к нахождению решения (Х11*, Х12*,…, Х35*) системы линейных уравнений (2), (3), доставляющих минимум линейной функции(1).

Решим данную задачу транспортного типа методом потенциалов.

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

В таблице 2 построен начальный опорный план методом минимального элемента.

Табл. 2.

            Ui
  - 4   + 6     U1=0
      - 10 + 4 *   U2=4
  50 +     - 6   U3=3
Vj V1=4 V2=1 V3=6 V4=3 V5=-2  

Число занятых клеток равно 7, совпадает с m+n-1=3+5-1=7- опорный план-невырожденный.

Замечание. Если при построении опорного плана занятых клеток будет меньше, чем m+n-1, то опорный план – вырожденный; а в свободную клетку, соответствующую наименьшему тарифу, и не образующую замкнутый цикл с занятыми клетками, заносится нуль, и эта клетка считается занятой.

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


составленных по заполненным клеткам. Получаем


Найдём оценки свободных клеток:


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


для занимаемой клетки (2,4). Прибавляя λ в положительных клетках и вычитая в отрицательных, получаем новый опорный план, содержащийся в табл.3.

табл.3.

            Ui
  250 +   150 -     U1=0
            U2=1
500 100 -   + *     U3=3
Vj V1=4 V2=4 V3=6 V4=3 V5=-2  


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

для занимаемой клетки (3,3). Прибавляя λ в положительных клетках и вычитая в отрицательных, получаем новый опорный план, содержащийся в табл.4. табл.4

            Ui
            U1=0
            U2=0
      8 100     U3=2
Vj V1=4 V2=5 V3=6 V4=4 V5=-1  


Клеток с отрицательными оценками в табл. 4 нет. Следовательно, в ней содержится оптимальный план.


Этому плану соответствуют минимальные суммарные затраты:


По этому плану перевозок завод А1 должен 350 ед. продукции доставить на склад В1 и 50 ед. продукции доставить на склад В3; завод А2 должен 250 ед. продукции доставить на склад В2 и 50 ед. продукции доставить на склад В4; завод А3 должен 100 ед. продукции доставить на склад В3 и 200 ед. продукции доставить на склад В4. При этом суммарные затраты будут минимальными и составят 5350 ден. ед.

Нераспределённая продукция в объёме 200 ед. останется на заводе А3.

2)Решим данную задачу транспортного типа методом потенциалов при дополнительном условии, что продукция завода А3 должна быть распределена полностью. Это ограничение будет соблюдено в том случае, если в заключительной таблице с оптимальным планом клетка (А3, В5) останется свободной.Чтобы добиться этого, на время решения условно завысим показатель критерия оптимальности в клетке (А3, В5) до величины М=100 (М- большое положительное число). Понятно, что теперь занимать клетку (А3, В5) будет явно невыгодно. В таблице 5 построен начальный опорный план с учётом дополнительного ограничения по методу минимального элемента.

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

Табл. 5.

            Ui
            U1=0
      - 10 +4 *   U2=5
      + 8 - 6   U3=3
Vj V1=4 V2=0 V3=5 V4=3 V5=2  

Число занятых клеток равно 7, совпадает с m+n-1=3+5-1=7- опорный план-невырожденный.


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

составленных по заполненным клеткам. Получаем


Найдём оценки свободных клеток:


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


для занимаемой клетки (2,4). Прибавляя λ в положительных клетках и вычитая в отрицательных, получаем новый опорный план, содержащийся в табл.6.

табл.6

            Ui
            U1=0
            U2=1
            U3=3
Vj V1=4 V2=4 V3=5 V4=3 V5=2  


Клеток с отрицательными оценками в табл. 6 нет. Следовательно, в ней содержится оптимальный план.

 

Этому плану соответствуют минимальные суммарные затраты:


По этому плану перевозок завод А1 должен 200 ед. продукции доставить на склад В1; завод А2 должен 250 ед. продукции доставить на склад В2 и 50 ед. продукции доставить на склад В4; завод А3 должен 150 ед. продукции доставить на склад В1; 150 ед. продукции доставить на склад В3 и 200 ед. продукции доставить на склад В4. При этом суммарные затраты будут минимальными и составят 6100 ден. ед.

Нераспределённая продукция в объёме 200 ед. останется на заводе А1.

При соблюдении дополнительного условия, что продукция завода А3 должна быть распределена полностью, минимальные суммарные затраты увеличиваются на 6100-5350=750 ден. ед.

3) Найдём оптимальный план перевозки готовой продукции на склады при дополнительном условии, что из пункта отправления А2 в пункт назначения В4 должно быть перевезено не менее 100 ед. продукции, а из пункта отправления А1 в пункт назначения В1 должно быть перевезено не более 150 ед. продукции.

В таблице 4, содержащей оптимальный план, в клетке (2;4) стоит число 50<100. Итак, поставка Х24 =100 ед. обязательна и должна войти в оптимальный план. Уменьшим количество продукции у поставщика А2 на 100 ед., т.е. а2′ = а2 – 100=300-100=200 ед., и пропускную способность склада В4 на 100 ед., т.е. b4′ = b4 – 100=250-100=150 ед.. Т.к. по маршруту А1В1 можно перевезти не более 150 ед. продукции, то В1-ый столбец матрицы перевозок разобьём на два: В1′ и В1′′. Тогда b1′= b1-150=350-150=200; b1′′= 150. Тарифы С i 1′= С i 1′′= С i 1 (i=2,3); С 11′=100 (клетка блокируется). Решим задачу относительно необязательных поставок.

В таблице 7 построен начальный опорный план методом минимального элемента.

 

Табл. 7.

              Ui
      - 8     +2 * U1=0
  - 9   + 5       U2′=-3
  + 7         - 1 U3= -5
Vj V1′=12 V1′′=4 V2=8 V3=6 V4′=11 V5= 6  

 
 

Число занятых клеток равно 8, совпадает с m+n-1=3+6-1=8- опорный план-невырожденный. Для исследования плана на оптимальность необходимо найти оценки свободных клеток. Для этого надо знать потенциалы Ui и Vj, которые определим в результате решения системы уравнений,

составленных по заполненным клеткам. Получаем


Найдём оценки свободных клеток:


Поскольку среди оценок имеются отрицательные, то план неоптимален и его можно улучшить, занимая клетку (1,5). В таблице 7для этой клетки построен замкнутый контур, по которому находим величину


Для занимаемой клетки (1,5). Прибавляя λ в положительных клетках и вычитая в отрицательных, получаем новый опорный план, содержащийся в табл.8.

              Ui
              U1=0
              U2′= -3
              U3= -1
Vj V1′=8 V1′′=4 V2=8 V3=6 V4′=7 V5= 2  

 

Найдём оценки свободных клеток:

 
 

Клеток с отрицательными оценками в табл. 8 нет. Следовательно, в ней содержится оптимальный план, причём

Х 24* = Х 24+100=0+100=100; Х 11* = Х 11′+ Х 11′′=0+150=150; Х 21* = Х 21′+ Х 21′′=0+0=0;

Х 31* = Х 31′+ Х 31′′=200+0=200;

 
 

 

Этому плану соответствуют минимальные суммарные затраты:


По этому плану перевозок завод А1 должен 150 ед. продукции доставить на склад В1; 50 ед. продукции доставить на склад В2; 150 ед. продукции доставить на склад В3; завод А2 должен 200 ед. продукции доставить на склад В2 и 100 ед. продукции доставить на склад В4; завод А3 должен 200 ед. продукции доставить на склад В1; 150 ед. продукции доставить на склад В4. При этом суммарные затраты будут минимальными и составят 5850 ден. ед.

Нераспределённая продукция в объёме 50 ед. останется на заводе А1 и 150 ед. останется на заводе А3.

При соблюдении дополнительного условия, что из пункта отправления А2 в пункт назначения В4 должно быть перевезено не менее 100 ед. продукции, а из пункта отправления А1 в пункт назначения В1 должно быть перевезено не более 150 ед. продукции, минимальные суммарные затраты увеличиваются на

5850-5350=500 ден. ед.

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2019-03-02 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: