Это языковое агностическое решение; вы можете реализовать это с помощью любой из библиотек линейного программирования смешанного целого в python, например. CPLEX, SCIP, glpk и т. Д.
Идея состоит в том, что ваша проблема может быть представлена в виде смешанной целочисленной линейной программы путем добавления вспомогательных двоичных переменных y
с использованием техники «большого М».
У вас есть множество k
неравенств вида:
E[i]: sum[j=0..n] a[i][j]*x[j] <= b[i]
Для каждого из этих ограничений, выбрать постоянную M[j]
, что является «достаточно большой», то есть всегда больше, чем с левой стороны минус правая часть неравенства. Пусть y[i]
бинарная переменная, связанная с ограничением, и рассмотрим модифицированное неравенство:
EM[i]: sum[j=0..n] a[i][j]*x[j] <= b[i] + M[i]*(1-y[i])
Вы можете видеть, что (при условии M[i]
является достаточно большим):
- если
y[i]=0
, то EM[i]
всегда проверяется ;
- если
y[i]=1
и EM[i]
подтверждено, то E[i]
также подтверждено.
Таким образом, все, что вам нужно сделать, это решить смешанно-целочисленную задачу:
Minimize: sum[i=0..k] y[i]
Subject to: EM[i] for all i=0..k
sum[j=0..n] x[j] = 1
Где x
массив непрерывных переменных и y
представляет собой массив двоичных переменных.
После решения этой проблемы компонент x
решения - это значения, которые вы ищете. Кроме того, вы можете получить число удовлетворенных неравенств, подсчитав число компонентов со значением 1
в оптимальном значении y
.
Навин, я не собираюсь решать систему линейных уравнений, вместо этого у меня есть система линейных НЕРАВЕНСТВ, которые, как я знаю, не будут удовлетворены для любых значений x1, x2, ...., x6 одновременно. Поэтому меня интересуют те значения xs, для которых выполняется большинство неравенств. Например, если x1 = 0,1, x2 = 0,3, ...... удовлетворяет 10 неравенствам из 15 и x1 = 0,2, x2 = 0,4, ....... удовлетворяет 12 неравенствам из 15, тогда мое решение должно быть вторым набором значений x. – Hammer
Не могли бы вы опубликовать то, что вы сделали до сих пор, и где вы застряли.это я посмотрю на код –