资源描述：
《运筹学 指派问题.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、一指派问题AssignmentProblem设有n项工作和n个人，且一人只做一项工作，而一项工作只需一个去做。c为第i个人做第j项工作所需要的时间。问应如何安排人员使ij总的时间最省？⎧1当第i个人做第j项工作时设xij=⎨，则该问题的数学模型为⎩0其他nnminf=∑∑cijxiji==11jns.t.∑xij=1j=1,2,?,ni=1n∑xij=1i=1,2,?,nj=1xij=0,1i,j=1,2,?,n匈亚利法介绍某四人将分别被指派去完成四项工作，要求每人只做一项工作，而一项工作只需一人。已知他们完成不同工作所
2、需要时间如下表工作ABCD人员甲10232112乙18122223丙17222421丁15161917问应如何安排他们的工作使总时间最少？工作ABCD⎛10232112⎞−10人员⎜⎟甲1023211218122223−12乙18122223解：⎜⎟丙17222421⎜17222421⎟−17丁15161917⎜⎝15161917⎟⎠−15⎛⎞013112⎛⎞01370每行减去⎜⎟每列减去⎜⎟6069601011⎯⎯⎯⎯其最小数→⎜⎟⎯⎯⎯⎯其最小数→⎜⎟⎜⎟0574⎜⎟0532⎜⎟⎜⎟⎝⎠0142⎝⎠0100−4−2结
3、论：甲做工作D；乙做工作B；丙做工作A；丁做工作C。⎛127979⎞−7⎛50202⎞⎜89666⎟每行减去其最⎜⎟⎜⎟−6小数,然后每⎜23000⎟C=⎜71712149⎟−7⎯列减去其最小数⎯→⎯⎯⎯⎯010572⎜⎟⎜15146610⎟−6⎜98004⎟⎜⎝4107109⎟⎠−4⎜06365⎟⎝⎠⎛⎞50202⎛⎞70202⎜⎟23000⎜⎟⎜⎟43000第三、五行减⎜⎟→⎜⎟010572-2⎯⎯⎯⎯⎯22，第一列加→⎜⎟08350⎜⎟⎜⎟⎜⎟98004⎜⎟118004⎜⎟⎝⎠06365-2⎜⎟⎝⎠04143+2关
4、于最大值问题最大值问题只需对效益矩阵C=(cij)作处理B=()M−cij，其中M=maxmaxcij。将其化为以B作效益矩ij阵的最小问题来处理。二线性规划LinearProgramming例：某工厂生产A、A两种产品，生产每单12位产品A、A可分别获利15元和20元。每个设该工厂生产的两12产品都需经过三道工序，每道工序在一个个产品产量分别为x1、月内所能利用的工时数以及单位产品A1、A2x2，则该模型为在三道工序中所需要的加工时间如下表：maxZ=15x1+20x2工时工序产品B1B2B3s.t.3x1+2x2≤8
5、00A13212x1+3x2≤800A2231x1+x2≤350需求量800800350x1,x2,x3≥0工厂应如何安排一个月的生产计划，使获得的利润最多？线性规划的一般数学模型⎛⎞x1maxz=cx←目标函数⎜⎟x其中：x=⎜⎟2s.t.Ax≤b←约束条件⎜⎟@x≥0←变量限制⎜⎟x⎝⎠nccc=(12?cn)maxzcxcx=++?cx1122nn⎛⎞aa1112?a1ns.t.axax111++122?+≤axb1nn1⎜⎟aa?aaxax++?+≤axbA=⎜⎟21222n2112222nn2⎜⎟@??@@⎜⎟
6、aa?a⎝⎠mm12mnaxax++?+≤axbmm1122mnnm,,xx12?xn≥0bbb=(12?bm)线性规划的标准模型maxZ=cxs.t.Ax=bx≥0注：在解线性规划模型时，一般要求b≥0线性规划模型的标准化（1）目标函数的规范化问题minf⇒max(−f)（2）约束条件的规范化问题---引入松弛变量、剩余变量⎯加松弛变量⎯→⎯⎯⎯⎯x3x+x+x=15x1+20x2≤3151202333x1+2x2≥7⎯减剩余变量⎯→⎯⎯⎯⎯x33x1+2x2−x3=7（3）变量的规范化问题a)若xi≤0，则令xi=−
7、xi′并代入模型b)若xi无约束，则令xi=xi′−xi′′并代入模型举例标准化线性规划模型minZ=−2x1+x2−x3s.t.2x1+x2−x3=302x2−3x3≥12x1−x2+2x3≤10x1≥0,x2≤0,x3无约束1.将目标函数由最小问题化为最大问题2.第二个约束条件减去x4，第一个约束条件加上x53.令x2=−x2′，x3=x3′−x3′′则原模型化为maxZ=2xxxx++−′′′′123s.t.2xxxx−′−+′′′=301233xxxx−2′′′−+−33′12=2334xxxx+′′′+−22′
8、+=x1012335,,,,,xxxxxx′′′′≥0123345xj≥0不需要处理变量xj≤0xj=−x′jxj无限制xj=xx′−′′jbj≥0不需要处理约束bj≤0约束条件两端用乘-1≤加松弛变量条件=不需要处理≥减剩余变量目标maxz不需要处理函数minx令z′=-z，求maxz′单纯形法SimplexMet
