Студопедия

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

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

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






  • Сервис онлайн-записи на собственном Telegram-боте
    Тот, кто работает в сфере услуг, знает — без ведения записи клиентов никуда. Мало того, что нужно видеть свое расписание, но и напоминать клиентам о визитах тоже. Нашли самый бюджетный и оптимальный вариант: сервис VisitTime.
    Для новых пользователей первый месяц бесплатно.
    Чат-бот для мастеров и специалистов, который упрощает ведение записей:
    — Сам записывает клиентов и напоминает им о визите;
    — Персонализирует скидки, чаевые, кэшбэк и предоплаты;
    — Увеличивает доходимость и помогает больше зарабатывать;
    Начать пользоваться сервисом

    • Решение задачи методом ветвей и границ 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)

    Забиваем Сайты В ТОП КУВАЛДОЙ - Уникальные возможности от SeoHammer
    Каждая ссылка анализируется по трем пакетам оценки: SEO, Трафик и SMM. SeoHammer делает продвижение сайта прозрачным и простым занятием. Ссылки, вечные ссылки, статьи, упоминания, пресс-релизы - используйте по максимуму потенциал SeoHammer для продвижения вашего сайта.
    Что умеет делать SeoHammer
    — Продвижение в один клик, интеллектуальный подбор запросов, покупка самых лучших ссылок с высокой степенью качества у лучших бирж ссылок.
    — Регулярная проверка качества ссылок по более чем 100 показателям и ежедневный пересчет показателей качества проекта.
    — Все известные форматы ссылок: арендные ссылки, вечные ссылки, публикации (упоминания, мнения, отзывы, статьи, пресс-релизы).
    — SeoHammer покажет, где рост или падение, а также запросы, на которые нужно обратить внимание.
    SeoHammer еще предоставляет технологию Буст, она ускоряет продвижение в десятки раз, а первые результаты появляются уже в течение первых 7 дней.
    Зарегистрироваться и Начать продвижение

    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 :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.