배낭문제

소개글

배낭문제에 관한 리포트입니다

목차

없음

본문내용

위 배낭 문제는 제약조건 속에서 최대효용을 얻어내는 문제이다. 즉, 개수라는 의사결정 변수를 정해서 최대효용이라는 목적함수를 구해야하는 것이다. 제약조건으로는 학생의 체력을 고려해서 짐의 무게를 30kg이하로 하는 것이 주어졌다. 따라서 ‘짐의 무게들의 합인 셀 $C$8은 $C$9(30kg) 보다 작거나 같다’라는 제약조건을 주었다. 이것만 생각할 경우 f만 10개를 가져가면 100의 효용을 가져올 수 있어 최고의 선택이 될 수 있다.
하지만 문제에서는 또 다른 제약조건을 주는데 이는 바로 ‘각 물건은 하나씩 필요함’이다. 즉, a, b, c, d, e, f는 하나보다 더 많이 가져 갈 필요가 없다는 것이다. 따라서 a, b, c, d, e, f의 개수를 의미하는 셀들($B$2 $B$3 $B$4 $B$5 $B$6 $B$7)에 1 or 0을 의미하는 bin(이진수)을 제약조건으로 주었다.
그런 후 소프트웨어를 통해 계산과정을 거쳐 산출해낸 결과를 바탕으로 볼 때, 필요한 물건의 무게와 효용을 모두 따져보아 물건 b를 제외한 나머지 a, c, d, e, f를 각각 하나씩 챙길 경우가 제약조건을 모두 만족하는 의사결정대안들 중에서 가장 효율적이고 효과적인 대안으로 나왔다.

이때 총 효용은 5(a) + 8(c) + 3(d) + 9(e) + 10(f) = 35

또한 총 무게는
7(a) + 8(c) + 6(d) + 5(e) + 3(f) = 29 (단위:kg)

의 값을 가지므로 이는 30kg이하의 무게라는 제약조건을 만족하며 조건 하의 최댓값인 35의 값을 가진다.

참고 자료

없음