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

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

Решение задачи методом отсекающих плоскостей


⇐ Предыдущая123456789Следующая ⇒



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

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

и целые.

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

 

Таблица 2.1.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.1.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 -3/4           -1/4   -1/2  
Y -16                  

 

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

Требование целочисленности не выполнено. Составляем следующее уравнение отсекающей плоскости. Т.к. дробные части у всех нецелых значений базисных переменных равны, выберем любую, например .

Аналогично:

.

Теперь решаем новую расширенную задачу.

 

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

 

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

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

Ответ: .




⇐ Предыдущая123456789Следующая ⇒


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


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


Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...


Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...


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

Конституционно-правовые нормы, их особенности и виды Характеристика отрасли права немыслима без уяснения особенностей составляющих ее норм...

Толкование Конституции Российской Федерации: виды, способы, юридическое значение Толкование права – это специальный вид юридической деятельности по раскрытию смыслового содержания правовых норм, необходимый в процессе как законотворчества, так и реализации права...

Значення творчості Г.Сковороди для розвитку української культури Важливий внесок в історію всієї духовної культури українського народу та її барокової літературно-філософської традиції зробив, зокрема, Григорій Савич Сковорода (1722—1794 pp...

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

Сущность, виды и функции маркетинга персонала Перснал-маркетинг является новым понятием. В мировой практике маркетинга и управления персоналом он выделился в отдельное направление лишь в начале 90-х гг.XX века...

Разработка товарной и ценовой стратегии фирмы на российском рынке хлебопродуктов В начале 1994 г. английская фирма МОНО совместно с бельгийской ПЮРАТОС приняла решение о начале совместного проекта на российском рынке. Эти фирмы ведут деятельность в сопредельных сферах производства хлебопродуктов. МОНО – крупнейший в Великобритании...
Studopedia.info - Студопедия - 2014-2026 год . (0.011 сек.) русская версия | украинская версия