Целочисленное программирование: отсутствует оптимальное реш

[OlgaM]

Помогите, пожалуйста, решить задачу:
Доказать, что задача целочисленного программирования
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 и т.д.

[RIP]

По сути требуется показать, что для любых допустимых $(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}$ (попробуйте подобрать их самостоятельно).

[Vassil]

Если я чего-то не недопонял, то пара (2,2) как будто является решением?

[RIP]

Vassil писал(а):

Если я чего-то не недопонял, то пара (2,2) как будто является решением?

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

[OlgaM]

А будет ли доказательством следующее:
для каждой допустимой пары (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.

[Brukvalub]

Да, это будет как раз тем доказательством, о котором Вам писал RIP, если Вы ещё докажете, что условия

OlgaM писал(а):

0<z_1-\sqrt{2} z_2 <\sqrt{2} x_2 -x_1

обеспечивают допустимость новой пары (в чем я несколько сомневаюсь )

[neo66]

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

[RIP]

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.

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

[Vassil]

Конечно, вчера я ошибся в расчетах, прошу простить меня. Спасибо модератору.

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

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

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

[RIP]

Vassil писал(а):

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

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

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

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

[Vassil]

Наконец-то внял ...
Спасибо.