1. 习题一：线性规划问题
题目描述
某工厂生产两种产品A和B，生产A产品需要2小时的机器时间和3小时的工人时间，生产B产品需要1小时的机器时间和2小时的工人时间。工厂每天有8小时的机器时间和12小时的工人时间。A产品每件利润为50元，B产品每件利润为30元。问：每天生产A和B产品各多少件，才能使工厂获得最大利润？
解题步骤
建立模型：
- 设生产A产品x件，B产品y件。
- 目标函数：最大化利润 ( Z = 50x + 30y )。
- 约束条件： [ \begin{cases} 2x + y \leq 8 \ 3x + 2y \leq 12 \ x, y \geq 0 \end{cases} ]
求解过程：
- 使用单纯形法求解线性规划问题。
- 初始基本可行解为 ( x = 0, y = 0 )。
- 通过迭代，找到最优解 ( x = 4, y = 2 )。
答案解析：
- 每天生产A产品4件，B产品2件，可获得最大利润 ( Z = 50 \times 4 + 30 \times 2 = 260 ) 元。
2. 习题二：运输问题
题目描述
某工厂有3个生产点，分别生产产品A、B和C。产品A、B和C的需求量分别为100、200和150件。生产点1、2和3的单位生产成本分别为10、8和5元。运输成本如下表所示：
| 生产点 | 需求点 |
|---|---|
| A | 10 |
| B | 15 |
| C | 20 |
问：如何安排运输方案，使得总成本最低？
解题步骤
建立模型：
- 设从生产点i到需求点j的运输量为 ( x_{ij} )。
- 目标函数：最小化总成本 ( Z = \sum{i=1}^{3} \sum{j=1}^{3} c{ij} x{ij} )。
- 约束条件： [ \begin{cases} \sum{i=1}^{3} x{ij} = dj & \text{（j=1,2,3）} \ \sum{j=1}^{3} x_{ij} = si & \text{（i=1,2,3）} \ x{ij} \geq 0 & \text{（i,j=1,2,3）} \end{cases} ]
- 其中，( c_{ij} ) 为从生产点i到需求点j的运输成本，( s_i ) 为生产点i的产量，( d_j ) 为需求点j的需求量。
求解过程：
- 使用北西角法求解运输问题。
- 根据北西角法，得到初始基本可行解。
答案解析：
- 运输方案为：从生产点1到需求点1运输10件，从生产点1到需求点2运输20件，从生产点1到需求点3运输30件，从生产点2到需求点1运输15件，从生产点2到需求点2运输25件，从生产点2到需求点3运输35件。
- 总成本为 ( Z = 10 \times 10 + 20 \times 20 + 30 \times 30 + 15 \times 15 + 25 \times 25 + 35 \times 35 = 1850 ) 元。
3. 习题三：指派问题
题目描述
某公司有5个部门需要分配到5个办公室，每个部门只能分配到一个办公室，每个办公室只能分配一个部门。各部门对办公室的偏好如下表所示：
| 部门 | 办公室1 | 办公室2 | 办公室3 | 办公室4 | 办公室5 |
|---|---|---|---|---|---|
| A | 5 | 4 | 3 | 2 | 1 |
| B | 4 | 5 | 2 | 3 | 1 |
| C | 3 | 2 | 5 | 4 | 1 |
| D | 2 | 3 | 4 | 5 | 1 |
| E | 1 | 1 | 3 | 4 | 5 |
问：如何分配部门到办公室，使得总满意度最高？
解题步骤
建立模型：
- 设部门i分配到办公室j的满意度为 ( c_{ij} )。
- 目标函数：最大化总满意度 ( Z = \sum{i=1}^{5} \sum{j=1}^{5} c{ij} x{ij} )。
- 约束条件： [ \begin{cases} \sum{j=1}^{5} x{ij} = 1 & \text{（i=1,2,3,4,5）} \ \sum{i=1}^{5} x{ij} = 1 & \text{（j=1,2,3,4,5）} \ x_{ij} \in {0,1} & \text{（i,j=1,2,3,4,5）} \end{cases} ]
求解过程：
- 使用匈牙利算法求解指派问题。
- 根据匈牙利算法，得到最优解。
答案解析：
- 部门A分配到办公室1，部门B分配到办公室2，部门C分配到办公室3，部门D分配到办公室4，部门E分配到办公室5。
- 总满意度为 ( Z = 5 + 5 + 5 + 5 + 5 = 25 )。