Cтраница 4
IV, § 6, вывод), что геометрическое место точек, координаты которых удовлетворяют системе линейных неравенств, образует выпуклый многогранник, называемый многогранником решений данной системы. Грани этого многогранника расположены на плоскостях, уравнения которых получаются, если в неравенствах системы знак неравенства заменить точным равенством. Сам многогранник решений является пересечением полупространств, на которые делит пространство каждая из указанных плоскостей. [46]
IV, § 6, вывод), что геометрическое место точек, координаты которых удовлетворяют системе линейных неравенств, образует выпуклый многогранник, называемый многогранником решений данной системы. Грани этого многогранника расположены на плоскостях, уравнения которых получаются, если в неравенствах системы знак неравенства заменить точным равенством. Сам многогранник решений является пересечением полупространств, на которые делит пространство каждая из указанных плоскостей. [47]
Решение сформулированных задач можно найти методами линейного программирования, о чем более подробно будет сказано в дальнейшем. Предположим, что множество неотрицательных решений системы линейных уравнений ( 58) ( многогранник решений) не пусто и включает более чем одну точку. Тогда исходная задача состоит в определении при каждом значении параметра / е [ а, 0 ] такой точки многогранника решений, в которой функция ( 57) принимает максимальное значение. [48]
Предположим, что в задаче ( 1) - ( 3) множество неотрицательных решений системы линейных уравнений ( 2) ( многогранник решений) не пустое и включает более чем одну точку. Тогда исходная задача состоит в определении при каждом параметре t e [ а, ( 3 ] такой точки многогранника решений, в который функция ( 1) принимает max. Чтобы найти эту точку, будем считать t t0 и находим решение полученной задачи ЛП ( 1) - ( 3), то есть определим вершину многогранника решений, в которой функция ( 1) имеет max, либо устанавливаем, что при данном значении t0 задача неразрешима. [49]
IV, § 6, вывод), что геометрическое место точек, координаты которых удовлетворяют системе линейных неравенств, образует выпуклый многогранник, называемый многогранником решений данной системы. Грани этого многогранника расположены на плоскостях, уравнения которых получаются, если в неравенствах системы знак неравенства заменить точным равенством. Сам многогранник решений является пересечением полупространств, на которые делит пространство каждая из указанных плоскостей. [50]
Для общих задач этот метод применяется тогда, когда задача линейного программирования записана в канонической форме. В этом случае автоматически находится начальная вершина допустимой области, а затем по описанной выше схеме осуществляется направленный перебор вершин. С этой целью для каждой из внебазисных переменных по формуле (6.5) подсчитываются величины ck - zk, которые называются относительными оценками. Выбирается переменная xk, для которой ck - zk 0 и, кроме того, вектор условий, соответствующий xk, имеет хотя бы одну положительную компоненту. Для каждого i - ro уравнения, для которого ct ik 0, вычисляем рУа: и выбираем то уравнение, где это отношение минимально. Затем по методу Жордана - - Гаусса исключаем переменную xk из всех уравнений, кроме 1-го. В результате перейдем к задаче линейного программирования, записанной в канонической форме, которая автоматически определяет новую верщину многогранника решений. Как следует из предыдущего параграфа, значение функции цели в новой вершине будет меньше, чем в исходной. Для найденной вершины выполняем аналогичный цикл операций, именуемый итерацией. Этот процесс продолжается до тех пор, пока относительные оценки внебазисных переменных не окажутся положительными. В этом случае переход к новой вершине нецелесообразен. Покажем, что тогда задача линейного программирования решена. [51]