Студопедия

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

Разделы сайта

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






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






Таблица 2.1.21

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

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

Таблица 2.1.22

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11
X5 20/3             -1/3 -2/3   -5/3 -5/3
X1 17/3             -1/3 -2/3   1/3 -5/3
X6 5/3             -4/3 -2/3   4/3 -8/3
X4 1/3             1/3 -1/3   -1/3 -1/3
X9 2/3             -1/3 -2/3   1/3 -5/3
X2                     -1  
X3                       -1
Y -58/3             2/3 10/3   1/3 13/3

Решение данной задачи: Y=-58/3; X=(17/3; 2; 2; 1/3; 20/3; 5/3; 0; 0; 2/3; 0; 0)

 

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

 

Для образования порожденных задач выберем переменную x1

 

Задача №8:

Добавляется ограничение x1≥ 6

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

x9=-3-(-1*X1-2*X2+0*X3+0*X4)

x6=-9-(-2*X1+0*X2+0*X3+2*X4)

x7=-5-(-1*X1-1*X2+1*X3+2*X4)

x8=-2-(-1*X1+0*X2+2*X3-1*X4)

x9=-5-(-1*X1+0*X2+0*X3+0*X4)

x10=-2-(0*X1-1*X2+0*X3+0*X4)

x11=-2-(0*X1+0*X2-1*X3+0*X4)

x12=-6-(-1*X1+0*X2+0*X3+0*X4)

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

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

Таблица 2.1.23

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

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

Таблица 2.1.24

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

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

Таблица 2.1.25

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12
X5 11/2       -1   -1/2       -2    
X1 9/2       -1   -1/2            
X7 3/2           -1/2       -1    
X8 5/2       -2   -1/2            
X9 -1/2       -1   -1/2            
X2                     -1    
X11 -2     -1                  
X12 -3/2       -1   -1/2            
Y -20     -3                  

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

Таблица 2.1.26

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12
X5 11/2       -1   -1/2       -2    
X1 9/2       -1   -1/2            
X7 -1/2           -1/2       -1    
X8 -3/2       -2   -1/2            
X9 -1/2       -1   -1/2            
X2                     -1    
X3                       -1  
X12 -3/2       -1   -1/2            
Y -14                     -3  

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

Таблица 2.1.27

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

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

Таблица 2.1.28

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

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

Таблица 2.1.29

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

Решение данной задачи: Y=-20; X=(6; 2; 2; 0; 7; 3; 1; 0; 1; 0; 0; 0)

 

Задача №9:

Добавляется ограничение x1≤ 5

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

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

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

x7=-5-(-x1-x2+x3+2x4)

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

x9=-5-(-x1+0x2+0x3+0x4)

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

x11=-2-(0x1+0x2-x3+0x4)

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

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

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

Таблица 2.1.30

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

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

Таблица 2.1.31

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

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

Таблица 2.1.32

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10 X11 X12
X5 11/2       -1   -1/2       -2    
X1 9/2       -1   -1/2            
X7 3/2           -1/2       -1    
X8 5/2       -2   -1/2            
X9 -1/2       -1   -1/2            
X2                     -1    
X11 -2     -1                  
X12 1/2           1/2            
Y -20     -3                  

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






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.