Число допустимых решений ЗЛП

[Andrey_Kireew]

ИСН в сообщении #1447623 писал(а):

В данном случае - трёхмерная грань четырёхмерного тела

Т.е. это грань, нормальная одной из координатных осей, и их число не может быть больше размерности. Теперь понятно.

Но тут сразу напрашивается вопрос. Ведь в многограннике таких гаперграней может не быть вообще, и всё это грубо говоря зависит от ориентации координатных осей. Но ведь число вершин не может зависит от выбора системы координат.

starper в сообщении #1447628 писал(а):

В нашей задаче гиперграни высекают ограничения, если заменить неравенства на равенства

Я понимаю, что равенства в действительности понижают размерность, т.к. позволяют выразить 1 переменную через остальные. Если все ограничения заданы как равенства - то получается просто СЛАУ, но решение будет зависеть от того, какие переменные войдут в базис. Т.е. из числа переменных нужно вычесть число ограничений - равенств. Эта разность и будет истинной размерностью выпуклого многогранника, число вершин которого определяет количество допустимых решений ЗЛП, правильно?

[Someone]

Andrey_Kireew в сообщении #1447700 писал(а):

Т.е. это грань, нормальная одной из координатных осей

С какой стати?

[starper]

Andrey_Kireew в сообщении #1447700 писал(а):

решение будет зависеть от того, какие переменные войдут в базис

Простите, не понял, можете уточнить, что имеется в виду?

Andrey_Kireew в сообщении #1447700 писал(а):

Т.е. из числа переменных нужно вычесть число ограничений - равенств. Эта разность и будет истинной размерностью выпуклого многогранника, число вершин которого определяет количество допустимых решений ЗЛП, правильно?

Ну да, в общем случае верно

[Andrey_Kireew]

starper в сообщении #1447725 писал(а):

Ну да, в общем случае верно

Немного подумав, прихожу к выводу, что неверно. Ведь сняв все ограничения, никакого многогранника не остаётся. Оставшиеся переменные становится ничем не ограниченными.

-- 27.03.2020, 21:08 --

В общем, то что число итераций связано с числом возможных комбинаций базисных переменных, похоже на правду. Тем более, что это у меня подтверждается экспериментально. Но как связать со всем этим многогранник и число его вершин - большой большой вопрос. А ведь в объяснении симплекс метода только об этом пресловутом многограннике и говорится - о движении от одной вершины к другой. Может Вы Someone прольёте свет на эту тайну, будучи специалистом в этой области?

[starper]

Andrey_Kireew, если говорить о многограннике, то да, там еще от знаков неравенств зависит, может одна гиперплоскость отсечь многогранник, а может и n в общем положении не отсечь. Вопросы о существовании решения не так тривиальны, как у системы уравнений.

-- 27.03.2020, 20:33 --

Andrey_Kireew в сообщении #1447734 писал(а):

В общем, то что число итераций связано с числом возможных комбинаций базисных переменных, похоже на правду. Тем более, что это у меня подтверждается экспериментально. Но как связать со всем этим многогранник и число его вершин - большой большой вопрос.

Например, если ограничения задают гиперкуб все как раз состыковывается. $2^n$ вершин у него. И у нас n неравенств. Количество вершин оценивается для n переменных с n ограничениями ограничивается сверху как $\binom{1}{n} + \binom{2}{n}+...+ \binom{n}{n} = 2^n$
Может n ограничений высекать меньше вершин, но больше не может

[Andrey_Kireew]

Тут не вопросы существование, а вопрос о максимальном числе вершин многогранника при заданном числе ограничений и заданном количестве переменных. Что то мне подсказывает, что на него есть вполне однозначный ответ.

-- 27.03.2020, 22:10 --

starper в сообщении #1447738 писал(а):

Количество вершин оценивается для n переменных с n ограничениями ограничивается сверху как $\binom{1}{n} + \binom{2}{n}+...+ \binom{n}{n} = 2^n$

Вообще, здравый смысл подсказывает, что при равенстве числа переменных числу ограничений, ЗЛП имеет единственное решение, так как все переменные входят в базис. Что Вы думаете по этому поводу?

[Someone]

Andrey_Kireew в сообщении #1447734 писал(а):

Может Вы Someone прольёте свет на эту тайну, будучи специалистом в этой области?

Специалистом в "этой" области я не являюсь, но давайте Вы для начала запишете задачу линейного программирования именно в той форме, в какой к ней применяется симплекс-метод. То, что у Вас написано в первом сообщении, в симплекс-метод не лезет:

Andrey_Kireew в сообщении #1447283 писал(а):

$$\left\{ \begin{array}{rcl} &a_{1,1}x_1+a_{1,2}x_2+a_{1,3}x_3+a_{1,4}x_4>L_1& \\ &a_{2,1}x_1+a_{2,2}x_2+a_{2,3}x_3+a_{2,4}x_4>L_2& \\ &a_{3,1}x_1+a_{3,2}x_2+a_{3,3}x_3+a_{3,4}x_4>L_3& \\ \end{array} \right.$$

Три гиперплоскости в четырёхмерном пространстве могут образовать "многогранник" не более чем с одной вершиной.

И я не вижу здесь никакой реакции на моё замечание. Почему Вы решили, что трёхмерная грань четырёхмерного многогранника должна быть непременно нормальна одной из координатных осей и какую размерность имеют остальные его грани?

P.S. Для записи всяких систем очень удобно окружение cases.

[starper]

Andrey_Kireew в сообщении #1447740 писал(а):

Вообще, здравый смысл подсказывает, что при равенстве числа переменных числу ограничений, ЗЛП имеет единственное решение, так как все переменные входят в базис. Что Вы думаете по этому поводу?

В самом начале я же упоминал, что базисные решения и вершины многогранника, которые задают ограничения - не одно и то же. Если система из 2 ограничений задана на 2-мерном
пространстве, это же не значит, что одну вершину многогранник имеет или что вы имели в виду?

[Andrey_Kireew]

Someone в сообщении #1447749 писал(а):

Почему Вы решили, что трёхмерная грань четырёхмерного многогранника должна быть непременно нормальна одной из координатных осей и какую размерность имеют остальные его грани?

Для того, чтобы ответить на этот вопрос, нужно прояснить, какой смысл Вы вкладываете в понятие размерность грани?
Я Вас не понимаю. Мне, возможно ошибочно, представляется, что n-мерный многогранник - это многогранник, расположенный в n-мерном пространстве. Каждая вершина у него задаётся n координатами. И грани его тоже находятся в n мерном пространстве. Утверждение 3-х мерная грань 4-х мерного многогранника ставит меня в тупик. Это что то на грани абсурда. В моей голове, по крайней мере, такое никак не укладывается.

-- 27.03.2020, 23:34 --

starper в сообщении #1447753 писал(а):

или что вы имели в виду?

Это про ограничения типа равенств. В таком случае как бы да. Но какой при равенствах может быть многогранник я не представляю. Поэтому я специально записал систему ограничений как положено. На плоскости тогда будет не 1 единственное решение, а треугольник с 3-мя вершинами. Но чтобы свести неравенства к равенствам, мы обязаны ввести ещё столько же вспомогательных переменных. Это я к тому, что с ограничениями типа равенств число переменных никогда не будет равно числу ограничений.

[starper]

Andrey_Kireew, мы же хотим выяснить, сколько максимум вершин может быть? Тогда можно смело неравенства на равенства заменить, на переменные же условия неотрицательности наложены, то есть n неравенств у нас априори есть, поэтому и многогранник получится. Когда вы приводили свои рассуждения о 2-х и 3-х мерном многограннике, то прямыми и плоскостями разрезали же, а не полуплоскостями и полупространствами, потому что этого достаточно, чтобы получить информацию о максимуме вершин.

[Andrey_Kireew]

starper в сообщении #1447763 писал(а):

на переменные же условия неотрицательности наложены

я вообще об этом нигде не писал, но пусть даже так. Всё равно, при равенстве числа переменных числу остальных ограничений, решение ЗЛП единственно. А раз так, то и вершина этого гипотетического многогранника должна быть как бы одна. Но с другой стороны, это тоже абсурд. Что за такой многогранник с одной вершиной - как то не нормально всё это.

[starper]

Andrey_Kireew, да нет же, есть вершины, которые имеют ровно n ненулевых координат, также могут быть вершины, которые имеют n-1 (n число дополнительных ограничений) ненулевую координату и так до 1 ненулевой координаты. Если в пространстве ограничений высекается единичный куб (это бывает, когда 3 дополнительных ограничения наложены), не значит же это, что решение будет только в точке $(1, 1, 1)$. Решением называется и точка $(0, 0, 1)$. Но только оно не базисное. А базисные решения - не есть все вершины многогранника, а только их подмножество.

-- 28.03.2020, 00:13 --

Правда, именно куб, мне кажется, не может быть решением, так как тогда вектор-столбцы будут линейно-зависимы

[Andrey_Kireew]

starper, мне нужно всё это обмозговать, пока многое непонятно и концы с концами не сходятся. Надеюсь, что со временем кое что проясниться.

[Andrey_Kireew]

Всё таки удалось кое что выяснить. По этому вопросу более менее понятно написано в фундаментальном труде Юдина и Гольшштейна. По крайней мере - на счёт многомерных граней всё стало понятно. Понятие это трактуется намного шире, чем я мог себе предположить. Вершина - это нуль-мерная грань, ребро - одномерная. В трёхмерном пространстве, понятно, остаётся место только для двухмерной грани. В многомерном случае - многогранник имеет грани всех высших размерностей. Видимо в этом и причина недоразумения. Там есть раздел "Выпуклые многогранные множества", на стр. 112 даётся верхняя оценка количества вершин многомерного многогранника

$$N=C^n_k,$$

где n - число переменных, k - общее число ограничений (и равенств и неравенств).
В общем, получается, что это как раз число возможных комбинаций базисных переменных.

Так же, хотелось бы добавить, может кому будет интересно: количество итераций, необходимых для достижений оптимального решения, примерно равно двоичному логарифму от числа вершин многогранника задачи $N$. Конечно, это очень примерно, но всё же, хоть какая то оценка. На малых задачах она работает довольно хорошо, на больших - результаты могут различаться в разы. Но всё равно, в разы это не на порядки.

(Оффтоп)

к стати, кто ни будь знает, как сделать в LaTex отступ первой строки (табуляцию)

[Евгений Машеров]

Допустимым решением ЗЛП является любая точка в пространстве переменных, для которой выполняются все ограничения. Это значит, что допустимых точек бесконечно много. Некоторые алгоритмы (методы внутренней точки - эллипсоидов, Кармаркара и пр.) это используют и идут по внутренности области ограничений. Другие, исторически первые и практически в основном и используемые, учитывают тот факт, что если ограничения - строгие неравенства, то можно улучшить решение, пока в равенства не превратятся столько ограничений, сколько переменных. И рассматриваются не произвольные точки, а лишь точки, в которых пересекаются n плоскостей ограничений. Вообще говоря, не все они являются допустимыми, поскольку могут не выполняться какие-то не входящие в эти n (n - число переменных) ограничения. Поэтому число вершин многоугольника, которые надо рассматривать, переходя от одной к другой с улучшением целевой функции, как правило, куда меньше числа наборов из k по n.