运筹学案例8培训讲学

运筹学案例8精品文档精品文档收集于网络，如有侵权请联系管理员删除收集于网络，如有侵权请联系管理员删除精品文档收集于网络，如有侵权请联系管理员删除运筹学案例8报告组员晋榕榕尹琪徐凯文耿志强张晗模型假设 1问题分析 1模型求解 2LINGO程序部分： 2题目a 2题目b 4题目c 5程序运行结果： 7题目a 7题目b 13题目c 19结果分析 25问题a 25问题b 26问题c 27附录 28原问题的中文版本描述 28问题的英文原版描述 30模型假设首先我们假设每位艺术家作品数量都是4件,并将其中作品数目不足4件的艺术家的作品所对应的变量xij的值取为0，同时，展品展出所需的费用全部包含在表中所列价格中。问题分析通过讨论分析，我们认为题目a所要求解的是在艾西·布里格斯所提供的资金（400万）的范围内，能够展出的展品的最大数目以及展出的具体艺术家及其作品。题目b要求求解在保证展品数目不少于20件的条件下，使本次展览所耗费的资金数量最小的方案以及展出的具体作品。题目c是要求解在确保20件展品的情况下，求赞助人利塔·罗斯基所需要出资的最小的数目以及展出的具体作品。这一问题在所提供的中文版本的案例中的描述不够准确，所以我们查阅了英文原版案例。决策变量xiji=1,2,……,13j=1,2,3,4各变量的取值为0或1，当展品展出时变量取值为1，否则取0。故此问题为0-1规划。题目a目标函数max约束条件由此建立模型如下max题目b目标函数min约束条件由此建立模型如下题目c目标函数min约束条件由此建立模型如下模型求解由上面分析可知此案例属于0-1规划问题，所以我们利用LINGO来求解各个问题。以下是每个问题对应的LINGO程序以及结果。LINGO程序部分：题目a!案例8分配艺术品（ItroductiontoManagementScience,F.S.Hillier,Case9-2AssigningArt）;!a题;!所有的价格以万元为单位;model:sets: artist/1..13/; piece/1..4/; link(artist,piece):price,x;endsets!目标函数;max=@sum(artist(I):@sum(piece(J):x(I,J)));!约束条件;x(3,2)+x(7,1)+x(12,1)+x(12,2)=1;!collage;@sign(@sum(piece(I)|I#le#3:x(1,I))-1)=@sign(@sum(piece(I)|I#le#2:x(2,I))-1);!wiremeshsculpture,computerpainting;@sum(piece(I)|I#le#2:x(6,I))+x(8,1)>=1;!photo-realistic;@sum(piece(I)|I#le#2:x(11,I))+x(8,2)>=1;!cubist;x(8,3)>=1;!expressionist;@sum(piece(I)|I#le#2:x(4,I))+@sum(piece(I)|I#le#4:x(13,I))>=1;!water-color;@sum(piece(I)|I#le#2:x(5,I))+@sum(piece(I)|I#le#2:x(9,I))+x(10,3)>=1;!油画oil-paint;@sum(artist(I)|I#ne#1#and#I#ne#2#and#I#ne#3#and#I#ne#7#and#I#ne#10#and#I#ne#12:@sum(piece(J)|J#le#2:x(I,J)))+x(8,3)+x(10,3)+x(13,3)+x(13,4)<=2*(@sum(artist(I)|I#eq#1#or#I#eq#2#or#I#eq#3#or#I#eq#7#or#I#eq#12:@sum(piece(J):x(I,J)))+x(10,1)+x(10,2));!绘画<=其他x2(painting<=2xother-form);!@sum(artist(I)|I#ne#1#and#I#ne#3#and#I#ne#7#and#I#ne#11#and#I#ne#12:@sum(piece(J):x(I,J)))+x(11,1)<=20;!绘画<=20(这个条件在原书中没有);@sum(piece(I)|I#le#4:x(13,I))=4;!allAsh;@sum(piece(I)|I#le#2:x(4,I))=2;!凯蒂作品全展出allCandy;@sum(piece(I)|I#le#4:x(6,I))=@sum(piece(I)|I#le#4:x(8,I));!戴维，里克作品数相等;@sum(piece(I)|I#le#4:x(6,I))>=1;!而且都大于1;@sum(piece(I)|I#le#4:x(12,I))<=1;!Ziggy的作品不多于1件;@sum(artist(I)|I#ne#2#and#I#ne#4#and#I#ne#7#and#I#ne#11:@sum(piece(J):x(I,J)))<=2*(@sum(artist(I)|I#eq#2#or#I#eq#4#or#I#eq#7#or#I#eq#11:@sum(piece(J):x(I,J))));!男<=女x2;@sum(piece(I)|I#le#2:x(3,I))>=1;!老年地球，浪费资源;@sum(piece(I)|I#le#4:x(10,I))>=1;!Bill至少有一件;x(2,1)+x(2,2)+x(9,1)+x(9,2)>=1;!混沌至少一件;@sum(piece(I)|I#le#4:x(1,I))+x(3,1)+x(7,2)+x(7,3)<=4;!雕像<=4;@sum(artist(I):@sum(piece(J):x(I,J)))-(@sum(piece(I)|I#le#4:x(1,I))+x(3,1)+x(7,2)+x(7,3))<=20;!20painting,collage,drawing;x(7,2)>=x(12,2);!自恋，沉思;@sum(artist(I):@sum(piece(J):price(I,J)*x(I,J)))<=400;!总价格约束;total_price_used=@sum(artist(I):@sum(piece(J):price(I,J)*x(I,J)));!得到的总价格;total_display=@sum(artist(I):@sum(piece(J):x(I,J)));!总展出数;!限制变量取值;x(1,4)+x(3,3)+x(3,4)+x(4,3)+x(4,4)+x(5,3)+x(5,4)+x(6,3)+x(6,4)+x(7,4)+x(8,4)+x(9,3)+x(9,4)+x(10,4)+x(11,3)+x(11,4)+x(12,3)+x(12,4)=0;!空缺部分;@for(artist(I):@for(piece(J):@bin(x(I,J))));!限制变量取值0-1;!数据部分;data: price=302512.50 40504055 7057.500 2022.500 151500 857500 4017.5450 5050500 656500 2535450 404000 303000 5555;enddataend题目b!案例8分配艺术品（ItroductiontoManagementScience,F.S.Hillier,Case9-2AssigningArt）;!b题;!所有的价格以万元为单位;model:sets: artist/1..13/; piece/1..4/; link(artist,piece):price,x;endsets!目标函数;!max=@sum(artist(I):@sum(piece(J):x(I,J)));min=@sum(artist(I):@sum(piece(J):price(I,J)*x(I,J)));!最小花费;!约束条件;x(3,2)+x(7,1)+x(12,1)+x(12,2)=1;!collage;@sign(@sum(piece(I)|I#le#3:x(1,I))-1)=@sign(@sum(piece(I)|I#le#2:x(2,I))-1);!wiremeshsculpture,computerpainting;@sum(piece(I)|I#le#2:x(6,I))+x(8,1)>=1;!photo-realistic;@sum(piece(I)|I#le#2:x(11,I))+x(8,2)>=1;!cubist;x(8,3)>=1;!expressionist;@sum(piece(I)|I#le#2:x(4,I))+@sum(piece(I)|I#le#4:x(13,I))>=1;!water-color;@sum(piece(I)|I#le#2:x(5,I))+@sum(piece(I)|I#le#2:x(9,I))+x(10,3)>=1;!油画oil-paint;@sum(artist(I)|I#ne#1#and#I#ne#2#and#I#ne#3#and#I#ne#7#and#I#ne#10#and#I#ne#12:@sum(piece(J)|J#le#2:x(I,J)))+x(8,3)+x(10,3)+x(13,3)+x(13,4)<=2*(@sum(artist(I)|I#eq#1#or#I#eq#2#or#I#eq#3#or#I#eq#7#or#I#eq#12:@sum(piece(J):x(I,J)))+x(10,1)+x(10,2));!绘画<=其他x2(painting<=2xother-form);!@sum(artist(I)|I#ne#1#and#I#ne#3#and#I#ne#7#and#I#ne#11#and#I#ne#12:@sum(piece(J):x(I,J)))+x(11,1)<=20;!绘画<=20(这个条件在原书中没有);@sum(piece(I)|I#le#4:x(13,I))=4;!allAsh;@sum(piece(I)|I#le#2:x(4,I))=2;!凯蒂作品全展出allCandy;@sum(piece(I)|I#le#4:x(6,I))=@sum(piece(I)|I#le#4:x(8,I));!戴维，里克作品数相等;@sum(piece(I)|I#le#4:x(6,I))>=1;!而且都大于1;@sum(piece(I)|I#le#4:x(12,I))<=1;!Ziggy的作品不多于1件;@sum(artist(I)|I#ne#2#and#I#ne#4#and#I#ne#7#and#I#ne#11:@sum(piece(J):x(I,J)))<=2*(@sum(artist(I)|I#eq#2#or#I#eq#4#or#I#eq#7#or#I#eq#11:@sum(piece(J):x(I,J))));!男<=女x2;@sum(piece(I)|I#le#2:x(3,I))>=1;!老年地球，浪费资源;@sum(piece(I)|I#le#4:x(10,I))>=1;!Bill至少有一件;x(2,1)+x(2,2)+x(9,1)+x(9,2)>=1;!混沌至少一件;@sum(piece(I)|I#le#4:x(1,I))+x(3,1)+x(7,2)+x(7,3)<=4;!雕像<=4;@sum(artist(I):@sum(piece(J):x(I,J)))-(@sum(piece(I)|I#le#4:x(1,I))+x(3,1)+x(7,2)+x(7,3))<=20;!20painting,collage,drawing;x(7,2)>=x(12,2);!自恋，沉思;!@sum(artist(I):@sum(piece(J):price(I,J)*x(I,J)))<=400;!总价格约束;@sum(artist(I):@sum(piece(J):x(I,J)))>=20;!增加约束，展品数>=20;total_price=@sum(artist(I):@sum(piece(J):price(I,J)*x(I,J)));!总价格;total_display=@sum(artist(I):@sum(piece(J):x(I,J)));!总展品数;!限制变量取值;x(1,4)+x(3,3)+x(3,4)+x(4,3)+x(4,4)+x(5,3)+x(5,4)+x(6,3)+x(6,4)+x(7,4)+x(8,4)+x(9,3)+x(9,4)+x(10,4)+x(11,3)+x(11,4)+x(12,3)+x(12,4)=0;!空缺部分;@for(artist(I):@for(piece(J):@bin(x(I,J))));!限制变量取值0-1;!数据部分;data: price=302512.50 40504055 7057.500 2022.500 151500 857500 4017.5450 5050500 656500 2535450 404000 303000 5555;enddataend题目c!案例8分配艺术品（ItroductiontoManagementScience,F.S.Hillier,Case9-2AssigningArt）;!c题;!所有的价格以万元为单位;model:sets: artist/1..13/; piece/1..4/; link(artist,piece):price,x;endsets!目标函数;!max=@sum(artist(I):@sum(piece(J):x(I,J)));min=@sum(artist(I):@sum(piece(J):price(I,J)*x(I,J)));!最小花费;!约束条件;x(3,2)+x(7,1)+x(12,1)+x(12,2)=1;!collage;@sign(@sum(piece(I)|I#le#3:x(1,I)))=@sign(@sum(piece(I)|I#le#2:x(2,I)));!wiremeshsculpture,computerpainting;@sum(piece(I)|I#le#2:x(6,I))+x(8,1)>=1;!photo-realistic;@sum(piece(I)|I#le#2:x(11,I))+x(8,2)>=1;!cubist;x(8,3)>=1;!expressionist;@sum(piece(I)|I#le#2:x(4,I))+@sum(piece(I)|I#le#4:x(13,I))>=1;!water-color;@sum(piece(I)|I#le#2:x(5,I))+@sum(piece(I)|I#le#2:x(9,I))+x(10,3)>=1;!油画oil-paint;@sum(artist(I)|I#ne#1#and#I#ne#2#and#I#ne#3#and#I#ne#7#and#I#ne#10#and#I#ne#12:@sum(piece(J)|J#le#2:x(I,J)))+x(8,3)+x(10,3)+x(13,3)+x(13,4)<=2*(@sum(artist(I)|I#eq#1#or#I#eq#2#or#I#eq#3#or#I#eq#7#or#I#eq#12:@sum(piece(J):x(I,J)))+x(10,1)+x(10,2));!绘画<=其他x2(painting<=2xother-form);!@sum(artist(I)|I#ne#1#and#I#ne#3#and#I#ne#7#and#I#ne#11#and#I#ne#12:@sum(piece(J):x(I,J)))+x(11,1)<=20;!绘画<=20(这个条件在原书中没有);@sum(piece(I)|I#le#4:x(13,I))=4;!allAsh;@sum(piece(I)|I#le#2:x(4,I))=2;!凯蒂作品全展出allCandy;@sum(piece(I)|I#le#4:x(6,I))=@sum(piece(I)|I#le#4:x(8,I));!戴维，里克作品数相等;@sum(piece(I)|I#le#4:x(6,I))>=1;!而且都大于1;@sum(piece(I)|I#le#4:x(12,I))<=1;!Ziggy的作品不多于1件;@sum(artist(I)|I#ne#2#and#I#ne#4#and#I#ne#7#and#I#ne#11:@sum(piece(J):x(I,J)))<=2*(@sum(artist(I)|I#eq#2#or#I#eq#4#or#I#eq#7#or#I#eq#11:@sum(piece(J):x(I,J))));!男<=女x2;@sum(piece(I)|I#le#2:x(3,I))>=1;!老年地球，浪费资源;@sum(piece(I)|I#le#4:x(10,I))>=1;!Bill至少有一件;x(2,1)+x(2,2)+x(9,1)+x(9,2)>=1;!混沌至少一件;@sum(piece(I)|I#le#4:x(1,I))+x(3,1)+x(7,2)+x(7,3)<=4;!雕像<=4;@sum(artist(I):@sum(piece(J):x(I,J)))-(@sum(piece(I)|I#le#4:x(1,I))+x(3,1)+x(7,2)+x(7,3))<=20;!20painting,collage,drawing;x(7,2)>=x(12,2);!自恋，沉思;!@sum(artist(I):@sum(piece(J):price(I,J)*x(I,J)))<=400;!总价格约束;@sum(artist(I):@sum(piece(J):x(I,J)))>=20;!增加约束，展品数>=20;!增加的约束条件;@sum(artist(I):@sum(piece(J):x(I,J)))=20;!总展品数;@sum(piece(I)|I#le#4:x(2,I))=4;!allLoskey;total_price=@sum(artist(I):@sum(piece(J):price(I,J)*x(I,J)));!总价格;total_display=@sum(artist(I):@sum(piece(J):x(I,J)));!总展品数;patron_pay=@sum(artist(I):@sum(piece(J):price(I,J)*x(I,J)))-400;!限制变量取值;x(1,4)+x(3,3)+x(3,4)+x(4,3)+x(4,4)+x(5,3)+x(5,4)+x(6,3)+x(6,4)+x(7,4)+x(8,4)+x(9,3)+x(9,4)+x(10,4)+x(11,3)+x(11,4)+x(12,3)+x(12,4)=0;!空缺部分;@for(artist(I):@for(piece(J):@bin(x(I,J))));!限制变量取值0-1;!数据部分;data: price=302512.50 40504055 7057.500 2022.500 151500 857500 4017.5450 5050500 656500 2535450 404000 303000 5555;enddataend程序运行结果：题目aLocaloptimalsolutionfound.Objectivevalue:15.00000Objectivebound:15.00000Infeasibilities:0.000000Extendedsolversteps:2Totalsolveriterations:176VariableValueReducedCostTOTAL_PRICE_USED395.00000.000000TOTAL_DISPLAY15.000000.000000PRICE(1,1)30.000000.000000PRICE(1,2)25.000000.000000PRICE(1,3)12.500000.000000PRICE(1,4)0.0000000.000000PRICE(2,1)40.000000.000000PRICE(2,2)50.000000.000000PRICE(2,3)40.000000.000000PRICE(2,4)55.000000.000000PRICE(3,1)70.000000.000000PRICE(3,2)57.500000.000000PRICE(3,3)0.0000000.000000PRICE(3,4)0.0000000.000000PRICE(4,1)20.000000.000000PRICE(4,2)22.500000.000000PRICE(4,3)0.0000000.000000PRICE(4,4)0.0000000.000000PRICE(5,1)15.000000.000000PRICE(5,2)15.000000.000000PRICE(5,3)0.0000000.000000PRICE(5,4)0.0000000.000000PRICE(6,1)85.000000.000000PRICE(6,2)75.000000.000000PRICE(6,3)0.0000000.000000PRICE(6,4)0.0000000.000000PRICE(7,1)40.000000.000000PRICE(7,2)17.500000.000000PRICE(7,3)45.000000.000000PRICE(7,4)0.0000000.000000PRICE(8,1)50.000000.000000PRICE(8,2)50.000000.000000PRICE(8,3)50.000000.000000PRICE(8,4)0.0000000.000000PRICE(9,1)65.000000.000000PRICE(9,2)65.000000.000000PRICE(9,3)0.0000000.000000PRICE(9,4)0.0000000.000000PRICE(10,1)25.000000.000000PRICE(10,2)35.000000.000000PRICE(10,3)45.000000.000000PRICE(10,4)0.0000000.000000PRICE(11,1)40.000000.000000PRICE(11,2)40.000000.000000PRICE(11,3)0.0000000.000000PRICE(11,4)0.0000000.000000PRICE(12,1)30.000000.000000PRICE(12,2)30.000000.000000PRICE(12,3)0.0000000.000000PRICE(12,4)0.0000000.000000PRICE(13,1)5.0000000.000000PRICE(13,2)5.0000000.000000PRICE(13,3)5.0000000.000000PRICE(13,4)5.0000000.000000X(1,1)0.0000000.000000X(1,2)0.0000000.000000X(1,3)1.0000000.000000X(1,4)0.0000001.000000X(2,1)1.000000-2.000000X(2,2)0.000000-2.000000X(2,3)0.000000-1.000000X(2,4)0.000000-1.000000X(3,1)0.000000-1.000000X(3,2)1.0000000.000000X(3,3)0.0000001.000000X(3,4)0.0000001.000000X(4,1)1.0000000.000000X(4,2)1.0000000.000000X(4,3)0.0000001.000000X(4,4)0.0000001.000000X(5,1)1.000000-1.000000X(5,2)0.000000-1.000000X(5,3)0.0000001.000000X(5,4)0.0000001.000000X(6,1)0.000000-2.000000X(6,2)1.000000-2.000000X(6,3)0.0000000.000000X(6,4)0.0000000.000000X(7,1)0.0000000.000000X(7,2)1.000000-1.000000X(7,3)0.000000-1.000000X(7,4)0.0000001.000000X(8,1)0.0000000.000000X(8,2)0.0000000.000000X(8,3)1.0000000.000000X(8,4)0.0000002.000000X(9,1)0.000000-1.000000X(9,2)0.000000-1.000000X(9,3)0.0000001.000000X(9,4)0.0000001.000000X(10,1)1.000000-1.000000X(10,2)0.000000-1.000000X(10,3)0.000000-1.000000X(10,4)0.0000001.000000X(11,1)1.000000-1.000000X(11,2)0.000000-1.000000X(11,3)0.0000001.000000X(11,4)0.0000001.000000X(12,1)0.0000000.000000X(12,2)0.0000000.000000X(12,3)0.0000001.000000X(12,4)0.0000001.000000X(13,1)1.000000-1.000000X(13,2)1.000000-1.000000X(13,3)1.000000-1.000000X(13,4)1.000000-1.000000RowSlackorSurplusDualPrice115.000001.00000020.0000001.00000030.0000001.00000040.0000000.00000050.0000000.00000060.0000000.00000075.0000000.00000080.0000000.00000090.0000000.000000100.0000000.000000110.0000001.000000120.000000-1.000000130.0000000.000000141.0000000.000000150.0000000.000000160.0000000.000000170.0000000.000000180.0000000.000000192.0000000.000000207.0000000.000000211.0000000.000000225.0000000.000000230.0000000.000000240.0000000.000000250.0000002.000000题目bLocaloptimalsolutionfound.Objectivevalue:560.0000Objectivebound:560.0000Infeasibilities:0.6888934E-13Extendedsolversteps:0Totalsolveriterations:17VariableValueTOTAL_PRICE560.0000TOTAL_DISPLAY20.00000PRICE(1,1)30.00000PRICE(1,2)25.00000PRICE(1,3)12.50000PRICE(1,4)0.000000PRICE(2,1)40.00000PRICE(2,2)50.00000PRICE(2,3)40.00000PRICE(2,4)55.00000PRICE(3,1)70.00000PRICE(3,2)57.50000PRICE(3,3)0.000000PRICE(3,4)0.000000PRICE(4,1)20.00000PRICE(4,2)22.50000PRICE(4,3)0.000000PRICE(4,4)0.000000PRICE(5,1)15.00000PRICE(5,2)15.00000PRICE(5,3)0.000000PRICE(5,4)0.000000PRICE(6,1)85.00000PRICE(6,2)75.00000PRICE(6,3)0.000000PRICE(6,4)0.000000PRICE(7,1)40.00000PRICE(7,2)17.50000PRICE(7,3)45.00000PRICE(7,4)0.000000PRICE(8,1)50.00000PRICE(8,2)50.00000PRICE(8,3)50.00000PRICE(8,4)0.000000PRICE(9,1)65.00000PRICE(9,2)65.00000PRICE(9,3)0.000000PRICE(9,4)0.000000PRICE(10,1)25.00000PRICE(10,2)35.00000PRICE(10,3)45.00000PRICE(10,4)0.000000PRICE(11,1)40.00000PRICE(11,2)40.00000PRICE(11,3)0.000000PRICE(11,4)0.000000PRICE(12,1)30.00000PRICE(12,2)30.00000PRICE(12,3)0.000000PRICE(12,4)0.000000PRICE(13,1)5.000000PRICE(13,2)5.000000PRICE(13,3)5.000000PRICE(13,4)5.000000X(1,1)0.000000X(1,2)1.000000X(1,3)1.000000X(1,4)0.000000X(2,1)1.000000X(2,2)1.000000X(2,3)1.000000X(2,4)0.000000X(3,1)0.000000X(3,2)1.000000X(3,3)0.000000X(3,4)0.000000X(4,1)1.000000X(4,2)1.000000X(4,3)0.000000X(4,4)0.000000X(5,1)1.000000X(5,2)1.000000X(5,3)0.000000X(5,4)0.000000X(6,1)0.000000X(6,2)1.000000X(6,3)0.000000X(6,4)0.000000X(7,1)0.000000X(7,2)1.000000X(7,3)0.000000X(7,4)0.000000X(8,1)0.000000X(8,2)0.000000X(8,3)1.000000X(8,4)0.000000X(9,1)0.000000X(9,2)0.000000X(9,3)0.000000X(9,4)0.000000X(10,1)1.000000X(10,2)1.000000X(10,3)0.000000X(10,4)0.000000X(11,1)1.000000X(11,2)0.000000X(11,3)0.000000X(11,4)0.000000X(12,1)0.000000X(12,2)0.000000X(12,3)0.000000X(12,4)0.000000X(13,1)1.000000X(13,2)1.000000X(13,3)1.000000X(13,4)1.000000RowSlackorSurplus1560.000020.00000030.00000040.00000050.00000060.00000075.00000081.00000097.000000100.000000110.000000120.000000130.000000141.000000151.000000160.000000171.000000