Студопедия — Метод Гомори
Студопедия Главная Случайная страница Обратная связь

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

Метод Гомори

Метод Гомори

Свойства «правильного отсечения (Гомори)»:

· линейные

· отсекает найденные оптимальные нецелочисленные решения задачи (1)-(3)

· не затрагивает ни одной из целочисленных точек задачи (1)-(4)

 

Б       В
       
       
       
       
      F(x)
 

Найдено оптимальные, нецелочисленные решения ЗЛП (1) - (3)

∈ Б (базисные) переменные

Б (небазисные)

Пусть

 

Ι. Полностью целочисленные задачи:

Выбор наиболее эффективного отсечения.

Пусть и – нецелочисленные. Выбирают:

- строку, соответствующую ∉ Z с наибольшей дробной частью:

- если = , выбирают строку, которой соответствует:

       
   
 
 

 

Если i – порождающая строка:

+ + … + +…+ =

(1+0) + ([ ] + ) + … + ([ ] + ) + … ([ ] + ) = [ ] +

- [0 + + … + + … + … + … + ]+ = -

 


ЗЦП не имеет решения, если в симплекс-таблице появляется, хотя бы одна строка с дробным свободным членом () и целыми коэффициентами при переменных () (в этом случае соответствующие уравнение не имеет решения в целых числах).

Пример 2:

 
 


Б -3           В [ ]
  -1/4   3/4     3/2 9/2   1/2   1/4
  3/4   1/2     -1/2 7/2   1/2 7/4 2/7
  -3/4   1/4     -1/4       - -
              - - - -
 

Строка, соответствующая порождающая:

отсечение Гомори (для дальнейшего решения применяют двойственный симплекс – метод)

Пример 1 (продолжение).

 

 


Б         В [ ]
      7/22 1/22 7/2   1/2 8/22 11/8
      -1/22 3/22 9/2   1/2 24/22 11/24
    28/11 15/11 63 - -    
 

       
   
 

 


Б           В
      7/22 1/22   7/2
      -1/22 3/22   9/2
      -7/22 -1/22   -1/2
    28/11 15/11    
            3
        1/7 -1/7 32/7
        1/7 -22/7 11/7
           

Б             В  
               
        1/7 -1/7   32/7
        1/7 -22/7   11/7
        -1/7 -6/7   -4/7
             
               
          -1    
          -4    
            -7  
             
 

II. Частично целочисленная задача:

 

 

 

Пусть в примере (А) Z (условие целочисленности накладывается только на
, все остальные , j≠2, могут быть дробными)

Пример 3:

       
 
   

 


 




<== предыдущая лекция | следующая лекция ==>
О чем корпоративная культура напоминает человеку с советским прошлым | Тотальный диктант напишут в Антарктиде

Дата добавления: 2015-08-30; просмотров: 610. Нарушение авторских прав; Мы поможем в написании вашей работы!



Шрифт зодчего Шрифт зодчего состоит из прописных (заглавных), строчных букв и цифр...

Картограммы и картодиаграммы Картограммы и картодиаграммы применяются для изображения географической характеристики изучаемых явлений...

Практические расчеты на срез и смятие При изучении темы обратите внимание на основные расчетные предпосылки и условности расчета...

Функция спроса населения на данный товар Функция спроса населения на данный товар: Qd=7-Р. Функция предложения: Qs= -5+2Р,где...

Искусство подбора персонала. Как оценить человека за час Искусство подбора персонала. Как оценить человека за час...

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

Тема 5. Анализ количественного и качественного состава персонала Персонал является одним из важнейших факторов в организации. Его состояние и эффективное использование прямо влияет на конечные результаты хозяйственной деятельности организации.

Ведение учета результатов боевой подготовки в роте и во взводе Содержание журнала учета боевой подготовки во взводе. Учет результатов боевой подготовки - есть отражение количественных и качественных показателей выполнения планов подготовки соединений...

Сравнительно-исторический метод в языкознании сравнительно-исторический метод в языкознании является одним из основных и представляет собой совокупность приёмов...

Концептуальные модели труда учителя В отечественной литературе существует несколько подходов к пониманию профессиональной деятельности учителя, которые, дополняя друг друга, расширяют психологическое представление об эффективности профессионального труда учителя...

Studopedia.info - Студопедия - 2014-2024 год . (0.01 сек.) русская версия | украинская версия