线性规划的计算机求解 Excel 是分析和求解线性规划问题一个很好的工具，它不仅可以很方便地将线性规划模型所有的参数录入电子表格，而且可以利用规划求解工具迅速找到模型的解。最重要的是，在解好的模型中，任何参数的改变都可以立即反映到模型的解中，在不重新应用求解工具的情况下就可以知道许多信息，当然，即使重新求解也只是点一下鼠标就可以了 线性规划的计算机求解 作为office家族的一员，Excel的普及性和易学性也会让读者感到利用计算机求解线性规划十分容易。当然，除Excel外还有很多求解线性规划的计算机软件，但Excel强大的功能、普及性和易学性足以满足学习运筹学的读者理解线性规划的计算机求解方法、帮助读者们学习解决线性规划问题的要求。线性规划的计算机求解线性规划的计算机求解线性规划的计算机求解线性规划的计算机求解线性规划的计算机求解线性规划的计算机求解线性规划的计算机求解线性规划的计算机求解线性规划的计算机求解农场灌溉问题 某公司有四个农场，每个农场的耕地作物需要用水灌溉，因灌溉条件限制，农场的最大水资源供应量有一定限制，各农场的总耕地面积与最大水资源供应量如表3-1所示。该地区种植的作物有棉花、玉米和高粱，三种农作物每种作物每单位种植面积的净收入和耗水量以及每种作物最大允许种植面积如表3-2所示。由于水资源短，公司规定每个农场受灌溉面积占农场总耕地面积的比例相同，公司决策问题还是如何确定各农场种植各种作物的面积，使得公司总收入最大。例1. 农场灌溉问题例1. 农场灌溉问题 我们首先建立此问题的线性规划模型。由于此问题是决定四个农场中每个农场种植三种农作物的面积，我们引入决策变量xij（i = 1，2，3，4；j = 1，2，3）表示第i个农场种植第j种作物的面积，目标是使总收入 Z = 800( x11 + x21 + x31 + x41) + 600(x12 + x22 + x32 + x42 ) + 450(x13 + x23 + x33 + x43)最大化 例1. 农场灌溉问题 满足下列约束条件： 1). 农场的耕地面积约束x11 + x12 + x13 4000 (农场1)x21 + x22 + x23 6000 (农场2)x31 + x32 + x33 5000 (农场3)x41 + x42 + x43 4500 (农场4)例1. 农场灌溉问题 2). 农场最大供水量约束 2x11 + 1.5x12 + x13 6000 (农场1) 2x21 + 1.5x22 + x23 9000 (农场2) 2x31 + 1.5x32 + x33 5500 (农场3) 2x41 + 1.5x42 + x43 5000 (农场4)例1. 农场灌溉问题 3)农作物的种植面积约束x11 + x21 + x31 + x41 6000 （农作物1，棉花） x12 + x22 + x32 + x42 5500 （农作物2，玉米）x13 + x23 + x33 + x43 5000 （农作物3，高粱） 即各农作物种植面积不超过最大允许种植面积。 例1. 农场灌溉问题 4)种植作物面积占总耕地面积比例约束 即各农场种植作物面积（灌溉面积）占总耕地面积的比例相同。 5) 决策变量的非负约束xij 0， i = 1，2，3，4；j = 1，2，3。例1. 农场灌溉问题例2. 证券投资问题 一证券投资者将1000万元资金用于证券投资，已知各种证券（A、B、C、D、E、F）的评级、到期年限、每年税后收益如表所示。管理层对该投资者提出下列要求： 国债投资额不能少于300万元； 投资证券的平均评级不超过1.5； 投资证券的平均到期年限不超过5年。 问：每种证券投资多少可以使得税后收益最大？例2. 证券投资问题例2. 证券投资问题 引入决策变量xA、xB、xC、xD、xE、xF分别表示证券A、B、C、D、E、F的投资金额（单位：万元），相应的目标函数（税后收益）为： Z = 90.043xA + 120.044xB + 50.032xC + 40.03xD + 30.032xE + 40.045xF 约束条件为： 资金总额约束： xA + xB + xC + xD + xE + xF 1000 国债投资额约束： xC + xD 300例2. 证券投资问题证券平均评级约束： 这是一个非线性约束，容易转化为以下线性约束： 0.5xA + 0.5xB 0.5xC 0.5xD + 2.5xE + 3.5xF 0证券平均到期年限约束： 它等价于线性约束： 4xA + 7xB xD 2xE xF 0非负约束: xA 0，xB 0， xC 0， xD 0， xE 0 xF 0例2. 证券投资问题例3. 话务员排班问题 某寻呼公司雇用了多名话务员工作，他们每天工作3节，每节3小时，每节开始时间为午夜、凌晨3点钟、凌晨6点钟，上午9点、中午12点、下午3点、6点、9点，为方便话务员上下班，管理层安排每位话务员每天连续工作3节，根据调查，对于不同的时间，由于业务量不同，需要的话务员的人数也不相同，公司付的薪水也不相同，有关数据见表。例3. 话务员排班问题 问：如何安排话务员才能保证服务人数，又使总成本最低？例3. 话务员排班问题 解：这个问题实际上是一个成本效益平衡问题。管理层在向客户提供满意服务水平的同时要控制成本，因此必须寻找成本与效益的平衡。由于每节工作时间为3小时，一天被分为8班，每人连续工作3节，各班时间安排如下表：例3. 话务员排班问题例3. 话务员排班问题 为了建立数学模型，对应于一般成本效益平衡问题，我们首先必须明确包含的活动数目，活动一个单位是对应于分派一个话务员到该班次收，效益的水平对应于时段。收益水平就是该时段里上下班的话务员数目，各活动的单位效益贡献就是在该时间内增加的在岗位话务员数目。我们给出下列成本效益平衡问题参数表：例3. 话务员排班问题例3. 话务员排班问题 决策变量Xi表示分派到第班的话务员人数（i= 1，2，3，4，5，6，7，8），约束条件为： 0-3时间段： 3-6时间段： 6-9时间段： 9-12时间段： 12-15时间段： 例3. 话务员排班问题 15-18时间段： 18-21时间段： 21-0时间段： 非负约束： 目标函数为最小化成本： 例3. 话务员排班问题例4.多阶段生产安排问题 南方机电制造公司为全国各地生产一种大型机电设备，按照公司的订单合同，不久要交付使用一定数量的机电设备，所以有必要制定为期6个月的设备生产计划。根据合同，公司必须在未来6个月中每个月底交付一定数量的机电设备，由于原料价格、生产条件、保修和维修工作等安排不同，每月的生产能力和生产成本也不同，当然，可以在成本较低的月份多生产一些设备，但在供给客户之前必须存放，需要付一定的存贮费用。管理层需要制定出一个逐月生产计划，使生产和存贮的总成本达到最小。例4.多阶段生产安排问题 管理科学小组通过调查收集到每单位生产成本、每月单位存贮费、每月需求量、最大生产能力等数据（见表)。例4.多阶段生产安排问题 解：管理层需要作出的决策是每个月生产多少台设备，因此我们引入决策变量 xj表示第个月生产机电设备的台数（j= 1，2，3，4，5，6）。为了建立此问题的一般数学模型，我们用dj表示第j月的需求量；用lj表示第j月的最大生产能力；用cj表示第j月的单位生产成本；用hj表示第j月的单位存贮成本；用fj表示第j月的最大存贮量。例4.多阶段生产安排问题 由最大生产能力限制，我们容易得到约束：xj lj , j= 1，2，3，4，5，6 用Ij表示第月底的库存量（j= 1，2，3，4，5，6），由最大存贮量约束，我们有：Ij fj , j= 1，2，3，4，5，6 各个月份之间生产量、需求量和存贮量之间的关系可由下图（图2-15）表示：例4.多阶段生产安排问题 容易得到下列约束：例4.多阶段生产安排问题 另外有非负约束： xj 0, Ij 0， j= 1，2，3，4，5，6 目标为总成本 最小化:例4.多阶段生产安排问题例5.下料问题 某工厂要做100套钢架，每套用长为2.9 m, 2.1m, 1.5m的圆钢各一根。已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？解:考虑下列各种下料方案（按一种逻辑顺序给出）把各种下料方案按剩余料头从小到大顺序列出假设 x1,x2,x3,x4,x5 分别为上面前 5 种方案下料的原材料根数。我们建立如下的数学模型。目标函数： Min z=x1 + x2 + x3 + x4 + x5 约束条件： s.t. x1 + 2x2 + x4 100 2x3 + 2x4 + x5 100 3x1 + x2 + 2x3+ 3x5 100 x1,x2,x3,x4,x5 0模型1假设 x1,x2,x3,x4,x5,x6,x7,x8 分别为上面前 8种方案下料的原材料根数。我们建立如下的数学模型。目标函数： Min z = 0.1x1+0.3x2+0.9x3+1.1x5+0.2x6+0.8x7+1.4x8 约束条件： s.t. 2x1+x2+x3+x4 100 2x2+x3 +3x5+2x6+ x7 100 x1 +x3+3x4 +2x6+3x7+4x8 100 x1,x2,x3,x4,x5,x6,x7,x8 0，整数模型2假设 x1,x2,x3,x4,x5,x6,x7,x8 分别为上面前 8种方案下料的原材料根数。我们建立如下的数学模型。目标函数： Min z = x1+x2+x3+x5+x6+x7+x8 约束条件： s.t. 2x1+x2+x3+x4 100 2x2+x3 +3x5+2x6+ x7 100 x1 +x3+3x4 +2x6+3x7+4x8 100 x1,x2,x3,x4,x5,x6,x7,x8 0，整数模型3例6医药公司的中草药配方问题 安康医药公司考虑配制一种中成药; 市场上有八种中草药材包含该中成药所需要的特定成份, 公司准备采购一些中草药来配制这种中成药，要求配制后的中成药所包含三种特定成份(不妨设为成份A、成份B和成份C)分别为39、36、38。由于每种中草药材包含的成份不同, 采购成本也不同; 公司管理层希望以最低的成本来完成中成药的配制; 各个中草药材(每单位)包含的三种成份含量及单位采购成本数学建模 决策变量Xi表示第种草药在中成药中的使用量（i= 1，2，3，4，5，6, 7, 8）。为了使成本最低我们有: 目标函数 Z=10 x1+8x2+16x3+11x4+15x5+10 x6+9x7+12x8 求极小化约束条件 2x1+5x2+5x3+4x4+5x5+4x6+3x7+7x8 =39 3x1+3x2+2x3+2x4+4x5+2x6+2x7+3x8 =36 4x1+3x2+3x3+3x4+4x5+3x6+x7+2x8 =38 Xi 0 , i=1,2,3.8.安康医药公司的中草药配方问题的Excel规划求解 讨论:为什么8种中草药,最优方案只选了三种呢?(草药1,草药2和草药7) 事实上, 由于这个问题只有三个函数约束(成份A、成份B和成份C), 三个等式约束看作一个线性方程组: 2x1+5x2+5x3+4x4+5x5+4x6+3x7+7x8 =39 3x1+3x2+2x3+2x4+4x5+2x6+2x7+3x8 =36 4x1+3x2+3x3+3x4+4x5+3x6+x7+2x8 =38讨论:为什么8种中草药,最优方案只选了三种呢? 若将第i种草药三种成份含量看作一个三维向量Pi则: 由线性代数知识我们知道向量组P1,P2,P7 线性无关且构成三维向量空间的一个极大无关组; 任何一个三维向量P可由 的线性组合来表示出来, 即: 存在唯一的一组数,k1,k2,k3, 使得: P=k1P1+k2P2+k3P3讨论 例如: 对于第5种草药三种成份含量, 可以表示为一个三维向量P5 ,讨论 这就意味着一个单位的第5种草药, 其成份等价于0.5个单位的第1种草药 + 0.5个单位的第2种草药 + 0.5个单位的第