管理运筹学第2章线性规划与单纯形法

《管理运筹学第2章线性规划与单纯形法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章线性规划与单纯形法主讲教师:马越峰第二章线性规划与单纯形法2.1线性规划问题与数学模型2.2图解法2.3线性规划的应用2.4单纯形法基本原理及计算步骤2.5单纯形法的进一步讨论2.6线性规划的对偶问题2.1线形规划(LinearProgramming)问题及其数学模型【引例】某工厂在计划期内要安排甲乙两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，以及资源的限制如下表所示：甲乙资源限制设备11300台时原料A21400千克原料B01250千克单件利润50（元/件）100（元/件）问:工厂应分别生产多少个产品甲、

2、乙才能使工厂获利最多？设生产甲产品x1个，生产乙产品x2个目标函数maxZ=50x1+100x2约束条件x1+x2≤3002x1+x2≤400x2≤250x1≥0,x2≥0线性规划模型1.适用条件：（1）优化条件:问题目标最大化、最小化的要求；（2）约束条件:问题目标受一系列条件的限制；（3）选择条件:实现目标存在多种备选方案；（4）非负条件的选择:根据问题的实际意义决定是否非负。2.构建线性规划模型的步骤（1）科学选择决策变量（2）明确目标要求（3）根据实际问题的背景材料，找出所有的约束条件（4）确定是否增加决策变量的非负条件线性规划模型

3、表示形式——决策变量；——目标函数系数、价值系数或费用系数；——右端项或资源常数；——称为约束系数或技术系数。（1）一般形式：（2）集合形式：（3）向量形式：（4）矩阵形式：【例】将线性规划模型一般表达式化为矩阵形式。解:设:例1.目标函数：Maxz=50x1+100x2约束条件：s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最优解：x1=50，x2=250最优目标值z=27500§2图解法对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，

4、并求解。下面通过例1详细讲解其方法：步骤：(1)分别取决策变量X1,X2为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。x2x1X2≥0X2=0x2x1X1≥0X1=0（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1

5、所示。100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图2-1（4）目标函数z=50x1+100x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。x1x2z=20000=50x1+100x2图2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=5

6、0x1+100x2CBADE解的几种可能结果唯一最优解解无穷多个最优解无界解(可行域无界，常为模型遗漏了某些必要的约束条件)无可行解（可行域为空集，约束条件自相矛盾,资源满足不了人们的需求）可行解：满足LP问题所有约束条件的解最优解：满足目标要求的可行解四种结局:x1x2唯一最优解x2x1无穷多最优解x1x2无界解x2x1无可行解无界解无可行解：可行域为空集增加的约束条件线性规划标准形式线性规划标准模型的一般表达式：非标准形式标准化方法：1.目标函数2.约束条件为不等式:引进松驰变量xs:引进剩余变量xs:4.决策变量为自由变量:5.约束右

7、端项为负:两端乘-1:≥03.约束条件为不等式:引入松驰变量（含义是资源的剩余量）【引例】中引入s1，s2，s3模型化为目标函数：Maxz=50x1+100x2+0s1+0s2+0s3约束条件：s.t.x1+x2+s1=3002x1+x2+s2=400x2+s3=250x1,x2,s1,s2,s3≥0对于最优解x1=50x2=250，s1=0s2=50s3=0说明：生产50单位Ⅰ产品和250单位Ⅱ产品将消耗完所有可能的设备台时数及原料B，但对原料A则还剩余50千克。【例】将线性规划模型转化为标准式解:无约束(4)在第一、第三约束左端加上松弛

8、变量x4,x6≥0，在第二约束左端减去剩余变量x5≥0习题1.用图解法求解下列LP问题（1）minZ=6x1+4x2(2)maxZ=3x1-2x22x1+x2≥1x1+x2≤13