Ћекции.ќрг


ѕоиск:




 атегории:

јстрономи€
Ѕиологи€
√еографи€
ƒругие €зыки
»нтернет
»нформатика
»стори€
 ультура
Ћитература
Ћогика
ћатематика
ћедицина
ћеханика
ќхрана труда
ѕедагогика
ѕолитика
ѕраво
ѕсихологи€
–елиги€
–иторика
—оциологи€
—порт
—троительство
“ехнологи€
“ранспорт
‘изика
‘илософи€
‘инансы
’ими€
Ёкологи€
Ёкономика
Ёлектроника

 

 

 

 


јнал≥тичний розвТ€зок задач≥




јлгоритм розвТ€зку задач≥ (1) Ц (2) складаЇтьс€ з двох етап≥в.

≈тап I. ѕараметру надають ф≥ксоване значенн€, наприклад

.

÷им задача приводитьс€ до задач≥ л≥н≥йного програмуванн€.

–озвТ€зуючи отриману «Ћѕ симплекс-методом, знаход€ть вершину, в €к≥й дос€гаЇ максимум.

≈тап II. ¬изначають ≥нтервал зм≥ни параметра , дл€ €кого максимум , дос€гаЇтьс€ в одн≥й ≥ т≥й же вершин≥ многогранника .

«найдений ≥нтервал виключаЇтьс€ ≥з в≥др≥зка дл€ частини в≥др≥зка, що залишилас€, знову розвТ€зують «Ћѕ симплекс-методом тобто переходимо до етапу I.

–озвТ€зок продовжуЇтьс€ до тих п≥р поки весь в≥др≥зок не буде розбито на частинн≥ ≥нтервали.

«адача. «найти ≥нтервали зм≥ни параметра t на в≥др≥зку , дл€ €ких

дос€гаЇ максимум в одн≥й ≥ т≥й же вершин≥ област≥ допустимих значень системи обмежень.

–озвТ€занн€.

≈тап I.

1. ѕокладемо

.

“од≥ функц≥€ прийме вигл€д

. (7)

¬с≥ дан≥ задач≥ заносимо в жорданову таблицю.

¬ р€док ц≥Їњ таблиц≥ в кожен стовпчик записуЇмо число, €ке р≥вне сум≥ чисел .

 р≥м того, додамо до таблиц≥ два р€дки дл€ запису функц≥њ з дов≥льним параметром (табл. 1).

ѕри цьому в передостанньому р€дку записуЇмо коеф≥ц≥Їнти , а в останньому Ц .

ўоб отримати , потр≥бно перемножити коеф≥ц≥Їнти останнього р€дка на ≥ додати њх до коеф≥ц≥Їнт≥в передостаннього.


 

“аблиц€ 1

  Е  
=    
Е Е
=
Е  
Е  
Е  

 

2. «находимо оптимальний план задач≥ звичайним симплекс-методом, зд≥йснюючи перетворенн€ ≥ елемент≥в останн≥х двох р€дк≥в.

ѕрипустимо, що план, представлений в таблиц≥ 2, Ї оптимальним.

“аблиц€ 2

   
           
           
           
         
           

 

“од≥ вс≥ коеф≥ц≥Їнти р€дка Ц нев≥дТЇмн≥:

.

ќск≥льки оптимальний план знайдено, переходимо до виконанн€ д≥й другого етапу.


≈тап II.

1. «находимо значенн€ параметра , при €ких план в табл. 2 буде залишатись оптимальним (максимум дос€гаЇтьс€ в т≥й сам≥й вершин≥).

ƒл€ цього необх≥дно, щоб вс≥ коеф≥ц≥Їнти функц≥њ були нев≥дТЇмн≥:

(8)

≤з системи (8) видно, що у вс≥х випадках, кр≥м (при нер≥вн≥сть виконуЇтьс€ при будь-€ких значенн€х ; в≥дпов≥дно, на стовпчик, в €кому знаходитьс€ , можна не звертати уваги), границею зм≥ни параметра служить в≥дношенн€

.

“ому передивл€Їмось останн≥ елементи останнього р€дка таблиц≥:

Ј €кщо вс≥ вони б≥льш≥ нул€, переходимо до пункту 2;

Ј €кщо вс≥ вони менш≥ нул€ Ц до пункту 3;

Ј €кщо ж серед елемент≥в Ї ≥ додатн≥, ≥ в≥дТЇмн≥ Ц до пункту 4.

2. Ќехай вс≥ .

—еред в≥дношень

вибираЇмо найб≥льше.

¬ерхньоњ меж≥ дл€ в цьому випадку не ≥снуЇ.

“аким чином,

(9)

¬ ≥нтервал≥ функц≥€ дос€гаЇ максимум в т≥й сам≥й вершин≥, що й при ; в≥дпов≥дно, .

3. Ќехай вс≥ .

—еред в≥дношень

вибираЇмо найменше.

якщо вз€ти

,

то вс≥ умови (8) будуть задоволен≥.

Ќижньоњ меж≥ дл€ в цьому випадку не ≥снуЇ, тому його можна зменшувати неск≥нченно.

ќтже,

(10)

як ≥ ран≥ше, .

4. Ќехай серед елемент≥в Ї €к додатн≥, так ≥ в≥дТЇмн≥.

–озд≥лимо систему нер≥вностей (8) на дв≥ п≥дсистеми в≥дпов≥дно до знак≥в коеф≥ц≥Їнт≥в .

“од≥ ≥з п≥дсистеми нер≥вностей з

отримаЇмо

,

а з другоњ п≥дсистеми з

будемо мати

.

¬≥дпов≥дно, вс€ система нер≥вностей (8) буде задовольн€тись, €кщо буде приймати значенн€:

(11)

¬ цьому випадку вид≥лений ≥нтервал, в €кому функц≥€ дос€гаЇ максимум в т≥й сам≥й вершин≥, що й при , Ї в≥др≥зком

.

5. «р≥вн€Їмо отриманий ≥нтервал з заданим .

Ќезалежно в≥д значенн€ л≥вою границею першого ≥нтервалу буде , так €к б≥льше бути не може.

якщо

,

то весь ≥нтервал попадаЇ всередину ≥нтервалу , ≥ задача розвТ€зана.

ƒл€ будь-€кого значенн€ параметра максимум функц≥њ дос€гаЇтьс€ в одн≥й ≥ т≥й сам≥й вершин≥ (рис. 4).

–ис. 4 –ис. 5

6.якщо , то в ≥нтервал≥ максимум функц≥њ буде в знайден≥й вершин≥ (рис. 5).

¬иключаЇмо цей ≥нтервал ≥з розгл€ду ≥ розвТ€зуЇмо задачу дл€ ≥нтервалу, що залишивс€ .

ƒл€ цього надаЇмо значенн€ ≥ зам≥нюЇмо р€док р€дком .

¬ результат≥ зам≥ни отримаЇмо нову таблицю (табл. 3).

“аблиц€ 3

   
           
           
           
         
           

 


«а розвТ€зуючий стовпчик в нов≥й таблиц≥ вибираЇтьс€ той, по €кому визначено значенн€ (в цьому стовпчику на перетин≥ з Ц р€дком знаходитьс€ елемент, р≥вний нулю).

якщо нул≥ знаход€тьс€ в к≥лькох стовпц€х, то за розвТ€зуючий можна брати будь-€кий з них.

–озвТ€зуючий елемент знаходимо по найменшому симплексному в≥дношенню ≥ робимо один крок модиф≥кованих жорданових виключень.

ќтримаЇмо наступний по пор€дку оптимальний розвТ€зок, так €к вс≥ коеф≥ц≥Їнти в стр≥чц≥ при перетворенн≥ не зм≥н€тьс€.

ƒл€ знайденого розвТ€зку знову визначаЇмо ≥нтервал зм≥ни параметра , дл€ чого переходимо до пункту 1.

якщо в розвТ€зуючому стовпчику не ви€витьс€ нев≥дТЇмних коеф≥ц≥Їнт≥в, то функц≥€ при необмежена; задача на ≥нтервал≥ , що залишивс€ розвТ€зку не маЇ.

«ауваженн€. ѕри в≥дшуканн≥ оптимального розвТ€зку дл€ (при виконанн≥ пункту 2 етапу ≤ алгоритму) може ви€витис€, що функц≥€ зверху необмежена.

¬ цьому випадку в розвТ€зуючому стовпчику коеф≥ц≥Їнт - стр≥чки в≥дТЇмний , а вс≥ ≥нш≥ коеф≥ц≥Їнти стовпчика недодатн≥.

ѕри значенн≥ на перетин≥ стр≥чки ≥ стовпчика буде елемент

.

Ќас ц≥кавить значенн€ цього елемента, так €к вони визначають повед≥нку функц≥њ при

.

¬иберемо таке значенн€ , при €кому коеф≥ц≥Їнт

.

«в≥дси отримуЇмо, що

.

якщо значенн€ елемента , то дл€ вс≥х коеф≥ц≥Їнт розвТ€зуючого стовпчика в стр≥чц≥ буде в≥дТЇмним

.

ќтже, на всьому заданому в≥др≥зку ц≥льова функц≥€ необмежена (задача розвТ€зку не маЇ).

якщо елемент , то при коеф≥ц≥Їнт, що знаходитьс€ в розвТ€зуючому стовпчику та -стр≥чц≥, буде в≥дТЇмним.

«начить ≥ в цьому випадку ц≥льова функц≥€ необмежена ≥ задача розвТ€зку не маЇ.

ѕри значенн≥ коеф≥ц≥Їнт

,

а при подальшому зб≥льшенн≥ в≥н буде додатн≥м.

ƒо в≥др≥зку застосовуЇмо посл≥довно весь алгоритм розвТ€зку задач≥.

ѕриклад 3. «найти розвТ€зок задач≥ з прикладу 1 при зм≥н≥ параметра на в≥др≥зку [0,12].

–озвТ€зок. ѕрипускаЇмо .

“од≥

.

«аносимо умову задач≥ в таблицю 4 ≥ розвТ€зуЇмо њњ симплекс-методом.

ќпускаючи подробиц≥, наводимо оптимальний розвТ€зок (табл. 5.):

.

¬изначаЇмо значенн€ параметра , при €ких оптимальний розвТ€зок в т≥й сам≥й вершин≥, що й при .

“ак €к в останньому р€дку елемент

, а ,

то дл€ визначенн€ значень , при €ких максимум буде дос€гатись в знайден≥й вершин≥, п≥дставимо в≥дпов≥дн≥ значенн€ в в≥дношенн€ (11), отримаЇмо

 

“аблиц€ 4. “аблиц€ 5

         
    -5   14/3 1/30 7/30
-5 -1 -1   25/3 1/6 1/6
  -1       3/10 1/10
        4/3 -2/15 1/15
  -4 -2     2/5 4/5
  -4 -2     2/5 4/5
    -1   4/3 -2/15 1/15

“ут , а .

ќтриманий ≥нтервал менший заданого , тому його виключаЇмо з подальшого розгл€ду ≥ розвТ€зуЇмо задачу дл€ ≥нтервалу, що залишивс€ .

ƒл€ цього даЇмо значенн€ ≥ обчислюЇмо дл€ нього р€док .

«анесемо елементи - р€дка в табл. 6. ¬с≥ ≥нш≥ елементи таблиц≥ залишаЇмо без зм≥н.

“аблиц€ 6 “аблиц€ 7

         
14/3 1/30 7/30   31/9    
25/3 1/6 1/6   20/9    
  3/10 1/10   110/3    
4/3 -2/15 1/15   56/9    
             
  2/5 4/5   64/3 -4/3 2/3
4/3 -2/15 1/15   56/9 4/9 1/9

 

¬ першому стовпчику ≥ - р€дку табл. 6. знаходитьс€ нуль, тому цей стовпець беремо за розвТ€зуючий (при на м≥сце нул€ першим зТ€витьс€ в≥дТЇмне число ≥ план перестане бути оптимальним).

«находимо розвТ€зуючий елемент по найменшому симплексному в≥дношенню ≥ переходимо до новоњ таблиц≥ (табл. 7).


ѕлан

в табл. 7 оптимальний, так €к вс≥ елементи - р€дка нев≥дТЇмн≥.

¬ останньому р€дку вс≥ елементи , в≥дпов≥дно, застосовуЇмо формулу (7) ≥ визначаЇмо, що

,

тобто .

“ак €к значенн€ , то задача розвТ€зана.

ќтже, при

максимальне значенн€ функц≥њ дос€гаЇтьс€ у вершин≥ , при

максимальне значенн€ функц≥њ дос€гаЇтьс€ у вершин≥ (рис. 3). ѕри значенн≥ оптимум дос€гаЇтьс€ у вершинах , а також в њх випукл≥й л≥н≥йн≥й комб≥нац≥њ.

 





ѕоделитьс€ с друзь€ми:


ƒата добавлени€: 2015-11-05; ћы поможем в написании ваших работ!; просмотров: 838 | Ќарушение авторских прав


ѕоиск на сайте:

Ћучшие изречени€:

Ќе будет большим злом, если студент впадет в заблуждение; если же ошибаютс€ великие умы, мир дорого оплачивает их ошибки. © Ќикола “есла
==> читать все изречени€...

2357 - | 2088 -


© 2015-2024 lektsii.org -  онтакты - ѕоследнее добавление

√ен: 0.078 с.