线性规划的标准型和基本概念

《线性规划的标准型和基本概念》由会员分享，可在线阅读，更多相关《线性规划的标准型和基本概念（46页珍藏版）》请在金锄头文库上搜索。

1、线性规划的标准型和基本概念p 线性规划问题及其数学模型 p 线性规划的图解法 p 线性规划的标准形式 p 标准型线性规划的解的概念 p 线性规划的基本理论1n 问题的提出：在生产管理的经营活动中，通常需要对“有限的资源”寻求“最佳”的利用或分配方式。l 有限资源：劳动力、原材料、设备或资金等 l 最佳：有一个标准或目标，使利润达到最大或成本达到最小。有限资源的合理配置有两类问题l 如何合理的使用有限的资源，使生产经营的效益达到最大；l 在生产或经营的任务确定的条件下，合理的组织生产，安排经 营活动，使所消耗的资源数最少。 p线性规划问题及其数学模型2例，某制药厂生产甲、乙两种药品，生产这两种药

2、品要消耗某种维生素。生产每吨药品所需要的维生素量，所占用的设备时间，以及该厂每周可提供的资源总量如下表所示：每吨产品的消耗 每周资源总量 甲乙 维生素（公斤） 3020160 设备（台班） 5115已知该厂生产每吨甲、乙药品的利润分别为5万元和2万元。但根据市场需求调查的结果，甲药品每周的产量不应超过4吨。问该厂应如何安排两种药品的产量才能使每周获得的利润最大？3定义x1为生产甲种药品的计划产量数，x2为生产乙种药品的计划产量数。 数学模型为s.t. （subject to)(such that) 每吨产品的消耗 每周资源总量 甲乙 维生素（公斤） 3020160 设备（台班） 5115 单位

3、利润（万元） 54例2 靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天 500万m3，在两个工厂之间有一条流量为200万m3的支流。两化工厂每 天排放某种有害物质的工业污水分别为2万m3和1.4万m3。从第一化工 厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。环保 要求河流中工业污水含量不能大于0.2%。两化工厂处理工业污水的成 本分别为1000元/万m3和800元/万m3。现在要问在满足环保要求的条 件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的费 用最小 工厂1工厂2200万m3500万m35决策变量：x1、x2分别代表工厂1和工厂2处理 污水的数量(万m3

4、)。 则目标函数：min z=1000x1+800x2 约束条件： 第一段河流（工厂1工厂2之间）：(2x1)/500 0.2% 第二段河流： 0.8(2x1) +(1.4x2)/7000.2% 此外有： x12； x21.4 化简有：min z=1000x1+800x2x1 10.8x1 + x2 1.6x1 2x21.4x1、x20 称之为上述问题的数学模型。6例，某铁器加工厂要制作100套钢架，每套要用长为2.9米，2.1米和1.5米的圆钢各一根。已知原料长为7.4米，问应如何下料，可使材料最省？ 分析：在长度确定的原料上截取三种不同规格的圆钢，可以归纳出8种不同的下料方案：圆钢（米）2

5、91201010021002211301531203104料头（米）00.10.20.30.80.91.1.4问题归纳为如何混合使用这8种不同的下料方案，来制造100套钢架，且要使剩余的料头总长为最短。7设xj表示用第j种下料方案下料的原料根数，j=1,28,数学模型s.t. 这是一个下料问题，是在生产任务确定的条件下，合理的组织生产，使所消耗的资源数最少的数学规划问题。 满足一组约束条件的同时，寻求变量x1至x8的值,使目标函数取得最小值。 圆钢（米）291201010021002211301531203104料头（米）00.10.20.30.80.91.11.4且为整数8n 线性规划的一般

6、数学模型线性规划模型的特征：（1）用一组决策变量x1，x2，xn表示某一方案，且在一般情况下，变量的取值是非负的。（2）有一个目标函数，这个目标函数可表示为这组变量的线性函数。（3）存在若干个约束条件，约束条件用决策变量的线性等式或线性不等式来表达。（4）要求目标函数实现极大化（max）或极小化（min）。 满足上述4个特征的规划问题称为线性规划问题9线性规划的模型的一般形式: 目标函数满足约束条件通常称 为决策变量， 为价值系数，为消耗系数, 为资源限制系数。 10p 线性规划的图解法 适用于求解两个变量的线性规划问题n 图解法的基本步骤例4,利用例1说明图解法的主要步骤，例1的数学模型为

7、s.t. 11O51015x1x1=4x25101AB( 2, 5)CZ5x1+x2=1530x1+20x2=1605x1+2x2=512线性规划图解法的基本步骤：（1）建立以x1,x2为坐标轴的直角坐标系，画出线性规划问题的可行域,（2）求目标函数 Z=C1x1+C2x2 的梯度Z =（c1,c2）,（3）任取等值线 C1x1+C2x2=Z0, 沿梯度Z正方向平移,（若是极小化问题，则沿负梯度方向-Z平移），求等直线将离未离可行域时与可行域的交点。（4）若交点存在，则该点坐标就是最优解 。13n 图解法的几种可能结果(1）有唯一最优解，如例1。（2）有无穷多最优解如例1中的目标函数设为 ma

8、xZ=10x1+2x2则目标函数等值线10x1+2x2=Z 与第二约束 5x1+x215的边界线平行。将等值线沿梯度Z =（10，2）正方向平移至B点时与可行域OABC的整条边界线AB重合。这表明线段AB上的每一点都使目标函数取得同样的最大值，因而都是最优解。14O51015x1x1=4x25101AB（2，5）CZ5x1+x2=1530x1+20x2=16010x1+2x2=515例5，试用图解法求解下列线性规划问题st.（3） 无界解（或称无最优解）无界解是指线性规划问题的最优解无界。若是极大化问题，则可使目标函数值Z+,极小化问题 则可使目标函数值Z-， 有无界解的线性规划问题的可行域是

9、无界区域，但反之则不必然。16-1 O24x1x224-Z=(3,2)-2x1+x2=2x1-3x2=3-1 O3317（4）无可行解某些线性规划问题的可行域是空集，既不存在满足所有约束条件的点，这时问题无可行解，当然更谈不上最优解了。在实际中出现这种情况可以认为资源条件无法满足人们的要求，既不存在可行方案。 18例6 max z=x1+2x2x1 + 2x21x1 + x22x1、x20无可行解。1112OA19以上几种情况的图示如下：可行域有界唯一最优解 可行域有界多个最优解20可行域无界唯一最优解可行域无界无穷多最 优解21可行域无界目标函数无界 可行域为空集无可行解221. 有最优解唯

10、一最优解 无穷多最优解2. 最优解无界3. 无可行解23直观结论：（1）可行域可以是个凸多边形，可能无界，也可能为 空；（2）若线性规划问题的最优解存在，它一定可以在 可行域的某一个顶点上得到；（3）若在两个顶点上同时得到最优解，则该两点连 线上的所有点都是最优解，即LP有无穷多最优解；（4）若可行域非空有界，则一定有最优解。24n 标准线性规划模型线性规划问题的标准形式：s.t 其中（2）（3）p线性规划的标准形式（1）25l紧凑格式：s.t.l向量格式：s.t.其中 称为价值向量， 为决策变量向量， 为决策变量xj所对应的消耗系数向量， 为资源向量。26l矩阵格式：其中 为mn阶矩阵为价值

11、向量，为决策变量向量，为资源向量。27n非标准形式线性规划问题的标准化（1）极大化与极小化 ：若 ，令 ，则有原目标函数 。(2) 线性不等式与线性等式：其中 为非负松弛变量，其中 为非负剩余变量。 28(4) 非负变量与符号不受限制的变量若 xi的符号不受限制，则可引进非负变量xi1,xi2，令xi = xi1-xi2，这样就可以使线性规划里所有的变量都转化为有非负限 制的变量。 例7，将下述线性规划问题化为标准型解：令 ,其中符号不受限制符号不受限制(3) 右端项为负约束两端乘以（1）29O51015x1x25101AB( 2, 5)CZ5x1+x2=1530x1+20x2=1605x1+

12、2x2=530考虑一个标准的线性规划问题： s.t 其中为n维行向量，是n维列向量，是m维列向量，是mn阶矩阵，假定满足mn，且()=m，p标准型线性规划的解的概念31线性规划问题解的概念：(1) 可行解。满足约束条件的解 可行解集 称为线性规划问题的可行域。(2) 最优解。使目标函数达到最优值的的可行解称为最优解，最优解常用 表示。(3) 基。若是中mm阶非奇异矩阵，即|0，则称是线性规划问题的一个基。 32基向量，基变量 若是线性规划问题的一个基，那么一定是由 m个线性无关的列向量组成，不失一般性，可设称 为基向量，与基向量 相对应的变量 称为基变量。基的个数 一个线性规划的基通常不是唯一

13、的，但是基的个数也不会超过 个。一旦线性规划的基确定了，那么相应的基向量、基变量和非基变量也就确定了。33(4) 基本解。设B是线性规划的一个基，若令n-m个非基变量等于0，则所得的方程组=b的解称为线性规划问题的一个基本解（简称基解）。 有一个基就可以求得一个基本解。 由基的有限性可知，基本解的个数也不会超过 个。 由于基本解中的非零分量可能是负数，所以基本解不一定是可行的。(5) 基本可行解。满足非负条件的基本解称为基本可行解（简称基可行解）。与基本可行解对应的基称为可行基。 基本可行解的非零向量的个数小于等于m，并且都是非负的。 由于基本可行解的数目一般少于基本解的数目，因此可行基的数目

14、也要少于基的数目。 当基本可行解中有一个或多个基变量是取零值时，称此解为退化的基本可行解。 34线性规划问题各种解的关系可用文氏图表示，可行解基本解基本 可行 解35例8、求下列约束方程所对应的线性规划的所有基本解，基本可行解。s.t 解：化为标准形式 为24阶矩阵。 且R(A)=2,所以该线性规划基的个数 =6个 取 , 为基变量，若令非基变量 ， 约束方程组为 可得对应的基本解 是一个基本可行解。 36按相同步骤，可求得线性规划其他4个基：对应基本解是一个基本可行解。 对应基本解是一个基本可行解。 对应基本解不是一个基本可行解。 对应基本解是一个基本可行解。 37若利用图解法画出线性规划的可行域，如图，CDOBA44838p 线性规划的基本理论 由图解法的步骤，可以从几何的角度得出以下两个 结论：（1）线性规划问题的可行域是一个有界或无界的凸多边形，其顶点个数是有限个。（2）若线性规划问题有最优解，那么最优解一定可在可行域的某个顶点上找到。39引理1：若线性规划问题存在可行域，则其可行域是一个凸集。 证明：为了证明满足=，0的所有点（可行解）组成的几何体 是凸集，只要证明中任意两点