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

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

Читайте также:
  1. Contents 1 страница
  2. Contents 10 страница
  3. Contents 11 страница
  4. Contents 12 страница
  5. Contents 13 страница
  6. Contents 14 страница
  7. Contents 15 страница

Таблица 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.

Дата добавления: 2015-09-07; просмотров: 87 | Нарушение авторских прав

Читайте в этой же книге: Решение задачи 1.2 | Решение задачи 1.3 | Решение задачи методом отсекающих плоскостей (метод Гомори) | Решение задачи методом отсекающих плоскостей (метод Гомори) | Решение задачи методом ветвей и границ | Определение вида квадратичной формы | Решение задачи методом Била | Решение задачи сепарабельным симплекс-методом | Переход от прямой задачи к двойственной | Интерфейс |
<== предыдущая страница | следующая страница ==>
Решение задачи методом ветвей и границ 1 страница| Решение задачи методом ветвей и границ 3 страница
mybiblioteka.su - 2015-2024 год. (0.011 сек.)