Студопедия

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

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

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






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






    .

    Задача №1 - исходная задача со снятым требованием целочисленности. Перепишем решение из таблицы 1.12.

    Таблица 2.56

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

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

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

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

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

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

    Решение задачи удовлетворяет требованию целочисленности для переменной х4, и значение целевой функции больше, чем найденное до этого оптимально . На данной итерации найдено новое оптимально целочисленное решение.

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

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

    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=3-(0x1+0x2+0x3+1x4)

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

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

     

    Таблица 2.62

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

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

    Таблица 2.63

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

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

    Таблица 2.64

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

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

    Таблица 2.64

    БП СЧ X1 X2 X3 X4 X5 X6 X7 X8 X9
    X5       -3/2         -3/2 -2
    X6 103/4     45/8       3/4 -15/8 23/4
    X2 3/4     5/8       -1/4 1/8 -1/4
    X1 17/4     7/8       1/4 -5/8 1/4
    X4                    
    Y -59/4     83/8       1/4 15/8 9/4

    Остановка: Решение задачи удовлетворяет требованию целочисленности для переменной х4, но значение целевой функции не больше, чем найденное до этого.

    Список задач пуст. Блок-схема решения задачи представлена на рисунке 2.2.

     

    Ответ: Y=-55/4, X=(59/12; 5/12; 0; 4; 0; 131/4; 0; 2/3; 0).

    Рисунок 2.2 - Схема решения частично целочисленной задачи методом ветвей и границ.

     







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