用lingo求解数学规划模型实例

1、用用lingo求解数学规划模型实例求解数学规划模型实例一、一、lingo中的输入输出函数中的输入输出函数text函数函数 该函数被用在数据部分该函数被用在数据部分，用来用来将所需的数据将所需的数据输出至输出至文本文件中。文本文件中。其语法为其语法为： text(filename) 这里这里filename是文件名，可以采用相对路径和绝对是文件名，可以采用相对路径和绝对路径两种表示方式。如果忽略路径两种表示方式。如果忽略filename，那么数据就，那么数据就被输出到标准输出设备（大多数情形都是屏幕）。被输出到标准输出设备（大多数情形都是屏幕）。 text函数仅能出现在模型数据部分的一条语句的函

2、数仅能出现在模型数据部分的一条语句的左边。左边。如在例如在例6.7 （职员时序安排模型）（职员时序安排模型） 一项工作一周一项工作一周7天天都需要有人（比如护士工作），每天（周一至周日）都需要有人（比如护士工作），每天（周一至周日）所需的最少职员数为所需的最少职员数为20、16、13、16、19、14和和12，并要求每个职员一周连续工作并要求每个职员一周连续工作5天，天，试求每周所需最少职员数，并给出安排。试求每周所需最少职员数，并给出安排。注意这里我们考虑稳定后的情况。注意这里我们考虑稳定后的情况。决策变量：决策变量：xi第第i周天开始上班的人数；周天开始上班的人数； 目标函数：目标函数：

3、71miniixjiijdxts 511)7 , 1mod( .7 , 2 , 1 jsets:day/mon.sun/:x,d;endsetsobjmin=sum(day:x);for(day(j):sum(day(i)|i#le#5:x(wrap(j+i+2,7)=d);for(day:gin(x); data:d=20,16,13,16,19,14,12;text(F:数学软件数学软件lingolili607.txt)=day 开始上班的人数为开始上班的人数为 x;Enddata ,min71 iix，jiijdxts 511)7 , 1mod( .7 , 2 , 1 j MON 开始上

4、班的人数为开始上班的人数为 8.0000000 TUE 开始上班的人数为开始上班的人数为 2.0000000 WED 开始上班的人数为开始上班的人数为 0.0000000 THU 开始上班的人数为开始上班的人数为 6.0000000 FRI 开始上班的人数为开始上班的人数为 3.0000000 SAT 开始上班的人数为开始上班的人数为 3.0000000 SUN 开始上班的人数为开始上班的人数为 0.0000000file函数函数 该函数用从外部文件中输入数据，可以放在模型中任该函数用从外部文件中输入数据，可以放在模型中任何地方。何地方。语法格式为语法格式为file(filename)这里这里

5、filename是文件名，可以采用相对路径和绝对路径是文件名，可以采用相对路径和绝对路径两种表示方式。两种表示方式。执行一次执行一次 file输入输入 1个记录，记录之间的分隔符为个记录，记录之间的分隔符为 。table函数函数该函数以表格形式输出数据，只能在数据段（该函数以表格形式输出数据，只能在数据段（DATA）中使用。中使用。二、线性规划模型二、线性规划模型 特点：目标函数与约束条件均为一次的。特点：目标函数与约束条件均为一次的。 线性规划的一般模型线性规划的一般模型 niiixcz1 min .ts niiijxa1ib),( ), 2 , 1(mj iiihxl ), 2 , 1(n

6、i 例例1（运输规划模型）（运输规划模型） 某产品有某产品有6个产地个产地Ai 和和8个销售地个销售地Bj (i=1,2,6, j=1,2,8) ，产地到销地的单位运价见下表，产地到销地的单位运价见下表，问如何安排运输可使运输总费用最小。问如何安排运输可使运输总费用最小。B B1 1B B2 2B B3 3B B4 4B B5 5B B6 6B B7 7B B8 8产产 量量A A1 16 62 26 67 74 42 25 59 960A A2 24 49 95 53 38 85 58 82 255A A3 35 52 21 19 97 74 43 33 351A A4 47 76 67 7

7、3 39 92 27 71 143A A5 52 23 39 95 57 72 26 65 541A A6 65 55 52 22 28 81 14 43 352销销 量量3537223241324338 单位运价表：单位运价表：产地产地总产量和：总产量和：302销地销地总销量和：总销量和：280产大于销的模型。产大于销的模型。产地产地 Ai ：总产量总产量 ai销地销地 Bi ：总销量总销量 bi产地产地Ai到销地到销地Bj ：单位运价单位运价 cij运输量运输量 xiji=1,2,6; j=1,2,8决策变量：产地决策变量：产地Ai到销地到销地Bj的的运输量运输量 xij从产地从产地Ai到

8、销地到销地Bj的运费的运费 cij xij从从Ai到各销地的运费到各销地的运费 81jijijxc总运费总运费 6181ijijijxc目标函数：目标函数：6811minijijijc x产地产地 Ai ：总产量总产量 ai销地销地 Bi ：总销量总销量 bi产地产地Ai到销地到销地Bj ：单位运价单位运价 cij运输量运输量 xiji=1,2,6; j=1,2,8产地总产量和：产地总产量和：302销地总销量和：销地总销量和：280为产大于销的模型。为产大于销的模型。目标函数：目标函数：6811minijijijc x运往运往Bj的总运量：的总运量：jiijbx 61从从Aj运出的总量：运出的

9、总量：81ijijxa 对变量对变量xij的限制：的限制：0 ijxi=1,2,6; j=1,2,8sets:chdi/w1.w6/:a; xdi/v1.v8/:b;link(chdi,xdi):c,x;endsetsobjmin=sum(link:c*x);for(xdi(j):sum(chdi(i):x(i,j)=b(j);for(chdi(i):sum(xdi(j):x(i,j)=a(i);data:a=60,55,51,43,41,52;b=35,37,22,32,41,32,43,38;c=6,2,6,7,4,2,5,9,4,9,5,3,8,5,8,2,5,2,1,9,7,4,3,3

10、,7,6,7,3,9,2,7,1,2,3,9,5,7,2,6,5,5,5,2,2,8,1,4,3;text()=table(x);enddata6811minijijijc xs.t：81ijijxa jiijbx 610 ijx V1 V2 V3 V4 V5 V6 V7 V8 W1 0 19 0 0 41 0 0 0 W2 1 0 0 32 0 0 0 0 W3 0 11 0 0 0 0 40 0 W4 0 0 0 0 0 5 0 38 W5 34 7 0 0 0 0 0 0 W6 0 0 22 0 0 27 3 0 Objective value: 664.0000例例2 （指派问题）九种

11、不同型号的装备配给（指派问题）九种不同型号的装备配给9个部队，个部队，由于各部队的特点与条件不同，不同的装备在不同部队由于各部队的特点与条件不同，不同的装备在不同部队中产生效能不同，问如何分配可保证每个部队各分得一中产生效能不同，问如何分配可保证每个部队各分得一种装备，且使总效能最大种装备，且使总效能最大（装备在不同部队的效能见下表）装备在不同部队的效能见下表）。 0.24 0.42 0.15 0.46 0.34 0.69 0.03 0.57 0.69 0.31 0.04 0.60 0.69 0.11 0.24 0.45 0.35 0.27 0.31 0.24 0.08 0.14 0.54 0

12、.61 0.37 0.48 0.34 0.49 0.06 0.28 0.13 0.65 0.41 0.55 0.25 0.36 0.63 0.15 0.31 0.60 0.06 0.41 0.47 0.19 0.31 0.45 0.02 0.37 0.14 0.69 0.29 0.61 0.18 0.46 0.45 0.07 0.26 0.15 0.18 0.43 0.55 0.66 0.08 0.32 0.24 0.58 0.64 0.43 0.45 0.09 0.05 0.20 0.33 0.56 0.41 0.13 0.65 0.07 0.22 0.46 0.11123456789A B

13、 C D E F G H I 装备装备部队部队设设 , 0, 1ijx第第i个部队分配第个部队分配第j种装备种装备目标函数：目标函数： 9191maxijijijxa : .ts191 iijx191 jijxxij=0或或1（ i, j=1,2,9）第第i个部队不分配第个部队不分配第j种装备种装备 9191maxijijijxa191 iijx191 jijxxij=0或或1（ i, j=1,2,9）sets: army/ar1.ar9/;equi/eq1.eq9/;link(army,equi):a,x;endsetsobjmax=sum(link:a*x);for(equi(i):sum

14、(army(j):x(i,j)=1);for(army(j):sum(equi(i): x(i,j)=1);for(link: bin(x); data: a=file(F:数学软件数学软件lingolidali002.txt); text(F:数学软件数学软件lingolili002.txt )=table(x);enddata EQ1 EQ2 EQ3 EQ4 EQ5 EQ6 EQ7 EQ8 EQ9 AR1 0 0 0 0 0 0 0 0 1 AR2 0 0 0 1 0 0 0 0 0 AR3 0 0 0 0 0 1 0 0 0 AR4 0 0 0 0 1 0 0 0 0 AR5 1 0 0

15、 0 0 0 0 0 0 AR6 0 0 0 0 0 0 1 0 0 AR7 0 0 0 0 0 0 0 1 0 AR8 0 0 1 0 0 0 0 0 0 AR9 0 1 0 0 0 0 0 0 0 0.24 0.42 0.15 0.46 0.34 0.69 0.03 0.57 0.69 0.31 0.04 0.60 0.69 0.11 0.24 0.45 0.35 0.27 0.31 0.24 0.08 0.14 0.54 0.61 0.37 0.48 0.34 0.49 0.06 0.28 0.13 0.65 0.41 0.55 0.25 0.36 0.63 0.15 0.31 0.60

16、 0.06 0.41 0.47 0.19 0.31 0.45 0.02 0.37 0.14 0.69 0.29 0.61 0.18 0.46 0.45 0.07 0.26 0.15 0.18 0.43 0.55 0.66 0.08 0.32 0.24 0.58 0.64 0.43 0.45 0.09 0.05 0.20 0.33 0.56 0.41 0.13 0.65 0.07 0.22 0.46 0.11123456789A B C D E F G H I 装备装备部队部队例例3 （合理设计海岛旅游线路合理设计海岛旅游线路问题）问题）某景区由某景区由5个海岛个海岛A,B,C,D,E组成。海岛

17、之间及与大陆港口组成。海岛之间及与大陆港口P的的距离由表距离由表1给出，每个海岛的游览时间为半天，给出，每个海岛的游览时间为半天，C,D两个岛屿有两个岛屿有旅馆可供住宿。游览的过程为：游船早晨由港口旅馆可供住宿。游览的过程为：游船早晨由港口P出发，每半出发，每半天游览一个景点。如果行程超过一天，则晚上选择岛屿天游览一个景点。如果行程超过一天，则晚上选择岛屿C或或D住宿。游览结束后回到港口住宿。游览结束后回到港口P。景点每次接待游客的能力由表。景点每次接待游客的能力由表2给出，目前旅行社可选择大、小两种游船用于旅游。大型可载给出，目前旅行社可选择大、小两种游船用于旅游。大型可载乘客乘客100人，

18、小型可载乘客人，小型可载乘客40人。大型游船的每公里客均费用人。大型游船的每公里客均费用是小型游船的是小型游船的85%，但景点，但景点E只能停泊小型游船。客均旅行费只能停泊小型游船。客均旅行费用正比于船的行程。针对问题一、二、三、四分别建立数学模用正比于船的行程。针对问题一、二、三、四分别建立数学模型，完成规划旅游线路的设计，要求在尽可能满足各景点最大型，完成规划旅游线路的设计，要求在尽可能满足各景点最大接待能力的条件下，使旅行社的成本尽可能低？接待能力的条件下，使旅行社的成本尽可能低？问题一：若该公司只经营一日游业务，只选择小型船，应如何问题一：若该公司只经营一日游业务，只选择小型船，应如何

19、规划旅游线路？规划旅游线路？问题二：若该公司只经营一日游业务，可同时选择小型船和大问题二：若该公司只经营一日游业务，可同时选择小型船和大型船，应如何规划旅游线路？型船，应如何规划旅游线路？问题三：若该公司同时经营一日游、二日游业务，只选择小型问题三：若该公司同时经营一日游、二日游业务，只选择小型船，应如何规划旅游线路？船，应如何规划旅游线路？问题四：若该公司同时经营一日游、二日游业务，可同时选择问题四：若该公司同时经营一日游、二日游业务，可同时选择小型船和大型船，应如何规划旅游线路？小型船和大型船，应如何规划旅游线路？表表1：岛屿及港口之间距离（：岛屿及港口之间距离（km）ABCDE大陆港口大

20、陆港口PA4621506070B303255115C485390D2195E85景点旅游（半天）景点旅游（半天） 住宿（每晚）住宿（每晚）A A240240B B470470C C250250280280D D280280200200E E210210 表表2: 景点每半天可接待游客的人数景点每半天可接待游客的人数假设游船都是满载的。假设游船都是满载的。 问题一：若该公司只经营一日游业务，只选择小型船，应如何问题一：若该公司只经营一日游业务，只选择小型船，应如何规划旅游线路？规划旅游线路？景点旅游（半天）景点旅游（半天） 住宿（每晚）住宿（每晚）A A240240B B470470C C250

21、250280280D D280280200200E E210210 表表2: 景点每半天可接待游客的人数景点每半天可接待游客的人数尽可能满足景点最大接待能力：尽可能满足景点最大接待能力：各景点半天最多接待船数各景点半天最多接待船数Si：A：S1=6B：S2=11C：S3=6D：S4=7E：S5=5决策变量：航程为决策变量：航程为PijP的船数的船数xij岛岛i岛岛j的人均费用：的人均费用： cij表表1：岛屿及港口之间距离（：岛屿及港口之间距离（km）ABCDE大陆港口大陆港口PA4621506070B303255115C485390D2195E85港口港口P岛岛i的人均费用：的人均费用： p

22、i航程为航程为PijP的单船费用：的单船费用：40(pi +cij+pj)旅行社总成本：旅行社总成本：551140()iijjijijpcpx目标函数：目标函数：5511min40()iijjijijpcpx约束：约束：51,ijijijxS 1,2,3,4,5i 51,ijjiijxS 1,2,3,4,5j xij为正整数为正整数5511min40()iijjijijpcpx51,ijijijxS 51,ijjiijxS ,1,2,3,4,5i j xij为正整数，为正整数，. .s t sets: dao/dao1.dao5/:p,s;link(dao,dao):c,x;endsetsmi

23、n=sum(link(i,j):40*(p(i)+c(i,j)+p(j)*x(i,j);for(dao(i):sum(dao(j):x(i,j)=s(i);for(dao(j):sum(dao(i):x(i,j)=s(j);for(link(i,i):x(i,i)=0);for(link:gin(x);data: p=70,115,90,95,85; s=6,11,6,7,5; c=0,46,21,50,60, 46, 0,30,32,55, 21,30, 0,48,53, 50,32,48, 0,21, 60,55,53,21,0; text()=table(x);enddata DAO1

24、DAO2 DAO3 DAO4 DAO5 DAO1 0 3 3 0 0 DAO2 6 0 3 2 0 DAO3 0 6 0 0 0 DAO4 0 2 0 0 5 DAO5 0 0 0 5 0派船方案：派船方案： PABP：3条条 PACP：3条条 PBAP：6条条 PBCP：3条条 PBDP：2条条 PCBP：6条条 PDBP：2条条 PDEP：5条条 PEDP：5条条共需要共需要35条小船，条小船，总成本：总成本：308600假设游船都是满载的。假设游船都是满载的。 问题二：若该公司只经营一日游业务，可同时选择大型船与小问题二：若该公司只经营一日游业务，可同时选择大型船与小型船，应如何规划旅游

25、线路？型船，应如何规划旅游线路？景点旅游景点旅游（半天）（半天）住宿住宿（每晚）（每晚）A A240240B B470470C C250250280280D D280280200200E E210210 表表2: 景点每半天可景点每半天可接待游客的人数接待游客的人数尽可能满足景点最大接待能力：尽可能满足景点最大接待能力：景点景点i 半天最多接待大船数半天最多接待大船数Ti小船数小船数Si剩余剩余接待能力接待能力mi ,构成数组构成数组 (Ti,Si,mi)A:(0,6,0), (1,3,20),(2,1,0)B:(0,11,30),(1,9,10),(2,6,30),(3,4,10),(4,1

26、,30)C:(0,6,10),(1,3,30),(2,1,10)D:(0,7,0),(1,4,20),(2,2,0)E:(0,5,10)寻找满足寻找满足“尽可能满足景点最大接待能力尽可能满足景点最大接待能力”的合理模式！的合理模式！使景点的剩余接待能力最小！使景点的剩余接待能力最小！A:(0,6,0), (1,3,20),(2,1,0)B:(0,11,30),(1,9,10),(2,6,30),(3,4,10),(4,1,30)C:(0,6,10),(1,3,30),(2,1,10)D:(0,7,0),(1,4,20),(2,2,0)E:(0,5,10)“尽可能满足景点最大接待能力尽可能满足景

27、点最大接待能力”的合理模式的合理模式: A B C D E(0,6) (1,9) (0,6) (0,7) (0,5)(0,6) (1,9) (0,6) (2,2) (0,5)(0,6) (1,9) (2,1) (0,7) (0,5)(0,6) (1,9) (2,1) (2,2) (0,5)(0,6) (3,4) (0,6) (0,7) (0,5)(0,6) (3,4) (0,6) (2,2) (0,5)(0,6) (3,4) (2,1) (0,7) (0,5)(0,6) (3,4) (2,1) (2,2) (0,5)“尽可能满足景点最大接待能力尽可能满足景点最大接待能力”的合理模式的合理模式:

28、 A B C D E(2,1) (1,9) (0,6) (0,7) (0,5)(2,1) (1,9) (0,6) (2,2) (0,5)(2,1) (1,9) (2,1) (0,7) (0,5)(2,1) (1,9) (2,1) (2,2) (0,5)(2,1) (3,4) (0,6) (0,7) (0,5)(2,1) (3,4) (0,6) (2,2) (0,5)(2,1) (3,4) (2,1) (0,7) (0,5)(2,1) (3,4) (2,1) (2,2) (0,5)“尽可能满足景点最大接待能力尽可能满足景点最大接待能力”的合理模式的合理模式:模式模式 A B C D E1. (0

29、,6) (1,9) (2,1) (2,2) (0,5)2. (0,6) (3,4) (2,1) (2,2) (0,5)3. (2,1) (1,9) (0,6) (0,7) (0,5)4. (2,1) (1,9) (2,1) (0,7) (0,5)5. (2,1) (1,9) (2,1) (2,2) (0,5)6. (2,1) (3,4) (0,6) (2,2) (0,5)7. (2,1) (3,4) (2,1) (0,7) (0,5)8. (2,1) (3,4) (2,1) (2,2) (0,5)共共8种合理模式！种合理模式！模式模式1：T=(0,1,2,2,0), S=(6,9,1,2,5)

30、 模式模式8：T=(2,3,2,2,0), S=(1,4,1,2,5)决策变量：航程为决策变量：航程为PijP的小船数的小船数xij ，大船数，大船数yij 岛岛i岛岛j的人均费用：的人均费用： cij港口港口P岛岛i的人均费用：的人均费用： pi航程为航程为PijP的小船单船费用：的小船单船费用：40(pi +cij+pj)旅行社总成本：旅行社总成本：航程为航程为PijP的大船单船费用：的大船单船费用：85(pi +cij+pj) 5151)(85)(40ijijjijiijjijiypcpxpcp51,ijjiyT 目标函数：目标函数： 5151)8540)(minijijijjijiyx

31、pcp约束：约束：51,ijijxS 1,2,3,4,5i 51,ijjixS 1,2,3,4,5j xij , yij为正整数为正整数1,2,3,4,5i 51,ijijyT 1,2,3,4,5j 0,0iiiixy目标函数：目标函数： 5151)8540)(minijijijjijiyxpcp xij , yij为正整数为正整数 i,j=1,2,3,4,5sets: dao/dao1.dao5/:p,s,t;link(dao,dao):c,x,y;endsetsmin=sum(link(i,j):(p(i)+c(i,j)+p(j)*(40*x(i,j)+85*y(i,j);for(dao(

32、i):sum(dao(j):x(i,j)=s(i);sum(dao(j):y(i,j)=t(i);for(dao(j):sum(dao(i):x(i,j)=s(j); sum(dao(i):y(i,j)=t(j);for(link(i,i):x(i,i)=0;y(i,i)=0);for(link:gin(x);gin(y);51,ijjiyT 51. .,ijijs txS 51,ijjixS 51,ijijyT 0,iix 0,iiy 模式模式1：T=(0,1,2,2,0), S=(6,9,1,2,5) data: p=70,115,90,95,85; s=6,9,1,2,5; t=0,1,

33、2,2,0; c=0,46,21,50,60, 46, 0,30,32,55, 21,30, 0,48,53, 50,32,48, 0,21, 60,55,53,21,0; text()=table(x); text()=table(y);enddata Objective value: 311600.0 DAO1 DAO2 DAO3 DAO4 DAO5 DAO1 0 5 1 0 0 DAO2 6 0 0 0 3 DAO3 0 1 0 0 0 DAO4 0 0 0 0 2 DAO5 0 3 0 2 0 DAO1 DAO2 DAO3 DAO4 DAO5 DAO1 0 0 0 0 0 DAO2 0

34、 0 1 0 0 DAO3 0 0 0 2 0 DAO4 0 1 1 0 0 DAO5 0 0 0 0 0模式模式1：T=(0,1,2,2,0), S=(6,9,1,2,5) 模式模式2，模式，模式3，模式模式8：T=(2,3,2,2,0), S=(1,4,1,2,5)Objective value 287285.0 DAO1 DAO2 DAO3 DAO4 DAO5 DAO1 0 1 0 0 0 DAO2 0 0 1 0 3 DAO3 1 0 0 0 0 DAO4 0 0 0 0 2 DAO5 0 3 0 2 0 DAO1 DAO2 DAO3 DAO4 DAO5 DAO1 0 1 1 0 0

35、DAO2 0 0 1 2 0 DAO3 2 0 0 0 0 DAO4 0 2 0 0 0 DAO5 0 0 0 0 0三、非线性规划模型三、非线性规划模型 特点：目标函数或约束条件为为非线性函数。特点：目标函数或约束条件为为非线性函数。 一般模型一般模型: 12min(,)nzf x xx 1212(,)0,(1,2,). .(,)0,(1,2, )injnh x xxims tgx xxjl 例例4 （选址问题）某公司有（选址问题）某公司有6个建筑工地，位置坐标为个建筑工地，位置坐标为(ai,bi) (单位单位:km),水泥日用量水泥日用量di (单位：吨）单位：吨）ABCDEFai1.25

36、8.750.55.7537.25bi1.250.754.7556.57.75di3547611(1)现有现有2个料场，位于个料场，位于P(5, 1), Q(2, 7),记记(xj,yj), j=1,2, 日储量日储量ej各为各为20吨。吨。问如何安排每天的供应计划，能使从问如何安排每天的供应计划，能使从P, Q两料场分别两料场分别向各工地运送水泥的总吨公里数最小。向各工地运送水泥的总吨公里数最小。 （假设：料场和工地之间有直线道路）（假设：料场和工地之间有直线道路）决策变量：决策变量：从从P向各工地运量向各工地运量ti1从从Q向各工地运量向各工地运量ti2 21612/ 122)()(minj

37、iijijijbyaxt,61jiijet ,21ijijdt (i=1,2,6; j=1,2)s.t:sets: demand/1.6/:a,b,d; supply/1,2/:x,y,e;link(demand,supply):t; endsetsOBJmin=sum(link(i,j):t(i,j)*sqrt(x(j)-a(i)2+(y(j)-b(i)2);for(supply(j):sum(demand(i): t(i,j)=e(j);for(demand(i):sum(supply(j): t(i,j)=d(i);data:a=1.25,8.75,0.5,5.75,3,7.25;b=1

38、.25,0.75,4.75,5,6.5,7.75;d=3,5,4,7,6,11;e=20,20;x=5,2;y=1,7;text()=table(t);enddata(2) 改建两个新料场，需要确定新料场位置改建两个新料场，需要确定新料场位置(xj,yj)和运和运量量tij ，在其它条件不变下使总吨公里数最小。，在其它条件不变下使总吨公里数最小。 21612/ 122)()(minjiijijijbyaxt,61jiijet ,21ijijdt (i=1,2,6; j=1,2)s.t: 21612/ 122)()(minjiijijijbyaxt,61jiijet ,21ijijdt (i=1

39、,2,6; j=1,2)s.t:sets: demand/1.6/:a,b,d; supply/1,2/:x,y,e;link(demand,supply):t; endsetsOBJmin=sum(link(i,j):t(i,j)*sqrt(x(j)-a(i)2+(y(j)-b(i)2);for(supply(j):sum(demand(i): t(i,j)0, d-=0 若未完成指标若未完成指标, d+=0, d- 0 恰好完成指标恰好完成指标, d+=0, d-=0则必有：则必有： d+d- 032145 . 35 . 2 minxxxz 24012108 .321 xxxts101 x

40、152 x93 xxi为正整数为正整数实际利润实际利润z*=82当且仅当当且仅当d+d-=0， 即即d+d- 达到最小达到最小 ddz min32145 . 35 . 2 minxxxz ddz min24012108 .321 xxxts101 x152 x93 x0 d0 dxi为正整数为正整数8245 . 35 . 2321 ddxxx32145 . 35 . 2 minxxxz 24012108 .321 xxxts101 x152 x93 xxi为正整数为正整数工厂要求工厂要求（4）尽可能达到或超过原计划利润指标）尽可能达到或超过原计划利润指标82万元。万元。（1）B型车的产量不大于

41、型车的产量不大于C型车的产量。型车的产量。8245 . 35 . 211321 ddxxx（3）尽量充分利用设备台时，不要加班生产）尽量充分利用设备台时，不要加班生产32xx 02232 ddxx2401210844321 ddxxx（2）适当降低）适当降低A型车产量。型车产量。10331 ddx目标函数：目标函数： 1 mindz 2d 3d 44dd根据各目标的重要程度，赋予权值根据各目标的重要程度，赋予权值目标函数：目标函数： 11 mindpz 22dp 33dp)(444 ddp8245 . 35 . 2 .11321 ddxxxts02232 ddxx10331 ddx240121

42、0844321 ddxxx,101 x,152 x93 x, 0 id3 , 2 , 1 , 0 idixi为正整数为正整数1.基本概念基本概念 （1）偏差量：）偏差量： 正偏差量表示超额完成指标偏差量：正偏差量表示超额完成指标偏差量： d+=指标的实际值指标的实际值-预计的指标值；预计的指标值； 负偏差量表示未完成指标的偏差量：负偏差量表示未完成指标的偏差量： d-=预计的指标值预计的指标值-指标的实际值。指标的实际值。 若超额完成了指标，则若超额完成了指标，则d+ 0，d- =0； 若未完成指标，则若未完成指标，则d- 0，d+=0； 若恰好完成指标，则若恰好完成指标，则d+ =d- =0

43、；（2 2）绝对（刚性）约束和目标约束：）绝对（刚性）约束和目标约束： 绝对约束是指必须满足的等式约束或者不等式绝对约束是指必须满足的等式约束或者不等式约束。约束。 目标约束是目标规划特有的，可以把约束右端目标约束是目标规划特有的，可以把约束右端项看作是想要达到的目标值，在达到此目标值时允项看作是想要达到的目标值，在达到此目标值时允许存在正的或者负的偏差，因此在这约束条件中加许存在正的或者负的偏差，因此在这约束条件中加入正、负偏差量。入正、负偏差量。（3）优先因子与权系数：）优先因子与权系数： 对于任意一个多目标决策问题中多个目标总能对于任意一个多目标决策问题中多个目标总能有主次之分，也就是可

44、以根据各个目标的主次排出有主次之分，也就是可以根据各个目标的主次排出优先级。优先级。（4）目标函数与偏差变量：）目标函数与偏差变量： 目标规划的目标函数是：目标规划的目标函数是：min=f(d+,d-) 假设要求恰好达到目标值，即要求目标的正负偏差假设要求恰好达到目标值，即要求目标的正负偏差都尽可能的小都尽可能的小; 假设要求超过指标值，即要求目标的正偏差不限，假设要求超过指标值，即要求目标的正偏差不限，而负偏差越小越好；而负偏差越小越好； 假设要求不超过指标值，即要求目标的负偏差不限，假设要求不超过指标值，即要求目标的负偏差不限，而正偏差越小越好。而正偏差越小越好。 KkLllkllklkd

45、wdwpz11)(minn-1n1- 1,2 1,2. .0 1,2,0 1,2ljjllljljjijjllc xddglLa xbmms txjnd dlL （， ， ）（ ，）（， ， ）（， ， ）（， ， ）多目标决策问题的一般的目标规划模型多目标决策问题的一般的目标规划模型例例6 （节能灯具生产问题）某灯具厂接到了订购（节能灯具生产问题）某灯具厂接到了订购16000套套A型和型和B型节能灯具的订货合同，合同中没有对两种灯具各自的数量型节能灯具的订货合同，合同中没有对两种灯具各自的数量做要求，但合同要求工厂在一周内完成生产任务并交货。根据做要求，但合同要求工厂在一周内完成生产任务并交

46、货。根据该厂的生产能力，一周内可以利用的生产时间为该厂的生产能力，一周内可以利用的生产时间为20000min，可，可利用的包装时间为利用的包装时间为36000min，生产和包装完成一套，生产和包装完成一套A型灯具各型灯具各需要需要2min，生产和包装完成一套，生产和包装完成一套B型灯具分别需要型灯具分别需要1min和和3min，每套每套A型灯具成本型灯具成本7元，销售价元，销售价15元；每套元；每套B型灯具成本型灯具成本14元，元，销售价销售价20元；厂长要求元；厂长要求:(1)必须要按合同完成任务，既不要有必须要按合同完成任务，既不要有不足量也不要有超过量。不足量也不要有超过量。(2)销售额

47、尽量达到或接近销售额尽量达到或接近275000元。元。(3)在生产时间和包装时间上可以有所增加，但超过量尽可能小。在生产时间和包装时间上可以有所增加，但超过量尽可能小。在实际中增加生产时间比增加包装时间困难的多，试为该厂制在实际中增加生产时间比增加包装时间困难的多，试为该厂制定生产计划。定生产计划。要求要求:(1)必须要按合同完成任务，既不要有不足量也不要有超必须要按合同完成任务，既不要有不足量也不要有超过量。过量。(x1+x2=16000)决策变量：分别决策变量：分别 x1 , x2分别表示分别表示A型、型、B型灯具的数量。型灯具的数量。用用 分别表示未达到和超额完成分别表示未达到和超额完成

48、16000套的偏差量；套的偏差量； 11,dd)min(11 dd16000:.1121 ddxxts(2)销售额尽量达到或接近销售额尽量达到或接近275000元。元。用用 分别表示未完成和超额完成销售指标的偏差量；分别表示未完成和超额完成销售指标的偏差量； 22,dd27500020152221 ddxx 2mind(3)在生产时间和包装时间上可以有所增加，但超过量尽可能小。在生产时间和包装时间上可以有所增加，但超过量尽可能小。用用 分别表示减少和增加生产时间的偏差量；分别表示减少和增加生产时间的偏差量；用用 分别表示减少和增加包装时间的偏差量；分别表示减少和增加包装时间的偏差量； 33,d

49、d 44,dd2000023321 ddxx36000324421 ddxx)6 . 04 . 0min(43 dd在实际中增加生产时间比增加包装时间困难的多在实际中增加生产时间比增加包装时间困难的多首先确定问题目标的优先级：首先确定问题目标的优先级： 第一优先级：恰好生产和包装完成节能灯具第一优先级：恰好生产和包装完成节能灯具16000套，赋予优先因子套，赋予优先因子p1； 第二优先级：完成或尽量完成销售额第二优先级：完成或尽量完成销售额275000元，赋予优先因子元，赋予优先因子p2； 第三优先级：生产时间和包装时间的增加尽量第三优先级：生产时间和包装时间的增加尽量的小，赋予优先因子的小，

50、赋予优先因子p3；该问题的目标规划模型：该问题的目标规划模型：)6 . 04 . 0()(min43322111 ddpdpddp :.ts160001121 ddxx27500020152221 ddxx2000023321 ddxx36000324421 ddxx, 0, 0, 0,21 iiddxx4 , 3 , 2 , 1 i模型求解：采用序贯算法模型求解：采用序贯算法模型求解的序贯算法：模型求解的序贯算法：)6 . 04 . 0()(min43322111 ddpdpddp11121gddxx 222212015gddxx 333212gddxx 4442132gddxx , 0,

51、0, 0,21 iiddxx4 , 3 , 2 , 1 i第一步：求解第一目标模型第一步：求解第一目标模型)( min11 ddz11121gddxx 222212015gddxx 333212gddxx 4442132gddxx , 0, 0, 0,21 iiddxx得最优值：得最优值：1z模型求解的序贯算法：模型求解的序贯算法：)6 . 04 . 0()(min43322111 ddpdpddp11121gddxx 222212015gddxx 333212gddxx 4442132gddxx , 0, 0, 0,21 iiddxx4 , 3 , 2 , 1 i第二步：求解第二目标模型第二

52、步：求解第二目标模型 2 mindz11121gddxx 222212015gddxx 333212gddxx 4442132gddxx , 0, 0, 0,21 iiddxx得最优值：得最优值：2z111zdd 模型求解的序贯算法：模型求解的序贯算法：)6 . 04 . 0()(min43322111 ddpdpddp11121gddxx 222212015gddxx 333212gddxx 4442132gddxx , 0, 0, 0,21 iiddxx4 , 3 , 2 , 1 i第三步：求解第三目标模型第三步：求解第三目标模型 436 . 04 . 0 minddz11121gddxx

53、 222212015gddxx 333212gddxx 4442132gddxx , 0, 0, 0,21 iiddxx得最优值：得最优值：3z111zdd 22zd )6 . 04 . 0()(min43322111 ddpdpddp11121gddxx 222212015gddxx 333212gddxx 4442132gddxx , 0, 0, 0,21 iiddxx4 , 3 , 2 , 1 i 3121)(minijijijidwpiiiiigddxcxc 212211记：记： iiiidddd21, 0, 0 ijjdx2 , 1; 4 , 3 , 2 , 1 ji模型化为：模型化

54、为：记：记： 21jijijidwf 31miniiifp模型化为：模型化为： 21jijijidwfiiijjigddxc 212112 , 1; 4 , 3 , 2 , 1 ji .ts, 0, 0 ijjdx 31miniiifp模型化为：模型化为： 21jijijidwf2 , 1; 4 , 3 , 2 , 1 ji .ts, 0, 0 ijjdxiiijjijgddxc 2121sets:nx/1.2/:x;you/1.3/:p,f,z;obj/1.4/:d1,d2,g;link1(you,obj):w1,w2; link2(obj,nx): c;endsets160001121 d

55、dxx27500020152221 ddxx2000023321 ddxx36000324421 ddxx, 0, 0, 0,21 iiddxx4 , 3 , 2 , 1 idata:p=?;z=?0;c=1,1,15,20,2,1,2,3;g=16000,275000,20000,36000;w1=1,0,0,0, 0,1,0,0, 0,0,0,0;w2=1,0,0,0, 0,0,0,0, 0,0,0.4,0.6;enddata 31miniiifp 21jijijidwf2 , 1; 4 , 3 , 2 , 1 ji .ts, 0, 0 ijjdxiiijjijgddxc 2121min=

56、 sum(you:p*f);for(you(k):f(k)=sum(obj(i): (w1(k,i)*d1(i)+w2(k,i)*d2(i);); for(obj(i):sum(nx(j):c(i,j)*x(j)+d1(i)-d2(i)=g(i);for(obj(k)|k#lt#size(you):bnd(0,f(k),z(k););for(nx: gin(x);程序运行方法：程序运行方法：共有三级目标，需运行三次该程序。共有三级目标，需运行三次该程序。第一次运行时，取第一次运行时，取p(1)=1, p(2)= p(3)=0, z(1)与与z(2)都取较都取较大的值。大的值。得：得：Objec

57、tive value: 0.000000，X( 1) 0.000000 X( 2) 16000.00 第二次运行时，取第二次运行时，取p(1)=0, p(2)=1, p(3)=0, z(1)=0, z(2)取取较大的值。较大的值。得：得：Objective value: 0.000000，X( 1) 0.000000 X( 2) 16000.00第三次运行时，取第三次运行时，取p(1)=0, p(2)=0, p(3)=0, z(1)=0, z(2)=0得：得： X( 1) 9000 X( 2) 7000 D2(3) 5000 D2(4) 3000第三次运行时，取第三次运行时，取p(1)=0,

58、p(2)=0, p(3)=0, z(1)=0, z(2)=0得：得：X( 1) 9000 X( 2) 7000 D2(3) 5000 D2(4) 3000该厂生产该厂生产A灯具灯具9000套，套，B灯具灯具7000套，可完成计划，套，可完成计划，且完成销售指标且完成销售指标275000元，生产时间需增加元，生产时间需增加5000min，包装时间需增加包装时间需增加3000min。 交巡警服务平台的设置与调度交巡警服务平台的设置与调度 警察肩负着刑事执法、治安管理、交通管理、服务群众四警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些大职能。

59、为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面

60、的问题：型分析研究下面的问题： 附图附图1给出了该市中心城区给出了该市中心城区A的交通网络和现有的的交通网络和现有的20个交个交巡警服务平台的设置情况示意图，相关的数据信息见附件巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为分钟内有交巡警（警车的时速为60km/h）到达事发地。）到达事发地。附图附图1：A区的交通网络与平台设置的示意图区的交通网络与平台设置的示意图 说明：（说明：（1）图中实线表示市区道