运筹学-第01章-线性规划问题.ppt

运筹学运筹学 第一章 线性规划问题本章重点本章重点n线性性规划建模划建模n线性性规划的划的图解法解法n线性性规划的划的标准形式准形式n单纯形法形法n两两阶段法段法n大大M法法线性规划的概念线性规划的概念n对于求取于求取变量量xj(j=1,2,n)，使之既，使之既满足足线性性约束条件，又使束条件，又使线性的目性的目标函数取得极函数取得极值的一的一类最最优化化问题称称为线性性规划划问题uxj(j=1,2,n)表示解决表示解决问题的方案，称的方案，称为决策决策变量量u约束条件表示要解决的束条件表示要解决的问题的限制条件，用一的限制条件，用一组决决策策变量的量的线性等式或性等式或线性不等式来表示性不等式来表示u目目标函数表示要解决的函数表示要解决的问题要求达到的目要求达到的目标，用决，用决策策变量的量的线性函数表示性函数表示线性规划建模步骤线性规划建模步骤n设定决策定决策变量量n明确明确约束条件并用决策束条件并用决策变量的量的线性等式或不性等式或不等式表示等式表示n用用变量的量的线性函数表示要达到的目性函数表示要达到的目标，并确，并确定是求极小定是求极小还是求极大是求极大n根据根据变量的物理性量的物理性质确定确定变量是否具有非量是否具有非负性性n注：其中最关注：其中最关键是是设定决策定决策变量量这一步一步生产计划问题生产计划问题(1)(1)n某工厂用三种原料生某工厂用三种原料生产三种三种产品，已知的条品，已知的条件如下表所示，件如下表所示，试制制订总利利润最大的日生最大的日生产计划划产品所需原料数量（公斤/件）产品Q1（件）产品Q2（件）产品Q3（件）原料可用量（公斤/日）原料P12301500原料P2024800原料P33252000产品的利润（千元/件）354生产计划问题生产计划问题(2)(2)n设每天生每天生产三种三种产品的件数分品的件数分别为x x1 1、x x2 2、x x3 3其中，max是maximize的缩写，含义为“最大化”；s.t.是subject to的缩写，其含义是“受限制于”配料问题配料问题(1)n养海狸鼠，养海狸鼠，饲料料营养要求：养要求：VAVA每天至少每天至少700700克，克，VBVB每天至少每天至少3030克，克，VCVC每天每天刚好好200200克。克。现有五有五种种饲料，搭配使用，料，搭配使用，饲料成分如下表。料成分如下表。问如如何何购买饲料，使得花料，使得花费最少？最少？饲料饲料Va(g)Vb(g)Vc(g)价格价格(元元/kg)/kg)I(kg)II(kg)III(kg)IV(kg)V(kg)32161810.50.220.50.510.220.827495营养要求营养要求(g)(g)7007003030200200配料问题配料问题(2)n设购买饲料分料分别为x x1 1、x x2 2、x x3 3、x x4 4、x x5 5 kgn目目标函数函数为：花：花费最少，最少，则有有其中，min是minimize的缩写，含义为“最小化”；合理下料问题合理下料问题(1)n现需要需要2.9m2.9m、2.1m2.1m、1.5m1.5m长的棒料各的棒料各100100根，根，问要怎要怎样切割切割7.4m7.4m长的原料才能使零料最少？的原料才能使零料最少？n总共有以下共有以下6 6种切割方案，种切割方案，设xj分分别代表采用切代表采用切割方案割方案j j使用的原料数量使用的原料数量合理下料问题合理下料问题(2)n目标函数为：使裁剪后零料最少，则有人员安排问题人员安排问题(1)n医院医院护士士2424小小时值班，班，不同不同时段需要的段需要的护士士人数不等（人数不等（见下表）。每个下表）。每个护士士每天每天连续值班班8 8小小时，在各在各时段开始段开始时上班上班。问最少最少需要多少需要多少护士？士？序号序号时段时段最少人数最少人数106106021014703141860418225052202206020630人员安排问题人员安排问题(2)n设xj为第j时段开始值班的护士人数n目标函数为：使人数最少，则有运输问题运输问题(1)n某厂要把若干某厂要把若干单位的位的产品从两个品从两个仓库A Ai i(i=1,2)(i=1,2)发送到零售点送到零售点B Bj j(j=1,2,3,4)(j=1,2,3,4)，仓库A Ai i能供能供应的的产品数量品数量为a ai i，零售点，零售点B Bj j所需的所需的产品的数量品的数量为b bj j。假。假设供供给总量和需求量和需求总量相等，量相等，且已知从且已知从A Ai i运一个运一个单位位产品往品往B Bj j的运价的运价为c cij。问应如何如何组织运运输才能使才能使总运运费最小？最小？运输问题运输问题(2)n设从从仓库A Ai i运往的零售点运往的零售点B Bj j产品数量品数量为xijn目目标函数函数为：使：使总运运费最少，最少，则有有最大流量问题最大流量问题(1)n某油田通某油田通过输油管道向港口油管道向港口输送原油，中送原油，中间有有5 5个个泵站（站（泵站不存站不存储原油），每段管道原油），每段管道上的上的输送能力如下送能力如下图所示，求所示，求这个系个系统的最的最大大输送能力。送能力。最大流量问题最大流量问题(2)n设各点往其他点的各点往其他点的输送量如下表所示送量如下表所示 最大流量问题最大流量问题(3)n可得可得线性性规划模型划模型线性规划的一般形式线性规划的一般形式(和式和式)线性规划的一般形式线性规划的一般形式(矩阵式矩阵式)作业作业(1)n书上上68页1-1n书上上72-73页的的1-8、1-9、1-10线性规划的图解法线性规划的图解法f(x)=36n图解法一般只用有于1-3个决策变量的线性规划作业作业(2)n书上上70页1-3的的线性规划问题的单纯形解法线性规划问题的单纯形解法n为了使了使线性性规划划问题的解法的解法标准，就要把一准，就要把一般形式化般形式化为标准形式准形式线性规划的标准形式线性规划的标准形式(和式和式)线性规划的标准形式线性规划的标准形式(矩阵式矩阵式)非标准形式的转换非标准形式的转换(1)n目目标函数函数为minmin型，价型，价值系数一律反号系数一律反号u令令 f f(X)=-(X)=-f f(X)=-CX(X)=-CXu则 minminf f(X)=-max-(X)=-max-f f(X)=-maxX)=-maxf f(X)(X)n第第i i个个约束的束的b bi i为负值u则该行左右两端系数同行左右两端系数同时反号，同反号，同时不等号也要不等号也要反向反向nmn或或mn,rankAmu可以去掉可以去掉 m-rankA 个等式个等式约束束非标准形式的转换非标准形式的转换(2)n第第i i个个约束束为 型型u在不等式左在不等式左边加上一个非加上一个非负的的变量量x xn+i n+i，称称为松弛松弛变量；同量；同时令令c cn+i n+i=0=0n第第i i个个约束束为 型型u在不等式左在不等式左边减去一个非减去一个非负的的变量量x xn+in+i ，也称也称为松弛松弛变量；同量；同时令令c cn+in+i =0=0n若若x xj j 0 0u令令x xj j=-=-x xj j ，代入非，代入非标准型，准型，则有有x xj j 0 0n若若x xj j 不限符号不限符号u令令x xj j=x xj j -x xj j，x xj j 0 0，x xj j 0 0，代入非代入非标准型准型示例示例(1.1-1)作业作业(3)n书上上69页1-2的的线性规划问题解的有关概念线性规划问题解的有关概念(1)n可行解：可行解：满足所有足所有约束条件的一束条件的一组变量的取量的取值。所。所有可行解构成的集合称有可行解构成的集合称为可行解集。可行解集。n可行域：可行域：由于一般由于一般线性性规划划问题的可行解集构成的可行解集构成n n维空空间的区域，因此可行解集也称的区域，因此可行解集也称为可行域。可行域。n最最优解：解：使目使目标函数取到最大函数取到最大值(max)或最小或最小值(min)的可行解称的可行解称为线性性规划划问题的最的最优解。解。n最最优值：最最优解解对应的目的目标函数的取函数的取值称称为最最优值n基：基：基：基：设A A为线性性规划模型中划模型中约束方程的系数矩束方程的系数矩阵(m n，且，且mn)，而，而B B为其其m m阶非奇异子矩非奇异子矩阵（即（即|B|0），），则称称B B为该线性性规划模型的一个基。划模型的一个基。n基基基基变变量：量：量：量：基中每个列向量所基中每个列向量所对应的的变量称量称为基基变量。量。n非基非基非基非基变变量：量：量：量：模型中基模型中基变量之外的量之外的变量称量称为非基非基变量。量。线性规划问题解的有关概念线性规划问题解的有关概念(2)n基本解：基本解：令模型中所有非基令模型中所有非基变量的量的值等于零后，由等于零后，由模型的模型的约束方程束方程组得到的一得到的一组解。解。n基本可行解：基本可行解：满足非足非负条件的基本解称条件的基本解称为基本可行基本可行解。解。n可行基：可行基：对应于基本可行解的基称于基本可行解的基称为可行基。可行基。n退化解：退化解：基本可行解基本可行解的非零分量个数的非零分量个数小于小于m时，称，称为退化退化解。解。n最最优基：基：若若对应于基于基B的基本可行解的基本可行解X是是线性性规划的划的最最优解，解，则称称B为线性性规划的最划的最优基基线性规划问题解的有关概念线性规划问题解的有关概念(3)n线性性规划划问题解的关系解的关系约束方程的约束方程的解空间解空间基本解基本解可行解可行解基本基本可行解可行解退化解退化解Rn示例示例(1.2-1)n可行解、基本解和基本可行解可行解、基本解和基本可行解举例例线性规划问题解的特点线性规划问题解的特点(1)n凸集：凸集：设 S 为 n 维欧氏空欧氏空间 En 中一个集合，若中一个集合，若对任意两点任意两点 xS，yS 及任一及任一实数数 0,1，都有，都有x+(1-)yS，则称称 S 是是 En 中的凸集。中的凸集。x+(1-)y 称称为 x 和和 y 的凸的凸组合。合。n凸集中任意两点凸集中任意两点连线上的点都在上的点都在该凸集中凸集中n凸集的凸集的顶点：点：设 S 为非空凸集，非空凸集，zS，若，若 z 不能表不能表示成示成 S 中两个不同点的凸中两个不同点的凸组合（即假合（即假设z=x+(1-)y，xS，yS，(0,1)，必推得，必推得z=x=y），），则称称 z 是凸集是凸集 S 的的顶点。点。n凸集的凸集的顶点的个数一般是有限的点的个数一般是有限的(无限凸集和曲无限凸集和曲边界界凸集除外凸集除外)线性规划问题解的特点线性规划问题解的特点(2)n线性性规划划问题的可行域是凸集的可行域是凸集线性规划问题解的特点线性规划问题解的特点(3)n线性性规划划问题的基本可行解的基本可行解对应于凸集的于凸集的顶点点n最最优解只可能在凸集的解只可能在凸集的顶点或点或边界上，而不可界上，而不可能能发生在凸集的内部生在凸集的内部线性规划问题解的特点线性规划问题解的特点(4)n若有两个最若有两个最优解，解，则其其连线上的点也是最上的点也是最优解，即最解，即最优解有无解有无穷多个多个n顶点个数顶点个数=基本可行解个数基本可行解个数基的个数基的个数线性规划解的情况线性规划解的情况下面的求解方法考虑三种情况：有有界解、有无界解、无解n以2个变量的线性规划为例单纯形法求解的基本原理单纯形法求解的基本原理从可行域的某个顶点出发，设法求取使目标改善的另一个从可行域的某个顶点出发，设法求取使目标改善的另一个顶点，直至确定某个顶点使目标最优或者有无界解为止。顶点，直至确定某个顶点使目标最优或者有无界解为止。确定初始基本可行解确定初始基本可行解求最优解的目标函数值求最优解的目标函数值确定改善方向确定改善方向求新的基本可行解求新的基本可行解检查是否为检查是否为最优解？最优解？是是否否原线性规划问题原线性规划问题单纯形法应用的前提单纯形法应用的前提如何换基如何换基确定初始基本可行解确定初始基本可行解(1)b AZ Cb1a11a12a1nb2a21a22a2nbmam1am2amnZc1c2c3c4下面是线性规划问题标准形式的参数表下面是线性规划问题标准形式的参数表Z 表示目标函数表示目标函数确定初始基本可行解确定初始基本可行解(2)n具体如何得到一具体如何得到一组初始基本可行解不是初始基本可行解不是单纯形法考形法考虑的内容，在两的内容，在两阶段法段法/大大M法中法中说明明n下面介下面介绍在确定了一个可行基（或一在确定了一个可行基（或一组基基变量）后，量）后，如何由参数表得到如何由参数表得到单纯形表形表u根据等式根据等式约束，把基束，把基变量用非基量用非基变量表达量表达u把基把基变量的表达式代入目量的表达式代入目标函数，用非基函数，用非基变量表示目量表示目标函数函数u把基把基变量的表达式按等式量的表达式按等式约束的形式写出，束的形式写出，这m m个等式个等式约束和用非基束和用非基变量表示的目量表示的目标函数以及非函数以及非负约束构成一束构成一个新的个新的线性性规划，划，这个个线性性规划和原划和原线性性规划等价划等价u这个个线性性规划的参数表即划的参数表即为原原线性性规划的一个划的一个单纯形表形表确定初始基本可行解确定初始基本可行解(3)B-1bB-1BB-1NZ-CBB-1bCB-CBB-1B CN-CBB-1NB-1bIB-1NZ-CBB-1b0CN-CBB-1NbAZCbBNZ CBCNB-1b B-1B B-1NZCBCN用矩阵表示如下：用矩阵表示如下：等式变换等式变换用非基变量表示目标函数用非基变量表示目标函数为了方便矩阵为了方便矩阵运算，通常将运算，通常将目标目标 Z 记为记为0 0下面的单纯形表中，下面的单纯形表中，B B-1-1b b是基变量的解值，非基是基变量的解值，非基变量的解值均为变量的解值均为0 0，对应的目标函数值为，对应的目标函数值为C CB BB B-1-1b b，N N=C=CN N-C-CB BB B-1-1N N 称为非基变量的检验数称为非基变量的检验数示例示例(1.3-1)n试列出下面列出下面线性性规划划问题的初始的初始单纯形表形表1002311012033201040452400注：注：注：注：该问题添加了两个松弛变量，标准形式的参数表就是初始单纯形表判断是否最优判断是否最优n在用非基在用非基变量表示的目量表示的目标函数中，函数中，N N=C=CN N-C-CB BB B-1-1N N 称称为非基非基变量的量的检验数，它数，它们是目是目标函数中非基函数中非基变量量的系数的系数n假假设非基非基变量量xj的的检验数数为j，若，若xj 从从0开始开始增大，增大，其他非基其他非基变量的量的值不不变，则基基变量和目量和目标函数（用函数（用非基非基变量表示）要量表示）要发生生变化化uj0时，目，目标函数函数值减少，当前基本可行解即减少，当前基本可行解即为最最优解解uj0时，目，目标函数函数值增大，当前基本可行解不是最增大，当前基本可行解不是最优解解n因此，若因此，若N N00，则当前基本可行解是最当前基本可行解是最优解，算解，算法法结束，否束，否则，需要，需要进行改善行改善1002311012033201040452400确定改善方向确定改善方向(1)n确定入基确定入基变量量u从不从不满足足N N00的非基的非基变量量中任中任选一个一个x xj*j*，x xj*j*称称为入基入基变量，量，让x xj*j*增大可以改善目增大可以改善目标u第第j*+1j*+1列称列称为主列主列ux xj*j*的的选择可以任意，但有可能会造成解的退化，可以任意，但有可能会造成解的退化，进而而产生循生循环计算。一般算。一般选择下下标j j最小的（或最最小的（或最大的）大的）1002311012033201040452400确定改善方向确定改善方向(2)u若找不到若找不到 ，则算法算法结束，原束，原问题有无界解有无界解若所有的若所有的a aij*ij*00，则x xj*j*在所有基在所有基变量的表达式中系数量的表达式中系数都都为正，正，则x xj*j*可以一直增大，使目可以一直增大，使目标函数函数趋向无向无穷u若下若下标i*(即第即第 i*行行)使使 最小，最小，则第第 i*行行对应的基的基变量量称称为出基出基变量，第量，第 i*行称行称为主行主行u若有多个行同若有多个行同时使使 最小，最小，可以任意可以任意选择其中之一其中之一为主行，主行，但有可能会造成解的退化，但有可能会造成解的退化，进而而产生循生循环计算。一般算。一般选择 i 最小的最小的(或最大的或最大的)行行u主行主行 i*行与行与主列主列 j*相交的元素相交的元素ai*j*称称为主元主元n确定出基变量确定出基变量u为了保证不出基的基变量的取值在改善后仍为正值，按最为了保证不出基的基变量的取值在改善后仍为正值，按最小比例原则选择出基变量小比例原则选择出基变量1002311012033201040452400解的改善解的改善n进行行换基运算（也称基运算（也称为换主元运算）主元运算）u对当前的当前的线性性规划，通划，通过等式等式变换将主行所将主行所对应的等式的等式约束中束中x xj*j*的系数的系数变为1 1消去其它等式消去其它等式约束和目束和目标函数中的函数中的x xj*j*（将其系数（将其系数变为0 0）u相当于，在相当于，在单纯形表中，通形表中，通过矩矩阵的初等行的初等行变换将主行的各元素乘上某一个数将主行的各元素乘上某一个数值，使得主元的，使得主元的值变为1 1将主行的各元素乘上某一个数将主行的各元素乘上某一个数值，再加到其他行上去，使得主，再加到其他行上去，使得主列中除主元外的其它元素的列中除主元外的其它元素的值变为0 0n得到了一个改善的基本可行解得到了一个改善的基本可行解n返回判断解是否最返回判断解是否最优示例示例(1.3-2)10023110120332010404524001002311040112/301/3040452400示例示例(1.3-3)2001-1/31-2/340112/301/3-160005-8/30-40/3检验数2不满足非正条件，需要调整2001-1/31-2/320101-11-170000-1-5-10n检验数全部数全部满足非正条件足非正条件n得最得最优解解为ux x1 1=20=20，x x2 2=20=20，x x3 3=0=0umaxmaxf f(X)=1700(X)=1700n下面下面给出出该问题的最的最优基基示例示例(1.3-4)n将最将最优表中表中m个基个基变量的量的约束方程系数列按束方程系数列按单位矩位矩阵Im 顺序排列，同序排列，同时相相应的的调整参整参数表中基数表中基变量的量的约束方程系数列的束方程系数列的顺序序n由由调整后的参数表中整后的参数表中m个基个基变量的量的约束方程束方程系数列系数列组成的成的m阶方方阵就是最就是最优基基2001-1/31-2/320101-11-170000-1-5-101002311012033201040452400作业作业(4)n书上上70页1-5的的和和n补充要求：写出最充要求：写出最优基基确定初始基本可行解的方法确定初始基本可行解的方法(1)n由原由原线性性规划划问题直接确定一直接确定一组初始基本可初始基本可行解很多行解很多时候是很困候是很困难的。的。n可以通可以通过添加人工添加人工变量的方法来确定一量的方法来确定一组初初始基本可行解始基本可行解确定初始基本可行解的方法确定初始基本可行解的方法(2)n添加的添加的变量量x xn+1n+1,x,xn+2n+2,x,xn+mn+m称称为人工人工变量量n添加了人工添加了人工变量后，新量后，新问题有了一个初始有了一个初始基本可行解，可以用基本可行解，可以用单纯形法迭代形法迭代计算。算。n若原若原线性性规划划问题第第i 个个约束束为 型，型，则将将其化其化为标准形式后再添加准形式后再添加人工人工变量量时，相，相应的人工的人工变量量x xn+in+i可以不用再添加了可以不用再添加了n经过若干次迭代，把人工若干次迭代，把人工变量全部替量全部替换出出基，基，则原原问题的的约束条件得到恢复，同束条件得到恢复，同时也就有了一个原也就有了一个原问题的基本可行解的基本可行解确定初始基本可行解的方法确定初始基本可行解的方法(3)n这一方法的关一方法的关键在于怎在于怎样才能将人工才能将人工变量尽量尽快替快替换出基出基n为了解决了解决这个个问题，提出了两种方法，提出了两种方法u大大M M法法u两两阶段法段法大大M法法(1)n大大M法也称法也称为惩罚法法nM为任意为任意大的正数大的正数大大M法法(2)n对新的新的线性性规划使用划使用单纯形法，其解有两种形法，其解有两种情况情况u若有无界最若有无界最优解，解，则原原问题有无界最有无界最优解解u若有有界最若有有界最优解，又有两种情况解，又有两种情况若人工若人工变量的量的值不全不全为0，则原原问题无可行解无可行解若人工若人工变量取量取值均均为0，则当前最当前最优值就是原就是原问题的最的最优值，当前最，当前最优解的前解的前n个分量就是原个分量就是原问题的最的最优解解若原问题有可行解X=(x1,x2,xn)T，则X=(x1,x2,xn,0,0)T是新的线性规划的可行解，则g(X)有界。若人工变量的值不全为0，则g(X)趋向于负无穷。因此，原问题无可行解。示例示例(1.4-1)n用大用大M法求解下面的线性规划法求解下面的线性规划先化为标准形式示例示例(1.4-2)n改成大改成大M M法需要的线性规划法需要的线性规划列出参数表6 62 21 10 0-1-10 01 10 04 41 11 11 10 0-1-10 01 10 0-10-10-8-8-7-70 00 0-M-M-M-M示例示例(1.4-3)n调整得调整得6 62 21 10 0-1-10 01 10 04 41 11 11 10 0-1-10 01 110M10M-10+3M-10+3M-8+2M-8+2M-7+M-7+M-M-M-M-M0 00 03 31 11/21/20 0-1/2-1/20 01/21/20 01 10 01/21/21 11/21/2-1-1-1/2-1/21 130+M30+M0 0-3+M/2-3+M/2-7+M-7+M-5+M/2-5+M/2-M-M5-3M/25-3M/20 0示例示例(1.4-4)2 21 10 0-1-1-1-11 11 1-1-12 20 01 12 21 1-2-2-1-12 236360 00 0-1-1-2-2-6-62-M2-M6-M6-Mn检验数全部数全部满足非正条件足非正条件n得原得原问题的最的最优解解为ux1=2，x2=2，x3=0uminf(X)=36两阶段法两阶段法(1)两阶段法两阶段法(2)n对新的新的线性性规划使用划使用单纯形法，必定存在一形法，必定存在一个有界最个有界最优解，在解，在这个最个最优解中解中u若最若最优值不不为0，则原原问题无可行解无可行解u若最若最优值为0，则原原问题有可行解有可行解人工人工变量均量均为非基非基变量量对当前的当前的单纯形表，去掉其中人工形表，去掉其中人工变量量对应的列，将最后的列，将最后一行（目一行（目标函数系数函数系数对应的行）的的行）的值改改为(0,C)，再使用，再使用单纯形法求解形法求解基基变量中有人工量中有人工变量量此此时基中的人工基中的人工变量取量取值为0选择某个不是人工某个不是人工变量的非基量的非基变量量进基，把在基中的人工基，把在基中的人工变量替量替换出来，再按照人工出来，再按照人工变量均量均为非基非基变量的情况量的情况处理理若原问题有可行解X=(x1,x2,xn)T，则X=(x1,x2,xn,0,0)T是新的线性规划的可行解，则g(X)=0。因此，若最优值不为0，则原问题无可行解。示例示例(1.5-1)n用用两阶段法两阶段法求解下面的线性规划求解下面的线性规划先化为标准形式示例示例(1.5-2)n改成两阶段法需要的线性规划改成两阶段法需要的线性规划列出参数表6 62 21 10 0-1-10 01 10 04 41 11 11 10 0-1-10 01 10 00 00 00 00 00 0-1-1-1-1示例示例(1.5-3)n调整得调整得6 62 21 10 0-1-10 01 10 04 41 11 11 10 0-1-10 01 110103 32 21 1-1-1-1-10 00 03 31 11/21/20 0-1/2-1/20 01/21/20 01 10 01/21/21 11/21/2-1-1-1/2-1/21 11 10 01/21/21 11/21/2-1-1-3/2-3/20 0示例示例(1.5-4)2 21 10 0-1-1-1-11 11 1-1-12 20 01 12 21 1-2-2-1-12 20 00 00 00 00 00 0-1-1-1-1n检验数全部数全部满足非正条件，两足非正条件，两阶段法第段法第一一阶段段调用用单纯形法形法结束束n人工人工变量的量的值全部全部为零，零，进行下一行下一阶段段调用用单纯形法前的初始化工作形法前的初始化工作示例示例(1.5-5)2 21 10 0-1-1-1-11 12 20 01 12 21 1-2-20 0-10-10-8-8-7-70 00 02 21 10 0-1-1-1-11 12 20 01 12 21 1-2-236360 00 0-1-1-2-2-6-6n检验数全部满足非检验数全部满足非正条件正条件n得原问题的最优解得原问题的最优解为为ux1=2，x2=2，x3=0uminf(X)=36作业作业(5)n书上上71页1-6的的上机题目上机题目n用用两阶段法或或大M法求解求解标准形式准形式线性性规划划