管理运筹学复习（1）某工厂在计划期内要安排Ⅰ,Ⅱ两种产品的生产.生产单位产品所需的设备台时及A,B 两种原材料的消耗以及资源的限制如下表所示:生产多少单位产品Ⅰ和产品Ⅱ才能使获利最多？解：max z=50X1+100X2 ；满足约束条件：X1+X2≤300，2X1+X2≤400，X2≤250，X1≥0,X2≥0。

（2）：某锅炉制造厂，要制造一种新型锅炉10台，需要原材料为∮63.5×4mm的锅炉钢管，每台锅炉需要不同长度的锅炉钢管数量如下表所示：多少根原材料？设按14 种方案下料的原材料的根数分别为X1,X2,X3,X4,X5,X6,X7,X8,X9,X10,X11,X12,X13,X14, 可列出下面的数学模型：min f＝X1+X2+X3+X4+X5+X6+X7+X8+X9+X10+X11+X12+X13+X14满足约束条件：2X1＋X2＋X3＋X4≥ 80X2＋3X5＋2X6＋2X7＋X8＋X9＋X10≥420X3＋X6＋2X8＋X9＋3X11＋X12＋X13≥ 350X4＋X7＋X9＋2X10＋X12＋2X13＋3X14≥ 10X1，X2，X3，X4，X5，X6，X7，X8，X9，X10，X11，X12，X13，X14≥ 0（3）某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、应如何调运，使得总运输费最小？解：此运输问题的线性规划的模型如下min f =6X11+4X12+6X13+6X21+5X22+5X23约束条件：X11+X12+X13=200X21+X22+X23=300X11+X21=150X12+X22=150X13+X23=200X ij≥0(i=1,2;j=1,2,3)(4) 某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、（5）某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的（6）某公司在三个地方有三个分厂，生产同一种产品，其产量分别为300箱、400箱、500箱。

需要供应四个地方的销售，这四地的产品需求分别为400箱、②如果2分厂的产量从400箱提高到了600箱,那么应如何安排运输方案,使得总运费为最小?③如果销地甲的需求从400箱提高到550箱,而其他情况都同①,那该如何安排运输方案,使得运费为最小?解:①此运输问题的线性规划的模型如下minf=21X11+17X12+23X13+25X14+10X21+15X22+30X23+19 X24+23X31+21X32+20X33+22X34 约束条件：X11+X12+X13 +X14=300X21+X22+X23+X24=400X31+X32+X33+X34=500X11+X21+X31=400X12+X22+X32=250X13+X23+X33=350X14+X24+X34=200X ij≥0(i=1,2,3;j=1,2,3,4)③解：这是一个销大于产的运输问题，建立一个假想销地4分厂，得到产销平衡（7）整数规划的图解法某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利解：设X1,X2分别为甲、乙两种货物托运的件数，其数学模型如下所示：max z=2X1+3X2约束条件：195X1+273X2≤1365，4X1+40X2≤140，X1≤4，X1, X2≥0，X1, X2 为整数。

（8）指派问题有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时解：引入0—1变量X ij，并令1，当指派第i人去完成第j项工作时；X ij=0，当不指派第i人去完成第j项工作时；此整数规划的数学模型为：min z=15X11+18X12+21X13+24X14+19X21+23X22+22X23+18 X24+26X31+17X32+16X33+19X34 +19X41+21X42+23X43+17X44约束条件：X11+X12+X13 +X14=1（甲只能干一项工作）X21+X22+X23+X24=1（乙只能干一项工作）X31+X32+X33+X34=1（丙只能干一项工作）X41+X42+X43+X44=1（丁只能干一项工作）X11+X21+X31+X41=1（A工作只能一个人干）X12+X22+X32+X42=1（B工作只能一个人干）X13+X23+X33+X43=1（C工作只能一个人干）X14+X24+X34+X44=1（D工作只能一个人干）X ij为0—1变量，(i=1,2,3，4;j=1,2,3,4)(9)有优先权的目标规划的图解法一位投资商有一笔资金准备购买股票，资金总额为90000元，目前可选的股票有A 、B 两种（可以同时投资于两种股票），其价格以及年收益率和风险系数股票A 的收益率为（3/20）×100%=15%,股票B 的收益率为（4/50）×100%=8%, A 的收益率比B 大，但同时A 的风险也比B 大，这符合高风险高收益的规律。

试求一种投资方案，使得一年的总投资风险不高于700，且投资收益不低于10000元。

解：设X 1、X 21.针对优先权最高的目标建立线性规划 建立线性规划模型如下：min d 1+约束条件：20X 1+50X 2 ≦900000.5X 1+0.2X 2-d 1++d 1- =700 3X 1+4X 2-d 2++d 2- =10000 X 1 , X 2 , d 1+ , d 2- ≧02.针对优先权次高的目标建立线性规划 建立线性规划模型如下： min d2- 约束条件： 20X 1+50X 2 ≦900000.5X 1+0.2X 2-d 1++d 1- =700 3X 1+4X 2-d 2++d 2- =10000 d 1+=0X 1 ， X 2 ，d 1+ ，d 1- ，d 2+，d 2- ≧03.目标规划模型的标准化对于两个不同优先权的目标单独建立线性规划进行求解，为方便，把他们用一个模型来表达：min P 1(d 1+)+P 2(d 2-)约束条件： 20X 1+50X 2 ≦90000 ，0.5X 1+0.2X 2-d 1++d 1- =700，3X 1+4X 2-d 2++d 2- =10000，X 1 ， X 2 ，d 1+ ，d 1- ，d 2+，d 2- ≧0。

（10）某工厂试对产品A、B进行生产，市场需求并不是很稳定，因此对每种产品分别预测了在销售良好和销售较差时的预期利润，这两种产品都经过甲、乙两台设备加工，已知产品A和B分别在甲和乙设备上的单位加工时间，甲、乙设备的可用加工时间以及预期利润如表所示，要求首先是保证在销售较差时，预期利润不少于5千元，其次是要求销售良好时，预期销售利润尽量达到1万元。

试建解：设工厂生产A 产品X1 件，生产B 产品X2件。

按照生产要求，建立如下目标规划模型: min P1(d1+)+P2(d2-)约束条件：4X1+3X2≦45 ，2X1+5X2≦305X1+5X2-d1++d1- =50，8X1+6X2-d2++d2- =100，X1 ，X2，d i+，d i- ≧0.i=1,2(11)动态规划石油输送管道铺设最优方案的选择问题：如图所示，其中A为出发点，E为目的地，B、C、D分别为三个必须建立油泵加压站的地区，其中的B1、B2、B3;C1、C2、C3;D1、D2分别为可供选择的各站站点。

图中的线段表示管道可铺设的位置，线段旁的数字为铺设管线所需要的费用，问如何铺设管道才使总费用最小？解：第四阶段：D1—E 3；D2—E 4；第三阶段：C1—D1—E 5；C2—D2—E 8；C3—D1—E 8；C3—D2—E 8；第二阶段：B1—C1—D1—E 11；B1—C2—D2—E 11；B2—C1—D1—E 8；B3—C1—D1—E 9 ；B3—C2—D2—E 9；第一阶段：A—B1—C1—D1—E 14；A—B1—C2—D2—E 14；A—B2—C1—D1—E 13；A—B3—C1—D1—E 13；A—B3—C2—D2—E 13；最优解：A―B2―C1―D1―E；A―B3―C1―D1―E；A―B3―C2―D2―E 最优值：13（12）最小生成树问题某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如图所示，图中V1，……，V7表示7个学院办公室，图中的边为可能联网的途径，边上的所赋权数为这条路线的长度，单位为百米。

请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。

解：①在G中找到一个圈（V1，V7，V6，V1）,并知在此圈上边[V1，V6]的权数10为最大，在G中去掉边[V1，V6]得图G1 ，如上图所示②在G1中找到一个圈（V3，V4，V5，V7，V3），去掉其中权数最大的边[V4，V5]，得图G2 ，如上图所示③在G2中找到一个圈（V2，V3，V5，V7，V2），去掉其中权数最大的边[V5，V7]，得图G3 ，如上图所示④在G3中找到一个圈（V3，V5，V6，V7，V3），去掉其中权数最大的边[V5，V6]，得图G4 ，如上图所示⑤在G4中找到一个圈（V2，V3，V7，V2），去掉其中权数最大的边[V3，V7]，得图G5 ，如上图所示⑥在G5中已找不到任何一个圈了，可知G5即为图G的最小生成树。

这个最小生成树的所有边的总权数为3+3+3+1+2+7=19(13)某一个配送中心要给一个快餐店送快餐原料，应按照什么路线送货才能使送货时间最短。

下图给出了配送中心到快餐店的交通图，图中V1，……，V7表示7个地名，其中V1表示配送中心，V7表示快餐店，点之间的联线表示两地之间的道路，边所赋的权数表示开车送原料通过这段①给起始点1标号为（0，S）②I={V1},J={ V2，V3，V4，V5，V6 ,V7} ，边的集合{[V i，V j] ︳V i，V j两点中一点属于I,而另一点属于J}={[ V1，V2]，[ V1，V3]}，并有S12=L1+C12=0+4=4 ；S13=L1+C13=0+18=18min (S12,S13)= S12 =4给边[ V1，V2]中的未标号的点V2 标以（4，1），表示从V1 到V2 的距离为4，并且在V1到V2的最短路径上V2的前面的点为V1.③这时I={V1，V2},J={V3，V4，V5，V6 ,V7}，边的集合{[V i，V j] ︳V i，V j两点中一点属于I,而另一点属于J}={[ V1，V3]，[ V2，V3]，[ V2，V4]}，并有S23=L2+C23=4+12=16 ；S24=L2+C24=4+16=20 ；min (S23,S24 , S13)= S23 =16 给边[ V2，V3]中的未标号的点V3 标以（16，2）④这时I={V1，V2 ，V3},J={V4，V5，V6 ,V7}，边的集合{[V i，V j] ︳V i，V j两点中一点属于I,而另一点属于J}={[ V2，V4]，[ V3，V4]，[ V3，V5]}，并有S34=L3+C34=16+2=18 ；S35=L3+C35=16+6=22 ；S24=L2+C24=4+16=20min (S34,S35,S24)= S34 =18给边[ V3，V4]中的未标号的点V4 标以（18，3）⑤这时I={V1，V2 ，V3 ，V4},J={V5，V6 ,V7}，边的集合{[V i，V j] ︳V i，V j两点中一点属于I,而另一点属于J}={ [ V4，V6]，[ V4，V5]，[ V3，V5]}，并有S46=L4+C46=18+7=25 ；S45=L4+C45=18+8=26 ；min (S46,S45 ,S35)= S35 =24 给边[ V3，V5]中的未标号的点V5 标以（24，3）⑥这时I={V1，V2 ，V3 ，V4 ，V5 },J={V6，V7}，边的集合{[V i，V j] ︳V i，V j 两点中一点属于I,而另一点属于J}={[ V5，V7]，[ V4，V6] }，并有S57=L5+C57=22+5=27 ；min (S57,S46)= S46 =25给边[ V4，V6]中的未标号的点V6 标以（25，4）⑦这时I={V1，V2 ，V3 ，V4 ，V5 ，V6},J={ V7}，边的集合{[V i，V j] ︳V i，V j 两点中一点属于I,而另一点属于J}={[ V5，V7]，[ V6，V7] }，并有S67=L6+C67=25+6=31 ；min (S57,S67)= S57 =27给边[ V5，V7]中的未标号的点V7 标以（27，5）⑧此时I={V1，V2 ，V3 ，V4 ，V5 ，V6，V7},J=空集，边集合{[V i，V j] ︳V i，V j两点中一点属于I,而另一点属于J}=空集，计算结束。