Геометрическое нахождение максимума

[nbyte]

Здравствуйте.
Помогите пожалуйста решить задачу

Цитата:

Решите задачу при помощи геометрической интерпретации.

$$\begin{array}{l} z = - {x_1} + {x_2} - 3 \to \max \\ 4*{x_1} - {x_2} \ge 6 \\ 9*{x_1} + 8*{x_2} \le 157 \\ - 3*{x_1} + 11*{x_2} \ge 16 \\ {x_1} \ge 0 \\ \end{array}$$

Пробую решить

Цитата:

Нахожу по две точки для построения линий

Беру
$4*{x_1} - {x_2} \ge 6$
нахожу две точки
$(1.5;0)(0; - 6)$

Беру
$9*{x_1} + 8*{x_2} \le 157$
нахожу две точки
$\left( {\frac{{157}}{9};0} \right)\left( {0;\frac{{157}}{8}} \right)$

Беру
$- 3*{x_1} + 11*{x_2} \ge 16$
нахожу две точки
$\left( { - \frac{{16}}{3};0} \right)\left( {0;\frac{{16}}{{11}}} \right)$

Черчу график, получаю

серым помечаю поле в котором я ищу $max$
А вот что дальше делать, я не понял.


У нас был похожий пример на доске.
И вот дальше решался используя понимае вот такое какое-то :) (извините, но не знаю как правильно выразится)

$$\begin{gathered} z = f({x_1};{x_2}) \hfill \\ \left\{ {({x_1};{x_2})|f({x_1};{x_2}) = C} \right\}\,\,,C \in \mathbb{R} \hfill \\ \end{gathered} $$

дальше брались разные константы $C$ непонятно для меня откуда,
и подставлялись в формулу у которой мы ищем $max$, получая множества.
И дальше вообще я ничего не понял из концовки принципа решения.

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

[paha]

Смотрите, Вам нужно максимизировать разность $x_2-x_1$... Стройте прямую $x_2=x_1+C$ и смотрите при каком наибольшем $C$ (ведь $C=x_2-x_1$) она имеет общие точки с Вашим треугольником (правильность построения которого я не проверял)

[ewert]

paha в сообщении #349652 писал(а):

Вам нужно максимизировать разность

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

[nbyte]

ewert в сообщении #349653 писал(а):

Надо просто проверить значения в вершинах, смысл задания именно в этом.

А как проверить?

[ewert]

Молча. Тупо посчитать значения той линейной функции во всех вершинах -- и выбрать наилучшее.

[nbyte]

А тогда $C$ какое имеет отношение к решению?

[gris]

Надо построить прямую $-x_1+x_2=0$, а потом двигать её параллельно самой себе в направлении градиента, если надо находить максимум, и против градиента, если надо находить минимум. Крайние положения прямой, при которых она имеет пересечения с многоугольником, соответствуют маскимуму и минимуму целевой функции. В этом и есть смысл графического решения.

[Alexey1]

После того, как Вы построили допустимую область (треугольник) находите градиент целевой функции (направление роста функции), это будет вектор $\Big(\frac{\partial z}{\partial x_1};\frac{\partial z}{\partial x_2}\Big)=(-1;1)$. Затем, добавляете его на рисунок. После этого рассматриваете множества точек $(x_1;x_2)$, такие, что $z=-x_1+x_2-3=C$, где $C$ - некоторая константа. Все эти точки (для фиксированного $C$) будут прямыми перпендикулярными вектору градиенту - то есть, их можно просто рисовать на графике, не рассматривая конкретные значения $C$.
Визуально, можно вообразить, что прямая перпеникулярная вектору градиенту просто скользит по нему. Теперь двигайте эту прямую в направлении вектора градиента до тех пор, пока эта прямая не будет касаться (заметьте не пересекать, а именно касаться) допустимого множества, так, что дальнейшее смещение приведёт к тому, что прямая не будет ни пересекать, ни касаться допустимого множества. Эта точка касания (может и не одна) и будет решением задачи.
Однако, если не решать графически, то решение можно найти вычисляя значения функции в каждой вершине треугольника. Решением будет та вершина, где значение целевой функции максимально.

[ewert]

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

-- Сб сен 04, 2010 20:49:44 --

nbyte в сообщении #349649 писал(а):

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

А-а, кажется, понял проблему. Оптимизация -- это попросту нахождение минимума некоей функции (ну или максимума, с точностью до знака в постановке вопроса). Вас как информатиков -- вероятно, дрессировали на дискретную оптимизацию; ну а тут она "аналоговая", вот и вся разница. (Аналоговая, кстати, гораздо проще дискретной.)

[nbyte]

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

просто скользит по нему

А это нарисовать как я понимаю крайне сложно (или вообще полностью не возможно)?

-- Сб сен 04, 2010 21:17:14 --

ewert в сообщении #349665 писал(а):

А-а, кажется, понял проблему.

Я только что в Википедию зашел и усмехнулся :)
Вы правы

Цитата:

# Оптимизация (математика) — нахождение оптимума (максимума или минимума) функции при выполнении некоторых ограничений
# Оптимизация (информатика) — процесс модификации системы для улучшения её эффективности.

-- Сб сен 04, 2010 21:19:15 --

nbyte в сообщении #349674 писал(а):

Alexey1 в сообщении #349664 писал(а):
просто скользит по нему

А это нарисовать как я понимаю крайне сложно (или вообще полностью не возможно)?

Если это так, то я как-бы отхожу от условия? (и могу получить "штрафные")

-- Сб сен 04, 2010 21:24:59 --

ewert в сообщении #349665 писал(а):

дрессировали на дискретную оптимизацию

Ну я можно-ли назвать дискретной оптимизацией.
Я только имел в представлении, то что вот написано тут
[url]http://ru.wikipedia.org/wiki/%D0%9E%D0%BF%D1%82%D0%B8%D0%BC%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%28%D0%B8%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0%29
[/url]
тоесть

Цитата:

Понятие «оптимизация» обычно подразумевает, что система сохраняет ту же самую функциональность. Однако, значительное улучшение производительности часто может быть достигнуто и с помощью удаления избыточной функциональности.

[ewert]

nbyte в сообщении #349674 писал(а):

(и могу получить "штрафные")

нет, кстати, не можете, это совсем другая тема, из которой Вас немедленно выкинут (без осознания)

[nbyte]

ewert
В том смысле, что это из темы. Что точка не имеет размера и объёма. Следовательно я могу двигать прямую до бесконечности?
(или я не так понял?)

[Alexey1]

nbyte в сообщении #349674 писал(а):

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

просто скользит по нему

А это нарисовать как я понимаю крайне сложно (или вообще полностью не возможно)?

Ну зачем Вам все то прямые рисовать. Нарисуйте ту, которая касается, то есть поседнюю, соответствующую максимальному значению $C$. А точка касания (или множество точек) и будет решением задачи.
Кстати, посмотрите как здесь решена задача.

[nbyte]

Мммммм
Теперь дошло!

До это времени, в голове так и летала мысль - "а зачем это нужно рисовать".

Тогда в моём случае это будет одна точка $(5, 14)$ и $z=6$
Вроде теперь всё ясно, Спасибо Вам!

Для меня только одно странное остаётся. Как это связано с информатикой.
Надеюсь по мере изучения и углубления в предмет истина пользы станет ясной :)

[ewert]

nbyte в сообщении #349688 писал(а):

Как это связано с информатикой.

Формально -- никак не связано. Но вот понимать, что информатика есть не более чем служанка для математики -- небесполезно.