《数学建模(规划方法1)课件》由会员分享，可在线阅读，更多相关《数学建模(规划方法1)课件（28页珍藏版）》请在金锄头文库上搜索。
1、数学规划模型 (一）,4.1斯大林格勒战役德军空中补给 4.2军事工程施工物资保障效率 4.3规划模型的基本概念,斯大林格勒战役,斯大林格勒战役，是第二次世界大战的主要转折点。参战主要军队为苏联和纳粹德国。一般认为，该次战役包括下述几部分：德军对苏联南部城市斯大林格勒（现称“伏尔加格勒”）的大规模轰炸行动；德军攻入市区；市区的巷战；苏联红军合围；最终全歼德军及轴心国盟军。,时间为1942年7月17日开始至1943年2月2日 ，历时六个半月，伤亡人数超过200万人。,4.1斯大林格勒战役德军空中补给,1942年11月23日，苏军完成了对斯大林格勒的包围。苏军3个方面军将德第6集团军的5个军22个
2、师，罗马尼亚和意大利部队以及部分克罗地亚军队共约27万人合围在斯大林格勒1500平方公里的地域内，第6集团军只有约5万人的部队被分割在包围圈之外。,德国空军必须通过“空中桥梁”为第6集团军提供每天700吨的需求。,被围德军空中补给需求,空中飞行计划模型,在斯大林格勒战役中，德国第六集团军被苏联军队包围长达4个月，由于苏军封锁了所有水陆交通通道，被包围的德军只能依靠空中交通维持供给，总共需要10万t物资。 运送4个月的供给分别需要2，3，3，4次飞行。 每次飞行编队由50架飞机组成（每架飞机需要3名飞行员）。 每架飞机每个月只能飞行一次，每名飞行员每个月也只能飞行一次。 在执行完运输任务后的返回
3、途中有20%的飞机会被苏军击落，相应的飞行员也因此牺牲或失踪。,在第1个月开始时，德军拥有110架飞机和330名熟练的飞行员。 在每个月开始时，德军可以招聘新飞行员和购买新飞机。新飞机必须经过一个月的检查后才可以投入使用，新飞行员必须在熟练飞行员的指导下经过一个月的训练才能投入飞行。 每名熟练飞行员可以作为教练每个月指导20名飞行员（包括他自己在内）进行训练。 每名飞行员在完成一个月的飞行任务后，必须有一个月的带薪假期，假期结束后才能再投入飞行。 已知各项费用（单位略去）如下表所示，请为德军安排一个飞行计划。,飞行计划的原始数据,问题分析,把问题看成由飞机和飞行员构成的系统，动态变化的过程。,
4、决策变量,设4个月开始德军新购买的飞机数量分别为x1、x2 、x3、x4架，闲置的飞机数量分别为y1、y2、y3、y4架，飞行员中教练和新飞行员数量分别为u1、u2、u3、u4人，闲置的熟练飞行员数量分别为v1、v2、v3、v4人。,目标函数,可以看出，执行飞行任务以及执行飞行任务后休假的熟练飞行员数量是常数，所以这部分费用（报酬）是固定的。,Min z =200 x1+195x2+190 x3+185x4+10u1+9.9u2+ 9.8u3+9.7u4+7v1+6.9v2+6.8v3+6.7v4,约束条件,（1）飞机数量限制。4个月中执行飞行任务的飞机分别为100，150，150，200（架
5、），但只有80，120，120，160（架）能够返回供下个月使用。,第1个月 100+y1=110,第2个月 150+y2=80+ y1+ x1,第3个月 150+y3=120+ y2+ x2,第4个月 200+y4=120+ y3+ x3,（2）飞行员数量限制。4个月中执行飞行任务的熟练飞行员分别分别为300，450，450，600（人），但只有240，360，360，480（人）能够返回（下个月一定休假）。,第1个月 300 +0.05u1 +v1=330,第2个月 450+ 0.05u2 +v2 =u1+ v1,第3个月 450+ 0.05u3 +v3 =u2+ v2+240,第4个月
6、600+ 0.05u4 +v4 =u3+ v3+360,数学模型,Min z =200 x1+195x2+190 x3+185x4+10u1+9.9u2+ 9.8u3+9.7u4+7v1+6.9v2+6.8v3+6.7v4,求解,程序,结果,军事工程（Military Engineering)是用于军事目的的各种工程建筑和保障军队作战行动所采取的工程技术措施的统称。其中，工程建筑既指军事工程建设的对象，也指建设全过程的工程侦察、勘测、设计、施工、维护等技术活动和对工程材料、设备的选用。物资保障的效率是工程施工速度和质量的重要指标。,4.2军事工程施工物资保障效率,某项军事工程在72平方公里范围
7、内6个不同地点同时施工，每个工地的位置(用平面坐标a,b表示，距离单位：km)及S物质日用量d(单位：t)由下面表给出。目前有两个临时军供站位于P(5,1)， P(2,7)，日储量各有20t。请回答以下两个问题： (1)假设从军供站到工地之间均有直线道路相连，试制定每天的供应计划，即从A，B两军供站分别向各工地运送多少吨S物质，使总的吨公里数最少？ (2)为进一步减少吨公里数，打算舍弃目前的两个临时军供站，改建两个新的军供站，日储量仍各有20t，问应建在何处，与目前相比节省的吨公里数有多大？,临时军供站设定,设工地的位置为(ai , bi)，S物质日用量di，i=1，6；军供站的位置 (xj
8、, yj) ，日储量为ej， j=1，2；从军供站j向工地i 的运送量为cij；z为总吨公里数。,该问题的数学模型为：,求解2,程序,求解1,1、规划模型的一般形式,规划模型的三个要素：,（1）决策变量，它通常是该问题要求解的那些未知量，不妨用n维向量x=（x1，x2 ， ， xn ）T表示，当对x赋值后通常称为该问题的一个解；,（2）目标函数，它通常是该问题要优化（最大或最小）的那个目标的数学表达式，它是决策变量x的函数，可以记作f(x)；,4.3 规划模型的基本概念,（3）约束条件，由该问题对决策的限制条件给出，即x允许取值的范围x ， 称为可行域，通常用一组关于x的等式hi(x)=0(i
9、=1,2,me）或不等式gj(x) 0(j= me +1, me +2, me +m）来界定，分别称为等式约束和不等式约束。,规划模型的一般数学形式： opt z=f(x); s.t. hi(x)=0 (i=1,2,me）, gj(x) 0 (j= me +1, me +2, me +m）. 其中opt是最优化的意思，可以是min或max两者之一；s. t.是“受约束于”（subject to)的意思。,2、可行解和最优解,同时满足约束条件和的解x(x )称为可行解，否则成为不可行解，满足约束条件的可行解x*称为最优解，在最优解x* 处目标函数的取值f(x*)称为最优值。,如果在某个可行解x*
10、 的附近(x* 的某个邻域)，x* 使目标函数达到的取值最优，但x*不一定是整个可行域上的最优解，则x* 称为一个局部最优解。相对于局部最优解，我们把整个可行域上的最优解称为全局最优解或整体最优解。,3、基本类型,(1)连续型，当模型中决策变量的x的所有分量xi(i=1,2,n）的取值均为连续数值(即实数)时，模型称为连续型规划。此时，若f(x)，hi(x) ， gj(x) 都是线性函数，称为线性规划；若f(x)，hi(x) ， gj(x) 至少有一个是非线性函数，称为非线性规划；特别地，若f(x)是二次函数，而hi(x) ， gj(x) 都是线性函数，称为二次规划；,(2)离散型，当模型中决
11、策变量的x的一个或多个分量只取离散数值，模型称为离散型规划。此时，通常x的一个或多个分量只取整数数值，称为整数规划。,(2)离散型，当模型中决策变量的x的一个或多个分量只取离散数值，模型称为离散型规划。此时，通常x的一个或多个分量只取整数数值，称为整数规划。,可以进一步分为纯整数规划(x的所有分量只取整数数值)和混合整数规划(x的部分分量只取整数数值) 。,特别地，若x的分量中取整数数值的范围还限定为只取0或1,则称为0-1规划 。,此外，整数规划还可以分为线性整数规划和非线性整数规划。,SAILCO公司需要决定下四个季度的帆船生产量，下四个季度的帆船需求量分别是40条，60条，75条，25条
12、，这些需求必须按时满足。每个季度正常的生产能力是40条帆船，每条船的生产费用为400美元。如果加班生产，每条船的生产费用为450美元。每个季度末，每条船的库存费用为20美元。假定生产提前期为0，初始库存为10条船，如何安排生产可使总费用最小？,帆船生产计划,我们设DEM(I)， RP(I)，OP(I)，INV(I)分别表示第I个季度的需求量、正常生产的产量、加班生产的产量、库存量(I=1,2,3,4)。这个问题的模型如下：,s.t. RP(I) 40， (I=1,2,3,4);,INV(I)= INV(I-1)+ RP(I) +OP(I) -DEM(I) ，(I=1,2,3,4);,INV(0
13、)= 10;,LINGO求解程序 MODEL: sets: quarters/1,2,3,4/:DEM,RP,OP,INV; endsets min=sum(quarters:400*RP+450*OP+20*INV); for(quarters(I):RP(I)40); for(quarters(I) |I#gt#1: INV(I)=INV(I-1) +RP(I)+OP(I)-DEM(I);); INV(1)=10+RP(1)+OP(1)-DEM(1);,data: DEM=40,60,75,25; enddata end,求解,model: min =200*x1+195*x2+190*x
14、3+185*x4+10*u1+9.9*u2+9.8*u3+9.7*u4+7*v1+6.9*v2+6.8*v3+6.7*v4; y1=10; y1+x1-y2=70; y2+x2-y3=30; y3+x3-y4=80; 0.05*u1+v1=30; u1+v1-0.05*u2-v2=450; u2+v2-0.05*u3-v3=210; u3+v3-0.05*u4-v4=240; gin(x1);gin(x2);gin(x3);gin(x4); gin(u1);gin(u2);gin(u3);gin(u4); gin(y1);gin(y2);gin(y3);gin(y4); gin(v1);gin
15、(v2);gin(v3);gin(v4); end,返回,Global optimal solution found. Objective value: 42324.40 Extended solver steps: 0 Total solver iterations: 3 Variable Value Reduced Cost X1 60.00000 200.0000 X2 30.00000 195.0000 X3 80.00000 190.0000 X4 0.000000 185.0000 U1 460.0000 10.00000 U2 220.0000 9.900000 U3 240.0
16、000 9.800000 U4 0.000000 9.700000 V1 7.000000 7.000000 V2 6.000000 6.900000 V3 4.000000 6.800000 V4 4.000000 6.700000 Y1 10.00000 0.000000 Y2 0.000000 0.000000 Y3 0.000000 0.000000 Y4 0.000000 0.000000,返回,LINGO求解程序 model: sets: demand/1.6/:a,b,d; supply/1.2/:x,y,e; link(demand,supply) :c; endsets data: 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=3,5,4,7,6,1
