Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Розв’язання транспортних задач

⇐ Предыдущая61626364656667686970Следующая ⇒


9.3.1. Розв’язати методом потенціалів нижченаведені Т- задачі.

1) a\b           2) a\b          
                           
                           
                           
                           
3) A\b           4) a\b          
                           
                           
                           
                           
5) a\b           6) a\b          
                           
                           
                           
                           
7) a\b           8) a\b          
                           
                           
                           
                           
9) a\b           10) a\b          
                           
                           
                           
                           
                                     

Відповіді: 1) L (x*) = 575. 2) L (x*) = 710. 3) L (x*) = 360. 4) L (x*) = 910.

5) L (x*) = 750. 6) L (x*) = 200. 7) L (x*) = 209.

8) L (x*) = 184. 9) L (x*) = 285. 10) L (x*) = 785.

9.3.2. Розв’язати Т-задачі з обмеженням пропускної здатності

1)                        
  C =         , R =         ,
                         

a = (74, 33, 19), b = (28, 70, 15, 13);

2)                        
  C =         , R =         ,
                         

a = (63, 72, 17), b = (33, 40, 43, 36);

3)                        
  C =         , R =         ,
                         

a = (13, 79, 34), b = (49, 30, 22, 25);

4)                        
  C =         , R =         ,
                         

a = (20, 76, 54), b = (40, 30, 52, 28);

5)                        
  C =         , R =         ,
                         

a = (64, 75, 21), b = (57, 33, 44, 26);

6)                        
  C =         , R =         ,
                         

a = (42, 99, 27), b = (68, 40, 30, 30);

7)                        
  C =         , R =         ,
                         

a = (78, 37, 53), b = (38, 60, 30, 40);

8)                        
  C =         , R =         ,
                         

a = (77, 24, 70), b = (56, 30, 40, 45);

9)                        
  C =         , R =         ,
                         

a = (72, 29, 68), b = (65, 24, 50, 30);

10)                        
  C =         , R =         ,
                         

a = (53, 45, 38), b = (21, 30, 75, 10).

Відповіді: 1) L (x*) = 444. 2) L (x*) = 538. 3) L (x*) = 413. 4) L (x*) = 837. 5) L (x*) = 1091.

6) L (x*) = 700. 7) L (x*) = 800. 8) L (x*) = 885. 9) L (x*) = 1134. 10) L (x*) = 649.

9.3.3. Розв’язати задачі про оптимальні призначення (угорський метод):

1)               2)              
                               
                               
                               
                               
                               
                               
3)               4)              
                               
                               
                               
                               
                               
                               
5)               6)              
                               
                               
                               
                               
                               
                               
7)               8)              
                               
                               
                               
                               
                               
                               
9)               10)              
                               
                               
                               
                               
                               
                               

Відповіді: 1) L (x*) = 16. 2) L (x*) = 24. 3) L (x*) = 25.

4) L (x*) = 38. 5) L (x*) = 24. 6) L (x*) = 25.

7) L (x*) = 81. 8) L (x*) = 73. 9) L (x*) = 60. 10) L (x*) = 68.

9.3.4. Розв’язати методом Мака задачі про оптимальні призначення. Умови варіантів задач про оптимальні призначення такі ж як і у попередньому завданні.

9.3.5.Розв’язати методом Форда-Фалкерсона задачі про максимальний потік в мережах, що задані матрицями суміжностей C i пропускних здатностей R. У всіх задачах джерелом потоку є вершина 1, а стоком потоку – вершина 6.

1)                                
                                 
  C =             , R =             ;
                                 
                                 
                                 
2)                                
                                 
  C =             , R =             ;
                                 
                                 
                                 
3)                                
                                 
  C =             , R =             ;
                                 
                                 
                                 
4)                                
                                 
  C =             , R =             ;
                                 
                                 
                                 
5)                                
                                 
  C =             , R =             ;
                                 
                                 
                                 
6)                                
                                 
  C =             , R =             .
                                 
                                 
                                 

Відповіді: 1) d* = 28. 2) d* = 44. 3) d* = 55.

4 ) d* = 51. 5) d* = 68. 6) d* = 61.

9.3.6. Розв’язати методом Мiнтi задачі про найкоротший шлях в наведених нижче мережах, кожна з яких задається числом вершин N =10 i матрицею L, що описує множину дуг (кожний стовпець цієї матриці відповідає існуючій дузі мережі, при цьому, перший елемент стовпця є початок дуги, другий – кінець дуги, третій – довжина дуги):

                                     
                                     
                                     
                                       
                                       
                                       
                                       
                                       
                                       
                                     
                                     
                                     
                                       
                                       
                                       
                                       
                                       
                                       

9.4 Розв’язання задач цілочислового програмування

9.4.1. Розв’язати нижченаведені задачі методом Гоморi-1. В усіх нижченаведених задачах всі змінні невід’ємні та цілі.

1) 5 x1+ 6 x2+ 6 x3 min, 2) 6 x1+ 4 x2 min,
  2 x1+ 4 x2 10,   2 x1+ x2 3,
  3 x1+ 2 x2+ 2 x3 10;   x1– x2 1;
3) 6 x1+ 4 x2 min, 4) x1+ x2 min,
  2 x1+ x2 3,   – x1– x2 + x5= –1,
  x1– 2 x2 2,   –2 x1+ 2 x2+ x3 = –2,
  3 x1+ 2 x2 1;   –4 x1+ 2 x2 + x4 = –1;
5) 6 x1+ 4 x2 min, 6) 2 x1+ 3 x2 min,
  2 x1+ x2 3,   x1+ 2 x2 16,
  x1– x2 1;   2 x1+ x2 16;
7) 5 x1 – 3 x2 max, 8) 5 x2 + 7 x4 min,
  3 x1 + 2 x2 6,   – 10 x2+ x3+ x4 = –16,
  2 x1 – 3 x2 – 6,   x1– 3 x2 – 3 x4 = –12,
  x1– x2 4,   – 6 x2 – 2 x4+ x5= –17;
9) – 5 x4– 7 x5 max, 10) 8 x1+ 2 x2 max,
  x1 – x4– 2 x5= – 7,   x1– 4 x2+ x3 = 4,
  – x3+ 3 x4– 6 x5= – 3,   – 4 x1+ x2 + x4 = 4,
  x2 – x4– 4 x5= –11;   x1+ x2 + x5 = 6.

Відповіді: 1) x * = (3; 1; 0), L (x*) = 21. 2) x * = (1; 1), L (x*) = 10.

3) x * = (1; 1), L (x*) = 10. 4) x * = (1; 0; 0; 3; 0), L (x*) = 1.

5) x * = (2; 0), L (x*) = 12. 6) x * = (6; 5), L (x*) = 27.

7) x * = (18; 14), L (x*) = 48. 8) x * = (0; 4; 24; 0; 7), L (x*) = 20.

9) x * = (0; 0; 0; 3; 2), L (x*) = -29. 10) x * = (5; 1; 0; 0; 0), L (x*) = 42.

9.4.2. Розв’язати методом Гоморi-2 задачі частково дискретного ЛП:

1) x1+ 8 x2 max, 2) – 6 x1– x2 min,
  3 x1+ x2 9,   – 2,9 x1+ 6 x2 17,4,
  0,16 x1+ x2 1,9,   3 x1– x2 1,
  xj 0, xj– ціле, j = 1,2;   xj 0, xj– ціле, j = 1,2;
3) 0,25 x1+ x2 max, 4) – 2 x1– 4 x2 min,
  0,5 x1+ x2 1,75,   2 x1+ x2 19,33,
  x1+ 0,3 x2 1,5,   x1+ 3 x2 10,
  xj 0, xj– ціле, j = 1,2;   xj 0, xj– ціле, j = 1,2;
5) x1+ x2 max, 6) x1+ x2 max,
  2 x1+ 11 x2 38,   2 x1+ 11 x2 38,
  x1+ x2 7,   x1+ x2 7,
  4 x1– 5 x2 5,   4 x1– 5 x2 5,
  xj 0, j = 1,2, x2– ціле;   xj 0, j = 1,2, x1– ціле;
7) x1 max, 8) – 8 x1– 6 x2 min,
  x1+ 3 x2 12,   3 x1+ 5 x2+ x3 = 11,
  3 x1– 8 x2 24,   4 x1+ x2 + x4= 8,
  xj 0, j = 1,2, x1– ціле;   xj 0, j = 1,2, x1– ціле.

Відповіді: 1) x * = (2; 1), L (x*) = 10. 2) x * = (1; 3), L (x*) = 9.

3) x * = (1; 1), L (x*) = 1,25. 4) x * = (7; 1), L (x*) = 18.

5) x * = (3,75; 2), L (x*) = 5,75. 6) x * = (4; 2,73), L (x*) = 6,73.

7) x * = (9; 0.38), L (x*) = 9. 8) x * = (1; 1,6; 0; 2,41), L (x*) = 17,6.

9.4.3. Розв’язати методом Гоморi-3 нижченаведені задачі дискретного ЛП. В усіх задачах всі змінні невід’ємні та цілі.

1) – x1– 5 x2 max, 2) 3 x1+ 2 x2 min, 3) x1+ 3x2 min,  
  12 x1– 3 x2 8,   – 3 x2 2,   x1+ 6x2 5,  
  – 3 x1+ 9 x2 8,   – 2 x1+ 2 x2 2,   – 5x1+ 19x2 13,  
  – x1+ 3 x2 3;   2 x1– x2 1;   – 3x1+ 6x2 2;  
4) 7x1+ 12x2 min, 5) –3x1– 8x2 max, 6) 10x1+ 7x2 min,  
  4x1– 23x2 –14,   –2x1+ 10x2 4,   2x1– 12x2 –9,  
  –12x1+ 2x2 –9,   –3x1– 5x2 –10,   x1+ 4x2 10,  
  –13x1– x2 –10;   2x1– x2 2;   4x1– 2x2 14;  
7) – 3 x4– 2 x5 max, 8) 3 x2 + x5 min,
  x1 – 5 x4+ x5= –15,   – 2 x2+ x3 – 18 x5= –20,
  x3+ x4– 8 x5= – 9,   x1+ x2 – 15 x5= – 7,
  x2 – x4– 10 x5= –19;   – 5 x2 + x4+ x5= – 9.
                     

Відповіді: 1) x * = (2; 2), L (x*) = –12. 2) x * = (1; 0), L (x*) = 3.

3) x * = (0; 1), L (x*) = 3. 4) x * = (1; 1), L (x*) = 19.

5) x * = (2; 1), L (x*) = –14. 6) x * = (5; 2), L (x*) = 64.

7) x * = (3; 5; 3; 4; 2), L (x*) = –16. 8) x * = (6; 2; 2; 0; 1), L (x*) = 7.

9.4.4. Розв’язати методом гілок та границь задачі цiлочислового ЛП. В усіх задачах виконуються умови: xj 0, xj – цілі, j= 1,2.

1) x1 + x2 max, 2) –2 x1– x2 min, 3) 6 x1+ 4 x2 min,
  2 x1+ 11 x2 38,   6 x1+ 4 x2 24,   2 x1+ x2 3,
  x1+ x2 7,   x1– x2 3,   x1– 2 x2 2,
  4 x1– 5 x2 5;   – x1+ 3 x2 3;   3x1+ 2x2 1;
4) x1+ x2 min, 5) 5 x1+ 7 x2 min, 6) 2 x1– x2 max,
  – x1 – x2 – 1,   – 10 x1 + x2 – 16,   2 x1+ x2 8,
  – 2 x1+ 2 x2 – 2,   – 3 x1– 3 x2 – 12,   x1+ 3 x2 6,
  – 4 x1+ 2 x2 – 1;   – 6 x1–2 x2 – 17,   3 x1 + x2 3;
7) x1+ 4 x2 min, 8) –5 x1–7 x2 max, 9) x1+ 2 x2 min,
  x1– 3 x2 –1,   2 x1+ x2 3,   2 x1+ 2 x2 5,
  8 x1– x2 6,   20 x1– x2 15,   x1– 3 x2 – 1,
  3 x1– 11 x2 –7;   x1– x2 –2;   x1– x2 2.
                   

Відповіді: 1) x * = (3; 2) або x * = (2; 3), L (x*) = 5.

2) x * = (3; 1), L (x*) = –7. 3) x * = (1; 1), L (x*) = 10.

4) x * = (1; 0), L (x*) = 1. 5) x * = (4; 0), L (x*) =20.

6) x * = (3; 1), L (x*) = 5. 7) x * = (1; 1), L (x*) = 5.

8) x * = (1; 3), L (x*) = –26. 9) x * = (4; 2), L (x*) = 8.

⇐ Предыдущая61626364656667686970Следующая ⇒


Дата публикования: 2015-09-18; Прочитано: 735 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!

studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.02 с)...