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

运筹学案例8

精品文档
运筹学案例8报告
组员 晋榕榕 尹琪 徐凯文 耿志强 张晗
模型假设 1
问题分析 1
模型求解 2
LINGO程序部分： 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件展品的情况下，求赞助人利塔·罗斯基所需要出资的最小的数目以及展出的具体作品。这一问题在所提供的中文版本的案例中的描述不够准确，所以我们查阅了英文原版案例。
决策变量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;!绘画<=20(这个条件在原书中没有);
@sum(piece(I) | I #le# 4: x(13,I))=4;!all Ash;
@sum(piece(I) | I #le# 2: x(4,I))=2;!凯蒂作品全展出all Candy;
@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;!20 painting, 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=30 25 12.5 0
40 50 40 55
70 57.5 0 0
20 22.5 0 0
15 15 0 0
85 75 0 0
40 17.5 45 0
50 50 50 0
65 65 0 0
25 35 45 0
40 40 0 0
30 30 0 0
5 5 5 5;
enddata
end
题目b
!案例8 分配艺术品（Itroduction to Management Science, F.S.Hillier, Case 9-2 Assigning Art）;
!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); !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;!绘画<=20(这个条件在原书中没有);
@sum(piece(I) | I #le# 4: x(13,I))=4;!all Ash;
@sum(piece(I) | I #le# 2: x(4,I))=2;!凯蒂作品全展出all Candy;
@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;!20 painting, 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=30 25 12.5 0
40 50 40 55
70 57.5 0 0
20 22.5 0 0
15 15 0 0
85 75 0 0
40 17.5 45 0
50 50 50 0
65 65 0 0
25 35 45 0
40 40 0 0
30 30 0 0
5 5 5 5;
enddata
end
题目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;!绘画<=20(这个条件在原书中没有);
@sum(piece(I) | I #le# 4: x(13,I))=4;!all Ash;
@sum(piece(I) | I #le# 2: x(4,I))=2;!凯蒂作品全展出all Candy;
@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;!20 painting, 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;!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 0
40 50 40 55
70 57.5 0 0
20 22.5 0 0
15 15 0 0
85 75 0 0
40 17.5 45 0
50 50 50 0
65 65 0 0
25 35 45 0
40 40 0 0
30 30 0 0
5 5 5 5;
enddata
end
程序运行结果：
题目a
Local 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)