第4讲线性规划和非线性规划

第 4讲 线性规划和非线性规划数学建模与数学实验西南科技大学 理学院 杨学南Lingo优化软件的使用方法Lingo安装完成，启动后，可以看到如下界面算术运算负号： +(加法） -（减法） *（乘法） /(除法） (乘幂）逻辑运算符号： #AND#(与 ) #OR#(或 ) #NOT#(非 ) #EQ#(等于 ) #NE#(不等于 ) #GT#(大于 ) #GE#(大于等于 ) #LT#(小于 ) #LE#(小于等于 ) 逻辑运算的结果只有 “真 ”（ TRUE)和 “假 ”（ FALES)， Llingo用 1表示 True,其它的都是 False。关系运算符号： (=)大于等于Lingo的运算符号Lingo函数常见函数 ： abs cos exp floor(取整） lgm(自变量的gama函数的自然对数） smax(list)（ 返回列数的最大值） smin sin tan集合循环函数function(setname(set_index_list) |condition： expression_list);其中， function是集合函数名，有 for,max,min,sum四种； setname是集合名； set_index_list是集合索引列表； condition是逻辑表达式描述的条件； expresstoin_list是一个表达式 ， 对 for函数可以有一组 表达式 。for对 集合 setname的每个元素独立生成约束，约束由expression_list描述。 max、 min、 sum依次返回集合setname上的表达式的最大值、最小值、和。例 1 ： 任务分配问题：某车间有甲、乙两台机床，可用于加工三种工件。假定这两台车床的可用台时数分别为 800和 900，三种工件的数量分别为 400、 600和 500，且已知用三种不同车床加工单位数量不同工件所需的台时数和加工费用如下表。问怎样分配车床的加工任务，才能既满足加工工件的要求，又使加工费用最低？一 、线性规划解 设在甲车床上加工工件 1、 2、 3的数量分别为 x1、 x2、 x3，在乙车床上加工工件 1、 2、 3的数量分别为 x4、 x5、 x6。 可建立以下线性规划模型：解答在 lingo下编程： model: min=13*x1+9*x2+10*x3+11*x4+12*x5+8*x6; x1+x4=400; x2+x5=600; x3+x6=500; 0.4*x1+1.1*x2+x360; x1+x270; x2+x360; x3+x450; x4+x520; x5+x630; gin(x1);gin(x2);gin(x3);gin(x4); gin(x5);gin(x6); end丁的蛙泳成绩退步到 115”2； 戊的自由泳成绩进步到 57”5, 组成接力队的方案是否应该调整 ？如何选拔队员组成 4100米混合泳接力队 ?例 4 混合泳接力队的选拔 甲 乙 丙 丁 戊蝶泳 106”8 57”2 118” 110” 107”4仰泳 115”6 106” 107”8 114”2 111”蛙泳 127” 106”4 124”6 109”6 123”8自由泳 58”6 53” 59”4 57”2 102”45名候选人的 百米成绩穷举法 ： 组成接力队的方案共有 5!=120种 。目标函数若选择队员 i参加泳姿 j 的比赛，记 xij=1, 否则记 xij=0 0-1规划模型 cij(秒 )队员 i 第 j 种泳姿的百米成绩约束条件每人最多入选泳姿之一 cij i=1 i=2 i=3 i=4 i=5j=1 66.8 57.2 78 70 67.4j=2 75.6 66 67.8 74.2 71j=3 87 66.4 84.6 69.6 83.8j=4 58.6 53 59.4 57.2 62.4每种泳姿有且只有 1人 MIN 66.8x11+75.6x12+87 x13+58.6x14 +57.2x21+66 x22+66.4x23+53 x24 +78 x31+67.8x32+84.6x33+59.4x34 +70 x41+74.2x42+69.6x43+57.2x44 +67.4x51+71 x52+83.8x53+62.4x54 SUBJECT TO x11+x12+x13+x14 =1 x21+x22+x23+x24 =1 x31+x32+x33+x34 =1 x41+x42+x43+x44 =1 x51+x52+x53+x54 =1 x11+x21+x31+x41+x51 =1 x12+x22+x32+x42+x52 =1 x13+x23+x33+x43+x53 =1 x14+x24+x34+x44+x54 =1 END INT 20模型求解 输入 LINDO求解 exam0207 最优解： x14 = x21 = x32 = x43 = 1, 其它变量为 0;成绩为 253.2(秒 )=413”2 甲 乙 丙 丁 戊蝶泳 106”8 57”2 118” 110” 107”4仰泳 115”6 106” 107”8 114”2 111”蛙泳 127” 106”4 124”6 109”6 123”8自由泳 58”6 53” 59”4 57”2 102”4甲 自由泳、乙 蝶泳、丙 仰泳、丁 蛙泳 .问题 1. 如何下料最节省 ? 例 5 钢管下料 问题 2. 客户增加需求：原料钢管 :每根 19米 4米 50根 6米 20根 8米 15根 客户需求由于采用不同切割模式太多，会增加生产和管理成本，规定切割模式不能超过 3种。如何下料最节省？5米 10根 按照客户需要在一根原料钢管上安排切割的一种组合。 切割模式余料 1米 4米 1根 6米 1根 8米 1根 余料 3米 4米 1根 6米 1根 6米 1根 合理切割模式 的余料应小于客户需要钢管的最小尺寸余料 3米 8米 1根 8米 1根 钢管下料 为满足客户需要，按照哪些种合理模式，每种模式切割多少根原料钢管，最为节省？合理切割模式2. 所用原料钢管总根数最少 模式 4米钢管根数 6米钢管根数 8米钢管根数 余料 (米 )1 4 0 0 32 3 1 0 13 2 0 1 34 1 2 0 35 1 1 1 16 0 3 0 17 0 0 2 3钢管下料问题 1 两种标准1. 原料钢管剩余总余量最小xi 按第 i 种模式切割的原料钢管根数 (i=1,2,7 ) 约束 满足需求 决策变量 目标 1（总余量）按模式 2切割 12根 ,按模式 5切割 15根，余料 27米 模式4米根数6米根数8米根数余料1 4 0 0 32 3 1 0 13 2 0 1 34 1 2 0 35 1 1 1 16 0 3 0 17 0 0 2 3需求50 20 15最优解： x2=12, x5=15, 其余为 0；最优值： 27。整数约束： xi 为 整数当余料没有用处时， 通常以总根数最少为目标 目标 2（总根数）钢管下料问题 1 约束条件不变 最优解： x2=15, x5=5, x7=5, 其余为 0；最优值： 25。xi 为 整数按模式 2切割 15根，按模式 5切割 5根，按模式 7切割 5根，共 25根，余料 35米 虽余料增加 8米，但减少了 2根 与 目标 1的结果 “共切割27根，余料 27米 ” 相比 二、非线性规划min=exp(x1)*(4*x12+2*x22+4*x1*x2+2*x2+1);x1*x2-x1-x2+1.50;-x1*x2-100;free(x1);free(x2);end一、实验内容 线性规划 无约束非线性规划 约束非线性规划 多目标规划 对策论模型2018/8/15 Mathematica优化问题求解是 Mathematica系统比较薄弱的部分， 只提供了求解线性规划和无约束非线性规划的内容，相应命令分别为 LinearProgramming、FindMinimum。 MatLabMatLab的优化工具箱是其应用较广二、数学软件优化工具箱对比2018/8/15影响较大的内容，它的主要功能有：1、求解线性规划和二次规划；2、求函数的最大值和最小值；3、非线性函数的最小二乘；4、多目标优化；5、约束条件下的优化；6、求解非线性方程。MatLab优化工具箱的专有函数有 11个。2018/8/15 LindoLindo主要用于 线性规划和二次规划，其输入模式完全是手写式的。 Lingo包含了 Lindo的全部功能，是强大的优化软件 ，在关于求解优化问题的数学软件中独占鳌头，给出的综合分析报告一枝独秀 。三、线性规划1、线性规划的标准型我们将线性规划的下列形式称为