Assignment 1
Homework 1
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} $$
| 基变量 | $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$ |
初始表
| 基变量 | $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$ |
第一次迭代 (入 $x_2$, 出 $x_4$)
| 基变量 | $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$ |
第二次迭代 (入 $x_1$, 出 $x_4$)
| 基变量 | $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$ |
第三次迭代 (入 $x_3$, 出 $x_5$)
综上, 在三次迭代后, 已得到最优解, 无法再优化. 此时的解为 $\vec x^T=(4,4,4)$, $f=136$.
Question 2 人才培养
北方印染公司需要的技术工人分为初级工、中级工和高级工三个层次。统计资料显示：培养出来的每个初级工每年可为公司增加产值 1 万元，每个中级工每年可为公司增加产值 4 万元，每个高级工每年可为公司增加产值 5.5 万元。公司计划在今后三年中对招聘的高中生和本公司的技工进行培训，预计拨出 150 万元作为职工培训费，其中，第一年投资 55 万元，第二年投资 45 万元，第三年投资 50 万元。每个等级的技术工人培训费用和时间如下表所示。
| 培训方式 | 第一年 | 第二年 | 第三年 | |
|---|---|---|---|---|
| 1 | 高中生升初级工 | 1000 | ||
| 2 | 高中生升中级工 | 3000 | 3000 | 1000 |
| 3 | 高中生升高级工 | 3000 | 2000 | 4000 |
| 4 | 初级工升中级工 | 2800 | ||
| 5 | 初级工升高级工 | 2000 | 3200 | |
| 6 | 中级工升高级工 | 3600 |
目前公司共有初级工 226 人，中级工 560 人，高级工 496 人。由于公司目前师资力量不足，教学环境有限，每年在培养的职工人数受到一定限制。根据目前的情况，每年在培的初级工不超过 90 人，在培的中级工不超过 80 人，在培的高级工不超过 80 人。制定培训方案，使企业增加的产值最大。
要求： 请确定决策变量，写出完成的优化模型并附简要说明。
设
$$
\left\lbrace
\begin{array}{ll}
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{array}
\right.
$$
有三种限制: 资金限制, 学员限制, 师资限制.
对于资金限制
$$
\left\lbrace
\begin{array}{l}
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{array}
\right.
$$
对于师资限制
$$
\text{第一年}:\left\lbrace
\begin{array}{l}
x_{11}\leqslant 90\\
x_{21}+x_{41}\leqslant 80\\
x_{31}+x_{51}+x_{61}\leqslant 80
\end{array}
\right.
\quad
\text{第二年}:\left\lbrace
\begin{array}{l}
x_{12}\leqslant90\\
x_{21}+x_{42}\leqslant 80\\
x_{31}+x_{51}+x_{52}+x_{62}\leqslant 80
\end{array}
\right.
\quad
\text{第三年}:\left\lbrace
\begin{array}{l}
x_{13}\leqslant 90\\
x_{21}+x_{43}\leqslant 80\\
x_{31}+x_{52}+x_{63}\leqslant 80
\end{array}
\right.
$$
对于学员限制
$$
\text{第一年}:\left\lbrace
\begin{array}{l}
x_{41}+x_{51}\leqslant 226\\
x_{61}\leqslant 560
\end{array}
\right.
\quad
\text{第二年}:\left\lbrace
\begin{array}{l}
x_{41}+x_{51}+x_{42}+x_{52}\leqslant 226+x_{11}\\
x_{61}+x_{62}\leqslant 560+x_{41}
\end{array}
\right.
$$
$$
\text{第三年}:\left\lbrace
\begin{array}{l}
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{array}
\right.
$$
但实际上结合每年各级别培训人数限制, 学员限制中有效的只有 $x_{41}+x_{42}+x_{43}+x_{51}+x_{52}\leqslant 226+x_{11}+x_{12}$.
除了上述三种限制外, 还要求各阶段各级别培训人数非负.
下面考虑总收益函数 $f$ 的表示:
感觉题目有不同理解.
如果考虑三年之后每年的产值最高, 那么应该是 (本人理解题目应该是这种情况, 不然高中生培训三年的方案没有意义):
三年后 (即最晚第四年起可以进行工作) 各级别工人人数依次为
$$
\begin{array}{l}
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{array}
$$
整理后年产值增加 (单位: 万)
$$
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}.
$$
若理解为只考虑这三年的总收益增加最多, 且培训期间不产生产值, 那么函数如下:
分年份考虑当年参与工作的各级别工人数量, 依次为初级工, 中级工和高级工.
$$
\text{第一年}:\left\lbrace
\begin{array}{ll}
226-x_{41}-x_{51}\\
560-x_{61}\\
496
\end{array}
\right.
\quad
\text{第二年}:\left\lbrace
\begin{array}{ll}
226-x_{41}-x_{51}-x_{42}-x_{52}+x_{11}\\
560-x_{61}-x_{62}+x_{41}\\
496+x_{61}
\end{array}
\right.
$$
$$
\text{第三年}:\left\lbrace
\begin{array}{ll}
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{array}
\right.
$$
整理后总的增加收益 (单位: 万) 为
$$
f=x_{11}+x_{12}+5x_{41}+2x_{42}-x_{43}+2.5x_{51}-x_{52}-x_{61}-2.5x_{62}-4x_{63}.
$$