Cтраница 2
Ясно, что любое из условий (4.2) или (4.4) является жестким ограничением. Чтобы убедиться в том, что неравенство с номером t является нежестким ограничением многогранника, достаточно указать точку многогранника, координаты которой удовлетворяют этому неравенству как строгому. [16]
Предположим, что в задаче ( 1) - ( 3) множество неотрицательных решений системы линейных уравнений ( 2) ( многогранник решений) не пустое и включает более чем одну точку. Тогда исходная задача состоит в определении при каждом параметре t e [ а, ( 3 ] такой точки многогранника решений, в который функция ( 1) принимает max. Чтобы найти эту точку, будем считать t t0 и находим решение полученной задачи ЛП ( 1) - ( 3), то есть определим вершину многогранника решений, в которой функция ( 1) имеет max, либо устанавливаем, что при данном значении t0 задача неразрешима. [17]
Точки многогранника, в которых это неравенство выполнено как равенство, по определению являются его граничными точками. Вообще, граничными называются те точки многогранника, в которых обращаются в равенства одно или несколько неравенств, выполненных как строгие неравенства для каких-либо точек многогранника. [18]
Коэффициенты линейной функции определяют семейство параллельных прямых на плоскости и направление, в котором увеличивается значение функции. При существовании допустимой области решений для задачи минимизации, прямую на плоскости надо перемещать параллельно самой себе в сторону уменьшения ее значений до тех пор, пока она еще будет содержать точки многогранника. [19]
В предыдущий главе было показано, что если задача линейного программирования имеет решение, то оно соответствует хотя бы одной угловой точке многогранника решений и совпадает по крайней мере с одним из допустимых базисных решений системы ограничений. Поэтому для решения задачи линейного программирования необходимо перебрать конечное число базисных решений, выбрать среди них то, на котором целевая функция принимает экстремальное значение. Геометрически это соответствует перебору всех угловых ( крайних) точек многогранника. Если оптимальное решение существует, то такой перебор приведет к нахождению оптимального решения. Такой прямой перебор связан с очень большим числом вычислений. [20]
Так как t - пространство тг - мерно, будем говорить о ( ri - 1) - мерной гиперплоскости, определяющей многогранник Р ( G, г), g0), как о его грани. Грань многогранника определяется неравенством. Под этим понимается, что все точки грани удовлетворяют ему как равенству, а все точки многогранника - как неравенству. Соответствие между вершинами и гранями многогранников Рх ( В, N, Ь) и Р ( G, т ], go) непосредственное. [21]
Решение сформулированных задач можно найти методами линейного программирования, о чем более подробно будет сказано в дальнейшем. Предположим, что множество неотрицательных решений системы линейных уравнений ( 58) ( многогранник решений) не пусто и включает более чем одну точку. Тогда исходная задача состоит в определении при каждом значении параметра / е [ а, 0 ] такой точки многогранника решений, в которой функция ( 57) принимает максимальное значение. [22]
Пусть dim Л п и для меньших размерностей теорема доказана. Так как множество S замкнуто, ограниченная сверху функция f на нем принимает максимальное значение в некоторой точке а. Это значит, что f принимает максимальное значение в точке непустого многогранника S -, который является гранью S и лежит в аффинном подпространстве a fj ( a) 0 размерности п - 1, ибо fi непостоянна. [23]
Интуитивно площадь поверхности тела можно представить себе как площадь бумаги, пошедшей на оклеивание тела, или ткани, которой его можно обшить. В случае изученных нами тел вращения ( цилиндра, конуса, шара) их площадь поверхности можно определить как предел площадей поверхностей описанных около них многогранников при условии, что все точки этих многогранников становятся сколь угодно близкими к поверхности этих тел. Идея такого определения состоит в том, что при неограниченном приближении всех точек описанного многогранника к поверхности данного тела его грани будут очень похожи на близкие к ним куски поверхности этого тела. [24]
Случай dim А 0 очевиден. Пусть dim A п, и пусть для меньших размерностей теорема доказана. Так как множество S замкнуто, то ограниченная сверху функция / на нем принимает максимальное значение в некоторой точке а. Считаем теперь, что fi ( a) 0 для некоторого г. Это значит, что / принимает максимальное значение в точке непустого многогранника Si, который является гранью S и лежит в аффинном подпространстве а fi ( a) 0 размерности п - 1, ибо fa непостоянна. [25]