Студопедия

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

КАТЕГОРИИ:

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






Решение задачи методом ветвей и границ 2 страница






Таблица 2.22

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

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

Таблица 2.23

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
X9 1/3     -2/3   1/3         2/3 -2/3
X6 113/3     -1/3   5/3         10/3 -19/3
X2                     -1  
X8       -3             -2 -2
X4 13/3     -2/3   1/3         2/3 -2/3
X7 13/3     -14/3   1/3         -13/3 -5/3
X1                       -1
Y -61/3     47/3   2/3         19/3 8/3

Решение оптимально. Решение данной задачи не удовлетворяет требованиям целочисленности, поэтому необходимо простроить две порождённые задачи. Для образования порожденных задач выберем переменную Х4.

Задача №8 - к исходным данным задачи №6 добавляется ограничение Х4> =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=-6-(-1x1+0x2+0x3+0x4)

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

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

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

Таблица 2.24

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12
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 -6 -1                      
X12 -5       -1                
Y         -2                

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

Таблица 2.25

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12
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 -6 -1                      
X12 -5       -1                
Y -11       -3                

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

Таблица 2.26

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

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

Таблица 2.27

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

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

Таблица 2.28

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

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

Таблица 2.29

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

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

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

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

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=-6-(-1x1+0x2+0x3+0x4)

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

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

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

Таблица 2.30

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12
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 -6 -1                      
X12                          
Y         -2                

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

Таблица 2.31

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12
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 -6 -1                      
X12                          
Y -11       -3                

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

Таблица 2.32

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

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

Таблица 2.33

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

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


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

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