数学建模教材(第四章)

1、精选优质文档-倾情为你奉上精选优质文档-倾情为你奉上专心-专注-专业专心-专注-专业精选优质文档-倾情为你奉上专心-专注-专业第4章 数学规划模型本章研究数学规划模型，其中包括：线性规划、整数规划、非线性规划、多目标规划与动态规划等内容4.1线性规划模型线性规划是运筹学的一个重要分支，随着计算机技术的发展，线性规划不仅在理论上已趋向成熟，而且在实际应用中也日益广泛与深入本节将借助Lingo数学软件对线性规划模型进行求解4.1.1问题的提出在生产管理和经营活动中经常提出一类问题，即如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果引例1 普通生产计划安排问题某工厂在计划期内要安排

2、生产、两种产品，已知生产单位产品所需的设备台时及、两种原材料的消耗，如表4-1所示该工厂每生产一件产品可获利2元，每生产一件产品可获利3元，问应该如何安排计划使该工厂获利最多？表4.1普通生产计划安排问题设备原材料原材料利润140220438台时16kg12kg引例2 奶制品的生产计划问题一奶品加工厂用牛奶生产、两种奶制品，1桶牛奶可以在甲类设备上用12小时加工成3公斤，或者在乙类设备上用8小时加工成4公斤，根据市场需求，生产的、全部能售出，且每公斤获利24元，每公斤获利16元现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且甲类设备每天最多能加工100公斤，乙类

3、设备的加工能力没有限制试为该厂制定一个生产计划，使每天获利最大，并进一步讨论以下个附加问题：若用35元可以买到1桶牛奶，应否做这项投资？若投资，每天最多购买多少桶牛奶？若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？由于市场需求变化，每公斤的获利增加到30元，应否改变生产计划？4.1.2模型建立1.引例1普通生产计划安排问题的模型建立对于引例1，可以设、分别表示在计划期内产品、的产量若用表示利润，这时，因为设备的有效台时为8，因此应有限制条件：；同理考虑原材料的不同限制，可得如下限制条件：，综上所述，该计划问题可用数学模型表示为：目标函数：约束条件：2.引例2奶制品生产计

4、划问题的模型建立对于引例2，可以设每天用桶牛奶生产，用桶牛奶生产类似引例1可得奶制品生产计划问题的数学模型：目标函数：约束条件：从以上两例可以看出，他们都属于同一类优化问题，他们的共同特征：每一个问题都用一组决策变量表示某一方案；这组决策变量的值就代表一个具体方案，一般这些变量取值都是非负的；存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示；都有一个要求达到的目标，它可用决策变量的线性函数来表示，这个函数称为目标函数满足以上三个条件的数学模型称为线性规划数学模型其一般形式为：目标函数：约束条件：4.1.3模型求解1.引例1普通生产计划安排问题的模型求解使用Lingo数学软件

5、对引例进行求解，编写程序如下：max=2*x+3*y;x+2*y8;4*x16;4*y12;end求解结果为：目标函数的最大值，即可获得最大利润元；最优生产计划方案是：生产产品4件，生产产品2件2.引例2奶制品生产计划问题的模型求解使用Lingo数学软件对引例2进行求解，编写程序如下：max=72*x1+64*x2;x1+x250;12*x1+8*x2480;3*x1100;end求解结果为：每天用20桶牛奶生产，用30桶牛奶生产，最大利润是3360元下面来回答三个附加问题： 针对附加问题1，可假设应投资购买桶牛奶，目标函数应修改为：关于牛奶的约束条件也应作相应的修改：通过编程求解得：最大利润

6、增加到3490元，因此，应作该项投资，每天最多购买10桶牛奶 针对附加问题2，首先将劳动时间480小时增加1个小时，对原问题进行求解，可得最大利润由3360元增加到3362元，其中增加的2元就是劳动时间的影子价格因此，若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时2元其次，若还想知道以低于每小时2元的价格增加劳动时间，最多可购买多少劳动时间？可以对目标函数以及关于劳动时间的约束条件作类似的修改，然后进行求解例如，若以每小时1.5元的价格聘用临时工人，最多可购买53.333小时针对附加问题3，只需改变目标函数中的系数即可将原来的目标函数改为：，约束条件不变通过求解可得：最大利润

7、有所增加，由原来的3360元增加到3720元，但生产计划没有改变，仍然是每天用20桶牛奶生产，用30桶牛奶生产4.1.4应用实例例1一个家庭有625英亩的土地可以用来种植农作物，这个家庭考虑种植的农作物有玉米、小麦和燕麦，预计可以有1000英亩-英尺的灌溉用水，农场工人每周可以投入的工作时间为300小时，其他的数据在表4-2中给出，为能够获得最大收益，每种作物应该种植多少？表4.2农场问题的有关数据玉 米小 麦燕 麦现有量灌溉用水（英亩-英尺）劳力（人-小时/周）收益（美元）3.00.84001.00.22001.50.32501000300解设应种植玉米英亩，小麦英亩和燕麦英亩可得如下线性规

8、划模型：目标函数：约束条件：使用Lingo数学软件进行求解，编写程序如下：max=400*x1+200*x2+250*x3;x1+x2+x3625;0.8*x1+0.2*x2+0.3*x3300;3*x1+x2+1.5*x31000;end程序运行结果为：应分别种植玉米187.5英亩，小麦437.5英亩和燕麦0英亩，获最大收益美元例2 某市有甲、乙、丙、丁四个居民区，自来水由、三个水库供应四个区每天必须得到保证的基本生活用水量分别为30，70，10，10千吨，但由于水源紧张，三个水库每天最多只能供应50，60，50千吨自来水由于地理位置的差别，自来水公式从各水库向各地区送水所需付出的引水管理费

9、不同（见表4-3，其中水库与丁地区之间没有输水管道），其它管理费用都是450元千吨根据公司规定，各区用户按照统一标准900元千吨收费此外，四个区都向公司申请了额外用水量，分别为每天50，70，20，40千吨该公司应如何分配供水量，才能获利最多？为了增加供水量，自来水公司正在考虑进行水库改造，使三个水库每天的最大供水量都提高一倍，问那时供水方案应如何改变？公司利润可增加多少？表4.3引水管理费引水管理费（元千吨）甲乙丙丁160140190130130200220190230170150解决策变量应为、三个水库分别向甲、乙、丙、丁四个区的供水量设水库向区的日供水量为千吨，由于水库与丁区之间没有输水

10、管道，即，因此只有11个决策变量于是可得如下线性规划模型：目标函数：约束条件：水库供应量限制可以表示为：各区基本用水量与额外用水量限制为：使用Lingo数学软件进行求解，编写程序如下：max=(450-160)*x11+(450-130)*x12+(450-220)*x13+(450-170)*x14+(450-140)*x21+(450-130)*x22+(450-190)*x23+(450-150)*x24+(450-190)*x31+(450-200)*x32+(450-230)*x33;x11+x12+x13+x1450;x21+x22+x23+x2460;x31+x32+x3350;

11、x11+x21+x3130;x12+x22+x3270;x13+x23+x3310;x14+x2410;end程序运行结果为：水库向乙区供水50千吨；水库向乙、丁区分别供水50，10千吨；水库向甲、丙分别供水40，10千吨最大利润为47600元对于本例来说，无论是目标函数还是约束条件都显得比较麻烦，特别是目标函数为多项相加随着水库与居民区个数的增加，程序会更加复杂下面来研究更一般的编程方法为此，需假定水库向丁地区的引入管理费用为无穷大，本例可用1000元千吨来代替使用Lingo数学软件中的高级编程技巧进行求解，编写程序如下：model:sets:sk/1.3/:g;dq/1.4/:sl1,sl

12、2;link(sk,dq):c,x;endsetsdata:c=160 130 220 170140 130 190 150190 200 230 1000;g=50 60 50;sl1=30 70 10 10;sl2=80 140 30 50;enddataobj max=sum(link(i,j):x(i,j)*(450-c(i,j);for(sk(i):sum(dq(j):x(i,j)sl1(j);for(dq(j):sum(sk(i):x(i,j)sl2(j);end程序运行结果完全相同如果三个水库每天的最大供水量都提高一倍，只需将数据段中的供水量修改成：g=100 120 100；或

13、者对第一个约束条件作简单修改，在小于号后面将供水量扩大2倍，其它条件不变最后的运行结果为：水库向乙区供水100千吨；水库向甲、乙、丁区分别供水30，40，50千吨；水库向甲、丙分别供水50，30千吨总利润为88700元评注：本例考虑的是将某种物资从若干供应点运往一些需求点，在供需量约束条件下使总费用最少，或总利润最大这类问题一般称为运输问题注意：本例目标函数采用的是最大利润，而非最小成本一般来说，成本最小，未必利润最大当总收入是常数时，最小成本与最大利润是等价的；若总收入随决策变量的改变而变化时，最小成本与最大利润并不等价通常追求的目标应该是最大利润，而非最小成本4.2非线性规划在工程技术、经

14、济管理、交通运输和日常生活等诸多领域中，很多实际问题可以归结为线性规划问题，其目标函数和约束条件都是自变量（决策变量）的一次函数（线性函数）但是，还有另外一些问题，其目标函数和（或）约束条件很难用线性函数表达如果目标函数或约束条件中包含有非线性函数，就称这种规划问题为非线性规划问题由于计算机技术的快速发展，使非线性规划的理论及其应用在近几十年来得以长驱进展特别是Lingo数学软件的开发与应用，对非线性规划模型的求解提供了很大的帮助4.2.1问题的提出1.引例1液体原料混合问题某公司将4种不同含硫量的液体原料（分别记为甲、乙、丙、丁）混合生产两种产品（分别记为、）按照生产工艺的要求，原料甲、乙、

15、丁必须首先倒入混合池中混合，混合后的液体再分别与原料丙混合生产和已知原料甲、乙、丙、丁的含硫量分别是3，1，2，1（%），进货价格分别为6，16，10，15（千元吨）；产品、的含硫量分别不能超过2.5，1.5（%），售价分别为9，15（千元吨）根据市场信息，原料甲、乙、丙的供应没有限制，原料丁的供应量最多为50吨；产品、的市场需求量分别为100、200（吨），问应如何安排生产？2.引例2最佳选址问题某乡镇由12个主要的自然村组成，每个自然村的位置（用平面坐标x，y表示，距离单位：km）和自然村的人口数（R）如表4-4所示试根据需要解决如下问题：目前准备在该乡镇建一个服务网点为各村提供各种服务，

16、那么服务网点应该建在何处？假设各村人口增长了一倍，需要建两个服务网点，确定其位置表4.4最佳选址问题0123456789101112XyR006008.200.5010000.504.908005.705.0014000.776.4912002.878.767004.433.266002.589.328000.729.9610009.763.1612003.197.2010005.557.8811004.2.2模型建立1.引例1液体原料混合问题的模型建立设分别是产品中来自混合池和原料丙的吨数；分别是产品中来自混合池和原料丙的吨数；混合池中原料甲、乙、丁所占的比例分别为，优化目标是总利润（）最大

17、 目标函数为：约束条件为：原料最大供应限制：产品最大需求限制：产品最大含硫量限制：其它限制：2.引例2最佳选址问题的模型建立（1）模型一的建立设服务网点的坐标为：；自然村的位置坐标：；自然村的人口数：，服务网点到各自然村的距离为：以自然村的人口数作为距离的权重，优化的目标为总距离最小目标函数为：约束条件为：（2）模型二的建立设两个服务网点的坐标分别为：；自然村的位置坐标：，；自然村的人口数：；服务网点到自然村的距离为：；服务网点对自然村服务的人口数为：； ；表示第个服务网点服务的人口数占人口总数的比例以服务网点对自然村服务的人口数作为距离的权重，优化的目标为总距离最小目标函数为：约束条件：从以

18、上两个引例可以总结出非线性规划的一般模型：目标函数：约束条件：目标函数为一般非线性函数，约束条件为一般非线性等式或非线性不等式一般来说，目标函数与约束条件中只要有非线性项存在，即为非线性规划特别地，若某非线性规划的目标函数为决策变量的二次函数，约束条件又全是线性的，就称这种规划为二次规划4.2.3模型求解1.引例1液体原料混合问题的模型求解使用Lingo数学软件进行求解，编写程序如下：max=(9-6*x1-16*x2-15*x4)*y1+(15-6*x1-16*x2-15*x4)*y2+(1-10)*z1+(15-10)*z2;x4*(y1+y2)50;y1+z1100;y2+z2200;(

19、3*x1+x2+x4)*y1+2*z1)/(y1+z1)2.5;(3*x1+x2+x4)*y2+2*z2)/(y2+z2)1.5;x1+x2+x4=1;end用Lingo求解时，如果怀疑不是全局最优解，用LINGO|OPTIONS菜单命令启动Global Solver选项卡上的Use Global Solver选项，然后求解，可以得到全局最优解如下：，其余为0；目标函数值为450如果将产品最大含硫量限制的约束条件作简单修改后，也可直接进行求解，并得到相同的结果修改后的程序如下：max=(9-6*x1-16*x2-15*x4)*y1+(15-6*x1-16*x2-15*x4)*y2+(1-10)

20、*z1+(15-10)*z2;x4*(y1+y2)50;y1+z1100;y2+z2200;!(3*x1+x2+x4)*y1+2*z1)/(y1+z1)2.5;(3*x1+x2+x4-2.5)*y1-0.5*z10;!(3*x1+x2+x4)*y2+2*z2)/(y2+z2)1.5;(3*x1+x2+x4-1.5)*y2+0.5*z22*r(j);endsubmodelcalc:e(1)=sum(point:r);e(2)=sum(point:r);solve(xuanzhi);ole(选址.xls,最佳位置a)=a;ole(选址.xls,最佳位置b)=b;ole(选址.xls,最优方案)=c

21、;EndcalcEnd用Lingo求解得到结果为：两个服务网点的位置坐标为：；各服务网点服务人数对照表见表4-5表4.5服务人数对照表（限制服务网点的服务人数相同）123456789101112人口总数（千人）网点1网点20.40.8021.6002.82.401.4001.21.602002.42002.211.411.4针对模型二，若不考虑服务网点服务人数的限制，使用Lingo数学软件进行求解，编写程序如下：model:title:最佳选址（一）;sets:point/1.12/:x,y,r;weizhi/1.2/:a,b,e;link(weizhi,point):c;endsetsdat

22、a:X=0 8.20 0.50 5.70 0.77 2.87 4.43 2.58 0.72 9.76 3.19 5.55;Y=0 0.50 4.90 5.00 6.49 8.76 3.26 9.32 9.96 3.16 7.20 7.88;r=600 1000 800 1400 1200 700 600 800 1000 1200 1000 1100;enddatasubmodel xuanzhi:min=sum(link(i,j): c(i,j)*(a(i)-x(j)2+(b(i)-y(j)2)(1/2);!for(weizhi(i): sum(point(j):c(i,j)=e(i);fo

23、r(point(j): sum(weizhi(i):c(i,j)2*r(j);endsubmodelcalc:!e(1)=sum(point:r);!e(2)=sum(point:r);solve(xuanzhi);ole(选址.xls,最佳位置a)=a;ole(选址.xls,最佳位置b)=b;ole(选址.xls,最优方案)=c;endcalc用Lingo求解得到结果为：两个服务网点的位置坐标为：；，各服务网点服务人数对照表见表4-6 表4.6服务人数对照表（服务网点服务人数不限制）123456789101112人口总数（千人）网点1网点201.2021.6002.82.401.4001.2

24、1.602002.4202.2013.29.64.2.4应用实例例1求解二次规划：解本例编写简单的Lingo程序即可求解，编写Lingo程序如下：max=8*x1+10*x2-x12-x22;3*x1+2*x2=0 b(i,j)=atan(x12/x11); elseif x12=0 b(i,j)=pi+atan(x12/x11); elseif x12=0 b(i,j)=b(i,j)-atan(x22/x21); elseif x22=0 b(i,j)=b(i,j)-atan(x22/x21)-pi; elseif x22pi b(i,j)=b(i,j)-2*pi; elseif b(i,j

25、)alpha(i,j););for(link:bnd(0,alpha,90);for(plane:bnd(-30,d_cita,30);objmin=sum(plane:(d_cita)2);end5.结果检验对题目所给实例进行计算得如下调整方案：， ， ， ， 各飞行方向角按此方案调整后，系统各架飞机均满足（即不会相撞）其中有些飞机对可能会有（0.01是题目要求的计算精度）如果希望，只须将模型中的用代替即可6.模型评价与改进此模型采用圆状模型分析碰撞问题是合理的，同时采用相对速度作为判断标准，既体现了碰撞的本质（相对运动），又简化了模型的计算题目要求飞机飞行方向角调整的幅度尽量小，这个尽量小

26、是针对每架飞机而言的，同时也要求整体满意程度（即对管理层而言，应使每架飞机的调整都尽量的小）因此构造目标函数时，也可以认为若对方向角调整量最大的飞机而言，其调整量可满意，则由假设（5）对其余飞机调整量均可满意即要求每架飞机的调整量都小于某个数故目标函数也可取：于是可得如下线性规划模型：目标函数：约束条件：模型二： 最短距离模型.问题分析目标函数的选取与模型一相同进入该区域的飞机在到达该区域边缘时，与区域内的飞机的距离应在60km以内，很容易验证目前所给数据是满足的，因此，约束条件只需要限制任意两架位于该区域内的飞机的距离应大于8km但这个问题的难点在于飞机是动态的，这个约束不好直接描述为此，可

27、以考虑在飞行过程中任意两架飞机的最短距离大于8km即可飞行时间可以只考虑一架飞机飞越该区域所需的最长时间，若超过这个时间，即使两架飞机的最短距离小于8km，由于飞机已经离开该区域，因此不再予以考虑2.模型假设与模型一相同3.模型的建立符号说明：表示第架飞机的飞行方向与x轴正向的夹角（转角）；表示第架飞机在调整前的位置坐标；表示第架飞机时刻的位置坐标；表示飞机的飞行时间；表示飞机的飞行速度；表示第架飞机飞出区域的时刻；表示任意一架飞机在该区域内停留的最长时间；表示第架飞机与第架飞机距离最短的时刻；表示第架飞机的飞行方表示第架飞机与第架飞机的距离；记飞机飞行速率为，以当前时刻为0时刻，设第架飞机在

28、调整前的位置坐标为，时刻的位置坐标，即如果要严格表示两架位于该区域内的飞机的距离应大于8km，则需要考虑每架飞机在区域内到为飞行时间的长度记为第架飞机飞出区域的时刻，即记时刻第架飞机与第架飞机的距离为，并记，这时在区域内飞机不相撞的约束条件就变成了其中此外，经过计算可以得到：其中所以，是一个关于的二次函数，当，即（记为）时，函数取最小值若，只要初始时刻不相撞即可，此时满足条件，不需要限制；若，只需要即可；若，即可，即实际上，在时也成立，因此，可以不再附加的条件，于是可得如下非线性规划模型：目标函数：约束条件：4.模型求解由于的计算相当复杂，求解时可进一步简化：不单独考虑每架飞机在区域内停留的时

29、间，而以最大时间代替，此时所有实际上强化了问题的要求，即考虑了有些飞机可能已经飞出区域，但仍不允许两架飞机的距离小于8km这个简化的模型可以如下输入Lingo软件：model:title: 飞行管理问题的非线性规划模型二;sets:plane/1.6/:x0,y0,cita0,cita1,d_cita;!cita0表示初始角度，cita1为调整后的角度，d_cita为调整的角度;link(plane,plane)|&1#lt#&2:b,c;endsetsdata:x0,y0,cita0= 150 140 243 85 85 236 150 155 220.5 145 50 159 130 15

30、0 230 0 0 52;max_cita=30;t_max=0.283;v=800;pi=3.;enddatainit:d_cita=0 0 0 0 0 0;endinitfor(plane:cita1-cita0=d_cita);for(link(i,j):b(i,j)=-2*(x0(i)-x0(j)*sin(cita1(i)+cita1(j)*pi/360)+2*(y0(i)-y0(j)*cos(cita1(i)+cita1(j)*pi/360);c(i,j)=(x0(i)-x0(j)2+(y0(i)-y0(j)2-64;);!避免碰撞的条件;!右端点非负;for(link(i,j):r

31、ight(2*v*t_max*sin(cita1(i)-cita1(j)*pi/360)2+b(i,j)*(2*v*t_max*sin(cita1(i)-cita1(j)*pi/360)+c(i,j)0);!左端点非负;for(link(i,j):c(i,j)0);!最小点非负;for(link(i,j):minimumif(-b(i,j)/4/v/sin(cita1(i)-cita1(j)*pi/360)#gt#0#and#-b(i,j)/4/v/sin(cita1(i)-cita1(j)*pi/360)#lt#t_max,b(i,j)2-4*c(i,j),-1)0);!for(link(i

32、,j):b(i,j)2-4*c(i,j)0);for(link:free(b);!调整角度上下限，单位为角度;for(plane:bnd(-max_cita,d_cita,max_cita);objmin=sum(plane:(d_cita)2);end使用Lingo全局求解程序求解该模型，得到的结果与模型一几乎是一样的调整方案如下：， ， ， ， 4.3整数规划在线性规划或非线性规划模型中，经常会遇到决策变量必须是整数的限制，例如，当决策变量表示人数、机器设备的台数、机械车辆数等的时候，显然，这些量必须取整数一般地，包含有整数决策变量的数学模型称为整数规划模型在研究实际问题时，有时还会遇到决

33、策变量是0-1变量的情形，即决策变量只能取0或1两个值，这种特殊的整数规划模型称为0-1规划模型，0-1规划模型是整数规划模型中非常重要的一类模型4.3.1问题的提出1.引例1 汽车厂的生产计划问题一汽车厂生产小、中、大三种类型的汽车，已知各类型每辆车对钢材、劳动时间的需求量，利润以及每月工厂钢材、劳动时间的现有量如表4-8所示试制订月生产计划，使工厂的利润最大进一步讨论：由于各种条件的限制，如果生产某一类型的汽车，则至少要生产80辆，那么最优的生产计划应作何改变？表4.8汽车厂的生产数据小型中型大型现有量钢材（吨）劳动时间（小时）利润（万元）1.52802325035400460060000

34、2.引例2 混合泳接力队的选拔问题某班计划从5名游泳队员中选择4人组成接力队，参加学校的4100m混合泳接力比赛5名队员4种泳姿的百米平均成绩如表4-9所示，问应如何选拔队员组成接力队？如果最近队员丁的蛙泳成绩有较大退步，只有1152；而队员戊经过艰苦训练自由泳成绩有所进步，达到575，组成接力队的方案是否应该调整？表4.9各队员4种泳姿的百米平均成绩甲乙丙丁戊蝶泳仰泳蛙泳自由泳1068115612758657210610645311810781246594110114210965721074111123810243.引例3 原油的采购与加工问题某公司用两种原油（A和B）混合加工成两种汽油（甲

35、和乙），甲、乙两种汽油含原油A的最低比例分别为50%和60%，每吨售价分别为4800元和5600元该公司现有原油A和B的库存量分别为500吨和1000吨，还可以从市场上买到不超过1500吨的原油A原油A的市场价为：购买量不超过500吨时的单价为10000元/吨；购买量超过500吨但不超过1000吨时，其超过500吨的部分8000元/吨；购买量超过1000吨时，超过1000吨的部分6000元/吨该公司应如何安排原油的采购和加工？4.3.2 模型的建立与求解1.模型一的建立与求解针对模型一，显然决策变量应为生产小、中、大三种类型汽车的数量，分别设为，于是可得如下的线性规划模型：目标函数：约束条件：

36、使用Lingo求解，得到输出：目标函数值为632.2581；决策变量的值分别为：最优解中出现了小数，显然不合适如果在上述模型中再加入整数约束，即可解决此类问题求解Lingo程序如下：ax=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3600;280*x1+250*x2+400*x360000;gin(x1);gin(x2);gin(x3);end程序最后一行是3个变量均为整数的约束运行该程序可得如下输出结果：目标函数值为632；决策变量的值分别为：即问题要求的月生产计划为：生产小型车64辆、中型车168辆，不生产大型车讨论：对于问题中提出的如果生产某一类型汽车，则至少要生产80

37、辆的限制，上面得到的最优解并不满足这个条件这种类型的要求是实际生产中经常提出的为此，我们提出两种方法来处理这类问题 引入0-1变量，化为0-1规划问题设只取0，1两个值，则或等价于其中为相当大的正数，本例可取1000（根据约束条件可知：都不可能超过1000）类似的有：其中都是0-1变量，编写Lingo程序如下：max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3600;280*x1+250*x2+400*x360000;x180*y1;x280*y2;x380*y3;gin(x1);gin(x2);gin(x3);bin(y1);bin(y2);bin(y3);end程序最后

38、一行是3个变量均为0-1变量的约束运行该程序可得如下输出结果：目标函数值为610；决策变量的值分别为：即问题要求的月生产计划为：生产小型车80辆、中型车150辆，不生产大型车 化为非线性规划问题如果生产某一类型汽车，则至少要生产80辆等价于：式子左端是决策变量的非线性函数，加上这些约束条件构成非线性规划模型编写Lingo程序如下：max=2*x1+3*x2+4*x3;1.5*x1+3*x2+5*x3600;280*x1+250*x2+400*x30;x2*(x2-80)0;x3*(x3-80)0;gin(x1);gin(x2);gin(x3);end求解结果与0-1规划模型的结果完全一致由于非

39、线性规划模型的结果常依赖于初值的选择，且运行时间相对较长，因此，一般尽量不用非线性规划来求解2.模型二的建立与求解针对模型二，决策变量可以考虑0-1变量，建立0-1规划模型记甲乙丙丁戊分别为队员；记蝶泳、仰泳、蛙泳、自由泳分别为泳姿；记队员的第种泳姿的百米平均成绩为；设为0-1变量，取值0表示队员不参加第种泳姿的比赛，取值1表示队员参加第种泳姿的比赛，于是可得如下的0-1规划模型：目标函数：约束条件：首先将题目所给数据标准化（单位：秒），编写Lingo程序如下：model:title:混合泳接力队的选拔;sets:duiyuan/1.5/:;yongzi/1.4/:;link(duiyuan,

40、yongzi):c,x;endsetsdata:c=66.8 75.6 87 58.6 57.2 66 66.4 53 78 67.8 84.6 59.4 70 74.2 69.6 57.2 67.4 71 83.8 62.4; enddatamin=sum(link:c*x);for(duiyuan(i):sum(yongzi(j):x(i,j)1;);for(yongzi(j):sum(duiyuan(i):x(i,j)=1;);for(link:bin(x););end求解得到结果为：，其它变量为0，成绩为：253.2秒，即应当选派甲乙丙丁4人组成接力队，分别参加自由泳、蝶泳、仰泳、蛙泳

41、的比赛讨论：如果最近队员丁的蛙泳成绩有较大退步，只有1152；而队员戊经过艰苦训练自由泳成绩有所进步，达到575，则将由原来的69.6秒修改为75.2秒；将由原来的62.4秒改为57.5秒使用修改后的新数据代入模型再次求解，得到如下结果：，其它变量为0，成绩为：257.7秒，即应当选派乙丙丁戊4人组成接力队，分别参加蝶泳、仰泳、蛙泳、自由泳的比赛评注：本例属于这样一类分派问题：有若干项任务，每项任务必须有一人且只能有一人承担，每人也只能承担其中一项，不同人员承担不同任务的收益（或成本）不同，问题是怎样分派各项任务使总收益最大（或总成本最小）它又称为指派问题由本例的研究可知，当遇到诸如是否参加、

42、是否选择、是否成立等二值问题时，可采用0-1变量，建立0-1规划模型进行求解3.模型三的建立与求解问题分析安排原油采购、加工的目的是利润最大，题目中给出的是两种汽油的售价和原油A的采购价，利润为销售汽油的收入与购买原油A的支出之差这里的难点在于原油A的采购价与购买量的关系比较复杂，是分段函数关系，能否及如何用线性规划、整数规划模型加以处理是关键所在在实际问题中，目标函数中经常遇到包含分段函数的情形，对这类问题的讨论研究是十分必要的针对模型三，设原油A的购买量为，根据题目所给数据，采购的支出可表示为如下的分段函数（以下价格以千元吨为单位）：设原油A用于生产甲、乙两种汽油的数量分别为：和；原油B用

43、于生产甲、乙两种汽油的数量分别为：和，则总收入为：，于是目标函数为：约束条件包括两种汽油用的原油A、原油B库存量的限制，和原油A购买量的限制，以及两种汽油含原油A的比例，它们表示为：0-1规划模型的建立与求解由于目标函数中包含分段函数，因此，上面的模型不是线性规划模型，事实上，使用一般的非线性规划也很难求解该问题为了解决这类问题，可以考虑引入0-1变量，建立0-1规划模型进行求解设是0-1变量，价格区间、与分别对应：表示在第个价格区间购买原油A；表示在第个价格区间不购买原油A购买量对应于于是有：应该注意到，只有当以10千元吨的价格购买满500吨时，才能以8千元吨的价格购买；只有当以10千元吨的

44、价格购买满500吨，而且以8千元吨的价格购买也满500吨时，才能以6千元吨的价格购买因此，需要增加如下的线性约束：由上面的约束可以看出：，显然满足购买原油A的价格要求编写Lingo程序如下：max=4.8*x11+4.8*x21+5.6*x12+5.6*x22-10*x1-8*x2-6*x3;x-x1-x2-x3=0;x11+x12-x500;x21+x221000;x0;0.4*x12-0.6*x220;x1500*y1;500*y2x1;x2500*y2;500*y3x2;x3500*y3;bin(y1);bin(y2);bin(y3);end运行该程序可得如下输出结果：目标函数值为500

45、0千元；决策变量的值分别为：，其它都是0即用原油A1500吨（包括库存的500吨以及以10千元价格购买的500吨和以8千元价格购买的500吨），原油B1000吨，生产2500吨的汽油乙，获利5000千元设原油A用于生产甲、乙两种汽油的数量分别为：和；原油B用于生产甲、乙两种汽油的数量分别为：和，则总收入为：，于是目标函数为：非线性规划模型的建立与求解与0-1规划模型类似，首先引入变量分别表示以10千元吨、8千元吨、6千元吨采购的原油A的吨数，总支出，且 为了限制先用高价格购买，在以较低价格购买，可使用下面的非线性约束条件： 同理可得：编写Lingo程序如下：max=4.8*x11+4.8*x2

46、1+5.6*x12+5.6*x22-10*x1-8*x2-6*x3;x-x1-x2-x3=0;x11+x12-x500;x21+x221000;x0;0.4*x12-0.6*x220;(x1-500)*x2=0;(x2-500)*x3=0;x1500;x2500;x3500;end运行该程序可得如下输出结果：目标函数值为4800千元；决策变量的值分别为：，其它都是0即用库存的原油A500吨，原油B500吨，生产1000吨的汽油甲，获利4800千元，该方案不需要购买原油A若使用Lingo全局求解程序求解该程序，得到的结果与0-1规划模型的结果几乎完全一致4.3.3 应用实例例1飞行计划安排问题甲

47、乙双方的一场战争中，一部分甲方部队被乙方部队包围长达4个月由于乙方封锁了所有水陆交通通道，被包围的甲方部队只能依靠空中交通维持供给运送4个月的供给分别需要2次，3次，3次，4次飞行，每次飞行编队由50架飞机组成（每架飞机需要3名飞行员），可以运送10万吨物质每架飞机每个月只能飞行一次，每名飞行员每个月也只能飞行一次在执行完运输任务后的返回途中有20%的飞机会被乙方部队击落，相应的飞行员也因此牺牲或失踪在第一个月开始时，甲方拥有110架飞机和330名熟练的飞行员在每个月开始时，甲方可以招聘新飞行员和购买新飞机新飞机必须经过一个月的训练才能投入飞行每名熟练飞行员可以作为教练每个月指导20名飞行员（

48、包括他自己在内）进行训练每名飞行员在完成一个月的飞行任务后，必须有一个月的带薪假期，假期结束后才能再投入飞行已知各项费用（单位略去）如表4-10所示，请你为甲方安排一个飞行计划表4.10飞行计划的有关数据第1个月第2个月第3个月第4个月新飞机价格闲置的熟练飞行员报酬教练和新飞行员报酬（包括训练费用）执行飞行任务的熟练飞行员报酬休假期间的熟练飞行员报酬200.07.010.09.05.0195.06.99.98.94.9190.06.89.89.84.8185.06.79.79.74.7如果每名熟练飞行员可以作为教练每个月指导不超过20名飞行员（包括他自己在内）进行训练，模型和结果有哪些改变？解

49、这个问题看起来很复杂，但只要理解了这个例子中所描述的事实，其实建立优化模型并不困难首先可以看出，执行飞行任务以及执行飞行任务后休假的熟练飞行员数量是常数，所以这部分费用（报酬）是固定的，在优化目标中可以不考虑设4个月开始时甲方新购买的飞机数量分别为架；闲置的飞机数量分别为架；4个月中，教练和新飞行员数量分别为；闲置的熟练飞行员数量分别为人于是可得如下整数规划模型：目标函数：约束条件：飞机数量限制：4个月中执行飞行任务的飞机分别为100，150，150，200（架），但只有80，120，120，160（架）能够返回供下个月使用第1个月 第2个月 第3个月 第4个月 飞行员数量限制：4个月中执行飞

50、行任务的熟练飞行员分别为300，450，450，600（人），但只有240，360，360，480能返回（下个月一定休假）第1个月 第2个月 第3个月 第4个月 所有变量都要求非负，且为整数编写程序Lingo如下：min=200*x1+195*x2+190*x3+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

51、*u4-v4=240;gin(x1);gin(x2);gin(x3);gin(x4);gin(y1);gin(y2);gin(y3);gin(y4);gin(u1);gin(u2);gin(u3);gin(u4);gin(v1);gin(v2);gin(v3);gin(v4);end运行该程序可得如下输出结果：目标函数值为42324.40；决策变量的值分别为：；讨论：如果每名熟练飞行员可以作为教练每个月指导不超过20名飞行员（包括他自己在内）进行训练，此时可将教练与新飞行员分开设4个月教练的数量分别为，新飞行员的数量分别为，其它决策变量不变飞行员的数量限制约束为：第1个月 第2个月 第3个月

52、第4个月 另外还需要加上教练与新飞行员的数量关系约束：编写程序Lingo如下：min=200*x1+195*x2+190*x3+185*x4+10*u1+9.9*u2+9.8*u3+9.7*u4+7*v1+6.9*v2+6.8*v3+6.7*v4+10*w1+9.9*w2+9.8*w3+9.7*w4;y1=10;y1+x1-y2=70;y2+x2-y3=30;y3+x3-y4=80;u1+v1=30;u1+v1+w1-u2-v2=450;u2+v2+w2-u3-v3=210;u3+v3+w3-u4-v4=240;w1-19*u10;w2-19*u20;w3-19*u30;w4-19*u4sum

53、(xfz(i):c1(i,1)*x(i,1);sum(xfz(i):c1(i,4)*x(i,4)sum(xfz(i):c1(i,3)*x(i,3);sum(xfz(i):c1(i,6)*x(i,6)sum(xfz(i):c1(i,5)*x(i,5);sum(xfz(i):c1(i,7)*x(i,7)sum(xfz(i):c1(i,6)*x(i,6);for(link:bin(x););end求解得到如下结果：决策变量的值分别为：，其它变量为0；目标函数值为335.00即消防站1应向火警地点2派2辆车，向火警地点3派1辆车；消防站2应向火警地点1派2辆车；消防站3应向火警地点3派2辆车；最小总损

54、失为335.00经过检验可以发现，此时的派车方案是合理的例2面试顺序问题有4名同学到一家公司参加三个阶段的面试：公司要求每个同学都必须首先找公司秘书初试，然后到部门主管处复试，最后到经理处参加面试，并且不允许插队（即在任何一个阶段4名同学的顺序是一样的）由于4名同学的专业背景不同，所以每人在三个阶段的面试时间也不同，如表4-12所示这4名同学约定他们全部面试完以后一起离开公司，假定现在是早晨8:00，请问他们最早何时能离开公司？表4.12面试时间要求秘书初试主管复试经理面试同学甲同学乙同学丙同学丁13102081520161020181015解实际上，这个问题就是要安排4名同学的面试顺序，使完

55、成全部面试所花费的时间最少设表示第名同学参加第阶段面试需要的时间，表示第名同学参加第阶段面试的开始时刻（不妨记早上8:00面试开始为0时刻），（；），为完成全部面试所花费的最少时间；用0-1变量表示第名同学是否排在第名同学前面（1表示是，0表示否）优化目标为：约束条件：时间先后次序约束（每人只有参加完前一个阶段的面试后才能进入下一个阶段）：每个阶段同一时间只能面试1名同学当时，即当第名同学排在第名同学前面时，则有：；当时，即当第名同学排在第名同学后面时，则有：这类约束条件是条件约束，为此，可利用0-1变量，将条件约束改为无条件约束：（）等价于无条件约束：（）等价于无条件约束：目标函数的处理方法

56、是将非线性的优化目标改写成如下线性优化目标：目标函数为；增加约束条件：编写程序Lingo如下：model:title:面试顺序问题;sets:tongxue/1.4/:;mianshi/1.3/:;link1(tongxue,tongxue)|&1#lt#&2:y;link(tongxue,mianshi):t,x;endsetsdata:t=13 15 20 10 20 18 20 16 10 8 10 15;enddataOBJmin=tt;for(tongxue(i):x(i,3)+t(i,3)tt;);for(link(i,j)|j#lt#3:x(i,j)+t(i,j)x(i,j+1)

57、;for(link(i,j):for(tongxue(k)|k#gt#i:x(i,j)+t(i,j)-x(k,j)tt*y(i,k););for(link(i,j):for(tongxue(k)|k#gt#i:x(k,j)+t(k,j)-x(i,j)tt*(1-y(i,k););for(link1:bin(y););End求解得到如下结果：目标函数值为84；决策变量的值分别为：，即所有面试完成至少需要84分钟，面试顺序是丁、甲、乙、丙，早上8:00面试开始，最早9:24面试可以全部结束4.4目标规划目标规划是由线性规划发展演变而来的线性规划考虑的是只有一个目标函数的问题，而实际问题中往往需要考

58、虑多个目标函数，这些目标不仅有主次关系，而且有的还互相矛盾这些问题用线性规划求解比较困难，因而提出了目标规划4.4.1问题的提出1.引例 生产安排问题某企业生产甲、乙两种产品，需要用到，三种设备，关于产品的盈利与使用设备的工时及限制如表4-13所示问：该企业应如何安排生产，使得在计划期内总利润最大？表4.13生产产品使用设备的工时、限制和产品的盈利甲乙设备的生产能力h(h/件)(h/件)(h/件)盈利(元/件)240200205300121615企业的经营目标不仅仅是利润，还需要考虑下面的因素（目标）：力求利润指标不低于1500元；考虑到市场需求，甲、乙两种产品的产量比应尽量保持1:2；设备为

59、贵重设备，严格禁止超时使用；设备可以适当加班，但要控制；设备既要求充分利用，又尽可能不加班在重要性上，设备是设备的3倍从上述问题可以看出，仅用线性规划方法是不够的，需要借助于目标规划的方法进行建模求解2.线性规划建模的局限性一般来说，在求解实际问题时，线性规划模型存在以下局限性：线性规划要求所求解的问题必须满足全部的约束，而实际问题中并非所有约束都需要严格的满足；线性规划只能处理单目标的优化问题，而对一些次目标只能转化为约束处理，而在实际问题中，目标和约束是可以互相转化的，处理时不一定严格区分；线性规划在处理问题时，将各个约束（也可以看做目标）的地位看成同等重要，而在实际问题中，各个目标的重要

60、性既有层次上的差别，也有在同一层次上不同权重的差别；线性规划寻找最优解，而许多实际问题只需要找到满意解就可以了4.4.2目标规划的基本概念1.设置偏差变量用偏差变量来表示实际值与目标值之间的差异，令表示超出目标的差值，称为正偏差变量；表示未达到目标的差值，称为负偏差变量其中与至少有一个为0当实际值超过目标值时，有；当实际值未达到目标值时，有；当实际值与目标值一致时，有2.统一处理目标与约束在目标规划中，约束条件有两类：一类是对资源有严格限制，同线性规划的处理方法相同，用严格的等式或不等式约束来处理，这类约束称为刚性约束；另一类约束是可以不严格限制的，连同原线性规划的目标，构成柔性约束在引例中，