运筹学案例8培训讲学.docx
《运筹学案例8培训讲学.docx》由会员分享，可在线阅读，更多相关《运筹学案例8培训讲学.docx（43页珍藏版）》请在冰点文库上搜索。
运筹学案例8培训讲学
运筹学案例8
运筹学案例8报告
组员晋榕榕尹琪徐凯文耿志强张晗
模型假设
首先我们假设每位艺术家作品数量都是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;
enddata
end
题目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;
enddata
end
题目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;
enddata
end
程序运行结果：
题目a
Localoptimalsolutionfound.
Objectivevalue:
15.00000
Objectivebound:
15.00000
Infeasibilities:
0.000000
Extendedsolversteps:
2
Totalsolveriterations:
176
VariableValueReducedCost
TOTAL_PRICE_USED395.00000.000000
TOTAL_DISPLAY15.000000.000000
PRICE（1,1）30.000000.000000
PRICE（1,2）25.000000.000000
PRICE（1,3）12.500000.000000
PRICE（1,4）0.0000000.000000
PRICE（2,1）40.000000.000000
PRICE（2,2）50.000000.000000
PRICE（2,3）40.000000.000000
PRICE（2,4）55.000000.000000
PRICE（3,1）70.000000.000000
PRICE（3,2）57.500000.000000
PRICE（3,3）0.0000000.000000
PRICE（3,4）0.0000000.000000
PRICE（4,1）20.000000.000000
PRICE（4,2）22.500000.000000
升级会员 