Студопедия

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

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

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






💸 Как сделать бизнес проще, а карман толще?
VisitTime
Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое раписание, но и напоминать клиентам о визитах тоже. Проблема в том, что средняя цена по рынку за такой сервис — 800 руб/мес или почти 15 000 руб за год. И это минимальный функционал. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!

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


⇐ ПредыдущаяСтр 4 из 14Следующая ⇒




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

Задача №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.


⇐ Предыдущая12345678910Следующая ⇒




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