2014 dxdy logo

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

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


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


В этом разделе нельзя создавать новые темы.



Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Вопрос по системе ограничений
Сообщение01.02.2016, 20:52 
Заслуженный участник
Аватара пользователя


22/01/11
2641
СПб
ГАЗ-67
а... не умеете
тогда добавьте условие: попарные произведения элементов в каждой строке равны нулю

 Профиль  
                  
 
 Re: Вопрос по системе ограничений
Сообщение01.02.2016, 20:53 


20/03/14
12041
alcoholist в сообщении #1095939 писал(а):
если добавить условие, которое дал Евгений Машеров -- положительность и целочисленность, то верно

Не, ну если добавить, то конечно.

 Профиль  
                  
 
 Re: Вопрос по системе ограничений
Сообщение01.02.2016, 20:55 
Заслуженный участник
Аватара пользователя


22/01/11
2641
СПб
Матрица содержит ровно одну единицу в каждой строке и ровно одну единицу в каждом столбце в том и только в том случае, когда выполнены оба условия:
1) суммы элементов в каждой строке и в каждом столбце равны 1
2) попарные произведения элементов в каждой строке равны нулю

-- Пн фев 01, 2016 20:58:15 --

Это $2n+\frac{n^2(n-1)}{2}$ условий для матрицы $n\times n$

 Профиль  
                  
 
 Re: Вопрос по системе ограничений
Сообщение01.02.2016, 20:58 


09/06/06
367
Совсем не подходит.Совсем.Только линейные равенства.

 Профиль  
                  
 
 Re: Вопрос по системе ограничений
Сообщение01.02.2016, 21:00 
Заслуженный участник
Аватара пользователя


22/01/11
2641
СПб
ГАЗ-67
что не подходит? равенство нулю не проверить?

 Профиль  
                  
 
 Re: Вопрос по системе ограничений
Сообщение01.02.2016, 21:14 


09/06/06
367
Попарные произведения не подходят.

 Профиль  
                  
 
 Re: Вопрос по системе ограничений
Сообщение01.02.2016, 21:33 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Целочисленность невозможно задать линейными неравенствами.

 Профиль  
                  
 
 Re: Вопрос по системе ограничений
Сообщение01.02.2016, 21:36 


09/06/06
367
Xaositect в сообщении #1095954 писал(а):
Целочисленность невозможно задать линейными неравенствами.

Равенствами.
Может стоит попробовать попарные суммы столбцов и строк?

 Профиль  
                  
 
 Re: Вопрос по системе ограничений
Сообщение01.02.2016, 21:40 
Заслуженный участник
Аватара пользователя


22/01/11
2641
СПб
ГАЗ-67 в сообщении #1095950 писал(а):
Попарные произведения не подходят.

тогда никак
либо "замаскировать":
а) все элементы неотрицательны ($a=\operatorname{abs}(a)$)
б) в массиве попарных сумм элементов каждой строки имеется $n$ нулей

 Профиль  
                  
 
 Re: Вопрос по системе ограничений
Сообщение01.02.2016, 21:46 


09/06/06
367
alcoholist в сообщении #1095961 писал(а):
ГАЗ-67 в сообщении #1095950 писал(а):
Попарные произведения не подходят.

тогда никак
либо "замаскировать":
а) все элементы неотрицательны ($a=\operatorname{abs}(a)$)
б) в массиве попарных сумм элементов каждой строки имеется $n$ нулей

Хм...Попробую.

 Профиль  
                  
 
 Re: Вопрос по системе ограничений
Сообщение01.02.2016, 22:40 
Заслуженный участник
Аватара пользователя


11/03/08
9496
Москва
Условие целочисленности через линейные равенства или неравенства не выражается.

 Профиль  
                  
 
 Re: Вопрос по системе ограничений
Сообщение01.02.2016, 22:50 
Заслуженный участник
Аватара пользователя


22/01/11
2641
СПб
ГАЗ-67
Описка у меня: $n-1$ попарных сумм НЕ равны нулю, остальные попарные суммы -- нули

 Профиль  
                  
 
 Re: Вопрос по системе ограничений
Сообщение02.02.2016, 00:32 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Если Вам нужно проверять, является ли матрица такой, какую Вам хочется иметь, нужно проверять равенство каждого элемента нулю, равенство каждого элемента единице (если он не равен нулю), и так или иначе проверять количество единиц в строках и столбцах. Хотя бы суммированием по строкам и столбцам. Все равенства линейные.

 Профиль  
                  
 
 Re: Вопрос по системе ограничений
Сообщение02.02.2016, 00:36 
Заслуженный участник


25/02/11
1786
ГАЗ-67 в сообщении #1095892 писал(а):
У меня в большой задаче возникла небольшая подзадача. Имеется квадратная матрица состоящая из нулей и единиц. В каждом столбце и в каждой строке может быть только одна единица. Я задал ограничения:суммы по строкам и столбцам равны 1.

Предпоследнее условие не то же самое, что и последнее. Допускается ли строка из нулей?

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

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



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

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


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

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