北外奥鹏作业运筹学.ppt

《北外奥鹏作业运筹学.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学作业精讲第一单元某企业生产甲、乙两种产品，其单位利润分别为20元和30元。每生产一件甲产品需劳动力3个，原材料2千克，设备4小时；每生产一件乙产品需劳动力7个，原材料4千克，设备3小时。企业现有劳动力240个，原材料150千克，设备可用时间为250小时。问：如何安排生产计划，才能使所获总利润最大？写出线性规划模型；化成标准形式；用图解法进行求解。解：设x1和x2分别表示产品甲和乙的产量，这样可以建立如下的数学模型。目标函数：Max 20x1+30x2约束条件：s.t. 3x1+ 7x2≤240（劳动力限制）2x1+ 4x2≤150（原材料限制）4x1+ 3x2≤250（设备限制）x

2、1，x2≥0（非负约束）化为标准型：目标函数：Max 20x1+30x2约束条件：s.t. 3x1+  7x2+x3= 2402x1+ 4x2+x4= 1504x1+ 3x2+x5= 250x1，x2，x3，x4，x5≥0阴影部分为可行域，虚线为目标函数线。由图可知最优解为约束2和约束3的交点，解得坐标为（55,10），故最优生产计划为生产甲产品55件，乙产品10件，最大利润为20×55+30×10=1400元。第二单元某厂生产三种型号的铝锅，已知单耗数据如下。试制定最优生产计划使总收入最大。解：设x1、x2、x3分别表示大号、中号、小号铝锅的产量，这样可以建立如下的数学模型。目标函数：

3、Max 50x1+40x2+30x3约束条件：s.t. 6x1+2x2+4x3≤400（铝板限制）4x1+8x2+6x3≤360（劳力限制）8x1+4x2+10x3≤420（机器限制）x1，x2，x3≥0（非负约束）化为标准型：目标函数：Max 50x1+40x2+30x3约束条件：s.t. 6x1+2x2+ 4x3+x4= 4004x1+8x2+ 6x3+x5= 3608x1+4x2+10x3+x6= 420x1，x2，x3，x4，x5，x6≥0使用单纯形法求解：得到最优解（40,25,0,110,0,0），最优值3000。即应该生产大号铝锅40个，中号铝锅25个单位，小号铝锅产量为0

4、（不生产），最大利润为3000元。이문서는나눔글꼴로작성되었습니다.설치하기第三单元线性规划Maxz=–5x1+5x2+13x3s.t.   –x1+x2+ 3x3≤2012x1+4x2+10x3≤90x1,x2,x3≥0的最优表为：分析在下列条件下，最优解分别有什么变化（1）b2由90变为70。（2）c1由-5变为-10。（3）增加一个约束条件4x1+3x2+6x3≤50。解：（1）由最优基不变的条件Max{-bi/βir½βir>0}≤Dbr≤Min{-bi/βir½βir<0}得-10=-10/1≤Db2b2由90变为70，超出了允许变化范围，继续计算或者由B-1(b+Db)=(2

5、0,-10)T可以知道最优基发生变化，继续迭代。最优解变为x1=0，x2=5，x3=5，x4=0，x5=0，最优值z*=90。2）c1是非基变量的系数，最优解不变的条件是：Dc1≤-s1，c1由-5→-10，Dc1=-5<0=-s1，不影响最优解。（3）增加一个约束条件4x1+3x2+6x3≤50，原最优解不满足这个约束。引入松弛变量，得到4x1+3x2+6x3+x6=50填入最优单纯形表，进一步求解，得到最优解为X=(0，10，10/3)T，最优值为280/3。第四单元对于以下的运输问题，若各个销地少得到1个单位的产品，将要求得到赔偿，金额分别为9、12、6、12，问如何组织运输，才能

6、使总费用最低。（建立运输模型，用最小元素法求初始解，并求出最优解）解：总产量为99+55+110=264，总销量44+88+88+77=297，产销不平衡且供不应求，增加一个虚拟产地A4，其产量为297-264=33。由虚拟产地运往销地的费用即为赔偿金额。因此可以建立运输模型如下：使用最小元素法求初始解：说明：每次选择最小元素，因此依次选择3（x33）、6（x22）、9（x41）、12（x11）、15（x14）、21（x32）、33（x12）。）得到初始解x11=11，x12=11，x14=77，x22=55，x32=22，x33=88，x41=33，其余运量为0，总运费为3003。使用

7、位势法计算各非基变量检验数，填入括号中：令u1=0，由基变量满足ui+vj=cij，依次得到各位势v1=12，v2=33，v4=15，u4=-3，u2=-27，u3=-12，v3=15，再根据公式sij=cij-ui-vj计算各非基变量检验数。进行调整：选负检验数中最小的s42，那么x42为主元，作为进基变量。以x42为起点找一条闭回路x42、x41、x11、x12，取偶数标号格的最小运量11作为调整量，调整后运量为x42=11，x