Многогранник - решение
Cтраница 3
По аналогии с плоским случаем и трехмерным пространством можно себе представить, что оптимальное значение формы ( если оно существует) достигается в некоторой вершине многогранника решений в четырехмерном пространстве. [31]
IV, § 6, вывод), что геометрическое место точек, координаты которых удовлетворяют системе линейных неравенств, образует выпуклый многогранник, называемый многогранником решений данной системы. Грани этого многогранника расположены на плоскостях, уравнения которых получаются, если в неравенствах системы знак неравенства заменить точным равенством. Сам многогранник решений является пересечением полупространств, на которые делит пространство каждая из указанных плоскостей. [32]
Следовательно, еслл коэффициент, стоящий в столбце s против нуля, отрицателен, то по ребру s передвигаться из данной вершины можно, при таком движении будем приближаться к многограннику решений. [33]
Таким образом, при переходе от задачи ( 126) - ( 128) к задаче ( 129) - ( 131) уменьшилось число ограничений, однако возросло число переменных. К тому же нам понадобилось определить все вершины многогранников решений D и О2, что не всегда возможно сделать так просто. [34]
 |
Решение оптимизационной задачи методом линейного программирования. [35] |
Ряду произвольных значений F соответствует семейство параллельных плоскостей. Максимальному и минимальному значениям функции соответствуют плоскости, проходящие через вершины многогранника решений. [36]
В двойственной задаче число независимых переменных равно т, и столько же компонент плана ( переменных из левого столбца) приравнено нулю. Следовательно, этот план - опорный, геометрически представляющий собой вершину многогранника решений. Среди таких планов надо искать оптимальный. [37]
Решение сформулированных задач можно найти методами линейного программирования, о чем более подробно будет сказано в дальнейшем. Предположим, что множество неотрицательных решений системы линейных уравнений ( 58) ( многогранник решений) не пусто и включает более чем одну точку. Тогда исходная задача состоит в определении при каждом значении параметра / е [ а, 0 ] такой точки многогранника решений, в которой функция ( 57) принимает максимальное значение. [38]
Правда, мы видели, что оптимальные значения целевой функции достигаются на границе области допустимых решений. Поэтому в случае п неизвестных ( п 3) можно построить n - мерный многогранник решений, найти его вершины и вычислить значения целевой функции в этих точках. Наименьшее среди полученных значений можно принять за искомое, а координаты соответствующей вершины - за оптимальные значения проектных параметров. [39]
 |
Симплекс-таблицы для примера 1 - 3. [40] |
И в этом случае FmaJi и Fmln соответствуют гиперплоскостям, проходящим через вершины многогранника решений. [41]
При этом предполагается, что основное уравнение фильтрации газа линеаризовано одним из известных способов. В задачах линейного программирования максимум целевой функции находится в вершине ( или на плоскости) многогранника решений. Вершина ( точка) определяется координатами л-мерного пространства, являющимися независимыми переменными. Остальные переменные задачи выражаются с помощью линейных соотношений через эти независимые переменные. [42]
Исходя из этого, можно было бы предложить следующий путь решения задачи линейного программирования: найти все допустимые базисные решения и выбрать среди них то, которое минимизирует целевую функцию. Очевидно, такой подход мало эффективен, поскольку в нем отсутствует целенаправленность в переборе вершин многогранника решений. [43]
Предположим, что в задаче ( 1) - ( 3) множество неотрицательных решений системы линейных уравнений ( 2) ( многогранник решений) не пустое и включает более чем одну точку. Тогда исходная задача состоит в определении при каждом параметре t e [ а, ( 3 ] такой точки многогранника решений, в который функция ( 1) принимает max. Чтобы найти эту точку, будем считать t t0 и находим решение полученной задачи ЛП ( 1) - ( 3), то есть определим вершину многогранника решений, в которой функция ( 1) имеет max, либо устанавливаем, что при данном значении t0 задача неразрешима. [44]
Доказанная теорема носит принципиальный характер, так как она предлагает теоретическое обоснование алгоритма решения задач линейного программирования. Согласно этой теоремы, вместо того чтобы исследовать бесконечное множество допустимых решений для нахождения среди них оптимального, необходимо исследовать лишь конечное число угловых точек многогранника решений. Метод аналитического нахождения угловых точек предлагает следующая теорема. [45]
Страницы: 1 2 3 4