Студопедия

КАТЕГОРИИ:


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

Загальна постановка задачі




АНАЛІТИЧНІ МЕТОДИ розв’язування ЗДЛП

ГРАФІЧНИМ МЕТОДОМ

ДЕЯКІ ОСОБЛИВОСТІ Розв’язування ЗДЛП

Розв’язування задачі в середовищі Mathcad

I

Given

 


1. ОПР обмежена знизу й зверху

 
 

 


 

2. Багатогранник розв’язків необмежений, однак на ньому існують точки, у яких цільова функція досягає свого оптимуму

 
 

 

 


3. Багатогранник розв’язків необмежений, однак один з экстремумов існує

 
 

 

 


Задача має так званий асимптотичнтй максимум, тобто .

4. Багатогранник розв’язків необмежений, задача має асимптотичні оптимуми

 

 
 

 

 


Необхідно знайти оптимум наступної функції:

(3.10)

Задача вирішується при обмеженнях виду:

(3.10)

. (3.11)

Задача (3.10)–(3.11) може бути зведена до задачі лінійного програмування. Для цього необхідно ввести нові змінні, при цьому . У такому випадку здійснюється перехід в область нових змінних, на підставі співвідношень виду:

. (3.12)

З використанням нових змінних, задача (3.10)-(3.11) зводиться до наступної ЗЛП:

(3.12)

при обмеженнях виду:

(3.13)

і рівняннях зв'язків виду

(3.14)

Задача вирішується при умовах невід’ємності, що накладають на n змінних

;

. (3.15)

.

Задача (3.12)-(3.15) є задачею лінійного програмування, отже, розв’язуючи її відомими методами можна знайти відповідні розв’язки. При цьому, одержавши оптимальний план такої задачі, на підставі співвідношень (3.12) можна знайти оптимальний план вихідної задачі (3.10)-(3.11). Таким чином, можна вказати наступний алгоритм розв’язування ЗДЛП.

I. Вихідну ЗДЛП (3.10)-(3.11) зводять до ЗЛП (3.12)-(3.15).

II. Знаходять оптимальний план ЗЛП відомими методами.

III. Використовуючи співвідношення (3.12) знаходять оптимальний план вихідної задачі.

IV. Підставляючи значення xj, при у вираз для функції (3.10) отримують оптимальне значення цільової функції вихідної задачі.

Приклад. Знайти максимальне значення функції:

; (3.16)

(3.17)

. (3.18)

Зведемо дану задачу до ЗЛП, при цьому

. (3.19)

Далі вводимо нові змінні:

(3.20)

Тоді вихідна задача (3.16)-(3.18) зводиться до наступної ЗЛП

. (3.19)

Задача вирішується в рамках обмежень виду:

(3.20)

; (3.21)

; (3.22)

.

Задача (3.19)-(3.22) є ЗЛП і розв’язок її можна знайти методом штучного базису. Для цього формулюють наступну розширену задачу

;

;

;

.

Далі розширену задачу заносять у первісну симплексну таблицю

    з1 з2 з3 з4 з5 з0  
x 1           –1     –11  
x 2             –8  
x 3   –1         –9 Þ
x 4                
F   –2 –1          
f       –1     –28  
                     

 

    з2 з3 з4 з5 з0  
в 1     –1     –11  
x 2   –3          
x 3     –1     –20 Þ
x 4   –1          
  +3 –2     –22  
f           –6  

 

    з2 з3 з4 з0  
в 1     –1   –11  
x 2   –3        
в 5     –1   –20 Þ
x 4   –1        
    –2   –22  
f   –4        

 


 

    з2 з3 з4    
в 1   –27        
в 0   –3        
в 5   –45     :(3) Þ
x 4     –8 –11    
  –57        
f     –8 –11    

 

    з2 з3 з4  
в 1   –9 8/3 11/3  
в 0   –1 1/3 1/3  
в 5   –15 17/3 20/3 Þ
x 4         –8/3 –11/3  
  –19 16/3 22/3  
f     –8/3 –11/3  
               

 

    з3 з4  
в 1        
в 0        
в 5       Þ
в 2   –8/3 –11/3  
  8/3 11/3  
f        

Далі розділивши останню таблицю на 10, одержують оптимальний план ЗЛП

    з3 з4
в 1 9/10    
в 0 1/10    
в 5 15/10    
в 2 1/10 –8/30 –11/30
19/10 8/30 11/30

Висновок: у процесі визначення первісного опорного плану робоча точка пошуку экстремума вийшла в ту вершину опуклого багатогранника, що є точкою максимуму.

.

З урахуванням того, що , знаходять оптимальний план ЗДЛП

.

 

 

розв’язування задачі в середовищі Mathcad:




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


Дата добавления: 2014-11-25; Просмотров: 622; Нарушение авторских прав?; Мы поможем в написании вашей работы!


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



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




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