2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Геометрическое нахождение максимума
Сообщение04.09.2010, 18:58 


21/03/09
406
Здравствуйте.
Помогите пожалуйста решить задачу
Цитата:
Решите задачу при помощи геометрической интерпретации.
$$\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$, получая множества.
И дальше вообще я ничего не понял из концовки принципа решения.


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

 Профиль  
                  
 
 Re: Геометрическое нахождение максимума
Сообщение04.09.2010, 19:03 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Геометрическое нахождение максимума
Сообщение04.09.2010, 19:06 
Заслуженный участник


11/05/08
32166
paha в сообщении #349652 писал(а):
Вам нужно максимизировать разность

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

 Профиль  
                  
 
 Re: Геометрическое нахождение максимума
Сообщение04.09.2010, 19:22 


21/03/09
406
ewert в сообщении #349653 писал(а):
Надо просто проверить значения в вершинах, смысл задания именно в этом.

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

 Профиль  
                  
 
 Re: Геометрическое нахождение максимума
Сообщение04.09.2010, 19:29 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Геометрическое нахождение максимума
Сообщение04.09.2010, 19:35 


21/03/09
406
А тогда $C$ какое имеет отношение к решению?

 Профиль  
                  
 
 Re: Геометрическое нахождение максимума
Сообщение04.09.2010, 19:40 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Геометрическое нахождение максимума
Сообщение04.09.2010, 19:42 
Заслуженный участник


08/09/07
841
После того, как Вы построили допустимую область (треугольник) находите градиент целевой функции (направление роста функции), это будет вектор $\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$.
Визуально, можно вообразить, что прямая перпеникулярная вектору градиенту просто скользит по нему. Теперь двигайте эту прямую в направлении вектора градиента до тех пор, пока эта прямая не будет касаться (заметьте не пересекать, а именно касаться) допустимого множества, так, что дальнейшее смещение приведёт к тому, что прямая не будет ни пересекать, ни касаться допустимого множества. Эта точка касания (может и не одна) и будет решением задачи.
Однако, если не решать графически, то решение можно найти вычисляя значения функции в каждой вершине треугольника. Решением будет та вершина, где значение целевой функции максимально.

 Профиль  
                  
 
 Re: Геометрическое нахождение максимума
Сообщение04.09.2010, 19:43 
Заслуженный участник


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

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

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

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

 Профиль  
                  
 
 Re: Геометрическое нахождение максимума
Сообщение04.09.2010, 20:09 


21/03/09
406
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]
тоесть
Цитата:
Понятие «оптимизация» обычно подразумевает, что система сохраняет ту же самую функциональность. Однако, значительное улучшение производительности часто может быть достигнуто и с помощью удаления избыточной функциональности.

 Профиль  
                  
 
 Re: Геометрическое нахождение максимума
Сообщение04.09.2010, 20:26 
Заслуженный участник


11/05/08
32166
nbyte в сообщении #349674 писал(а):
(и могу получить "штрафные")

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

 Профиль  
                  
 
 Re: Геометрическое нахождение максимума
Сообщение04.09.2010, 20:29 


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

 Профиль  
                  
 
 Re: Геометрическое нахождение максимума
Сообщение04.09.2010, 20:42 
Заслуженный участник


08/09/07
841
nbyte в сообщении #349674 писал(а):
Alexey1 в сообщении #349664 писал(а):
просто скользит по нему

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

 Профиль  
                  
 
 Re: Геометрическое нахождение максимума
Сообщение04.09.2010, 20:56 


21/03/09
406
Мммммм :D
Теперь дошло!

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

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

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

 Профиль  
                  
 
 Re: Геометрическое нахождение максимума
Сообщение04.09.2010, 21:14 
Заслуженный участник


11/05/08
32166
nbyte в сообщении #349688 писал(а):
Как это связано с информатикой.

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

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

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



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

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


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

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