Ћекции.ќрг


ѕоиск:




 атегории:

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

 

 

 

 


—имплекс-метод




–ешение задачи Ћѕ (2.1.1), согласно теоремам 2, 3, 4, достигаетс€ в вершине многогранного множества. “еорема 2 дает простое описание вершин и способ их определени€ при известном базисе. „исло вершин конечно. ћинимум задачи может быть найден за конечное число шагов посредством перебора вершин.

¬ симплекс-методе осуществл€етс€ иде€ перебора вершин соседних текущей вершине и выбора среди них в качестве следующего приближени€ вершины с наименьшим значением целевой функции. —имплекс-метод примен€ют дл€ задач, записанных в форме:

. (2.4.1)

ѕусть на -ом шаге получена точка , €вл€юща€с€ вершиной множества , и пусть .

Ќазовем невырожденной вершиной множества , если число положительных компонент в ней равно .

ѕредположим, что все вершины множества невырождены. ¬ силу невырожденности множество содержит элементов. –азобьем вектор на две группы , где отвечает компонентам из , - компонентам, не принадлежащим . “огда система может быть записана в виде:

, (2.4.2)

где , столбцы которой €вл€ютс€ столбцами с индексами из , -матрица, составленна€ из оставшихс€ столбцов. ќтсюда, в силу невырожденности матрицы ,

(2.4.3)

÷елева€ функци€ приобретает вид:

, (2.4.4)

где - вектор с компонентами , , -вектор с компонентами , . — учетом (2.4.3) целева€ функци€ может быть выражена только через .

—ледовательно, исходна€ задача эквивалентна следующей:

, (2.4.5)

ѕри этом точке соответствует вектор , где , . “очка €вл€етс€ допустимой дл€ задачи (2.4.5) при ограничении , которое удовлетвор€етс€ как строгое неравенство . ѕоэтому оно может быть отброшено (как неактивное) при анализе точки на оптимальность.

¬ задаче

, (2.4.6)

минимум достигаетс€ в 0 тогда и только тогда, когда .

»так, если

(2.4.7)

то точка €вл€етс€ решением (2.1.1) и одновременно (2.4.5), а тем самым €вл€етс€ решением (2.4.1). ≈сли же среди компонент есть отрицательные (например, ), то не €вл€етс€ решением (2.4.6), и, увеличива€ , можно уменьшить значение целевой функции в (2.4.6).

»так, сделаем шаг

- -й орт. (2.4.8)

¬ыбор производитс€ из следующих соображений. — увеличением целева€ функци€ уменьшаетс€, однако может нарушитьс€ ограничение , которое в точке , было неактивным. »так, нужно выбрать из услови€

. (2.4.9)

≈сли при этом , то задача не имеет решени€ в силу бесконечного убывани€ функции. ≈сли же , то получаем новую точку ,

где . Ёта точка вновь €вл€етс€ вершиной (она допустима и имеет m положительных компонент, так как -€ компонента стала положительной, а одна из компонент обратилась в 0).

ѕоэтому в ней можно повторить всю процедуру заново. ѕри этом значение целевой функции уменьшилось. —ледовательно, возврат в одну из точек невозможен. ¬ силу конечности общего числа вершин метод конечен.

”слови€ (2.4.7) €вл€ютс€ условием оптимальности в симплекс-методе.





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


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


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

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

Ќачинайте делать все, что вы можете сделать Ц и даже то, о чем можете хот€ бы мечтать. ¬ смелости гений, сила и маги€. © »оганн ¬ольфганг √ете
==> читать все изречени€...

1967 - | 1781 -


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

√ен: 0.014 с.