运筹学作业辅导

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2015-8-17,#,运筹学作业精讲,第一单元,某企业生产甲、乙两种产品，其单位利润分别为,20,元和,30,元。每生产一件甲产品需劳动力,3,个，原材料,2,千克，设备,4,小时；每生产一件乙产品需劳动力,7,个，原材料,4,千克，设备,3,小时。企业现有劳动力,240,个，原材料,150,千克，设备可用时间为,250,小时。,问：如何安排生产计划，才能使所获总利润最大？写出线性规划模型；化成标准形式；用图解法进行求解。,解：设,x,1,和,x,2,分别表示产品甲和乙的产量，,这样可以建立如下的数学模型。,目标函数：,Max20,x,1,+30,x,2,约束条件：,s.t.3,x,1,+7,x,2,240,（劳动力限制）,2,x,1,+4,x,2,150,（原材料限制）,4,x,1,+3,x,2,250,（设备限制）,x,1,，,x,2,0,（非负约束）,化为标准型：,目标函数：,Max20,x,1,+30,x,2,约束条件：,s.t.3,x,1,+7,x,2,+,x,3,=240,2,x,1,+4,x,2,+,x,4,=150,4,x,1,+3,x,2,+,x,5,=250,x,1,，,x,2,，,x,3,，,x,4,，,x,5,0,阴影部分为可行域，虚线为目标函数线。由图可知最优解为约束,2,和约束,3,的交点，解得坐标为（,55,10,），故最优生产计划为生产甲产品,55,件，乙产品,10,件，最大利润为,2055+3010,=1400,元。,第二单元,产品,资源,大号,中号,小号,可用资源量,铝板,(,张,),6,2,4,400,劳力,(,小时,),4,8,6,360,机器,(,台,),8,4,10,420,售价,(,元,/,个,),50,40,30,某厂生产三种型号的铝锅，已知单耗数据如下,。,试制定最优生产计划使总收入最大。,解：设,x,1,、,x,2,、,x,3,分别表示大号、中号、小号铝锅的产量，,这样可以建立如下的数学模型。,目标函数：,Max50,x,1,+40,x,2,+30,x,3,约束条件：,s.t.6,x,1,+2,x,2,+4,x,3,400,（铝板限制）,4,x,1,+8,x,2,+6,x,3,360,（劳力限制）,8,x,1,+4,x,2,+10,x,3,420,（机器限制）,x,1,，,x,2,，,x,3,0,（非负约束）,化为标准型：,目标函数：,Max50,x,1,+40,x,2,+30,x,3,约束条件：,s.t.6,x,1,+2,x,2,+4,x,3,+,x,4,=400,4,x,1,+8,x,2,+6,x,3,+,x,5,=360,8,x,1,+4,x,2,+10,x,3,+,x,6,=420,x,1,，,x,2,，,x,3,，,x,4,，,x,5,，,x,6,0,使用单纯形法求解：,50,40,30,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,0,x,4,400,6,2,4,1,0,0,200/3,0,x,5,360,4,8,6,0,1,0,90,0,x,6,420,(8),4,10,0,0,1,105/2,-z,0,50*,40,30,0,0,0,0,x,4,85,0,-1,-7/2,1,0,-3/4,-,0,x,5,150,0,(6),1,0,1,-1/2,25,50,x,1,105/2,1,1/2,5/4,0,0,1/8,105,-z,-2625,0,15*,-65/2,0,0,-25/4,0,x,4,110,0,0,-10/3,1,1/6,-5/6,40,x,2,25,0,1,1/6,0,1/6,-1/12,50,x,1,40,1,0,7/6,0,-1/12,1/6,-z,-3000,0,0,-35,0,-5/2,-5,得到最优解（,40,25,0,110,0,0,），最优值,3000,。即应该生产大号铝锅,40,个，中号铝锅,25,个单位，小号铝锅产量为,0,（不生产），最大利润为,3000,元。,.,第三单元,c,j,-5,5,13,0,0,i,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,5,x,2,20,-1,1,3,1,0,0,x,5,10,16,0,-2,-4,1,-z,-100,0,0,-2,-5,0,线性规划,Max,z,=5,x,1,+5,x,2,+13,x,3,s.t.,x,1,+,x,2,+3,x,3,20,12,x,1,+4,x,2,+10,x,3,90,x,1,x,2,x,3,0,的最优表为：,分析在下列条件下，最优解分别有什么变化,（,1,）,b,2,由,90,变为,70,。,（,2,）,c,1,由,-5,变为,-10,。,（,3,）增加一个约束条件,4,x,1,+3,x,2,+6,x,3,50,。,解,：,（,1,）由最优基不变的条件,Max-,bi,/,ir,ir,0D,br,Min-,bi,/,ir,ir,0,得,-10=-10/1D,b,2,b,2,由,90,变为,70,，超出了允许变化范围，继续计算,或者由,B,-1,(,b,+D,b,)=(20,-10),T,可以知道最优基发生变化，继续迭代。,最优解变为,x,1,=0,，,x,2,=5,，,x,3,=5,，,x,4,=0,，,x,5,=0,，最优值,z*=90,。,2,）,c,1,是非基变量的系数，最优解不变的条件是：,D,c,1,-,s,1,，,c,1,由,-5-10,，,D,c,1,=-5 0=-,s,1,，不影响最优解。,c,j,-5,5,13,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,5,x,2,20,-1,1,3,1,0,0,x,5,-10,16,0,(-2),-4,1,-z,-100,0,0,-2,-5,0,5,x,2,5,23,1,0,-5,3/2,13,x,3,5,-8,0,1,2,-1/2,-z,-90,-16,0,0,-1,-1,（,3,）增加一个约束条件,4,x,1,+3,x,2,+6,x,3,50,，原最优解不满足这个约束。引入松弛变量，得到,4,x,1,+3,x,2,+6,x,3,+,x,6,=50,填入最优单纯形表，进一步求解，得到最优解为,X=(0,，,10,，,10/3)T,，最优值为,280/3,。,C,i,-5,5,13,0,0,0,C,B,X,B,b,x,1,x,2,x,3,x,4,x,5,x,6,5,x,2,20,-1,1,3,1,0,0,0,x,5,10,16,0,-2,-4,1,0,0,x,6,50,4,3,6,0,0,1,-,z,-100,0,0,-2,-5,0,0,5,x,2,20,-1,1,3,1,0,0,0,x,5,10,16,0,-2,-4,1,0,0,x,6,-10,7,0,(-3),-3,0,1,-,z,-100,0,0,-2,-5,0,0,5,x,2,10,6,1,0,-2,0,1,0,x,5,50/3,34/3,0,0,-2,1,-2/3,13,x,3,10/3,-7/3,0,1,1,0,-1/3,-,z,-280/3,-14/3,0,0,-3,0,-2/3,第四单元,对于以下的运输问题，若各个销地少得到,1,个单位的产品，将要求得到赔偿，金额分别为,9,、,12,、,6,、,12,，问如何组织运输，才能使总费用最低。（建立运输模型，用最小元素法求初始解，并求出最优解）,解,：总产量为,99+55+110=264,，总销量,44+88+88+77=297,，产销不平衡且供不应求，增加一个虚拟产地,A4,，其产量为,297-264=33,。由虚拟产地运往销地的费用即为赔偿金额。因此可以建立运输模型如下：,使用最小元素法求初始解：,说明：每次选择最小元素，因此依次选择,3,（,x,33,）、,6,（,x,22,）、,9,（,x,41,）、,12,（,x,11,）、,15,（,x,14,）、,21,（,x,32,）、,33,（,x,12,）。）,得到初始解,x,11,=11,，,x,12,=11,，,x,14,=77,，,x,22,=55,，,x,32,=22,，,x,33,=88,，,x,41,=33,，其余运量为,0,，总运费为,3003,。,B1,B2,B3,B4,产量,余额,A1,12,11,33,11,9,(),15,77,99,88,11,A2,30,(),6,55,18,(),27,(),55,0/,A3,24,(),21,22,3,88,30,(),110,22,0/,A4,9,33,12,(),6,(),12,(),33,0/,销量,44,88,88,77,297,余额,11,0,33,11,0/,0/,使用位势法计算各非基变量检验数，填入括号中：,B1,B2,B3,B4,产量,位势,u,i,A1,12,11,33,11,9,(-6),15,77,99,0,A2,30,(45),6,55,18,(30),27,(39),55,-27,A3,24,(24),21,22,3,88,30,(27),110,-12,A4,9,33,12,(-18),6,(-6),12,(0),33,-3,销量,44,88,88,77,297,位势,v,j,12,33,15,15,令,u,1,=0,，由基变量满足,u,i,+,v,j,=,c,ij,，依次得到各位势,v,1,=12,，,v,2,=33,，,v,4,=15,，,u,4,=-3,，,u,2,=-27,，,u,3,=-12,，,v,3,=15,，再根据公式,s,ij,=,c,ij,-,u,i,-,v,j,计算各非基变量检验数。,进行调整：选负检验数中最小的,s,42,，那么,x,42,为主元，作为进基变量。以,x,42,为起点找一条闭回路,x,42,、,x,41,、,x,11,、,x,12,，取偶数标号格的最小运量,11,作为调整量，调整后运量为,x,42,=11,，,x,41,=22,，,x,11,=22,，,x,12,=0,（调整为非基变量），得到新的基本解，并重新用位势法计算检验数（令,v,2,=0,），如下表所示。,所有非基变量检验数均非负，得到最优解为,x,11,=22,，,x,14,=77,，,x,22,=55,，,x,32,=22,，,x,33,=88,，,x,41,=22,，,x,42,=11,，其余运量为,0,，最小的总运费为,2805,。,B1,B2,B3,B4,产量,位势,u,i,A1,12,22,33,(18),9,(12),15,77,99,15,A2,30,(27),6,55,18,(30),27,(21),55,6,A3,24,(6),21,22,3,88,30,(9),110,21,A4,9,22,12,11,6,(12),12,(0),33,12,销量,44,88,88,77,297,位势,v,j,-3,0,-18,0,第五单元,有一个工厂要确定明年各季度的生产计划，通过订货了解到各季度对产品的需求量,d,k,分别为,4000,件、,3000,件、,4000,件和,4000,件。又知，工厂生产该产品的季度固定成本为,10,万元（但如果在某季度中，该种产品,1,件也不生产，则不需支付固定成本费），单位产品的可变成本为,50,元，由于设备的能力所限，每季度最多只能生产,5000,件。若产品销售不出，则每件每季度的存贮费为,8,元。假设本年底无存货转入下年，明年末也不需要留有存货，问每季度的生产计划应如何安排（假设生产产量以千件为单位），才能使生产的总费用最省？,解：首先建立动态规划模型,（,1,）阶段,k,：每个季度作为一个阶段，,k,=1,2,3,4,（,2,）状态变量,s,k,：第,k,个季度初的库存量（千件）,（,3,）决策变量,u,k,：第,k,个季度的生产量（千件）,（,4,）状态转移方程：,s,k,+1,=,s,k,+,u,k,-,d,k,(,需求，千件