《运筹与优化--线性规划》由会员分享，可在线阅读，更多相关《运筹与优化--线性规划（70页珍藏版）》请在金锄头文库上搜索。
1、运筹与优化,第一章 线性规划与单纯形法,福州大学体育馆,第一章 线性规划与单纯形法,线性规划模型 线性规划的图解 可行域的性质 线性规划的基本概念 线性规划的几何意义 单纯形法 人工变量法 单纯形法的矩阵表示,第一节线性规划及其数学模型 1.1 LP的数学模型,例题1(生产计划问题) : 某厂生产两种产品， 需要三种资源，已知各产品的利润、各资源 的限量和各产品的资源消耗系数如下表：,例题1建模,问题：如何安排生产计划，使得获利最多？步骤： 1、确定决策变量：设生产A产品X1kg， B产品 X2kg 2、确定目标函数：maxZ=70X1+120X2 3、确定约束条件：人力约束 9X1+4X23
2、60 设备约束 4X1+5X2 200 原料约束 3X1+10X2300 非负约束 X10 X20,例题2套裁下料问题,例、某工厂要做100套钢架，每套用长2.9m,2.1m, 1.5m的圆钢各一根。已知原料每根长7.4m，问： 应如何下料，可使所用原料最省？最简单的做法:1根原料截割成2.9m、2.1m、1.5m各一根,100根原料 截割成100套钢架,每根剩余料头0.9m,共有料头90m.设计下列 8 种下料方案,例题2建模,令 xi(i=1,2,8)表示第 i 种方案下料的 原材料根数,这样我们建立如下的数学模型。目标函数：Min Z= x1+x2+x3+x4+x5+x6+x7+x8约束
3、条件： s.t. x1+ 2x2 + x4 + x6 100 2x3 +2x4 + x5 + x6 +3x7 100 3x1+ x2+2x3 +3x5 + x6 +4x8 100 x1, x2, x3, x4, x5, x6, x7, x8 0,例题3 人力资源分配的问题,例3某商场是个中型的百货商场，它对售货员的需求 经过统计分析如下表：为了保证售货人员充分休息， 售货人员每周工作 5天，休息两天，并要求休息的 两天是连续的。问应该如何安排售货人员的作息， 既满足工作需要，又使配备的售货人员的人数最少？,例题3建模,解：设 xi ( i = 1 - 7)表示星期一至星期日开始 休息的人数,这
4、样我们建立如下的数学模型。 目标函数： Min(x1 + x2 + x3 + x4 + x5 + x6 + x7) 约束条件： s.t.x1 + x2 + x3 + x4 + x5 28 x2 + x3 + x4 + x5 + x6 15 x3 + x4 + x5 + x6 + x7 24 x4 + x5 + x6 + x7 + x1 25 x5 + x6 + x7 + x1 + x2 19 x6 + x7 + x1 + x2 + x3 31 x7 + x1 + x2 + x3 + x4 28 x1 ,x2 ,x3 ,x4 ,x5 ,x6 ,x7 0,归纳：线性规划的一般模式,LP(linea
5、r programming)是在有限资源的条件 下，合理分配和利用资源，以期取得最佳的经济效益的优化方法。 LP的特征 : 一组有待决策的变量，一个线性的目标函数，一组线性的约束条件。目标函数：max(min)Z=c1x1+c2x2+c3x3+cnxn约束条件：a11x1+a12x2+a13x3+a1nxn (= )b1 a21x1+a22x2+a23x3+a2nxn(= )b2 am1x1+am2x2+am3x3+amnxn(= )bm非负性约束：x10, x2 0, , xn 0,1.2线性规划图解法,现对第一节的例题1进行图解： Z=70X1+120X2 X2 = (70/120)X1
6、-Z/120是一条直线，以Z为参数的一族等值线。 9X1+4X2 360 X2 360/4 - 9X2/4 是直线 X2= 360/4 - 9X1/4 下方的半平面。 所有半平面的交集称之为可行域，可行域内的任意一点，就是满足所有约束条件的解，称之为可行解(可行点)。,例1图示,等值线 z=70x1+120 x2 沿其法向量 n=70,120移至其极限位置点H . Maxz=z(20,24)=4280,90 80 60 40 20,0 20 40 60 80 100,x1,x2,9x1+4x2 360,4x1+5x2 200,3x1+10x2 300,A,B,C,D,E,F,G,H,I,Z=7
7、0x1+120x2,概 念,1.可行解：满足所有约束条件的解。2.可行域：满足所有约束条件的解的集合， 称为可行域。即可行解的集合。3. 最优解：使目标函数达到最优值的可行解.4.基解：约束条件的交点称为基解(几何直观).5.基可行解：基解当中的可行解(几何上为顶点).6.凸集：集合内任意两点的连线上的点均属 这个集合。如：实心球、三角形.,例2图解,max z=x1+3x2 s.t. x1+ x26-x1+2x28x1 0, x20 等值线沿方向 n=1,3移动,可行域,目标函数等值线,唯一最优解(4/3,14/3),6,4,-8,6,0,x1,x2,例3图解,max z=x1+x2 s.t
8、. x1+ x26-x1+2x28x1 0, x20 等值线沿方向 n=1,1移动,可行域,目标函数等值线,无穷多最优解,6,4,-8,6,0,x1,x2,例4图解,max z=2x1+2x2s.t. x1- x21-x1+2x20x1 0, x20等值线沿方向n=1,1移动,有maxz=;沿-n移动,有minz=z(1,0)=2,可行域,目标函数等值线,无界解,4,2,1,4,0,x1,x2,2,1,例5图解,min z=x1+3x2s.t. x1+x2 1 x1+2x2 4x1 0, x20可行域S=,无可行解.,4,1,0,x1,x2,1,2,结 论,可行域是凸集可行域有有限个顶点最优值
9、在可行域的某个顶点上达到无穷多解的情形无界解情形无解情形,凸集,凸集,不是凸集,顶点,1.3 线性规划的标准型,和式： 向量式: 矩阵式:,其中：价值向量 决策向量 资源向量 系数矩阵,标准型的特征,目标函数极大化约束条件为等式决策变量非负,其中： 价值向量 决策向量 资源向量 系数矩阵,非标准型转化为标准型,目标函数极小化转为极大化： minz =max(Z) （一个数的极小化等价于其相反数的极大化）不等式约束的转化： aijxjbi 加入松弛变量 aijxj bi 减去剩余变量非正变量：即xk 0 则令xk = xk 自由变量：即xk无约束，令xk= xkx”k有界变量: 即xk ()vk
10、 则令xk = (xk vk) (),非标准型转化举例之一,maxZ=70X1+120X2 maxZ=70X1+120X2 9X1+4X2360 9X1+4X2+X3=360 4X1+5X2 200 4X1+5X2 +x4=200 3X1+10X2 300 3X1+10X2+x5 =300 X10 X20 Xj0 j=1,2,5,非标准型转化举例之二,minZ=x1+2x2-3x3 maxZ=x12x2+3(x3x”3) x1+x2+x3 9 x1+x2+x3 x”3 + x4 =9 -x1-2x2+x3 2 x12x2+x3 x”3 x5= 2 3x1+x2-3x3=5 3x1+x23(x3
11、 x”3 )=5 x1 0 x2 0 x3无约束 x1 0 x2 0 x3 0 x”3 0 x4 0 x5 0,1.4 线性规划解的概念基矩阵,基的概念：如前所述LP标准型 和式：maxZ = cjxj , aijxj=bj , xj 0 , j = 1 n 矩阵式：maxZ = CX , s.t. AX = b, X 0 . 约束方程的系数矩阵A的秩为m，且m n . 设A=(B,N)，B是A中mm阶非奇异子矩阵， 则称B 是LP的一个基，即B是A中m个线性 无关向量组。,n,j=1,n,j=1,基解、基可行解,不失一般性,设B是A的前m列，即 B = ( p1 , p2, , pm） 其相对应的变量XB=(x1, x2, , xm)T,称为基变量；其余变量XN =(xm+1 ,xn)T称为非基变量。B中Pj称为基向量. 令所有非基变量等于零,则 X=（x1 ,x2 ,xm ,0 ,0)T,称为基解 。基可行解：基解可正可负，负则不可行（违背非负性 约束条件），称满足所有约束条件的基解为基可行解。退化的基可行解：若某个基变量取值为零，则称之为 退化的基可行解。基最优解：使目标函数达到最优值的基可行解。基解的数目：最多 =n!/m!(n-m)!,
