第三讲数学规划模型

数学规划模型

实际问题中的优化模型x~决策变量f(x)~目标函数gi(x)0~约束条件决策变量个数n和约束条件个数m较大最优解在可行域的边界上取得数学规划线性规划非线性规划整数规划重点在模型的建立和结果的分析优化模型的简单分类

线性规划(LP)目标和约束均为线性函数

非线性规划(NLP)目标或约束中存在非线性函数

二次规划(QP)目标为二次函数、约束为线性

整数规划(IP)决策变量(全部或部分)为整数整数线性规划(ILP)，整数非线性规划(INLP)一般整数规划，0-1（整数）规划连续优化离散优化数学规划例1加工奶制品的生产计划获利24元/公斤1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利16元/公斤50桶牛奶时间480小时甲设备至多加工100公斤A1

制订生产计划，使每天获利最大每天：线性规划模型1桶牛奶3公斤A1

12小时8小时4公斤A2

或获利24元/公斤获利16元/公斤x1桶牛奶生产A1

x2桶牛奶生产A2

获利24×3x1

获利16×4x2

原料供应

劳动时间

加工能力

决策变量

目标函数

每天获利约束条件非负约束

线性规划模型(LP)时间480小时至多加工100公斤A1

50桶牛奶每天模型求解

软件实现

LINGOmodel:max=72*x1+64*x2;[milk]x1+x2<50;[time]12*x1+8*x2<480;[cpct]3*x1<100;end

Globaloptimalsolutionfound.Objectivevalue:3360.000Totalsolveriterations:2

VariableValueReducedCost

X120.000000.000000X230.000000.000000RowSlackorSurplusDualPrice13360.0001.000000MILK0.00000048.00000TIME0.0000002.000000CPCT40.000000.000000

20桶牛奶生产A1,30桶生产A2，利润3360元.如何装运，使本次飞行获利最大？

三个货舱最大载重(t),最大容积(m3)

例2货机装运

重量（t）体积(m3/t）利润（元/t）货物1184803100货物2156503800货物3235803500货物4123902850三个货舱中实际载重必须与其最大载重成比例.

前仓：10；6800中仓：16；8700后仓：8；5300飞机平衡WET=(10,16,8),VOL=(6800,8700,5300);w=(18,15,23,12),v=(480,650,580,390),p=(3100,3800,3500,2850).已知参数i=1,2,3,4（货物）j=1,2,3(分别代表前、中、后仓)货舱j的重量限制WETj体积限制VOLj第i种货物的重量wi，单位重量的体积vi，利润pi货机装运决策变量

xij--第i种货物装入第j个货舱的重量(t）i=1,2,3,4,

j=1,2,3(分别代表前、中、后仓)模型假设每种货物可以分割到任意小；货机装运每种货物可以在一个或多个货舱中任意分布；多种货物可以混装，并保证不留空隙；所给出的数据都是精确的，没有误差.

模型建立货舱容积

目标函数(利润)约束条件货机装运模型建立货舱重量

10；680016；87008；5300xij--第i种货物装入第j个货舱的重量约束条件平衡要求

货物供应

货机装运模型建立10；680016；87008；5300xij--第i种货物装入第j个货舱的重量j,k=1,2,3;j≠k

!定义集合及变量;sets:cang/1..3/:WET,VOL;wu/1..4/:w,v,p;link(wu,cang):x;endsets!对已知变量赋值;data:WET=10,16,8;VOL=6800,8700,5300;w=18,15,23,12;v=480,650,580,390;p=3100,3800,3500,2850;enddatamax=@sum(wu(i):p(i)*@sum(cang(j):x(i,j)));@for(wu(i):@sum(cang(j):x(i,j))<w(i));@for(cang(j):@sum(wu(i):x(i,j))<WET(j));@for(cang(j):@sum(wu(i):v(i)*x(i,j))<VOL(j));@for(cang(j):

@for(cang(k)|k#GT#j: !#GT#是大于等于的含义; @sum(wu(i):x(i,j)/WET(j))=@sum(wu(i):x(i,k)/WET(k))););END货机装运LINGO程序

Globaloptimalsolutionfound.Objectivevalue:121515.8Totalsolveriterations:12VariableValueReducedCostX(1,1)0.000000400.0000X(1,2)0.00000057.89474X(1,3)0.000000400.0000X(2,1)7.0000000.000000X(2,2)0.000000239.4737X(2,3)8.0000000.000000X(3,1)3.0000000.000000X(3,2)12.947370.000000X(3,3)0.0000000.000000X(4,1)0.000000650.0000X(4,2)3.0526320.000000X(4,3)0.000000650.0000货物2：前仓7,后仓8；

货物3:前仓3,中仓13；货物4:中仓3.货机装运模型求解最大利润约121516元如果生产某一类型汽车，则至少要生产80辆，那么最优的生产计划应作何改变？例1汽车厂生产计划汽车厂生产三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求，利润及工厂每月的现有量.小型中型大型现有量钢材（t）1.535600劳动时间（h）28025040060000利润（万元）234制订月生产计划，使工厂的利润最大.4.3

汽车生产与原油采购IP可用LINGO直接求解整数规划(IntegerProgramming,简记IP)IP的最优解x1=64，x2=168，x3=0，最优值z=632max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3<600;280*x1+250*x2+400*x3<60000;@gin(x1);@gin(x2);@gin(x3);

Globaloptimalsolutionfound.

Objectivevalue:632.0000Extendedsolversteps:0Totalsolveriterations:3VariableValueReducedCost

X164.00000-2.000000

X2168.0000-3.000000

X30.000000-4.000000IP结果输出设每月生产小、中、大型汽车的数量分别为x1,x2,x3其中3个子模型应去掉，然后逐一求解，比较目标函数值，再加上整数约束，得最优解：方法1：分解为8个LP子模型汽车厂生产计划若生产某类汽车，则至少生产80辆，求生产计划.x1,x2,,x3=0或80x1=80，x2=150，x3=0，最优值z=610LI雀NG泪O中对0-词1变量透的限顾定：@b舱in押(y护1)尘;象@b恼in古(y创2)核;需@b口in哄(y敢3)挺;方法2：引入0-痰1变量类，化飘为整慌数规猛划M为大哄的正兵数,本例莫可取10钓00Ob由je迅ct悉iv泼e紧Va季lu愈e:琴61趣0.吸00警00Va握ri断ab肾le储Va琴lu个e众R表ed奖uc疼ed折C据os茂tX1遇80粒.0阀00寄00睛0-2王.0剧00卖00婚0X2大15叔0.总00能00兽00-3壁.0执00搅00素0X3筑0.央00亿00域00-4跑.0垂00瞒00访0Y1客1.粒00耕00报00众0.气00款00矮00Y2侍1.肉00嚼00馆00麦0.抬00恒00严00Y3拦0.搭00凉00与000.菠00另00讯00若生粮产某声类汽忠车，皇则至辩少生还产80辆，淘求生婚产计笨划.x1=0或80x2=0或

80x3=0或

80最优仰解同卵前ma萄x=殖2*变x1婚+3福*x产2+迁4*峰x3差;1.盏5*晕x1直+3俱*x要2+杂5*臂x3灾<6动00迹;28秒0*肢x1棵+2剑50针*x索2+大40农0*甲x3垮<6竿00矩00犬;x1百*(揉x1悼-8慨0)奋>0使;x2稳*(赌x2原-8摘0)扒>0奖;x3到*(哗x3蔑-8葬0)蝇>0祖;@g境in晨(x亩1)名;@搅gi誉n(词x2该);微@g警in债(x奏3)摩;方法3：化为殖非线列性规愁划非线误性规内划（No伴n-点L扎in纪ea狮r痕Pr犬og朱ra依mm戒in荷g，简但记NL苗P）若生悠产某泻类汽泛车，超则至亿少生奥产80辆，闷求生柿产计碰划.x1=0或80x2=0或

80x3=0或

80最优证解同猛前.一般塑地，黄整数覆规划烈和非狱线性净规划谷的求识解比窝线性兴规划朵困难两得多奸，特点别是旁问题亩规模情较大社或者岗要求盐得到悲全局某最优统解时.汽车夜厂生升产计兴划决策隙变量付为整霉数,建立整数药规划常模型.求解窝整数桶规划警和非乐线性重规划损比线良性规团划困跌难得浅多(即便变用数疯学软葡件)悟.当整刘数变乎量取佛值很习大时,可作感为连膏续变凑量处扔理,问题简化败为线赵性规游划.对于近类似疾于“x=0或80菊”这样买的条茎件，筹通常引入0-稍1变量处理忠，尽旨量不屈用非渔线性感规划律（特坝别是夹引入迈的整赢数变质量个究数较爆少时钥）.应如饥何安舒排原勺油的朵采购述和加造工？例2原油乔采购捐与加诊工市场飞上可析买到绒不超诸过15鱼00t的原坡油A：购买越量不染超过50蹲0t时的泳单价枕为10徐00乖0元/t；购买感量超犁过50被0t但不常超过10顿00t时，控超过50疼0t的柄部分80盏00元/t；购买译量超银过10那00t时，丝式超过10月00t的部显分60镇00元/t然.售价4800元/t售价5600元/t库存500t库存1000t汽油甲(A50%)原油A原油B汽油乙(A60%)决策冻变量目标所函数问题巨分析利润动：销顾售汽努油的喉收入购买坑原油A的支馋出.难点惧：原棍油A的购爪价与扑购买胡量的顺关系泡较复芬杂.甲(A50%)AB乙(A60%)购买xx11x12x21x224.8千元/t5.6千元/t原油A的购霞买量,原油A,悬B生产汽油甲,乙的驴数量c(x)本~购买北原油A的支般出利润(千元)c(x)如何裳表述逼？原油织供应约束动条件x50哗0t单价巧为10千元/t；50举0tx10路00t，超余过50竟0t的8千元/t；10挪00tx15喜00t，超参过10渗00t的6千元/t怒.目标立函数购买xABx11x12x21x22库存500t库存1000t目标江函数剩中c(x)不是株线性随函数绝，是箭非线半性规莲划；对于貌用分毕段函捐数定陡义的c(x)，一负般的浴非线倘性规辫划软泽件也男难以钩输入堵和求浅解；想办填法将愉模型素化简桑，用全现成掏的软当件求度解.汽油桨含原寒油A的比走例限厦制约束世条件甲(A50%)AB乙(A60%)x11x12x21x22x1,x2,x3~以价眼格10煌,勉8,善6腿(千元/t)采购A的吨层数目标贩函数只有返当以10千元/t的价咐格购行买x1=5尤00(t可)时，常才能容以8千元/t的价刑格购久买x2方法1非线谜性规度划模嫌型，可艰以用LI溜NG垦O求解模型但求解x=x1+x2+x3,c(x)栏=裳10x1+8x2+6x350良0tx10疲00t，超大过50椒0t的8千元/t增加约束x=x1+x2+x3,c(x)虽=袍10x1+8x2+6x3类似地有方法1：LI临NG凉O求解Mo计de且l:Ma透x=院4辫.8鲜*x窜11密+绪4票.8咳*x衡21贷+纳5键.6苹*x装12财+裙5唯.6农*x伞22冶-瞒1枯0*摆x1踩-特8且*x励2叹-福6*浇x3捆;x1刑1+动x1决2受<昆x际+谜50厚0;x2浴1+胸x2批2日<胆10轮00兴;x1弃1牛-颂x2界1能>棉0;2*赤x1统2旷-念3*狐x2幸2签>光0;x=优x1陷+x刺2+刺x3忌;(x撇1饼-瓦50敌0)终*内x功2=张0;(x阀2段-散50花0)言*辛x护3=较0;x1锈<盗5斯00拍;x2毫<佩5等00让;x3皆<语5挤00饮;en露dLo佛ca粱l引op幕ti撞ma挣l研so傲lu渴ti播on条f症ou馅nd黑.Ob狂je倚ct桥iv恢e慌va汇lu霸e:撕48研00说.0琴00To扫ta离l今so不lv愿er追i帐te薯ra戴ti花on陆s:避14Va逃ri凉ab明le隶V喷al单ue仆Re旧du补ce讽d荒Co食stX1序1召5尾00骑.0贺00连0捎0头.0冒00协00环0X2林1损5耗00年.0匀00俗0耐0愉.0雀00礼00述0X1偷2栋0雨.0凝00筛00得0犹0.健26误66泉66杠7X2荡2仙0魂.0值00床00曲00.无00街00垒00X1垃0.助00葬00饰00唯0躺.4峡00体00饲00X2渐0.乓00万00吊000.恢00统00后00X3悔0.反00狡00牛000.膝00辩00偶00X表0肉.0定00镜00广00.议00抬00俭00LI亡NG撤O得到群的是锦局部陶最优喘解,还能削得到独更好低的解槐吗？用库稠存的50钩0t原油A、50格0t原油B生产誓汽油述甲，孔不购乱买新拣的原某油A，利难润为48披00千元.方法1：LI余NG吼O求解计算腾全局夜最优永解睁：选LI应NG稠O|犹Op斤ti住on哗s菜单缎；在弹纵出的能选项症卡中辟选择倚“Ge俗ne置ra升l侍So沃lv捆er居”；然后柄找到令选项荷“Us传e催Gl磨ob踩al碌S裳ol垃ve评r”将其钢选中启；应用纷或保统存；索重新哨求解泰。Gl臭ob挤al秩o判pt尝im链al及s础ol割ut英io构n锣fo纪un栗d.Ob伸je恭ct虫iv糊e艰va叛lu船e:散50赤00爷.0雹00Ex澡te斯nd梨ed香s秧ol矩ve贸r抱st毯ep本s:朋1To剥ta钩l揪so催lv匙er害i些te馒ra邮ti诞on布s:胃43Va馋ri笨ab泉le俯V动al患ue钻Re搅du版ce困d铸Co述stX1意1幅0蹦.0轧00薄00赌00.吼00绩00悟00X2悠1追0兵.0怎00伟00衔0遮0.你90萄00泛00X1仪2烛1室50穷0.拉00遗0偿0测.0怎00固00抱0X2闭2救1割00哨0.脊00顾0幼0值.0祸00处00袜0X1松50撇0.纤00劣00倘0.悦00凯00套00X2金50罢0.暑00辈00磨0.闲00惊00鞠00X3垦0.臣00滥00牵000.朴00史00域00X控1饮00辞0.舅00揪0赖0组.0先00缓00疤0还有绢其他驴建模呜和求具解方杀法吗？购买10摔00帆t原油A，与知库存界的50颈0t原油A和10讽00停t原油B一起围，共踪蝶生产25透00改t汽油史乙，漠利润繁为50英00千元.y1,y2,y3=1卵~以价哪格10屑,白8,广6漫(千元/t)采购A增加菜约束方法20-协1线性叨规划疯模型,可用LI唤NG吩O求解.y1,y2,y3=0或1购买10黄00t原油A，与叙库存闲的50汪0t原油A和10复00t原油B一起帝，生忍产汽层油乙捧，利勤润为50勇00千元.x1,x2,x3~以价注格10闲,击8,扰6贼(千元/t)采购A的吨图数y=0x=0x>0y=1与方陷法1（全欣局最扩优解吵）的陕结果区相同引入0-堤1变量模型示求解b1b2b3b4方法3b1xb2，x=z1b1+z2b2，z1+z2=1，z1,z20,c(x)=z1c(b1)+z2c(b2).c(x)x1200090005000O50010001500b2xb3，x=z2b2+z3b3，z2+z3=1，z2,z30,c(x)=z2c(b2)+z3c(b3).b3xb4，x=z3b3+z4b4，z3+z4=1，z3,z40,c(x)=z3c(b3)+z4c(b4).直接狱处理肚分段浇线性浩函数c(x)IP模型肌，LI慢NG酬O求解库，得幅到的朋结果开与方碗法2相同.bkxbk+1yk=1,否则,yk=0方法3bkxbk+1,x=zkbk+zk+1bk+1zk+zk+1=1，zk,zk+10,c(x)=zkc(bk)+zk+1c(bk+1).c(x)x1200090005000O50010001500b1b2

b3

b4对于k=1弱,2塘,3方法3:直接扒处理赠分段钳线性绪函数链，方诸法更留具一夫般性.分段针函数无法恨直接蓬用非雅线性锡规划搅方法转或软室件求亭解.原油张采购体与加徐工方法1:增加捷约束埋化为非线果性规此划,可以盼用LI哪NG牙O求解,但可钓能得到眼的是灯局部季最优假解.方法2:引入0-茅1变量,化为线性非规划泪模型,可用LI悬NG扔O求解.如何异选拔轰队员古组成410辨0m混合盖泳接弊力队?例1混合技泳接缴力队借的选挺拔5名候鹅选人墨的百米光成绩甲乙丙丁戊蝶泳仰泳蛙泳自由泳目标意函数若选架择队袋员i参加属泳姿j的比冰赛，却记xij=1,否则相记xij=00-浪1规划锁模型cij(s)~队员i第j种泳贞姿的两百米抖成