早稲田大学 創造理工学研究科 経営デザイン専攻 2025年実施 専門科目 問2（オペレーションズ・リサーチ）

标签：

• Waseda-University
• Simplex-Method
• Linear-Programming-Duality
• Complementary-Slackness
• Branch-and-Bound
• Binary-Integer-Programming
• Dynamic-Programming-Principle
• M-M-1-Queue
• Littles-Law

Author

祭音Myyura (co-authored with GPT 6 Astra)

Description

小問1

以下の線形計画問題を考える。

$$\begin{array}{ll} \text{Maximize} & z=3x_1+5x_2\\ \text{Subject to} & x_1+2x_2\le 6,\\ &3x_1+2x_2\le 12,\\ &x_1,x_2\ge 0. \end{array}$$

(1) スラック変数 $s_1,s_2$ を用いて，単体法を用いて最適解を求めたい。目的関数の改善に最も寄与する変数を選びピボット操作を1回行い，新しい辞書を以下の空欄に埋めよ。

基底変数	$x_1$	$x_2$	$s_1$	$s_2$	定数項
$z$

(2) 双対変数 $\lambda_1,\lambda_2$ を用いて，双対問題を定式化せよ。

(3) 主問題の候補解として $x_1=2,x_2=2$ が，与えられている。この解が最適解であるかどうかを，相補性条件を用いて確認せよ。

小問2

(1) ある企業は3つの開発プロジェクト P1，P2，P3 の実施可否を検討している。それぞれにはコストと利益があり，予算の上限は10百万円である。また，実行に関するいくつかの論理的な制約が存在する。この問題を各プロジェクトの実施可否を示すバイナリ変数 $x_1,x_2,x_3$ を用いて，整数計画問題として定式化せよ。

プロジェクト	費用（百万円）	利益（百万円）
P1	5	8
P2	6	9
P3	4	6

条件：

• 条件①：P2 を実施するならば，必ず P1 も実施しなければならない。
• 条件②：P1 と P3 のいずれか一方は実施しなければならない（ただし両方実施も可）。
• 条件③：P2 を実施する場合は，P3 は実施してはならない。

(2) 整数計画問題に関する以下の空欄を埋めよ。

分枝限定法では，まず（①）制約を無視して連続変数として解く（②）問題を解くことで，（③）を求める。あるノードの（③）が，現在の最良整数解の値（④）よりも小さいとき，そのノードは探索から除外される。この操作を（⑤）と呼ぶ。動的計画法では，動的計画法では，「問題の最適解は，その部分問題の解を組み合わせて得られる」という（⑥）の原理に基づいて構成される。以前に計算した状態の値を用いて次の状態を定義する（⑦）関係を持つ。状態数が変数の増加に応じて指数的に増えることで，計算量やメモリ量が爆発的に増大する現象を，一般に（⑧）と呼ぶ。

小問3

待ち行列理論に関する以下の空欄を埋めよ。

M/M/1 型待ち行列モデルに従うある受付窓口では，顧客の来店が（①）分布に従い，1時間あたり平均8人が到着する。また，1人の対応時間は（②）分布に従い，平均対応時間6分である。すなわち，1時間あたり（③）人を対応できる。これらの到着率 $\lambda$（人／時）は，$\lambda=$（④），サービス率 $\mu$（人／時）は $\mu=$（⑤），利用率 $\rho$ は $\rho=$（⑥） となる。このとき，システム内の平均人数 $L$ は（⑦），平均待ち時間 $W$ は（⑧）となる。両者の間には $L=$（⑨）$\times W$ という関係が成立し，これを（⑩）の法則とよぶ。多くの場合，利用率 $\rho$ が（⑪）より小さくなると，システムは（⑫）とよばれる安定な状態へ向かい，確率論的な解析が可能となる。

题目描述

小问1 考虑线性规划：最大化 $z=3x_1+5x_2$，约束为 $x_1+2x_2\le6$、$3x_1+2x_2\le12$、$x_1,x_2\ge0$。

(1) 引入松弛变量 $s_1,s_2$，选择对目标函数改善贡献最大的变量，执行一次枢轴操作，将新字典填入上表。(2) 用对偶变量 $\lambda_1,\lambda_2$ 写出对偶问题。(3) 用互补松弛条件判断候选解 $(x_1,x_2)=(2,2)$ 是否最优。

小问2 (1) 企业选择开发项目 P1、P2、P3，各项目费用分别为5、6、4百万円，利润分别为8、9、6百万円，预算不超过10百万円。实施 P2 必须实施 P1；P1 与 P3 至少实施一个，可以同时实施；P2 与 P3 不能同时实施。用二元变量 $x_1,x_2,x_3$ 建立整数规划模型。

(2) 填空：分支定界法首先忽略①约束，把变量视为连续变量，求解②问题以取得③。如果某节点的③小于当前最好整数解的值④，则排除该节点，称为⑤。动态规划基于⑥原理，以部分问题的解组合成原问题的最优解；通过⑦关系用已计算的状态值定义后续状态。状态数随变量增加而指数增长，导致计算量和内存急剧增加的现象，称为⑧。

小问3 M/M/1 服务窗口的到店人数服从①分布，每小时平均到达8人；每位顾客的服务时间服从②分布，平均6分钟，每小时可服务③人。求到达率④、服务率⑤、利用率⑥、系统内平均人数⑦、平均时间⑧。关系 $L=$⑨$\times W$ 称为⑩定律；当利用率小于⑪时，系统趋向称为⑫的稳定状态。原文将 $W$ 称为“平均等待时间”。

Kai

小問1

(1)

初期辞書は

$$s_1=6-x_1-2x_2,\qquad s_2=12-3x_1-2x_2,\qquad z=3x_1+5x_2.$$

$5>3$ より $x_2$ を入基底変数とする。最小比率は $\min\{6/2,12/2\}=3$ なので，$s_1$ が出基底変数となる。ピボット後は

$$\boxed{\begin{aligned} z&=15+\frac12x_1-\frac52s_1,\\ x_2&=3-\frac12x_1-\frac12s_1,\\ s_2&=6-2x_1+s_1. \end{aligned}}$$

各行を「基底変数＝右辺」の形で表し，表に右辺の係数を記入すると，

基底変数	$x_1$	$x_2$	$s_1$	$s_2$	定数項
$z$	$1/2$	$0$	$-5/2$	$0$	$15$
$x_2$	$-1/2$	$0$	$-1/2$	$0$	$3$
$s_2$	$-2$	$0$	$1$	$0$	$6$

となる。

(2)

$$\boxed{\begin{array}{ll} \text{Minimize}&w=6\lambda_1+12\lambda_2\\ \text{Subject to}&\lambda_1+3\lambda_2\ge3,\\ &2\lambda_1+2\lambda_2\ge5,\\ &\lambda_1,\lambda_2\ge0. \end{array}}$$

(3)

候補解 $(2,2)$ は実行可能で，主制約のスラックは $(s_1,s_2)=(0,2)$ である。最適なら相補性条件より

$$\lambda_2s_2=0\quad\Longrightarrow\quad\lambda_2=0.$$

また $x_1,x_2>0$ より，両双対制約は等号となるから

$$\lambda_1+3\lambda_2=3,\qquad 2\lambda_1+2\lambda_2=5.$$

$\lambda_2=0$ を代入すると $\lambda_1=3$ と $\lambda_1=5/2$ が同時に必要となり，矛盾する。したがって，$\boxed{(2,2)\text{ は最適解ではない}}$。

実際，$(x_1,x_2)=(3,3/2)$ と $(\lambda_1,\lambda_2)=(9/4,1/4)$ は主・双対の実行可能解で，目的値はともに $33/2>16$ となる。

小問2

(1)

$x_i=1$ を Pi の実施，$x_i=0$ を非実施とすると，

$$\boxed{\begin{array}{ll} \text{Maximize}&8x_1+9x_2+6x_3\\ \text{Subject to}&5x_1+6x_2+4x_3\le10,\\ &x_2\le x_1,\\ &x_1+x_3\ge1,\\ &x_2+x_3\le1,\\ &x_i\in\{0,1\}\quad(i=1,2,3). \end{array}}$$

予算制約に続く3本の不等式が，それぞれ条件①，②，③を表す。

(2)

空欄	解答	空欄	解答
①	整数	⑤	限定操作（枝刈り）
②	緩和	⑥	最適性
③	上界	⑦	再帰
④	下界	⑧	次元の呪い

最大化問題では，緩和問題の最適値が上界，実行可能な整数解の目的値が下界を与える。

小問3

$$\mu=\frac{60}{6}=10,\qquad \rho=\frac{\lambda}{\mu}=\frac8{10}=0.8,$$

$$L=\frac{\rho}{1-\rho}=4,\qquad W=\frac{L}{\lambda}=\frac1{\mu-\lambda}=\frac12\text{ 時間}.$$

空欄	解答	空欄	解答
①	ポアソン	⑦	$4$ 人
②	指数	⑧	$0.5$ 時間（30分）
③	$10$	⑨	$\lambda$
④	$8$	⑩	リトル
⑤	$10$	⑪	$1$
⑥	$0.8$	⑫	定常状態

ここで $W$ は $L=\lambda W$ に対応するサービス時間を含めた平均系内時間である。サービス開始までの平均待ち時間は $W_q=W-1/\mu=0.4$ 時間（24分）となる。