关闭

关闭

关闭

封号提示

内容

首页 ch01.ppt

ch01.ppt

ch01.ppt

上传者: 白水有小楼 2014-03-11 评分 0 0 0 0 0 0 暂无简介 简介 举报

简介:本文档为《ch01ppt》,可适用于高等教育领域,主题内容包含二、线性规划与目标规划清华大学出版社*二、线性规划与目标规划第章线性规划与单纯形法第章对偶理论与灵敏度分析第章运输问题第章目标规划第章线性规划与单纯符等。

二、线性规划与目标规划清华大学出版社*二、线性规划与目标规划第章线性规划与单纯形法第章对偶理论与灵敏度分析第章运输问题第章目标规划第章线性规划与单纯形法清华大学出版社*第章线性规划与单纯形法第节线性规划问题及其数学模型第节线性规划问题的几何意义第节单纯形法第节单纯形法的计算步骤第节单纯形法的进一步讨论第节应用举例第节线性规划问题及其数学模型清华大学出版社*第节线性规划问题及其数学模型问题的提出图解法线性规划问题的标准形式线性规划问题的解的概念第节线性规划问题及其数学模型清华大学出版社*第节线性规划问题及其数学模型线性规划是运筹学的一个重要分支。线性规划在理论上比较成熟在实用中的应用日益广泛与深入。特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之后线性规划的适用领域更为广泛了。从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用。它已是现代科学管理的重要手段之一。解线性规划问题的方法有多种以下仅介绍单纯形法。问题的提出清华大学出版社*问题的提出问题的提出例某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品已知生产单位产品所需的设备台时及A、B两种原材料的消耗如表所示。每生产一件产品Ⅰ可获利元每生产一件产品Ⅱ可获利元问应如何安排计划使该工厂获利最多问题的提出清华大学出版社*问题的提出用数学关系式描述这个问题问题的提出清华大学出版社*问题的提出得到本问题的数学模型为:这就是一个最简单的线性规划模型。问题的提出清华大学出版社*问题的提出例靠近某河流有两个化工厂(见图)流经第一化工厂的河流流量为每天万立方米在两个工厂之间有一条流量为每天万立方米的支流。图化工厂每天排放含有某种有害物质的工业污水万立方米化工厂每天排放的工业污水为万立方米。从化工厂排出的污水流到化工厂前有可自然净化。根据环保要求河流中工业污水的含量应不大于。因此两个工厂都需处理一部分工业污水。化工厂处理污水的成本是元万立方米,化工厂处理污水的成本是元万立方米。问:在满足环保要求的条件下每厂各应处理多少工业污水使两个工厂处理工业污水的总费用最小。问题的提出清华大学出版社*问题的提出设:化工厂每天处理的污水量为x万立方米化工厂每天处理的污水量为x万立方米建模型之前的分析和计算问题的提出清华大学出版社*问题的提出得到本问题的数学模型为:问题的提出清华大学出版社*问题的提出每一个线性规划问题都用一组决策变量表示某一方案这组决策变量的值代表一个具体方案。一般这些变量的取值是非负且连续的都有关于各种资源和资源使用情况的技术数据创造新价值的数据存在可以量化的约束条件这些约束条件可以用一组线性等式或线性不等式来表示都有一个达到某一目标的要求可用决策变量的线性函数(称为目标函数)来表示。按问题的要求不同要求目标函数实现最大化或最小化。上述两个问题具有的共同特征:问题的提出清华大学出版社*问题的提出决策变量及各类系数之间的对应关系问题的提出清华大学出版社*问题的提出线性规划模型的一般形式图解法清华大学出版社*图解法图解法例是一个二维线性规划问题因而可用作图法直观地进行求解。图解法清华大学出版社*图解法目标值在()点达到最大值图解法清华大学出版社*图解法()无穷多最优解(多重最优解)见图。()无界解见图。()无可行解见图。通过图解法可观察到线性规划的解可能出现的几种情况:图解法清华大学出版社*图解法目标函数maxz=xx图无穷多最优解(多重最优解)图解法清华大学出版社*图解法图无界解图解法清华大学出版社*当存在相互矛盾的约束条件时线性规划问题的可行域为空集。例如如果在例的数学模型中增加一个约束条件:则该问题的可行域即为空集即无可行解无可行解的情形图解法图解法清华大学出版社*图不存在可行域图解法线性规划问题的标准型式清华大学出版社*线性规划问题的标准型式线性规划问题的标准型式线性规划问题的标准型式清华大学出版社*线性规划问题的标准型式用向量形式表示的标准形式线性规划线性规划问题的几种表示形式线性规划问题的标准型式清华大学出版社*线性规划问题的标准型式用矩阵形式表示的标准形式线性规划线性规划问题的标准型式清华大学出版社*线性规划问题的标准型式()若要求目标函数实现最小化即minz=CX则只需将目标函数最小化变换求目标函数最大化即令z′=z于是得到maxz′=CX。()约束条件为不等式。分两种情况讨论:若约束条件为“”型不等式则可在不等式左端加入非负松弛变量把原“”型不等式变为等式约束若约束条件为“”型不等式则可在不等式左端减去一个非负剩余变量(也称松弛变量)把不等式约束条件变为等式约束。()若存在取值无约束的变量xk,可令如何将一般线性规划转化为标准形式的线性规划线性规划问题的标准型式清华大学出版社*线性规划问题的标准型式例将例的数学模型化为标准形式的线性规划。例的数学模型在加入了松驰变量后变为线性规划问题的标准型式清华大学出版社*线性规划问题的标准型式例将下述线性规划问题化为标准形式线性规划()用xx替换x其中xx()在第一个约束不等式左端加入松弛变量x()在第二个约束不等式左端减去剩余变量x()令z′=z将求minz改为求maxz′即可得到该问题的标准型。线性规划问题的标准型式清华大学出版社*线性规划问题的标准型式例例的标准型线性规划问题的解概念清华大学出版社*线性规划问题的解概念可行解基基可行解可行基线性规划问题的解的概念清华大学出版社*线性规划问题的解的概念定义满足约束条件()、()式的解X=(x,x…xn)T称为线性规划问题的可行解其中使目标函数达到最大值的可行解称为最优解。可行解线性规划问题的解的概念清华大学出版社*线性规划问题的解的概念基基向量基变量线性规划问题的解的概念清华大学出版社*线性规划问题的解的概念满足非负条件()的基解称为基可行解基可行解的非零分量的数目不大于m并且都是非负的。基可行解线性规划问题的解的概念清华大学出版社*线性规划问题的解的概念对应于基可行解的基称为可行基。约束方程组()具有的基解的数目最多是个一般基可行解的数目要小于基解的数目。以上提到了几种解的概念它们之间的关系可用图表明。说明:当基解中的非零分量的个数小于m时该基解是退化解。在以下讨论时假设不出现退化的情况。可行基线性规划问题的解的概念清华大学出版社*线性规划问题的解的概念不同解之间的关系第节线性规划问题的几何意义清华大学出版社*第节线性规划问题的几何意义基本概念几个定理基本概念清华大学出版社*基本概念凸集凸组合顶点基本概念清华大学出版社*基本概念定义设K是n维欧氏空间的一点集若任意两点X()KX()K的连线上的所有点αX()(α)X()K(α)则称K为凸集。图凸集基本概念清华大学出版社*基本概念实心圆实心球体实心立方体等都是凸集圆环不是凸集。从直观上讲凸集没有凹入部分其内部没有空洞。图中的(a)(b)是凸集(c)不是凸集。图中的阴影部分是凸集。任何两个凸集的交集是凸集见图(d)基本概念清华大学出版社*基本概念设X()X()…X(k)是n维欧氏空间En中的k个点。若存在μμ…μk且μi,i=,,…k使X=μX()μX()…μkX(k)则称X为X()X()…X(k)的一个凸组合(当<μi<时称为严格凸组合)。凸组合基本概念清华大学出版社*基本概念设K是凸集XK若X不能用不同的两点X()K和X()K的线性组合表示为X=αX()(α)X()(<α<)则称X为K的一个顶点(或极点)。图中的Q,,,都是顶点。顶点几个定理清华大学出版社*几个定理定理若线性规划问题存在可行域则其可行域是凸集。几个定理清华大学出版社*几个定理定理的证明:只需证明D中任意两点连线上的点必然在D内即可。设是D内的任意两点且X()X()。几个定理清华大学出版社*几个定理几个定理清华大学出版社*几个定理引理线性规划问题的可行解X=(x,x,…xn)T为基可行解的充要条件是:X的正分量所对应的系数列向量是线性独立的。几个定理清华大学出版社*几个定理定理线性规划问题的基可行解X对应于可行域D的顶点。证:不失一般性假设基可行解X的前m个分量为正。故现分两步来讨论分别用反证法。几个定理清华大学出版社*几个定理()若X不是基可行解则它一定不是可行域D的顶点。根据引理若X不是基可行解则其正分量所对应的系数列向量PP…Pm线性相关即存在一组不全为零的数αi,i=,,…,m使得αPαP…αmPm=()用一个数μ>乘()式再分别与()式相加和相减得(xμα)P(xμα)P…(xmμαm)Pm=b(xμα)P(xμα)P…(xmμαm)Pm=b几个定理清华大学出版社*几个定理因X不是可行域D的顶点故在可行域D中可找到不同的两点X()=(x(),x(),…,xn())TX()=(x(),x(),…,xn())T使得X=αX()(α)X()<α<设X是基可行解对应的向量组P…Pm线性独立故当j>m时有xj=xj()=xj()=。由于X()X()是可行域的两点因而满足()若X不是可行域D的顶点则它一定不是基可行解。将两式相减得因X()X()所以上式中的系数不全为零故向量组P,P,…Pm线性相关与假设矛盾即X不是基可行解。几个定理清华大学出版社*几个定理引理若K是有界凸集则任何一点XK可表示为K的顶点的凸组合。本引理的证明从略用以下例子说明本引理的结论。例设X是三角形中任意一点X()X()和X()是三角形的三个顶点试用三个顶点的坐标表示X(见图)图几个定理清华大学出版社*几个定理解:任选一顶点X()做一条连线XX()并延长交于X()、X()连接线上一点X′。因为X′是X()、X()连线上一点故可用X()、X()线性组合表示为X′=αX()(α)X()<α<又因X是X′与X()连线上的一个点故X=λX′(λ)X()<λ<将X′的表达式代入上式得到X=λ[αX()(α)X()](λ)X()=λαX()λ(α)X()(λ)X()令μ=αλ,μ=(λ),μ=λ(α)得到X=μX()μX()μX()iμi=,<μi<几个定理清华大学出版社*几个定理定理若可行域有界则线性规划问题的目标函数一定可以在其可行域的顶点上达到最优。证:设X(),X()…X(k)是可行域的顶点若X()不是顶点且目标函数在X()处达到最优z*=CX()(标准型是z=maxz)。因X()不是顶点所以它可以用D的顶点线性表示为代入目标函数得几个定理清华大学出版社*几个定理在所有的顶点中必然能找到某一个顶点X(m)使CX(m)是所有CX(i)中最大者。并且将X(m)代替()式中的所有X(i)得到由此得到X()CX(m)根据假设CX()是最大值所以只能有CX()=CX(m)即目标函数在顶点X(m)处也达到最大值。几个定理清华大学出版社*几个定理有时目标函数可能在多个顶点处达到最大这时在这些顶点的凸组合上也达到最大值这时线性规划问题有无限多个最优解。假设是目标函数达到最大值的顶点则对这些顶点的凸组合有几个定理清华大学出版社*几个定理设:于是:另外若可行域为无界则可能无最优解也可能有最优解若有最优解也必定在某顶点上得到。基本结论清华大学出版社*基本结论线性规划问题的所有可行解构成的集合是凸集也可能为无界域它们有有限个顶点线性规划问题的每个基可行解对应可行域的一个顶点。若线性规划问题有最优解必在某顶点上得到。虽然顶点数目是有限的若采用“枚举法”找所有基可行解然后一一比较最终必然能找到最优解。但当n,m较大时这种办法是行不通的所以要继续讨论如何有效寻找最优解的方法。本课程将主要介绍单纯形法。第节单纯形法清华大学出版社*第节单纯形法举例初始基可行解的确定最优性检验与解的判断基变换迭代(旋转运算)单纯形法求解线性规划的思路:清华大学出版社*单纯形法求解线性规划的思路:一般线性规划问题具有线性方程组的变量数大于方程个数这时有不定的解。但可以从线性方程组中找出一个个的单纯形每一个单纯形可以求得一组解然后再判断该解使目标函数值是增大还是变小决定下一步选择的单纯形。这就是迭代直到目标函数实现最大值或最小值为止。这样问题就得到了最优解先举一例来说明。举例清华大学出版社*举例例试以例来讨论如何用单纯形法求解。解:已知本例的标准型为:举例清华大学出版社*举例约束条件()式的系数矩阵为从()式可看到x,x,x的系数构成的列向量举例清华大学出版社*举例P,P,P是线性独立的这些向量构成一个基B。对应于B的变量x,x,x为基变量从()式中可以得到()举例清华大学出版社*举例将()式代入目标函数():得到当令非基变量x=x=便得到z=。这时得到一个基可行解X()X()=(,,,,)T本基可行解的经济含义是:工厂没有安排生产产品Ⅰ、Ⅱ资源都没有被利用所以工厂的利润为z=。举例清华大学出版社*举例从分析目标函数的表达式()可以看到:非基变量x,x(即没有安排生产产品ⅠⅡ)的系数都是正数因此将非基变量变换为基变量目标函数的值就可能增大。从经济意义上讲安排生产产品Ⅰ或Ⅱ就可以使工厂的利润指标增加。所以只要在目标函数()的表达式中还存在有正系数的非基变量这表示目标函数值还有增加的可能就需要将非基变量与基变量进行对换。举例清华大学出版社*举例如何确定换入、换出变量一般选择正系数最大的那个非基变量x为换入变量将它换到基变量中同时还要确定基变量中哪一个换出来成为非基变量。可按以下方法来确定换出变量:分析()式当将x定为换入变量后必须从x,x,x中确定一个换出变量并保证其余的变量仍然非负即x,x,x。举例清华大学出版社*举例如何确定换入、换出变量当x=时由()式得到举例清华大学出版社*举例如何确定换入、换出变量当x取何值时才能满足非负要求呢?从()式可看出只有选择x=min(,,)=时才能使()式成立。因当x=时基变量x=这就决定用x去替换x。以上数学描述说明每生产一件产品Ⅱ需要用掉的各种资源数为()。由这些资源中的薄弱环节就确定了产品Ⅱ的产量。这里就是由原材料B的数量确定了产品Ⅱ的产量x==件。举例清华大学出版社*举例如何确定换入、换出变量为了求得以x,x,x为基变量的一个基可行解和进一步分析问题需将()中x的位置与x的位置对换得到举例清华大学出版社*举例将()式中x的系数列向量变换为单位列向量。其运算步骤是:′=′=′′=,并将结果仍按原顺序排列有:高斯消去法举例清华大学出版社*举例再将()式代入目标函数()式得到举例清华大学出版社*举例从目标函数的表达式()可看到非基变量x的系数是正的说明目标函数值还可以增大即X()还不是最优解。于是再用上述方法确定换入、换出变量继续迭代得到另一个基可行解X()X()=(,,,,)T再经过一次迭代又得到一个基可行解X()X()=(,,,,)T而这时得到目标函数的表达式是:z=xx()再检查()式可见所有非基变量x,x的系数都是负数这说明若要用剩余资源x,x就必须支付附加费用。所以当x=x=时即不再利用这些资源时目标函数达到最大值。所以X()是最优解。即当产品Ⅰ生产件产品Ⅱ生产件时工厂可以得到最大利润。小结清华大学出版社*小结通过上例可将每步迭代得到的结果与图解法做一对比。例的线性规划问题是二维的即有两个变量x,x。当加入松弛变量x,x,x后变换为高维的。这时可以想象满足所有约束条件的可行域是高维空间中的凸多面体(凸集)。该凸多面体上的顶点就是基可行解。初始基可行解为X()=(,,,,)T对应于图中的原点()X()=(,,,,)T对应于图中的Q点()X()=()T对应于Q点()最优解X()=()T相当于图中的Q点()。从初始基可行解X()开始迭代依次得到X()X()X()相当于图中的目标函数平移时从点开始首先碰到Q然后碰到Q最后达到Q。初始基可行解的确定清华大学出版社*初始基可行解的确定为了确定初始基可行解要首先找出初始可行基其方法如下。()直接观察()加松弛变量()加非负的人工变量初始基可行解的确定清华大学出版社*初始基可行解的确定从线性规划问题的系数构成的列向量Pj(j=,,…,n)中通过直接观察找出一个初始可行基()直接观察初始基可行解的确定清华大学出版社*初始基可行解的确定对所有约束条件为“”形式的不等式利用化标准型的方法在每个约束条件的左端加上一个松弛变量。经过整理重新对xj及aij(i=,,…,mj=,,…,n)进行编号则可得下列方程组(x,x,…,xm为松弛变量):()加松弛变量初始基可行解的确定清华大学出版社*初始基可行解的确定于是()中含有一个mm阶单位矩阵初始可行基B即可取该单位矩阵。将()式每个等式移项得初始基可行解的确定清华大学出版社*初始基可行解的确定令xm=xm=…=xn=由()式可得xi=bi(i=,,…,m)得到一个初始基可行解。又因bi(在节中已做过规定)所以得到一个初始基可行解X=(x,x,…,xm,…)Tnm个=(b,b,…,bm,…)Tnm个初始基可行解的确定清华大学出版社*初始基可行解的确定对所有约束条件为“”形式的不等式及等式约束情况若不存在单位矩阵时可采用人造基方法。即对不等式约束减去一个非负的剩余变量再加上一个非负的人工变量对于等式约束再加上一个非负的人工变量这样总能在新的约束条件系数构成的矩阵中得到一个单位矩阵。()加非负的人工变量最优性检验与解的判别清华大学出版社*最优性检验与解的判别由于线性规划问题的求解可能出现唯一最优解、无穷多最优解、无界解和无可行解等四种情况因此需要建立解的判别准则。一般情况下经过迭代后()式变成最优性检验与解的判别清华大学出版社*最优性检验与解的判别将代入目标函数()式整理后得最优性检验与解的判别清华大学出版社*最优性检验与解的判别令最优性检验与解的判别清华大学出版社*最优性检验与解的判别若为对应于基B的一个基可行解且对于一切j=m,…,n有σj则X()为最优解。称σj为检验数。最优解的判别定理最优性检验与解的判别清华大学出版社*最优性检验与解的判别若为一个基可行解对于一切j=m…,n有σj又存在某个非基变量的检验数σmk=则线性规划问题有无穷多最优解。证:只需将非基变量xmk换入基变量中找到一个新基可行解X()。因σmk=由()知z=z故X()也是最优解。由节的定理可知X()和X()连线上所有点都是最优解。无穷多最优解判别定理最优性检验与解的判别清华大学出版社*最优性检验与解的判别若为一基可行解有一个σmk>并且对i=,,…m有a‘i,mk那么该线性规划问题具有无界解(或称无最优解)。证:构造一个新的解X()它的分量为.无界解判别定理最优性检验与解的判别清华大学出版社*最优性检验与解的判别因所以对任意的λ>都是可行解把x()代入目标函数内得到z=zλσmk因σmk>故当λ则z故该问题目标函数无界。最优性检验与解的判别清华大学出版社*最优性检验与解的判别其它情形以上讨论都是针对标准型的即求目标函数极大化时的情况。当要求目标函数极小化时一种情况是将其化为标准型。如果不化为标准型只需在上述点中把σj改为σj第点中将σmk>改写为σmk<即可。基变换清华大学出版社*基变换若初始基可行解X()不是最优解及不能判别无界时需要找一个新的基可行解。具体做法是从原可行解基中换一个列向量(当然要保证线性独立)得到一个新的可行基称为基变换。为了换基先要确定换入变量再确定换出变量让它们相应的系数列向量进行对换就得到一个新的基可行解。换入变量的确定清华大学出版社*换入变量的确定由()式可知当某些σj>时若xj增大则目标函数值还可以增大。这时需要将某个非基变量xj换到基变量中去(称为换入变量)。若有两个以上的σj>那么选哪个非基变量作为换入变量呢为了使目标函数值增加得快从直观上看应选σj>中的较大者即由应选择xk为换入变量。换出变量的确定清华大学出版社*换出变量的确定设PP…Pm是一组线性独立的向量组它们对应的基可行解是X()将它代入约束方程组()得到其他的向量Pm,Pm,…,Pmt,…,Pn都可以用PP…Pm线性表示。若确定非基变量Pmt为换入变量必然可以找到一组不全为的数(i=,,…,m)使得换出变量的确定清华大学出版社*换出变量的确定在()式两边同乘一个正数θ然后将它加到()式上得到换出变量的确定清华大学出版社*换出变量的确定换出变量的确定清华大学出版社*换出变量的确定换出变量的确定清华大学出版社*换出变量的确定新的基可行解为换出变量的确定清华大学出版社*换出变量的确定由此得到由X()转换到X()的各分量的转换公式换出变量的确定清华大学出版社*换出变量的确定这里是原基可行解X()的分量是新基可行解X()的各分量βi,mt是换入向量Pmt对应原来一组基向量的坐标。现在的问题是这个新解X()的m个非零分量对应的列向量是否独立事实上因为X()的第一个分量对应于X()的相应分量是零即换出变量的确定清华大学出版社*换出变量的确定成立。又因将()式减()式得到换出变量的确定清华大学出版社*换出变量的确定由于上式中至少有βl,mt所以上式表明PP…Pm是线性相关这与假设相矛盾。由此可见X()的m个非零分量对应的列向量Pj(j=,,…,m,jl)与Pmt是线性独立的即经过基变换得到的解是基可行解。实际上从一个基可行解到另一个基可行解的变换就是进行一次基变换。从几何意义上讲就是从可行域的一个顶点转向另一个顶点。迭代(旋转运算)清华大学出版社*迭代(旋转运算)上述讨论的基可行解的转换方法是用向量方程描述的在实际计算时不太方便因此下面介绍系数矩阵法。考虑以下形式的约束方程组一般线性规划问题的约束方程组中加入松弛变量或人工变量后很容易得到上述形式迭代(旋转运算)清华大学出版社*迭代(旋转运算)设x,x,…,xm为基变量对应的系数矩阵是mm单位阵I它是可行基。令非基变量xm,xm,…,xn为零即可得到一个基可行解。若它不是最优解则要另找一个使目标函数值增大的基可行解。这时从非基变量中确定xk为换入变量。显然这时θ为在迭代过程中θ可表示为其中是经过迭代后对应于的元素值。迭代(旋转运算)清华大学出版社*迭代(旋转运算)按θ规则确定xl为换出变量xk,xl的系数列向量分别为迭代(旋转运算)清华大学出版社*迭代(旋转运算)为了使xk与xl进行对换须把Pk变为单位向量这可以通过()式系数矩阵的增广矩阵进行初等变换来实现。迭代(旋转运算)清华大学出版社*迭代(旋转运算)变换的步骤是:()将增广矩阵()式中的第l行除以alk得到()将()式中xk列的各元素除alk变换为以外其他都应变换为零。其他行的变换是将()式乘以aik(il)后从()式的第i行减去得到新的第i行。迭代(旋转运算)清华大学出版社*迭代(旋转运算)由此可得到变换后系数矩阵各元素的变换关系式是变换后的新元素。迭代(旋转运算)清华大学出版社*迭代(旋转运算)()经过初等变换后的新增广矩阵是迭代(旋转运算)清华大学出版社*迭代(旋转运算)()由()式中可以看到x,x,…,xk,…xm的系数列向量构成mm单位矩阵它是可行基。当非基变量xm,…xl,…,xn为零时就得到一个基可行解X()在上述系数矩阵的变换中元素alk称为主元素它所在列称为主元列它所在行称为主元行元素alk位置变换后为。迭代(旋转运算)清华大学出版社*迭代(旋转运算)例试用上述方法计算例的两个基变换。解:例的约束方程组的系数矩阵写成增广矩阵当以x,x,x为基变量x,x为非基变量令x,x=可得到一个基可行解X()=(,,,,)T迭代(旋转运算)清华大学出版社*迭代(旋转运算)现用x去替换x于是将x,,x,x的系数矩阵变换为单位矩阵经变换后为令非基变量x,x=得到新的基可行解X()=(,,,,)T第节单纯型法的计算步骤清华大学出版社*第节单纯型法的计算步骤单纯型表计算步骤单纯型表清华大学出版社*单纯型表为了便于理解计算关系现设计一种计算表称为单纯形表其功能与增广矩阵相似。将()式与目标函数组成n个变量m个方程的方程组。线性规划的方程组清华大学出版社*线性规划的方程组线性规划的方程组清华大学出版社*线性规划的方程组为了便于迭代运算可将上述方程组写成增广矩阵形式线性规划的方程组清华大学出版社*线性规划的方程组若将z看作不参与基变换的基变量它与x,x,…,xm的系数构成一个基这时可采用行初等变换将c,c,…,cm变换为零使其对应的系数矩阵为单位矩阵。得到表线性规划的方程组清华大学出版社*线性规划的方程组表的说明XB列中填入基变量这里是xx,…xmCB列中填入基变量的价值系数这里是c,c,…,cm它们是与基变量相对应的b列中填入约束方程组右端的常数cj行中填入基变量的价值系数c,c,…,cnθi列的数字是在确定换入变量后按θ规则计算后填入最后一行称为检验数行对应各非基变量xj的检验数是计算步骤清华大学出版社*计算步骤表称为初始单纯形表每迭代一步构造一个新单纯形表。计算步骤:()按数学模型确定初始可行基和初始基可行解建立初始单纯形表。()计算各非基变量xj的检验数检查检验数若所有检验数则已得到最优解可停止计算。否则转入下一步。计算步骤清华大学出版社*计算步骤()在σj>,j=m,…,n中若有某个σk对应xk的系数列向量Pk则此问题是无界停止计算。否则转入下一步。()根据max(σj>)=σk确定xk为换入变量按θ规则计算计算步骤清华大学出版社*计算步骤()以alk为主元素进行迭代(即用高斯消去法或称为旋转运算)把xk所对应的列向量将XB列中的xl换为xk得到新的单纯形表。重复()~()直到终止。计算步骤清华大学出版社*计算步骤现用例的标准型来说明上述计算步骤()取松弛变量x,x,x为基变量它对应的单位矩阵为基。这就得到初始基可行解X()=(,,,,)T将有关数字填入表中得到初始单纯形表见表。表中左上角的cj是表示目标函数中各变量的价值系数。在CB列填入初始基变量的价值系数它们都为零。计算步骤清华大学出版社*计算步骤表计算步骤清华大学出版社*计算步骤计算非基变量的检验数各非基变量的检验数为σ=cz=()=σ=cz=()=填入表的底行对应非基变量处。计算步骤清华大学出版社*计算步骤它所在行对应的x为换出变量x所在列和x所在行的交叉处称为主元素或枢元素(pivotelement)计算步骤清华大学出版社*计算步骤()以为主元素进行旋转运算或迭代运算即初等行变换使P变换为(,,)T,在XB列中将x替换x,于是得到新表换人变量换出变量主元素计算步骤清华大学出版社*计算步骤()检查表的所有cjzj,这时有cz=说明x应为换入变量。重复()~()的计算步骤得表。换人变量换出变量主元素因为还存在检验数>继续进行迭代。计算步骤清华大学出版社*计算步骤()表最后一行的所有检验数都已为负或零。这表示目标函数值已不可能再增大于是得到最优解X*=X()=(,,,,)T目标函数的最大值z*=第节单纯形法的进一步讨论清华大学出版社*第节单纯形法的进一步讨论人工变量法退化检验数的几种表示形式人工变量法清华大学出版社*人工变量法设线性规划问题的约束条件其中没有可作为初始基的单位矩阵则分别给每一个约束方程加入人工变量xn,…,xnm得到人工变量法清华大学出版社*人工变量法以xn,…xnm为基变量并可得到一个mm单位矩阵。令非基变量x,…,xn为零便可得到一个初始基可行解X()=(,,…,,b,b,…,bm)T因为人工变量是后加入到原约束条件中的虚拟变量要求经过基的变换将它们从基变量中逐个替换出来。基变量中不再含有非零的人工变量这表示原问题有解。若在最终表中当所有cjzj而在其中还有某个非零人工变量这表示原问题无可行解。以下讨论如何解含有人工变量的线性规划问题。人工变量法清华大学出版社*人工变量法例现有线性规划问题试用大M法求解。大M法人工变量法清华大学出版社*人工变量法解在上述问题的约束条件中加入松弛变量x剩余变量x人工变量x,x得到这里M是一个任意大的正数。人工变量法清华大学出版社*人工变量法因本例的目标函数是要求min所以用所有cjzj来判别目标函数是否实现了最小化用单纯形法进行计算时见表。人工变量法清华大学出版社*人工变量法在表的最终计算结果可看出已得到最优解:x=,x=,x=x=x=x=x=目标函数z=人工变量法清华大学出版社*人工变量法以下介绍求解含有人工变量线性规划问题的两阶段法。第一阶段:不考虑原问题是否存在基可行解给原线性规划问题加入人工变量并构造仅含人工变量的目标函数和要求实现最小化。两阶段法人工变量法清华大学出版社*人工变量法第一阶段:不考虑原问题是否存在基可行解给原线性规划问题加入人工变量并构造仅含人工变量的目标函数和要求实现最小化。如人工变量法清华大学出版社*人工变量法第一阶段求解用单纯形法求解上述模型。若得到的最有值w=说明原问题存在基可行解可以进行第二段计算。否则原问题无可行解应停止计算。第二阶段求解从第一阶段计算得到的最终表中除去人工变量将目标函数行的系数换为原问题的目标函数系数作为第二阶段计算的初始表。各阶段的计算方法及步骤与第节介绍的单纯形法相同。人工变量法清华大学出版社*人工变量法例试用两阶段法求解如下线性规划问题:人工变量法清华大学出版社*人工变量法解:先在上述线性规划问题的约束方程中加入人工变量给出第一阶段的数学模型为:人工变量法清华大学出版社*人工变量法第一阶段用单纯形法求解见表。求得的结果是w=最优解是x=,x=,x=,x=,x=x=x=因为人工变量x=x=所以()T是原线性规划问题的基可行解。于是可以进行第二阶段运算。将第一阶段的最终表中的人工变量取消填入原问题的目标函数系数进行第二阶段计算见表。人工变量法清华大学出版社*人工变量法表人工变量法清华大学出版社*人工变量法表从表得到最优解:x=,x=,x=,目标函数值z=退化清华大学出版社*退化在单纯形法计算中用θ规则确定换出变量时有时存在两个以上相同的最小比值这样在下一次迭代中就有一个或几个基变量等于零这就出现了退化解。这时换出变量xl=迭代后目标函数值不变。这时不同基表示为同一顶点。有人构造了一个特例当出现退化时进行多次迭代而基从B,B…又返回到B即出现计算过程的循环便永远达不到最优解。退化清华大学出版社*退化尽管实际计算过程中循环现象极少出现但还是有可能发生的。如何解决这问题先后有人提出了“摄动法”“字典序法”。年由勃兰特(Bland)提出一种简便的规则简称勃兰特规则:()选取cjzj>中下标最小的非基变量xk为换入变量即k=min(j|cjzj>)()当按θ规则计算存在两个和两个以上最小比值时选取下标最小的基变量为换出变量。按勃兰特规则计算时一定能避免出现循环。检验数的几种表示形式清华大学出版社*检验数的几种表示形式本书以maxz=CXAX=bX为标准型以cjzj(j=,,…,n)作为最优解的判别准则。由于还有其他形式的问题为了避免混淆将有关情况归纳如下:设x,x,…,xm为约束方程的基变量于是可得检验数的几种表示形式清华大学出版社*检验数的几种表示形式将它们代入目标函数后可有两种表达形式判别准则的选择清华大学出版社*判别准则的选择当要求目标函数实现最大化时若用()式来分析就需要用cjzj,(j=,…,n)作为判别准则若用()式来分析就需要用zjcj,(j=,,…,n)作为判别准则。当要求目标函数实现最小化时可用()式或()式来分析这时可分别用cjzj或zjcj(j=,,…,n)来判别目标函数是否已达到最小。几种判别准则的汇总清华大学出版社*几种判别准则的汇总单纯形法小结清华大学出版社*单纯形法小结() 根据实际问题给出数学模型列出初始单纯形表。进行标准化见表。分别以每个约束条件中的松弛变量或人工变量为基变量列出初始单纯形表。表第节 应用举例清华大学出版社*第节 应用举例一般讲一个经济、管理问题凡满足以下条件时才能建立线性规划模型。()要求解问题的目标函数能用数值指标来表示且为线性函数()存在着多种方案及有关数据()要求达到的目标是在一定约束条件下实现的这些约束条件可用线性等式或不等式来描述。第节 应用举例清华大学出版社*第节 应用举例例合理利用线材问题。现要做套钢架每套需用长为mm和m的元钢各一根。已知原料长m问应如何下料使用的原材料最省。解:最简单做法是在每一根原材料上截取mm和m的元钢各一根组成一套每根原材料剩下料头m(=)。为了做套钢架需用原材料根共有m料头。若改为用套裁这可以节约原材料。下面有几种套裁方案都可以考虑采用。见表。表第节 应用举例清华大学出版社*第节 应用举例为了得到套钢架需要混合使用各种下料方案。设按Ⅰ方案下料的原材料根数为x,Ⅱ方案为xⅢ方案为xⅣ方案为x,Ⅴ方案为x。根据表的方案可列出以下数学模型:第节 应用举例清华大学出版社*第节 应用举例在以上约束条件中加入人工变量x,x,x然后用表进行计算。表第节 应用举例清华大学出版社*第节 应用举例第次计算第节 应用举例清华大学出版社*第节 应用举例第次计算第节 应用举例清华大学出版社*第节 应用举例最终计算表(第次计算)由计算得到最优下料方案是:按Ⅰ方案下料根Ⅱ方案下料根Ⅳ方案下料根。即需根原材料可以制造套钢架。有非基变量的检验数为零所以存在多重最优解。第节 应用举例清华大学出版社*第节 应用举例例(配料问题)某工厂要用三种原材料C、P、H混合调配出三种不同规格的产品A、B、D。已知产品的规格要求产品单价每天能供应的原材料数量及原材料单价分别见表和表。该厂应如何安排生产使利润收入为最大解:如以AC表示产品A中C的成分AP表示产品A中P的成分依次类推。表第节 应用举例清华大学出版社*第节 应用举例根据表有:这里ACAPAH=ABCBPBH=B()将()逐个代入()并整理得到第节 应用举例清华大学出版社*第节 应用举例表表明这些原材料供应数量的限额。加入到产品A、B、D的原材料C总量每天不超过kgP的总量不超过kgH总量不超过kg。表第节 应用举例清华大学出版社*第节 应用举例由此得约束条件ACBCDCAPBPDPAHBHDH在约束条件中共有个变量为计算和叙述方便分别用x,…,x表示。令x=Ac,x=Ap,x=AH,x=BC,x=BP,x=BH,x=DC,x=DP,x=DH第节 应用举例清华大学出版社*第节 应用举例约束条件可表示为:第节 应用举例清华大学出版社*第节 应用举例目标函数目的是使利润最大即产品价格减去原材料的价格为最大。产品价格为:(xxx)产品A(xxx)产品B(xxx)产品D原材料价格为:(xxx)原材料C(xxx)原材料P(xxx)原材料H为了得到初始解在约束条件中加入松弛变量x~x得到数学模型:第节 应用举例清华大学出版社*第节 应用举例例的线性规划模型第节 应用举例清华大学出版社*第节 应用举例最优解用单纯形法计算经过四次迭代得最优解为:x=,x=,x=这表示:需要用原料C为kgP为kgH为kg构成产品A。即每天只生产产品A为kg分别需要用原料C为kgP为kgH为kg。从最终计算表中得到总利润是z=元天。第节 应用举例清华大学出版社*第节 应用举例例生产与库存的优化安排问题某工厂生产五种产品(i=,…,)上半年各月对每种产品的最大市场需求量为dij(i=,…,j=,…,)。已知每件产品的单件售价为Si元生产每件产品所需要工时为ai单件成本为Ci元该工厂上半年各月正常生产工时为rj(j=,…,)各月内允许的最大加班工时为rj′Ci′为加班单件成本。又每月生产的各种产品如当月销售不完可以库存。库存费用为Hi(元件月)。假设月初所有产品的库存为零要求月底各产品库存量分别为ki件。现要求为该工厂制定一个生产计划在尽可能利用生产能力的条件下获取最大利润。第节 应用举例清华大学出版社*第节 应用举例解:设xij和xij′分别为该工厂第i种产品的第j个月在正常时间和加班时间内

职业精品

用户评论

0/200
    暂无评论

精彩专题

上传我的资料

热门资料

资料评价:

/168
1下载券 下载 加入VIP, 送下载券

意见
反馈

返回
顶部

Q