비 인접 셀 제한이있는 Excel 해 찾기?

Question

저는 Excel 솔버가있는 초보자이며 데이터 과학 서적을 집어 들었을 때 그 사실을 알게되었습니다. 이 도구에 익숙해지기 위해 여러 가지 문제를 해결하기 위해 노력했습니다. 비록 내가 솔버를 사용할 수 있다면 나는 확신 할 수 없다. 기본적으로, 확인해야 할 제약 조건은 두 셀이 인접 해 있는지 여부입니다.

내 문제 : 나는 구슬의 다른 숫자를 포함하는 가방 무리가 있습니다. 나는 가방을 가져 와서 얻는 구슬의 수를 극대화하고 싶지만 서로 인접 해있을 수는 없습니다.

• 값 =
• 는
• 위반 (이진) 가방 여부를 선택할지 여부를 = 선택 가방에 구슬의 수 = (선택 * 가방 :

  이

  내가 스프레드 시트에있는 것입니다 번호) 1 - (Bag 번호 선택) 2

인접한 두 개의 가방을 가져 오는 경우 위반이 -1이됩니다.

+------------+----+----+----+---+---+-------------+ 
| Bag Number | 1 | 2 | 3 | 4 | 5 | Total Value | 
+------------+----+----+----+---+---+-------------+ 
| Value  | 10 | 20 | 30 | 40| 50|   150| 
| Choose  | 0 | 0 | 0 | 0 | 0 |   0| 
| Violation | 0 | 0 | 0 | 0 | |    | 
+------------+----+----+----+---+---+-------------+ 

최적의 솔루션 : 나는 몇 constraits의 조합을 시도했습니다

+------------+----+----+----+---+---+-------------+ 
| Bag Number | 1 | 2 | 3 | 4 | 5 | Total Value | 
+------------+----+----+----+---+---+-------------+ 
| Value  | 10 | 20 | 30 | 40| 50|   150| 
| Choose  | 1 | 0 | 1 | 0 | 1 |   90| 
| Violation | 1 | -3 | 3 |-5 | |    | 
+------------+----+----+----+---+---+-------------+ 

: 행

• 선택에 진 제약 조건을 두는를
• 위반> = 0 위반 < = -2
• 총 목표 값 < = T 가능한 값 (150)

나는이 문제를 스스로 해결했다. 이것은 심지어 실현 가능합니까?

Answer 1

예, 문제가 많습니다.

나는 인접성 제약 조건을 공식화하는 다른 방법을 제안합니다.

choose_1 + choose_2 <= 1 
choose_2 + choose_3 <= 1 
choose_3 + choose_4 <= 1 
choose_4 + choose_5 <= 1 

이 대부분의 (1,2), (2,3), (3,4)의 각 쌍에서 하나 (4,5)가 선택 될 수 있음을 나타냅니다 특히, 나는 다음과 같은 사용합니다. 일반적으로 가방 이름 (즉, 숫자 대신 문자열)이 될 수있는 가방 번호를 사용하지 않는다는 이점이 있습니다. 또 다른 이점이 있습니다. 변수를 2 진수로 정의 할 필요가 없으며 0과 1 사이의 연속으로 만 정의 할 수 있습니다 : 0 <= choose_i <= 1, 모두 i = 1,...,5. 이는 결과 제약 행렬이 Totally Unimodular이기 때문에 이진 문제의 linear programming relaxation을 풀면 choose_i이 모두 0 또는 1 인 최적의 솔루션이됩니다. 이 변수 (녹색)를 구별하기 위해 다른 색상을 사용하는 것이 좋습니다

하는 것으로, 제약 (빨간색) 및 데이터 (파란색) :

은 여기 내 스프레드 시트 레이아웃입니다.또한 목표 셀에 녹색 글씨로 표시합니다. 여기

그리고 해석 모델입니다 :

솔루션 :

여기

는 공식 있습니다3210

매트릭스가 완전히 단일 모듈이라는 사실은 guarantee이며 최적 해는 이진 값을 갖습니다. 일반적으로 이것은 사실이 아니므로 변수를 이진수로 정의해야 branch and bound에 도달해야합니다.

이 정보가 도움이되기를 바랍니다. 행복한 모델링!