선형 프로그래밍이있는 기계

Question

선형 계획법을 사용하여 계획 문제를 해결할 수 있다고 들었습니다. 선형 프로그래밍이 최적이고 대규모 계획 (예 : m 개의 기계에서 n 개의 작업 계획)이 기하 급수적으로 어려우므로 실제로 수행하는 방법을 이해하지 못합니다.

선형 프로그래밍을 사용하여 예를 들어 100 개의 작업과 10 개의 기계를 어떻게 해결할 수 있습니까? 설명이나 추가 독서를 나에게 줄 수 있니?

Answer 1

어떻게 선형 프로그래밍을 사용하여 100 개의 작업과 10 개의 기계를 문제를 해결할 수 있습니까?

일반적으로 할 수 없습니다. 이는 선형 프로그래밍 (LP)이 적용 할 수있는 일종의 계획 문제는 아닙니다.

LP 문제에서 해결할 변수 집합이 있습니다. 변수에 대한 제약 조건을 나타내는 일련의 선형 부등식 집합이 있습니다. 그리고 주어진 솔루션의 비용 (또는 이점)을 나타내는 변수의 선형 함수 (즉, 지수가 없거나 나눗셈이 없거나 "if-then-else"가없는 등)가 있습니다.

그런 문제가 있으면 LP를 사용하여 효율적으로 최적의 솔루션을 생성 할 수 있습니다. 당신이 물어 보는 것과 같은 작업 현장 스케줄링은 그런 종류의 문제가 아닙니다.

LP는 "상위 레벨"계획에 도움이되는 경향이 있습니다. 각 공장에서 얼마나 많은 제품을 생산해야합니까? 이러한 문제에서 LP를 사용하기 위해해야하는 것처럼 제약 조건을 선형 부등식으로 지정하고 비용 (또는 이점)을 선형 함수로 지정할 수 있습니다. 공지, 나는 얼마나 많은 제품이 ... "얼마나 많은 제품이 아닌지 ..."라고 말했다. 이것이 LP의 또 다른 한계이기 때문에 변수는 실제 값을 가져야합니다. 정수 솔루션을 제공하기 위해 솔루션이 필요한 경우 Integer Programming (또는 혼합 정수 프로그래밍) 문제가 발생합니다.