北外奥鹏作业运筹学

运筹学作业精讲第一单元某企业生产甲、乙两种产品，其单位利润分别为20元和30元。每生产一件甲产品需劳动力3个，原材料2千克，设备4小时；每生产一件乙产品需劳动力7个，原材料4千克，设备3小时。企业现有劳动力240个，原材料150千克，设备可用时间为250小时。问：如何安排生产计划，才能使所获总利润最大？写出线性规划模型；化成标准形式；用图解法进行求解。解：设x1和x2分别表示产品甲和乙的产量，这样可以建立如下的数学模型。目标函数：Max20x1+30x2约束条件：s.t.3x1+7x2≤240（劳动力限制）2x1+4x2≤150（原材料限制）4x1+3x2≤250（设备限制）x1，x2≥0（非负约束）化为标准型：目标函数：Max20x1+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元。第二单元产品资源大号中号小号可用资源量铝板(张)624400劳力(小时)486360机器(台)8410420售价(元/个)504030某厂生产三种型号的铝锅，已知单耗数据如下。试制定最优生产计划使总收入最大。解：设x1、x2、x3分别表示大号、中号、小号铝锅的产量，这样可以建立如下的数学模型。目标函数：Max50x1+40x2+30x3约束条件：s.t.6x1+2x2+4x3≤400（铝板限制）4x1+8x2+6x3≤360（劳力限制）8x1+4x2+10x3≤420（机器限制）x1，x2，x3≥0（非负约束）化为标准型：目标函数：Max50x1+40x2+30x3约束条件：s.t.6x1+2x2+4x3+x4=4004x1+8x2+6x3+x5=3608x1+4x2+10x3+x6=420x1，x2，x3，x4，x5，x6≥0使用单纯形法求解：504030000CBXBb’x1x2x3x4x5x60x4400624100200/30x5360486010900x6420(8)410001105/2-z050*40300000x4850-1-7/210-3/4---0x51500(6)101-1/22550x1105/211/25/4001/8105-z-2625015*-65/200-25/40x411000-10/311/6-5/640x225011/601/6-1/1250x140107/60-1/121/6-z-300000-350-5/2-5得到最优解（40,25,0,110,0,0），最优值3000。即应该生产大号铝锅40个，中号铝锅25个单位，小号铝锅产量为0（不生产），最大利润为3000元。이문서는나눔글꼴로작성되었습니다.설치하기第三单元cj-551300θiCBXBb’x1x2x3x4x55x220-113100x510160-2-41-z-10000-2-50线性规划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½βir0}≤Dbr≤Min{-bi/βir½βir0}得-10=-10/1≤Db2b2由90变为70，超出了允许变化范围，继续计算或者由B-1(b+Db)=(20,-10)T可以知道最优基发生变化，继续迭代。最优解变为x1=0，x2=5，x3=5，x4=0，x5=0，最优值z*=90。2）c1是非基变量的系数，最优解不变的条件是：Dc1≤-s1，c1由-5→-10，Dc1=-50=-s1，不影响最优解。cj-551300CBXBb’x1x2x3x4x55x220-113100x5-10160(-2)-41-z-10000-2-505x252310-53/213x35-8012-1/2-z-90-1600-1-1（3）增加一个约束条件4x1+3x2+6x3≤50，原最优解不满足这个约束。引入松弛变量，得到4x1+3x2+6x3+x6=50填入最优单纯形表，进一步求解，得到最优解为X=(0，10，10/3)T，最优值为280/3。Ci-5513000CBXBbx1x2x3x4x5x65x220-1131000x510160-2-4100x650436001-z-10000-2-5005x220-1131000x510160-2-4100x6-1070(-3)-301-z-10000-2-5005x210610-2010x550/334/300-21-2/313x310/3-7/30110-1/3-z-280/3-14/300-30-2/3第四单元对于以下的运输问题，若各个销地少得到1个单位的产品，将要求得到赔偿，金额分别为9、12、6、12，问如何组织运输，才能使总费用最低。（建立运输模型，用最小元素法求初始解，并求出最优解）解：总产量为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。B1B2B3B4产量余额A1121133119()15779988,11A230()65518()27()550/A324()212238830()11022,0/A493312()6()12()330/销量44888877297余额11,033,110/0/使用位势法计算各非基变量检验数，填入括号中：B1B2B3B4产量位势uiA1121133119(-6)1577990A230(45)65518(30)27(39)55-27A324(24)212238830(27)110-12A493312(-18)6(-6)12(0)33-3销量44888877297位势vj12331515令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，x41=22，x11=22，x12=0（调整为非基变量），得到新的基本解，并重新用位势法计算检验数（令v2=0），如下表所示。所有非基变量检验数均非负，得到最优解为x11=22，x14=77，x22=55，x32=22，x33=88，x41=22，x42=11，其余运量为0，最小的总运费为2805。B1B2B3B4产量位势uiA1122233(18)9(12)15779915A230(27)65518(30)27(21)556A324(6)212238830(9)11021A492212116(12)12(0)3312销量44888877297位势vj-30-180第五单元有一个工厂要确定明年各季度的生产计划，通过订货了解到各季度对产品的需求量dk分别为4000件、3000件、4000件和4000件。又知，工厂生产该产品的季度固定成本为10万元（但如果在某季度中，该种产品1件也不生产，则不需支付固定成本费），单位产品的可变成本为50元，由于设备的能力所限，每季度最多只能生产5000件。若产品销售不出，则每件每季度的存贮费为8元。假设本年底无存货转入下年，明年末也不需要留有存货，问每季度的生产计划应如何安排（假设生产产量以千件为单位），才能使生产的总费用最省？解：首先建立动态规划模型（1）阶段k：每个季度作为一个阶段，k=1,2,3,4（2）状态变量sk：第k个季度初的库存量（千件）（3）决策变量uk：第k个季度的生产量（千件）（4）状态转移方程：sk+1=sk+uk-dk(需求，千件)（即季度末库存量=季度初库存量+季度生产量-季度销售量或需求量）（5）阶段指标：gk(sk,uk)=生产成本C(uk)+库存成本E(sk)（6）最优指标函数fk(sk)：第k个季度的状态为sk时从该季度至计划结束的最低总费用（万元）（7）递推方程：fk(sk)=min{gk(sk,uk)+fk+1(sk+1)}（8）终端条件：f5(s5)=0下面进行求解，采用逆序解法。（1）k=5，f5(s5)=0（2）k=4，0≤s4≤4，u4=4-s4，s5=s4+u4-d4（说明：第4季度的需求为4千件，因此库存量不应超过4且显然非负，所以有0≤s4≤4；年底不需要有库存，所以生产量u4=4-s4）s4u4(s4)s5g4(s4,u4)g4(s4,u4)+f5(s5)f4(s4)u4*040303030413025.825.825.8322021.621.621.6231017.417.417.414003.23.23.20（3）k=3，0≤s3≤5+5-4-3=3，s4=s3+u3-d3=s3+u3-4，Max(0,4-s3)≤u3≤Min(5,8-s3)（说明：前两季度总产量为5+5=10千件，需求量为3+4=7千件，所以第3季度初最大库存量=10-7=3千件；在产量需求方面，为了满足需求，至少生产d3-u3=4-u3，且最大产量为5千件，后两个季度总需求为4+4=8千件，产量不应该超过8-s3。因此有0≤s3≤3，Max(0,4-s3)≤u3≤Min(5,8-s3)）（4）k=2，0≤s2≤5-4=1，s3=s2+u2-d2=s2+u2-3，Max(0,3-s2)≤u2≤Min(5,11-s2)（5）k=1，s1=0，s2=s1+u1-d1=u1-4，4≤u1≤5最优解为s1=0,u1*=5,s2=1,u2*=5,s3=3,u3*=5,s4=4，u4*=0即前3个季度均生产5000件，第4个季度不生产，最低总费用为111.4万元。第六单元某企业生产甲、乙两种产品。生产一件甲产品需要使用劳动力4小时，能源2个单位，销售利润为16万元；生产一件乙产品需要使用劳动力2小时，能源4个单位，销售利润为20万元。企业目前拥有劳动力可用时间22小时，能源20个单位。在制定生产计划时，决策者考虑下述4项目标：首先，乙产品的产量不低于甲产品的产量；其次加班费用比较高，尽量不要加班；第三，尽可能充分利用能源，但是又不希望再购买；最后，利润尽量不少于112万元。求决策方案。（建立目标规划模型并用单纯形法求解）解：设X1、X2分别表示甲产品和乙产品的产，以建立如下的目标规划模型：目标函数：MINF=P1D1++P2D2++P3(D3-+D3+)+P4D4-约束条件：X1﹣X2+D1--D1+=04X1+2X2+D2-﹣D2+=222X1+4X2+D3-﹣D3+=2016X1+20X2+D4-﹣D4+=112X1，X2，DI-，DI+≥0，I=1,2,3,4（说明：目标1和2是不超过目标值，因此正偏差变量尽量小；目标3是恰好达到目标值，因此要求正、负偏差变量都尽量小；目标4要求不少于目标值，因此是负偏差变量尽量小）下面用单纯形法进行求解。列出单纯形表，取d1-、d2-、d3-、d4-为初始基变量。把最小化问题转为为最大化问题，所以目标函数系数均乘以-1；基变量的检验数应该为0，处理初始基