《ch1单纯形法课件》由会员分享，可在线阅读，更多相关《ch1单纯形法课件（58页珍藏版）》请在金锄头文库上搜索。
1、第二节 单纯形法是求解线性规划的主要算法，1947G.B.Danzig）提出。 尽管在其后的几十年中，又有一些算法问世，但单纯形法以其简单实用的特色始终保持着绝对的“市场”占有率。1ch1单纯形法PPT课件1.线性规划的标准型 用单纯形法求解线性规划的前提是先将模型化为标准型表示为 标准型的特征：Max型、等式约束、非负约束一、单纯形法的预备知识2ch1单纯形法PPT课件非标准形式如何化为标准1) MinMin型化为型化为MaxMax型型 加负号 因为，求一个函数的极小点，等价于求该函数的负函数的极大点。注意： Min型化为Max型求解后，最优解不变，但最优值差负号。 3ch1单纯形法PPT课
2、件.约束方程的转换：由不等式转换为等式。约束方程的转换：由不等式转换为等式。称为松弛变量称为松弛变量称为剩余变量称为剩余变量4ch1单纯形法PPT课件 例1 某工厂可生产甲、乙两种产品，需消耗煤、电、油三种资源。现将有关数据列表如下： 试拟订使总收入最大的生产方案。资源单耗 产品资源甲 乙资源限量煤电油9 44 5 3 10360200300单位产品价格 7 122) 不等式约束化为等式约束不等式约束化为等式约束5ch1单纯形法PPT课件2) 不等式约束化为等式约束分析：以例1中煤的约束为例之所以“不等”是因为左右两边有一个差额，称为“松弛量”，若在左边加上这个松弛量，则化为等式。而这个松弛量
3、也是变量，记为X3 ，则有X3称为松弛变量。问题：它的实际意义是什么？ 煤资源的“剩余”。6ch1单纯形法PPT课件练习：请将例1的约束化为标准型解：增加松弛变量则约束化为易见，增加的松弛变量的系数恰构成一个单位阵I。7ch1单纯形法PPT课件一般地，记松弛变量的向量为 Xs，则问题：松弛变量在目标中的系数为何？ 0。 3) 当模型中有某变量 xk 没有非负要求，称为自由变量, 则可令 化为标准型。8ch1单纯形法PPT课件p45 1.2(1)作业：作业：9ch1单纯形法PPT课件2.基本概念（1）可行解与最优解直观上，可行解是可行域中的点，是一个可行的方案； 最优解是可行域的角点，是一个最优
4、的方案。10ch1单纯形法PPT课件（2）基矩阵与基变量基矩阵(简称基)：由系数阵A中的线性无关的列线性无关的列组成的m阶子矩阵阶子矩阵，记为B；其余列构成非基矩阵，记为N。基向量：基B中的列；其余的列称非基向量。基变量：与基向量Pj对应的决策变量xj，记其组成的 向量为XB；与非基向量对应的变量称非基变 量，记其组成的向量为XN。基矩阵的特点:1. 基B是可逆矩阵,即2. 基B是一个 方阵r（B）=m或者A= ( B N )11ch1单纯形法PPT课件 6个。一般地，mn 阶矩阵A中基的个数最多有多少个？问题：本例的A中一共有几个基？12ch1单纯形法PPT课件【例例4】线性规划线性规划 求
5、所有基矩阵求所有基矩阵。 【解解】约束方程的系数矩阵为约束方程的系数矩阵为25矩阵矩阵 容易看出容易看出r(A)=2，2阶阶子矩子矩阵阵有有C52=10个，个，其中第其中第1列与第列与第3列构成的列构成的2阶阶矩矩阵阵不是一个基，不是一个基，基矩基矩阵阵只有只有9个，即个，即13ch1单纯形法PPT课件（3）基本解与基本可行解可见：一个基本解是由一个基决定的。注意：基本解仅是资源约束的解，并未要求其非负，因此其未必可行。称非负的基本解为基本可行解基本可行解（简称基可行解）。14ch1单纯形法PPT课件例3中求相应于基B1和B2的基本解，它们是否基本可行解？15ch1单纯形法PPT课件对对来说，
6、来说，x1,x2是基变量，是基变量，x3,x4，x5是非基变是非基变量，令量，令x3=x4=x5=0，因因|B1|，由克莱姆法则知，由克莱姆法则知，x1、x2有唯一解有唯一解x12/5,x2=1则则 基本解为基本解为在例4中,Xi0,是基本可行解16ch1单纯形法PPT课件在在 中中x10且且aik（i=1，2,m）则则线线性性规规划具有无界解划具有无界解退化基本可行解的判断退化基本可行解的判断:存在某个基变量为零的基本可行解。存在某个基变量为零的基本可行解。无无可可行行解解的的判判断断：(1)当当用用大大M单单纯纯形形法法计计算算得得到到最最优优解解并并且且存在存在Ri0时，则表明原线性规划
7、无可行解。时，则表明原线性规划无可行解。(2) 当第一阶段的最优值当第一阶段的最优值w0时，则原问题无可行解时，则原问题无可行解。53ch1单纯形法PPT课件建建立立模模型型个个 数数取取 值值右右 端端 项项等式或等式或不等式不等式极大或极小极大或极小新加新加变量变量系数系数两两个个三个三个以上以上xj0xj无无约束约束xj 0 bi 0bi 0=maxZminZxs xa求求解解图图解解法法、单单纯纯形形法法单单纯纯形形法法不不处处理理令令xj = xj - xj xj 0xj 0令令 xj =- xj不不处处理理约束约束条件条件两端两端同乘同乘以以-1加加松松弛弛变变量量xs加加入入人人
8、工工变变量量xa减减去去xs加加入入xa不不处处理理令令z=- ZminZ=max z0-M54ch1单纯形法PPT课件对目标函数求max的线性规划问题，用单纯形法计算步骤的框图见图1-9。 55ch1单纯形法PPT课件作业作业:1.6(3),1.8用单纯形法求解下述线性规划问题,并列出初始单纯形表和计算的终表.56ch1单纯形法PPT课件练习练习P45 1.6(1)57ch1单纯形法PPT课件0-M0-5+2M3-4M2+3M-Z51-101-5210x6-M70011117X4-Mx6x5x4x3x2x1bxBcB-M0-M-532cj-M+1/7-1/7-M-16/7-50/700-102/7-Z1/7-1/75/76/70145/7x12-1/71/72/71/7104/7x23x6x5x4x3x2x1bxBcB-M0-M-532cj58ch1单纯形法PPT课件
