Homework 1
姓名: 刘欣楠
班级: 数学强基 2301
学号: 2233310237
Question 1
使用单纯形法来求解如下优化问题： 要求： 将其转化为标准形式，列出单纯形表手算作答。
$$
\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}
综上, 在三次迭代后, 已得到最优解, 无法再优化. 此时的解为 $\vec x^T=(4,4,4)$, $f=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 人。制定培训方案，使企业增加的产值最大。
要求： 请确定决策变量，写出完成的优化模型并附简要说明。
设 $ \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} $
有三种限制: 资金限制, 学员限制, 师资限制.
对于资金限制 $$\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}$$
对于师资限制 $$\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}}$$
对于学员限制 $$\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}} $$
$$ \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}$$ 但实际上结合每年各级别培训人数限制, 学员限制中有效的只有 $x_{41}+x_{42}+x_{43}+x_{51}+x_{52}\leqslant 226+x_{11}+x_{12}$.
除了上述三种限制外, 还要求各阶段各级别培训人数非负.
下面考虑总收益函数 $f$ 的表示:
感觉题目有不同理解.
如果考虑三年之后每年的产值最高, 那么应该是 (本人理解题目应该是这种情况, 不然高中生培训三年的方案没有意义):
三年后 (即最晚第四年起可以进行工作) 各级别工人人数依次为 $$\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=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}$.
若理解为只考虑这三年的总收益增加最多, 且培训期间不产生产值, 那么函数如下:
分年份考虑当年参与工作的各级别工人数量, 依次为初级工, 中级工和高级工.
整理后总的增加收益 (单位: 万) 为 $f=x_{11}+x_{12}+5x_{41}+2x_{42}-x_{43}+2.5x_{51}-x_{52}-x_{61}-2.5x_{62}-4x_{63}$.