2014 dxdy logo

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

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




 
 Целочисленное программирование: отсутствует оптимальное реш
Сообщение22.04.2007, 07:55 
Помогите, пожалуйста, решить задачу:
Доказать, что задача целочисленного программирования
max \left\{x_1-\sqrt{2} x_2|x_1 \geqslant {1}, x_1\leqslant \sqrt{2} x_2 , (x_1,x_2)\in Z_{+}^{2}\right\}
не имеет оптимального решения.

Ясно, что x_1-\sqrt{2} x_2\leqslant {0}. При этом равно нулю это выражение быть не может, из-за последнего ограничения. Я пыталась подставлять -1, -2 и т.д.

 
 
 
 
Сообщение22.04.2007, 09:41 
Аватара пользователя
По сути требуется показать, что для любых допустимых $(x_1,x_2)$ можно найти такие допустимые $(y_1,y_2)$, что $x_1-\sqrt2\,x_2<y_1-\sqrt2\,y_2<0$. Это можно делать разными способами. Например, можно взять $y_1=ax_1+bx_2$, $y_2=cx_1+dx_2$ с подходящими постоянными $a,b,c,d\in\mathbb{N}$ (попробуйте подобрать их самостоятельно).

 
 
 
 А как насчет пары (2,2)?
Сообщение22.04.2007, 09:49 
Если я чего-то не недопонял, то пара (2,2) как будто является решением?

 
 
 
 
Сообщение22.04.2007, 10:18 
Аватара пользователя
Vassil писал(а):
Если я чего-то не недопонял, то пара (2,2) как будто является решением?

Решением чего?

 
 
 
 
Сообщение22.04.2007, 22:23 
А будет ли доказательством следующее:
для каждой допустимой пары (x_1,x_2) найдется допустимая пара (y_1,y_2), где y_1=x_1+z_1, y_2=x_2+z_2, такая что x_1-\sqrt{2} x_2 <  y_1-\sqrt{2} y_2 <0.
Это справедливо, так как всегда найдутся целые z_1, z_2 такие, что 0<z_1-\sqrt{2} z_2 <\sqrt{2} x_2 -x_1.

 
 
 
 
Сообщение22.04.2007, 23:00 
Аватара пользователя
Да, это будет как раз тем доказательством, о котором Вам писал RIP, если Вы ещё докажете, что условия
OlgaM писал(а):
0<z_1-\sqrt{2} z_2 <\sqrt{2} x_2 -x_1
обеспечивают допустимость новой пары (в чем я несколько сомневаюсь :wink: )

 
 
 
 
Сообщение22.04.2007, 23:38 
Будем считать известным, что уравнене Пелля $x_1^2-2x_2^2=-1$ имеет бесконечное множество решений в натуральных числах. Исходное утверждение с очевидностью следует из этого факта и из тождества $x_1-\sqrt{2}x_2=-\frac{1}{x_1+\sqrt{2}x_2}$.

 
 
 
 
Сообщение23.04.2007, 06:16 
Аватара пользователя
OlgaM, просветите, пожалуйста. Чем таким утверждение
OlgaM писал(а):
всегда найдутся целые z_1, z_2 такие, что 0<z_1-\sqrt{2} z_2 <\sqrt{2} x_2 -x_1.

отличается от
OlgaM писал(а):
для каждой допустимой пары (x_1,x_2) найдется допустимая пара (y_1,y_2),... такая что x_1-\sqrt{2} x_2 <  y_1-\sqrt{2} y_2 <0.

, что первое Вы считаете очевидным, а второе $-$ нет?

 
 
 
 Мне кажется, что задача имеет решение ...
Сообщение23.04.2007, 11:14 
Конечно, вчера я ошибся в расчетах, прошу простить меня. Спасибо модератору.

И все таки, мне кажется, что эта задача целочисленного программирования имеет решение:

$$ x_1=24, \;x_2=17 $$

Возможно я чего то не так понял?

 
 
 
 
Сообщение23.04.2007, 15:20 
Аватара пользователя
Vassil писал(а):
И все таки, мне кажется, что эта задача целочисленного программирования имеет решение:

$$ x_1=24, \;x_2=17 $$

Возможно я чего то не так понял?

$24-17\sqrt2=-0.04163...<82-58\sqrt2=-0.0243866...<0$
Возможно, я чего-то не так понял?

 
 
 
 Заблудился
Сообщение23.04.2007, 16:36 
Наконец-то внял ...
Спасибо.

 
 
 [ Сообщений: 11 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group