(简介)线性、对偶规划.ppt

第一章 线性规划与单纯形法 线性规划模型 线性规划的图解 可行域的性质 线性规划的基本概念 线性规划的几何意义 单纯形法 人工变量法 单纯形法的矩阵表示 线性规划的一般模式 LP的特征 : 一组有待决策的变量，一个线性的 目标函数，一组线性的约束条件。 目标函数：max(min)Z=c1x1+c2x2+c3x3+…+cnxn 约束条件：a11x1+a12x2+a13x3+…+a1nxn ≤(= ≥)b1 a21x1+a22x2+a23x3+…+a2nxn≤(= ≥)b2 … … … … am1x1+am2x2+am3x3+…+amnxn≤(= ≥)bm 非负性约束：x1≥0, x2 ≥0, …, xn ≥0 可行域是凸集。可行域有有限个顶点 最优值在可行域的某个顶点上达到 无穷多解的情形、无界解情形、无解情形 图解法：例1图示 等值线 z=70x1+120 x2 沿其法向量 n={70,120} 移至其极限 位置点H . Maxz =z(20,24) =4280 线性规划的标准型 和式： 向量式: 矩阵式: 标准型的特征 目标函数极大化 约束条件为等式 决策变量非负 非标准型转化为标准型 目标函数极小化转为极大化： minz =－max(－Z) （一个数的极小化等价于其相反数的极大化） 不等式约束的转化：∑aijxj≤bi 加入松弛变量 ∑aijxj ≥ bi 减去剩余变量 非正变量：即xk ≤0 则令x’k =－ xk 自由变量：即xk无约束，令xk= x’k－x”k 有界变量: 即xk ≥(≤)vk 则令x’k = (xk － vk) (－) 非标准型转化举例 minZ=x1+2x2-3x3 maxZ’=x’1－2x2+3(x’3－x”3) x1+x2+x3 ≤9 －x’1+x2+x’3－ x”3 + x4 =9 -x1-2x2+x3 ≥2 x’1－2x2+x’3 －x”3 – x5= 2 3x1+x2-3x3=5 － 3x’1+x2－3(x’3 － x”3 )=5 x1 ≤0 x2 ≥0 x3无约束 x’1 ≥ 0 x2 ≥0 x’3 ≥0 x”3 ≥0 x4 ≥0 x5 ≥0 基矩阵 基的概念：如前所述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中m?m阶非奇异子矩阵， 则称B 是LP的一个基，即B是A中m个线性 无关向量组。 基解、基可行解 不失一般性,设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,称为基解 。 基