线性规划理论与模型应用

线性规划理论与模型应用第1页，课件共51页，创作于2023年2月2.1对偶规划1.食谱问题

设有n种食物,各含m种营养素,第j种食物中第i种营养素的含量为aij,所有n种食物价格分别为c1,c2,…,cn,营养素的价格分别为w1,w2,…,wm,要求食谱中m种营养素的含量分别不低于b1,b2,…,bm,食谱中n种食物的数量为x1,x2,…,xn,如下表所示:第2页，课件共51页，创作于2023年2月对偶规划消费者希望费用最低且满足营养要求，则有食谱厂家在确定营养素价格时，希望收益最大且能吸引消费者，则有第3页，课件共51页，创作于2023年2月对偶规划前述的两个规划是同一问题的两个方面: 消费者希望费用最低； 营养厂家希望收益最大。这一对问题即是我们要研究的线性规划的对偶问题.第4页，课件共51页，创作于2023年2月对偶规划对称形式下对偶规划 考虑以下两种形式的线性规划问题第5页，课件共51页，创作于2023年2月对偶规划定义2.1称以上两种形式的线性规划问题为一对对偶线性规划问题，其中LP问题为原规划，LD问题为对偶规划。 其矩阵形式表示为其中定义2.2满足下列条件的线性规划问题为成为具有对称形式：变量均具有非负约束；当目标求极小时约束条件均为“”，当目标求极大时约束条件均为“≤”。第6页，课件共51页，创作于2023年2月对偶规划如果将对偶规划(LD)作为原规划，其形式为其对偶规划是即是原规划定理2.1对偶规划的对偶规划是原规划，即LD是LP的对偶规划时，LP也是LD的对偶规划。第7页，课件共51页，创作于2023年2月对偶规划对称形式下原规划和对偶规划转换规则：原规划min问题，对偶规划max问题右端项与目标系数互相转换；系数矩阵互为转置关系；原规划约束条件对应对偶规划的变量‘’约束，对偶规划对应

的变量0；原规划的变量对应对偶规划的约束条件变量0，对偶规划中对应

的约束为‘≤’约束非对称形式下的特点线性规划问题的约束条件有‘’、‘=’、‘≤’约束，变量中有0、≤0、自由变量第8页，课件共51页，创作于2023年2月对偶规划非对称形式下对偶规划 例2.1写出下述线性规划问题的对偶规划第9页，课件共51页，创作于2023年2月对偶规划将约束全变为“”此问题的对偶问题为第10页，课件共51页，创作于2023年2月对偶规划此问题的对偶问题为第11页，课件共51页，创作于2023年2月对偶规划非对称形式下原规划和对偶规划转换规则：原规划min问题，对偶规划max问题右端项与目标系数互相转换；系数矩阵互为转置关系；原规划约束条件‘≤’约束，对偶规划对应

的变量≤0；‘’约束，对偶规划对应

的变量0；‘=’约束，对偶规划对应

的变量无约束(自由变量)；原规划的变量约束0的变量，对偶规划中对应

的约束为‘≤’约束；≤0的变量，对偶规划中对应

的约束为‘’约束；自由变量，对偶规划中对应

的约束为‘=’约束。第12页，课件共51页，创作于2023年2月对偶规划例2.2写出下述线性规划问题的对偶规划第13页，课件共51页，创作于2023年2月2.2对偶定理为便于讨论，本节仅对对称形式的对偶规划进行讨论，非对称形式的对偶规划同样可证明类似的结论。为方便起见，LP简称为P,LD简称为D。第14页，课件共51页，创作于2023年2月对偶定理1.弱对偶定理定理2.2设x0是P的可行解，w0是D的可行解，则

cx0w0b；若x*、w*分别是P、D的可行解且cx*=w*b，则x*、w*分别是P、D的最优解；若P、D中有一个目标函数值无界，则另一个可行域为空集；P、D都有最优解的充要条件是P、D都有可行解。证：1)因为Ax0b，x00，w0A≤c，w00，对Ax0b两边左乘w0则有w0Ax0w0b；对w0A≤c两边右乘x0则有w0Ax0≤cx0；从而有cx0w0b。

2)设x0是P的任意可行解，由1)有cx0w*b=cx*从而x*是P的最优解；同样可证w*是D的最优解。 用1)的结论可容易证明3)和4)成立。第15页，课件共51页，创作于2023年2月对偶定理2.强对偶定理定理2.3一对对偶规划P和D中的一个有最优解的充要条件是另一个有最优解，且两问题的最优值相等。证：对问题P引入松弛变量v=(xn+1,…,xn+m)T将其变成设该问题的最优解为x*，B为最优基，则有令w*=cBB-1，则有w*是D的可行解又w*b=cBB-1b=cx*，由定理2.2可知w*是D的最优解。第16页，课件共51页，创作于2023年2月对偶定理3.互补松弛定理及其应用

定理2.4(互补松弛定理)已知x*,w*分别是P和D的可行解，则它们分别是P和D的最优解的充要条件是

w*(Ax*-b)=0,(c-w*A)x*=0证：因为x*,w*分别是P和D的可行解，从而

w*b≤w*Ax*≤cx*必要性：若x*,w*分别是P和D的最优解，则w*b=cx*，从而上式中两“≤”号等式成立，显然结论成立。充分性： 若w*(Ax*-b)=0，则w*Ax*=w*b，

若(c-w*A)x*=0，则cx*=w*Ax*从而cx*=w*b，即x*,w*分别是P和D的最优解第17页，课件共51页，创作于2023年2月对偶定理将互补松弛定理的结论写成如下形式：以上两式表示 P规划的约束严格不等号成立(松)时，D规划相应的变量必取0(紧)； D规划的约束严格不等号成立(松)时，P规划相应的变量必取0(紧)，非基变量； 第二式也就是λjxj=0(j=1,2,…,n)表示在P规划中检验数与变量互为松弛。第18页，课件共51页，创作于2023年2月对偶定理例2.3求解线性规划问题其对偶问题：第19页，课件共51页，创作于2023年2月对偶定理对偶规划是两个变量的问题可用图解法求解，得对偶规划的最优解显然，第1、5个约束等式成立，其它严格不等式成立，由互补松弛定理原规划的最优解中x2*=x3*=x4*

=0，因为w1*和w2*均不等于0，从而原规划的最优解中两个约束是紧的，即第20页，课件共51页，创作于2023年2月对偶定理例2.4求解线性规划问题的对偶问题：第21页，课件共51页，创作于2023年2月对偶定理用单纯形表格求解线性规划问题第22页，课件共51页，创作于2023年2月对偶定理原问题的最优解为对偶问题的最优解为第23页，课件共51页，创作于2023年2月作业P74： 4，5，7第24页，课件共51页，创作于2023年2月2.3对偶单纯形法1.理论基础 考虑线性规划标准形其对偶规划为第25页，课件共51页，创作于2023年2月对偶单纯形法由对偶定理，若有x*,w*满足Ax*=b,x*0,w*A≤

c,cx*=w*b，则x*,w*是P,D的最优解；考虑单纯形法的迭代过程，若x是基可行解，B是相应的可行基，则Ax=b,x0。令w=cBB-1，则cx=wb，检验数可表示为λ=c-cBB-1A=c–

wA；在单纯形法的迭代中，对偶定理中的4个条件由3个条件Ax=b,x0,cx=wb始终满足；单纯形法的迭代过程实际上可看作验证检验数是否满足λ0的过程，也就是验证D问题约束条件wA≤c是否满足的过程;单纯形法迭代也可看作是从原问题P的基可行解逐步迭代到对偶问题D的可行解的过程（两问题的目标函数值始终相等）。对偶单纯形法的本质是从对偶问题的可行解逐步迭代到原问题P的可行解的过程。第26页，课件共51页，创作于2023年2月对偶单纯形法定义若A=(B,N),其中B非奇异，w=cBB-1称为D的一个基解，若c-cBB-1A0,即wA≤c，称w为D的一个基可行解，此时称B为原规划的一个正则基，

称为原规划问题的一个正则基解。对偶单纯形法的基本思想：若有一个正则基B，则w=cBB-1满足wA≤c，Ax=b，cx=wb，若x0，则x已是最优解，否则求另一个正则基解，直到满足若x0为止。原规划单纯形迭代是在满足Ax=b和x0前提下逐步使解达到最优；对偶单纯形法迭代是在满足Ax=b和最优性条件前提下逐步使解满足x0。第27页，课件共51页，创作于2023年2月对偶单纯形法2.对偶单纯形表格 不妨设前m个为基变量，表格形式仍然如同单纯形表格 区别在于检验数始终满足λj0，不再要求bi0。迭代思想是，如果br<0，则为xr出基变量；选进基变量xk使所有λj0仍然成立，进行转轴变换使xk所在列为单位向量。第28页，课件共51页，创作于2023年2月对偶单纯形法对检验数行消元之后，目标函数形式为为保证λj0仍然成立，显然下式确定的k即可如果yr,j0，则原问题无可行解。如何使所有λj0仍然成立，考虑xr所在方程和目标函数。第29页，课件共51页，创作于2023年2月对偶单纯形法例2.6用对偶单纯形法求解下述线性规划问题解：转化为标准形取x4,x5为基变量，方程两边乘以-1，则有如下标准形第30页，课件共51页，创作于2023年2月对偶单纯形法此问题x4,x5为基变量时，检验数均为正，是一个正则基，对偶单纯形表格为x4为出基变量，x2为进基变量，以y12为主元做转轴变换得第31页，课件共51页，创作于2023年2月对偶单纯形法x5为出基变量，x3为进基变量，以y23为主元做转轴变换得原问题的最优解x=(0,¼,½)T，最优值z*=17/2。第32页，课件共51页，创作于2023年2月作业P77： 8第33页，课件共51页，创作于2023年2月2.4灵敏度分析目标系数的灵敏度分析目标系数变化对最优解的影响 为求出数据变化后的最优解，不必从最初的阶段开始求解，仅从原问题最后的单纯形表的基础之上，重新计算检验数，然后求出最优解并与原最优解比较。不影响最优基变化时系数ck的变化范围灵敏度分析，是讨论线性规划问题中原始数据aij，bi，cj的变化对最优解的影响，所谓对最优解的影响主要有两个层面，一是对最优解的影响，另一是当某个数据在什么范围内变化时，最优基将不会改变。本节讨论bi和cj的变化、增加变量对最优解的影响。第34页，课件共51页，创作于2023年2月灵敏度分析设目标系数ck的改变量为,其中为变化之后的系数。当xk不是基变量时，此时只对检验数λk产生影响，只要考虑保持λk0即可。当xk是基变量时，此时ck的变化将对所有检验数产生影响。设xk对应第i个方程，基的新旧目标系数为第35页，课件共51页，创作于2023年2月灵敏度分析第36页，课件共51页，创作于2023年2月灵敏度分析例2.7某工厂用甲乙两种原料生产A、B、C、D四种产品，每种产品的利润、原料数量、每种产品消耗原料定额如下表所示：问应怎样组织生产才能使总利润最大？如果产品A、D的利润均变到15万元，最优解有何变化？又各产品的利润在何范围内变化时，最优基不变？解：1)设x1，x2，x3，x4分别表示A、B、C、D四种产品的生产数量，可建立如下模型：第37页，课件共51页，创作于2023年2月灵敏度分析化为标准形用单纯形法得到最后一个表格如下，最优解产品C生产1万件，产品D生产2万件，总利润88万元。第38页，课件共51页，创作于2023年2月灵敏度分析2)计算c1，c4改变后的检验数代入上表格(在当前基下)第39页，课件共51页，创作于2023年2月灵敏度分析3)讨论cj(j=1,2,3,4)的变化范围 (1)非基变量x1，x2的检验数为λ1=4，λ2=2/3，系数的变化范围是从而c1，c2变化范围分别是 (2)基变量x3，x4的系数，先考虑c3变化范围第40页，课件共51页，创作于2023年2月灵敏度分析从而c3变化范围分别是再考虑c4变化范围得到c4变化范围分别是第41页，课件共51页，创作于2023年2月灵敏度分析2.右端项的灵敏度分析右端项的几个分量改变对最优解的影响，此时不影响检验数，但可能影响基变量的非负性，如果B-1b0，当前解仍然是最优解，否则，用对偶单纯形法求出最优解。另一类有意义的问题是当某一个分量在什么范围内变化，才不影响基变量，设bk的改变量为，记当前最优解的基解为，改变后的基解为，则有设，如果，则应有第42页，课件共51页，创作于2023年2月灵敏度分析因此，不改变当前最优基前提下bk的变化范围是例2.8考虑例2.7中在当前最优基下右端项的变化范围。第43页，课件共51页，创作于2023年2月灵敏度分析3.增加新变量时的灵敏度分析设新增变量为xn+m+1，相应的列向量为An+m+1，目标系数为cn+m+1，此时考虑最优解的变化，从最后的单纯形表格中的B-1计算yn+m+1=B-1An+m+1及检验数λn+m+1=cn+m+1-cByn+m+1，如果λn+m+10，最优解不变，否则将xn+m+1作为进基变量继续求解得出新的最优解。例2.9在例2.7中某工厂考虑引进新产品E，该产品每1万件要消耗原料甲3公斤，原料乙1公斤，当产品E的利润为17万元时最优解如何变化?解：设产品E的产量为x7，则相应的有第44页，课件共51页，创作于2023年2月灵敏度分析将以上信息加入到最后的单纯形表格中得继续求解的如下最优解第45页，课