1 大学数学实验 Experiments in Mathematics 实验8 约束优化 清华大学数学科学系 约束优化基本内容:LP,QP,NLP 2. 基本原理 3. 算法和 MATLAB实现 1. 问题与模型 约束优化问题一般形式 ljxg mixhts xf j i x n ,...,1,0)( ,...,1,0)(.. )(min =≤ == ?∈ 当最优解在可行域边 界上取得时，不能用 无约束优化方法求解 1桶 牛奶 3千克 A 1 12小时 8小时 4千克 A 2 或 获利 12元 /千克 获利 8元 /千克 0.8千克 B 1 2小时 ,1.5元 1千克 获利 22元 /千克 0.75千克 B 2 2小时 ,1.5元 1千克 获利 16元 /千克 制订生产计划，使每天净利润最大 ? 15元可增加 1桶牛奶，应否投资？ 50桶牛奶 , 480小时 至多 100公斤 A 1 ? B 1 ， B 2 的获利经常有 10%的波动，对计划有无影响？ 实例 1: 奶制品生产销售计划 ? 聘用临时工人增加劳动时间，工资最多每小时几元？ 1桶 牛奶 3千克 A 1 12小时 8小时 4千克 A 2 或 获利 12元 /千克 获利 8元 /千克 0.8千克 B 1 2小时 ,1.5元 1千克 获利 22元 /千克 0.75千克 B 2 2小时 ,1.5元 1千克 获利 16元 /千克 出售 x 1 千克 A 1 , x 2 千克 A 2 ， x 3 千克 B 1 , x 4 千克 B 2 原料 供应 劳动 时间 加工能力 决策 变量 目标 函数 利润 约束 条件 非负约束 0, 61 ≥xxL x 5 千克 A 1 加工 B 1 ， x 6 千克 A 2 加工 B 2 654321 5.15.11622812 xxxxxxzMax ??+++= 50 43 6251 ≤ + + + xxxx 48022 )(2)(4 65 6251 ≤++ +++ xx xxxx 100 51 ≤+ xx 附加约束 53 80 x.x = 64 750 x.x = 50万元基金用于投资三种股票 A、 B、 C： A每股年期望收益 5元 (标准差 2元 )，目前市价 20元； B每股年期望收益 8元 (标准差 6元 )，目前市价 25元； C每股年期望收益 10元 (标准差 10元 )，目前市价 30元； 股票 A、 B收益的相关系数为 5/24; 股票 A、 C收益的相关系数为 –0.5; 股票 B、 C收益的相关系数为 –0.25。 实例2：投资组合问题 ?如期望今年得到至少20% 的投资回报，应如何投资？ ?投资回报率与风险的关系如何？ 假设： 1、基金不一定要用完（不用不计利息或贬值） 2、风险通常用收益的方差或标准差衡量 决策变量 x 1 、 x 2 和 x 3 分别表示投资 A、 B、 C的数量 （国内股票通常以 “一手 ”（ 100股）为最小单位出售， 这里以 100股为单位，期望收益以百元为单位） 实例2：投资组合问题 A、 B、 C每手 (百股 )的收益分别记为 S 1 ,S 2 和 S 3 (百元 )： ES 1 =5, ES 2 =8, ES 3 =10， DS 1 =4, DS 2 =36, DS 3 =100， r 12 =5/24, r 13 =-0.5， r 23 =-0.25 总收益 S=x 1 S 1 +x 2 S 2 +x 3 S 3 ：是一个随机变量 15),cov( 10),cov( 25),cov( 322332 311331 211221 ?== ?== == DSDSrSS DSDSrSS DSDSrSS 2 投资风险（总收益的方差）为 实例2：投资组合问题 总期望收益为 Z 1 =ES= x 1 ES 1 +x 2 ES 2 +x 3 ES 3 =5x 1 +8x 2 +10x 3 总收益 S=x 1 S 1 +x 2 S 2 +x 3 S 3 ：是一个随机变量 323121 2 3 2 2 2 1 32323131 21213 2 32 2 21 2 1 332233112211 3322113322112 30205100364 ),cov(2),cov(2 ),cov(2 ),cov(2),cov(2),cov(2 )()()()( xxxxxxxxx SSxxSSxx SSxxDSxDSxDSx SxSxSxSxSxSx SxDSxDSxDSxSxSxDZ ??+++= ++ +++= +++ ++=++= 二次规划（ QP）模型 实例2：投资组合问题 s.t. 5x 1 +8x 2 +10x 3 ≥ 1000 20x 1 +25x 2 +30x 3 ≤ 5000 x 1 ， x 2 ， x 3 ≥ 0 323121 2 3 2 2 2 12 30205100364min xxxxxxxxxZ ??+++= 通过试探发现 β 从 0.0001~0.1以 0.0001的步长变 化就可以得到很好的近似结果 Min Z =β Z 2 - Z 1 s.t. 20x 1 +25x 2 +30x 3 ≤ 5000 x 1 ， x 2 ， x 3 ≥ 0 加权 模型 实例3：供应与选址 某公司有 6个建筑工地，位置坐标为 (a i , b i ) (单位：公里 ), 水泥日用量 d i (单位：吨） i １２３４５６ a 1.25 8.75 0.5 5.75 3 7.25 b 1.25 0.75 4.75 5 6.5 7.75 d 3547 1 1)现有 2 料场，位于 A (5, 1), B (2, 7), 记 (x j ,y j ),j=1,2, 日储量 e j 各有 20 吨。 假设： 料场和工地之间有直线道路 目标： 制定每天的供应计划，即从 A, B 两料场分别 向各工地运送多少吨水泥，使总的吨公里数最小。 2,1, 6,...,1,.. ])()[(min 6 1 2 1 2 1 6 1 2/122 =≤ == ?+? ∑ ∑ ∑∑ = = == jec idcts byaxc jij i iij j ji ijijij 线性规划模型 决策变量： c ij (料场 j到工地 i的 运量） ~12维 2） 改建两个新料场，需要确定新料场位置 (x j ,y j )和 运量 c ij ，在其它条件不变下使总吨公里数最小。 2,1, 6,...,1,.. ])()[(min 6 1 2 1 2 1 6 1 2/122 =≤ == ?+? ∑ ∑ ∑∑ = = == jec idcts byaxc jij i iij j ji ijijij 决策变量： c ij， (x j ,y j )~16维 非线性规划模型 约束优化问题的分类 ? 线性规划 (LP) 目标和约束均为线性函数 ? 非线性规划 (NLP) 目标或约束中存在非线性函数 9二次规划 (QP) 目标为二次函数、约束为线性 ? 整数规划 (IP) 决策变量 (部分 )为整数 9整数 线性 规划 (ILP) 9整数 非线性 规划 (INLP) 3 求解线性规划 (LP)的基本原理 基本模型 0,.. ,min)max( ≥≤ ∈= xbAxts Rxxczor nT mnmn RbRARc ∈∈∈ × ,, ?二维线性规划的图解法 ?一般线性规划的单纯形算法 ?一般线性规划的内点算法 二维线性规划的图解法 x 2 x 1 0 L 1 L 2 L 3 z 1 =0 z 2 =2 z 3 =6 z 4 =10 z 5 =13 grad z x* * 起作用约束： L 2 ;L 3 最优解（ 4， 1），最优值 z max =13 ~L 1 ~L 2 ~L 3 0, 1423 22 2.. 3max 21 21 21 21 21 ≥ ≤+ ≤? ≤+? += xx xx xx xxts xxz 2 21 ?≥? xx 求解 LP的基本思想 从可行域的某一顶点开始，只需在有限多个顶点中 一个一个找下去，一定能得到 最优解 。 LP的约束和目标函数均为线性函数 2维 可行域 线段组成的凸多边形 目标函数 等值线为直线 最优解 凸多边形的某个顶点 n维 超平面组成的凸多面体 等值线是超平面 凸多面体的某个顶点 算法：怎样从一点转到下一点，尽快找到最优解。 x 2 x 1 0 L 1 L 2 L 3 x 2 x 1 0 L 1 L 2 L 3 x 2 x 1 0 L 1 L 2 求解LP的特殊情形 ~L 1 ~L 2 ~L 3 无可行解 无最优解 (无界 ) 最优解不唯一 321 ~4123 Lxx ≥+? 3 L无 x 2 x 1 0 L 1 L 2 L 3 z=c 0, 1423 22 2.. 3max 21 21 21 21 21 ≥ ≤+ ≤? ≤+? += xx xx xx xxts xxz 2 21 ?≥? xx 321 ~413 Lxx ≤+ 线性规划的标准形和基本性质 nmRA xbAxts xcz nm T ≤∈ ≥= = × , 0,.. min 标 准 形 加入松弛变量 /剩余变量将不等式变为等式 0, 0,1423 0,22 0003min 21 5521 4421 54321 ≥ ≥=++ ≥=+? ?+?+?+??= xx xxxx xxxx xxxxxz 0,2.. 3321 ≥=++? xxxxts 0, 1423 22 2.. 3max 21 21 21 21 21 ≥ ≤+ ≤? ≤+? += xx xx xx xxts xxz 2 21 ?≥? xx 0,,,, ,1423 ,22 2.. 0003min 54321 521 421 321 54321 ≥ =++ =+? =++? ?+?+?+??= xxxxx xxx xxx xxxts xxxxxz 0,,,, ,1423 ,22 2 54321 521 421 321 ≥ =++ =+? =++? xxxxx xxx xxx xxx 对标准形求解 先求可行解 nmRA xbAxts xcz nm T ≤∈ ≥= = × , 0,.. min 0, ≥= xbAx 满足 再在有限个可行解中寻找最优解 4 1423 22 2 521 421 321 =++ =+? =++? xxx xxx xxx ? ? ? ? ? ? ? ? ? ? ? ? = 10023 01021 00111 A 可 逆， BNBA ],[? ],[ T N T B T xxx ? bNxBxAx NB =+= ][ 54321 ppppp= bBxx BN 1 0 ? =?= x 2 x 1 O T xpppB )14,2,2,0,0(][ 543 =?= T xpppB )8,0,4,0,2(][ 531 =?= T xpppB )16,0,3,1,0(][ 532 ?=?= O点 Q点 R点 Q R 基本可行解 x ： Ax=b, x ≥0 (x B ≥0， x N =0) T xpppB )0,0,5,1,4(][ 321 =?= P点 P 可行域存在时，必是凸多面体； 可行解对应于可行域的顶点； 最优解存在时，必在可行域的顶点取得。 LP基本性质 最优解只需在有限个可行解中寻找 单纯形法的基本思路是 从一个顶点转换到另一个顶点（即构成 x B 和 x N 的 向量 p i 间的转换），使目标函数下降最多。 LP的通常解法是单纯形法 内点法 (Interior point method) 20世纪 80年代人们提出的一类新的算法 ——内点算 法也是迭代法，但不再从可行域的一个顶点转换到另一 个顶点，而是直接从可行域的内部逼近最优解。 LP其他算法 有效集 (Active Set)方法 线性规划是二次规划的一个特例（只需令所有二次 项为零即可），因此也可以用二次规划的算法（如有效 集方法，详见下节关于二次规划的介绍）解线性规划 [x,fval,exitflag,output,lambda] = linprog(c,A1,b1,A2,b2,v1,v2,x0,options) MATLAB 求解 LP 212211 ,,.. min vxvbxAbxAts xcz T ≤≤=≤ = 输入： x0~初始解(缺省时为0) options ~ MATLAB控制参数 中间所缺参数项补[] 输出： lambda ~ Lagrange乘子， 维数等于约束个数，非零分 量对应于起作用约束 ? lambda.ineqlin ? lambda. eqlin ? lambda. upper ? lambda. lower Exam0802.m MATLAB 求解 LP options ~ MATLAB控制参数: 三种 算法选择 ? 缺省时采用大规模算法（是一种内点算法）； ? 当 opt中 “LargeScale”参数设置为 “off”时，采用中规模算法， 该模式下缺省的算法是二次规划的算法（一种有效集方法）； ? 当 opt中 “LargeScale”参数设置为 “off”，并且 “Simplex”参数设 置为 “on”时，采用单纯形算法。 只有有效集方法可以由用户提供初始解 x0，其他两个算法则不 需要（即使提供了也会被忽略）。 Exam0801.m c=[12 8 22 16 -1.5 -1.5]; A1=[4 3 0 0 4 3;2 1 0 0 3 2;1 0 0 0 1 0]; b1=[600 240 100]; A2=[0 0 1 0 -0.8 0;0 0 0 1 0 -0.75]; b2=[0 0]; v1=[0 0 0 0 0 0]; [x,z0,ef,out,lag]=linprog(-c,A1,b1,A2,b2,v1) lag.ineqlin, lag.eqlin 实例 1: 奶制品生产销售计划 654321 5.15.11622812 xxxxxxzMax ??+++= 50 43 6251 ≤ + + + xxxx 48022)(2)(4 656251 ≤+++++ xxxxxx 100 51 ≤+ xx 08.0 53 =? xx 075.0 64 =? xx 0 654321 ≥x,x,x,x,x,x 6003434 6521 ≤+++ xxxx 240232 6521 ≤+++ xxxx x=(0,168,19.2,0,24,0) ; z = -z0 =1730.4; lag.ineqlin =(1.58;3.26; 0.00) ; … shili0801.m 5 ? 15元可增加 1桶牛奶，应否投资？ 实例 1: 奶制品生产销售计划 654321 5.15.11622812 xxxxxxzMax ??+++= 50 43 6251 ≤ + + + xxxx 48022)(2)(4 656251 ≤+++++ xxxxxx 100 51 ≤+ xx 53 80 x.x = 64 750 x.x = 0 654321 ≥x,x,x,x,x,x x=(0,168,19.2,0,24,0) ; z = -z0 =1730.4 lag.ineqlin =(1.58;3.26; 0.00) ; … 6003434 6521 ≤+++ xxxx 601 z1=1731.98 z1-z = 1731.98-1730.4=1.58 z1=lag.ineqlin(1) z1*12=1.58*12= 18.96>15 应该投资！ “影子价格 ” 实例 1: 奶制品生产销售计划 ? 聘用临时工人增加劳动时间，工资最多每小时几元？ 654321 5.15.11622812 xxxxxxzMax ??+++= 50 43 6251 ≤ + + + xxxx 48022)(2)(4 656251 ≤+++++ xxxxxx 100 51 ≤+ xx 53 80 x.x = 64 750 x.x = 0 654321 ≥x,x,x,x,x,x x=(0,168,19.2,0,24,0) ; z = -z0 =1730.4 lag.ineqlin =(1.58;3.26; 0.00) ; … 6003434 6521 ≤+++ xxxx 240232 6521 ≤+++ xxxx lag.ineqlin(2)=3.26， 所以 1小时劳动时间的影 子价格应为 3.26/2=1.63， 即单位劳动时间增加的利 润是 1.63(元 ) ? B 1 ， B 2 的获利经常有 10%的波动，对计划有无影响？ 实例 1: 奶制品生产销售计划 654321 5.15.11622812 xxxxxxzMax ??+++= 50 43 6251 ≤ + + + xxxx 48022)(2)(4 656251 ≤+++++ xxxxxx 100 51 ≤+ xx 53 80 x.x = 64 750 x.x = 0 654321 ≥x,x,x,x,x,x x=(0,168,19.2,0,24,0) ; z = -z0 =1730.4 lag.ineqlin =(1.58;3.26; 0.00) ; 若每公斤 B1的获利下降 10%, 应将目标函数中 x 3 的系数改 为 19.8，重新计算发现最优 解和最优值均发生了变化 若 B2的获利向上波动 10%， y 原计划也不再是最优的 MATLAB没有给出这种敏 感性分析的结果（ LINDO 和 LINGO软件可以给出） NLP基本原理(不等式约束) ljxgts xfz j x n ,...,1,0)(.. )(min =≤ = ?∈ ?g 1 d g 2 =0 g 1 =0 g 3 =0 g j <0 o x 设 x为可行解， 位于约束边界 1 ,0)( Jjxg j ∈= J 1 ~起作用约束 (j=1) 2 ,0)( Jjxg j ∈< J 2 ~不起作用约束 (j=2,3) )0( 0 λλλ <<∈+ Gdx 可行方向 d 下降方向 d )0()()( 0 λλλ <<<+ xfdxf (G) )1()(0)( 1 Jjdxg T j ∈<? )2(0)( <? dxf T )()()()( 2 λλλ Odxgxgdxg T jjj +?+=+ 若 x沿 d方向既可行又下降，则 x不是最优解 最优解的必要条件 0)()( 1 =?+? ∑ = xgxf j l j i λ ljxg jj L,2,1,0)( ==λ ~KKT条件 互补性条件 ljxg mixhts xf j i x n ,...,1,0)( ,...,1,0)(.. )(min =≤ == ?∈ ，和则存在 线性无关， 0 )(, 1 ≥ ∈?? ji ji Jjgh λμ 0)()()( 11 =?+?+? ∑∑ == xgxhxf j l j i m i ii λμ ljxg jj L,1,0)( ==λ x为最优解 不存在满足 (1),(2)的 d )1()(0)( 1 Jjdxg T j ∈<? )2(0)( <? dxf T 0, 1 ≥ l λλL)()( 1 Jjxg j ∈? 且 线性无关，则存在 若 x为最优解， KKT条件的几何解释 Q P ?f -?g 1 -?g 2 ?f -?g 1 -?g 2 0)( 04)( 010)(.. )3()7()(min 23 212 2 2 2 11 2 2 2 1 ≥= ≤?+= ≤?+= ?+?= xxg xxxg xxxgts xxxf 0)()( 1 =?+? ∑ = xgxf j l j i λ ljxg jj L,2,1,0)( ==λ x 2 x 10 最优解在 P(3,1)取得 0)(2)()( ,0,2,1 21 321 =?+?+? === PgPgPf λλλ P(3,1)是 KKT点 其它点 (如 Q)均不是 ? (7,3) 6 二次规划(QP)及有效集方法 bAxts cxHxxxf T ≤ += .. 2 1 )(min 当 H为对称阵，称二次规划 当 H正定时，称凸二次规划 凸二次规划性质 ： 最优点 ?KKT点； 局部最优解 ?全局最优解； mTT RbAxcxHxxxL ∈?++= λλλ ),( 2 1 ),( 最优解方程 0 0 =? =++ bAx AcHx TT λ L函数 等式约束 下 的 Lagrange乘子法 bAx = 解二次规划的有效集方法 基本思想： 对于不等式约束的二次规划，在某可行点 处将不起作用约束去掉， 起作用约束视为等式约束 ， 通过求解等式约束的二次规划来改进可行点。 ? 若 x为 (1)的最优解，则它也是 (2)的最优解 ? 若 x为 (1)的可行解，又是 (2)的 KKT点，且 L—乘子非负，则它必是 (1)的最优解。 bAxts cxHxxxf T ≤ += .. 2 1 )(min (1) 1 ,.. 2 1 )(min Jjbxats cxHxxxf jj T ∈= += )( 列的第是 jAa j (2) 基本 原理 *,0.. )*()*()*( 2 1 )*(min Jjdats dxcdxHdxdxf j T ∈= ++++=+ 若 d*≠0，以此为方向确定步长 α*使得 ap(x*+α*d*)=bp， p?J*，则有效集修正为 J*∪{p}。 设 (1)的可行点为 x*，有效集 记作 J*，用 L—乘子法求解 : 基本步骤 得 d*, λ* ? 若 d*=0, 则 x*为 (2)最优解 ; 当 λ *非负时 x*是 (1)最优解 若 d*=0, 且 (λ *)q<0, q∈J* , 则 x*不是最优解 , 有效集修正为 J*\{q} 。 有效集 修正 MATLAB求解QP [x,fval,exitflag,output,lambda] = quadprog(H,c,A1,b1,A2,b2,v1,v2,x0,options) 212211 2 1 ,,.. min vxvbxAbxAts xcHxxz TT ≤≤=≤ += 0,2 33 32 32.. 3332),(min 21 21 21 21 21 2 221 2 121 ≤≥ ≤? ?≥? =+ +?+?= xx xx xx xxts xxxxxxxxf Exam0803.m ]Inf,0[2],Inf,2[,3),2,1( , 3 3 , 31 12 1 3 , 63 34 122 11 =?=== ? ? ? ? ? ? ? ? = ? ? ? ? ? ? ? ? ? ? = ? ? ? ? ? ? ? ?? = ? ? ? ? ? ? ? ? ? ? = vvbA bA cH 解得 x = 1.0e+002 *（ 1.3111， 0.1529， 0.2221） 如果一定要整数解，可以四舍五入到（ 131， 15， 22） 如利用 LINGO软件 ,可得整数最优解 (132， 15， 22) 用去资金为 132×20+15×25+22×30 = 3675（百元） 期望收益为 132×5+15×8+22×10 = 1000（百元） 风险 (方差 )为 68116，标准差约为 261（百元） 实例2：投资组合问题 s.t. 5x 1 +8x 2 +10x 3 ≥ 1000 20x 1 +25x 2 +30x 3 ≤ 5000 x 1 ， x 2 ， x 3 ≥ 0 323121 2 3 2 2 2 12 30205100364min xxxxxxxxxZ ??+++= portfolio1.m 通过试探发现 β 从 0.0001~0.1以 0.0001的 步长变化就可以得到 很好的近似结果 实例2：投资组合问题 Min Z =β Z 2 - Z 1 s.t. 20x 1 +25x 2 +30x 3 ≤ 5000 x 1 ， x 2 ， x 3 ≥ 0 加权 模型 0 200 400 600 800 1000 1200 1400 1600 1800 0 100 200 300 400 500 600 700 800 900 预期收益(百元) 均方差（百元） 投资股票 A、 B、 C分别 为 153、 35、 35（手） portfolio2.m 7 非线性规划(NLP)的解法 可行方向法、罚函数法、梯度投影法 ... 逐步二次规划法 (Sequential Quadratic Programming) SQP的基本原理 构造 LNP的拉格朗日函数 )()()(),,( 11 xgxhxfxL j l j j m i ii ∑∑ == ++= λμλμ ljxg mixhts xf j i x n ,...,1,0)( ,...,1,0)(.. )(min =≤ == ?∈ 用二次函数近似 L(x,μ,λ), NLP化为 QP, 再解一系列 QP子问题。 QP子 问题 ljxgdxg mixhdxhts dxfdGd kj T kj ki T ki T kk T L L ,1,0)()( ,1,0)()(.. )( 2 1 min =≤+? ==+? ?+ k x 是第 k 次迭代的初始点， k G 是海赛阵 L 2 ? 的近似。 ? 求解 QP子问题，得 d k ； 将最优解 d k 作为迭代的搜索方向，令 kkkk dxx α+= +1 SQP的 基本步骤 ? 确定矩阵 G k 的迭代公式。 ? 用线性搜索计算迭代步长 α k ； MATLAB求解 约束NLP [x,fval,exitflag,output,lambda,grad,hessian] = fmincon(@fun,x0,A1,b1,A2,b2,v1,v2,@nlcon,options,P1,P2, ...) fun.m给出函数 f，当 GradObj=‘on’时必须给出 f的梯度， Hessian=‘on’时还必须给出其 Jacobi矩阵，形式为 212211 21 ,, ,0)(,0)(.. )(min vxvbxAbxA xcxcts xfz ≤≤=≤ =≤ = function [f,g,H] = fun(x) f = ... % objective function value if nargout > 1 g = ... % gradient of the function if nargout > 2 H = ... % Hessian end nlcon.m给出约束 ,GradConstr=‘on’时还给出梯度 ,形式为 212211 21 ,, ,0)(,0)(.. )(min vxvbxAbxA xcxcts xfz ≤≤=≤ =≤ = function [c1,c2,GC1,GC2] = nlcon(x) c1 = ... % nonlinear inequalities at x c2 = ... % nonlinear equalities at x if nargout > 2 GC1 = ... % gradients of c1 GC2 = ... % gradients of c2 end MATLAB求解 约束NLP 例 4 Exam0804.m )12424(min 221 2 2 2 1 1 ++++ xxxxxe x 010,05.1 212121 ≥+≤+?? xxxxxx 01 2 2 1 =?+ xx 用例中数 据计算， 最优解为 i 123456 1i c （料场 A） 350701 2i c （料场 B） 0040610 总吨公里数为 136.2 2,1, 6,...,1,.. ])()[(min 6 1 2 1 2 1 6 1 2/122 =≤ == ?+? ∑ ∑ ∑∑ = = == jec idcts byaxc jij i iij j ji ijijij 线性规划模型 决策变量： c ij (料场 j到工地 i的 运量） ~12维 Shili0803lin.m 实例3: 供应与选址 结果： 总吨公里数为 85.3，比使用原料场减少了 50.9。 初始点的选择 实例3: 供应与选址 2,1, 6,...,1,.. ])()[(min 6 1 2 1 2 1 6 1 2/122 =≤ == ?+? ∑ ∑ ∑∑ = = == jec idcts byaxc jij i iij j ji ijijij 决策变量： c ij， (x j ,y j )~16维 用现料场总吨公里数为 136.2 改建两个新料场 局部最优解问题 Shili0803.m; shili083fun.m 8 2 6 1 1 6 1 2/12 2 2 2 6 1 2/12 1 2 1 )(, 6,1,.. }])())[(( ])()[({min ecdec idcts byaxcd byaxc i iii i ii iiii i iii ≤?≤ =≤ ?+??+ ?+? ∑∑ ∑ == = L 决策变量： c i ， (x j ,y j )~10维 计算方法的改善 局部最优解问题有所改进 Shili0803n.m; shili083fun1.m i 12345 6 新料场位置（ ), jj yx 1i c 30476 0 （ 3.2552 5.6528） 2i c 050001 （ 7.2497 7.7499） +为工地 , 数字为用量 ; *为新料场 , 数字为供应量。 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 3 5 4 7 6 11 20 16 实验 目的 1）掌握用MATLAB优化工具包解线性规划和 非线性规划(包括二次规划)的方法； 2）练习建立实际问题的线性规划和非线性 规划模型。 实验 内容 课上布置，或参见网络学堂 布置实验内容