問1
頻出度★★★
表は，技術者A，B，C がそれぞれ製品X，Y，Z を製造する場合の1日の生産額を示している。各技術者は1日に1製品しか担当できないとき，1日の最大生産額は何万円か。ここで，どの製品も必ず生産するものとする。 単位 万円／日
| 技術者 A | 技術者 B | 技術者 C | |
|---|---|---|---|
| 製品 X | 6 | 6 | 5 |
| 製品 Y | 7 | 6 | 8 |
| 製品 Z | 8 | 7 | 8 |
平成29年度 秋期 ITパスポート試験 問1
ストラテジ系企業活動 › 業務分析・データ利活用
This question's explanation and your answers so far.
解説
問 1
Incorrectア
20 is an example of a valid assignment, such as A→X (6), B→Y (6), C→Z (8) = 20, but it is not the maximum; it is lower than the best solution (22).
Incorrectイ
21 is a total that can be reached, for example A→X (6), B→Z (7), C→Y (8) = 21, or A→Y (7), B→X (6), C→Z (8) = 21, but neither reaches the maximum of 22.
- ウ
正解 This is an assignment problem (combinatorial optimization). Each engineer handles only one product, and X, Y, and Z must all be produced, so engineers and products are matched one-to-one (a bijection). With 3 engineers and 3 products, there are 3!=6 possible assignments. Computing them all, when A→Z (8), B→X (6), and C→Y (8), the total is 8+6+8=22 (ten-thousand yen), which is the maximum. Therefore the correct answer is 22 (choice ウ).
Incorrectエ
23 cannot be reached by any assignment (the 6 bijections). Looking only at the maximum of each column (engineer) gives 8, 7, 8, but these maxima are concentrated on product Z, which would mean selecting the same product more than once and violates the constraint. The upper limit of an assignment that satisfies the constraint is 22, so 23 is too high.
ここがポイント
- Assignment problem (combinatorial optimization): match rows (products) and columns (engineers) one-to-one to maximize the total. Simply adding up the maximum of each column selects the same product/engineer more than once and does not hold, so compare the 3!=6 assignments and pick the maximum.
- Reading the constraints: “each engineer makes one product per day” and “every product must be produced” together mean a bijection between engineers and products. Under this condition, the maximum total is 22.
用語