Многогранник - условие
Cтраница 1
Многогранник новых канонических условий образован пересечением новой ( N - М) - мерной плоскости условий с первым координатным углом. [1]
 |
Случай для п 2 и т - 1.| Случай для п - - 3 и m 1. [2] |
Вершинами многогранника условий в данном случае являются точки О ( О, О), А ( 1, 0) и В ( О, 1), у которых не более одной координаты отлично от нуля. [3]
Вершинами многогранника условий служат точки О ( О, О, О), А ( 1 0 0), В ( 0, 1 0) и С ( О, О, 1), причем их координаты содер жат только одну составляющую, не равную нулю. [4]
В параграфе изучается многогранник условий хорошо известной и многосторонне изученной задачи о назначении и ее обобщений. [5]
Соответственно каждая вершина многогранника условий может считаться точкой пересечения п гиперплоскостей, образующих его область, прилегающую к данной вершине. Однако возможны случаи, когда в вершине многогранника условий пересекаются более чем п гиперплоскостей. Примером подобного случая в трехмерном пространстве ( п - 3) является вершина пирамиды, у которой в основании лежит четырехугольник. При этом в вершине пирамиды пересекаются четыре плоскости, служащие ее боковыми гранями. Если в основании пирамиды лежит многоугольник с еще большим числом сторон, то в ее вершине пересекается соответственно большее число плоскостей-граней. [6]
Соответственно каждая вершина многогранника условий может считаться точкой пересечения п гиперплоскостей, образующих его область, прилегающую к данной вершине. Однако возможны случаи, когда в вершине многогранника условий пересекаются более чем п гиперплоскостей. Примером подобного случая в трехмерном пространстве ( п 3) является вершина пирамиды, у которой в основании лежит четырехугольник. При этом в вершине пирамиды пересекаются четыре плоскости, служащие ее боковыми гранями. Если в основании пирамиды лежит многоугольник с еще большим числом сторон, то в ее вершине пересекается соответственно большее число плоскостей-граней. [7]
При канонической форме записи многогранника условий из каждой его вершины исходит jV - М ребер. Выбирая одно ребро, мы выбрасываем из рассмотрения РЕПИНЫ, лежащие на остальных траекториях. Следовательно, за k шагов мы рассматриваем ( N - М) - - ю часть вершин, проходя мимо остальных. [8]
Базисное решение определяет координаты вершины многогранника условий рассматриваемой оптимальной задачи, тогда как допустимое решение может определять координаты любой другой точки этого многогранника, включая и его внутренние точки. [9]
Достаточно показать, что у многогранника условий задачи (6.15) существует целочисленная вершина, минимизирующая гу. Тогда на основании теоремы двойственности линейного программирования и теоремы 6.5 о целочисленности многогранника, являющегося пересечением двух полиматроидов, получаем утверждения теоремы. [10]
Поэтому в самом неблагоприятном случае ( Мя 1 /) многогранник условий может иметь до CJv / 2 2W вершин. Если N - 100, то это число настолько велико, что простой перебор вершин невозможен. [11]
 |
Пример задачи с незамкнутой областью изменения переменных и ограниченным значением критерия оптимальности. [12] |
Максимальное значение критерия оптимальности при этом достигается также на границе многогранника условий в n - мерном пространстве и может соответствовать как вершине этого многогранника, так и его граням, образованным различными пересечениями гиперплоскостей, составляющих этот многогранник. [13]
 |
Область изменения переменных, определяемая условиями ( VIII38. [14] |
Это представляет известные неудобства при поиске оптимального решения обследованием границ многогранника условий, поскольку заранее неизвестно, какие уравнения системы ( VIII37) характеризуют оптимальное решение. [15]
Страницы: 1 2 3