第1章+线性规划与单纯形法-第1节.pdf

《第1章+线性规划与单纯形法-第1节.pdf》由会员分享，可在线阅读，更多相关《第1章+线性规划与单纯形法-第1节.pdf（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、二.线性规划与目标规划第第1章 线性规划与单纯形法章 线性规划与单纯形法线性规划是运筹学的一个重要分支1947年丹捷格（G.B.Dantzig）提出单纯形法后，线性规划在理论上趋于成熟，应用日益广泛与深入线性规划的适用领域广泛。从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用。它已是现代科学管理的重要手段之一解线性规划问题的方法有多种第1节 线性规划问题及其数学模型1.1 问题的提出从一个简化的生产计划安排问题开始例 1某工厂在计划期内要安排生产、两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表1-1所示。产 品资源拥

2、有量设备1 2 8台时原材料 A40 16 kg原材料 B04 12 kg续例1该工厂 每生产一件产品可获利2元，每生产一件产品可获利3元，问应如何安排计划使该工厂获利最多?数学模型 +=+=0,1241648232max21212121xxxxxxxxz目标函数约束条件台时约束原材料A约束原材料B约束称它们为决策变量。产品的数量，分别表示计划生产设III,21xx例2.简化的环境保护问题 靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万立方米，在两个工厂之间有一条流量为每天200万立方米的支流。续例2 第一化工厂每天排放含有某种有害物质的工业污水2万立方米，第二化工厂每天排放这

3、种工业污水1.4万立方米。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可自然净化。根据环保要求，河流中工业污水的含量应不大于0.2%这两个工厂都需各自处理一部分工业污水。第一化工厂处理工业污水的成本是1000元/万立方米。第二化工厂处理工业污水的成本是800元/万立方米 问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂总的处理工业污水费用最小建模型之前的分析和计算设设：一厂每天处理工业污水量为x1万立方米，二厂每天处理工业污水量为x2万立方米 10002700)4.1()2(8.0)(210002500)2()(2211+xxx：近似厂后的水质要求经：近似厂前的水质要

4、求经0,4.126.18.018001000min212121121+=xxxxxxxxxz约束条件目标函数前最大排放量后数学模型共同的特征(1)每一线性规划问题都用一组决策变量（x1,x2,，xn）表示某一方案，这组决策变量的值就代表一个具体方案。一般这些变量取值是非负且连续的(2)存在一定的约束条件，可以用一组线性等式或线性不等式来表示(3)有一个达到目标的要求，它可用决策变量的线性函数(称为目标函数)来表示。要求目标函数实现最大化或最小化)3.1(0,),()2.1(),(),()1.1(max(min)21221122222121112121112211=+=+=+=+=+=+=nmn

5、mmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxcz?约束条件目标函数线性规划的一般模型形式非负约束1.2 图解法例1是二维空间（平面）线性规划问题，可用作图法直观地来表述它的求解。因存在必须在直角坐标的第1象限内作图，求解。021x,x可行解和可行域+=+=0,1241648232max21212121xxxxxxxxz在(4,2)点，目标值达到最大值14目标函数2132xxzmax+=表示一簇平行线33212zxx+=可能出现的几种情况（1）无穷多最优解(多重最优解)，见图1-4（2）无界解，见图1-5-1（3）无可行解，见图1-5-2（1）无穷多最优解(多重最

6、优解)目标函数max z=2x1+4x2（2）无界解+=ox,xxxxxxxzmax2121121242（3）无可行解当存在矛盾的约束条件时，为无可行域。85.121+xx如在例1的中增加一个约束条件:该问题的可行域为空集空集，即无可行解不存在可行域85121+x.x增加的约束条件1.3 线性规划问题的标准型式=+=+=+=+=+=+=0,:212211222221211121212211nnnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxM?111czmax约束条件：目标函数：线性规划问题的标准型式=n,j,xm,i,bxaxczmax:Mjnjijijnjj

7、j?21021111约束条件：目标函数：bi0用向量表示为：()()njbbbbaaaPxxxXcccCnjxbxPCXzMmmjjjjnnjnjjj?,2,1;,2,1,0max:212121211 1=约束条件：目标函数：()()()()TnnmnmnxxxXPPPaaaaAXbAXCXzM,;,0max:21211111 1?=决策变量向量：价值向量：资源向量：系数矩阵：约束条件：目标函数：Cbbbm1一般一般nm用矩阵表示为：如何变换为标准型：(1)若要求min z=CX。只需将目标函数最小化变换为求目标函数最大化，即令z=-z，于是得到max z=-CX(2)约束方程为不等式。对“”

8、不等式:可在不等式的左端加入非负松弛变量，把原“”不等式变为等式对“”不等式:可在不等式的左端减去一个非负剩余变量(也可称松弛变量)，把不等式约束条件变为等式约束条件例3 将例1的数学模型化为标准型=+=+=+=+=+=+=+=0,124164820,1241648200032max32max5432152413212121215432121xxxxxxxxxxxxxxxxxxxxxxxzxxz例1的数学模型,加松驰变量后(3)若存在取值无约束的变量xk,可令,其中:kkkxxx=0,kkxx例4 将下述线性规划问题化为标准型=+=为无约束3213213213213210533732x;x,x

9、xxxxxxxxxxxxzmin处理步骤：(1)用x4-x5替换x3，其中x4，x50；(2)在第一个约束不等式号的左端加入松弛变量x6；(3)在第二个约束不等式号的左端减去剩余变量x7；(4)令z=-z，把求min z 改为求max z，即可得到该问题的标准型例4的标准型=+=+=+=+=+=+=0,5)(232)(7)(00)(32max7654214217542165421765421xxxxxxxxxxxxxxxxxxxxxxxxxxz1.4 线性规划问题的解的概念1.可行解2.基3.基可行解4.可行基1.可行解满 足 约 束 条 件(1-5)，(1-6)式 的 解X=(x1,x2，x

10、n)T，称为线性规划问题的可行解可行解，其中使目标函数达到最大值的可行解称为最优解最优解=)61(,2,1,0)51(,2,1,)41(max11njxmibxaxczjnjijijnjjj?()()()否则为非基变量为基变量为基向量基。为线性规划问题的一个称阶非奇异子矩阵中的是系数矩阵,),2,1(),2,1(,021212222111211mjmjPPPaaaaaaaaaBmmBmmmmmmm?=jjxPBBA设A中前m列线性无关2.基、基向量、基变量、基解基解 改写（改写（1-5）：）：基变量：基变量：XB=(x1,x2,，xm)T 令非基变量：令非基变量：XN=(xm+1,xm+2,x

11、n)T=0 由由(1-7)得一基解：得一基解：X=(x1,x2,xm,0,0)T 基解的非零分量个数基解的非零分量个数m 图中的图中的0、Q1、Q2、Q3、Q4和延长各条线的交点都是基解和延长各条线的交点都是基解)71(11=+=+=nmjjjmjjjxPbxP3.基可行解满足非负条件（1-6）的基解，称为基可行解.基可行解的非零分量的数目也不大于m，并且都是非负的。是基可行解43210Q,Q,Q,Q,4.可行基 对应于基可行解的基，称为可行基 约束方程组(1-5)具有基解的数目最多是个 一般基可行解的数目要小于基解的数目。基解中的非零分量的个数小于m个时，该基解是退化解。在以下讨论时，假设不出现退化的情况mnC几种解之间的关系小结1.线性规划问题的模型特征2.通过图解法了解如何求解线性规划问题3.为求解高维线性规划问题，必须建立的概念