线性规划与单纯形法(II)

《线性规划与单纯形法(II)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章线性规划线性规划模型及单纯形法（2学时）单纯形法续（2学时）对偶理论（2学时）灵敏度分析及整数规划（2学时）1Chapter1线性规划与单纯形法线性规划模型（1.1)单纯形法(1.4)重点：线性规划的模型，单纯形法难点：解的概念，单纯形法基本要求：掌握线性规划的标准化，理解解的概念、解的性质，掌握单纯形法2Chapter1例1-1某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，已知生产单位产品所需的设备台时和原料A、B的消耗量如下表。该工厂每生产一件产品Ⅰ可获利2元，每生产一件产品Ⅱ可获利3元，问应如何安排生产计

2、划能使该厂获利最多？1问题的提出1.1线性规划模型3Chapter1建立模型明确问题，确定决策变量设计划期内产品Ⅰ、Ⅱ的产量分别为x1，x2MaxZ=2x1+3x2x1+2x2≤804x1≤1604x2≤120（非负值约束）x1,x2≥0确定约束条件：设备条件：确定目标函数：确定决策变量的约束：原材料A：原材料B：4Chapter1整理得：目标函数：MaxZ=2x1+3x2约束条件：s.t.：x1+2x2≤804x1≤1604x2≤120x1,x2≥05Chapter16Chapter1一般形式目标函数：Max（

3、Min）z=c1x1+c2x2+…+cnxn（1-1）约束条件：s.t.a11x1+a12x2+…+a1nxn≤（=,≥）b1a21x1+a22x2+…+a2nxn≤（=,≥）b2…………am1x1+am2x2+…+amnxn≤（=,≥）bm（1-2）x1，x2，…，xn≥0（1-3）技术系数Subjectto非负约束价值系数资源限制系数2线性规划模型7Chapter1maxz=c1x1+c2x2++cnxna11x1+a12x2++a1nxn=b1a21x1+a22x2++a2nxn=b2

4、am1x1+am2x2++amnxn=bmx1,x2,,xn≥0其中，bi≥0(i=1,2,,m)标准型8Chapter1标准型的表达形式Maxz=CXAX=bX>=0要求b的各个分量非负资源向量价值系数决策变量系数矩阵9Chapter1化标准型的步骤：（1）目标函数为最小：minz=c1x1+c2x2++cnxn令z=-z,变为maxz=-c1x1-c2x2--cnxn（2）决策变量xj无非负约束。（i）xj≤0，令xj=-xj，xj≥0（ii）xj无约束，令xj=xj-xj，xjx

5、j≥0（3）bi<0,不等式或等式两端同时乘–110Chapter1x1+2x2+x3=804x1+x4=1604x2+x5=120maxz=2x1+3x2+0x3+0x4+0x5x1,…,x5≥0将例1-1的线性规划问题化为标准型11Chapter112Chapter1则该问题的标准型为：13Chapter11.3线性规划问题的解的概念1-41-51-61.3线性规划问题解的概念及性质14Chapter1即，对于标准的LP问题来说满足这两个条件的x是可行解或者可行点三者皆满足是最优解15Chapter1定义1

6、-1基：设A是约束方程组m×n维的系数矩阵，其秩为m，B是矩阵A中m×m阶非奇异子矩阵（B的行列式│B│≠0），则称B是线性规划问题的一个基。最多有个基1.3.1基本概念16maxz=2x1+3x2+0x3+0x4+0x5x1+2x2+x3=804x1+x4=1604x2+x5=120x1,x2≥0基有：B1，B2，B3B4不是基100010001B1=系数矩阵:121004001004001A=121400040B2=120401040B3=210000401B4=17Chapter1基基向量18Chapter

7、1若令方程组中的非基变量x1=x2=0，可以求出一个解：X=（0，0，80，160，120）T称X为基解。19Chapter1一个基本解的非零分量个数不超过m个。基础可行解的非零分量个数

8、况无可行解有可行解无最优解有最优解唯一最优解无穷多最优解线性规划问题23Chapter11.3.2线性规划解的性质定理24Chapter1要找到线性规划问题的最优解，只要在基本可行解中寻找就可以了。虽然基本可行解的数目是有限个（不超过Cnm个），但当m,n较大时，要用“穷举法”求出所有基本可行解也是行不通的。因此，必须寻求一种更有效的方法。1.4单纯形法25Chapter