Лекции.Орг


Поиск:




Зіставлення методу потенціалів i симплекс-методу




Проiлюструємо зв’язок мiж методом потенцiалiв i симплекс-методом на
прикладi розв’язання такої задачi:

             
       
             
       
       

Будемо розв’язувати її паралельно методом потенцiалiв i симплекс-методом. Знайдемо початковий розв’язок методом північно-західного кута.

  v 1=5 v 2=10 v 3=18      
                   
u 1=0          
                   
                   
u 2=-6          
  -7                
             
         
               

Записуємо задачу у вигляді системи:

min z=5x11+10x12+7x13+6x21+4x22+12x23 ;

x11+ x12+ x13 =5; (5.21)

x21 + x22+ x23=10; (5.22)

x11 + x21 =3; (5.23)

x12 + x22 =7; (5.24)

x13 + x23=5; (5.25)

x11,x12,x13,x21,x22,x23 ³0.

Вилучимо перше рівняння й зведемо систему до діагонального вигляду відносно змінних x 11, x 12, x 22, x 23:

min z=5x11+10x12+7x13+6x21+4x22+12x23;

x11+ x21 =3; (5.21a)

x13 + x23 =5; (5.22a)

-x13 + x21+ x22 =5; (5.23a)

x12+ x13 - x21 =2; (5.24a)

x11,x12,x13,x21,x22,x23 ³0.

Примітка:

(5.21a)=(5.23)

(5.22a)=(5.25)

(5.23a)=(5.22)—(5.25)

(5.24a)=(5.24)+(5.25)—(5.22)

Далi наводимо транспортну таблицю i симплекс-таблицю для вiдповiдного кроку:

v 1=5 Ý v 2=10 v 3=18                      
                  БП x 11 x 12 x 13 x 21 x 22 x 23 Р
u 1 =0     x 13       z       -7      
        Å       x 11              
                  x 12       -1      
u 2=-6               x 22     -1        
  -7     Å         x 23              
          Z=115                
v 1=5 v 2=-1 v 3=7                      
                  БП x 11 x 12 x 13 x 21 x 22 x 23 Р
u 1=0               z   -11          
  -11     Å       x 11              
                    x 13       -1      
u 2=5 x 21           x 22              
  Å             x 23   -1          
      5 ß   Z=93                
  v 1=5 V 2=3 v 3=7                      
                    БП x 11 x 12 x 13 x 21 x 22 x 23 Р
u 1=0 0               z   -7       -4  
      -7             x 11           -1  
                    x 13              
u 2=1             x 22              
          -4         x 21   -1          
          Z=81                

Як бачимо, між методом потенціалів та симплекс-методом існує взаємо­однозначний зв’язок.

Задачi для самостійної роботи

Задача 1. Три нафтопереробні заводи з максимальним щоденним виробничим обсягом 6, 5 та 8 млн галонів бензину постачають три бензосховища, потреби яких складають 4, 8 та 7 млн галонів. Бензин транспортується до бензосховищ трубопроводом. Вартість перекачування бензину на одну милю, розрахована з урахуванням довжини трубопроводу, складає 1 цент на 100 галонів. У таблиці відстаней вказано, що завод 1 не зв’язаний зі сховищем 3. Сформулюйте відповідну транс­портну задачу.

бензосховища
Заводи        
      -
       
       

Задача 2. Розв’яжіть транспортну задачу методом потенціалів двічі: перший раз початковий розв’язок знайдiть методом північно-західного кута, другий – методом найменшої вартостi. Порівняйте їх.

         
     
         
     
         
     
     

Задача 3. Розв’яжіть транспортну задачу методом потенціалів двічі: перший раз початковий розв’язок знайдiть методом північно-західного кута, другий – методом найменшої вартостi. Порівняйте їх.

         
     
         
     
         
     
         
     
     
           

Задача 4. Розв’яжіть транспортну задачу методом потенціалів. Початковий розв’язок знайдіть методом північно-західного кута.

             
       
             
       
             
       
       

Задача 5. Розв’яжіть транспортну задачу методом потенціалів. Початковий розв’язок знайдiть методом найменшої вартостi.

                 
         
                 
         
                 
         
                 
         
         

Задача 6. Розв’яжіть транспортну задачу методом потенціалів та симплекс-методом, а також покажіть, що між ітераціями цих методів існує взаємооднозначна відповідність. Початковий розв’язок знайдiть методом північно-західного кута.

       
       
       
       

Задача 7. Розв’яжіть таку транспортну задачу:

             
             
             
             
             
             
       

Задача 8. Розв’яжіть транспортну задачу:

                     
                     
                     
                     
                     
                     
                     
                     
           

Задача 9. Розв’яжіть таку транспортну задачу:

                 
                 
                 
                 
                 
                 
                 
                 
         

Задача 10. Розгляньте оптимальну транспортну таблицю задачі 1 (табл. 5.9). У кожному з наведених випадків знайдіть зміни обсягу виробництва та попиту, за яких поточний розв’язок залишається допустимим.

1) вихідний пункт 1 – пункт призначення 1;

2) вихідний пункт 1 – пункт призначення 2;

3) вихідний пункт 2 – пункт призначення 2;

4) вихідний пункт 3 – пункт призначення 3.

Задача 11. Розв’яжiть задачу розподілу верстатів чотирьох різних типів за п'ятьма типами робіт. Нехай є 25, 30, 20 і 30 верстатів відповідних типів. П'ять типів робіт характеризуються 20, 15, 30, 10 і 25 операціями відповідно. На верстаті 4 не можна виконувати роботу 4. Виходячи з коефіцієнтів вартості операцій, наведених в таблиці, побудуйте модель оптимального розподілу верстатів за типами робіт.

Тип верстатів Тип робіт
           
           
           
           
        -  

Задача 12. У наведеній транспортній задачі сумарний попит переважає сумарний обсяг виробництва. Нехай штрафи за недопостачання одиниці продукції в пункти призначення 1, 2 і 3 дорівнюють 5, 3 і 2 відповідно. Знайдіть оптимальний розв’язок.

       
       
       
       

Задача 13. У деяких реальних умовах постановка транспортної задачi може ускладнюватися такими додатковими умовами:

а) з пункту в пункт перевезення здiйснити не можна;

б) з пункту виробництва в пункт споживання треба забезпечити перевезення точно одиниць продукцiї;

в) з пункту виробництва в пункт споживання треба завезти не менше ніж одиниць продукцiї;

г) з пункту виробництва в пункт споживання треба завезти не бiльше ніж одиниць продукцiї.

Для кожної з умов визначте, що треба зробити, щоб урахувати її при розв’язаннi транспортної задачi. Вiдповiдь подайте у виглядi транспортних таблиць.

Задача 14. У незбалансованій транспортній задачі призначається плата за зберігання кожної одиниці невивезеного товару з вихідного пункту й вантажу. Нехай коефіцієнти вартості зберігання вантажу у вихідних пунктах 1, 2 і 3 дорівнюють 5, 4 і 3 відповідно. Знайдіть оптимальний розв’язок, якщо весь обсяг вантажу вихідного пункту 2 має бути вивезений для того, щоб вивільнити місце для нової продукції.

       
       
       
       

Задача 15. Нехай у транспортній задачі розмірністю 3x3 через позначено кількість вантажу, що перевозиться з i в j, – коефіцієнт вартості відповідного перевезення. Обсяги виробництва у вихідних пунктах 1, 2 і 3 дорівнюють 15, 30 і 85 одиниць, а попит в пунктах призначення 1, 2 і 3 – 20, 30 і 80 одиниць. Припустимо, що початковий розв’язок, одержаний методом північно-західного кута, є оптимальним базисним розв’язком задачі. Відповідні значення потенціалів вихідних пунктів 1, 2 і 3 дорівнюють 2, 3 і 5, а значення потенціалів пунктів призначення 1, 2 і 3 – 2, 5 і 10.

1. Знайдіть сумарні транспортні видатки.

2. Вкажіть найменші значення для небазисних змінних, при яких розв’язок залишається оптимальним

Задача 16. Визначте початковий розв’язок транспортної задачі за допомогою
а) методу північно-західного кута; б) методу найменшої вартості; в) наближеного методу Фогеля. Знайдіть оптимальний розв’язок, виходячи з найкращого початкового розв’язку.

         
         
         
         
         
         

Задача 17. Повітряна лінія зв'язує два міста: А і В. Екіпаж, що формується в місті А (В) і вилітає у місто В (А), повинен здійснити зворотний рейс у місто А (В) в того самого або наступного дня. Екіпаж, що формується в А, можна призначити для зворотного рейсу в А за умови, якщо між часом прибуття у В і часом вильоту з В минуло не менше 90 хв. Задача полягає у складанні розкладу польотів, що мінімізує сумарний час простоїв усіх екіпажів. Розв’яжiть цю задачу про призначення, використовуючи такий розклад:

Рейс Виліт з А Приліт в В Рейс Виліт з В Приліт в А
  6:00 8:30   7:30 9:30
  8:15 10:45   9:15 11:15
  13:30 16:00   16:30 18:30
  15:00 17:30   20:00 22:00

Задача 18. Знайдіть найкоротший шлях між вершинами 1 і 7 у мережі, зображеній на рис. 5.2, сформулювавши задачу з проміжними пунктами. Відстані між різними вершинами вказано на дугах мережі.

Рис. 5.2

Задача 19. Директор ресторану, складаючи план роботи на чергові N днів, повинен попіклуватися про щоденний запас чистих серветок. Потреба ресторану в серветках за ці N днів дорівнює b1, b2,..., bN і може бути задоволена трьома різними шляхами:

1) покупкою нових серветок за ціною p1 центів;

2) пранням використаних серветок у пральні з терміном виконання 24 год за ціною p2 центів;

3) пранням використаних серветок у пральні з терміном виконання 48 год за ціною p 3 центів.

Сформулюйте цю задачу у виглядi транспортної.

Контрольнi запитання

1. Чи завжди можна збалансувати транспортну задачу?

2. Чи можуть для збалансування транспортної моделi одночасно бути потрiбнi як фiктивнi пункти виробництва, так i фiктивнi пункти споживання?

3. Який фiзичний змiст має кiлькiсть вантажу, що перевозиться з фiктивного пункту виробництва у пункти призначення?

4. Яка основна умова для застосування методу розв’язання транспортної задачі?

5. Зіставити кроки розв’язання транспортної задачi i симплекс-методу.

6. Чи будуть збігатися iтерацiї симплекс-методу i методу розв’язання транс­портної задачі, якщо використовується однаковий початковий базисний розв’язок?

7. Чи вiдрiзняється принципово процедура побудови замкнених циклiв, що використовується для вибору змiнної, яка виводиться з базису, у методi розв’язання транспортної задачі вiд тiєї, що використовується з аналогiчною метою в симплекс-методi при перевiрцi умови допустимостi?

8. Що являють собою потенцiали, якщо знайти їм вiдповiдники у ЗЛП?

9. Чи може вплинути на вибiр змiнної, що вводиться у базис, довiльний вибiр значення одного з потенцiалiв на iтерацiї розв’язання транспортної задачi?

10. Чи змiняться оптимальнi значення , якщо до всiх коефiцiєнтiв додати одне й те саме число?

11. Чи може збалансована транспортна модель не мати допустимих розв’язкiв?

12. Чи вироджений будь-який базисний розв’язок задачi про призначення?

13. Чи можна розв’язати задачу про призначення методом, що використовується для розв’язання транспортної задачі?

14. Якщо у транспортнiй моделi являють собою найменший коефiцiєнт вартостi перевезень з початкового пункту i в пункт призначення j, то чи мають транспортна задача i вiдповiдна їй задача з промiжними пунктами однаковий оптимальний розв’язок?





Поделиться с друзьями:


Дата добавления: 2015-10-01; Мы поможем в написании ваших работ!; просмотров: 477 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Победа - это еще не все, все - это постоянное желание побеждать. © Винс Ломбарди
==> читать все изречения...

783 - | 762 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.011 с.