고객지원
기술문의
질문있습니다.
- 최명진
- 2008.10.06
- 조회수 1,983
최적화모형 과제.hwp댓글 1
-
- 임승빈2008-10-06
- 안녕하세요.
우선 첫 번째 문제부터 말씀드리자면,
Objective에 상수값을 최대화 하는 형태가 되어 있네요(변수가 없음).
수정 내용은 다음과 같습니다.
결정변수:
varX_i - i번째 단어가 선택되면 1, 아니면 0 (0-1 integer)
상수:
S1_i - i번째 단어의 첫번째 글자 수치
S2_i - i번째 단어 두번째 글자 수치
S3_i - i번째 단어 세번째 글자 수치
목적식:
단어 수치 합을 최대로 하는 변수 선택
제약식 :
1. 선택되는 단어는 총 8가지
2. 첫번째 글자는 두번째 글자보다 작은 수
3. 첫번째 글자는 세번재 글자보다 작은 수
결과:
// solution (optimal) with objective 259
varX = [0 0 0 1 1 1 0 0 0 0 0 1 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0];
선택되는 단어는 4, 5, 6, 12, 13, 14, 16, 18 번째 단어입니다.
다음으로 두 번째 문제 풀이는 다음과 같습니다.
물건은 weight 단위로 쪼개질 수 없다라는 조건이 결정변수를 정하는데 중요한 역할을 한다고 생각되어집니다.
결정변수:
X_b_i - b 빈에 i 번째 물건이 들어가면 1, 아니면 0
Y_b - b 빈이 사용되면 1, 아니면 0
목적식:
사용되는 빈의 개수 최소화
제약식:
1. 각 빈에 들어가는 물건은 빈 용량의 최대수치를 넘을 수 없음
2. 모든 빈 안에 물건은 한번만 들어갈 수 있음
결과:
// solution (optimal) with objective 3
Y = [0 1 1 1 0];
X = [[0 0 0 0 0 0 0 0]
[0 1 0 0 1 0 0 0]
[1 0 0 0 0 1 0 0]
[0 0 1 1 0 0 1 1]
[0 0 0 0 0 0 0 0]];
사용되는 빈 수: 3개
빈 1 - 66, 19
빈 2 - 80, 9
빈 3 - 23, 17, 21, 32
구체적은 모델 내용은 아래와 같습니다.
1번문제:
range Index = 1..47;
int A=1; int B=2; int C=3; int D=4; int E=5;
int F=6; int G=7; int H=8; int I=9; int J=10;
int K=11; int L=12; int M=13; int N=14; int O=15;
int P=16; int Q=17; int R=18; int S=19; int T=20;
int U=21; int V=22; int W=23; int X=24; int Y=25;
int Z=26;
int S1[Index] = [ A, A, B, B, C, C, D, D, E, E,
F, F, G, G, H, H, H, I, I, J,
J, K, L, L, L, M, M, N, N, O,
O, P, P, Q, Q, R, R, S, S, T,
T, U, V, W, X, Y, Z ];
int S2[Index] = [ D, F, E, K, C, I, E, I, A, G,
A, I, H, O, A, O, U, O, V, C,
O, E, K, I, Y, O, T, E, T, I,
S, I, R, M, U, O, U, T, I, U,
V, T, I, H, I, E, I ];
int S3[Index] = [ V, T, T, S, W, R, R, P, T, O,
R, N, Q, O, T, I, G, N, E, S,
E, N, K, P, E, L, G, S, H, L,
F, P, F, G, E, E, G, G, P, E,
A, E, P, O, N, S, P ];
dvar int varX[Index] in 0..1;
maximize
sum(i in Index)
(S1[i] + S2[i] + S3[i]) * varX[i];
subject to {
const_1:
sum(i in Index)
varX[i] == 8;
const_2:
forall(i in Index)
S1[i] * varX[i] <= S2[i] * varX[i];
const_3:
forall(i in Index)
S1[i] * varX[i] <= S3[i] * varX[i];
}
2번문제:
int NbItems = 8;
int NbBins = 5;
int BoxWeight = 93;
range Items = 1..NbItems;
range Bins = 1..NbBins;
int WeightItems[Items] = [ 80, 66, 23, 17, 19, 9, 21, 32 ];
dvar int Y[Bins] in 0..1;
dvar int X[Bins][Items] in 0..1;
minimize
sum(b in Bins)
Y[b];
subject to {
const_1:
forall(b in Bins)
sum(i in Items)
WeightItems[i] * X[b][i] <= BoxWeight * Y[b];
const_2:
forall(i in Items)
sum(b in Bins)
X[b][i] == 1;
}
목록
확인