Прогнозирование устойчивости. Жигулин Г.П - 123 стр.

UptoLike

ВУЗ: 

Университет ИТМО | Санкт-Петербург

Составители: 

Рубрика: 

125
5. для определения оптимального решения достаточно перебрать все
вершины ОДР и выбрать ту, где функция
L достигает максимума
(минимума);
6. если число свободных переменных равно 2, а число базисных
m и
оптимальное решение существует, то оно всегда достигается в точке,
где по крайней мере две из переменных обращаются в нуль (в нашем
примере: на максимум –
0
*
2
*
1
== xx , на минимум – 0
*
7
*
6
== xx );
7. если в опорной точке пересекаются более двух ограничивающих
прямых, то такой случай называют вырожденным, и тогда в
оптимальном решении обращаются в нуль не две, а столько
переменных, сколько ограничивающих прямых пересекаются в опорной
точке.
2. Если
3=− mn , то геометрические построения необходимо производить в
трехмерном пространстве. Ограничения представляются в виде плоскостей.
ОДР будет представлять собой выпуклый многогранник, ограниченный этими
плоскостями.
Роль «основной прямой» в этом случае будет выполнять «основная
плоскость».
На этом мы останавливаться не будем, т.к. все выводы предыдущего случая
аналогичны, но менее обозримы геометрически.
Вывод. Мы рассмотрели простейший способ решения задач линейного
программирования, применимый в случае 2 независимых переменных. Тогда
задача сводится к решению плоской геометрической задачи.
6.3. Аналитические методы решения задач ЛП
Для 3=− mn геометрическая интерпретация задач ЛП уже (как мы видели)
затруднительна и непригодна для
3>
−
mn . Для задач такого типа разработаны
аналитические методы:
1. метод последовательного улучшения решения;
2. метод последовательного уточнения оценок;
3. метод сокращения невязок;
4. распределительный метод;
5. метод потенциалов;
6. венгерский метод и др.
Содержание всех названных методов одно и то же, а именно, оптимальное
решение ищется путем последовательных приближений. Вначале задаются
некоторым допустимым решением, а затем изменяют его в направлении
приближения к оптимальному.
Отличие этих методов заключается:
– вычислительными алгоритмами;
– областью применения.

Страницы