Глобальный экстремум (задача с параметром)

[ttrun]

Имеется следующая задача:
При каких значениях параметра k точка (1,5) является решением задачи

$$kx_1+(2-k)x_2\to extr$$ $$ \left\{ \begin{array}{rcl} 5x_1-x_2 & \leq & 7 \\ 2x_1+3x_2 & \leq & 3 \\ x_1+x_2 &\leq& 6\\ \end{array} \right. $$

У меня получилось, что k \in [1, \frac{5}{2}). Я пользовался теоремой Куна-Таккера. Это задача на глобальный экстремум, как показать, что при этих k точка будет глобальным экстремумом?

[Alexey1]

Это же задача линейного программирования. Если для этих значений $k$ симплекс-метод даёт оптимальное решение, то это глобалный минимум (максимум).

[ttrun]

да, но в данном случае у меня нет условий x_i\geq 0, i=1,2
Еще добавлю, что имеем задачу на максимум. Хотя я туплю) у указанной точки это как раз выполняется

[Alexey1]

Приведите её к виду, где есть ограничения $x_i \geq 0$. То есть если $x_i$ свободная переменная, то заменой переменных $x_i=x_i^+-x_i^-$, Вы приводите задачу к виду где $x_i^+\geq 0, x_i^- \geq 0$.
Что касается максимума, то приведите к минимуму умножением целевой функции на $-1$. Тут всё равно всё линейно.

[мат-ламер]

Условие положительности иксов тут не нужно. Это стандартная форма задачи ЛП. Если бы была каноническая форма (т.е. вместо неравенств - равенства), то тогда другое дело.

[ttrun]

Alexey1 в сообщении #316367 писал(а):

Приведите её к виду, где есть ограничения $x_i \geq 0$. То есть если $x_i$ свободная переменная, то заменой переменных $x_i=x_i^+-x_i^-$, Вы приводите задачу к виду где $x_i^+\geq 0, x_i^- \geq 0$.

Alexey1, возможна ситуация, когда $x_i \leq 0$. Это разве нормально?

А все-таки, разве недостаточно неотрицательности компонент точки (1,5)? мне же надо только эту точку проверить

[Alexey1]

Нормально для чего? Опять же, через замену переменных задачу можно привести к виду где все неизвестные неотрицательные (если это необходимо для решения задачи).
Вы пробовали решить эту задачу графическим способом? У Вас указанная точка не удовлетворяет второму ограничению.

[ttrun]

ttrun в сообщении #316340 писал(а):

При каких значениях параметра k точка (1,5) является решением задачи

$$kx_1+(2-k)x_2\to extr$$ $$ \left\{ \begin{array}{rcl} 5x_1-x_2 & \leq & 0 \\ 2x_1+3x_2 & \leq & 20 \\ x_1+x_2 &\leq& 6\\ \end{array} \right. $$

Это я неправильно написал условия задачи. Да, геометрически решать пытался, причем мне кажется, что точка при всех найденных мною k будет глобальным максимумом. Надо строгое доказательство. Какой заменой можно придти к виду, где все неизвестные неотрицательны?

Alexey1 в сообщении #316367 писал(а):

Приведите её к виду, где есть ограничения $x_i \geq 0$. То есть если $x_i$ свободная переменная, то заменой переменных $x_i=x_i^+-x_i^-$, Вы приводите задачу к виду где $x_i^+\geq 0, x_i^- \geq 0$.

Этой заменой? Если да, то не совсем представляю, как решать дальше

[Alexey1]

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

[ttrun]

спасибо, буду решать

[Yu_K]

Сначала просто желательно повнимательней глянуть на систему ограничений и точку (1,5) - удовлетворяет ли она системе ограничений. Либо Вы напутали, либо тот кто составлял задачу. И желательно для составителя, чтоб (1,5) была угловой точкой допустимого множества и в принципе , не важно есть ограничения неотрицательности или нет.

[ttrun]

Yu_K да, я ошибся в первом посте в условиях задачи, но позже поправился. А точка действительно является угловой.

[Yu_K]

Извиняюсь - не посмотрел, что там внутри. Рекомендую графический метод - нарисуйте допустимую область и вектор градиента целевой функции (он зависит от $k$) или линии уровня целевой функции.

[ttrun]

На данный момент я решил задачу с помощью симплекс-метода. Мне предлагали решить ее с помощью линий уровня, но я это себе не совсем представляю. Картинку я пытался строить, но ничего хорошего сказать по ней не могу.
Там получается такая ситуация, что при некотором значении целевой функции (которое яв-ся минимумом или максимумом) линия уровня имеет касательную точку с множеством, задаваемом ограничениями, в точке (1,5). Но как доказать, что это глобальный максимум или минимум по картинке?