运筹学案例8培训讲学.doc

运筹学案例8精品文档运筹学案例8报告组员 晋榕榕 尹琪 徐凯文 耿志强 张晗模型假设1问题分析1模型求解2LINGO程序部分：2题目a2题目b4题目c5程序运行结果：7题目a7题目b13题目c19结果分析25问题a25问题b26问题c27附录28原问题的中文版本描述28问题的英文原版描述30模型假设首先我们假设每位艺术家作品数量都是4件,并将其中作品数目不足4件的艺术家的作品所对应的变量xij的值取为0，同时，展品展出所需的费用全部包含在表中所列价格中。问题分析通过讨论分析，我们认为题目a所要求解的是在艾西布里格斯所提供的资金（400万）的范围内，能够展出的展品的最大数目以及展出的具体艺术家及其作品。题目b要求求解在保证展品数目不少于20件的条件下，使本次展览所耗费的资金数量最小的方案以及展出的具体作品。题目c是要求解在确保20件展品的情况下，求赞助人利塔罗斯基所需要出资的最小的数目以及展出的具体作品。这一问题在所提供的中文版本的案例中的描述不够准确，所以我们查阅了英文原版案例。决策变量xij i=1,2,13 j=1,2,3,4 各变量的取值为0或1，当展品展出时变量取值为1，否则取0。故此问题为0-1规划。题目a目标函数max 约束条件 由此建立模型如下max 题目b目标函数min约束条件由此建立模型如下题目c目标函数min约束条件 由此建立模型如下模型求解由上面分析可知此案例属于0-1规划问题，所以我们利用LINGO来求解各个问题。以下是每个问题对应的LINGO程序以及结果。LINGO程序部分：题目a!案例8 分配艺术品（Itroduction to Management Science, F.S.Hillier, Case 9-2 Assigning Art）;!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); !wire mesh sculpture, computer painting;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;!绘画=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);!男=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)=x(12,2);!自恋，沉思;sum(artist(I): sum(piece(J): price(I,J)*x(I,J)=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;!绘画=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);!男=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)=x(12,2);!自恋，沉思;!sum(artist(I): sum(piece(J): price(I,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=30 25 12.5 040 50 40 5570 57.5 0 020 22.5 0 015 15 0 085 75 0 040 17.5 45 050 50 50 065 65 0 025 35 45 040 40 0 030 30 0 05 5 5 5;enddataend题目c!案例8 分配艺术品（Itroduction to Management Science, F.S.Hillier, Case 9-2 Assigning Art）;!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); !wire mesh sculpture, computer painting;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;!绘画=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);!男=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)=x(12,2);!自恋，沉思;!sum(artist(I): sum(piece(J): price(I,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;!all Loskey;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=30 25 12.5 040 50 40 5570 57.5 0 020 22.5 0 015 15 0 085 75 0 040 17.5 45 050 50 50 065 65 0 025 35 45 040 40 0 030 30 0 05 5 5 5;enddataend程序运行结果：题目aLocal optimal solution found. Objective value: 15.00000 Objective bound: 15.00000 Infeasibilities: 0.000000 Extended solver steps: 2 Total solver iterations: 176 Variable Value Reduced Cost TOTAL_PRICE_USED 395.0000 0.000000 TOTAL_DISPLAY 15.00000 0.000000 PRICE( 1, 1) 30.00000 0.000000 PRICE( 1, 2) 25.00000 0.000000 PRICE( 1, 3) 12.50000 0.000000 PRICE( 1, 4) 0.000000 0.000000 PRICE( 2, 1) 40.00000 0.000000 PRICE( 2, 2) 50.00000 0.000000 PRICE( 2, 3) 40.00000 0.000000 PRICE( 2, 4) 55.00000 0.000000 PRICE( 3, 1) 70.00000 0.000000 PRICE( 3, 2) 57.50000 0.000000 PRICE( 3, 3) 0.000000 0.000000 PRICE( 3, 4) 0.000000 0.000000 PRICE( 4, 1) 20.00000 0.000000 PRICE( 4, 2) 22.50000 0.000000 PRICE( 4, 3) 0.000000 0.000000 PRICE( 4, 4) 0.000000 0.000000 PRICE( 5, 1) 15.00000 0.000000 PRICE( 5, 2) 15.00000 0.000000 PRICE( 5, 3) 0.000000 0.000000 PRICE( 5, 4) 0.000000 0.000000 PRICE( 6, 1) 85.00000 0.000000 PRICE( 6, 2) 75.00000 0.000000 PRICE( 6, 3) 0.000000 0.000000 PRICE( 6, 4) 0.000000 0.000000 PRICE( 7, 1) 40.00000 0.000000 PRICE( 7, 2) 17.50000 0.000000 PRICE( 7, 3) 45.00000 0.000000 PRICE( 7, 4) 0.000000 0.000000 PRICE( 8, 1) 50.00000 0.000000 PRICE( 8, 2) 50.00000 0.000000 PRICE( 8, 3) 50.00000 0.000000 PRICE( 8, 4) 0.000000 0.000000 PRICE( 9, 1) 65.00000 0.000000 PRICE( 9, 2) 65.00000 0.000000 PRICE( 9, 3) 0.000000 0.000000 PRICE( 9, 4) 0.000000 0.000000 PRICE( 10, 1) 25.00000 0.000000 PRICE( 10, 2) 35.00000 0.000000 PRICE( 10, 3) 45.00000 0.000000 PRICE( 10, 4) 0.000000 0.000000 PRICE( 11, 1) 40.00000 0.000000 PRICE( 11, 2) 40.00000 0.000000 PRICE( 11, 3) 0.000000 0.000000 PRICE( 11, 4) 0.000000 0.000000 PRICE( 12, 1) 30.00000 0.000000 PRICE( 12, 2) 30.00000 0.000000 PRICE( 12, 3) 0.000000 0.000000 PRICE( 12, 4) 0.000000 0.000000 PRICE( 13, 1) 5.000000 0.000000 PRICE( 13, 2) 5.000000 0.000000 PRICE( 13, 3) 5.000000 0.000000 PRICE( 13, 4) 5.000000 0.000000 X( 1, 1) 0.000000 0.000000 X( 1, 2) 0.000000 0.000000 X( 1, 3) 1.000000 0.000000 X( 1, 4) 0.000000 1.000000 X( 2, 1) 1.000000 -2.000000 X( 2, 2) 0.000000 -2.000000 X( 2, 3) 0.000000 -1.000000 X( 2, 4) 0.000000 -1.000000 X( 3, 1) 0.000000 -1.000000 X( 3, 2) 1.000000 0.000000 X( 3, 3) 0.000000 1.000000 X( 3, 4) 0.000000 1.000000 X( 4, 1) 1.000000 0.000000 X( 4, 2) 1.000000 0.000000 X( 4, 3) 0.000000 1.000000 X( 4, 4) 0.000000 1.000000 X( 5, 1) 1.000000 -1.000000 X( 5, 2) 0.000000 -1.000000 X( 5, 3) 0.000000 1.000000 X( 5, 4) 0.000000 1.000000 X( 6, 1)