跳到主要内容

中央大学 理工学研究科 情報工学専攻 2026年2月実施 一般入試（春季）問題V

标签：

Author​

祭音Myyura (Based on 中央大学の公式解答例 refined with GPT 6 Astra)

Description​

問題 I は必答。問題 II～V のうち、2 問を選んで解答すること。

問題 V.

1. ある工場では製品 A と製品 B を生産している。これらの製品はどちらも材料 1、材料 2、材料 3 から作られる。それぞれの製品を 1 kg1\,\mathrm{kg} 生産するために必要な材料の量は下の表の通りである。

材料 1 の使用量 (kg)材料 2 の使用量 (kg)材料 3 の使用量 (kg)
製品 A22520
製品 B125020

製品 A を 1 kg1\,\mathrm{kg} 生産すると利益が PAP_A 円、製品 B を 1 kg1\,\mathrm{kg} 生産すると利益が PBP_B 円得られる。また、材料 1 は M1 kgM_1\,\mathrm{kg}、材料 2 は M2 kgM_2\,\mathrm{kg}、材料 3 は M3 kgM_3\,\mathrm{kg} だけ利用可能である。それぞれの製品の生産量は必ずしも整数である必要はない。このとき、利益を最大化するために製品 A と製品 B をそれぞれいくら生産すればいいかを求めたい。

(1) この問題を表す線形計画問題を与えなさい。ただし、問題の変数は、製品 A の生産量 (kg) を表す変数 xAx_A と、製品 B の生産量 (kg) を表す変数 xBx_B のみとすること。

(2) 問題のパラメータが次の値を取るとき、利益を最大化する製品 A と製品 B の生産量を求めなさい。

PA=140,PB=210,M1=120,M2=600,M3=320.P_A=140,\quad P_B=210,\quad M_1=120,\quad M_2=600,\quad M_3=320.

2. ある一直線上に伸びた通りに沿って 4 軒の家が建っている。それぞれの座標を p1,p2,p3,p4p_1,p_2,p_3,p_4 とする。この通りにゴミ捨て場を 1 カ所設置する。ゴミ捨て場を設置できる場所の座標は LL 以上 RR 以下に限られている。すべての家のゴミ捨て場までの距離を合計したものを最小化するように、ゴミ捨て場の設置場所を決定したい。

設置するゴミ捨て場の座標を求める問題を表現する線形計画問題を与えなさい。変数は自由に導入していいが、導入した変数の最適解における値とゴミ捨て場の座標がどのように対応するかも説明すること。

3. 次の線形計画問題を考える。

maximize10x1+25x2+5x3+36x4subject to8x1−x2+3x3+4x4=11,5x1+6x2+2x3+10x4≤40,x1,x2,x3≥0.\begin{aligned} \text{maximize}\quad &10x_1+25x_2+5x_3+36x_4\\ \text{subject to}\quad &8x_1-x_2+3x_3+4x_4=11,\\ &5x_1+6x_2+2x_3+10x_4\leq40,\\ &x_1,x_2,x_3\geq0. \end{aligned}

(1) この線形計画問題の双対問題を与えなさい。

(2) (x1,x2,x3,x4)=(0,4.9,5.3,0)(x_1,x_2,x_3,x_4)=(0,4.9,5.3,0) は、この線形計画問題の最適解である。このことを証明しなさい。

题目描述​

问题 I 为必答题；从问题 II～V 中选择 2 题作答。

问题 V

1. 某工厂生产产品 A 和 B，两者均由材料 1、2、3 制成。每生产 1 kg1\,\mathrm{kg} 产品所需的材料如下。

材料 1 用量 (kg)材料 2 用量 (kg)材料 3 用量 (kg)
产品 A22520
产品 B125020

生产 1 kg1\,\mathrm{kg} 产品 A、B 分别获得 PAP_A 日元、PBP_B 日元利润；可用材料 1、2、3 分别为 M1 kgM_1\,\mathrm{kg}、M2 kgM_2\,\mathrm{kg}、M3 kgM_3\,\mathrm{kg}。产量不必为整数。求使利润最大化的 A、B 产量。

(1) 给出这一问题的线性规划模型，只能使用两个变量 xA,xBx_A,x_B，分别表示产品 A、B 的产量（kg）。

(2) 当参数为下列数值时，求最优产量：

PA=140,PB=210,M1=120,M2=600,M3=320.P_A=140,\quad P_B=210,\quad M_1=120,\quad M_2=600,\quad M_3=320.

2. 一条直线街道上有 4 户人家，坐标分别为 p1,p2,p3,p4p_1,p_2,p_3,p_4。要设置一个垃圾收集点，允许的位置坐标在 LL 以上、RR 以下。希望使所有住户到收集点的距离总和最小。

给出求收集点坐标的线性规划模型。可以自由引入变量，但须说明最优解中这些变量的值与收集点坐标如何对应。

3. 考虑以下线性规划：

最大化10x1+25x2+5x3+36x4约束条件8x1−x2+3x3+4x4=11,5x1+6x2+2x3+10x4≤40,x1,x2,x3≥0.\begin{aligned} \text{最大化}\quad &10x_1+25x_2+5x_3+36x_4\\ \text{约束条件}\quad &8x_1-x_2+3x_3+4x_4=11,\\ &5x_1+6x_2+2x_3+10x_4\leq40,\\ &x_1,x_2,x_3\geq0. \end{aligned}

(1) 写出它的对偶问题。

(2) 证明 (x1,x2,x3,x4)=(0,4.9,5.3,0)(x_1,x_2,x_3,x_4)=(0,4.9,5.3,0) 是最优解。

Kai​

1(1) 生産計画の定式化​

maximizePAxA+PBxBsubject to2xA+12xB≤M1,25xA+50xB≤M2,20xA+20xB≤M3,xA,xB≥0.\begin{aligned} \text{maximize}\quad &P_Ax_A+P_Bx_B\\ \text{subject to}\quad &2x_A+12x_B\leq M_1,\\ &25x_A+50x_B\leq M_2,\\ &20x_A+20x_B\leq M_3,\\ &x_A,x_B\geq0. \end{aligned}

3 本の不等式はそれぞれ材料 1、2、3 の利用可能量を表す。生産量は実数でよく、整数制約は課さない。

1(2) 最適生産量​

材料 2、3 の制約をそれぞれ 25、20 で割ると、

xA+2xB≤24,xA+xB≤16.x_A+2x_B\leq24,\qquad x_A+x_B\leq16.

目的関数について

140xA+210xB=70(xA+2xB)+70(xA+xB)≤70⋅24+70⋅16=2800140x_A+210x_B =70(x_A+2x_B)+70(x_A+x_B) \leq70\cdot24+70\cdot16=2800

が成り立つ。(xA,xB)=(8,8)(x_A,x_B)=(8,8) は両不等式を等号で満たし、材料 1 の使用量も 2⋅8+12⋅8=112≤1202\cdot8+12\cdot8=112\leq120 である。従って実行可能で、上界 2800 を達成する。

製品 A を 8 kg,製品 B を 8 kg\boxed{\text{製品 A を }8\,\mathrm{kg},\quad\text{製品 B を }8\,\mathrm{kg}}

が最適であり、最大利益は 28002800 円である。

2. 絶対値の線形化​

ゴミ捨て場の座標を xx とし、家 ii からの距離を表す補助変数 yiy_i を導入する。

minimize∑i=14yisubject tox−pi≤yi(i=1,2,3,4),pi−x≤yi(i=1,2,3,4),L≤x≤R.\begin{aligned} \text{minimize}\quad &\sum_{i=1}^4y_i\\ \text{subject to}\quad &x-p_i\leq y_i\qquad(i=1,2,3,4),\\ &p_i-x\leq y_i\qquad(i=1,2,3,4),\\ &L\leq x\leq R. \end{aligned}

各 2 本の制約は yi≥∣x−pi∣y_i\geq|x-p_i| と同値で、yi≥0y_i\geq0 も自動的に満たされる。最小化の最適解では yi=∣x−pi∣y_i=|x-p_i| となるので、目的関数は距離の合計そのものである。最適解の xx の値が求める設置座標に対応する。

3(1) 双対問題​

第 1 制約が等式なので、対応する双対変数 y1y_1 は符号自由である。第 2 制約は最大化問題の「≤\leq」制約なので y2≥0y_2\geq0。また、原問題で非負制約が課されているのは x1,x2,x3x_1,x_2,x_3 のみであり、x4x_4 は符号自由である。従って x4x_4 に対応する双対制約は等式となる。

minimize11y1+40y2subject to8y1+5y2≥10,−y1+6y2≥25,3y1+2y2≥5,4y1+10y2=36,y1∈R,y2≥0.\boxed{ \begin{aligned} \text{minimize}\quad &11y_1+40y_2\\ \text{subject to}\quad &8y_1+5y_2\geq10,\\ &-y_1+6y_2\geq25,\\ &3y_1+2y_2\geq5,\\ &4y_1+10y_2=36,\\ &y_1\in\mathbb{R},\quad y_2\geq0. \end{aligned}}

3(2) 最適性の証明​

与えられた点 x∗=(0,4.9,5.3,0)x^*=(0,4.9,5.3,0) では、

−4.9+3⋅5.3=11,6⋅4.9+2⋅5.3=40,-4.9+3\cdot5.3=11,\qquad6\cdot4.9+2\cdot5.3=40,

かつ x1∗,x2∗,x3∗≥0x_1^*,x_2^*,x_3^*\geq0 なので、原問題で実行可能である。目的関数値は

25⋅4.9+5⋅5.3=149.25\cdot4.9+5\cdot5.3=149.

双対変数として (y1,y2)=(−1,4)(y_1,y_2)=(-1,4) を取ると、左辺は順に

8(−1)+5⋅4=12≥10,−(−1)+6⋅4=25,3(−1)+2⋅4=5,4(−1)+10⋅4=368(-1)+5\cdot4=12\geq10,\quad -(-1)+6\cdot4=25,\quad 3(-1)+2\cdot4=5,\quad 4(-1)+10\cdot4=36

となり、y2=4≥0y_2=4\geq0 も満たす。従って双対実行可能で、その目的関数値は

11(−1)+40⋅4=149.11(-1)+40\cdot4=149.

弱双対性により、原問題の任意の実行可能解の目的関数値は 149149 以下である。x∗x^* は実際に 149149 を達成するので、x∗ は最適解\boxed{x^*\text{ は最適解}} である。

Reference​

本页目录