Здравствуйте, NetRaider, Вы писали:
NR>Что-то у меня из головы вылетело как находится максимум ф-ии при условиях.
Для двух X, можно решить графически — в Инете, в качестве примера, нашел вот это http://www.ecourses.ru:9000/courses/9/r2/r_2_6.html , а если надо вычислительным способом решать для N X, то смотри Симплекс-метод
ZOR>Для двух X, можно решить графически — в Инете, в качестве примера, нашел вот это http://www.ecourses.ru:9000/courses/9/r2/r_2_6.html , а если надо вычислительным способом решать для N X, то смотри Симплекс-метод
Это симплекс-методом ??? как из пушки по воробьям.
По моему там все проще должно быть... уравнение и условия простые до безобразия.
Здравствуйте, NetRaider, Вы писали:
NR>Это симплекс-методом ??? как из пушки по воробьям. NR>По моему там все проще должно быть... уравнение и условия простые до безобразия.
Ну, вообщем-то, Симплекс-метод сложным и не считается. И предложенная задача — задача линейной-оптимизации с линейными-ограничениями, а это как раз то то про что этот метод. Насколько я знаю, как исключение рассматривается случай только для 2-х X, так как его можно просто нарисовать. Я полагаю, что попытка решить эту задачу "на пальцах", будет по сути неявным применением Симплекс-метода, только не упоминая его названия
Здравствуйте, ZORK, Вы писали:
ZOR> Ну, вообщем-то, Симплекс-метод сложным и не считается. И предложенная задача — задача линейной-оптимизации с линейными-ограничениями, а это как раз то то про что этот метод. Насколько я знаю, как исключение рассматривается случай только для 2-х X, так как его можно просто нарисовать. Я полагаю, что попытка решить эту задачу "на пальцах", будет по сути неявным применением Симплекс-метода, только не упоминая его названия
Мдя... Первоначальная задача:
Есть функция 2x1+4x2-x1^1 -2x2^2 и некоторые условия.
Необходимо найти максимум. Можно решить используя Симплекс-метод.
Но надо решить используя метод Франка-Вулфа.
Пре решении этим методом в каждой итерации нужно находить максимумы для функций подобных функции из первого поста.
Вопрос: Какой наиболее простой способ их решения ? (кроме Симплекс-метода)
NR>Мдя... Первоначальная задача:
NR>Есть функция 2x1+4x2-x1^1 -2x2^2 и некоторые условия. NR>Необходимо найти максимум. Можно решить используя Симплекс-метод.
Функция содержит степени, так что Симплекс-методом ее решить нельзя.
NR>Но надо решить используя метод Франка-Вулфа. NR>Пре решении этим методом в каждой итерации нужно находить максимумы для функций подобных функции из первого поста.
NR>Вопрос: Какой наиболее простой способ их решения ? (кроме Симплекс-метода)
Не знаю чем объяснить такую нелюбовь к Симплекс-методу, который собственно для решения таких задач и предназначен
Ну да ладно — в данном случае система ограничений очень проста, так что построить многогранник допустимых решений — как 2 пальца об асфальт. После этого посчитай значения в каждой вершине, и выбири максимальное.
Конечно же это тот же Симплекс-метод, только в другой руке...
Здравствуйте, Bell, Вы писали:
B>Здравствуйте, NetRaider, Вы писали:
B> NR>>Мдя... Первоначальная задача:
NR>>Есть функция 2x1+4x2-x1^1 -2x2^2 и некоторые условия. NR>>Необходимо найти максимум. Можно решить используя Симплекс-метод.
...
NR>>Вопрос: Какой наиболее простой способ их решения ? (кроме Симплекс-метода) B>Не знаю чем объяснить такую нелюбовь к Симплекс-методу, который собственно для решения таких задач и предназначен B>Ну да ладно — в данном случае система ограничений очень проста, так что построить многогранник допустимых решений — как 2 пальца об асфальт. После этого посчитай значения в каждой вершине, и выбири максимальное. B>Конечно же это тот же Симплекс-метод, только в другой руке...
Только надо предварительно убедится в отсутствии локальных максимумов внутри, с учётом конкретной функции — достаточно только по х2.
Здравствуйте, mrhru, Вы писали:
MM> Только надо предварительно убедится в отсутствии локальных максимумов внутри, с учётом конкретной функции — достаточно только по х2.
Дак их там и не будет Оптимальное решение гарантированно находится в одной из вершинин (ну или на одной грани в случае альтернативного оптимума).
Здравствуйте, Bell, Вы писали:
B>Здравствуйте, mrhru, Вы писали:
MM>> Только надо предварительно убедится в отсутствии локальных максимумов внутри, с учётом конкретной функции — достаточно только по х2.
B>Дак их там и не будет Оптимальное решение гарантированно находится в одной из вершинин (ну или на одной грани в случае альтернативного оптимума).
А почему? Функция, вроде, полином степени больше 1.
Здравствуйте, mrhru, Вы писали:
M>Здравствуйте, Bell, Вы писали:
B>Здравствуйте, mrhru, Вы писали:
MM>> Только надо предварительно убедится в отсутствии локальных максимумов внутри, с учётом конкретной функции — достаточно только по х2.
B>Дак их там и не будет Оптимальное решение гарантированно находится в одной из вершинин (ну или на одной грани в случае альтернативного оптимума).
M>А почему? Функция, вроде, полином степени больше 1.
Стоп. Мы говорим о разных вещах. Я имел ввиду линейную функцию из самого первого поста. Полином роявился позже
Ну а для полинома ты все верно сказал — находим экстремумы, проверяем их на максимум, проверяем удовлетворяет ли решение ограничениям, и если нет — проверяем вершины многогранника доп. решений.
По-моему такие задачи в школе решают... Правда я не знаю, как этот метод соотносится с методом Франка-Вулфа (я о нем сейчас первый раз услышал). Может в нем как-то обходится необходимость аналитических вычисдений, связанных с нахождением экстремумов?
Здравствуйте, Bell, Вы писали:
B>По-моему такие задачи в школе решают... Правда я не знаю, как этот метод соотносится с методом Франка-Вулфа (я о нем сейчас первый раз услышал). Может в нем как-то обходится необходимость аналитических вычисдений, связанных с нахождением экстремумов?
Если честно, то школьникам методы оптимизации не потянуть... Поэтому эта наука даётся в универах, более того — не на первом курсе.
Теперь о методе Франка-Вулфа. Метод применим, если задача является задачей квадратичного программирования, то есть целевая функция есть полином степени 2, причём в случае минимизации это должна быть положительно определённая функция, то есть грубо говоря "стакан", представляющий функцию, должен быть направлен вверх. Все ограничения должны быть линейными.
Если все эти условия выполнены, то задача становится частным случаем задачи выпуклого программирования, и мы можем гарантировать, что экстремум существует и является единственным. Также, оказывается применима одна теоремка (Куна-Таккера), с помощью которой выписываются вспомогательные условия и задача сводится к задаче линейного программирования, и можно уже применять Симплекс-метод (столь нелюбимый автором топика ).
Если нужны ссылки на книжки, то завтра. Интернет-ресурсы по этой теме мне неизвестны
Вообще-то, это задача линейного программирования.
Алгоритм можно найти в лекциях по ИО любого препода с ВМК МГУ (просто я там учился, поэтому и ссылаюсь, умаю, что в других ВУЗах на курсе Исследовании Опереции это тоже учат). например www.karganov.ru
If the milk turns out to be sour,
I ain't the kind of pussy to drink it
Симплекс-метод — это очень просто, есть куда более сложные алгоритмы, в которых "без бутылки" не разберёшься, а если реализовывать, то совсем жуть Вводим вспомогательные переменные, чтобы был базис и выписываем начальную симплексную таблицу:
0 | -2 -4
---+------
8 | 1 2
12 | 2 -1
Первая итерация: находим первое попавшееся отрицательное число в первой строке, пусть это будет -4, и в этом столбце выбираем ведущий элемент. Согласно алгоритму это 2 во второй строке в третьем столбце. Пересчитываем таблицу с этим ведущим элементом:
16 | 0 2
---+-----------
4 | 1/2 1/2
20 | 3/2 1/2
Всё, получилась конечная таблица, (таким образом нам хватило одной итерации), отсюда получаем x2=4, x1=0. Оптимальное значение целевой функции = 16.
Здравствуйте, LCR, Вы писали:
... LCR>Всё, получилась конечная таблица, (таким образом нам хватило одной итерации), отсюда получаем x2=4, x1=0. Оптимальное значение целевой функции = 16.
LCR>Усё.
Привет, чел!!! Я, как человек изуч. 1,5 года эту лабуду, могу тебе сказать, что в принципе эта задача решается симплексным методом, но т.к. параметров всего 2, то легче графически. Т. е. находишь вершины области(сист. ограничений и x[i]>0) и находишь в них значение функции(тот же симп. метод). Выбираешь max или min (зависит от того что надо получить). Это и будет решение.
P.S. Если в 2-х разных точках значение f одинаково, то решение- отрезок, соед. эти точки. И ничего мудрить не нужно!!!
как из пушки по воробьям. 
Ну, вообщем-то, Симплекс-метод сложным и не считается. И предложенная задача — задача линейной-оптимизации с линейными-ограничениями, а это как раз то то про что этот метод. Насколько я знаю, как исключение рассматривается случай только для 2-х X, так как его можно просто нарисовать. Я полагаю, что попытка решить эту задачу "на пальцах", будет по сути неявным применением Симплекс-метода, только не упоминая его названия 
Только надо предварительно убедится в отсутствии локальных максимумов внутри, с учётом конкретной функции — достаточно только по х2.
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
