nan2inf .cn
数学 旧 .com 迁移

运筹学 / 习题/考试 / 作业 / 1

从旧 .com 全量搬运的历史内容，来源路径：/math/课程/运筹学/exams/作业/1/

约 4 分钟阅读
migrationlegacy-commathexamcourse

迁移来源

Homework 1 #

姓名: 刘欣楠

班级: 数学强基 2301

学号: 2233310237

Question 1 #

使用单纯形法来求解如下优化问题： 要求： 将其转化为标准形式，列出单纯形表手算作答。

min⁡−10x1−12x2−12x3s.t.x1+2x2+2x3≤20,2x1+x2+2x3≤20,2x1+2x2+x3≤20,x1,x2,x3≥0.⟹标准形式min⁡ f=−10x1−12x2−12x3s.t.x1+2x2+2x3+x4=20,2x1+x2+2x3+x5=20,2x1+2x2+x3+x6=20,x1,x2,x3,x4,x5,x6≥0. \begin{aligned} \min \quad & -10x_{1} - 12x_{2} - 12x_{3} \\ \text{s.t.} \quad & x_{1} + 2x_{2} + 2x_{3} \leq 20, \\ & 2x_{1} + x_{2} + 2x_{3} \leq 20, \\ & 2x_{1} + 2x_{2} + x_{3} \leq 20, \\ & x_{1}, x_{2}, x_{3} \geq 0. \end{aligned}\overset{\text{标准形式}}{\Longrightarrow} \begin{aligned} \min\ f &= -10x_1 - 12x_2 - 12x_3 \\ \text{s.t.}\quad & x_1 + 2x_2 + 2x_3 + x_4 = 20,\\ & 2x_1 + x_2 + 2x_3 + x_5 = 20,\\ & 2x_1 + 2x_2 + x_3 + x_6 = 20,\\ & x_1,x_2,x_3,x_4,x_5,x_6 \ge 0. \end{aligned} 



		\begin{tabular}{c|rrrrrr|r}

			基变量 & $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$ & $x_6$ & 右端项\\

			$-f$   & $-10$ & $-12$ & $-12$ & $0$ & $0$ & $0$ & $0$\\

			$x_4$ & $1$ & $2$ & $2$ & $1$ & $0$ & $0$ & $20$\\
			$x_5$ & $2$ & $1$ & $2$ & $0$ & $1$ & $0$ & $20$\\
			$x_6$ & $2$ & $2$ & $1$ & $0$ & $0$ & $1$ & $20$\\

		\end{tabular}


	\hfill


		\begin{tabular}{c|rrrrrr|r}

			基变量 & $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$ & $x_6$ & 右端项\\

			$-f$   & $-4$ & $0$ & $0$ & $6$ & $0$ & $0$ & $120$\\

			$x_2$ & $\frac12$ & $1$ & $1$ & $\frac12$ & $0$ & $0$ & $10$\\
			$x_5$ & $\frac32$ & $0$ & $1$ & $-\frac12$ & $1$ & $0$ & $10$\\
			$x_6$ & $1$ & $0$ & $-1$ & $-1$ & $0$ & $1$ & $0$\\

		\end{tabular}


	\begin{tabular}{c|rrrrrr|r}

		基变量 & $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$ & $x_6$ & 右端项\\

		$-f$   & $0$ & $0$ & $-4$ & $2$ & $0$ & $4$ & $120$\\

		$x_2$ & $0$ & $1$ & $\frac32$ & $1$ & $0$ & $-\frac12$ & $10$\\
		$x_5$ & $0$ & $0$ & $\frac52$ & $1$ & $1$ & $-\frac32$ & $10$\\
		$x_1$ & $1$ & $0$ & $-1$ & $-1$ & $0$ & $1$ & $0$\\

	\end{tabular}


\hfill


	\begin{tabular}{c|rrrrrr|r}

		基变量 & $x_1$ & $x_2$ & $x_3$ & $x_4$ & $x_5$ & $x_6$ & 右端项\\

		$-f$   & $0$ & $0$ & $0$ & $\frac{18}{5}$ & $\frac{8}{5}$ & $\frac{8}{5}$ & $136$\\

		$x_2$ & $0$ & $1$ & $0$ & $\frac{2}{5}$ & $-\frac{3}{5}$ & $\frac{2}{5}$ & $4$\\
		$x_3$ & $0$ & $0$ & $1$ & $\frac{2}{5}$ & $\frac{2}{5}$ & $-\frac{3}{5}$ & $4$\\
		$x_1$ & $1$ & $0$ & $0$ & $-\frac{3}{5}$ & $\frac{2}{5}$ & $\frac{2}{5}$ & $4$\\

	\end{tabular}

综上, 在三次迭代后, 已得到最优解, 无法再优化. 此时的解为 x⃗T=(4,4,4)\vec x^T=(4,4,4), f=136f=136.

Question 2 人才培养 #

北方印染公司需要的技术工人分为初级工、中级工和高级工三个层次。统计资料显示：培养出来的每个初级工每年可为公司增加产值 1 万元，每个中级工每年可为公司增加产值 4 万元，每个高级工每年可为公司增加产值 5.5 万元。公司计划在今后三年中对招聘的高中生和本公司的技工进行培训，预计拨出 150 万元作为职工培训费，其中，第一年投资 55 万元，第二年投资 45 万元，第三年投资 50 万元。每个等级的技术工人培训费用和时间如下表所示。

\begin{tabular}{ccccc}

		 &培训方式 & 第一年 & 第二年 & 第三年 \\

		1 & 高中生升初级工 & 1000 &   &   \\
		2 & 高中生升中级工 & 3000 & 3000 & 1000 \\
		3 & 高中生升高级工 & 3000 & 2000 & 4000 \\
		4 & 初级工升中级工 & 2800 &   &   \\
		5 & 初级工升高级工 & 2000 & 3200 & \\
		6 & 中级工升高级工 & 3600 &   &   \\

	\end{tabular}

目前公司共有初级工 226 人，中级工 560 人，高级工 496 人。由于公司目前师资力量不足，教学环境有限，每年在培养的职工人数受到一定限制。根据目前的情况，每年在培的初级工不超过 90 人，在培的中级工不超过 80 人，在培的高级工不超过 80 人。制定培训方案，使企业增加的产值最大。

要求： 请确定决策变量，写出完成的优化模型并附简要说明。

设 $

{x1t=第 t 年招收高中生升为初级工的人数t=1,2,3x2t=第 t 年招收高中生升为中级工的人数t=1x3t=第 t 年招收高中生升为高级工的人数t=1x4t=第 t 年由初级工升为中级工的人数t=1,2,3x5t=第 t 年由初级工升为高级工的人数t=1,2x6t=第 t 年由中级工升为高级工的人数t=1,2,3\begin{cases} x_{1t} = \text{第 $t$ 年招收高中生升为初级工的人数}&t=1,2,3 \\ x_{2t} = \text{第 $t$ 年招收高中生升为中级工的人数}&t=1 \\ x_{3t} = \text{第 $t$ 年招收高中生升为高级工的人数}&t=1 \\ x_{4t} = \text{第 $t$ 年由初级工升为中级工的人数}&t=1,2,3 \\ x_{5t} = \text{第 $t$ 年由初级工升为高级工的人数}&t=1,2 \\ x_{6t} = \text{第 $t$ 年由中级工升为高级工的人数}&t=1,2,3 \end{cases}

$

有三种限制: 资金限制, 学员限制, 师资限制.

对于资金限制

{1000x11+3000x21+3000x31+2800x41+2000x51+3600x61⩽5500001000x12+3000x21+2000x31+2800x42+3200x51+2000x52+3600x62⩽4500001000x13+1000x21+4000x31+2800x43+3200x52+3600x63⩽500000\begin{cases} 1000x_{11}+3000x_{21}+3000x_{31}+2800x_{41}+2000x_{51}+3600x_{61}\leqslant550000\\ 1000x_{12}+3000x_{21}+2000x_{31}+2800x_{42}+3200x_{51}+2000x_{52}+3600x_{62}\leqslant 450000\\ 1000x_{13}+1000x_{21}+4000x_{31}+2800x_{43}+3200x_{52}+3600x_{63}\leqslant 500000 \end{cases}

对于师资限制

{x11⩽90x21+x41⩽80x31+x51+x61⩽80第一年{x12⩽90x21+x42⩽80x31+x51+x52+x62⩽80第二年{x13⩽90x21+x43⩽80x31+x52+x63⩽80第三年\underset{\text{第一年}}{\begin{cases} x_{11}\leqslant 90\\ x_{21}+x_{41}\leqslant 80\\ x_{31}+x_{51}+x_{61}\leqslant 80 \end{cases}}\underset{\text{第二年}}{\begin{cases} x_{12}\leqslant90\\ x_{21}+x_{42}\leqslant 80\\ x_{31}+x_{51}+x_{52}+x_{62}\leqslant 80 \end{cases}}\underset{\text{第三年}}{\begin{cases} x_{13}\leqslant 90\\ x_{21}+x_{43}\leqslant 80\\ x_{31}+x_{52}+x_{63}\leqslant 80 \end{cases}}

对于学员限制

{x41+x51⩽226x61⩽560第一年{x41+x51+x42+x52⩽226+x11x61+x62⩽560+x41第二年\underset{\text{第一年}}{\begin{cases} x_{41}+x_{51}\leqslant 226\\ x_{61}\leqslant 560 \end{cases}}\underset{\text{第二年}}{\begin{cases} x_{41}+x_{51}+x_{42}+x_{52}\leqslant 226+x_{11}\\ x_{61}+x_{62}\leqslant 560+x_{41} \end{cases}} 第三年:{x41+x51+x42+x52+x43⩽226+x11+x12x61+x62+x63⩽560+x41+x42\text{第三年}:\begin{cases} x_{41}+x_{51}+x_{42}+x_{52}+x_{43}\leqslant 226+x_{11}+x_{12}\\ x_{61}+x_{62}+x_{63}\leqslant 560+x_{41}+x_{42} \end{cases}

但实际上结合每年各级别培训人数限制, 学员限制中有效的只有 x41+x42+x43+x51+x52⩽226+x11+x12x_{41}+x_{42}+x_{43}+x_{51}+x_{52}\leqslant 226+x_{11}+x_{12}.

除了上述三种限制外, 还要求各阶段各级别培训人数非负.

下面考虑总收益函数 ff 的表示:

感觉题目有不同理解.

如果考虑三年之后每年的产值最高, 那么应该是 (本人理解题目应该是这种情况, 不然高中生培训三年的方案没有意义):

三年后 (即最晚第四年起可以进行工作) 各级别工人人数依次为

226−x41−x42−x43−x51−x52+x11+x12+x13560−x61−x62−x63+x21+x41+x42+x43496+x31+x51+x52+x61+x62+x63\begin{aligned} 226-x_{41}-x_{42}-x_{43}-x_{51}-x_{52}+x_{11}+x_{12}+x_{13}\\ 560-x_{61}-x_{62}-x_{63}+x_{21}+x_{41}+x_{42}+x_{43}\\ 496+x_{31}+x_{51}+x_{52}+x_{61}+x_{62}+x_{63} \end{aligned}

整理后年产值增加 (单位: 万) f=x11+x12+x13+4x21+5.5x31+3x41+3x42+3x43+4.5x51+4.5x52+1.5x61+1.5x62+1.5x63f=x_{11}+x_{12}+x_{13}+4x_{21}+5.5x_{31}+3x_{41}+3x_{42}+3x_{43}+4.5x_{51}+4.5x_{52}+1.5x_{61}+1.5x_{62}+1.5x_{63}.

若理解为只考虑这三年的总收益增加最多, 且培训期间不产生产值, 那么函数如下:

分年份考虑当年参与工作的各级别工人数量, 依次为初级工, 中级工和高级工.

{226−x41−x51560−x61496第一年{226−x41−x51−x42−x52+x11560−x61−x62+x41496+x61第二年\underset{\text{第一年}}{\begin{cases} 226-x_{41}-x_{51}\\ 560-x_{61}\\ 496 \end{cases}}\underset{\text{第二年}}{\begin{cases} 226-x_{41}-x_{51}-x_{42}-x_{52}+x_{11}\\ 560-x_{61}-x_{62}+x_{41}\\ 496+x_{61} \end{cases}} 第三年:{226−x41−x51−x42−x52+x11−x43+x12560−x61−x62−x63+x41+x42496+x61+x62+x51\text{第三年:}\begin{cases} 226-x_{41}-x_{51}-x_{42}-x_{52}+x_{11}-x_{43}+x_{12}\\ 560-x_{61}-x_{62}-x_{63}+x_{41}+x_{42}\\ 496+x_{61}+x_{62}+x_{51} \end{cases}

整理后总的增加收益 (单位: 万) 为 f=x11+x12+5x41+2x42−x43+2.5x51−x52−x61−2.5x62−4x63f=x_{11}+x_{12}+5x_{41}+2x_{42}-x_{43}+2.5x_{51}-x_{52}-x_{61}-2.5x_{62}-4x_{63}.

讨论

评论

正在加载评论...