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

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

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

Согласно методу для каждой целочисленной переменной возможно задать верхнюю и нижнюю границу, в пределах которых содержится ее оптимальное значение. В данном случае нижняя граница равна . На практике верхний предел не вводят в виде дополнительного ограничения, а учитывают его в процессе решения не явно, то есть к исходным ограничения на практике добавляется ограничение, которое определяется самим методом.

Задача №1 - ослабленная задача. Данная задача решена в пункте 1.3. Добавим задачу в основной список. Решение:

Таблица 2.6

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8
X4 7/2     -3/4   1/2   1/2 -3/4
X6 229/8     21/16   23/8   29/8 -99/16
X2 5/8     13/16   -1/8   -3/8 5/16
X1 35/8     11/16   1/8   3/8 -13/16
Y -109/8     139/16   9/8   11/8 3/16

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

Задача №2 - к исходным данным задачи №1 добавляется ограничение Х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)

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

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

Таблица 2.7

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

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

Таблица 2.8

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

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

Таблица 2.9

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9
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          
Y -43/2     83/8 -9/4     1/4 15/8  

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

Таблица 2.10

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9
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
Y -25/2     83/8       1/4 15/8 -9/4

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

Таблица 2.11

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9
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
Y -55/4     17/2   5/4   3/2   1/4

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

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

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

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)

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

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

Таблица 2.12

БП СЧ 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 -1   -1                
Y         -2            

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

Таблица 2.13

БП СЧ 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 6/5 1/5   4/5 1/5     -1/5      
Y -11       -3            

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

Таблица 2.14

БП СЧ 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 1/2     5/8 1/4     -1/4 1/8    
Y -43/2     83/8 -9/4     1/4 15/8    

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

Таблица 2.15

БП СЧ 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.16

БП СЧ 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 -7/12     2/4   1/12   -1/6   5/12  
Y -55/4     17/2   5/4   3/2   1/4  

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

Таблица 2.17

БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9 X10
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
Y -19                    

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

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

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

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)

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

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

 

Таблица 2.18

БП СЧ 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 -6 -1                    
Y         -2              

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

Таблица 2.19

БП СЧ 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 -6 -1                    
Y -11       -3              

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

Таблица 2.20

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

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

Таблица 2.21

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

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


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


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

mybiblioteka.su - 2015-2024 год. (0.014 сек.)