내 문제는 특정 숫자의 가중치 합계의 절대 값을 최소화하는 것입니다. 나는 무게를 찾아야 해.가중 합계의 절대 값을 최소화
최소 중량 0.1 가령이다 (< 0 A4, A3)의 내가되도록 (A1, A2> 0), A3과 A4, A2, A1, 숫자 A의 세트가 있다고 가정하자 (10 %), 최대 값은 0.4 (40 %)입니다. 나는 가중치 합이 0이되도록 가중치 w을 찾고 있습니다. 0이 가능하지 않다면, 0에 가장 가깝습니다. 이를 달성하기 위해 간단한 선형 모델을 사용할 수 있습니다. 간단한 선형 프로그램으로 솔루션을 매우 빨리 찾을 수 있습니다. 그러나, 나는이 문제에 대한 다항식 알고리즘이나 공식을 찾기를 매우 원합니다. 어떤 아이디어? 이 문제가 잘 알려져 있습니까?
감사합니다.
최소화 (최대화) SUM w * a은 쉽습니다. 모든 가중치를 최소값으로 설정 한 다음 최소값에서 최대 값 (최대 값과 최소값)을 설정하면 전역 최대 값에 도달 할 때까지 최대 값을 유지하는 가중치가 증가합니다.
[최소, 최대] 간격에 0이 포함 된 경우 최적 해는이 두 해의 볼록한 조합으로 실현 될 수 있습니다. 그렇지 않은 경우 솔루션을 0에 가깝게 만듭니다.
ellipsoid algorithm은 선형 프로그래밍을위한 최악의 경우의 다항식 시간 알고리즘입니다.
그러나 문제를 빨리 해결하고 싶다고 생각합니다. 따라서 다항식 시간 알고리즘에 관심이있는 것입니다.
simplex 방법으로 더 편리 할 것입니다. 비록 심플 렉스가 최악의 경우 기하 급수적이라 할지라도, 이것은 실용적인 응용 분야에서 가장 좋은 선택 인 것으로 보인다. 당연히, 그것은 내가 아는 모든 양질의 솔버에서 구현됩니다.
안녕하세요 알리, 귀하의 답변 주셔서 감사합니다,하지만 사실 이미 이미 단서와 함께 그것을 매우 빨리 해결할 수 있습니다. 문제는 여기서 더 빨리 해결하고 싶지 않다는 것입니다. 선형 프로그래밍 모델을 사용하지 않고이 문제를 해결할 수있는 특수 알고리즘이 생겼는지 확인하고 싶습니다. – Chicoscience
OK, 알 수 있습니다. 선형 프로그래밍 모델을 피하는 이유는 무엇입니까? 응용 프로그램에 LP 솔버가 종속되어있는 것을 원하지 않습니까? – Ali
사실 내 의도는 문제가 얼마나 쉬운지를 수학적으로 증명 한 것입니다. – Chicoscience
흥미로운 아이디어인데, 나는 그것을 시도하고 그것에 대해 논평하기 위해 다시 올 것이다. – Chicoscience