《线性规划问题.ppt》由会员分享，可在线阅读，更多相关《线性规划问题.ppt（50页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第1章 线性规划与单纯形法本章要点：1。线性规划问题的数学模型；2。线性规划问题的基本理论；3。线性规划问题的求解。例1.1：美佳公司计划制造I，II两种家电产品。已知各制造一件时分别占用的设备A，B的台时、调试时间、调试工序及每天可用于这两种家电的能力、各售出一件时的获得情况，如表所示。问该公司应制造两种家电各多少件，使获取的利润为最大。项目III每天可用能力设备A（h）0515设备B（h）6224调试工序（h）115利润（元）21一、问题的提出1.1 线性规划问题与及其数学模型Max解：设x1和x2分别表示美佳公司制造家电I和II的数量。则该问题可用线性规划模型表示如下：1.1 线性规划问
2、题与及其数学模型1.1 线性规划问题与及其数学模型p例1.2 某工厂计划生产A、B、C三种产品，每吨利润分别为2万元、3万元、1万元；生产单位产品所需的工时及原材料如表所示。如果供应的原材料每天不超过3吨，每天所能利用的劳动力总工时是固定的，问如何制定日生产计划，使三种产品总利润最大？1/31/3A7/34/3原 材 料1/31/3工时（占总工时比例）CB每吨产品所需资源资源产品设每天生产A产品X1吨，B产品X2吨，C产品X3吨;则用数学语言可描述为：Max1.1 线性规划问题与及其数学模型p例1.3 某工地租赁机械甲和乙来安装A、B、C三种构件。已知这两种机械每天的安装能力如表所示。而工程任
3、务要求共安装250根A构件、300根B构件和700根C构件；又知机械甲每天租赁费为250元，机械乙每天租赁费为350元，试决定租赁机械甲和乙各多少天，才能使总租赁费最少？65A26机械乙108机械甲CB每天安装能力（根）机械构件1.1 线性规划问题与及其数学模型设租赁甲X1天，机械乙X2天，为满足A、B、C的安装要求;则用数学语言可描述为：Min1.1 线性规划问题与及其数学模型二、线性规划的数学模型共同特征：1）决策变量（向量）X2）约束条件（向量）AX=b3）线性目标函数Z=CX其中：C为价值系数（向量）A为约束条件系数矩阵1.1 线性规划问题与及其数学模型用数学语言可描述为：Max(Mi
4、n)1.1 线性规划问题与及其数学模型线性规划模型的结构目标函数：max，min约束条件：,=,变量符号：0,unr,0用矩阵描述为：1.1 线性规划问题与及其数学模型1.2 线性规划问题的求解p图解法：适用于个决策变量p鞍面法：1992年中国沈阳化工学院尚毅教授发明。p内点法：1984年美国籍印度数学家Karmarker（卡玛卡）发明p椭球法：1979年苏联数学家Khachiyan（哈奇扬）发明p单纯形法：1952年美国斯坦福大学教授Dantzig（丹茨格）发明，可以解决1.5万至2万个决策变量。1.2 线性规划的求解一、图解法max z=x1+3x2s.t.x1+x26-x1+2x28x1
5、 0,x20可行域目标函数等值线最优解64-860 x1x21.2 线性规划的求解p图解法求解步骤1）建立直角坐标系；2）根据线性规划问题的约束条件和非负条件画出可行域；3）作出目标函数等值线Z=c（c为一常数），并使其平移求得最优解。1.2 线性规划的求解p线性规划的解的特殊情况n唯一解X1X2X1X222X1X222n无界解（少了约束条件）例 Max z=x1+2x2 st x1=1 x2=2n无穷解（头与身平行）例 Max z=x1+x2 st 2x1+2x2=0,x2=01.2 线性规划的求解n无可行解（有矛盾约束）例Min Z=x1-x2 st x1=2 x1=1X1X222无可行解
6、域1.2 线性规划的求解二、线性规划问题的标准型1。线性规划问题的标准型统一规定：1）目标函数取极大化类型（也可以是极小化类型）；2）所有约束条件用等式来表示；3）所有决策变量取非负值；4）每一约束条件的右端常数为非负值。1.2 线性规划的求解2。线性规划问题的标准型为：Max1.2 线性规划的求解p标准型缩写式为:Max(i=1,2,m)1.2 线性规划的求解p向量形式为:Max Z=CX(j=1,2,n)线性规划的标准形式矩阵形式为：目标函数：max约束条件：=变量符号：01.2 线性规划的求解1.2 线性规划的求解l线性规划问题的标准化1)目标函数的标准化：对于最小化问题MIN Z，化为
7、最大化问题为：MAX Z=-Z=-CXp如不等号为“”，则左边减去一非负变量变为等式。p如不等号为“”，则左边加上一非负变量变为等式。p若右端为负，则左右两同乘（-1）即可。p若某个变量 无约束，则引入两个非负变量 ，可令2)约束条件的标准化1.2 线性规划的求解例1-4MaxMax1.2 线性规划的求解例1-5 将下面的线性规划问题化成标准型MinMin1.2 线性规划的求解MinMax1.2 线性规划的求解三、线性规划的解Max(i=1,2,m)(1)(2)(3)1。l可行解：满足上面模型中的（2）和（3）式的解X；l最优解：满足上面模型中的（1）的可行解X；l基（矩阵）：若B是A中的mm
8、阶非奇异子式（即|B|0），则B是线性规划问题的一个基（矩阵）；可设B=P1，P2，.，Pm则Pj为基向量，与Pj对应的变量xj为基（本）变量。1.2 线性规划的求解三、线性规划的解Max(i=1,2,m)(1)(2)(3)1。l非基（本）变量：X中除基（本）变量外的变量；在方程AX=b中，令非基变量的值为0，求得基本变量的值，这样得到的一组解X0称为方程AX=b关于基B的基本解。一般m0=k l确定换出基变量:4)继续迭代(旋转变换)1.2 线性规划的求解五、单纯形法3。表格单纯法（单纯形表）例1-9CBCj23100ixBbx1x2x3x4x50 x411/3 1/3 1/3 101/(1
9、/3)0 x531/3 4/3 7/3 013/(4/3)-Z023100CBCj23100ixBbx1x2x3x4x50 x41/4 1/4 0-1/4 1-1/413x29/4 1/4 17/403/4 9-Z020-17/40-9/4Max j|j0=k 1.2 线性规划的求解五、单纯形法CBCj23100ixBbx1x2x3x4x52x1110-11-13x2201201-Z-800-30-1j0l无界解判定：若非基变量k0，且 ，则该线性规划问题的解无界。1.2 线性规划的求解五、单纯形法p一般线性规划问题的处理没有立即出现初始基本可行解，人工加入变量（即人工变量）后，变换后的问题有
10、初始基本可行解，但两方程组不等价，当且仅当加入的变量可以优化为0时，变换前后方程组才等价。例1-9 用单纯形法解线性规划问题Max加入人工变量化标准形式如下:1）大M法（M为足够大的数）p目标函数中处理：把要优化为0的人工变量在目标函数中减去M乘以人工变量，再用单纯形法求解，可知人工变量会很快优化为0，否则目标函数无法增加，甚至无法达到目标最优解（即目标值最大）。当人工变量为0时，加入人工变量的前后方程是等价的，也即找到原问题的初始基本可行解。然后继续用单纯法迭代即对原问题完成求解。p如果得不到初始基本可行解，则原问题无解1）大M法Max1）大M法i66 0 4 0 3 -3 11-2 1-1
11、0-1 1 033 021 1-1 0 x4x2x700-M-Z0 6M-304M+103M-4M01-1xBb x1 x2 x3 x4 x5 x6 x7CBCj-3 0 1 0 0 -M -M41 1 1 1 0 0 01-2 1-1 0 -1 1 090 3 1 0 0 0 1x4x6x70-M-M-Z-2M-34M 10-M004131）大M法（续）xB b x1 x2 x3 x4 x5 x6 x7CBCj -30 1 0 0 -M -Mx4x2x100-3-Z-3/2-9/20 00 0 1-1/2 1/2-1/2 1 10 2/3 0 1/2-1/2 1/63 011/3 0 0 0
12、 1/33 00303/2-M-3/2-M+1/2i-93/23/2 3/2 0 1 0 3/4-3/4 1/45/2-1/2 1 0 0 -1/41/4 1/4 0 0 0 0 1 -1/2 1/2 -1/2x4x2x3001-Z000-3/4-M+3/4-M-1/42)二阶段法p第一阶段：目标函数处理成人工变量求和的最小化（Min），用单纯形法求解，直至优化到目标函数值为，即得到初始基本可行解p第二阶段：利用上阶段的初始基本可行解，目标函数换回原来的目标函数，再继续求解直至完成p如果得不到初始基本可行解，则原问题无解例1-9 用两阶段法求解Max加入人工变量：例1-9 用两阶段法求解p第一
13、阶段目标函数为：Min标准化为:Maxp第二阶段目标函数为：Max例1-9 用两阶段法求解：第一阶段xBb x1 x2 x3 x4 x5 x6CBiCj 0000-1-11051181010243201x5x6-1-1-W20754100010/810/25/45/81/81/811/8015/2 3/415/4 11/4 0-1/41x4x60-1-W 15/23/415/411/4 0-5/4010221/5111/150-1/15 4/1513/501/30 12/15-1/300 x40 x2-W00000-11例1-9 用两阶段法求解xBb x1 x2 x3 x4CBi Cj 5 3 2 4x41 3/5 0 1/30 1x22 1/5 1 11/15 043-Z-1020-1/3 05/3105/3 1 0 1/18 5/35/3 0 1 13/18 -1/3x1x253-Z-40/3 0 0 -4/9-10/3