Ћекции.ќрг


ѕоиск:




 атегории:

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

 

 

 

 


ќбщие сведени€ о симплексном методе




—имплексный метод решени€ задачи линейного программировани€.

ќбщие сведени€ о симплексном методе.

Ќа предыдущих лекци€х мы рассмотрели основные теоремы линейного программировани€, из которых следует, что если задача линейного программировани€ имеет оптимальное решение, то оно соответствует хот€ бы одной угловой точке многогранника решений и совпадает, по крайней мере, с одним из допустимых решений. √еометрически это соответствует перебору всех угловых точек многогранника. ѕрактическое осуществление такого перебора св€зано с огромными трудност€ми, так как дл€ реальных задач (где число переменных на много больше 2-х) число допустимых базисных решений хот€ и конечно, но очень велико.

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

 

 


ќбласть допустимых решений: HAB DTG. ƒопустим точка ј соответствует исходному допустимому базисному решению. ћожно в разную сторону двигатьс€ от точки ј, только в одном случае надо будет перебрать большее число угловых точек.

»де€ последовательного улучшени€ решени€ легла в основу универсального метода решени€ задачи линейного программировани€ Ц симплексного метода.

¬первые метод был предложен американским ученым ƒанцигом в 1949 году, однако еще в 1939 году основные идеи методы были разработаны российским ученым  анторовичем.

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

ƒл€ реализации симплексного метода необходимо знать 3 основных элемента:

1. —пособ определени€ какого-либо первоначального допустимого базисного решени€;

2. ѕризнак проверки оптимальности найденного решени€.

3. ѕравила перехода к лучшему (точнее, не худшему) решению;

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

ћы подробно рассмотрим наиболее простой алгоритм симплексного метода.

 





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


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


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

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

Ќеосмысленна€ жизнь не стоит того, чтобы жить. © —ократ
==> читать все изречени€...

2089 - | 1830 -


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

√ен: 0.007 с.