Студопедия

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

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

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






  • Решение частично целочисленной задачи






    Максимизировать целевую функцию вида:

    При ограничениях:

    ; - целoе.

    a) Метод Гомори для частично целочисленных задач.

    Решаем исходную задачу линейного программирования. Ее решение приведено в пункте 1.3. Последняя симплексная таблица имеет вид:

     

    Таблица 2.2.1
    БП СЧ x1 x2 x3 x4 x5 x6 x7 x8
    x5         -5     -2  
    x1 9/2       -1   -1/2    
    x2 7/4       -2   1/4 -1 1/2
    x3 5/4       -1   -1/4   1/2
    Y -16                

    Значения целевой функции и переменных:

    Значение переменной не удовлетворяет требованиям целочисленности.

    В соответствии с правилами формирования коэффициентов ограничений метода Гомери для частично целочисленных задач имеем:

    Вводим дополнительную свободную переменную:

    Выражаем новое ограничение в форме Куна-Таккера:

    Решаем новую расширенную задачу линейного программирования:

     

    Таблица 2.2.2
    БП СЧ x1 x2 x3 x4 x5 x6 x7 x8 x9
    x5         -5     -2    
    x1 9/2       -1   -1/2      
    x2 7/4       -2   1/4 -1 1/2  
    x3 5/4       -1   -1/4   1/2  
    x9 -1/2       -1   -1/2      
    Y -16                  

     

    Таблица 2.2.3
    БП СЧ x1 x2 x3 x4 x5 x6 x7 x8 x9
    x5         -5     -2    
    x1                   -1
    x2 3/2       -5/2     -1 1/2 ½
    x3 3/2       -1/2       1/2 -1/2
    x6                   -2
    Y -17                  

    Полученное оптимальное решение удовлетворяет поставленным ограничением и требованию целочисленности переменной .

    Ответ: .

     

    б) Метод ветвей и границ.

    Проанализировав ограничения определим границы следующим образом:

    Т.к. о целевой функции ничего не известно, примем .

    Решаем Задачу 1 – исходную задачу линейного программирования. Ее решение приведено в пункте 1.3. Последняя симплексная таблица имеет вид:

     

    Таблица 2.2.4
    БП СЧ x1 x2 x3 x4 x5 x6 x7 x8
    x5         -5     -2  
    x1 9/2       -1   -1/2    
    x2 7/4       -2   1/4 -1 1/2
    x3 5/4       -1   -1/4   1/2
    Y -16                

    Значения целевой функции и переменных:

    Принимаем

    Полученное решение не удовлетворяет требованиям целочисленности для переменной .

    Поэтому составляем относительно первой задачи две новых порожденных задачи:

    Задача 2.

    Максимизировать целевую функцию вида:

    При ограничениях:

    ;

    - новое ограничение.

    Преобразуем новую систему ограничений Задачи 2, введя свободные переменные и приведя их к форме Куна-Таккера:

    Воспользуемся симплекс методом и решим Задачу 2.

     

     

    Таблица 2.2.5
    БП СЧ x1 x2 x3 x4 x5 x6 x7 x8 x9
    x5 -3 -1 -2              
    x6 -9 -2                
    x7 -5 -1 -1              
    x8 -2 -1     -1          
    x9                    
    Y       -3            

     

     

    Таблица 2.2.6
    БП СЧ x1 x2 x3 x4 x5 x6 x7 x8 x9
    x5 3/2   -2   -1   -1/2      
    x1 9/2       -1   -1/2      
    x7 -1/2   -1       -1/2      
    x8 5/2       -2   -1/2      
    x9 -1/2           1/2      
    Y -18     -3            

     

    Таблица 2.2.6
    БП СЧ x1 x2 x3 x4 x5 x6 x7 x8 x9
    x5 5/2     -2 -3   1/2 -2    
    x1 9/2       -1   -1/2      
    x2 ½     -1 -1   1/2 -1    
    x8 5/2       -2   -1/2      
    x9 -1/2           1/2      
    Y -37/2     -2     3/2      

     

    Допустимого решения Задачи 2 не существует.

    Поэтому примем

    Выбираем и решаем Задачу 3.

    Максимизировать целевую функцию вида:

    При ограничениях:

    ;

    - новое ограничение.

    Преобразуем новую систему ограничений Задачи 3, введя свободные переменные и приведя их к форме Куна-Таккера:

    Воспользуемся симплекс методом и решим Задачу 2.

     

    Таблица 2.2.7
    БП СЧ x1 x2 x3 x4 x5 x6 x7 x8 x9 x10
    x5 -3 -1 -2                
    x6 -9 -2                  
    x7 -5 -1 -1                
    x8 -2 -1     -1            
    x9 -5 -1                  
    x10                      
    Y       -3              

     

    Таблица 2.2.8
    БП СЧ x1 x2 x3 x4 x5 x6 x7 x8 x9 x10
    x5 3/2   -2   -1   -1/2        
    x1 9/2       -1   -1/2        
    x7 -1/2   -1       -1/2        
    x8 5/2       -2   -1/2        
    x9 -1/2       -1   -1/2        
    x10 3/2           1/2        
    Y -18     -3              

     

    Таблица 2.2.8
    БП СЧ x1 x2 x3 x4 x5 x6 x7 x8 x9 x10
    x5 5/2     -2 -3   1/2 -2      
    x1 9/2       -1   -1/2        
    x2 1/2     -1 -1   1/2 -1      
    x8 5/2       -2   -1/2        
    x9 -1/2       -1   -1/2        
    x10 3/2           1/2        
    Y -37/2     -2     3/2        

     

    Таблица 2.2.9
    БП СЧ x1 x2 x3 x4 x5 x6 x7 x8 x9 x10
    x5       -2 -4     -2      
    x1                   -1  
    x2       -1 -2     -1      
    x8         -1         -1  
    x6                   -2  
    x10                      
    Y -20     -2              

     

    Таблица 2.2.10
    БП СЧ x1 x2 x3 x4 x5 x6 x7 x8 x9 x10
    x5         -5     -2      
    x1                   -1  
    x2 3/2       -5/2     -1 1/2 1/2  
    x3 3/2       -1/2       1/2 -1/2  
    x6                   -2  
    x10                      
    Y -17                    

    Полученное оптимальное решение удовлетворяет поставленным ограничением и требованию целочисленности переменной . Поэтому принимаем

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

    Ответ:

    Рис 2.2.1 Блок схема решения.

     

    На основе полученных результатов решения задачи методом Гомори и методом ветвей и границ, можно сделать вывод о том, метод Гомори менее трудоемок. Однако, стоит учесть простоту решаемой задачи, в которой требование целочисленности наложено всего на одну переменную из трех. Метод Гомори в данном случае позволяет получить оптимальное решение с использованием всего одного уравнения отсекающей плоскости и решением одной расширенной задачи. Используя метод ветвей и границ, приходится решать уже две порожденных задачи, т.е. использование этого метода в данном случае менее эффективно. Таким образом можно сделать вывод о том, что метод ветвей и границ вообще мало эффективен для решения простых задач, где не требуется получение всех локальных оптимумов. В таких случаях разумнее воспользоваться методом Гомори для частично целочисленных задач.


     







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