다음 선형계획법 모형에서 기저해(basic solution)의 수는?M… | [서울시 연구사 경영과학] 14년 1회차 기출문제 상세 페이지

1[서울시 연구사 경영과학] 14년 1회차
다음 선형계획법 모형에서 기저해(basic solution)의 수는?
Max z=5x1+6x2Max\ z = 5x_1 + 6x_2
5x1+10x2≤1105x_1 + 10x_2 \le 110
2x1+x2≤202x_1 + x_2 \le 20
3x1+3x2≤393x_1 + 3x_2 \le 39
x1≥0, x2≥0x_1 \ge 0,\ x_2 \ge 0
1
2개
2
4개
3
5개
4
8개
5
10개
해설

기저해의 수는 10개이다.

여유변수 3개를 더하면 변수 5개·제약식 3개가 되고, 기저해는 5개 변수 중 3개를 기저변수로 고르고 나머지 2개를 0으로 둔 해다.
5C3=5!3! 2!=10{}_5C_3=\dfrac{5!}{3!\,2!}=10

세 제약선과 두 좌표축 중 평행한 쌍이 없어 두 직선의 교점 10개가 모두 존재하므로, 실행가능 여부와 관계없이 10개가 모두 기저해다.

  • 5개: 실행가능 영역의 꼭짓점 (0, 0), (10, 0), (7, 6), (4, 9), (0, 11)만 센 실행가능 기저해의 수다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[서울시 연구사 경영과학] 14년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요서울시 연구사 경영과학 기출문제 암기장 전체 보기