Главная Обратная связь

Дисциплины:

Архитектура (936)
Биология (6393)
География (744)
История (25)
Компьютеры (1497)
Кулинария (2184)
Культура (3938)
Литература (5778)
Математика (5918)
Медицина (9278)
Механика (2776)
Образование (13883)
Политика (26404)
Правоведение (321)
Психология (56518)
Религия (1833)
Социология (23400)
Спорт (2350)
Строительство (17942)
Технология (5741)
Транспорт (14634)
Физика (1043)
Философия (440)
Финансы (17336)
Химия (4931)
Экология (6055)
Экономика (9200)
Электроника (7621)






Завдання 3 Розв´язання транспортної задачі



Є три постачальники і чотири споживачі однорідного продукту. Потужності постачальників і попити споживачів, а також витрати на перевезення одиниці вантажу для кожної пари «постачальник-споживач» зведені в таблицю 11 постачань.

Задача у наступному: знайти об'єми перевезень для кожної пари «постачальник-споживач» так, щоб:

1) потужності всіх постачальників були реалізовані;

2) попити всіх споживачів були задоволені;

3) сумарні витрати на перевезення були мінімальні.

Таблиця 11–Потужності постачальників і попити споживачів, витрати на перевезення одиниці вантажу

  Споживачі Потужність постачальників ai
B1 B2 B3 B4
Постачальники A1
A2
A3
Попит bj

Розв´язок

Поставлено збалансовану транспортну задачу, оскільки сумарний попит дорівнює сумарній потужності постачальників ® 280.

Для отримання начального опорного плану перевезень скористаємось методом мінімального елемента.

Для покращення будемо використовувати таблицю 12, у правому верхньому кутку якої стоїть тариф відповідного перевезення, а у лівому нижньому кутку – плановий обсяг перевезення.

Знаходимо в таблиці клітинки з найменшим тарифом. Таких клітин дві- (1;1) і (2;1) із тарифом, що дорівнює 1. Порівнюємо максимально можливі постачання для цих клітинок: для клітинки (1;1) x11=min{60,20}=20, для клітинки (2;1) x21=min{120,20}=20. Оскільки їх значення збігаються, то максимально можливе постачання записуємо в будь-яку з них. Наприклад, записуємо постачання, що дорівнює 20 од. у клітинку (2;1). У результаті попит першого споживача задоволений і перший стовпець таблиці постачань випадає

з наступного розгляду, а виробничу потужність для другого рядка зменшуємо на 20 од. Аналогічним способом продовжуємо заповнювати невикреслені

Таблиця 12– Отримання начального опорного плану перевезень

ai
           
      60          
       
          100  
         
    50   40   10  
bj

 



клітинки таблиці. У останній клітинці попит і пропозиція повинні збігтися, оскільки розглядається збалансована задача. Слід зазначити, що в таблиці повинна бути заповнена n+m-1 клітинка перевезень ( де n - число постачальників, m- число споживачів ).

Наприклад, для розглянутої задачі повинно бути заповнено 3+4-1=6 клітин. Остаточно одержуємо початковий опорний план перевезень.

Тепер скористаємося методом потенціалів, усі розрахунки виконаємо у таблиці 13. Для цього кожному стовпцю припишемо потенціал vj , а кожному рядку - потенціал ui. Для кожної заповненої клітини складемо лінійне рівняння за правилом ui+vj=cij, де cij - тариф відповідного перевезення. Потім розв’яжемо систему 6-ти рівнянь.

Оскільки в рівняннях буде 7 невідомих (3 потенціали u і 4 потенціали v), то довільний потенціал можна дорівняти до нуля.

Тепер для кожної незаповненої клітинки необхідно знайти оцінку Dij= ui+vj-cij. Якщо всі оцінки будуть негативними або нульовими, то початковий опорний план є оптимальним.

 

Таблиця 13– Розрахунки методом потенціалів

ai
V1=3 V2=3 V3=7 V4=4
  U1=-1   -1    
               
  U2=-2   -5      
           
  U3=0 -3        
         
bj  

D11=-1+3-1=1; D13=-1+7-5=1; D14=-1+4-3=0; D22=-2+3-6=-5; D23=-2+7-5=0; D31=0+3-6= -3. Оцінки D11 і D13 позитивні, отже, отримане початкове опорне розв’язання не оптимальне. З оцінок вибираємо найбільшу– D11, отже, у клітинку (1;1) будемо заносити ненульове перевезення. Заносимо в клітинку (1;1) знак «+» і будуємо ланцюг потенціалів, що може проходити тільки по заповнених клітинках, із чергуванням знаків «+» і «-» і повертається у вихідну незаповнену клітину, таблиця 14.



Cеред клітинок, позначених мінусом, вибираємо ту, що містить найменше перевезення.Це клітинка (3;4) з К=Х34 =10. У подальших обчисленнях ця клітинка буде вважатися незаповненою, тому що далі вміст вибраної клітинки,10, додаємо до вмісту клітинок, що позначені «+», і віднімаємо з клітинок, що позначені «-».У таблиці 15 повинна виявитися, як і раніше, n+m-1

Таблиця 14– Перехід до іньшого опорного плану з використанням ланцюга потенціалів

  ai
V1 V2 V3 V4
U1            
+   -          
  U2            
-         + 100  
U3          
    +       -  
bj  

заповнена клітинка. Перевіряємо отриманий опорний план на оптимальність.

Таблиця 15– Отриманий опорний план

  3 4 ai
V1=2 V2=3 V3=7 V4=3
  U1=-1     -1    
  -   +      
U2=-1   -4      
           

Продовження таблиці 15

       
 
 
   


U3=0 -4     -1  
    +   -      
bj  

D13=1; D14=-1; D22= -4; D23=1; D31= -4; D34= -1.

Тому що є дві клітини (1;3) і (2;3) з позитивними оцінками, то отриманий опорний план, таблиця 15, не оптимальний. Знайдемо новий опорний план з використанням ланцюга потенціалів, таблиця 15.

Оскільки дві позитивні оцінки набувають однакових позитивних значень, D13=D23=1, то можна занести ненульове перевезення або в клітинку (1;3), або в клітинку (2;3). Якщо у ланцюг будє включено клітинку (1;3),таблиця 15, то це перевезення буде дорівнювати 40 од.. Таким чіном одержано новий опорний план, таблиця 16.

Таблиця 16– Оптимальний опорний план

ai
V1=1 V2=2 V3=5 V4=2
  U1=0       -1    
         
  U2=0   -4      
           

Продовження таблиці 16

  U3=1 -4   -1 -1  
             
bj  

 

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

D14= -1; D22= -4; D23= 0; D31= -4; D33= -1; D34= -1.

 

Оскільки серед оцінок немає позитивних, можна сказати, що отриманий опорний план є оптимальним, але не єдиним (D23= 0).

У підсумку підприємствам можна запропонувати наступний план перевезень:

При такому розподілі перевезень потужності всіх постачальників будуть реалізовані, попит усіх споживачів задоволений, сумарні витрати складуть:

грош. од.

 


Эта страница нарушает авторские права

allrefrs.ru - 2019 год. Все права принадлежат их авторам!