Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Решение задачи методом ветвей и границ 3 страница. Таблица 2.34 БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12 X5 -2






Таблица 2.34

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12
X5       -2               -2  
X6                   -5   -3  
X2                     -1    
X8       -3             -2 -2  
X4                   -1      
X7       -4           -1 -5 -1  
X1                       -1  
X12                          
Y -21                 -2      

Используем обычный симплекс-метод. Вводим в базис X9, выводим из базиса X12.

Таблица 2.35

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12
X5       -2               -2 -3
X6                       -3  
X2                     -1    
X8       -3             -2 -2  
X4                          
X7       -4             -5 -1  
X1                       -1  
X9                          
Y -21                        

Решение оптимально.

Задача №7 - к исходным данным задачи №4 добавляется ограничение Х1< =5.

Выразим допустимый базис в форме Таккера;

x5=3-(-2x1+2x2-2x3+3x4)

x6=-2-(-3x1+0x2+3x3-5x4)

x7=-11-(-1x1-5x2-4x3-1x4)

x8=-10-(-2x1-2x2-3x3+0x4)

x9=-4-(0x1+0x2+0x3-1x4)

x10=-1-(0x1-1x2+0x3+0x4)

x11=5-(1x1+0x2+0x3+0x4)

Целевая функция в форме Таккера:

Y=0-(4x1+5x2+17x3-2x4)

Таблица 2.36

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
X5   -2   -2                
X6 -2 -3     -5              
X7 -11 -1 -5 -4 -1              
X8 -10 -2 -2 -3                
X9 -4       -1              
X10 -1   -1                  
X11                        
Y         -2              

Используем двойственный симплекс-метод. Вводим в базис X2, выводим из базиса X7.

Таблица 2.37

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
X5 -7/5 -12/5   -18/5 13/5     2/5        
X6 -2 -3     -5              
X2 11/5 1/5   4/5 1/5     -1/5        
X8 -28/5 -8/5   -7/5 2/5     -2/5        
X9 -4       -1              
X10 6/5 1/5   4/5 1/5     -1/5        
X11                        
Y -11       -3              

Используем двойственный симплекс-метод. Вводим в базис X1, выводим из базиса X8.

Таблица 2.38

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
X5       -3/2         -3/2      
X6 17/2     45/8 -23/4     3/4 -15/8      
X2 3/2     5/8 1/4     -1/4 1/8      
X1 7/2     7/8 -1/4     1/4 -5/8      
X9 -4       -1              
X10 1/2     5/8 1/4     -1/4 1/8      
X11 3/2     -7/8 1/4     -1/4 5/8      
Y -43/2     83/8 -9/4     1/4 15/8      

Используем двойственный симплекс-метод. Вводим в базис X4, выводим из базиса X9.

Таблица 2.39

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
X5 -1     -3/2         -3/2      
X6 63/2     45/8       3/4 -15/8 -23/4    
X2 1/2     5/8       -1/4 1/8 1/4    
X1 9/2     7/8       1/4 -5/8 -1/4    
X4                   -1    
X10 -1/2     5/8       -1/4 1/8 1/4    
X11 1/2     -7/8       -1/4 5/8 1/4    
Y -25/2     83/8       1/4 15/8 -9/4    

Используем двойственный симплекс-метод. Вводим в базис X8, выводим из базиса X5.

Таблица 2.40

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
X8 2/3         -2/3   -2/3   -4/3    
X6 131/4     15/2   -5/4   -1/2   -33/4    
X2 5/12     2/4   1/12   -1/6   5/12    
X1 59/12     3/2   -5/12   -1/6   -13/12    
X4                   -1    
X10 -7/12     2/4   1/12   -1/6   5/12    
X11 1/12     -6/4   5/12   1/6   13/12    
Y -55/4     17/2   5/4   3/2   1/4    

Используем двойственный симплекс-метод. Вводим в базис X7, выводим из базиса X10.

Таблица 2.41

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
X8       -1   -1       -3 -4  
X6 69/2         -3/2       -19/2 -3  
X2                     -1  
X1 11/2         -1/2       -3/2 -1  
X4                   -1    
X7 7/2     -3   -1/2       -5/2 -6  
X11 -1/2     -1   1/2       3/2    
Y -19                      

Используем двойственный симплекс-метод. Вводим в базис X3, выводим из базиса X11.

Таблица 2.42

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
X8 7/2         -3/2       -9/2 -5 -1
X6 63/2         3/2       -1/2    
X2                     -1  
X1                        
X4                   -1    
X7           -2       -7 -9 -3
X3 1/2         -1/2       -3/2 -1 -1
Y -51/2         17/2       47/2    

Решение оптимально. Остановка: текущее значение целевой функции < =-21.

Задача №5 - к исходным данным задачи №2 добавляется ограничение Х2< =0.

Выразим допустимый базис в форме Таккера:

x5=3-(-2x1+2x2-2x3+3x4)

x6=-2-(-3x1+0x2+3x3-5x4)

x7=-11-(-1x1-5x2-4x3-1x4)

x8=-10-(-2x1-2x2-3x3+0x4)

x9=-4-(0x1+0x2+0x3-1x4)

x10=0-(0x1+1x2+0x3+0x4)

Целевая функция в форме Таккера:

Y=0-(4x1+5x2+17x3-2x4)

Таблица 2.43

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X5   -2   -2              
X6 -2 -3     -5            
X7 -11 -1 -5 -4 -1            
X8 -10 -2 -2 -3              
X9 -4       -1            
X10                      
Y         -2            

Используем двойственный симплекс-метод. Вводим в базис X2, выводим из базиса X7.

Таблица 2.44

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X5 -7/5 -12/5   -18/5 13/5     2/5      
X6 -2 -3     -5            
X2 11/5 1/5   4/5 1/5     -1/5      
X8 -28/5 -8/5   -7/5 2/5     -2/5      
X9 -4       -1            
X10 -11/5 -1/5   -4/5 -1/5     1/5      
Y -11       -3            

Используем двойственный симплекс-метод. Вводим в базис X1, выводим из базиса X8.

Таблица 2.45

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X5       -3/2         -3/2    
X6 17/2     45/8 -23/4     3/4 -15/8    
X2 3/2     5/8 1/4     -1/4 1/8    
X1 7/2     7/8 -1/4     1/4 -5/8    
X9 -4       -1            
X10 -3/2     -5/8 -1/4     1/4 -1/8    
Y -43/2     83/8 -9/4     1/4 15/8    

Используем двойственный симплекс-метод. Вводим в базис X4, выводим из базиса X9.

Таблица 2.46

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X5 -1     -3/2         -3/2    
X6 63/2     45/8       3/4 -15/8 -23/4  
X2 1/2     5/8       -1/4 1/8 1/4  
X1 9/2     7/8       1/4 -5/8 -1/4  
X4                   -1  
X10 -1/2     -5/8       1/4 -1/8 -1/4  
Y -25/2     83/8       1/4 15/8 -9/4  

Используем двойственный симплекс-метод. Вводим в базис X8, выводим из базиса X5.

Таблица 2.47

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X8 2/3         -2/3   -2/3   -4/3  
X6 131/4     15/2   -5/4   -1/2   -33/4  
X2 5/12     2/4   1/12   -1/6   5/12  
X1 59/12     3/2   -5/12   -1/6   -13/12  
X4                   -1  
X10 -5/12     -2/4   -1/12   1/6   -5/12  
Y -55/4     17/2   5/4   3/2   1/4  

Используем двойственный симплекс-метод. Вводим в базис X9, выводим из базиса X10.

Таблица 2.48

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
X8       13/5   -2/5   -6/5     -16/5
X6       87/5   2/5   -19/5     -99/5
X2                      
X1       14/5   -1/5   -3/5     -13/5
X4       6/5   1/5   -2/5     -12/5
X9       6/5   1/5   -2/5     -12/5
Y -14     41/5   6/5   8/5     3/5

Решение оптимально.


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

mylektsii.su - Мои Лекции - 2015-2024 год. (0.013 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал