《最优化方法》参考答案及评分标准
1. 某文教用品厂用原材料白坯纸生产原稿纸、日记本和练习本三种产品。该厂现有工人100人，每月白坯纸供应量为30 000 kg.已知工人的劳动生产率为：每人每月可生产原稿纸30捆，或生产日记本30打，或练习本30箱。已知原材料消耗为：每捆原稿纸用白坯纸3日记本用白坯纸13kg,每箱练习本用白坯纸261kg,每打3132kg.又知每生产一捆原稿纸可获利2元，生3产一打日记本获利3元，生产一箱练习本获利1元。 试确定：
(a)现有生产条件下获利最大的方案；
(b)如白坯纸的供应数量不变，当工人数不足时可招收临时工，临时工工资支出为每人每月40元，则该厂要不要招收临时工，招多少临时工最合适？ 解：
（a）分别用x1,x2,x3代表原稿纸、日记本和练习本的每月生产量。 建立线性规划模型
(2分) (4分)
max2x1?3x2?x3??x/30?x/30?x/30?10023?1 4080?10x?x?x?30000?313233?x1,x2,x3?0?求解得最终单纯形表如表所示。 （9分） x1 0 1 0 x2 1 0 0 x3 7/3 -4/3 -10/3 x4 1/10 -1/10 -1/10 x5 -10 40 -50 x2 2000 x1 1000 cj?zj （b）临时工影子价格高于市场价格，故应招收。用参数规划计算确定招200人为最适宜。 （5分）
2. 求解下列产销平衡的运输问题，表中列出的为产地到销地之间的运价。 (1)用左上角法、最小元素法、沃格尔法求初始基本可行解。
(2)由上面所得的初始方案出发，应用表上作业法求最优方案，并比较初始方案需要的迭代次数。 产 销 地 地 B1 3 1 7 3 B2 11 9 4 6 B3 3 2 10 5 B4 12 8 5 6 产量 7 4 9 20 1 2 3 销量 解：
(1)西北角法：运费为z?135。 产 销 地 地 (5分) 产量 7 4 9 20 (5分) 产量 7 4 9 20 (5分) 产量 7 4 9 20 (5分) 产量 7 4 9 20 B1 3 3 B2 4 2 6 B3 2 3 5 B4 6 6 1 2 3 销量 最小元素法：运费为Z?92。 销 地 B1 产 地 B2 6 6 B3 4 1 5 B4 3 3 6 1 2 3 销量 3 3 沃格尔法：运费Z?85。 销 地 B1 产 地 B2 6 6 B3 5 5 B4 3 3 6 1 2 3 销量 销 地 2 1 3 (2)最优调运方案：最少运费Z?85。 产 地 B1 2 1 3 B2 6 6 B3 5 5 B4 3 3 6 1 2 3 销量 3. 用动态规划求解下面的问题
解：
（1）建立动态规划模型：
①阶段变量k=1,2,3。 ②状态变量sk表示第k阶段初各决策变量之积，则s3=27。 ③决策变量xk分别表示第k阶段的x的值 ④状态转移方程sk+1=sk/xk。 ⑤指标函数vk(sk,xk)表示第k阶段的总成本，即x1+x2+…+xk 由已知可得
(1分) (1分) (1分) (1分) (1分)
vk(sk,xk)?xk
(1分)
⑥基本方程为
{vk(sk,xk)?fk?1(sk?1)}??fk(sk)?0max?xk?6 ???f4(s4)?0
(2分) （12分）
（2）用动态规划的正向或反向推理算法求解可得：
?x1x2x3???333?minf(x)?9
评分标准：以上的推理过程，每一阶段的计算正确得3分（共3个阶段），其中，列写出
s或x的范围得1分，列写出决策表得1分，列写出最优决策表得1分，每出现一处错误，扣0.5分，至扣完本项分值为止。最终结果得3分，其中写出决策变量的值得2分，写出函数值得1分，每出现一处错误扣0.5分，至本项分值扣完为止。
4、分配甲、乙、丙、丁四个人去完成五项任务。每人完成各项任务时间如表所示。由于任务数多于人数，故规定其中有一个人可兼完成两项任务，其余三人每人完成一项。试确定总花费时间为最少的指派方案。 任务 人 甲 乙 丙 丁 A 25 39 34 24 B 29 38 27 42 C5 31 26 28 36 D 42 20 40 23 E 37 33 32 45 答案：加上假设的第五个人是戊,他完成各项工作时间取甲、乙、丙、丁中最小者，（3分） 构造表为 （10分） 任务 人 甲 乙 丙 丁 戊 A 25 39 37 24 24 B 29 38 27 42 27 C 31 26 28 36 26 D 42 20 40 23 20
E 37 33 32 45 32 (5分) (2分)
对表再用匈牙利法求解,得最优分配方案为甲-B,乙-B和C,丙-E,丁-A, 总计需要131h.
5. 试用变尺度法求解：
minf(X)?x14?(x2?1)2
按以下要求进行：
(a) X(b) X答： （a）
取最佳步长?0?1/2，
(4分)
(0)?(0,0)T，用最佳步长；
?(1,1)T，用固定步长??0.5，做一个循环。
(0)