线性规划问题
一．实验课题
某牧场饲养一批动物，平均每头动物需要700g蛋白质，30g矿物质和100g维生素。现有五种饲料可供选择，每千克饲料的营养成分（单位：g）与价格（单位：元/kg）如下表所示：
试求能满足动物生长营养需求又最经济的选饲料方案。
二. 实验内容
1. 单纯形法求解
下面建立描述这一问题的数学模型。利用单纯形法和Matlab的优化工具箱求解。
设x1,x2,x3,x4和x5分别表示这五种饲料的用量（x1,x2,x3,x4和x5是决策变量）。
显然，我们的目标是在不小于所需求量的条件下，如何确定五种饲料x1,x2,x3,x4,x5的用量以使所用的资金最少。用Z表示所用的总的资金，那么，这样，该规划问题可用数学模型表示为：
Z=0.4*x1+1.4*x2+0.8*x3+1.6*x4+1.6*x5
目标函数
Min Z= 0.4*x1+1.4*x2+0.8*x3+1.6*x4+1.6*x5
约束条件
0.003*x1+0.002*x2+0.001*x3+0.006*x4+0.0125*x5>=0.7
0.001*x1+0.0005*x2+0.0002*x3+0.002*x4+0.0005*x5>=0.03
0.0005*x1+0.001*x2+0.0012*x3+0.002*x4+0.0008*x5>=0.1
x1>=0,x2>=0,x3>=0,x4>=0,x5>=0
这是一个含5个变量的线性规划模型，它是求一个线性函数在非负自变量受到线性不等式约束时的极值问题，所求极值问题的解即为线性规划的最优解。
由于上述数学模型不是线性规划的标准型，因此需要把它化为标准型，其标准型为：目标函数
Max Z=-0.4*x1-1.4*x2-0.8*x3-1.6*x4-1.6*x5+0*x6+0*x7+0*x8 约束条件
0.003*x1+0.002*x2+0.001*x3+0.006*x4+0.0125*x5-x6=0.7
0.001*x1+0.0005*x2+0.0002*x3+0.002*x4+0.0005*x5-x7=0.03
0.0005*x1+0.001*x2+0.0012*x3+0.002*x4+0.0008*x5-x8=0.1
X k>=0,k=1,2,3,4,5,6,7,8
在标准型下，其约束条件的系数矩阵为
A=
0.003 0.002 0.001 0.006 0.012 -1 0 0 0.001 0.0005 0.0002 0.002 0.0005 0 -1 0 0.0005 0.001 0.0012 0.002 0.0008 0 0 -1
=(p1 p2 p3 p4 p5 p6 p7 p8)
可见，x6,x7,x8的系数列向量
p6=(-1 0 0)’ p7=(0 -1 0)’ p8=(0 0 -1)’
为矩阵A的列向量的一个极大线性无关组，是基向量，相应的变量x6,x7,x8是基量，
而其余的变量x1,x2,x3,x4,x5成为非基变量。从标准型可得
X6=0.003*x1+0.002*x2+0.001*x3+0.006*x4+0.0125*x5-0.7
X7=0.001*x1+0.0005*x2+0.0002*x3+0.002*x4+0.0005*x5-0.03 （1）
X8=0.0005*x1+0.001*x2+0.0012*x3+0.002*x4+0.0008*x5-0.1 将（1）代入目标函数有
Z=-0.4*x1-1.4*x2-0.8*x3-1.6*x4-1.6*x5 (2) 在（1）式中令非基变量x1=x2=x3=x4=x5=0,就得Z=0,
X=(0,0,0,0,0,-0.7,-0.03,-0.1)’。
这个解表明：牧场没有选用饲料x1,x2,x3,x4,x5,所以消耗的资金Z=0。分析目
标函数的表达式（2）可知：非基变量的系数都是负数，而根据实际情况应当选
用它们中的一部分，所以就需要将非基变量与基变量进行对换。确定x5为换入
变量，x6为换出变量，则（1）变成：
X5=56+80*x6-0.24*x1-0.16*x2-0.08*x3-0.48*x4
X7=-0.002+0.00088x1+0.00492*x2+0.00199*x3+0.00176*x4+0.04*x6 (3)
X8=-0.0552+0.000308*x1+0.000872*x2+0.001136*x3+0.001616*x4+0.064*x6 将（3）代入目标函数Z=-89.6-0.784*x1-1.656*x2-0.928*x3-20368*x4-128*x6
令非基变量x1=x2=x3=x4=x6=0,得
Z=-89.6
而此时基变量x7=-0.002,x8=-0.0552,均小于0，不满足约束条件，因此，该组解
不是一组可行解。
再确定x1为换入变量，x8为换出变量，则（3）变成：
X5=0.512*x2+0.808*x3+0.768*x4+1290872*x6-779.232*x8+12.992
X7=0.0025*x2-0.0013*x3-0.0028*x4-0.1429*x6+2.8572*x8+0.1557 (4)
X1=-2.8*x2-3.7*x3-5.2*x4-207.8*x6+3246.8*x8+179.2
将（4）代入目标函数有：
Z=-1.0992*x2-0.6128*x3-0.7488*x4-124.6752*x6-51.9488*x8-92.4672
其中所有的非基变量x2,x3,x4,x6,x8前面的系数都是负的，这说明只有
x2=x3=x4=x6=x8=0时，目标函数达到最大值。即当A种饲料选用179.2g,E种饲
料选用12.992g时，所消耗的资金最少。由此便得到了该线性规划问题的最优
解。
2. Matlab优化工具箱求解
将上述数学模型化为可以使用linprog命令的如下形式：
目标函数
Min Z= 0.4*x1+1.4*x2+0.8*x3+1.6*x4+1.6*x5
约束条件
-0.003*x1-0.002*x2-0.001*x3-0.006*x4-0.012*x5<=-0.7
-0.001*x1-0.0005*x2-0.0002*x3-0.002*x4-0.0005*x5<=-0.03 -0.0005*x1-0.001*x2-0.0012*x3-0.002*x4-0.0008*x5<=-0.1 在命令窗口键入命令：
c=[0.4,1.4,0.8,1.6,1.6];
a=[-0.003 -0.002 -0.001 -0.006 -0.012;...
-0.001 -0.0005 -0.0002 -0.002 -0.0005;...
-0.0005 -0.001 -0.0012 -0.002 -0.0008];
b=[-0.7 -0.03 -0.1];
x=linprog(c,a,b,[],[],zeros(1,2,3,4,5)),z=c*x
运行后得到如下结果：
x =
195.1016
0.0000
0.0000
0.0000
9.5579
z =
93.3333
由上可以看出，利用两种方法求得的解几乎是一致的，都是解决线性规划问题的有效方法，但更加方便，更加快捷的方法是使用Matlab优化工具箱
第五章线性规划在管理中的应用 某企业停止了生产一些已经不再获利的产品，这样就产生了一部分剩余生产力。管理层考虑将这些剩余生产力用于新产品Ⅰ、Ⅱ、Ⅲ的生产。可用的机器设备是限制新产品产量的主要因素，具体数据如下表： 司的利润最大化。 1、判别问题的线性规划数学模型类型。 2、描述该问题要作出决策的目标、决策的限制条件以及决策的总绩效测度。 3、建立该问题的线性规划数学模型。 4、用线性规划求解模型进行求解。 5、对求得的结果进行灵敏度分析（分别对最优解、最优值、相差值、松驰/剩余量、对偶价格、目标函数变量系数和常数项的变化范围进行详细分析）。 6、若销售部门表示，新产品Ⅰ、Ⅱ生产多少就能销售多少，而产品Ⅲ最少销售18件，请重新完成本题的1-5。 解： 1、本问题是资源分配型的线性规划数学模型。 2、该问题的决策目标是公司总的利润最大化，总利润为： + + 决策的限制条件： 8x1+ 4x2+ 6x3≤500 铣床限制条件 4x1+ 3x2≤350 车床限制条件 3x1+ x3≤150 磨床限制条件 即总绩效测试（目标函数）为： max z= + + 3、本问题的线性规划数学模型 max z= + + S．T．8x1+ 4x2+ 6x3≤500 4x1+ 3x2≤350 3x1+ x3≤150 x1≥0、x2≥0、x3≥0 4、用Excel线性规划求解模板求解结果：最优解（50，25，0），最优值：30元。 5、灵敏度分析
目标函数最优值为: 30 变量最优解相差值 x1 50 0 x2 25 0 x3 0 .083 约束松弛/剩余变量对偶价格 1 0 .05 2 75 0 3 0 .033 目标函数系数范围: 变量下限当前值上限 x1 .4 .5 无上限 x2 .1 .2 .25 x3 无下限.25 .333 常数项数范围: 约束下限当前值上限 1 400 500 600 2 275 350 无上限 3 150 （1）最优生产方案： 新产品Ⅰ生产50件、新产品Ⅱ生产25件、新产品Ⅲ不安排。最大利润值为30元。 （2）x3 的相差值是意味着，目前新产品Ⅲ不安排生产，是因为新产品Ⅲ的利润太低，若要使新产品Ⅲ值得生产，需要将当前新产品Ⅲ利润元/件，提高到元/件。 （3）三个约束的松弛/剩余变量0，75，0，表明铣床和磨床的可用工时已经用完，而车床的可用工时还剩余75个工时； 三个对偶价格，0，表明三种机床每增加一个工时可使公司增加的总利润额。 （4）目标函数系数范围 表明新产品Ⅰ的利润在元/件以上，新产品Ⅱ的利润在到之间，新产品Ⅲ的利润在以下，上述的最佳方案不变。 （5）常数项范围 表明铣床的可用条件在400到600工时之间、车铣床的可用条件在275工时以上、磨铣床的可用条件在到工时之间。各自每增加一个工时对总利润的贡献元，0元，元不变。 6、若产品Ⅲ最少销售18件，修改后的的数学模型是： max z= + + S．T．8x1+ 4x2+ 6x3≤500 4x1+ 3x2≤350 3x1+ x3≤150 x3≥18 x1≥0、x2≥0、x3≥0 这是一个混合型的线性规划问题。 代入求解模板得结果如下： 最优解（44，10，18），最优值：元。 灵敏度报告： 目标函数最优值为: 变量最优解相差值 x1 44 0 x2 10 0 x3 18 0 约束松弛/剩余变量对偶价格
附录2 线性规划案例 Appendix 2 Projects of Linear Programming 案例1 食油生产问题(1) 食油厂精炼两种类型的原料油——硬质油和软质油，并将精制油混合得到一种食油产品。硬质原料油来自两个产地:产地1和产地2，而软质原料油来自另外三个产地：产地3，产地4和产地5。据预测，这5种原料油的价格从一至六月分别为： 产品油售价为200元/吨。 硬质油和软质油需要由不同的生产线来精炼。硬质油生产线的每月最大处理能力为200吨，软质油生产线最大处理能力为250吨/月。五种原料油都备有贮罐，每个贮罐的容量均为1000吨，每吨原料油每月的存贮费用为5元。而各种精制油以及产品无油罐可存贮。精炼的加工费用可略去不计。产品的销售没有任何问题。 产品食油的硬度有一定的技术要求，它取决于各种原料油的硬度以及混合比例。产品食油的硬度与各种成份的硬度以及所占比例成线性关系。根据技术要求，产品食油的硬度必须不小于3.0而不大于6.0。各种原料油的硬度如下表（精制过程不会影响硬度）：
假设在一月初，每种原料油都有500吨存贮而要求在六月底仍保持这样的贮备。 问题1：根据表1预测的原料油价格，编制逐月各种原料油采购量、耗用量及库存量计划，使本年内的利润最大。 问题2：考虑原料油价格上涨对利润的影响。据市场预测分析，如果二月份硬质原料油价格比表1中的数字上涨Ｘ％，则软质油在二月份的价格将比表1中的数字上涨2Ｘ％，相应地，三月份，硬质原料油将上涨2Ｘ％，软质原料油将上涨4Ｘ％，依此类推至六月份。试分析Ｘ从1到20的各情况下，利润将如何变化？ 案例2 食油生产问题（2） 在案例1中，附加以下条件，求解新的问题： 1.每一个月所用的原料油不多于三种。 2.如果在某一个月用一种原料油，那么这种油不能少于20吨。 3.如果在一个月中用了硬质油1或硬质油2，则在这个月中就必须用软质油5。案例3 机械产品生产计划问题 机械加工厂生产7种产品（产品1到产品7）。该厂有以下设备：四台磨床、两台立式钻床、三台水平钻床、一台镗床和一台刨床。每种产品的利润（元/件，在这里，利润定义为销售价格与原料成本之差）以及生产单位产品需要的各种设备的工时（小时）如下表。表中的短划表示这种产品不需要相应的设备加工。
第五章线性规划在管理中的应用 5.1 某企业停止了生产一些已经不再获利的产品，这样就产生了一部分剩余生产力。管理层考虑将这些剩余生产力用于新产品Ⅰ、Ⅱ、Ⅲ的生产。可用的机器设备是限制新产品产量的主要因素，具体数据如下表： 量，使得公司的利润最大化。 1、判别问题的线性规划数学模型类型。 2、描述该问题要作出决策的目标、决策的限制条件以及决策的总绩效测度。 3、建立该问题的线性规划数学模型。 4、用线性规划求解模型进行求解。 5、对求得的结果进行灵敏度分析（分别对最优解、最优值、相差值、松驰/剩余量、对偶价格、目标函数变量系数和常数项的变化范围进行详细分析）。 6、若销售部门表示，新产品Ⅰ、Ⅱ生产多少就能销售多少，而产品Ⅲ最少销售18件，请重新完成本题的1-5。 解： 1、本问题是资源分配型的线性规划数学模型。 2、该问题的决策目标是公司总的利润最大化，总利润为： 0.5x1+ 0.2x2+ 0.25x3 决策的限制条件： 8x1+ 4x2+ 6x3≤500 铣床限制条件 4x1+ 3x2≤350 车床限制条件 3x1+ x3≤150 磨床限制条件 即总绩效测试（目标函数）为： max z= 0.5x1+ 0.2x2+ 0.25x3 3、本问题的线性规划数学模型 max z= 0.5x1+ 0.2x2+ 0.25x3 S．T．8x1+ 4x2+ 6x3≤500 4x1+ 3x2≤350 3x1+ x3≤150 x1≥0、x2≥0、x3≥0 4、用Excel线性规划求解模板求解结果：最优解（50，25，0），最优值：30元。 5、灵敏度分析
目标函数最优值为 : 30 变量最优解相差值 x1 50 0 x2 25 0 x3 0 .083 约束松弛/剩余变量对偶价格 1 0 .05 2 75 0 3 0 .033 目标函数系数范围 : 变量下限当前值上限 x1 .4 .5 无上限 x2 .1 .2 .25 x3 无下限 .25 .333 常数项数范围 : 约束下限当前值上限 1 400 500 600 2 275 350 无上限 3 37.5 150 187.5 （1）最优生产方案： 新产品Ⅰ生产50件、新产品Ⅱ生产25件、新产品Ⅲ不安排。最大利润值为30元。 （2）x3 的相差值是0.083意味着，目前新产品Ⅲ不安排生产，是因为新产品Ⅲ的利润太低，若要使新产品Ⅲ值得生产，需要将当前新产品Ⅲ利润0.25元/件，提高到0.333元/件。 （3）三个约束的松弛/剩余变量0，75，0，表明铣床和磨床的可用工时已经用完，而车床的可用工时还剩余75个工时； 三个对偶价格0.05，0，0.033表明三种机床每增加一个工时可使公司增加的总利润额。 （4）目标函数系数范围 表明新产品Ⅰ的利润在0.4元/件以上，新产品Ⅱ的利润在0.1到0.25之间，新产品Ⅲ的利润在0.333以下，上述的最佳方案不变。 （5）常数项范围 表明铣床的可用条件在400到600工时之间、车铣床的可用条件在275工时以上、磨铣床的可用条件在37.5到187.5工时之间。各自每增加一个工时对总利润的贡献0.05元，0元，0.033元不变。 6、若产品Ⅲ最少销售18件，修改后的的数学模型是： max z= 0.5x1+ 0.2x2+ 0.25x3 S．T．8x1+ 4x2+ 6x3≤500 4x1+ 3x2≤350 3x1+ x3≤150 x3≥18 x1≥0、x2≥0、x3≥0 这是一个混合型的线性规划问题。 代入求解模板得结果如下： 最优解（44，10，18），最优值：28.5元。 灵敏度报告： 目标函数最优值为 : 28.5 变量最优解相差值 x1 44 0 x2 10 0
线性规划应用案例
市场营销应用 案例一：媒体选择 在媒体选择中应用线性规划的目的在于帮助市场营销经理将固定的广告预算分配到各种广告媒体上，可能的媒体包括报纸、杂志、电台、电视和直接邮件。在这些媒体中应用线性规划，目的是要使宣传范围、频率和质量最大化。对于应用中的约束条件通常源于对公司政策、合同要求及媒体的可用性。在下面的应用中，我们将介绍如何应用线性规划这一工具来建立模型进而解决媒体选择问题。 REL发展公司正在私人湖边开发一个环湖社区。湖边地带和住宅的主要市场是距离开发区100英里以内的所有中上收入的家庭。REL公司已经聘请BP&J 来设计宣传活动。 考虑到可能的广告媒体和要覆盖的市场，BP&J建议将第一个月的广告局限于5种媒体。在第一个月末，BP&J将依据本月的结果再次评估它的广告策略。BP&J已经收集到了关于受众数量、广告单价、各种媒体一定周期内可用的最大次数以及评定5种媒体各自宣传质量的数据。质量评定是通过宣传质量单位来衡量的。宣传质量单位是一种用于衡量在各个媒体中一次广告的相对价值的标准，它建立于BP&J在广告业中的经验，将众多因素考虑在内，如受众层次（年龄、收入和受众受教育的程度）、呈现的形象和广告的质量。表4-1列出了收集到的这些信息。 表4-1 REL发展公司可选的广告媒体
REL发展公司提供给BP&J第一个月广告活动的预算是30000美元。而且，REL公司对BP&J如何分配这些资金设置了如下限制：至少要使用10次电视广告，达到的受众至少要有50000人，并且电视广告的费用不得超过18000美元。应当推荐何种广告媒体选择计划呢？ 案例二：市场调查 公司开展市场营销调查以了解消费者个性特点、态度以及偏好。专门提供此种信息的市场营销调查公司，经常为客户机构开展实际调查。市场营销调查公司提供的典型服务包括涉及计划、开展市场调查、分析收集数据、提供总结报告和对客户提出意见。在调查设计阶段，应当对调查对象的数量和类型设定目标或限额。市场营销调查公司的目标是以最小的成本满足客户要求。 市场调查公司（MSI）专门评定消费者对新的产品、服务和广告活动的反映。一个客户公司要求MSI帮助确定消费者对一种近期推出的家具产品的反应。在与客户会面的过程中，MSI统一开展个人入户调查，以从有儿童的家庭和无儿童的家庭获得回答。而且MSI还同意同时开展日间和晚间调查。尤其是，客户的合同要求依据以下限制条款进行1000个访问： ●至少访问400个有儿童的家庭； ●至少访问400个无儿童的家庭； ●晚间访问的家庭数量必须不少于日间访问的家庭数量； ●至少40%有儿童的家庭必须在晚间访问； ●至少60%无儿童的家庭必须在晚间访问。 因为访问有儿童的家庭需要额外的访问时间，而且晚间访问者要比日间访问者获得更多收入，所以成本因访问的类型不同而不同。基于以往的调查研究，预计的访问费用如下表所示： 以最小总访问成本满足合同要求的家庭——时间访问计划是什么样的
0-1整数线性规划Matlab程序 x = bintprog(f) x = bintprog(f, A, b) x = bintprog(f, A, b, Aeq, beq) x = bintprog(f, A, b, Aeq, beq, x0) x = bintprog(f, A, b, Aeq, Beq, x0, options) [x, fval] = bintprog(...) [x,fval, exitflag] = bintprog(...) [x, fval, exitflag, output] = bintprog(...) 这里x是问题的解向量 f是由目标函数的系数构成的向量 A是一个矩阵，b是一个向量 A，b和变量x={x1,x2,…,xn}一起，表示了线性规划中不等式约束条件 A，b是系数矩阵和右端向量。 Aeq和Beq表示了线性规划中等式约束条件中的系数矩阵和右端向量。 X0是给定的变量的初始值 options为控制规划过程的参数系列。 返回值中fval是优化结束后得到的目标函数值。 exitflag=0表示优化结果已经超过了函数的估计值或者已声明的最大迭代次数；
exitflag>0表示优化过程中变量收敛于解X， exitflag<0表示计算不收敛。 output有3个分量， iterations表示优化过程的迭代次数， cgiterations表示PCG迭代次数， algorithm表示优化所采用的运算规则。 在使用linprog()命令时，系统默认它的参数至少为1个， 但如果我们需要给定第6个参数，则第2、3、4、5个参数也必须给出，否则系统无法认定给出的是第6个参数。遇到无法给出时，则用空矩阵“[]”替代。 例如 max=193*x1+191*x2+187*x3+186*x4+180*x5+185*x6; %f由这里给出st. x5+x6>=1; x3+x5>=1; x1+x2<=1; x2+x6<=1; x4+x6<=1; %a、b由不等关系给出，如没有不等关系，a、b取[] x1+x2+x3+x4+x5+x6=1; %aep、bep由等式约束给出 代码如下 f=[-193;-191;-187;-186;-180;-185;];
线性规划 线性规划是处理线性目标函数和线性约束的一种较为成熟的方法，目前已经广泛应用于军事、经济、工业、农业、教育、商业和社会科学等许多方面。 8.2.1 基本数学原理 线性规划问题的标准形式是： ????? ??????≥=+++=+++=++++++=0,,,min 21221122222121112 121112211n m n mn m m n n n n n n x x x b x a x a x a b x a x a x a b x a x a x a x c x c x c z 或 ???? ?????=≥===∑∑==n j x m i b x a x c z j n j i j ij n j j j ,,2,1,0,,2,1,min 1 1 写成矩阵形式为： ?? ???≥==O X b AX CX z min 线性规划的标准形式要求使目标函数最小化，约束条件取等式，变量b 非负。不符合这几个条件的线性模型可以转化成标准形式。 MATLAB 采用投影法求解线性规划问题，该方法是单纯形法的变种。 8.2.2 有关函数介绍 在MATLAB 工具箱中，可用linprog 函数求解线性规划问题。 linprog 函数的调用格式如下： ●x=linprog(f,A,b)：求解问题minf'*x ，约束条件为A*x<=b 。 ●x=linprog(f,A,b,Aeq,beq)：求解上面的问题，但增加等式约束，即Aeq*x=beq 。若没有不等式约束，则令A=[ ],b=[ ]。 ●x=linprog(f,A,b,Aeq,beq,lb,ub)：定义设计x 的下界lb 和上界ub ，使得x 始终在该范围内。若没有等式约束，令Aeq=[ ],beq=[ ]。 ●x=linprog(f,A,b,Aeq,beq,lb,ub,x0)：设置初值为x0。该选项只适用于中型问题，默认时大型算法将忽略初值。 ●x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)：用options 指定的优化参数进行最小化。 ●[x,fval]=linprog(…)：返回解x 处的目标函数值fval 。 ●[x,lambda,exitflag]=linprog(…)：返回exitflag 值，描述函数计算的退出条件。 ●[x,lambda,exitflag,output]=linprog(…)：返回包含优化信息的输出参数output 。 ●[x,fval,exitflag,output,lambda]=linprog(…)：将解x 处的拉格朗日乘子返回到lambda 参数中。
实例matlab-非线性规划-作业
现代设计方法-工程优化理论、方法与设计 姓名 学号 班级 研 问题 ： 某厂向用户提供发动机，合同规定，第一、二、三季度末分别交货40台、60台、80台。每季度的生产费用为 （元），其中x 是该季生产的台数。若交货后有剩余，可用于下季度交货，但需支付存储费，每台每季度c 元。已知工厂每季度最大生产能力为100台，第一季度开始时无存货，设a=50、b=0.2、c=4，问工厂应如何安排生产计划，才能既满足合同又使总费用最低。讨论a 、b 、c 变化对计划的影响，并作出合理的解释。 问题的分析和假设： 问题分析：本题是一个有约束条件的二次规划问题。决策变量是工厂每季度生产的台数，目标函数是总费用（包括生产费用和存储费）。约束条件是生产合同，生产能力的限制。在这些条件下需要如何安排生产计划，才能既满足合同又使总费用最低。 问题假设： 1、工厂最大生产能力不会发生变化； 2、合同不会发生变更； 3、第一季度开始时工厂无存货； 4、生产总量达到180台时，不在进行生产； 5、工厂生产处的发动机质量有保证，不考虑退货等因素； 6、不考虑产品运输费用是否有厂家承担等和生产无关的因素。 符号规定： x1——第一季度生产的台数； x2——第二季度生产的台数； 180-x1-x2——第三季度生产的台数； y1——第一季度总费用； y2——第二季度总费用； y3——第三季度总费用； y ——总费用（包括生产费用和存储费）。 ()2bx ax x f +=
建模： 1、第一、二、三季度末分别交货40台、60台、80台； 2、每季度的生产费用为 （元）； 3、每季度生产数量满足40 ≤x1≤100，0≤x2≤100，100≤x1+x2 ≤180； 4、要求总费用最低，这是一个目标规划模型。 目标函数: y1 2111x b x a Z ?+?= y2()4012222-?+?+?=x c x b x a Z y3()()()10018018021221213 -+?+--?+--?=x x c x x b x x a Z y x x x x x x Z Z Z Z 68644.04.04.0149201 212221321--+++=++= 40≤x1≤100 0≤x2≤100 100≤x1+x2≤180 ()2 bx ax x f +=
LINGO 程序说明 3.1 程序名: linearp1（求极小问题） linearp1运行实例: 5 ,,1 ,0 1 2 2 6 .t .s 215min 532143212 1 =≥=-++=-+-+=j x x x x x x x x x x x z j 在model window 中输入以下语句： min=5*x1+21*x3; x1-x2+6*x3-x4=2; x1+x2+2*x3-x5=1; 按运行按钮在solution report 窗口得到以下结果： Global optimal solution found at iteration: 2 Objective value: 7.750000 Variable Value Reduced Cost X1 0.5000000 0.000000 X3 0.2500000 0.000000 X2 0.000000 0.5000000 X4 0.000000 2.750000 X5 0.000000 2.250000 Row Slack or Surplus Dual Price 1 7.750000 -1.000000 2 0.000000 -2.750000 3 0.000000 -2.250000 3.2 程序名: linearp2（求极大问题） linearp2运行实例： max 100150..2160 100 120 ,0 x y s t x y x y x y ++≤≤≤≥ 在model window 中输入以下语句： max=100*x+150*y; ! this is a commnent; x<=100; y<=120;
线性规划的应用 线性规划是运筹学中一个重要分支，它是研究线性约束条件下线性目标函数的极值问题的数学理论和方法。广泛应用于军事作战、经济分析、经营管理和工程技术等方面。如：经济管理、交通运输、工农业生为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。 线性规划作为运筹学的一个研究较早、发展较快、应用广泛、方法较成熟的重要分支，它在日常生活中的典型应用主要有：1合理利用线材问题：如何下料使用材最少 2配料问题：在原料供应量的限制下如何获取最大利润 3投资问题：从投资项目中选取方案，使投资回报最大 4产品生产计划：合理利用人力、物力、财力等，使获利最大 5劳动力安排：用最少的劳动力来满足工作的需要 6运输问题：如何制定调动方案，使总运费最小 其实，也就是说，线性规划在运筹学中的研究对象主要是在有一定的人力、财力、资源条件下，如何合理安排使用，效益最高和在某项任务确定后，如何安排人、财、物，使之最省。 例如： 某公司现有三条生产线来生产两种新产品，其主要数据如表1.1所示。请问如何生产可以让公司每周利润最大？
表1 产品组合问题的数据表 此问题是在生产线可利用时间受到限制的情形下寻求每周利润最大化的产品组合问题。 在建立产品组合模型的过程中，以下问题需要得到回答： （1）要做出什么决策？ （2）做出的决策会有哪些条件限制？ （3）这些决策的全部评价标准是什么？ （1）变量的确定 要做出的决策是两种新产品的生产水平，记x1为每周生产产品甲的产量，x2为每周生产产品乙的产量。一般情况下，在实际问题中常常称为变量（决策变量）。 （2）约束条件 求目标函数极值时的某些限制称为约束条件。如两种产品在相应生产线上每周生产时间不能超过每条生产线的可得时间，对于生产线一，有x1≤4，类似地，其它生产线也有不等式约束。 （3）目标函数 对这些决策的评价标准是这两种产品的总利润，即目标函数是要求每周的生产利润（可记为z，以百元为计量单位）为最大 这样，可以把产品组合问题抽象地归结为一个数学模型： max z = 3x1+5x2 s.t. x1 ≤4 2x2 ≤12 3x1+ 2x2 ≤18 x1≥0，x2 ≥0
Lingo12软件培训教案 Lingo 主要用于求解线性规划，整数规划，非线性规划，V10以上版本可编程。 例1 一个简单的线性规划问题 0 , 600 2 100 350 st. 3 2max >=<=+=<<=++=y x y x x y x y x z ! 源程序 max = 2*x+3*y; [st_1] x+y<350; [st_2] x<100; 2*x+y<600; !决策变量黙认为非负; <相当于<=; 大小写不区分 当规划问题的规模很大时，需要定义数组(或称为矩阵)，以及下标集(set) 下面定义下标集和对应数组的三种方法，效果相同:：r1 = r2 = r3, a = b = c. sets : r1/1..3/:a; r2 : b; r3 : c; link2(r1,r2): x; link3(r1,r2,r3): y; endsets data : ALPHA = ; a=11 12 13 ; r2 = 1..3; b = 11 12 13; c = 11 12 13; enddata
例2 运输问题 解： 设决策变量ij x = 第i 个发点到第j 个售点的运货量，i =1,2,…m; j =1,2,…n; 记为ij c =第i 个发点到第j 个售点的运输单价，i =1,2,…m; j =1,2,…n 记i s =第i 个发点的产量， i =1,2,…m; 记j d =第j 个售点的需求量， j =1,2,…n. 其中，m = 6; n = 8. 设目标函数为总成本，约束条件为（1）产量约束；（2）需求约束。 于是形成如下规划问题： n j m i x n j d x m i s x x c ij j n i ij i m j ij m i n j ij ij ,...,2,1,,...,2,1,0 ,...,2,1, ,...,2,1, st. z min 11 11==>=<==<==∑∑∑∑==== 把上述程序翻译成LINGO 语言，编制程序如下： ! 源程序
实验报告 课程名称：运筹学导论 实验名称：线性规划问题实例分析专业名称：信息管理与信息系统 指导教师：刘珊 团队成员：邓欣(20112111 蒋青青(20114298 吴婷婷(20112124 邱子群(20112102 熊游(20112110 余文媛(20112125 日期：2013-10-25 成绩：___________
1．案例描述 南部联盟农场是由以色列三个农场组成的联合组织。该组织做出了一个关于农场农作物的种植计划，如下： 每一个农场的农业产出受限于两个量，即可使用的灌溉土地量和用于灌溉的水量。数据见下表： 适合本地区种植的农作物包括糖用甜菜、棉花和高粱。这三种作物的差异在于它们每亩的期望净收益和水的消耗量不同。另外农业部门已经制定了南部联盟农场作物总亩数的最大配额，见下表： 作物的任何组合可以在任何农场种植，技术部门的任务是找出一个种植方案使南部联盟农场的净收益最大化。 2.建立模型 决策变量为Xi(i=1,2,……,9,表示每个农场每种作物的种植量。 MAX Z=1000(X1+X2+X3+750(X4+X5+X6+250(X7+X8+X9 约束条件： （1）每一个农场使用的土地 X1+X4+X7≤400
X2+X5+X8≤600 X3+X6+X9≤300 (2每一个农场的水量分布 3X1+2X4+X7≤600 3X2+2X5+X8≤800 3X3+2X6+X9≤375 (3每一种作物的总种植量 X1+X2+X3≤600 X4+X5+X6≤500 X7+X8+X9≤325 非负约束Xi≥0 , i=1,2, (9) 3.计算机求解过程 步骤1.生成表格 步骤2.输入数据
查漏补缺(一) 程序框图 1.执行如图所示的程序框图,输出的S 值为（ ） A ．2 B ．4 C ．8 D ．16 2.如图2,程序框图(算法流程图)的输出结果是（ ）A ．-3 B ．-2 C ．-5 D ．8 3.执行图3所示的程序框图，若输入x ＝4，则输出y 的值为( ) A ．12- B ．12 C ．54- D ．54 4.执行图4所示的程序框图,输入x ＝－2,h ＝0.5,那么输出的各个数的和等于（ ） A.3 B.3.5 C.4 D.4.5 5.执行图5所示的程序框图，如果输入的N 是6，那么输出的p 是( ) A ．120 B ． 720 C ． 1440 D ． 5040 图3 图4 图5 k=0,S=1 k <3 开始 结束 是 否 k=k+1 输出S S=S ×2k 图1
6.阅读右边的程序框图,运行相应的程序,当输入x 的值为25-时,输出x 的值为（ ） A ．1- B ．1 C ．3 D ．9 7.如果执行右边的程序框图,输入正整数(2)N N ≥和实数12,,...,n a a a ,输出,A B ,则( ) A ．A B +为12,,...,n a a a 的和 B ．2 A B +为12,,...,n a a a 的算术平均数 C ．A 和B 分别是12,,...,n a a a 中最大的数和最小的数 D ．A 和B 分别是12,,...,n a a a 中最小的数和最大的数 8.下图是一个算法流程图,则输出的k 的值是____. 9.如果执行如图3所示的程序框图,输入1x =-,n =3,则输出的数S = __ 开 始 输入x |x|>1 1 ||-=x x x = 2x+1 输出x 结 束 是 否 开始 输入x , n S ＝6 i ≥0? 是 否 输出S 结束 i ＝n －1 i ＝i －1 S ＝S·x ＋i ＋1
第一章 线性规划 §1 线性规划 在人们的生产实践中，经常会遇到如何利用现有资源来安排生产，以取得最大经济效益的问题。此类问题构成了运筹学的一个重要分支—数学规划，而线性规划(Linear Programming 简记LP)则是数学规划的一个重要分支。自从1947年G. B. Dantzig 提出求解线性规划的单纯形方法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是在计算机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了，已成为现代管理中经常采用的基本方法之一。 1.1 线性规划的实例与定义 例1 某机床厂生产甲、乙两种机床，每台销售后的利润分别为4000元与3000元。生产甲机床需用B A 、机器加工，加工时间分别为每台2小时和1小时；生产乙机床需用C B A 、、三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为A 机器10小时、B 机器8小时和C 机器7小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？ 上述问题的数学模型：设该厂生产1x 台甲机床和2x 台乙机床时总利润最大，则 21,x x 应满足 （目标函数）2134m ax x x z += (1) s.t.（约束条件）???????≥≤≤+≤+0 ,781022122 121x x x x x x x （2） 这里变量21,x x 称之为决策变量，（1）式被称为问题的目标函数，（2）中的几个不等式 是问题的约束条件，记为s.t.(即subject to)。上述即为一规划问题数学模型的三个要素。由于上面的目标函数及约束条件均为线性函数，故被称为线性规划问题。 总之，线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。 在解决实际问题时，把问题归结成一个线性规划数学模型是很重要的一步，但往往也是困难的一步，模型建立得是否恰当，直接影响到求解。而选取适当的决策变量，是我们建立有效模型的关键之一。 1.2 线性规划的Matlab 标准形式 线性规划的目标函数可以是求最大值，也可以是求最小值，约束条件的不等号可以是小于号也可以是大于号。为了避免这种形式多样性带来的不便，Matlab 中规定线性规划的标准形式为 b Ax x c x T ≤ that such min 其中c 和x 为n 维列向量，b 为m 维列向量，A 为n m ?矩阵。 例如线性规划 b Ax x c x T ≥ that such max 的Matlab 标准型为
线性规划的方法及应用 1 引言 运筹学最初是由于第二次世界大战的军事需要而发展起来的，它是一种科学方法，是一种以定量的研究优化问题并寻求其确定解答的方法体系．线性规划（Linear Progromming ，简称LP ）是运筹学的一个重要分支，其研究始于20世纪30年代末，许多人把线性规划的发展列为20世纪中期最重要的科学进步之一．1947年美国的数学家丹泽格提出了一般的线性规划数学模型和求解线性规划问题的通用方法――单纯形法，从而使线性规划在理论上趋于成熟．此后随着电子计算机的出现，计算技术发展到一个高阶段，单纯形法步骤可以编成计算机程序，从而使线性规划在实际中的应用日益广泛和深入．目前，从解决工程问题的最优化问题到工业、农业、交通运输、军事国防等部门的计划管理与决策分析，乃至整个国民经济的综合平衡，线性规划都有用武之地，它已成为现代管理科学的重要基础之一． 2 线性规划的提出 经营管理中如何有效地利用现有人力物力完成更多的任务，或在预定的任务目标下，如何耗用最少的人力物力去实现．这类问题可以用数学语言表达，即先根据问题要达到的目标选取适当的变量，问题的目标通常用变量的函数形式（称为目标函数），对问题的限制条件用有关变量的等式或不等式表达（称为约束条件）．当变量连续取值，且目标函数和约束条件为线性时，称这类模型为线性规划的模型．有关对线性规划问题建模、求解和应用的研究构成了运筹学中的线性规划分支．线性规划实际上是:求一组变量的值，在满足一组约束条件下，求得目标函数的最优解.从而线性规划模型的基本结构为： ①变量：变量又叫未知数，它是实际系统的位置因素，也是决策系统中的可控因素，一般称为决策变量，常引用英文字母加下标来表示，如n x x x ,,,21 等． ②目标函数：将实际系统的目标用数学形式表示出来，就称为目标函数，线性规划的目标函数是求系统目标的数值，即极大值（如产值极大值，利润极大值）或极小值（如成本极小值，费用极小值等等）． ③约束条件：约束条件是指实现系统目标的限制因素．它涉及到企业内部条件和外部环境的各个方面，如原材料供应设备能力、计划指标．产品质量要求和市场销售状态等等，这些因素都对模型的变量起约束作用，故称其为约束条件．约束条件的数学表示有三种，即 ,,,线性规划的变量应为非负值，因为变量在实际问题中所代表的均为实物，所以不能为负． 线性规划问题有多种形式，函数有的要求实现最大化，有的要求最小化；约束条件可以是“ ”，
8.2 线性规划 线性规划是处理线性目标函数和线性约束的一种较为成熟的方法，目前已经广泛应用于军事、经济、工业、农业、教育、商业和社会科学等许多方面。 8.2.1 基本数学原理 线性规划问题的标准形式是： ????? ??????≥=+++=+++=++++++=0,,,min 21221122222121112 121112211n m n mn m m n n n n n n x x x b x a x a x a b x a x a x a b x a x a x a x c x c x c z ΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛΛ 或 ???? ?????=≥===∑∑==n j x m i b x a x c z j n j i j ij n j j j ,,2,1,0,,2,1,min 1 1ΛΛ 写成矩阵形式为： ?? ???≥==O X b AX CX z min 线性规划的标准形式要求使目标函数最小化，约束条件取等式，变量b 非负。不符合这几个条件的线性模型可以转化成标准形式。 MATLAB 采用投影法求解线性规划问题，该方法是单纯形法的变种。 8.2.2 有关函数介绍 在MATLAB 工具箱中，可用linprog 函数求解线性规划问题。 linprog 函数的调用格式如下： ●x=linprog(f,A,b)：求解问题minf'*x ，约束条件为A*x<=b 。 ●x=linprog(f,A,b,Aeq,beq)：求解上面的问题，但增加等式约束，即Aeq*x=beq 。若没有不等式约束，则令A=[ ],b=[ ]。 ●x=linprog(f,A,b,Aeq,beq,lb,ub)：定义设计x 的下界lb 和上界ub ，使得x 始终在该范围内。若没有等式约束，令Aeq=[ ],beq=[ ]。 ●x=linprog(f,A,b,Aeq,beq,lb,ub,x0)：设置初值为x0。该选项只适用于中型问题，默认时大型算法将忽略初值。 ●x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)：用options 指定的优化参数进行最小化。 ●[x,fval]=linprog(…)：返回解x 处的目标函数值fval 。 ●[x,lambda,exitflag]=linpro g(…)：返回exitflag 值，描述函数计算的退出条件。 ●[x,lambda,exitflag,output]=linprog(…)：返回包含优化信息的输出参数output 。 ●[x,fval,exitflag,output,lambda]=linprog(…)：将解x 处的拉格朗日乘子返回到
市场营销应用 案例一：媒体选择 在媒体选择中应用线性规划的目的在于帮助市场营销经理将固定的广告预算分配到各种广告媒体上，可能的媒体包括报纸、杂志、电台、电视和直接邮件。在这些媒体中应用线性规划，目的是要使宣传范围、频率和质量最大化。对于应用中的约束条件通常源于对公司政策、合同要求及媒体的可用性。在下面的应用中，我们将介绍如何应用线性规划这一工具来建立模型进而解决媒体选择问题。 REL发展公司正在私人湖边开发一个环湖社区。湖边地带和住宅的主要市场是距离开发区100英里以内的所有中上收入的家庭。REL公司已经聘请BP&J 来设计宣传活动。 考虑到可能的广告媒体和要覆盖的市场，BP&J建议将第一个月的广告局限于5种媒体。在第一个月末，BP&J将依据本月的结果再次评估它的广告策略。BP&J已经收集到了关于受众数量、广告单价、各种媒体一定周期内可用的最大次数以及评定5种媒体各自宣传质量的数据。质量评定是通过宣传质量单位来衡量的。宣传质量单位是一种用于衡量在各个媒体中一次广告的相对价值的标准，它建立于BP&J在广告业中的经验，将众多因素考虑在内，如受众层次（年龄、收入和受众受教育的程度）、呈现的形象和广告的质量。表4-1列出了收集到的这些信息。 表4-1 REL发展公司可选的广告媒体
REL发展公司提供给BP&J第一个月广告活动的预算是30000美元。而且，REL公司对BP&J如何分配这些资金设置了如下限制：至少要使用10次电视广告，达到的受众至少要有50000人，并且电视广告的费用不得超过18000美元。应当推荐何种广告媒体选择计划呢？ 案例二：市场调查 公司开展市场营销调查以了解消费者个性特点、态度以及偏好。专门提供此种信息的市场营销调查公司，经常为客户机构开展实际调查。市场营销调查公司提供的典型服务包括涉及计划、开展市场调查、分析收集数据、提供总结报告和对客户提出意见。在调查设计阶段，应当对调查对象的数量和类型设定目标或限额。市场营销调查公司的目标是以最小的成本满足客户要求。 市场调查公司（MSI）专门评定消费者对新的产品、服务和广告活动的反映。一个客户公司要求MSI帮助确定消费者对一种近期推出的家具产品的反应。在与客户会面的过程中，MSI统一开展个人入户调查，以从有儿童的家庭和无儿童的家庭获得回答。而且MSI还同意同时开展日间和晚间调查。尤其是，客户的合同要求依据以下限制条款进行1000个访问： ●至少访问400个有儿童的家庭； ●至少访问400个无儿童的家庭； ●晚间访问的家庭数量必须不少于日间访问的家庭数量； ●至少40%有儿童的家庭必须在晚间访问； ●至少60%无儿童的家庭必须在晚间访问。 因为访问有儿童的家庭需要额外的访问时间，而且晚间访问者要比日间访问者获得更多收入，所以成本因访问的类型不同而不同。基于以往的调查研究，预计的访问费用如下表所示： 以最小总访问成本满足合同要求的家庭——时间访问计划是什么样的呢？
1.人力资源分配问题 设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，既能满足工作需要，又使配备司机和乘务人员的人数最少？ 解：设x i 表示第i班次时开始上班的司机和乘务人员数, 这样我们建立如下的数学模型。 目标函数：Min x1 + x2 + x3 + x4 + x5 + x6 约束条件：s.t. x1 + x6 ≥60 x1 + x2 ≥70 x2 + x3 ≥60 x3 + x4 ≥50 x4 + x5 ≥20 x5 + x6 ≥30 x1,x2,x3,x4,x5,x6 ≥0 运用lingo求解： Objective value: 150.0000 ariable Value Reduced Cost X1 60.00000 0.000000 X2 10.00000 0.000000 X3 50.00000 0.000000 X4 0.000000 0.000000 X5 30.00000 0.000000 X6 0.000000 0.000000 例2．一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？
解：设x i ( i = 1,2,…,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。 目标函数：Min x1 + x2 + x3 + x4 + x5 + x6 + x7 约束条件：s.t. x1 + x2 + x3 + x4 + x5 ≥28 x2 + x3 + x4 + x5 + x6 ≥15 x3 + x4 + x5 + x6 + x7 ≥24 x4 + x5 + x6 + x7 + x1 ≥25 x5 + x6 + x7 + x1 + x2 ≥19 x6 + x7 + x1 + x2 + x3 ≥31 x7 + x1 + x2 + x3 + x4 ≥28 x1,x2,x3,x4,x5,x6,x7 ≥0 lingo求解 Objective value: 36.00000 Variable Value Reduced Cost X1 12.00000 0.000000 X2 0.000000 0.3333333 X3 11.00000 0.000000 X4 5.000000 0.000000 X5 0.000000 0.000000 X6 8.000000 0.000000 X7 0.000000 0.000000 例3. 某储蓄所每天的营业时间为上午9:00到下午17:00，根据经验，每天不同时间段所需要 储蓄所可以雇佣全时和半时两类服务员。全时服务员每天报酬为100元，从上午9:00到下午17:00工作，但中午12:00到下午14:00之间必须安排1小时的午餐时间；储蓄所每天可以雇佣不超过3名的半时服务员，每个半时服务员必须连续工作4小时，报酬为40元。问： 1) 储蓄所应该如何雇佣全时和半时两类服务员？ 2) 如果不能雇佣半时服务员，每天至少增加多少经费？ 3) 如果雇佣半时服务员的数量没有限制，每天可以减少多少经费？ 解：设x1, x2分别表示12~13，13~14进行午餐的全时服务人员， y1，y2，y3，y4，y5分别表示9~10，10~11，11~12，12~13，13~14开始工作的半时服务人员，则问题1的模型如下所示： min=100*x1+100*x2+40*y1+40*y2+40*y3+40*y4+40*y5; x1+x2+y1>4; x1+x2+y1+y2>3; x1+x2+y1+y2+y3>4; x2+y1+y2+y3+y4>6; x1+y2+y3+y4+y5>5; x1+x2+y3+y4+y5>6; x1+x2+y4+y5>8; x1+x2+y5>8; y1+y2+y3+y4+y5<3;