조합 최적화 - 가구를 만들 때 최대 이익

Question

일부 회사는 대형 목재 패널과 함께 제공됩니다. 이 패널은 필수 조각으로 절단됩니다. 예를 들어 책꽂이를 만들려면 큰 패널에서 조각을 잘라야합니다. 대부분의 경우, 돼지 패널은 100 %에서 사용되지 않으며, 약간의 손실이있을 수 있으며, 일부 남은 조각은 사용할 수 없습니다. 손실을 최소화하기 위해 대형 패널/패널에서 개별 조각의 최적 배치를 찾아야합니다. 나는 이것이 "2 차원 직사각형 빈 포장 문제"라고 생각합니다.

이제 점점 더 흥미로워지고 있습니다.

일부 패널은 동일하지는 않지만 약간 색조가 다를 수 있습니다. 이상적인 책꽂이는 하나의 패널에서 모두 자르거나 같은 색조의 여러 패널에서 조각으로 만들어집니다. 그러나 책꽂이는 다른 자질 (이상적인 것, 다른 음색의 한 장, 두 장의 ..., 세 개의 다른 색판 사용, 등등 ...)으로 만들어 질 수 있습니다. 각 품질에는 자체 가격이 있습니다. (품질면에서 우월함).

이제 나무 패널이 재고가있어 가구 (예 : 책장 100 개)를 요청합니다. 목표는 수익을 극대화하는 것입니다 (예 : 이상적인 품질의 제품을 만들고 품질이 낮은 제품을 재료 손실을 낮게 유지하는 것).

이 문제를 해결하는 방법은 무엇입니까? 어떻게 빈 포장 문제와 결합? 그리고 힌트, 논문/기사는 감사하겠습니다. 정수형 선형 프로그래밍을 사용하여 일부 함수와 부등식을 최소화/최대화 할 수는 있지만이 문제를 해결하는 방법을 모르겠습니다.

(예를 들어 실제 장면을 고려하지 마십시오. 예를 들어 이상적인 것만 만들면 가장 좋습니다 ... 잔재로 인한 손실은 cm^2 당 X 돈이며 Y는 특정 가격입니다. 제품 품질 및 X와 Y는 "임의적"일 수 있음)

Answer 1

이러한 문제가 어떻게 해결되고 사용자가 특히 어려운지 아이디어를 제공 할 수 있습니다.

일반적인 최적화 문제에서 설정된 수의 변수 (예 : 길이)와 관련하여 기능 (예 : 에너지)을 최대화하거나 최소화하려고합니다. 예를 들어, 저장 에너지를 최소화하기 위해 스프링이 얼마나 오래 있어야 하는가? 답은 스프링의 평형 길이 인 숫자입니다. 또 다른 예는 "이익을 극대화하기 위해 어떤 가격으로 제품을 설정해야합니까?"입니다. (너무 비싸고 아무도 아무것도 사지 않을 것입니다, 너무 싸고 당신은 당신의 비용을 보상하지 않을 것입니다.) 다시 말하면, 대답은 숫자, 최적의 가격입니다. 그런 최적화는 보통의 미적분으로 처리됩니다.

더욱 어려운 최적화 문제는 답이 숫자가 아닌 모양과 같은 함수입니다. 예를 들면 중력의 위치 에너지를 최소화하기 위해 교수형 체인이 어떤 모양을 만들 것인가입니다. 또는 : 이익을 극대화하기 위해이 보드에서 어떤 모양을 잘라야합니까? 이러한 유형의 문제는 매우 어려운 분산 계산을 사용하여 해결됩니다.

최적화 문제를 수치 적으로 풀 경우 몇 가지 기본 단계가 있습니다. 먼저 다른 변수 'params'가 고정 된 상태에서 일부 변수 'cuts'와 관련하여 최대화하고자하는 이익 (cuts, params)과 같은 함수를 정의해야합니다. 'params'는 보유하고있는 나무의 양과 유형과 같은 정보를 저장하고 다른 유형의 가구는 가치가 있습니다.

두 번째 단계는 최상의 절단 세트를 추측하여 cuts_guess라고합니다. 이것을하기 위해서는 당신이 가지고있는 소모품을 사용하여 실제로 만들 수있는 가구 세트를 제안하는 알고리즘을 생각해 내야합니다. 예를 들어, 각 보드에서 적어도 하나의 책꽂이를 만들 수 있다면 나무를 사용하는 가장 좋은 방법은 처음 생각하는 것입니다.

세 번째 단계는 최적화입니다. 초기화를 위해 cuts_best = cuts_guess 및 profit_best = profit_guess = profit (cuts_guess, params)을 설정하십시오. 그런 다음 알고리즘 (알고리즘)을 사용하여 '상처 (cut)'에 대해 의사가 무작위로 변경하고 이익이 증가 또는 감소하는지 확인해야합니다. 당신이 찾은 가장 좋은 상처와 그에 상응하는 이익을 기록하십시오. 일반적으로 가능한 한 많은 수의 가능성을 탐색하고 가난한 선택에 '집착'하지 않기 위해 어떤 임의성이 관련된 경우 가장 좋습니다. 'Monte Carlo algorithm'을 보면이 예제를 찾을 수 있습니다.

어쨌든,이 모든 것이 여러분의 문제에 대해 매우 어려울 것입니다. 변수 (예 : 길이)를 추측하고 그 추측을 변경하는 방법 (예 : 길이를 약간 늘리거나 줄임)은 쉽습니다. 보드에 컷 아웃을 배치하는 방법이나 작은 변화를 만드는 방법에 대해 '추측'하는 방법은 전혀 분명하지 않습니다.