Cтраница 3
Оно показало, что алгоритм нахождения ОНР двойственным симплекс-методом очень устойчив при весах ( 34), а при весах ( 33) могут возникать осложнения. Более детальный анализ показал, что веса ( 33) приводят к параллельности некоторых ребер двойственного многогранника условий и плоскости целевой функции. [31]
Применение двойственного симплекс-метода к задаче линейного программирования может натолкнуться на сложности, если задача вырождена. Геометрически это означает, что одинаковые значения целевой функции достигаются более чем в одной вершине двойственного многогранника условий. [32]
Теория матроидов обобщает многие результаты теории графов, проективной геометрии, теории электрических цепей. В терминах экстремальных задач на матроидах могут быть сформулированы различные оптимизационные задачи, в первую очередь задачи оптимизации на сетях. Покажем, что многогранники условий в большинстве экстремальных задач на матроидах являются целочисленными. [33]
Найдем какую-нибудь вершину многогранника и все ребра, выходящие из этой вершины. Пойдем вдоль того из ребер, по которому функция убывает. Придем в следующую вершину, найдем выходящие из нее ребра и повторим процесс. Когда мы придем в такую вершину, что вдоль всех выходящих из нее ребер функция возрастает, то минимум достигнут. Поскольку L ( x) - линейная функция, а многогранник условий выпуклый, то этот процесс всегда сходится к решению задачи, причем за конечное число шагов. [34]