习题三某公司今后三年内有五项工程可以考虑投资。

每项工程的期望收入和年度费用(万元)如表3-10所示。

表3-10工程费用收入第一年第二年第三年1、23455 1 84 7 25 9 67 5 28 6 930·40201530资金拥有量30 25 30【解】设1jjxj⎧=⎨⎩投资项目不投资项目，模型为12345123451234512345max30402015305457830795625826293001,1,,5jZ x x x x xx x x x xx x x x xx x x x xx j=++++++++≤⎧⎪++++≤⎪⎨++++≤⎪⎪=⎩＝或【最优解X＝(1,1,1,0,1)，Z=110万元，即选择项目1、2、3、5时总收入最大。

址问题。

以汉江、长江为界将武汉市划分为汉口、汉阳和武昌三镇。

某商业银行计划投资9000万元在武汉市备选的12个点考虑设立支行，如图3-10所示。

每个点的投资额与一年的收益见表3－10。

计划汉口投资2～3个支行，汉阳投资1～2个支行，武昌投资3～4个支行。

如何投资使总收益最大，建立该问题的数学模型，说明是什么模型，可以用什么方法求解。

表3-11地址i.12345678910[1112投资额(万元)90012001000750680800720；1150120012508501000收益（万元）400500450350—300400320460500510380400 j j图3-1012312123111244771212115588max 40050045040090012001000850100090002,3,1,2,3,4101,,12j j j j j j j j j j j j jZ x x x x x x x x x x x x x x x x j =======++++⎧+++++≤⎪⎪≥≤≥≤≥≤⎨⎪⎪==⎩∑∑∑∑∑∑或， …最优解：x1＝x5=x12=0，其余xj=1,总收益Z=3870万元，实际完成投资额8920万元。

一辆货车的有效载重量是20吨，载货有效空间是8××2 m 。

现有六件货物可供选择运输，每件货物的重量、体积及收入如表表3-12。

另外，在货物4和5中先运货物5，货物1和2不能混装，怎样安排货物运输使收入最大，建立数学模型。

表3-12【解j j j 有⎪⎪⎪⎩⎪⎪⎪⎨⎧=≤+≤-≤+++++≤++++++++++=10105626547320274356376485max 2154654321654321654321或j x x x x x x x x x x x x x x x x x x x x x x x Z女子体操团体赛规定：（1）每个代表队由5名运动员组成，比赛项目是高低杠、平衡木、鞍马及自由体操。

（2）每个运动员最多只能参加3个项目并且每个项目只能参赛一次；（3）每个项目至少要有人参赛一次，并且总的参赛人次数等于10；（4）每个项目采用10分制记分，将10次比赛的得分求和，按其得分高低排名，分数越高成绩越好。

已知代表队5名运动员各单项的预赛成绩如表3-13所示。

…表3-13怎样安排运动员的参赛项目使团体总分最高，建立该问题的数学模型。

【解】设x ij （i =1，2，…，5；j ＝1，2，3，4）为第i 人参赛j 项目的状态，即⎩⎨⎧=项目人不参赛第项目人参赛第j i j i x ij 01记第i 人参赛j 项目的成绩为C ij ,，目标函数∑∑===5141max i j ij ij x C Z每个运动员最多只能参加3个项目并且每个项目只能参赛一次,约束条件：{5,,2,134321 =≤+++i x x x x i i i i每个项目至少要有人参赛一次，并且总的参赛人次数等于10，约束条件：4,3,2,1154321=≥++++j x x x x x j j j j j105141=∑∑==i j ijx数学模型为54111234123455411max 31,2,,511,2,3,41010,1,2,,5;1,2,3,4ij iji j i i i i j j j j j ij i j ij Z C x x x x x i x x x x x j x x i j =====+++≤=⎧⎪++++≥=⎪⎪⎨=⎪⎪⎪===⎩∑∑∑∑或 利用0－1变量对下列各题分别表示成一般线性约束条件\（1）x 1+2x 2≤8、4x 1+x 2≥10及2x 1+6x 2≤18 三个约束中至少两个满足 （2）若x 1≥5，则x 2≥10，否则x 2≤8 （3）x 1取值2，4，6，8中的一个高低杠 平衡木鞍马自由体操甲 <乙丙 ?丁戊:【解】12112212312228410(1)26181011,2,3jx x y Mx x y M x x y M y y y y j ⎧+≤+⎪+≥-⎪⎪+≤+⎨⎪++≤⎪⎪==⎩或， ⎪⎪⎪⎩⎪⎪⎪⎨⎧=-+≤-≥-+<-≥10)1(810)1(55)2(2211或y M y x yM x M y x yM x ⎪⎩⎪⎨⎧===++++++=4,3,2,11018642)3(432143211j y y y y y y y y y x j ，或 6．考虑下列数学模型)()(m in 21x g x f Z +=其中⎩⎨⎧=>+=⎩⎨⎧=>+=0,00,1015)(,0,00,610)(22221111x x x x g x x x x f 若若若若 满足约束条件 （1）x 1≥8或x 2≥6&（2）|x 1－x 2|=0，4或8（3）x 1+2x 2≥20、2x 1+x 2≥20及x 1+x 2≥20 三个约束中至少一个满足 （4）x 1≥0，x 2≥0将此问题归结为混合整数规划的数学模型。

【解】）条件（）条件（）条件（）条件（，，或432111,2,110;0,0220202202188440)1(68;1015610min 211110911211021921876548765421323122112211⎪⎪⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎪⎪⎨⎧==≥≥≤++-≥+-≥+-≥+=+++++-+-=---≥-≥≤≤+++= j y x x y y y M y x x M y x x M y x x y y y y y y y y y y x x M y x My x My x M y x x y x y Z j7．用分枝定界法求解下列IP 问题（1）12121212max 327245,0Z x x x x x x x x =++≤⎧⎪+≤⎨⎪≥⎩且为整数（2）⎪⎩⎪⎨⎧≥≥+≤+-+=且为整数0,50210102min 21212121x x x x x x x x Z【解】(1)X=(1,2),或X ＝（0,3）Z=3 (2) X=(5,0),Z=5》8．用割平面法求解下列IP 问题（1）⎪⎩⎪⎨⎧≥≤+≤++=且为整数0,1029232max 21212121x x x x x x x x Z （2）⎪⎩⎪⎨⎧≥≥+≥++=且为整数0,1029232min 21212121x x x x x x x x Z【解】(1)X=(3,3),Z=15 (2)X=(5,2),Z=169．用隐枚举法求解下列BIP 问题（1）⎪⎩⎪⎨⎧==≤++≥-++=3,2,11072462534max 321321321j x x x x x x x x x x Z j ，或＋ （2）⎪⎪⎩⎪⎪⎨⎧==≤+++≥-+-≥+++-++-=4,3,2,1107423422335434min 4321432143214321j x x x x x x x x x x x x x x x x x Z j ，或【解】(1)X=(1,1,1),Z=8 (2)X=(1,1,1,0),Z=410．用分枝定界－隐枚举法求解下列BIP 问题 #（1）⎪⎪⎩⎪⎪⎨⎧==≤+++≤-+-≤+++-++-=4,3,2,1107423422385434max 4321432143214321j x x x x x x x x x x x x x x x x x Z j ，或 （2）⎪⎩⎪⎨⎧==≥+--+≤++++++++-=5,,11042322825623min 543215432154321 j x x x x x x x x x x x x x x x x Z j ，或【解】(1)X=(1,0,1,1),Z=8 (2)X=(1,1,0,0,0),Z=－2习题四工厂生产甲、乙两种产品，由Ａ、Ｂ二组人员来生产。

Ａ组人员熟练工人比较多，工作效率高，成本也高；Ｂ组人员新手较多工作效率比较低，成本也较低。

例如，A 组只生产甲产品时每小时生产10件，成本是50元有关资料如表所示。

班生产的产品每件增加成本5元。

工厂根据市场需求、利润及生产能力确定了下列目标顺序： P 1：每周供应市场甲产品400件，乙产品300件 @P 2：每周利润指标不低于500元P 3：两组都尽可能少加班，如必须加班由Ａ组优先加班 建立此生产计划的数学模型。

【解】 解法一：设x 1, x 2分别为A 组一周内正常时间生产产品甲、乙的产量，x 3, x 4分别为A 组一周内加班时间生产产品甲、乙的产量；x 5, x 6分别为B 组一周内正常时间生产产品甲、乙的产量，x 7, x 8分别为B 组一周内加班时间生产产品甲、乙的产量。

总利润为13571357246824681234567880()(50554550)75()(45504045)3030252535353030x x x x x x x x x x x x x x x x x x x x x x x x +++-+++++++-+++=+++++++生产时间为A 组：12340.10.1250.10.125x x x x +++B 组：56780.1250.20.1250.2x x x x +++ ）数学模型为：112233454671357112468221234567833124456553min ()()(2)40030030302525353530305000.10.125400.1250.2400.10.Z p d d p d p d d p d d x x x x d d x x x x d d x x x x x x x x d d x x d d x x d d x ---+++++-+-+=++++++++++-=++++-=++++++++-=++-=++-=+－－－－－4667877125100.1250.2100,,0,1,2,,7;1,2,,8j i i x d d x x d d x d d i j -+-+-+⎧⎪⎪⎪⎪⎪⎪⎨⎪⎪+-=⎪⎪++-=⎪≥≥==⎪⎩解法二：设x 1, x 2分别为A 组一周内生产产品甲、乙的正常时间，x 3, x 4分别为A 组一周内生产产品甲、乙的加班时间；x 5, x 6分别为B 组一周内生产产品甲、乙的正常时间，x 7, x 8分别为B 组一周内生产产品甲、乙的加班时间。