下载文档原格式
求线性规划问题的最优整数解的方法作者：陈树礼来源：《中学教学参考·理科版》2010年第01期线性规划是新教材新增内容,在近几年高考中都以较易题目出现,要学好本节内容,应注意以下三点.一、判定最优解求线性目标函数z=ax+by(a≠0、b≠0)在线性约束条件下的最优解问题,可转化为求直线y=-abx+zb在y轴上的截距的最大值和最小值.易知在b>0时,当zb最大时,z取得最大值,当zb最小时,z取得最小值;在b二、求出最优解依据边界直线的斜率(或倾斜角)计算出最优解.三、修正最优解,得到最优整数解现改编人教版高二(上例3的问题,以求达到抛砖引玉的目的.【例】某工厂生产甲、乙两种产品.已恬生产甲种产品1t需耗A种矿石10t、B种矿石5t、煤4t;生产乙种产品1t需耗A种矿石4t、B种矿石4t、煤9t.每1t甲种产品的利润是600元,每1t乙种产品的利润是1000元.工厂在生产这两种产品的计划中要求消耗A种矿石不超过300t、B种矿石不超过200t、煤不超过360t.求:(1)甲、乙两种产品各生产多少吨(精确到1吨)才能使利润最大?(2)若甲种产品每吨利润600元,乙产品每吨利润200元.甲、乙两种产品各生产多少吨(精确到1吨)才能使利润最大?(3)若甲种产品每吨利润400元,乙产品每吨利润200元.甲、乙两种产品各生产多少吨(精确到1吨)才能使利润最大?(4)若甲种产品每吨利润200元,乙产品每吨利润600元.甲、乙两种产品各生产多少吨(精确到1吨)才能使利润最大?(5)若甲种产品每吨利润1000元,乙产品每吨利润800元.甲、乙两种产品各生产多少吨(精确到1吨)才能使利润最大?解:(1)设生产甲、乙两种产品分别为x吨,y吨.利润为z元.则10x+4y≤300,5x+4y≤200,4x+9y≤360,x≥0,y≥0,z=600x+1000y.作出以上不等式组表示的平面区域,即可行域.作直线:600x+1000y=0,即直线:3x+5y=0,则z=200(3x+5y).设u=3x+5y,则当u最大时,z最大.易知直线NQ、MN、PM的斜率分别为-52,-54,-49,直线l的斜率为-53.平移直线∵M点为最优解点.由方程组5x+4y=200,4x+9y=360得M点的坐标为(36029,100029).∵x,y都是正整数,∴u=3x+5y=608029也应为正整数.∴u=3x+5y≤209.于是整点(11,35)为所求.当生产甲产品11吨,乙产品35吨时,能使利润总额最大.(2)此时目标函数为z=600x+200y.作直线平移直线∵直线经过点Q(30,0)时,z取得最大值.即只生产甲产品30吨时,获得利润最大.(3)此时目标函数为z=400x+200y.作直线平移直线∵-类似(1)可求解.(4)此时目标函数为z=200x+600y.作直线平移直线∵--49.∴当直线经过点P(0,40)时,5x+4y=0,即只生产乙产品40吨时,获得利润最大.(5)此时目标函数为z=1000x+800y.作直线平移直线∵-∴当直线与直线5x+4y=0重合时,z取得最大值.∴当点位于线段MN上任意一点时,都能使z取得最大值.总之,在本部分内容的学习中,要做到“一定、二算、三修正”.(责任编辑金铃)。
2•解：满足约束条件必修五一一线性规划无数个最优解问题、乘 1问题答案和解析【答案】【解析】1•解：作出不等式组 Z + yMl 表示的平面区域，x?y >?1< 2得到如图的△ ABC 及其内部，其中 A （ 1，0），B （ 0，1），C （3，4）设 z=F （x , y ） =ax+by （a > 0, b >0）,将直线 l : z=ax+by 进 行平移，当I 经过点C 时，目标函数z 达到最大值即当且仅当a=b=1时，+的最小值为7故选：D9目 作出题中不等式组表示的平面区域，得如图的△ ABC 及其内部，再将目标函数 z=ax+by 对应的直线进行平移，可得当 x=3, y=4时，z 最大值为3a+4b=7•然后利用常数代换结合基本不 等式，可得当且仅当 a=b=1时，色+的最小值为7.■a b本题给出二元一次不等式组，在已知目标函数z=ax+by 最大值为7的情况下求” +的最小值.着重考查了运用基本不等式求最值和简单的线性规划等知识，属于中档题.I 的可行域如下图所示Xn••• z 最大值=F (3 , 4) =3a+4b=7, 可得 (3a+4b ) =1 因此, (3a+4b ) (■ + ) = (25+)b 7A 十 b(25+24) >X 49=,7■-01 5* 丫1 2 3n 刃•••.表示可行域内一点（X, y）与P （1, 5）连线的斜率又T k pA= =1, k PB= =-3,•••「的范围是（-汽-3）U （1 , + a）f?i|故选A画出满足约束条件的可行域，分析目标函数的几何意义，数形结合即可分析出目标函数的取值范围.本题考查的知识点是简单线性规划的应用，其中分析出目标函数的几何意义是表示可行域内一点（x, y）与P （1 , 5）连线的斜率是解答的关键.3•解：由约束条件｛¥二0 作出可行域如图，]y?x | 1 <0ly?2x + 4>0|由z=y-ax （a^0, 得y=ax+z,•/ a MQ•要使z=y-ax （a MQ取得的最优解（x, y）有无数个，a不能为负值，当a> 0时，直线y=ax+z与线段AC所在直线重合时，使z=y-ax取得最大值的最优解有无数个；直线y=ax+z与线段BC所在直线重合时，使z=y-ax取得最小值的最优解有无数个.综上，要使z=y-ax （a MQ取得的最优解（x, y）有无数个，贝U a=1或2. 故选：C.由约束条件作出可行域，化目标函数为直线方程的斜截式，结合可行域即可看出使z=y-ax （a MQ取得的最优解（x, y）有无数个的a值.本题考查了简单的线性规划，考查了数形结合的解题思想方法，是中档题.4•解：依题意，满足已知条件的三角形如下图示：令z=0,可得直线x+my=0的斜率为-,111结合可行域可知当直线x+my=0与直线AC平行时，线段AC上的任意一点都可使目标函数z=x+my取得最小值，而直线AC的斜率为=-1 ,3^1所以-=-1，解得m=1,ki故选C.增加网友的解法，相当巧妙值得体会！请看：依题意，1+3m=5+2m v 3+m，或1+3m=3+m v 5+2m，或3+m=5+2m v 1+3m解得m €空集，或m=1，或m €空集，所以m=1，选C.评析：此解法妙在理解了在边界处取到最小值这个命题的内蕴，区域的三个顶点中一定有两个顶点的坐标是最优解，故此两点处函数值相等，小于第三个顶点处的目标函数值，本题略去了判断最优解取到位置的判断，用三个不等式概括了三种情况，从而解出参数的范围，此方法可以在此类求参数的题中推广，具有一般性！将目标函数z=x+my化成斜截式方程后得：y=- x+_z，若m>0时，目标函数值Z与直线族：ip priiy=- x+ z截距同号，当直线族y=- x+ z的斜率与直线AC的斜率相等时，目标函数z=x+myrn Jii取得最小值的最优解有无数多个；若m v 0时，目标函数值Z与直线族：y=- x+ z截距异号，Pl III当直线族y=- x+ z的斜率与直线BC的斜率相等时，目标函数z=x+my取得最小值的最优解in rn|有无数多个，但此时是取目标函数取最大值的最优解为无数个，不满足条件.目标函数的最优解有无数多个，处理方法一般是：①将目标函数的解析式进行变形，化成斜截式；②分析Z与截距的关系，是符号相同，还是相反；③根据分析结果，结合图形做出结论④根据斜率相等求出参数.5.解：由题意，使目标函数Z=ax-y (a > 0)取得最大值，而y=ax-z即在Y轴上的截距最小；所以最优解应在线段AC上取到，故ax-y=0应与直线AC平行.■/ k AC=「L=,4?1| 3• I a=,i故选：A.由题设条件，目标函数Z=ax-y (a >0),取得最大值的最优解有无数个知取得最优解必在边界上而不是在顶点上，故最大值应该在边界AB上取到，即ax-y=0应与直线AB平行；进而计算可得答案.本题考查线性规划最优解的判定，属于该知识的逆用题型，知最优解的特征，判断出最优解的位置求参数.6•解：■/目标函数P=ax+y,/• y=_ax+P.故目标函数值Z是直线族y=-ax+P的截距，当直线族y=-ax+P的斜率与边界AC的斜率相等时，目标函数z=ax+y取得最大值的最优解有无数多个，此时，-a=^=-[,5?1 2即a=',① 将目标函数的解析式进行变形，化成 ③根据分析结果，结合图形做出结43 2 1 *1 -2 -3-4-5域.故选B .给出平面区域如图所示，其中A (5, 3),B (1, 1),C (1, 5),若使目标函数z=ax+y (a> 0)取得最大值的最优解有无穷多个，则a 的值为目标函数的最优解有无数多个，处理方法一般是： 斜截式②分析Z 与截距的关系，是符号相同，还是相反 论④根据斜率相等求出参数.7.解：■/ z=x+ay 则y=- x+ z ,为直线y=- x+在y 轴上 的截距要使目标函数取得最小值的最优解有无穷多个， 则截距最小时的最优解有无数个.•「a >0把x+ay=z 平移，使之与可行域中的边界 AC 重合即可，• -a=-1「a=1 故选 D .先根据约束条件画出可行域，由z=x+ay ，利用z 的几何意义求最值，要使得取得最小值的最优解有无数个， 只需直线z=x+ay 与可行域的边界 AC 平行时，从而得 到a 值即可. 本题主要考查了简单线性规划的应用、二元一次不等 式(组)与平面区域等知识，解题的关键是明确 z 的几何意义，属于中档题. 8•解：由x , y 满足线性约束条件联立L =^.，解得C ( 2, 1). > —V ■由可行域可知：当目标函数经过点 ••• 2a+b=1 (a >0， b >0)， ••丄+：=( 当且仅当b=2a=时，取等号,2••丄半的最小值为8. 故选B .由约束条件作出可行域，并找出目标函数取得最大值时的条件， 进而利用基本不等式的性质即可求出.本题考查线性规划的有关内容及基本不等式的运用，确定 2a+b=1，正确运用基本不等式是关键.9.解：由题意，z=mx+y ( m > 0)在平面区域内取得最大值的 最优解有无数多个，最优解应在线段AC 上取到，故mx+y=0应与直线AC 平行y JX，作出可行$5 ■ y V >04一<23 -2一1XX 1 1 1 >-5 -4 -3£[1 ;3 4 5C 时z 取得最大值1,-2-3 --4 —+ 后=8，-5-4 5借助与图形找到此时z的最小值即在取得最值的最优解有无穷多个时，目标函数通平移直y=-x+，由图象可知当直线* I.y=-」x+，经过点b bz最大, 「k A,57]• •• -m=-,20故选C.目标函数Z=mx+y，取得最大值的最优解有无数个知取得最优解必在边界上，目标函数的截距取得最大值，故最大值应在左上方边界AC上取到，即mx+y=0应与直线AC平行；进而计算可得m的值.本题考查线性规划的应用，目标函数的最优解有无数多个，处理方法一般是：①将目标函数的解析式进行变形，化成斜截式②分析Z与截距的关系，是符号相同，还是相反③根据分析结果，结合图形做出结论④根据斜率相等求出参数.10•解：满足约束条件（¥?如「2y?x > 0 y?3<0.因为z=mx+y在平面区域上取得最小值的最优解有无穷多个，所以m=.只有过点（0, 0）时，z=mx+y有最小值0. 故选B.先有z=mx+y在平面区域fv?2x _0 上取得最小值的2y?x > 0Lx + y?3<0.最优解有无穷多个找出m=.再把对应的平面区域画出,2可.本题考查的知识点是简单线性规划的应用. 常与线性约束条件中的某一条线平行.11•解：作出不等式组f上0对应的平面区域x?y>0> 0* V > 0如图:由z=ax+by ( a> 0, b > 0) 得y=^x+, b b则直线的斜率k=- v 0,截距最大时，z也最大.A时，直线y=- x+，的截距最大，此时9 E由l(3x?>f?2 = O,解得卜二I■ 0 ty - I即A (1,1),此时z=a+b=2,的平面区域如图.•.1+1= （i+i）（・」）= 1 b JH>2；U 〒Z北“京当且仅当口，，即卩a=b=1时取等号，此时m=2,y=sin （mx+电）=sin （2x+i）的图象向右平移聖后的表达式为：y=sin[2 （史）+]=sin2x.J J * 6 Bl故选：B.作出不等式组对应的平面区域，利用目标函数的几何意义，确定z取最大值点的最优解，利用基本不等式的性质，利用数形结合即可得到结论.本题主要考查线性规划的应用，利用z的几何意义先求出最优解是解决本题的关键，利用基本不等式的解法和结合数形结合是解决本题的突破点.同时考查三角函数的图象的平移变换.。
运筹学基本概念➢线性规划问题的基与解LP： max(min)z=CX （1-1）s.t AX=b （1-2）X>=0 （1-3）设A施m*n矩阵，且A的秩为m，则有●可行解：满足上述约束条件（1-2）、（1-3）的向量X称为可行解。
●最优解：满足式（1-1）的可行解称为最优解●基：A中任何一组m个线性无关的列向量构成的子矩阵B，称为该问题的一个基，即B为A的m*m非奇异子矩阵。
●基向量：基B中的一列即为B的一个基向量。
基B中公寓m个基向量●非基向量：矩阵A中基B之外的一列即为B的一个非基向量。
A中共有n-m个非基向量。
●基变量：与基B的基向量相应的变量恒伟B的基变量，基变量共有m个。
●非基变量：与基B非基向量相应的变量称为B的非基变量，非基变量共有n-m个。
●基本解：对于基B，令所有非基变量为零，求得满足式（1-2）的解，称为B对应的基本解。
●基本可行解：满足式（1-3）的基本解称为基本可行解，其对应的基称为可行基。
●基本最优解：满足式（1-1）的基本可行解称为基本最优解，其对应的基称为最优基。
●退化的基本解：若基本解中有基变量为零这，则称之为退化的基本解。
类似地，有退化的基本可行解和退化的基本最优解。
➢几何意义上的几个基本概念●凸集：设S是n维空间的一个点集，若任意两点X（1）、X(2) ∈S的所连线段上的一切点αX（1）+（1-α）X(2)，（0<=α<=1），则称S为凸集。
●凸组合：设X（1）、X(2)……X（K）,为n维空间中的k个点。
则X=μ1X（1）+μ2X(2)+ μkX（K）（0<=μi<=1，i=1,2……k,且μ1+……μk=1）称为X（1）、X(2)……X（K）的凸组合。
●极点：S是凸集，X∈S，若X不能用S中相异的两点X（1）、X(2)线性表示为：X=αX（1）+（1-α）X(2)，α∈（0,1），则称X为S的极点或定点。
即极点不能成为任何线段的内点。
线性规划的定义及解题方法线性规划是一种数学建模技术，旨在解决在约束条件下，寻求最优解的问题。
它的实际应用十分广泛，例如管理学、经济学、物流学等领域。
线性规划可以分为单目标和多目标两种，但其中比较常见的是单目标线性规划。
本文将从线性规划的定义、模型建立、求解方法等方面阐述其原理与应用。
一、线性规划的定义线性规划的定义是：在有限约束条件下，目标函数为线性的最优化问题。
它通过数学模型的建立，将涉及到的变量、约束条件与目标函数转化为线性等式或不等式的形式，从而寻找最优解。
通常，线性规划的目标是最大化或最小化某个变量，可以用以下的形式去表示：$$Z=C_1X_1+C_2X_2+……+C_nX_n $$其中，$Z$为目标函数值，$X_1, X_2,……,X_n$为待求变量，$C_1, C_2,……,C_n$为相应的系数。
在线性规划中，会涉及到许多变量，这些变量需要受到一些限制。
这些限制可以用不等式或等式来表示，这些方程式被称为约束条件。
例如：$$A_1X_1+A_2X_2+……+A_nX_n≤B$$$$X_i≥0, i=1,2,……, n $$这两个方程就代表了一些约束条件，例如目标函数系数的和不能超过某个值，若$X_i$为生产的产品数量，则需保证产量不能小于零等。
这些约束条件用于限制变量的取值范围，而目标函数则用于求解最优解。
二、线性规划的模型建立在建立线性规划模型时，需要考虑几个要素：1. 决策变量：它是模型求解的关键。
决策变量是指在模型中未知的数量，也就是需要我们寻找最优解的那些变量。
2. 目标函数：确定目标函数，既要知道最大化还是最小化，还要知道哪些变量是影响目标函数的。
3. 约束条件：约束条件通常是一组等式或不等式，代表问题的限制。
例如在一个工厂中最大的生产量、原材料的数量限制、人工的数量等等，这些都是约束条件。
4. 模型的参数：模型参数是指约束条件的系数和模型中的常数。
它们是从现实问题中提取出来的，由于模型的解法通常是数学的，因此需要具体的数值。
1、运筹学的主要内容包括：(D)A。
线性规划B。
非线性规划 C。
存贮论 D.以上都是2、下面是运筹学的实践案例的是：（D）A.丁谓修宫B。
田忌赛马C。
二战间,英国雷达站与防空系统的协调配合 D.以上都是3、规划论的内容不包括:（D）A.线性规划B.非线性规划C.动态规划 D。
网络分析4、关于运筹学的原意，下列说法不正确的是：BA．作业研究B．运作管理C．作战研究D．操作研究5、运筹学模型：BA．在任何条件下均有效 B.只有符合模型的简化条件时才有效C．可以解答管理部门提出的任何问题D．是定性决策的主要工具6、最早运用运筹学理论的是： AA.二次世界大战期间,英国军事部门将运筹学运用到军事战略部署B。
美国最早将运筹学运用到农业和人口规划问题上C。
二次世界大战后，英国政府将运筹学运用到政府制定计划D.50年代，运筹学运用到研究人口,能源,粮食，第三世界经济发展等问题上7、下列哪些不是运筹学的研究范围：DA。
库存控制 B.动态规划 C.排队论 D.系统设计8、对运筹学模型的下列说法,正确的是：BA．在任何条件下均有效 B．只有符合模型的简化条件时才有效 C．可以解答管理部门提出的任何问题 D．是定性决策的主要工具9、企业产品生产的资源消耗与可获利润如下表。
A该问题的线性规划数学模型中，决策变量有（）个：A。
二 B.四C。
六D。
三10、图解法通常用于求解有( ）个变量的线性规划问题。
BA。
1 B。
2 C。
4 D。
511、以下不属于运筹学求解目标的是：DA．最优解 B．次优解 C．满意解D．劣解12、线性规划问题的最优解( ）为可行解。
AA．一定 B．不一定 C．一定不 D．无法判断13、将线性规划问题转化为标准形式时，下列说法不正确的是:DＡ。
如为求z的最小值，需转化为求—z的最大值Ｂ。
如约束条件为≤，则要增加一个松驰变量Ｃ.如约束条件为≥，则要减去一个剩余变量Ｄ.如约束条件为＝，则要增加一个人工变量14、关于图解法，下列结论最正确的是:DA.线性规划的可行域为凸集。
线性规划问题的最优解引言线性规划是运筹学的一个基本分支，其应用极其广泛，其作用以为越来越多的人所重视。
线性规划主要就实际问题抽象成数学形式，即求一组变量的值，在满足一定的约束条件下，是某个目标达到最小或最大，而这些约束条件用可以用一组线性不等式或线性方程来表示。
而求得目标函数的最优解尤为重要，本文就线性规划问题的最优解求解方法作出阐述，并举出实例加以强化，同时也指出了线性规划问题应用于生产与运作管理的重要性。
1.线性规划问题的最优解探讨1.1线性规划问题的提出考虑下面的线性规划问题的标准型： 目标函数：CX Z =min (1)约束条件：⎩⎨⎧≥=0X b AX (2)其中，),,,(21n c c c C =,T n x x x X ),,,(21 =,T m b b b b ),,,(21 =,n m ij a A ⨯=)(阶矩阵。
设B 是A 中m 个线性无关的列向量构成的一个基，m m ij a B ⨯=)( 阶矩阵，这样将矩阵A 分成两个部分，即A=),(N B ,X=),(N B X X ,C=()N B C C ,,B X ,B C 为基B 对应的非基变量和系数，N X ,N X 为N 对应的非基变量和系数，这样将线性规划问题改写为：minZ ()N B C C ,=⎥⎦⎤⎢⎣⎡B B X X (3)约束条件：⎪⎩⎪⎨⎧≥=⎥⎦⎤⎢⎣⎡0),(NB N B X X bX X N B (4)经过矩阵变换，得出关于基B 的标准型如下：1min -=B C Z B +(N C -1-B C B N)N X (5)约束条件：⎩⎨⎧≥=+--0,11NB N B X X bB NX B X (6)T m b b b b B ),,,(''21'1 =-⎪⎪⎪⎪⎪⎭⎫⎝⎛=++++++-mnmm mm nm m n m m a a a a a a a a a N B2122212121111 将（5）（6）展开为：=Z min '1i mi i b c ∑=+∑+=nm j 1('1ij mi i j a c c ∑=-)j x (7)约束条件：i nm j j iji b x ax '1'=+∑+= ,m i ,,2,1 = (8)0≥j x ,n j ,,2,1 = (9)令 '10i mi i b c Z ∑== , =j σ'1ij mi i j a c c ∑=- ,n m m j ,,2,1 ++= ,称j σ为检验数。
1.2最优解判别准则准则一：若 T m b b b X )0,,0,,,,('2'1')1( = ，为对应于基B 的基本可行解，且对于一切的 n m m j ,,2,1 ++= ，j σ>0 ，则X 为线性规划问题的最优解。
证明：j σ>0 ，由（'7）式可知，对任意一组可行解Tn x x x X ),,,(21 =，∑==nj j j x c Z 1,均有 0Z Z >，但 )1(X 能使等式成立，即0Z Z = ，故 )1(X 为线性规划问题的最优解。
准则二：当j σ0≥,n m m j ,,2,1 ++= ，有某一个0=j σ，设1+=m j ,m i ,,2,1 = ,01'>+im a ，则该线性规划问题有第二个最优的基本可行解。
证明：构造一个行解 )2(X ，('8) 得：11''++-=m im i i x a b x m i ,,2,1 = θ=+1m x 0>θ 0=j x n m j ,,2 +=根据θ 原则θ=⎭⎬⎫⎩⎨⎧>=++≤≤0|min 1'1''1im im i m i a a b 1''+Lm L a b =+1m x θ 1''+=Lm L a b , 0=L x将 )2(X 带入原目标函数（4）得：',1i mLi i i b c Z ∑≠==+(1+m c -1'1+=∑im mi i a c +1'+Lm L a c ）1''+Lm La b由于 =+1m σ 1+m c -01'1=+=∑im mi i a c ，故：=Z ',1imLi i i bc ∑≠= + L L b c 'L mi i b c ===∑='10Z)2(X 也是最优的基本可行解。
推论：若 )1(X 和 )2(X 均为最优的基本可行解，)2()1()1(X X X αα-+= ,10≤≤α 均为最优可行解。
准则三：当 j σ≥0 ,n m m j ,,2,1 ++= ，有某一个 0=j σ ，对一切 m i ,,2,1 = ，则该线性规划有无穷多个最优解。
证明：构造一个新解 )3(X ，由 ('8)11''++-=m im i i x a b x m i ,,2,1 ==+1m x θ 0>θ0=j x n m j ,,2 +=由于 01'≤+im a ，0>θ ,故 0>i x ,m i ,,2,1 = 将)1(X 代入原目标函数（4）得：=Z ',1imLi i i bc ∑≠=+(1+m c -1'1+=∑im mi i a c ）θ由于：=+1m σ1+m c -01'1=+=∑im mi i a c故：=Z ',1imLi i i bc ∑≠=+0 , =θ '1i mi i b c ∑=当 ∞−→−θ时，)3(X 仍为可行解，得到无穷多可行解，而目标函数仍为 =Z =∑='1i mi i b c 0Z ，即)3(X 也是最优解。
以下举出一些实例，进一步说明线性规划最优解的具体求解方法：2. 线性规划最优解的问题举例2.1图解法求解线性规划问题例[]51：求解下面的线性规划问题：⎪⎪⎪⎩⎪⎪⎪⎨⎧=≥=-++=++-=--+-=.6,,2,1,0,20342,0574,0232,85max 6543654265416 j x x x x x x x x x x x x x x Z j （1）显然 ==T x x x X ),,,(621* T )0,0,0,20,0,0( 是该线性规划问题（1）的一个最优解。
因05'4'==c c ，及 {}==>=3,2,1,0:min 4'4''4i a a b i i i θ014'1'=a b ，{}==>=3,2,1,0:min 55'5''i a a b i i θ025'2'=a b ，可考虑如下线性规划问题：⎪⎪⎩⎪⎪⎨⎧=≥=+-=-++=.5,4,2,1,0074032max 54254154j x x x x x x x x x W j （2）易解得线性规划问题（2）的最优解为==T x x x x X ),,,(5421''T )0,0,0,0( ,0)(''=X W , 于是可得 ==T x x x X ),,,(621* T )0,0,0,20,0,0( 是该线性规划问题（1）的唯一最优解。
例[]72：求解下面的线性规划问题：6145624563456max 5204422252300,1,2,,6.j Z x x x x x x x x x x x x x x j ⎧=-⎪+--=⎪⎪++-=⎨⎪-++=⎪⎪≥=⎩ （1）显然 ==T x x x X ),,,(621* T )0,0,0,0,20,0( 是该线性规划问题（1）的一个最优解。
因05'4'==c c ，及 {}==>=3,2,1,0:min 4'4''4i a a b i i i θ014'1'=a b ，{}==>=3,2,1,0:min 55'5''i a a b i i θ025'2'=a b ，可考虑如下线性规划问题：⎪⎪⎩⎪⎪⎨⎧=≥=+-=-++=.5,4,3,1,00202max 54354154j x x x x x x x x x W j （2）易解得线性规划问题（2）有无界解，==T x x x x X ),,,(5431''T )1,2,3,0(是该问题的一个可行解 ,03)(''>=X W , 于是线性规划问题的最优解不唯一。
只要取T x x x X ),,,(621* =如下：1324560,3;25(42421)0;2,;0.x x s x s x s x s x ===-⨯+⨯≥===那么 'X 也是线性规划问题的最优解。
例如，分别取s=0.5、0.25时，则T )0,5.0,1,5.1,0,0(和T )0,25.0,5.0,75.0,5.12,0(以及=*X T )0,0,0,0,25,0(都是该线性规划问题（1）的最优解，其中，T )0,0,0,0,25,0(是一退化的基可行解，T )0,5.0,1,5.1,0,0(是一非退化的基可行解，而=T )0,25.0,5.0,75.0,5.12,0(()()10,0,1.5,1,0.5,00,25,0,0,0,02T T⎡⎤+⎣⎦是一可行解而不是基解。
例[]43：要将两种大小不同的钢板结成A,B,C 三种规格，每张钢板可同时截得三种规格的小钢板的块数乳下表所示：钢板类型 规格类型A 规格B 规格C 规格第一种钢板 2 1 1 第二种钢板 123今需 A , B , C 三种规格的成品分别为 15 ，18 ，27 块，问：各截取这两种钢板多少张可得所需三种规格成品，且使得所用钢板张数最少？解：需要截得第一种钢板X 张，第二种钢板Y 张，则⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≥≥+≥+≥+0027*******y x y x y x y x （*）作出可行区域图如下： 目标函数为y x z += ，经过可行区域内的整点且与原点最近的直线是12=+y x 。
它上面的整点有（0，12）、（1,11）、（2,10）、(3,9)、（4，8）、（5，7）、（6,6）、（7,5）、（8,4）、（9,3）、（10,2）、(11,1)、（12,0），若逐一讨论其是否在可行域内比较麻烦时，只需先判断点A （539,518）附近的整数点是否满足条件，若满足条件，则再试附近的整数点；若不满足条件，则不需要再判断下去。
