Cтраница 2
В общем случае множество X ( если оно ограниченное или неограниченное) будем называть многогранником решений задачи линейного программирования. [16]
Если оптимальное решение задачи ( А) существует, то оно достигается на некоторой вершине многогранника решений. [17]
Если максимальное значение целевая функция задачи ( 89) принимает более чем в одной вершине многогранника решений, то она достигает его также во всякой точке, являющейся выпуклой комбинацией данных вершин. [18]
Если оптимальное решение задачи ( А) существует, то оно достигается на некоторой вершине многогранника решений. [19]
Если существует хотя бы один план задачи, для которого значение функционала больше асимптотического, то в многограннике решений существует и вершина с большим значением функционала. [20]
Особенно следует подчеркнуть, что условия МДК ( для произвольного, но фиксированного 0 моделируют в л-мер-ном пространстве многогранник решений наибольшего объема, поскольку они отражают единственное очевидное требование: простой оборудования в течение года ( а значит, и на любом его подинтервале) не должен превышать годовой резерв соответствующего свободного фонда времени. Следовательно, при решении оптимизационных задач с ограничениями ( 50) и ( 51) ЭВМ представляется максимальная свобода варьирования допустимыми планами производства и при этом обеспечивается гарантия выполнения плана Р в течение планируемого года. [21]
Если после введения дополнительного ограничения текущая таблица перестает быть прямо допустимой, то текущее решение, представляющее собой вершину многогранника решений, не удовлетворяет этому дополнительному ограничению. Другими словами, дополнительное ограничение отсекает часть пространства решений. Если дополнительные ограничения не отсекают ни одной целочисленной точки пространства решений исходной задачи, то, вполне вероятно, после введения достаточного числа дополнительных ограничений вершины суженного множества решений будут целочисленными. [22]
Итак, если положительным компонентам некоторого допустимого решения отвечают линейно независимые векторы условий, то это допустимое решение является вершиной многогранника решений. [23]
Теорема 2.13. Если задача линейного программирования имеет оптимальное решение, то линейная функция принимает оптимальное значение в одной из угловых точек многогранника решений. [24]
Предположим, что в задаче ( 1) - ( 3) множество неотрицательных решений системы линейных уравнений ( 2) ( многогранник решений) не пустое и включает более чем одну точку. Тогда исходная задача состоит в определении при каждом параметре t e [ а, ( 3 ] такой точки многогранника решений, в который функция ( 1) принимает max. Чтобы найти эту точку, будем считать t t0 и находим решение полученной задачи ЛП ( 1) - ( 3), то есть определим вершину многогранника решений, в которой функция ( 1) имеет max, либо устанавливаем, что при данном значении t0 задача неразрешима. [25]
В предыдущий главе было показано, что если задача линейного программирования имеет решение, то оно соответствует хотя бы одной угловой точке многогранника решений и совпадает по крайней мере с одним из допустимых базисных решений системы ограничений. Поэтому для решения задачи линейного программирования необходимо перебрать конечное число базисных решений, выбрать среди них то, на котором целевая функция принимает экстремальное значение. Геометрически это соответствует перебору всех угловых ( крайних) точек многогранника. Если оптимальное решение существует, то такой перебор приведет к нахождению оптимального решения. Такой прямой перебор связан с очень большим числом вычислений. [26]
Теорема 1.2. Если основная задача линейного программирования имеет оптимальный план, то максимальное значение целевая функция задачи принимает в одной из вершин многогранника решений. Если максимальное значение целевая функция задачи принимает более чем в одной вершине, то она принимает его во всякой точке, являющейся выпуклой линейной комбинацией этик вершин. [27]
Отметим, что в пространстве, как и на плоскости, оптимальное решение ( коль скоро оно существует) достигается в некоторой вершине многогранника решений ( сравни с выводом на стр. [28]
Определение 1.12. Непустое множество планов основ - Q ной задачи линейного программирования называется многогран - r j пиком решений, а всякая угловая точка многогранника решений - вершиной. [29]
По аналогии с плоским случаем и трехмерным пространством можно себе представить, что оптимальное значение формы ( если оно существует) достигается в некоторой вершине многогранника решений. Несмотря на кажущуюся наглядность этого факта, доказательство его выходит за рамки нашего курса и далеко не просто. [30]