2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Число допустимых решений ЗЛП
Сообщение26.03.2020, 00:55 


07/10/15

2401
Доброе утро уважаемые участники. Давно не даёт покоя один вопрос - определение числа допустимых решений ЗЛП. Насколько мне известно, что допустимые решения находятся в вершинах многомерного многогранника. Число таких вершин равно произведению числа ограничений и числа переменных. С другой стороны, используя комбинаторные оценки, получается совсем другое число допустимых решений ЗЛП, которое намного больше и лично мне представляется более правдоподобным. Например, для системы ограничений:
$$\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.$$

число допустимых решений
$$N=\frac{4!}{3!\cdot1!}=4$$
а число вершин многогранника
$$N=4 \cdot 3 =12$$

в общем не совпадает. Может кто нибудь подскажет, в чём у меня ошибка?

 Профиль  
                  
 
 Re: Число допустимых решений ЗЛП
Сообщение26.03.2020, 07:21 
Заслуженный участник
Аватара пользователя


03/06/08
1161
МО
Andrey_Kireew в сообщении #1447283 писал(а):
Число таких вершин равно произведению числа ограничений и числа переменных

Почему?

 Профиль  
                  
 
 Re: Число допустимых решений ЗЛП
Сообщение26.03.2020, 14:53 


07/10/15

2401
пианист в сообщении #1447332 писал(а):
Почему?

Это приблизительно. Если число ограничений меньше размерности, то пространство не ограничено. Если число ограничений равно n+1 (где n размерность) получается простейший n+1 - аэдр. Далее, каждое новое ограничение даёт n-1 новых вершин. При этом, вершины всё время остаются n валентными, и этот процесс может продолжаться бесконечно.
Получается примерно произведение. Откуда катастрофический рост количества вершин, который по идее должен наблюдаться, я пока понять не могу

 Профиль  
                  
 
 Re: Число допустимых решений ЗЛП
Сообщение26.03.2020, 18:26 


13/04/18
95
Andrey_Kireew, насколько я знаю, допустимым решением называют любое, которое удовлетворяет ограничениям, то есть в вашем примере их бесконечно. То, что вы назвали числом допустимых решений - это, похоже, число базисных решений, то есть решений, которые построены на линейно-независимых векторах, которые образуют базис пространства условий. А число вершин многогранника - это число угловых точек из пространства решений, (угловые точки - те, которые не могут быть выражены, как выпуклая комбинация векторов из пространства решений), они не могут иметь больше, чем m ненулевых координат (m - размерность пространства условий), но может быть меньше, чем m, поэтому число вершин многогранника больше чем число базисных решений.

 Профиль  
                  
 
 Re: Число допустимых решений ЗЛП
Сообщение26.03.2020, 20:43 


07/10/15

2401
starper в сообщении #1447440 писал(а):
То, что вы назвали числом допустимых решений - это, похоже, число базисных решений, то есть решений, которые построены на линейно-независимых векторах, которые образуют базис пространства условий

можно сказать и так

starper в сообщении #1447440 писал(а):
поэтому число вершин Многогранника больше чем число базисных решений

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

 Профиль  
                  
 
 Re: Число допустимых решений ЗЛП
Сообщение26.03.2020, 21:21 


13/04/18
95
Andrey_Kireew в сообщении #1447491 писал(а):
как я понимаю число, базисных решений - это число возможных комбинаций векторов условий в базисе, оно находится через факториалы и очень велико, а число вершин - это просто произведение размерности и числа ограничений. Или может я что то неверно понимаю?

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

 Профиль  
                  
 
 Re: Число допустимых решений ЗЛП
Сообщение26.03.2020, 22:47 


07/10/15

2401
starper в сообщении #1447513 писал(а):
а про число вершин как произведение это откуда факт?

вот откуда
Andrey_Kireew в сообщении #1447394 писал(а):
Если число ограничений меньше размерности, то пространство не ограничено. Если число ограничений равно n+1 (где n размерность) получается простейший n+1 - аэдр. Далее, каждое новое ограничение даёт n-1 новых вершин. При этом, вершины всё время остаются n валентными, и этот процесс может продолжаться бесконечно

я пришел к такому умозаключению.
Например берём треугольник на плоскости. Каждое линейное ограничение добавляет максимум 1 новую вершину, и это в лучшем случае. Берём тетраэдр - каждое новое линейное ограничение добавляет 2 вершины, опять же в лучшем случае.
Я предполагаю, что в любом n-мерном случае будет та же картина. А если так, то число вершин не может так сильно расти.
Где ошибка в моих рассуждениях?

 Профиль  
                  
 
 Re: Число допустимых решений ЗЛП
Сообщение26.03.2020, 23:10 


13/04/18
95
Andrey_Kireew в сообщении #1447394 писал(а):
Если число ограничений меньше размерности, то пространство не ограничено.
Не факт, кстати, если, например в вашей системе все коэффициенты $a_i_j$ отрицательны, то уже точно будет ограниченным

-- 26.03.2020, 23:13 --

Andrey_Kireew в сообщении #1447394 писал(а):
Если число ограничений равно n+1 (где n размерность) получается простейший n+1 - аэдр.

И в этом случае может неограниченное множество получиться, все зависит от коэффициентов в системе

 Профиль  
                  
 
 Re: Число допустимых решений ЗЛП
Сообщение26.03.2020, 23:23 


07/10/15

2401
starper в сообщении #1447565 писал(а):
И в этом случае может неограниченное множество получиться, все зависит от коэффициентов в системе

может, но больше n+1 вершин не получить никак, вот в чём дело

 Профиль  
                  
 
 Re: Число допустимых решений ЗЛП
Сообщение27.03.2020, 02:20 


13/04/18
95
Andrey_Kireew, я понял, что вы имеете в виду. Но для двух и трехмерного пространства ваши оценки и комбинаторные совпадают. Значит в более высоких размерностях по-другому происходит. Тоже стало интересно почему, думать надо

-- 27.03.2020, 02:37 --

Например, для трехмерного пространства 3 гиперплоскости могут высечь куб, т. е. 8-вершинник. Для 4-мерного 4 гиперплоскости 16-вершинник могут высечь, для пятимерного уже 32 и т.д., то есть уже для пятимерного пространства оценка одно ограничение - не больше n+1 вершины не работает

 Профиль  
                  
 
 Re: Число допустимых решений ЗЛП
Сообщение27.03.2020, 09:12 


07/10/15

2401
starper в сообщении #1447587 писал(а):
Например, для трехмерного пространства 3 гиперплоскости могут высечь куб

в трёхмерном пространстве они не гипер - а просто плоскости, и трёх - недостаточно, чтобы образовать куб, нужно 6 штук, это я могу представить. Если потом его дробить, так как я раньше описывал, срезая вершины, то каждая новая плоскость будет давать так же 2 новые вершины. Все вершины так и остаются трёхвалентными. И вообще, при срезании вершины любой валентности, новые вершины станут трёхвалентными. И грани, по большей части будут все треугольные. Ну в 3D графике так ведь и есть - все грани у каких угодно сложных фигур треугольные.
Да и не только куб, могут и более сложные фигуры высечь, но число вершин, приходящееся на одну плоскость будет меньше, чем в случае с тетраэдром. Я же рассматриваю случай с максимально возможным числом вершин.

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

Вот например, из теоремы Эйлера для выпуклого многогранника следует:
$$V=2+R-G $$
число граней G - это и есть число ограничений, а число рёбер R - равно половине произведения числа вершин и их валентности (которая равна размерности пространства Size).
Получаем:
$$V=(G-2)/ (Size/2-1)$$
это вообще кошмар какой то, хотя, для тетраэдра и для куба работает. Вообще, есть серьёзные подозрения, что теорема Эйлера справедлива лишь для трёхмерного пространства. Видимо, он так и не смог до конца постичь этой тайны.

Об этом косвенно свидетельствует и тот факт, что работы Эйлера пытались обобщить, в частности Пуанкаре, в википедии даже приводится какая то странная формула, но что конкретно она обобщает, я так к сожалению и не понял. В том смысле, что неясно как по ней вычислить количество вершин N-мерного многогранника.

 Профиль  
                  
 
 Re: Число допустимых решений ЗЛП
Сообщение27.03.2020, 09:31 
Заслуженный участник
Аватара пользователя


18/05/06
13341
с Территории
Andrey_Kireew в сообщении #1447614 писал(а):
Вообще, есть серьёзные подозрения, что теорема Эйлера справедлива лишь для трёхмерного пространства.
"Есть подозрение, что ходить ногами можно только по поверхности." Разумеется, а как ещё-то? В каком ещё пространстве есть все эти объекты, из которых состоит формулировка теоремы, и только они?

Есть обобщение на любые размерности, известно давно. Оно формулируется не сложнее, чем для 3D. Скажем, для размерности 4: N(вершин) - N(рёбер) + N(граней) - N(гиперграней) = 0.

 Профиль  
                  
 
 Re: Число допустимых решений ЗЛП
Сообщение27.03.2020, 10:05 


07/10/15

2401
ИСН в сообщении #1447615 писал(а):
гиперграней

уточните, какой смысл Вы вкладываете в понятие "гипергрань" чтобы можно было воспользоваться этой формулой

 Профиль  
                  
 
 Re: Число допустимых решений ЗЛП
Сообщение27.03.2020, 10:57 
Заслуженный участник
Аватара пользователя


18/05/06
13341
с Территории
В данном случае - трёхмерная грань четырёхмерного тела.

 Профиль  
                  
 
 Re: Число допустимых решений ЗЛП
Сообщение27.03.2020, 11:22 


13/04/18
95
Andrey_Kireew в сообщении #1447614 писал(а):
starper в сообщении #1447587 писал(а):
Например, для трехмерного пространства 3 гиперплоскости могут высечь куб

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

Ну я имел в виду для нашей задачи, в ЗЛП же условие неотрицательности на переменные установлено и получается, что $n$ гиперплоскостей это условие дает, и еще $n$ ограничений дают нам новые гиперплоскости.

-- 27.03.2020, 11:45 --

В нашей задаче гиперграни высекают ограничения, если заменить неравенства на равенства. Например, единичный 4-куб получился бы, если бы гиперплоскости высекли бы множество с вершинами вида $(1, 0, 0, 0), (1, 1, 0, 0) $ и т. д., всего 2^4 вершин. 3-мерные грани получаются как множества, натянутые на 8 точек (только таких, чтобы их выпуклые комбинации не попадали внутрь 4-куба)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 30 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group