Студопедия

КАТЕГОРИИ:


Архитектура-(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)

Лекция № 13. Решение. Сначала с помощью симплекс-метода решим вспомогательную задачу нецелочисленного линейного программирования




Пример 12.1.

 

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

Запишем данную задачу в каноническом виде:

 

 

Начальная симплексная таблица имеет вид:

 

БП Сб Ао x1 x2 x3 x4
       
x3       [5]    
x4            
Zj - Cj   -20 -40    

 

БП Сб Ао x1 x2 x3 x4
       
x2     2/5   1/5  
x4     [13/5]   -6/5  
Zj - Cj   -4      

 

БП Сб Ао x1 x2 x3 x4
       
x2      
x1      
Zj - Cj    

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

Среди дробных частей найденного решения выберем наибольшую. И это так как .

Так, что строка последней симплексной таблицы, отвечающая переменной , поможет построить дополнительное линейное ограничение

 

 

где переменная оптимального решения, имеющая наибольшую дробную часть,

число, стоящее в строке переменной в последней симплексной таблице

 

Допишем полученное ограничение в последнюю симплекс таблицу. Получим новую таблицу:

 

БП Сб Ао x1 x2 x3 x4 x5
         
x2        
x1        
x5   -     - -  
Zj - Cj      

 

Чтобы затем решить данную задачу (в столбике А0 появилось отрицательное число) нужно выполнить следующие операции.

1). Рассмотрим строку, содержащую отрицательное число в столбце А0, и выберем какое- либо отрицательное число в этой строке. Выбранное число стоит в столбце переменной, которую нужно ввести в базис.

2). Для чисел с одинаковыми знаками составляем симплексные отношения.

3). Наименьшее симплексное отношение определяет ту переменную, которую выводим из базиса.

4). Составляем новую таблицу, выполняя симплексные преобразования.

В нашей задаче, в строке переменной x5 возьмём число , для данного столбца найдём симплексные отношения. -:=1; :=наименьшее симплексное отношение 1. Таким образом, вместо переменной x5 введём переменную x4.

 

БП Сб Ао x1 x2 x3 x4 x5
         
x2  
x1  
x5  
Zj - Cj      

 

Имеем оптимальное целочисленное решение расширенной задачи. Тогда оптимальное решение исходной задачи, учитывая ограничения (1),

12.3. Обобщённая схема алгоритма Гомори

 

Структурно алгоритм Гомори делится на так называемые большие итерации. Каждая большая итерация содержит следующие этапы.

1. Решение текущей задачи методами линейного программирования (малые итерации). На первой итерации в качестве текущей задачи выступает нецелочисленный аналог исходной целочисленной задачи ЛП.

2. Поиск первой нецелочисленной компоненты в оптимальном плане, полученном на первом этапе.

1).Если все компоненты являются целочисленными, то алгоритм завершается.

2).Если существуют нецелочисленные компоненты, то переходим к пункту 3 алгоритма.

3. Построение для найденной компоненты условия отсечения согласно правилу (3). Вновь сформированное ограничение добавляется к системе ограничений текущей задачи и таким образом получается новая текущая задача. Переходим на начало следующей большой итерации (пункт 1).

Можно доказать, что приведённый алгоритм конечен. Это означает, что на некотором шаге (итерации) будет найден целочисленный оптимальный план или обнаружен факт отсутствия допустимых оптимальных решений.

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

Контрольные вопросы:

1. Какие экономические задачи относятся к целочисленному программированию?

2. Алгоритм Гомори.

3. С помощью алгоритма Гомори решить задачу:




Поделиться с друзьями:


Дата добавления: 2013-12-13; Просмотров: 391; Нарушение авторских прав?; Мы поможем в написании вашей работы!


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



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.016 сек.