Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Den-Dzen
0 / 0 / 0
Регистрация: 03.01.2014
Сообщений: 13
#1

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

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

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

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

Для произвольных значений a, b вычислить решение системы неравенств
Для произвольных значений a, b вычислить решение системы неравенств (с...

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

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

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

Ошибка при работе минимизации методом градиентного спуска
программа выполняет минимизацию методом градиентного спуска ошибка вылетает...

16
FiLF
54 / 54 / 37
Регистрация: 05.09.2013
Сообщений: 1,867
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
54 / 54 / 37
Регистрация: 05.09.2013
Сообщений: 1,867
10.09.2014, 21:35 #4
Ничего не понял, предоставьте нормальную математическую модель (целевая функция, ограничения, переменные, их диапазоны). Не вижу никакой проблемы в том, что неравенств может быть любое количество. Алгоритмам (общим) нет до этого никакого дела. Попробуйте поискать реализацию на C++ для симплекс-метода, уверен - найдёте что-нибудь.
0
S_el
2133 / 1661 / 354
Регистрация: 15.12.2013
Сообщений: 6,595
10.09.2014, 21:40 #5
Цитата Сообщение от Den-Dzen Посмотреть сообщение
FiLF, спасибо, в институте помню решали симплексом и гауссом, но это был такой ад, что вспоминать не тянет)
Это далеко не ад.
Поищите учебники по линейному программированию,если то,что там написано для вашей задачи подходит,берите симплекс-метод и подставляйте свои значения.
Реализации я думаю найти(или сделать) не так сложно для любого распространенного ЯП.
Или можно решить онлайн-решателем или в математическом пакете.
0
FiLF
54 / 54 / 37
Регистрация: 05.09.2013
Сообщений: 1,867
10.09.2014, 21:42 #6
Цитата Сообщение от S_el Посмотреть сообщение
(или сделать)
Я бы не сказал так.
0
S_el
2133 / 1661 / 354
Регистрация: 15.12.2013
Сообщений: 6,595
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
2133 / 1661 / 354
Регистрация: 15.12.2013
Сообщений: 6,595
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
Эксперт С++
3178 / 1705 / 435
Регистрация: 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
Эксперт С++
3178 / 1705 / 435
Регистрация: 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
Эксперт С++
3178 / 1705 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
11.09.2014, 14:32 #15
Цитата Сообщение от Den-Dzen Посмотреть сообщение
видео по этому симплексу и не могу вкурить откуда там появляются эти цифры в таблице!?
Да там довольно простой алгоритм преобразования матрицы, который достаточно просто запомнить, понимать не обязательно, ну как употребление мягкого знака в "грузинских" словах "сол" и "фасол" и "вилька" и "тарьелька".
А вам обязательно самому симплекс-метод надо реализовывать? Так-то полно библиотек готовых.

Добавлено через 16 минут
Вообще-то я наверно погорячился насчет симплекс-метода. Пожалуй, он здесь не подойдет.
0
Den-Dzen
0 / 0 / 0
Регистрация: 03.01.2014
Сообщений: 13
11.09.2014, 15:29  [ТС] #16
Mr.X, да может он и простой, я помню что потом решал эти задачки с матрицами на раз (на первом-втором курсе), но вот поначалу въехать в этот процесс было для меня вывихом мозга, и щас я похоже повторяю этот процесс...) ТОлько тогда я еще помнил что-то со школы, а сейчас я с трудом вспоминаю как в столбик делить..
Насчет того, что понимать не обязательно, то я и пытаюсь найти такое объяснение где не обязательно понимать, но что-то не нахожу))
Вот попытался разложить приведенную мной задачу в уравнениях:

Функция минимизирует квадрат разницы между суммой элементов полученного раствора с суммой элементов эталонного раствора:
min F= (150-(A30+B110+C120+D130+E160))2

ограничения соответственно такие:
A10+B20+C70+D50+E40>25
A10+B20+C70+D50+E40<35
A10+B60+C10+D20+E50>65
A10+B60+C10+D20+E50<75
A10+B30+C40+D60+E70>45
A10+B30+C40+D60+E70<55

A,B,C,D,E >=0


Я для ограничений взял значения эталона 30 70 50 и разбил с погрешностью.

Далее, я так понимаю нужно добавить "пустые" переменные, чтобы неравенства превратить в равенства:
A10+B20+C70+D50+E40 -X1=25
A10+B20+C70+D50+E40+X2=35
A10+B60+C10+D20+E50-X3=65
A10+B60+C10+D20+E50+X4=75
A10+B30+C40+D60+E70-X5=45
A10+B30+C40+D60+E70+X6<55


а вот дальнейнейшие операции меня пока что смущают)..

Найти библиотеку было бы замечательно, мне нужна библиотека для java, еще лучше для конкретно processing-а, но пока не нашел..
0
Mr.X
Эксперт С++
3178 / 1705 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
11.09.2014, 15:41 #17
Да я уже дописал в предыдущем сообщении, но вы не заметили, после более подробного обдумывания мне кажется, что симплекс-метод тут не подходит.
0
11.09.2014, 15:41
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.09.2014, 15:41
Привет! Вот еще темы с решениями:

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

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

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

Замена кнопок минимизации и максимизации формы
Как заменить кнопки минимилизации и максимилизации на собственные , чтобы можно...


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

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

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