管理科学基础2线性规划ppt课件.ppt

《管理科学基础2线性规划ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1线性规划问题及其数学模型图解法单纯形法线性规划模型的应用线性规划2设备产品ABCD利润（元/件）P121402P222043有效台时1281612例：已知信息如右表所示，问如何安排生产才能获得最大利润？模型:maxZ=2x1+3x2s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12x1≥0,x2≥0线性规划问题及其数学模型3目标函数：约束条件：①②③价值系数技术系数限额系数线性规划数学模型的一般形式4也可以记为如下形式：目标函数：约束条件：5向量形式：决策变量向量价值向量资源向量系数列向量6矩阵形式：系数矩阵7特征：⑴目标函数为求最大值；⑵所有约束条件（非负条件除外）都

2、是等式，右端常数项大于零；⑶变量为非负。①②③线性规划模型的标准形式8标准型转换方式：(1)如果极小化原问题minZ=CX，则令Z'=-Z，转为求maxZ'=-CX(2)若某个bi<0，则以－1乘该约束两端，使之满足非负性的要求。(3)对于≤型约束，在左端加上一个非负松弛变量，使其为等式。(4)对于≥型约束，在左端减去一个非负剩余变量，使其为等式。(5)若某决策变量xk无非负约束，令xk=x'k-x"k，(x'k≥0,x"k≥0)。9转换方式：⑴目标函数的转换也就是：令，可得到上式。即如果是求最小值即，则可将目标函数乘以（－1），可化为求最大值问题。10⑵约束条件的转换：由不等式转换为等式

3、。称为松弛变量称为剩余变量11⑶变量的变换例1：将下列线性规划问题化为标准形式为无约束（无非负限制）若存在取值无约束的变量，可令其中：12解:用x4-x5替换x3，且x4,x5>=0，将第3个约束方程两边乘以（－1），再将最小值问题反号，变为求最大值。标准形式如下：引入变量13例2：将线性规划问题化为标准型为无约束解：作业1将下面的线性规划模型转换成标准形式（标准型）15⑴可行解：满足所有约束条件的解为可行解。所有解的集合称为可行解的集或可行域。⑵最优解：使目标函数达到最优值的可行解。⑶基：若B是矩阵A的一个m×m阶非奇异子矩阵（∣B∣≠0），则B是一个基。则称Pj(1≤j≤m)为基向量。

4、∴xj(1≤j≤m)为基变量，其他变量为非基变量。线性规划问题的解16⑷基解(基本解)：非零分量的数目不大于约束方程个数m的解（对应着一个基），最多为个。⑸基可行解：满足所有非负约束条件的基解⑹可行基：对应于基可行解的基称为可行基。非可行解可行解基解基可行解17一般有两种方法图解法单纯形法两个变量、直角坐标三个变量、立体坐标适用于任意变量，但需将一般形式变成标准形式线性规划模型的求解方法18建立直角坐标，图中阴影部分及边界上的点均为其解，是由约束条件来反映的。例一:⑴⑵⑶⑷图解法19012345678123456⑴⑵⑶⑷作图∴最优解：x1=4,x2=2，有唯一最优解，Z=14x2x1(42

5、)⑴⑵⑶⑷可行域20例二：例三：⑴⑵⑶无穷多最优解⑴⑵无界解x1x1x2x221⑴⑵x1x2无可行解例四:练习122解的情况唯一解无穷多最优解（多重最优解）无界解无可行解有最优解无最优解23凸集凸集不是凸集顶点线性规划问题的几何意义几个概念：1.凸集2.凸组合3.顶点24是否凸集？abcd25K是n维欧氏空间En的一个点集，若任意两点的连线上的所有点，则称K为凸集。凸集：凸组合：26顶点：则称X为K的一个顶点（或极点）。27几个定理定理1.若线性规划问题存在可行域，则其可行域证明.设28引理1.线性规划问题的可行解X为基可行解的充要条件是X的正分量对应的系数列向量线性无关。几个定理29定理

6、2.线性规划问题的基可行解X对应于可行域D的顶点。证明.不失一般性，设基可行解X的前m个分量为正，则分两步证明：（1）若X不是基可行解，则它不是可行域D的顶点。根据引理1，若X不是基可行解，则其正分量对应的系数列向量线性相关，即存在不全为0的数使得(1-8)-μ×(1-9)：(1-8)(1-9)几个定理30(1-8)-μ×(1-9)：(1-8)+μ×(1-9)：取当μ充分小时，有几个定理31（2）若X不是可行域D的顶点，则它不是基可行解。因为X不是可行域D的顶点，因此D内存在不同的两点设X是基可行解，对应的向量组线性无关。当j>m时，线性相关，矛盾！几个定理32引理2.若K是有界凸集，则任

7、何一点可表示为K的顶点的凸组合。定理3.若可行域D有界，线性规划问题的目标函数一定可以在其可行域的顶点达到最优。几个定理33思路：先找一个基可行解（顶点），如不是最优，继续寻找下一个基可行解（顶点），直到找出最优为止。⑴线性规划问题的可行域（非空）是凸集（凸多边形）。（定理1）⑵若可行域是有界凸集，则最优解一定是在凸集的某一顶点实现（顶点数目不超过个）（定理3）结论：(3)线性规划如果有可行解，则一定有基可行解；如果有最