Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Метод Гомори

Ответы.

Опорного плана, решить следующие задачи.

Используя метод искусственного базиса для нахождения исходного

Ответы.

Задачи.

Составим исходную симплексную таблицу.

Алгоритм решения канонической задачи ЛП

симплексным методом (общий случай).

Запишем в общем случае алгоритм решения канонической задачи ЛП симплексным методом [1-4].

1. Дано

при условиях:

;

    Коэффициенты при неизвестных
           
                     
                       
                     
                       
                     
F                      

.

 

3. Выберем разрешающий столбециз условия

(в задаче максимизации ) .

4. Выберем q – ю разрешающую строчку из условия

 

для

5. Формируем новую симплексную таблицу.

Пересчитываем элементы разрешающей q-й строки по формуле:



 

Если , затем исключим из 1-го и 3-го уравнений (точно также, как в методе Гаусса). Получим

 

 

 

Затем исключим аналогично из 1-го и 2-го уравнения. Придем к канонической системе, равносильной исходной.

Решить симплекс-методом следующие задачи:

 

№ 1 № 2 № 3
№ 4 № 5 № 6
№ 7 № 8 № 9
№ 10 № 11
       

 

 

№ 1.

№ 2.

№ 3.

№ 4.

№ 7.

№ 8.

№ 9.

№ 10.

№ 11. Линейная форма не ограничена.

 

 

 

 

№ 12 № 13
№ 14 № 15
№ 16 № 17

 

 

 

 

 

№ 12.

№ 13. Линейная форма не ограничена.

№ 14.

№ 15.

№ 16.

№ 17.

 

Глава 4. Целочисленное линейное программирование.

 

Важное значение в ЛП имеет случай, когда неизвестные целочисленные. Задача ЛП с дополнительным условием целочисленности неизвестных исследуется в новой области математического программирования – целочисленном (дискретном) программировании (ЛЦП).



К основной задаче ЛП добавим дополнительное условие – условие целочисленности неизвестных, в результате получим задачу ЛЦП. Можно, конечно, получить дробное оптимальное решение задачи ЛП и его округлить до ближайших целых значений. Но тогда может случиться, что мы будем либо близки к оптимальному плану задачи ЛЦП, либо далеки, либо вообще уйдем за пределы множества планов ЛЦП. Один из возможных методов решения задачи ЛЦП – метод Гомори. Идея метода базируется на представлении вещественного числа в виде суммы его целой и дробной частей. Как известно, целой частью вещественного числа «а» называется наибольшее целое число, не превосходящее Обозначение целой части [a]. Разность есть дробная часть числа Очевидно, например, что и Например:


Рассмотрим метод Гомори на примере(общая задача ЛП):

 

 

 

 

 

Снимем условие целочисленности.

 

Max Z = x1 + 2 x2

 

при условиях: x1 - 2 x2 + x3 = 2

- 2x1 + x2 + x4 =2

x1 + x2 + x5 =3

.

 

Исходная симплексная таблица

 

Базисные переменные   Свободные члены ( ) Коэффициенты при неизвестных
           
           
  -2      
  -2      
       
Z -1 -2        

 

 

Итерация 1

 

Базисные переменные   Свободные члены ( ) Коэффициенты при неизвестных
           
           
  -3      
  -2      
      -1  
Z -5        

 

 

Итерация 2

 

Базисные переменные   Свободные члены ( ) Коэффициенты при неизвестных
           
           
       
             
             
Z = 5            

Задача ЛП решена. Решение нецелочиcленное.

Добавляем неравенство Гомори к итерации 2. Получим задачу ЦЛП:

Max Z = x1 + 2 x2

при условиях: x3 + x4 + x5 = 7

x2 + x4 + x5 =

x1 - x4 + x5 =

- x4 - x5 ≤

.

.

 

Исходная симплексная таблица

Базисные переменные   Свободные члены ( ) Коэффициенты при неизвестных    
          S2  
           
         
               
               
S2                  
Z = 5              
                   

 

Итерация 1

Базисные переменные   Свободные члены ( ) Коэффициенты при неизвестных   S2
             
           
        -1  
           
          -1  
S2       -3  
Z          
                   

 

  Получили оптимальное и целочисленное решение L(max) = 5. Дадим геометрическую интерпретацию решения данной задачи. Из рис. 1 видно, что максимально значение целевая функция принимает в точке , то есть решение является оптимальным, но без учета требования целочисленности.    
 

X1

 

 

 

 

 

 

 

 

 

 

 

 

 

B

 

A max

 

A*

 

D

 

C

 

X2

 

 

I

 

 
.

 

.

 

x2=2

 

.

 

.

 

.

 

III

 

 

  II

 

Рис. 1

 

С учетом требования целочисленности решение не является оптимальным, поэтому используем дополнительное ограничение

или . Значения переменных x4 и x5 подставим из второго и третьего уравнений системы ограничений , . В результате получим . Этому неравенству на рис. 1 соответствует полуплоскость, ограниченная прямой , отсекающей от многоугольника допустимых решений треугольник АДА*. В новом многоугольнике допустимых решений ОДА*ВС найдем точку А*(1,2), в которой целевая функция принимает максимальное значение. Так как координаты точки А* – целые числа, то решение является оптимальным планом исходной задачи.

<== предыдущая лекция | следующая лекция ==>
| Метод Гомори

Дата добавления: 2014-01-06; Просмотров: 243; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ‚аш ip: 54.224.202.224
Генерация страницы за: 0.098 сек.