第七节线性规划典型例题及应用
第三节中已讨论过应用线性规划解决经济、管理领域的实际问题时的建模型过程。本节讨论述经济、管理领域中的一些典型问题的建模分析，并利用软件WinQSB对线性规划模型进行求解。
1.7.1生产组织与计划问题
该类问题的一般提法是：用若干种资源
，生产若干产品，资源供应有一定限制，要求制定一个产品生产计划，使其在资源限制条件下，得到最大效益。此类问题的已知条件可用表1-13。
表1-13
|
所需要资源 资源 |
| 可供资源 |
|
|
|
|
| 单位产品利润 |
|
设为生产产品的计划数，则可列出这类问题的数学模型如下：
例1.1就属于这一类问题。
【例1.9】某工厂生产A、B两种产品，都需要经过前、后两道工序。单位产品需要的时间和利润，以及可供使用的总时间如表1-14。每生产一个单位产品B的同时，会产生2个单位的副产品C，且不需外加任何费用。副产品C的一部分可以出售盈利，其余的只能加以销毁。副产品C每卖出一个单位可获利3元，但是如果卖不出去，则每单位需销毁费用2元。预测表明，最多可售出5个单位的副产品C。要求确定使利润最大的生产计划。
表1-14
| A | B | 可利用的时间 | |
| 第1道工序 第1道工序 | 2 3 | 3 4 | 16 24 |
| 单位利润 | 4 | 10 |
分析：本题与例1.1区别在于产品B的副产品C，副产品C的利润和产量不是线性关系，为了建立线性规划，将产品C的产量分为两个部分：销售量和报废量。因此可设产品A的计划产量为，产品B的计划产量为，产品C的销售量为，产品C的报废量为。根据各产品的单价可写出利润函数，根据资源的约束及各变量之间的关系，可写出约束条件，所以可得如下线性规划模型
现使用WinQSB求解上述模型。
WinQSB软件求解LP不必化为标准型，对于有界变量及无约束变量可以不转化，只需修改系统变量类型即可，对于不等式约束可以在输入数据时直接输入不等式，如符号，输入>、=>及>=任何一种都是等价的。本例中，变量数为4，约束条件为3，第4、5个约束条件由系统自动生成。
(1)启动线性规划程序。点击开始程序WinQSBLinear and Interger Programming，屏幕显示如图(1-7)所示的线性规划和整数规划的工作界面。
图1-7 线性规划和整数规划的工作界面
工作界面的最上面一行是程序名，第二行是菜单栏，第三行是工具格式栏，中间部分为工作区，最下面一行是信息栏。菜单栏、工具栏和格式栏随主窗口内容变化而变化，图1-8为刚进入程序的界面，工具栏的第一个图标为建立新问题工具，第二个图标为打开已有的文件工具，第三个图标为退出工具。
(2)建立新问题或打开磁盘中已有的文件。按图1-8所示操作建立或打开一个线性规划问题，或点击FileNew Problem建立新问题。点击FileLoad Problem打开磁盘中的数据文件PL程序自带后缀为“LPP”的3个典型例题，供学习参考，在你求解一个线性规划之前可以先打开例题，了解一下求解LP的工作界面布局。点击FileNew Problem，出现如图1-8所示的问题选项输入界面。
图1-8新问题建立界面
(3)输入数据。在选择数据输入格式时，选择Spreadsheet Matrix Form则以电子表格形式输入变量系数矩阵和右端常数矩阵，是固定格式，如图1-9所示。选择Normal Model Form则以自由格式输入标准模型，如图1-10所示。
图1-9电子表格数据输入格式
图1-10 自由格式输入标准
(4)修改变量类型。如图1-8中给出了非负连续(Nonnegative continuous)、非负整数(Nonnegative integer)、0-1型(Binary[0，1])和无符号或无约束(Unsigned/unrestricted)4种变量类型选项，当选择了某一种类型后系统默认所有变量都属该种类型。在本例中，四个决策变量都为非负连续型。另外，对第四个约束条件，直接将列中的上界(Lower Bound)由M改为5。如图1-9和图1-10所示。
图1-11 变量类型及上下界、约束条件符号修改及部分工具示意
(5)修改变量名和约束条件名。系统默认变量名为，约束条件名为。如果你对默认名不满意可以进行修改，点击菜单栏Edit后，下拉菜单有四个修改选项：修改标题名(Problem Name)、变量名(VariableName)、约束名(Constraint Name)和目标函数准则(或)。WinQSB支持中文，可以输入中文名称。
(6)求解模型时可直接点击工具栏的工具图标(图1-11)，还可以点击菜单栏Solve andAnalyze，下拉菜单有三个选项：求解不显示迭代过程(Solve the Problem)、求解并显示单纯形法迭代步骤(Solveand Display Steps)及图解法(Graphic Method，限两个决策变量)。如果选择Solve the Problem，系统直接显示求解的综合报告如图1-12所示，表中的各项含义如表1-15所示。LP有最优解或无最优解(无可行解或无界解)，系统会给出提示。如果选择Solve and Display Steps，系统会逐步显示迭代步骤，每点击Simplex Iteration下拉菜单的NextInteration，系统会给出一次迭代结果，直至最优解出现，如图1-13所示。
图1-12 最优解综合报告表
图1-13 迭代结果表
由图1-12和图1-13可知，本例的最优解，最优值=49，即产品A的计划产量为2.25，产品B的计划产量为2.5，副产品C产量为5时，该工厂可获得最大利润49。另外，由图1-13第6行提示Alternate Solution exists可知，本例题有多重解。
表1-15 LP常用术语词汇含义
| 常用术语 | 含义 |
| Alternative Solution exists Basic and Nonbasic Variable Basis Basis Status Branch-and-Bound Method Cj-Zj Combined Report Constraint Summary Constraint Constraint Dierction 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 Maximun Allowable Cj Minimum and Maximun Allowable RHS Objective Function Optimal Solution Optimal 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 Form A(i，j) Total Contribution Unbounded Solution | 存在替代解，有多重解 基变量和非基变量 基 基变量状态，提示是否为基变量 分支定界法 检验数 组合报告 约束条件摘要 约束条件 约束方向 约束状态 决策变量 对偶问题 入基(进基)变量 可行域 可行解 不可行 不可行性分析 出基变量 左端 下界或上界 最优解不变时，价值系数允许变化范围 最优基不变时，资源限量允许变化范围 目标函数 最优解 参数分析 参数分析的区间和斜率 约简成本(价值)，检验数，即当非基变量增加一个单位时目标函数的改变量 可行区间 最优区间 松弛问题 松弛最优 右端常数 目标函数系数的灵敏度分析 右端常数的灵敏度分析 影子价格 单纯形法 松弛变量、剩余变量或人工变量 最优解摘要 减少(增加)约束系数，调整工艺系数 总体贡献，目标函数 无界解 |
1.7.2合理配料问题
这类问题的一般提法是：由多种原料制成含有种成分的产品，已知产品中所含各种成分的最低需要量及各种原料的单价，并且知道各种原料的数量，问应如何配料，才能使产品的成本最低或利润最大。
【例1.10】某糖果厂要用三种原材料A、B、C混合调配出三种不同规格的糖果甲、乙、丙。已知糖果的规格要求、单位加工费、单价，每天能供应的原材料数量及原材料单价，见表1-16。该厂应如何安排生产，使利润收入为最大?
表1-16
| 甲 | 乙 | 丙 | 原材料成本(元/kg) | 原材料数量(kg) | |
| A B C | ≥60%
≤20% | ≥30%
≤50% |
≤60% | 2.0 1.5 1.0 | 2000 2500 1200 |
| 加工费(元/kg) 售价(元/kg) | 0.5 3.4 | 0.4 2.85 | 0.3 2.25 |
分析：用分别代表原材料A、B、C，用分别代表糖果甲、乙、丙，设表示三种糖果的计划产量，表示生产第种糖果中原材料的成分(重量)，则有
(1-19)
该糖果厂的利润函数为
三种糖果的产量受原材料供应和原料含量成份两类限制。
下列不等式可表示原材料供应限制。
下列不等式可表示成份限制。
(1-20)
将(1-19)中各式代入(1-20)可得：
由以上分析，可得以下数学模型：
利用WinQSB软件求解综合报告见图1-14。
图1-14例1.10的求解结果综合报告表
由图1-14可以看出，模型有多重最优解，其中一个最优解为
最优目标函数值=5450。
即糖果甲的生产量为966.67kg，糖果乙的生产量为4733.33kg，糖果丙的生产量为0kg，按这样的方案安排生产，可使利润达到最大值5450元。
1.7.3套裁下料问题
这类问题一般提法是：在加工业中，需要将某类规格的棒材或板材裁成不同规格的毛坯，对裁出毛坯有一定的数量要求。问如何裁取，既满足对裁出毛坯的数量要求，又使所使用的原材料最少。
解决这类问题一般有以下步骤：
(1)按照思路列出所有的排料方案，当方案很多而无法一一排出时，可以先确定一些筛选原则，然后把明显不合理的方案删除。
(2)设表示按第种方案下料的原材料数量，按照问题建立相关的线性规划模型。
【例1.11】某工厂计划做100套钢架，需要用长分别为2.9、2.1和1.5的圆钢各一根。已知可做原料使用的圆钢每根长7.4，问应如何下料才能使所用原料最省？
分析：最简单的下料方法是，每根圆钢截取2.9、2.1和1.5的长度各一根，组成一套，这样每根圆钢剩下料头0.9。完成任务后，共消耗圆钢100根，余下的料头共90，根据经验，这肯定不是最好的办法，若改成套裁一定会更好。所谓更好即第一要求是所有的方案配合起来能满足完成任务的需要，第一要求是所用原料最少。为此，先列出所有的下料方案，见表1-17。
表1-17
| 方案1 | 方案2 | 方案3 | 方案4 | 方案5 | 方案6 | 方案7 | 方案8 | |
| 2.9 | 2 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 2.1 | 0 | 2 | 1 | 0 | 3 | 2 | 1 | 0 |
| 1.5 | 1 | 0 | 1 | 3 | 0 | 2 | 3 | 4 |
| 料头 | 0.1 | 0.3 | 0.9 | 0 | 1.1 | 0.2 | 0.8 | 1.4 |
设表示按第种方案下料的原材料数量，所用原材料总数为，根据题意，可列数学模型如下：
利用WinQSB软件求解综合报告见图1-15。
图1-15 例 1.11的求解结果综合报告表
由图1-15可以看出，模型有多重最优解，其中一个最优解为：
最优目标函数值：=90
即按第一方案裁料10根原材料，按第二方案裁料50根原材料，按第四方案裁料30根原材料，可以使所用原材料最小，最小用量为90根。
1.7.4人力资源配置问题
该问题的一般提法是：一项工作根据其特点在不同的时间段，采用不同的工作人员。问如何安排工作人员的作息，既满足工作需要，又使配备人员的数量最小。
【例1.12】某商场决定：营业员每周连续工作5天后连续休息2天，轮流休息。根据统计，商场每天需要的营业员如表1-18所示。商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少。
表1-18
| 星期 | 一 | 二 | 三 | 四 | 五 | 六 | 日 |
| 需要人数 | 300 | 300 | 350 | 400 | 480 | 600 | 550 |
分析：设为休息两天后星期开始上班的人数，星期日记为，则每一天可以工作的人数应为当前日算起往前五天开始工作的人数，往前第六天和第七天开始工作的人现在正在休息，如星期一可以工作的人应该是星期一(当天)、星期日、上星期六、上星期五、上星期四开始工作的人，上星期三和上星期二开始工作的人本星期一正在休息。于是，根据资料可建立如下的线性规划模型：
利用WinQSB软件求解所得综合报告见图1-16。
图1-16 例1.12的求解结果综合报告表
从图1-16可知，最优的安排方案如下：
表1-19
| 星期 | 一 | 二 | 三 | 四 | 五 | 六 | 日 |
| 当天开始工作的人数 | 0 | 67 | 146 | 170 | 97 | 120 | 17 |
| 当天可以工作的人数 | 404 | 301 | 350 | 400 | 480 | 600 | 550 |
| 当天休息的人数 | 213 | 316 | 267 | 217 | 137 | 17 | 67 |
| 总人数 | 617 | ||||||
1.7.5连续投资问题
该问题的一般提法是：将某一固定的时间分为几个时间段，在这些时间段内对某一项目进行投资，投资的数额、回报率和回收时间都不一样，问如果利用有限的总投资数额在固定的时期内进行投资，使资金总额在期末达到最大值。
【例1.13】某部门在今后五年内考虑给下列项目投资，已知：
项目A，从第一年到第四年每年年初需要投资，并于次年末回收本利115%；
项目B，第三年初需要投资，到第五年末能回收本利125%，但规定最大投资额不超过4万元；
项目C，第二年初需要投资，到第五年末能回收本利140%，但规定最大投资额不超过3万元；
项目D，五年内每年初可购买公债，于当年末归还，并加利息6%。
该部门现有资金10万元，问它应如何确定给这些项目每年的投资额，使到第五年末拥有的资金的本利总额为最大?
分析：(1)确定变量。设，，，()分别表示第年年初给项目A，B，C，D的投资额。根据给定的条件，将变量列于表1-20中。
表1-20
| 项目 | 第一年 | 第二年 | 第三年 | 第四年 | 第五年 |
|
|
|
|
|
| |
|
|
| ||||
|
|
| ||||
|
|
|
|
|
|
|
(2)投资额应等于手中拥有的资金额
由于项目D每年都可以投资，并且当年末即能回收本息。所以该部门每年应把资金全部投出去，手中不应当有剩余的呆滞资金。因此，
第一年：该部门年初拥有100000元，所以有：
+=100000
第二年：因第一年给项目A的投资要到第二年末才能回收。所以该部门在第二年初拥有资金额仅为项目D在第一年回收的本息(1+6%)。于是第二年的投资分配是：
++=1.06
第三年：第三年初的资金额是从项目A第一年投资及项目D第二年投资中回收的本利总和：(1+15%)及(1+6%)。于是第三年的资金分配为：
++=1.15+1.06
第四年：同以上分析，可得
+=1.15+1.06
第五年：
=1.15+1.06
此外，由于对项目B、C的投资有限额的规定，即：
≤40000
≤30000
(3)目标函数
问题是要求在第五年末该部门手中拥有的资金额达到最大，这个目标函数可表示为：
=1.15+1.40+1.25+1.06
(4)数学模型
经过以上分析，这个与时间有关的投资问题可以用以下线性规划模型来描述：
(5)利用WinQSB软件求解所得最终迭代表如图1-17。
图1-17
从图中可知，模型的最优解为：
=34782.61，=65217.39，=39130.43，=30000.00，=0，=0，=40000.00，=0，=45000.00，=0，=0
最优目标函数值=143750.00
即最优投资方案为：
第一年：投资A项目34782.61元，投资D项目65217.39元，其它项目不投资；
第二年：投资A项目39130.43元，投资C项目30000.00，其它项目不投资；
第三年：投资B项目40000.00元，其它项目不投资；
第四年：投资A项目45000.00元，其它项目不投资；
第五年：不投资。
到第五年末该部门拥有资金总额为143750元，即盈利43.75%。
