《建模教程线性规划文档资料》由会员分享，可在线阅读，更多相关《建模教程线性规划文档资料（89页珍藏版）》请在金锄头文库上搜索。
1、静静 态态 最最 优优 化化 问问 题题20-Jul-24线性规划模型与求解线性规划模型与求解线性规划线性规划 Linear Programming运筹学中应用最广泛的方法之一运筹学中应用最广泛的方法之一运筹学的最基本的方法之一，网络规划，运筹学的最基本的方法之一，网络规划，整数规划，目标规划和多目标规划都是整数规划，目标规划和多目标规划都是以线性规划为基础的以线性规划为基础的解决稀缺资源最优分配的有效方法，使解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大付出的费用最小或获得的收益最大研究对象研究对象有一定的人力、财力、资源条件下，如有一定的人力、财力、资源条件下，如何合理安
2、排使用，效益最高何合理安排使用，效益最高某项任务确定后，如何安排人、财、物，某项任务确定后，如何安排人、财、物，使之最省使之最省线性规划的数学模型线性规划的数学模型某某家具厂木器车间生产木门与木窗两种家具厂木器车间生产木门与木窗两种产品。加工木门收入为产品。加工木门收入为56元扇、加工元扇、加工木窗收入为木窗收入为30元扇。生产一扇木门需元扇。生产一扇木门需要木工要木工4小时、油漆工小时、油漆工2小时；生产一扇小时；生产一扇木窗需要木工木窗需要木工3小时、油漆工小时、油漆工1小时。该小时。该车间每日可用木工总工时为车间每日可用木工总工时为120小时，小时，油漆工总工时为油漆工总工时为50小时。
3、问该车间应如小时。问该车间应如何安排生产才能使每日收入最大。何安排生产才能使每日收入最大。设该车间每日安排生产木门x1扇、木窗x2扇。Model:Maxz=56x1+30x2s.t4x1+3x21202x1+x250x1,x20解得：X*=(15,20)T,z*=1440假若另有一个个体经营者，手中有一批假若另有一个个体经营者，手中有一批木器家具生产订单。他想利用该木器车木器家具生产订单。他想利用该木器车间的木工与油漆工来加工完成他的订单。间的木工与油漆工来加工完成他的订单。他就要事先考虑付给该车间每个工时的他就要事先考虑付给该车间每个工时的价格。他可以构造一个数学模型来研究价格。他可以构造一
4、个数学模型来研究如何定价才能既使木器车间觉得有利可如何定价才能既使木器车间觉得有利可图从而愿意为他加工这批订单、又使自图从而愿意为他加工这批订单、又使自己所付的工时费用总数最少。己所付的工时费用总数最少。设w1,w2分别为付给木工和油漆工每个工时的价格。则该个体经营者的目标函数为每日所付工时总费用最小。Minf=120w1+50w2该个体经营者所付的价格不能太低，至少不能低于该车间生产木门、木窗时所得到的收入，否则该车间觉得无利可图就不会替他加工这批订单。因此，需满足4w1+2w2563w1+w230w1,w20解得：W*（2，24），f*=1440Maxz=56x1+30x2Minf=120
5、w1+50w2s.t4x1+3x2120s.t.4w1+2w2562x1+x2503w1+w230x1,x20w1,w20上面两个线性规划模型称为一对上面两个线性规划模型称为一对对偶对偶的的线性规划模型。线性规划模型。任一线性规划问题都有一对偶问题。任一线性规划问题都有一对偶问题。线性规划模型特点线性规划模型特点决策变量：向量(x1xn)T决策人要考虑和控制的因素，一般非负约束条件：线性等式或不等式目标函数：Z=(x1xn)线性式，求Z极大或极小一般式一般式max(min)Z=C1X1+ C2X2+CnXna11X1+ a12X2+ a1nXn (=, (=, )b)b1 1a21X1+ a2
6、2X2+ a2nXn (=, (=, )b)b2 2 am1X1+ am2X2+ amnXn (=, (=, ) )b bm mXj j 0(0(j=1,n) )11隐含的假设比例性：决策变量变化引起目标的改变量与决策变量改变量成正比可加性：每个决策变量对目标和约束的影响独立于其它变量连续性：每个决策变量取连续值确定性：线性规划中的参数aij, bi, ci为确定值线性规划模型线性规划模型线性规划模型的结构目标函数 ：max，min约束条件：,=,变量符号：0, unr, 0线性规划的标准形式目标函数：min约束条件：=变量符号：0线性规划的图解法线性规划的图解法max z=x1+3x2s.t
7、. x1+ x26-x1+2x28x1 0, x20可行域可行域目标函数等值线最优解64-860x1x2可行域可行域 线段组成的凸多边形线段组成的凸多边形目标函数目标函数 等值线为直线等值线为直线最优解最优解 凸多边形的某个顶点凸多边形的某个顶点LP问题的特性问题的特性2维维n维维超平面组成的凸多面体超平面组成的凸多面体等值线是超平面等值线是超平面凸多面体的某个顶点凸多面体的某个顶点凸集凸集D是是n维欧氏空间的一个集合维欧氏空间的一个集合 X(1), X(2)D,D,若任一个满足若任一个满足 X= X(1)+(1- ) X(2) (0 1) 有有XDD定义定义1：凸集凸集及其顶点及其顶点 X(
8、1) , X(2) , ,X(k)是n维欧氏空间中的k个点，若有一组数1 , 2 , , k满足0 i 1 (i=1, ,k)定义定义2 i =1ki=1有点有点 x= 1 X(1) + + k X(k)则称点则称点X为为 X(1) , X(2) , ,X(k) 的的凸组合。凸组合。凸组合凸组合 凸集D,点XD，若找不到两个不同的点X(1) , X(2) D使得X= X(1) +(1- ) X(2) (0 1) 则称X为D的顶点。定义定义3顶点顶点定理定理2：LP有最优解，必定可以在可行域有最优解，必定可以在可行域(凸凸多面集多面集)的顶点得到。的顶点得到。定理定理1：LP问题的可行域一定是凸
9、集问题的可行域一定是凸集(凸多面集凸多面集)LP问题的解的性质问题的解的性质凸集凸集不是凸集LP问题解的性质问题解的性质maxZ=CX AX =b X 0 0A Amn 满秩满秩 X = (x1 xn)T a11 a1m a1m+1 a1na21 a2m a2m+1 a2n am1 amm amm+1 amnP1 Pm Pm+1 PnBN(m 00且相应的且相应的Pm+k =(a1m+k , ,amm+k )T 0，则原问题则原问题无有限最优解。无有限最优解。线性规划的求解软件线性规划的求解软件LINDOLINGO()ExcelMatlabMathematicaSASCPLEXLinDo输入模
10、型输入模型求解求解 点击求解按钮点击求解按钮 即可即可结果结果输入模型!注释内容，可用中文!目标函数：最大-max,最小-min,大小写不分max3x1+5x2+4x3!约束，以subjectto开始subjectto2x1+3x2=15002x2+4x3=8003x1+2x2+5x3=2000end注意事项变量以字母开头，下标写在后面，系数与变量之间加空格不等号为:=(=(),=,=与等同变量非负约束可省略结束时以end标示结果LPOPTIMUMFOUNDATSTEP3OBJECTIVEFUNCTIONVALUE1)2675.000VARIABLEVALUEREDUCEDCOSTX1375.
11、0000000.000000X2250.0000000.000000X375.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.0000001.0500003)0.0000000.6250004)0.0000000.300000LinGo输入模型LinDo模式LinGo模式求解点击求解按钮即可结果LinGo输入模式model:MAX=3*x1+5*x2+4*x3; 2*x1+3*x2=1500; 2*x2+4*x3=800; 3*x1+2*x2+5*x3=2000;end注意与LinDo的区别目标函数中加等号变量与系数之间用“*”Model:-end可省
12、略LinGo模式Model:Sets:!定义集合EndsetsData:！定义数据Enddata调用函数与计算end集合部分model: ！开始sets: ！定义集合ve/1.3/:c,x;co/1.3/:b;ma(co,ve):a;endsets！注：集表达式：名称/成员/：属性名称（初始集）：属性定义数据data:！定义数据c=3 5 4;b=1500 800 2000;a=2 3 0 0 2 4 3 2 5;Enddata！注：数据的大小与集合定义中一致，分量中间用空格或逗号分开，数据结束后用分号； 调用函数调用函数max=sum(ve(j):c(j)*x(j);for(co(i):su
13、m(ve(j):a(i,j)*x(j) ”? ?整数约束是否可以忽略整数约束是否可以忽略? ?求解方法是否合适求解方法是否合适? ?有配套约束的资源优化问题有配套约束的资源优化问题某公司计划用资金某公司计划用资金60万元来购买万元来购买A、B、C三种运三种运输汽车。已知输汽车。已知A种汽车每辆为种汽车每辆为1万元，每班需一名万元，每班需一名司机，可完成司机，可完成2100t.km; B种汽车每辆为种汽车每辆为2万元，万元，每班需两名司机，可完成每班需两名司机，可完成3600t.km; C种汽车每种汽车每辆为辆为2.3万元，每班需两名司机，可完成万元，每班需两名司机，可完成3780t.km。每辆
14、汽车每天最多安排三班，每个司每辆汽车每天最多安排三班，每个司机每天最多安排一班。购买汽车数量不超过机每天最多安排一班。购买汽车数量不超过30辆，辆，司机不超过司机不超过145人。问：每种汽车应购买多少辆，人。问：每种汽车应购买多少辆，可使该公司今后每天可完成的可使该公司今后每天可完成的t.km数数最大。最大。例：某炼油厂生产三种规格的汽油：例：某炼油厂生产三种规格的汽油：70号、号、80号与号与85号，它们各有不同的辛烷值与含号，它们各有不同的辛烷值与含硫量的质量要求。这三种汽油由三种原料硫量的质量要求。这三种汽油由三种原料油调和而成。每种原料油每日可用量、质油调和而成。每种原料油每日可用量、
15、质量指标及生产成本，每种汽油的质量要求量指标及生产成本，每种汽油的质量要求和销售价格见下表。假定在调和中辛烷值和销售价格见下表。假定在调和中辛烷值与含硫量指标都符合线性可加性。问该炼与含硫量指标都符合线性可加性。问该炼油厂如何安排生产才能使利润最大。油厂如何安排生产才能使利润最大。原料辛烷值含硫量()成本(元吨)可用量(吨日)直馏汽油621.56002000催化汽油780.89001000重整汽油900.21400500产品辛烷值含硫量()销售价(元吨)70号汽油70190080号汽油801120085号汽油850.61500港口船只配备问题港口船只配备问题某航运公司承担六个港口城市某航运公司
16、承担六个港口城市A，B，C，D，E，F的四条固定航线的物资运输的四条固定航线的物资运输任务。已知各条航线的起点、终点城市任务。已知各条航线的起点、终点城市及每天航班数。假定各条航线使用相同及每天航班数。假定各条航线使用相同型号的船只，已知各城市间航程天数。型号的船只，已知各城市间航程天数。又知每条船只每次装卸货的时间各需一又知每条船只每次装卸货的时间各需一天。问该公司至少应配备多少条船，才天。问该公司至少应配备多少条船，才能满足所有航线运货要求。能满足所有航线运货要求。航线航线起点城市起点城市终点城市终点城市每天航班数每天航班数1ED32BC23AF14DB1从到ABCDEFA0121477B
17、1031388C2301555D14131501720E7851703F7852030航运公司所需配备的船只分两部分：航运公司所需配备的船只分两部分：载货航程（包括装、卸货）需要的周转船只数。载货航程（包括装、卸货）需要的周转船只数。航线航线起点城市起点城市终点城市终点城市每天航班数每天航班数所需船只数所需船只数1ED33 (17+2)=572BC22 (3+2)=103AF11 (7+2)=94DB11 (13+2)=15共共91条条港口间调度所需船只数。（即空船行驶部分）港口间调度所需船只数。（即空船行驶部分） 各港口每天船只余缺表各港口每天船只余缺表港口城市港口城市每天到达每天到达每天需
18、求每天需求余缺数余缺数-对某个港口对某个港口:若到达的船只多于发出船只，多余的船只则调往其他若到达的船只多于发出船只，多余的船只则调往其他港口，它相当于产地；若到达的船只少于发出船只，则需从其他港口，它相当于产地；若到达的船只少于发出船只，则需从其他港口调入船只，它相当于销地；以航程天数作为单位运价。港口调入船只，它相当于销地；以航程天数作为单位运价。这是一个供需平衡的运输问题这是一个供需平衡的运输问题调出量调出量235214131727831调入量调入量113最优调度方案如下，共需周转船最优调度方案如下，共需周转船40条。条。所需配备船只总数为 条131运输问题的数学模型设有同一种货物从设有
19、同一种货物从m个产地个产地1，2，m运往运往n个销地个销地1，2，n。第。第i个发地的供个发地的供应量（应量（Supply）为）为si（si0），第），第j个收地的个收地的需求量（需求量（Demand）为）为dj（dj0）。）。每单位每单位货物从发地货物从发地i运到收地运到收地j的运价为的运价为cij。求一个求一个使总运费最小的运输方案。我们假定从任使总运费最小的运输方案。我们假定从任一发地到任一收地都有道路通行。如果总一发地到任一收地都有道路通行。如果总供应量等于总需求量，这样的运输问题称供应量等于总需求量，这样的运输问题称为供求平衡的运输问题。为供求平衡的运输问题。 运输问题线性规划模型在
20、运输问题线性规划模型中，令在运输问题线性规划模型中，令X=（x11，x12，x1n，x21，x22，x2n，xm1，xm2，xmn）TC=（c11，c12，c1n，c21，c22，c2n，cm1，cm2，cmn）Tb=（s1，s2，sm，d1，d2，dn）TA=a11，a12，a1n，a21，a22，a2n，am1，am2，amn 则运输问题的线性规划可以写成：则运输问题的线性规划可以写成：min z=CTXs.t. AX=b X0其中其中A矩阵的列向量矩阵的列向量aij=ei+em+j2312341运输问题网络图运输问题网络图运输问题网络图运输问题网络图d1=3d2=6d3=5d4=6s2=
21、4s3=9s1=7供应地运价需求地311310912874105供应量需求量总供应量20吨总需求量20吨供求平衡的运输问题运输问题线性规划模型运输问题线性规划模型运输问题线性规划模型运输问题线性规划模型供应地约束需求地约束运输问题系数矩阵的秩为m+n-1。即运输问题有m+n-1个基变量，mn-(m+n-1)个非基变量。例如以上问题m=3，n=4，基变量为3416个，非基变量为1266个。运输问题的表格表示运输问题的表格表示运输问题的表格表示运输问题的表格表示运输问题的网络图、线性规划模型以及运输表之间的关系运输问题的网络图、线性规划模型以及运输表之间的关系网络图线性规划模型运输表节点 发点i约
22、束 前m个约束 表的行收点j后n个约束表的列边从节点i到节点j 变量xij，列向量aij 表中的一格运输问题单纯形法1、 求得一个初始基础可行解；求得一个初始基础可行解；2、 对对非非基基变变量量xij计计算算检检验验数数cij-zij，根根据据各各非非基基变变量的检验数量的检验数的的值，确定最优性或选择进基变量；值，确定最优性或选择进基变量；3、 当当进进基基变变量量xij进进基基时时，根根据据基基变变量量的的变变化化，求求出最先降为出最先降为0的基变量确定为离基变量；的基变量确定为离基变量；4、 进行基变换，获得新的基础可行解并转步骤进行基变换，获得新的基础可行解并转步骤2。 98A题题投
23、资的收益和风险投资的收益和风险试给该公司设计一种投资组合方案，即用给定的试给该公司设计一种投资组合方案，即用给定的资金，有选择地购买若干种资产或存银行生息，资金，有选择地购买若干种资产或存银行生息，使净收益尽可能大，而总体风险尽可能小使净收益尽可能大，而总体风险尽可能小。设变量设变量xi 表示存入银行和购买表示存入银行和购买Si的金额的金额yj=0表示不买表示不买Sj， yj=1表示购买表示购买Sj。投资的收益和风险的数学模型为投资的收益和风险的数学模型为这是一个双目标优化问题，可化为单目标规划问题。这是一个双目标优化问题，可化为单目标规划问题。模型1固定风险水平，优化收益模型2固定盈利水平，
24、最小化风险模型3确定投资者的风险-收益偏好参数0在上述三个模型中，选择k,h的不同水平和的不同取值进行求解就可揭示投资和风险间的相互依存关系，再根据投资者对风险的承受能力，确定投资方案。 求解中的问题求解中的问题：上述模型虽已化成单目标规划，但交易成本函数是非凸和非连续的，无法用通常的方法求解。交易费函数的简化：考虑到投资总额M相当大，若某种资产被选中，其投资额一般都超过ui ，从而交易费简化为风险度量的选择也造成了模型3求解的困难，可以用引入新变量的方法，把模型化为线性规划模型。电站建设计划电站建设计划在今后的十五年,某省的用电需求将显著增加.该省水利发电站将负责投资兴建新电站以满足增加的电
25、量需求,每年对电的需求通常由下面三个特性值确定:总电量总电量,单位为106千瓦时;保证功率保证功率,单位为103千瓦;峰值功峰值功率率,单位为103千瓦.下页表给出了以上特性值在以后的十五年应达的增加量因为电不可贮存,所以不同类型的电站的三个特性值很不相同,例如,同是一百万千瓦发电,蒸气发电峰值功率为0.30(103KW),而核发电站的保证功率和峰值功率分别为0.20(103KW)和0.25(103KW).1980年能力 1995年需求净增量总电量(106KWH)120002200010000保证功率(103KW)7200117004500峰值功率(103KW)10200170006800蒸汽
26、电站蒸汽电站 核电站核电站小型水电小型水电站站中型水电中型水电站站大型水电大型水电站站保证功率保证功率(103KW)0.150.200.100.200.80峰值功率峰值功率(103KW)0.300.250.100.400.90投资费用投资费用($103)3030406090年总费用年总费用($103)65314243100给出了在以后的十五年内欲意兴建的五座电站的功率特给出了在以后的十五年内欲意兴建的五座电站的功率特性值性值, 投资量以及年总费用所有数据都是对年输出电量投资量以及年总费用所有数据都是对年输出电量一百万千瓦时一百万千瓦时(106KWH) 而言的而言的,年总费用包括每年的建年总费用
27、包括每年的建设费用和操作费用设费用和操作费用. 而总投资不能超过而总投资不能超过730,000,000 美元美元.(1) 在最优计划中在最优计划中, 蒸汽电站蒸汽电站, 核电站核电站, 水利发电站等各水利发电站等各发电能力各为多少发电能力各为多少?(106KWH)(2) 总投资为多少总投资为多少? 年总费用为多少年总费用为多少?(3) 在计划中每供电在计划中每供电1 千瓦小时电量的平均费用为多少千瓦小时电量的平均费用为多少?(4) 在计划中生产最后一千瓦小时电的边际费用是多少在计划中生产最后一千瓦小时电的边际费用是多少?(5) 假如计划中峰值功率为假如计划中峰值功率为7000KW, 而不是而不
28、是6800KW, 则则每年费用的增加量为多少每年费用的增加量为多少?(6) 如在如在(5) 中峰值功率变为中峰值功率变为7400KW, 则如何则如何?(7) 假设该省水电局可以发行公债筹集投资费用假设该省水电局可以发行公债筹集投资费用, 最多最多发行公债发行公债$50106,年利率为年利率为13%, 问其是否采用此方问其是否采用此方式筹资式筹资? 若采用若采用, 应发行多少公债应发行多少公债? 这对年总费用将产这对年总费用将产生什么影响生什么影响?(8) 邻省欲在邻省欲在1995 年从该省购买电力年从该省购买电力5000106KWH (无保证功率和峰值功率的要求无保证功率和峰值功率的要求) 问
29、该省是否应提问该省是否应提高其发电量并出售给邻省高其发电量并出售给邻省, 若是若是, 那么每千瓦小时那么每千瓦小时的最低费用为多少的最低费用为多少? 可出售电量为多少可出售电量为多少?(9) 环境、保护工作者反对建立核电站环境、保护工作者反对建立核电站, 若不建核电若不建核电站站, 那么该省电力局建设新电站的年总费用将如何那么该省电力局建设新电站的年总费用将如何变化变化?(10) 若他们还认为大型水力发电站可能破坏自然景若他们还认为大型水力发电站可能破坏自然景色色, 要求将其发电能力限制在要求将其发电能力限制在5000(106KWH), 那么那么这对年总费用将产生什么影响这对年总费用将产生什么
30、影响?在总投资限制的前提下在总投资限制的前提下, 可对该省水利发电站建立线可对该省水利发电站建立线性规划模型以使年总费用为最小性规划模型以使年总费用为最小. 设设STEAM (x1): 蒸汽电站所发电量蒸汽电站所发电量(106KWH);NUCLFA (x2): 核电站所发电量核电站所发电量(106KWH);SMAHYD (x3): 小水电站发电量小水电站发电量(106KWH);MEDHYD (x4): 中水电站发电量中水电站发电量(106KWH);LARHYD (x5): 大水电站发电量大水电站发电量(106KWH);ANCOST (z): 为满足所需的电量增加所需的年总费为满足所需的电量增加所需的年总费用用($103);TOTELC: 计划计划15 年后的发电量年后的发电量(106KWH);GARPOW, DEAKW: 保证功率和峰值功率保证功率和峰值功率(103KW);INVEST: 总投资费用总投资费用($103). 则则LP 为为
