Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Den-Dzen
0 / 0 / 0
Регистрация: 03.01.2014
Сообщений: 13
#1

Как решаются системы неравенств и минимизации\максимизации? - C++

10.09.2014, 20:55. Просмотров 719. Ответов 16
Метки нет (Все метки)

требуется решить задачу, аналогичную "задаче о диете", но никак не соображу как интерпретировать систему неравенств и минимизацию. Можно представить что наши данные это матрица, имеющая произвольное число строк и столбцов, и нас интересуют коэффициенты к строкам, но как это дальше превратить в код?
Яндекс подсказал что бывают разные методы решения матриц: например метод Гаусса или Ньютона, но их описание опять же состоит из уравнений, и как перевести это в код я не догоняю..
Наверняка есть какой-то готовый алгоритм программирования подобных задач? Имею ввиду описание логики последовательности действий (циклы, массивы т.п.).
И как выбрать способ решения? Ведь параметры матрицы (число строк и столбцов) заранее не известны.
Спасибо.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.09.2014, 20:55
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Как решаются системы неравенств и минимизации\максимизации? (C++):

Для произвольных значений a, b вычислить решение системы неравенств - C++
Для произвольных значений a, b вычислить решение системы неравенств (с применением условных операторов) \begin{cases} & ax-b\geq 0 ...

Составить программу для вычисления решений системы неравенств - C++
Для произвольных значений a,b вычислить решение системы неравенств. a/x>=b b*x<=0

Для произвольных значений a, b вычислить решение системы неравенств (с применением условных операторов) - C++
Для произвольных значений a, b вычислить решение системы неравенств (с применением условных операторов) Существует тема на форуме, но...

Не подскажете как решаются задачи такого плана на C++? - C++
Если можно узнать формулу, и правильность записаного решения. Буду очень благодарен:)

Подскажите логику минимизации карт Карно - C++
нужна логика карт Карно например для 4-х переменных, просто логика минимизации, не желательно программа, а то я запутался совсем!

Распределить заготовки между станками для минимизации времени их обработки - C++
Подскажите как реализовать задачу полным перебором. n заготовок необходимо обработать на двух одинаковых станках. Известно время Cj,...

16
FiLF
53 / 53 / 15
Регистрация: 05.09.2013
Сообщений: 1,385
10.09.2014, 21:18 #2
Можно попробовать решить методом полного перебора, если стоит задача целочисленного программирования.
А вообще: программируете стандартный алгоритм решения таких задач (как вы бы решали эту задачу без использования ЭВМ). Какой-нибудь симплекс-метод.
0
Den-Dzen
0 / 0 / 0
Регистрация: 03.01.2014
Сообщений: 13
10.09.2014, 21:28  [ТС] #3
Конкретно мой пример включает систему двойных неравенств:
где:
p1,p2,p3... - компоненты которые мы смешиваем
A,B,C,D - коэффициенты количества компонентов
27>A*p1[1]+B*p2[1]+C*p[1]+D*p4[1]>33
67>A*p1[2]+B*p2[2]+C*p[2]+D*p4[2]>73
47>A*p1[3]+B*p2[3]+C*p[3]+D*p4[3]>53

Найти надо соответственно A, B, C, D, при том, что компонентов (p1[],p2[]...), и элементов в них (p[i]), т.е. числа строк и следовательно неравенств, может быть скольугодно много, или наоборот мало.
Т.е. Возможна как ситуация с 10 неизвестными коэффициентами при 3 искомых элементах (т.е. 3х неравенствах), так и обратная: когда 3 неизвестных и 10 искомых элементов (т.е. 10 неравенств).
Необходимо получить все удовлетворящие условиям решения, и затем выбрать из них наиболее близкое к Эталону (в данном случае 30, 70, 50).
Вот как выбрать я хорошо представляю, а как найти все возможные решения для неравенств, я не соображаю...

Добавлено через 2 минуты
FiLF, спасибо, в институте помню решали симплексом и гауссом, но это был такой ад, что вспоминать не тянет)
Надеялся что можно будет узнать готовый код-шаблон для таких случаев, и подогнать под себя.
0
FiLF
53 / 53 / 15
Регистрация: 05.09.2013
Сообщений: 1,385
10.09.2014, 21:35 #4
Ничего не понял, предоставьте нормальную математическую модель (целевая функция, ограничения, переменные, их диапазоны). Не вижу никакой проблемы в том, что неравенств может быть любое количество. Алгоритмам (общим) нет до этого никакого дела. Попробуйте поискать реализацию на C++ для симплекс-метода, уверен - найдёте что-нибудь.
0
S_el
2112 / 1632 / 308
Регистрация: 15.12.2013
Сообщений: 6,572
10.09.2014, 21:40 #5
Цитата Сообщение от Den-Dzen Посмотреть сообщение
FiLF, спасибо, в институте помню решали симплексом и гауссом, но это был такой ад, что вспоминать не тянет)
Это далеко не ад.
Поищите учебники по линейному программированию,если то,что там написано для вашей задачи подходит,берите симплекс-метод и подставляйте свои значения.
Реализации я думаю найти(или сделать) не так сложно для любого распространенного ЯП.
Или можно решить онлайн-решателем или в математическом пакете.
0
FiLF
53 / 53 / 15
Регистрация: 05.09.2013
Сообщений: 1,385
10.09.2014, 21:42 #6
Цитата Сообщение от S_el Посмотреть сообщение
(или сделать)
Я бы не сказал так.
0
S_el
2112 / 1632 / 308
Регистрация: 15.12.2013
Сообщений: 6,572
10.09.2014, 21:46 #7
Цитата Сообщение от FiLF Посмотреть сообщение
Я бы не сказал так.
Я тоже думаю,что найти готовое проще,чем сделать,тут не с чем спорить.
Но симплекс метод далеко не сложный для программирования численный метод.
0
Den-Dzen
0 / 0 / 0
Регистрация: 03.01.2014
Сообщений: 13
10.09.2014, 23:32  [ТС] #8
S_el, Насчет программирования не спорю, может и не сложный, если в нем разобраться. Я помню что ад был считать задачи этим способом на листочке, умножая в столбик...
0
S_el
2112 / 1632 / 308
Регистрация: 15.12.2013
Сообщений: 6,572
10.09.2014, 23:56 #9

Не по теме:

Цитата Сообщение от Den-Dzen Посмотреть сообщение
Я помню что ад был считать задачи этим способом на листочке, умножая в столбик...
Обычные преобразования,что бы ты сказал при решении задачи целочисленного программирования модифицированным симплекс-методом

Цитата Сообщение от Den-Dzen Посмотреть сообщение
Насчет программирования не спорю, может и не сложный, если в нем разобраться.
относительно не сложный.



Den-Dzen, обратитесь в раздел по методам оптимизации,там вам подскажут более квалифицированные в данной области пользователи.

Цитата Сообщение от Den-Dzen Посмотреть сообщение
Т.е. Возможна как ситуация с 10 неизвестными коэффициентами при 3 искомых элементах (т.е. 3х неравенствах), так и обратная: когда 3 неизвестных и 10 искомых элементов (т.е. 10 неравенств).
Я не уверен,что возможно решить настолько недоопределенную систему.
Насколько я понял вам необходимо минимизировать затраты и есть ограничения на количество использования этих компонент.Исходя из условия можно говорить о задаче линейного программирования.Однако будет лучше всего,если вы предоставите полное ТЗ.

Цитата Сообщение от FiLF Посмотреть сообщение
Ничего не понял, предоставьте нормальную математическую модель (целевая функция, ограничения, переменные, их диапазоны).
Как раз построение адекватной математической модели зачастую и является самой большой сложностью.Потом провести анализ,ну а вбить цифры и получить ответ дело нехитрое.
0
Den-Dzen
0 / 0 / 0
Регистрация: 03.01.2014
Сообщений: 13
11.09.2014, 01:58  [ТС] #10
Спасибо, мне нужно написать программу калькулятор на java, чтобы расчитывать хим.реактивы.
Нужно получить раствор с заданным соотношением элементов, чтобы его получить мы смешиваем компоненты с разными соотношениями этих элементов. Нужно найти оптимальное соотношение компонентов для получения раствора близкого к идеальному.
Подразумевается что число элементов т.е. условий может быть произвольным, по выбору пользователя, также как и число компонентов (неизвестных).

например нам нужно получить раствор с содержанием 3х элементов 30 70 50
У нас есть 5 компонентов, с содержанием элементов:
10 10 10
20 60 30
70 10 40
50 20 60
40 50 70

Нужно определить в каких пропорциях их смешать чтобы получить содержание элементов максимально близкое к эталонному.

Вроде такие задачи как раз решаются симплексом... я честно потратил 2 часа на поиски человеческого объяснения алгоритма этого метода, если не в программировании, так хоть на цифрах... но без толку, с ходу не въедешь, я уже все забыл. Если есть у вас ссылка на вменяемое объяснение очень был бы рад!

Был у нас препод, он был единственный в моей жизни пример человека который понятно объяснял как решить задачки по его предмету: "берете вот это число возле X и умножате на число возле Y, если результат больше нуля, то умножаете на результат вычислений вот этого куска" и т.д. в таком духе, т.е. без всяких там "вырожденная\невырожденная" "ранг матрицы" и т.п. это все считалось, но понятным образом: по шагам, вот это число умножить на вот это и т.п. Вот может есть в таком стиле объяснение у кого?)
0
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
11.09.2014, 06:24 #11
Цитата Сообщение от Den-Dzen Посмотреть сообщение
не соображу как интерпретировать систему неравенств и минимизацию.
Ну, давайте разберем вашу задачу на примере с двумя растворами. Тогда решение двойного неравенства с двумя неизвестными геометрически будет являться точками плоскости, расположенными между двумя параллельными прямыми, внутри этой полосы будет лежать оптимальная прямая, параллельная граничным.
Если компонента одна, то имеем на плоскости одну полосу с оптимальной прямой внутри. Решений – бесконечное множество, т.е. любая точка оптимальной прямой.
Если компоненты две, т.е. таких полос две, то опять полосы нас не интересуют, решение – это точка пересечения двух оптимальных прямых. Т.е. имеем систему двух линейных уравнений с двумя неизвестными, которую решаем методом Гаусса, например.
Если компонент больше двух, например три, то возможны два случая: все три полосы имеют общие точки на плоскости, или нет. Если нет, то решения не существует. Если имеют, то нужно из этих точек выбрать наиболее близкую к трем оптимальным прямым. Критерий близости у вас не сформулирован. Чтобы применить симплекс-метод, нужно, чтобы этот критерий был линейной функцией. Можно расстояние взять. Тогда задача сводится к следующей: из всех точек плоскости, принадлежащих пересечению трех полос, найти точку, сумма расстояний от которой до трех оптимальных прямых минимальна.
Итак, если компонент не больше, чем растворов, то находим точное решение из системы линейных уравнений. Если компонент меньше, чем растворов, то решений бесконечное множество, а если столько же, то одно.
Если компонент больше, чем растворов, то решения может и не быть. Если оно существует, то находим его симплекс-методом, минимизируя сумму расстояний до оптимальных гиперплоскостей.

Добавлено через 1 час 43 минуты
Заметил, что я в терминологии с автором разошелся. Он называет растворы компонентами, а вещества - элементами, а я растворы растворами, а вещества - компонентами.
0
Den-Dzen
0 / 0 / 0
Регистрация: 03.01.2014
Сообщений: 13
11.09.2014, 12:09  [ТС] #12
Mr.X, Спасибо!
Т.е. Правильно я понял, что для построения универсального алгоритма, мне нужно в коде реализовать несколько методов, например Симплекс и Гаусса, и решать тем или иным, в зависимости от выбранного пользователем числа "растворов" и "компонентов" по которым идет сравнение.
0
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
11.09.2014, 13:12 #13
Цитата Сообщение от Den-Dzen Посмотреть сообщение
Правильно я понял, что для построения универсального алгоритма, мне нужно в коде реализовать несколько методов, например Симплекс и Гаусса, и решать тем или иным, в зависимости от выбранного пользователем числа "растворов" и "компонентов" по которым идет сравнение.
Ну да.
0
Den-Dzen
0 / 0 / 0
Регистрация: 03.01.2014
Сообщений: 13
11.09.2014, 13:53  [ТС] #14
Так то все так, и идею и пример с Симплексом и областью решений на прямых я понимаю, но вот смотрю видео по этому симплексу и не могу вкурить откуда там появляются эти цифры в таблице!? + эта терминология "базисная переменная", "свободная", "вырожденная\невырожденная"... чтобы въехать придется разбираться еще и с этими определениями, уже мозг пухнет. а я то так надеялся что курс вышки мне никогда не понадобится в жизни.. попробую еще поискать внятное объяснение что откуда и как берется.
0
Mr.X
Эксперт С++
3051 / 1696 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
11.09.2014, 14:32 #15
Цитата Сообщение от Den-Dzen Посмотреть сообщение
видео по этому симплексу и не могу вкурить откуда там появляются эти цифры в таблице!?
Да там довольно простой алгоритм преобразования матрицы, который достаточно просто запомнить, понимать не обязательно, ну как употребление мягкого знака в "грузинских" словах "сол" и "фасол" и "вилька" и "тарьелька".
А вам обязательно самому симплекс-метод надо реализовывать? Так-то полно библиотек готовых.

Добавлено через 16 минут
Вообще-то я наверно погорячился насчет симплекс-метода. Пожалуй, он здесь не подойдет.
0
11.09.2014, 14:32
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.09.2014, 14:32
Привет! Вот еще темы с ответами:

Условный оператор. Система неравенств - C++
Здравствуйте! Помогите, пожалуйста, разобраться с задачкой. Знаю, что похожая тема уже была, но что-то все равно не получается. ...

Решить систему линейных неравенств - C++
Нужно написать программу, решающую систему неравенств. Программа должна правильно выполняться при любых значениях начальных...

Отсутствуют кнопки закрытия, максимизации и минимизации окна - C++ WinAPI
Переписал код из книжки, вот он #include <windows.h> LRESULT CALLBACK HelloWorldWndProc(HWND,UINT,UINT,LONG); int WINAPI...

Кто нибудь, забыл как решаются эти системы - Математика
1). { 2x^2-y^2-xy-3y-2=0 { x^2-y^2=1 2). { 2x^2+2xy+y^2-6x-2y+5=0 { 3x^2-xy-y^2+2x+7y-10=0


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru