图1-3 标准模型输入形式 附录： 线性规划常用术词汇及其含义
常用术语 含义 常用术语 含义 Alternative Solution Exists 有多重解 Basic and Nonbasic Variable 基变量和非基变量 Basis 基 Basis Status 基变量状态 Branch-and-Bound Mrthod 分支定界法 Cj-Zj 检验数 Combined Report 组合报告 Constraint Summary 约束条件摘要 Constraint 约束条件 Constraint Direction 约束方向 Constraint Status 约束状态 决策变量 Decision Variable 对偶问题 Dual Problem 入基变量 Entering Variable 可行域 Feasible Area 可行解 Feasible Solution 不可行 Infeasible 不可行分析 Infeasibility Analysis 出基变量 Leaving Variable 左端 Left-hand side 上界或下界 Lower or Upper Bound 最优解不变时，价Minimum and Maximum 值系数允许变化范Allowable Cj 围 Minimum and 最优基不变时，资源限Maximum Allowable 量允许变化范围 RHS 右端系数 Objective Function 目标函数 Optimal Solution 最优解 Parametric Analysis 参数分析 Range and Slope of 参数分析的区间和斜Parametric Analysis 率 Reduced Cost 约简成本（价值） Range of Feasibility 可行区间 Range of Optimality 最优区间 Relaxed Problem 松弛问题 Relaxed Optimum 松弛最优 Right-hand Side 右端常数 Sensitivity Analysis of 目标函数的灵敏度分OBJ Coefficients 析 Sensitivity Analysis of 右端常数的灵敏度分Right-Hand-sides 析 Shadow Price 影子价格 Simplex Method 单纯形法 Slack, Surplus or 松弛变量、剩余变量或Artificial Variable 人工变量 Solution Summary 最优解摘要 Subtract(Add) More 减少（增加）约束系数 Than This From A(i,j) 总体贡献 Total Contribution 无界解 Unbounded Solution
11
实验1作业
（1）某昼夜服务公共交通系统每天各时间段（每4小时为一个时间段）所需的值班人员如下表所示。这些值班人员在某时段上班后要连续工作8个小时（包括轮流用膳时间在内）。问该公交系统至少需多少名工作人员才能满足值班的需要。
（2）（任务分配问题）某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为800和900，三种工件的数量分别为400、600和500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？
单位工件所需加工台时数 车床 类 型 工件1 工件2 工件3 0.4 1.1 1.0 甲 乙 0.5 1.2 1.3 单位工件的加工费用 工件1 13 11 工件2 9 12 工件3 10 8 可用台时数 800 900 （3）（厂址选择问题）考虑A、B、C三地，每地都出产一定数量的原料，也消耗一定数量的产品（见表9-15）。已知制成每吨产品需3吨原料，各地之间的距离为：A-B：150km，A-C：100km，B-C：200km。假定每万吨原料运输1km的运价是5000元，每万吨产品运输1km的运价是6000元。由于地区条件的差异，在不同地点设厂的生产费用也不同。问究竟在哪些地方设厂，规模多大，才能使总费用最小？另外，由于其它条件限制，在B处建厂的规模（生产的产品数量）不能超过5万吨。 A、B、C三地出产原料、消耗产品情况表 地点 A B C 作业要求：
（1）建立问题模型、输入选项(电子表格、变量取非负连续)、输入数据、存盘、求解模型、结果存盘、观察结果。
（2）将所有变量取非负整数、求解、观察结果、存盘、打印窗口、打印结果。 (3) 将电子表格格式转换成标准模型。 （4）分析结果。
（5）将结果复制到Excel或Word文档中。
12
年产原料（万吨） 20 16 24 年销产品（万吨） 7 13 0 生产费用（万元/万吨） 150 120 100
实验2：对偶线性规划的WinQSB应用
（一）实验目的：掌握winQSB软件写对偶规划，灵敏度分析和参数分析的操作方法
（二）内容和要求：建立线性规划的对偶问题，求解模型，进行灵敏度分析和参数分析。
（三）操作步骤：
下面结合例题介绍WinQSB软件求解对偶线性规划的操作步骤及应用。
例2：已知线性规划
maxZ?x1?2x2?4x3?x4
?3x1?9x3?5x4?15?6x?4x?x?7x?301234??s.t.?4x2?3x3?4x4?20 ?5x?x?8x?3x?4034?12??xj?0,j?1,2,3,4（1） 写出对偶线性规划，变量用y表示； （2） 求原问题及对偶问题的最优解；
（3） 分别写出价值系数cj及右端常数的最大允许变化范围；
（4） 目标函数系数改为C?(4,2,6,1)，同时常数改为b?(20,40,20,40)，求最优解； （5） 删除第四个约束同时删除第三个变量，求最优解；
（6） 增加一个变量x5，系数为(c5,a15,a25,a35,a45)?(6,5,4,2,3)，求最优解。 解：启动线性规划与整数规划（Linear and Integer Programming），建立新问题，取名为dual1（可任意取名），输入数据得到表2-1，存盘。
表2-1
（1）点击Format→Switch to Dual Form，得到对偶问题的数据表，点击Format→Switch to Normal Model Form，得到对偶模型，点击Edit→Variable Name，分别修改变量名，得到以为变量名的对偶模型，如图2-1所示。
13
图2-1
（2）再求一次对偶返回到原问题，求解显示结果如表2-2，此时最优解为
X?(2,4.25,1,0)T，最优值Z?145。表中影子价格(Shadow Price)对应列的数据就是对偶
问题的最优解为Y?(0.2833.0.025,0.475,0)。
表2-2 最优解详细综合分析报告
（3）由表2-2最后两列可知：
价值系数cj(j?1,2,3,4)最大允许变化范围分别是
[0.8333,4.1667]，[1.333,5.7778]，[1.1667,4.5]，(??,3.4917]；
右端常数bi(i?1,2,3,4)的最大允许变化范围分别是
[5,27.4719]，[16.6667,50]，[0，33.3333]，[30.75,??)。
（4）直接修改表2-1的数据，求解后得到最优解为X?(3.6667,4.25,1,0)T，最优值
Z?29.1667。
（5）将数据修改回原问题，点击Edit→Delete a Constraint，选择要删除的约束C4，ok。点击Edit→Delete a Variable，选择要删除的变量X3，ok。得到如表2-3的模型，求解得到最优
T解为X?(1.6667,5,0)，最优值Z?11.6667。
表2-3
14
（6）调用原问题数据表，点击Edit→Insert a Variable，选择变量名和变量插入的位置，如图2-2，在显示的电子表格中输入数据(6,5,4,2,3)，得到最优解为X?(0,3.5,0,0,3)T，最优值
Z?25。
图2-2
实验2作业
（1）公司打算在三个工厂生产两种新产品，有数据如下：
生产每个单位产品所需时间 工厂1 工厂2 工厂3 单位利润（美元） 门 1小时 0 3小时 300 窗 0 2小时 2小时 500 每周可得时间 4小时 12小时 18小时 求得的最优解是：每周生产门2个，窗6个，总利润为3600美元。
对于研究者提出这个方案，管理层通过讨论后，提出以下问题：
（1） 如果新产品中，有一个产品的单位利润估计值不准确，将会发生怎样的情况？比如：现在估计门的价格单位利润是每个300美元，问，该价格可以在多大程度上偏离实际值，而最优解不变？
（2） 如果两种产品的单位利润都估计不准确呢？
（3） 如果某个工厂的可用时间发生变化，将会对结果产生什么影响？ （4） 如果三个工厂的可用时间都发生变化呢？ 请同学简述一下分析思路。
（2）利博公司的广告组合问题
15