Cтраница 1
Многогранник решений не ограничен, и один из экстремумов достигается. [1]
Многогранник решений имеет конечное число вершин, поэтому за конечное число шагов их можно перебрать все. Кроме того, мы перебираем вершины упорядочение, приближаясь на каждом шаге к вершине, обеспечивающей оптимум. [2]
Предположим, что многогранник решений является ограниченным. [3]
Может оказаться, что многогранник решений не будет содержать ни одной целочисленной точки. [4]
Покажем, что х является вершиной многогранника решений. [5]
Чтобы новая каноническая система определяла вершину многогранника решений, ее правые части должны быть неотрицательными. [6]
Геометрически: мы стоим в вершине многогранника решений, через которую проходит п гиперплоскость. Из этой вершины надо по какому-то ребру перейти в следующую, не оторвавшись от многогранника. [7]
Ответ на вопрос, в какой точке многогранника решений возможно решение задачи линейного программирования, дается в следующей фундаментальной теореме. [8]
Допустимое решение х является вершиной допустимой области ( многогранника решений) тогда и только тогда, когда оно базисное. [9]
Получим точку пересечения данных п гиперплоскостей, которая будет вершиной многогранника решений или какого-то другого многогранника, ограниченного указанными плоскостями. [10]
Эти полупространства, пересекаясь, образуют общую часть, называемую многогранником решений. [11]
Геометрически добавление каждого такого линейного ограничения отвечает проведению гиперплоскости, отсекающей от многогранника решений регуляризованной задачи старую оптимальную точку с дробными координатами, но не затрагивающей ни одной из целочисленных точек этого многогранника. [12]
Геометрически добавление каждого такого линейного ограничения соответствует проведению гиперплоскости, отсекающей от многогранника решений регуляризованной задачи старую оптимальную точку с дробными координатами, но не затрагивающей ни одной из целочисленных точек этого многогранника. [13]
Итак, чтобы решить задачу линейного программирования, достаточно сделать перебор крайних точек многогранника решений. При этом возникает вопрос о нахождении произвольной вершины допусти - мой области и перехода в другую вершину. [14]
В задаче дробно-линейного программирования ограничения линейны, а экстремум функционала достигается в вершине многогранника решений. Это сходство с линейным программированием позволяет решать дробно-линейные задачи обычным симплекс-методом с видоизмененным критерием оптимальности. [15]