10.应用MATLAB软件求解线性规划

应用MATLAB软件求解线性规划11minzs.t.CXAXbAXblbXub(1)•MATLAB（MATrixLABoratory）的基本含义是矩阵实验室，它是由美国MathWorks公司研制开发的一套高性能的集数值计算、信息处理、图形显示等于一体的可视化数学工具软件。它是建立在向量、数组和矩阵基础之上的，除了基本的数值计算、数据处理、图形显示等功能之外，还包含功能强大的多个“工具箱”，如优化工具箱（optimizationtoolbox）、统计工具箱、样条函数工具箱和数据拟合工具箱等都是优化计算的有力工具。在这里仅介绍用MATLAB6.5优化工具箱求解线性规划问题。•一般线性规划问题的数学模型为•其中C是目标函数的系数行向量（常数）,X是n维列向量（决策变量），A,A1是常数矩阵，b,b1是常数向量，lb,ub是n维列向量分别表示决策变量X的下界与上界。•在Matlab优化工具箱（OptimizationToolbox）中，求解(1)的程序如下：[x，fval，exitflag，output，lambda]=linprog(c，A，b，Aeq，beq，lb，ub，x0，options)•说明：(1)A是不等式约束的系数矩阵，b是相应的常数列向量，若没有不等式约束，则均用[]代替；•(2)Aeq是等式约束的系数矩阵，beq是相应的常数列向量，若没有等式约束，则均用[]代替；•(3)如果某个变量无下界，则用-inf表示；如果某个变量无上界，则用inf表示，若决策变量无下界，则lb用[]代替；若决策变量无上界，则ub用[]代替；•(4)x0是线性规划的初始解，这种设计仅对中规模算法有效，通常可以缺省。•(5)输出是最优解，fval是最优值。•(6)输出exitflag描述了程序的运行情况，若其值大于零，表示程序收敛到最优解；若其值等于零，表示计算达到了最大次数；若其值小于零，表示问题无可行解，或程序运行失败。•(7)输出output表示程序运行的某些信息，如迭代次数(iterations)、所用算法(algorithm)、共轭梯度(cgiterations)等。•(8)lambda表示解处的拉格朗日乘子，其中lower，upper，ineqlin，eqlin分别对应于下界、上界、不等式约束与等式约束。例3用MATLAB解线性规划问题123123123123123226442212005minzxxxxxxxxxs.t.xxxx,x,x（2）解Matlab程序如下:c=[-2,-1,1];A=[1,4,-1;2,-2,1];b=[4;12];Aeq=[1,1,2];beq=6;lb=[0,0,-inf];ub=[inf,inf,5];[x,z]=linprog(c,A,b,Aeq,beq,lb,ub)运行后得到输出Optimizationterminatedsuccessfully.x=4.66670.00000.6667z=-8.6667例4用MATLAB求解线性规划问题123123123max2357..25100,1,2,3izxxxxxxstxxxxi（3）解首先转化为求最小值问题123123123min2357..25100,1,2,3izSxxxxxxstxxxxiMatlab程序如下c=[-2,-3,5];A=[-2,5,-1];b=-10;Aeq=[1,1,1];beq=[7];lb=[0,0,0];[x,z]=linprog(c,A,b,Aeq,beq,lb)运行后得到输出x=6.42860.57140.0000z=-14.5714键入s=-z运行后得到原问题的目标函数最大值s=14.5714用MATLAB求解例2的程序与输出结果为：c=[0.2,0.7,0.4,0.3,0.5];A=[-0.3,-2,-1,-0.6,-1.8;-0.1,-0.05,-0.02,-0.2,-0.05;-0.05,-0.1,-0.02,-0.2,-0.08;1,1,1,1,1];b=[-60;-3;-8;52];lb=[0,0,0,0,0];[x,z]=linprog(c,A,b,[],[],lb)Optimizationterminatedsuccessfully.x=0.000012.00000.000030.000010.0000z=22.4000习题11.建立下列线性规划问题的数学模型（1）某工厂生产A、B、C三种产品，三种产品对于材料费用、劳动力和电力的单位消耗系数，资源限量和单位产品价格如表1.1所示。问应如何确定生产计划可使得总产值达到最大？建立线性规划问题的数学模型。表1.1生产计划问题的数据产品资源ABC资源限量材料费用（元）22.54320劳动力（人天）618640电力（度）5510750单位价格（百元）6410（2）某疗养院营养师要为某类病人拟订一周的菜单。可供选择的蔬菜及其费用和所含营养成分的数量以及这类病人每周所需各种营养成分的最低数量如表1.2所示。另外，为了口味的需要，规定一周内所用卷心菜不多于2份，其他蔬菜不多于4份。若病人每周需要14份蔬菜，问选用每种蔬菜各多少份，可使生活费用最小。建立线性规划问题的数学模型。表1.2食谱问题的数据蔬菜每份蔬菜所含营养成分费用（元/份）铁(mg)磷(mg)VA(单位)VC(mg)烟酸(mg)青豆0.451041580.31.5胡萝卜0.4528906530.351.5花菜1.05502550530.62.4卷心菜0.42575270.150.6甜菜0.5221550.251.8土豆0.57523580.81.0每周营养最低需求量6.0325175002455.0123123(3)1000,,,,BBBAAA某农场承包亩土地，因土壤等自然条件不同，。现要在三类地上种植三种作物。各土地的面积、各类作物的计划播种面积以及各种作物在各种土地上的亩产量如表1.3所示。问应如何因地制宜安排作物布局才使总产量最大？建立线性规划问题的数学模型。播种计划表亩产量表土地作物作物面积100600700500500800500850400400150300土地面积2003005001A2A3A1B2B3B3B2B1B（4）某糖果厂用原料A、B、C加工成三种不同牌号的糖果甲、乙、丙，已知各种牌号的糖果中A、B、C的含量，原料成本，各种原料的每月限制用量，三种牌号糖果的单位加工费及售价如表1.4所示，问该厂每月应生产这三种牌号的糖果各多少千克，使该厂获利最大？试建立这个问题的线性规划数学模型。%60%15%20%60%50甲乙丙原料成本(元/千克)每月限制用量（千克）A8.002000B6.002500C4.001200加工费（元/千克）2.01.61.2售价（元）13.611.49表1.4糖果厂生产计划数据表(5)1.5yx已知一个量依赖于另一个量，现收集有数据如表。0.00.51.01.51.92.53.03.54.04.51.00.90.71.52.02.43.22.02.73.55.05.56.06.67.07.68.59.010.01.04.03.62.75.74.66.06.87.3xyxy表1.5随变化的数据表xy求拟合以上数据的直线，目标为使y的各个观察值同按直线关系所预期的值的绝对偏差总和为最小（即：误差绝对值之和最小）。建立线性规划问题的数学模型。（提示：对任意的，令：那么，）abxyi110022iiiiiiuv，，iiiiiiuvuv，2.将下列线性规划问题化成标准形无限制32121321321321,0,306460682032..minxxxxxxxxxxxtsxxxS(1)无限制321321321321321,0,159761357195..532maxxxxxxxxxxxxxtsxxxS(2)3.用图解法求解下列线性规划问题12121212max233624..212,0Sxxxxstxxxx(1)1212121212min4223..33,0Sxxxxxxstxxxx(2)12121221212max393224..6250,0Sxxxxxxstxxxxx(3)1212121212max4103121..1,0Sxxxxxxstxxxx(4)12121212min2..31,0Sxxxxstxxxx(5)4.试将下述问题改写成线性规划问题1211112maxmin,,,1..0,1,2,,mmmiiiiiniiiimiaxaxaxxxxstxim(1)(2)()(1)(2)()()max,,()()max,,kkLPSLPLPSLP如果，，，都是线性规划问题：的可行解，则它们的任意凸组合也是的可行解；如果，，，都是线性规划问题：的最优解，则它们的任意凸组合也是()的最优解。5.xxxcxAxbxoxxxcxAxbxo*()max,,0(1)max()(2)1(3)maxLPSkSkkSkk如果是线性规划问题：的最优解，为某个常数，分别讨论以下情况时最优解的变化：目标函数变为，约束条件不变；目标函数不变，约束条件变为；目标函数变为约束条件变为。6.xcxAxbxocxAxbcx,Axb0***07.max,,max,,()()0*SScxx若线性规划问题的最优解，的最优解。证明：cxAxbxoxcxAxbxoxc8.用单纯形方法求解下列线性规划问题0,,6242.2max32121321321xxxxxxxxtsxxxS(1)0,,201022603.2max321321321321321xxxxxxxxxxxxtsxxxS(2)0,0,0242126042.61314max321321321321xxxxxxxxxtsxxxS(3)0,0,018216441022.46max321321321321321xxxxxxxxxxxxtsxxxS(4)9．某工厂在计划期内要安排甲、乙两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制和每单位产品的获利如表1.6。问工厂应分别生产甲、乙产品多少单位才能使工厂获利最大？建立线性规划问题数学模型，并用单纯形方法求出最优解。产品资源甲乙资源限制设备11300台时原料A21400千克原料B01250千克单位产品获利50元100元表1.6资源配置问题的数据10.对于线性规划问题：0,,,52max432143214321xxxxxxxxxxxxS（1）求该线性规划问题的全体基本最优解；（2）确定任意最优解的表达式。11.用两阶段法求解线性规划问题。0,,10527.532max321321321321xxxxxxxxxtsxxxS(1)0,,52010651535.765min321321321321321xxxxxxxxxxxxtsxxxS(2)12312312123min23428.326,,0Sxxxxxxstxxxxx(3)123123123123123max101512539561515.25,,0Sxxxxxxxxxstxxxxxx