运筹学 复习题(09.1)

东北电力大学线性规划与优化初步复习课一、填空题1．除图解法外，常用的求解线性规划问题的方法是_______________法。2、用单纯形法求解线性规划问题时，须将不等式约束化为等式，设不等号右边的常量为非负，则当不等号是小于等于时，应；当不等号是大于等于时，应。3.用图解法求解一个关于最大利润的线性规划问题时，必须画出________线，其最优解点必位于该线与可行解区域________的交点上。4.原问题的第1个约束方程是“=”型，则对偶问题相应的变量是___变量。。5.整数规划____________（是或不是）线性规划。6.求最小生成树问题，常用的方法有：避圈法和___。7.树图中，任意两个顶点间有且仅有一条链。8.线性规划的图解法适用于决策变量为线性规划模型。9.运输问题中求初始基本可行解的方法通常有与两种方法。10.求解不平衡的运输问题的基本思想是。11.称无圈的连通图为树，若图的顶点数为n，则其边数为。二、将下列线性规划化为标准形式123123123123123max423205743103650,0,Zxxxxxxxxxxxxxxx无限制0,0043105332131321321xxxxxxxxxxxMinZ，线性规划模型化为标准形式变量0jx0jx0ib0ib约束条件右端项形式njijijbxa1njijijbxa1njijijbxa1isinjjijbxxa1iainjjijbxxa1iaisinjjijbxxxa1不变jjxx0jx令则jjjxxx0,0jjxx令其中不变约束条件两端乘“－1”jx取值无约束线性规划模型化为标准形式目标函数极大或极小sixaix和前的系数njjjxcz1maxnjjjxcz1min不变sinjjjxxcz0max1ainjjjMxxcz1max加松弛变量或剩余变量时six加人工变量时aixnjjjxcz1max令化为求zz原问题（对偶问题）对偶问题（原问题）n个n个m个m个约束条件右端项目标函数中变量的系数max目标函数min目标函数00无约束=变量约束条件目标函数中变量的系数约束条件右端项约束条件变量=无约束取值无约束，，321321321213210033464562734301524maxyyyyyyyyyyyyyyw0,030351546324624347min32132321321321xxxxxxxxxxxxxxz取值无约束，00取值无约束，，321321321213210033464562734301524maxyyyyyyyyyyyyyyw0,030351546324624347min32132321321321xxxxxxxxxxxxxxz取值无约束，三、用图解法求解下列线性规划问题：12121212max2131,0Zxxxxxxxx12121212min32223120,0Zxxxxxxxx一家工厂制造甲、乙、丙三种产品，需要三种资源——技术服务、劳动力和行政管理。每种产品的资源消耗量、单位产品销售后所能获得的利润值以及这三种资源的储备量如下表所示：技术服务劳动力行政管理单位利润甲110210乙1426丙1564资源储备量1006003001）建立使得该厂能获得最大利润的生产计划的线性规划模型；2）用单纯形法求该问题的最优解。四、建模求解解：1）建立线性规划数学模型：设甲、乙、丙三种产品的生产数量应为x1、x2、x3，则x1、x2、x3≥0，设z是产品售后的总利润，则maxz=10x1+6x2+4x303006226005410100321321321321xxxxxxxxxxxx，，2）用单纯形法求最优解：加入松弛变量x4，x5，x6，maxz=10x1+6x2+4x3+0x4+0x5+0x66,...,2,1,03006226005410100632153214321jxxxxxxxxxxxxxj略∴X*=（，，0，0，0，100）31003200∴maxz=10×+6×=3100320032200求解整数规划问题：且为整数0,4595685max21212121xxxxxxxxzL0:x1=2.25,x2=3.75,z=41.250,4595685max21212121xxxxxxxxzL0:0,44595685max212212121xxxxxxxxxzL1:0,34595685max212212121xxxxxxxxxzL2:L1:x1=1.8,x2=4,z=41L2:x1=3,x2=3,z=3942x32x五、用分枝定界法求解42x52x21x11x:x1=1,x2=40/9,z=365/94L:x1=1,x2=4,z=375L:x1=0,x2=5,z=406L0,4595685max21212121xxxxxxxxzL0:且为整数0,44595685max212212121xxxxxxxxxzL1:且为整数0,34595685max212212121xxxxxxxxxzL2:L0:x1=2.25,x2=3.75,z=41.25L1:x1=1.8,x2=4,z=41L2:x1=3,x2=3,z=3942x32x:x1=0,x2=5,z=406L无可行解3L六、运输问题及其求解：某农产品经销公司有A1、A2、A3三个棉花收购站，向四个纺织厂供应棉花，其供应量分别是600吨、1000吨、700吨，四个纺织厂B1、B2、B3、B4的需求量分别为300吨、500吨、900吨、600吨。已知：从各收购站到各纺织厂的单位运价如下表（单位：千元/吨）试问：应如何调度运输使总运费最少？B1B2B3B4供应量A13986600A212207101000A36111314700需求量300500900600某公司有三个分公司A1、A2、A3，其产品销往B1、B2、B3、B4四个地区，该公司三个分公司的生产能力与到四个地区的单位运输费用如下表所示，试用表上作业法求使运输费用最小的调运方案及其最优解销地产地B1B2B3B4产量A1A2A3324743638425526销量3322七、用匈牙利算法求解ABCDE甲127979乙89666丙71712149丁15146610戊4107109八、最小树1、请用避圈法（或破圈法）求最小部分树？2．请用Dijkstra算法求从发点s到收点t的最短路？ts1323422543321最小部分树为ts132342254332从发点s到收点t的最短路为s2231t13425433203453求解线性规划问题1312312323123max3421..39,,0zxxxxxxxxstxxxxx1、列出该线性规划问题的标准形式2、请运用单纯形法的大M法求其最优解和目标函数值。1、线性规划问题的标准形式1345123412352312345max300421..39,,,,0zxxxxxxxxxxxxstxxxxxxx2、运用单纯形法的大M法求解（1）上式的标准型中添加人工变量，得：1345671234123562371234567max300421..39,,,,,,0zxxxxMxMxxxxxxxxxxstxxxxxxxxxx（2）列单纯形表1：cj→－30100―M－MCB基bx1x2x3x4x5x6x70x441111000－Mx61－2[1]－10－110－Mx790310001cj－zj－3－2M4M10－M00（3）列单纯形表2：cj→－30100―M－MCB基bx1x2x3x4x5x6x70x4330211－100x21－21－10－110－Mx76[6]0403－31cj－zj－3＋6M01＋4M03M－4M0（4）列单纯形表3：cj→－30100―M－MCB基bx1x2x3x4x5x6x70x400001－1/21/2－1/20x23011/30001/3－3x1110[2/3]01/2－1/21/6cj－zj00303/2－M－3/2－M＋1/2（5）列单纯形表4：cj→－30100―M－MCB基bx1x2x3x4x5x6x70x400001－1/21/2－1/20x25/2－1/2100－1/41/41/41x33/23/20103/4－3/41/4cj－zj－9/2000－3/4－M+3/4－M－1/4计算最后一行检验数，所有非基的0j，去掉人工变量，得最优解53(0,,,0,0)22X目标函数值3/2Z1、某公司拟使用二种原材料生产A、B两种产品。生产1件A产品所需原材料1、2分别是2吨、1吨,生产1件B产品所需原材料1、2分别是1吨、2吨。产品A、B的单位销售收益分别为3元和2元。公司对二种原材料1、2的拥有量分别是6吨、4吨。若生产出的产品能全部销售，试问：应如何制定生产计划使总销售收益最大？2、某企业一部门有A1、A2、A3三个人，该部门有B1、B2、B3三项工作需要做，要求每人只能做一项工作,每项工作只能一人去做。已知：A1人做B1、B2、B3项工作的单位消耗分布为：3、5、2；A2人做B1、B2、B3项工作的单位消耗分布为：2、10、12；A3人做B1、B2、B3项工作的单位消耗分布为：1、9、8。试建立应如何分配工作使总消耗最少的数学模型。3、某钢管厂有一批11米长的钢管，现一客户拟订购3米长的钢管60根，4米长钢管90根，试建立使总的废料最少的数学模型。4、某家具厂生产衣柜、书柜、圆桌和凳子，每个衣柜的利润是15元，每个书柜的利润是20元，每个圆桌的利润是10元，每个凳子的利润是8元。生产一个衣柜需要杂木0.15m3和松木0.3m3，生产一个书柜需要杂木0.2m3和松木0.4m3，生产一个圆桌只需要杂木0.2m3，生产一个的凳子只需要松木0.15m3。每月杂木和松木的供应量分别是80m3和60m3。问四种产品每月各应生产多少，能使总利润最大？试建立模型。1．请用避圈法（或破圈法）求最小部分树？2．请用Dijkstra算法求最短路？ts46785451821012163286101022避圈法863ts46785451210121628101022破圈法863ts46785451210121628101022最短路68121432863ts467854512101216281010022