C类运筹学第2章线性规划1

第一章线性规划与单纯形法1947年G.B.Dantzig提出单纯形法上海交通大学安泰管理学院2第一节线性规划问题及其数学模型问题的提出:在生产管理和经营活动中经常提出一类问题，即如何合理的利用有限的人力、物力、财力等资源，以便得到最好的经济效果。2020/1/11上海交通大学安泰管理学院3例1某工厂在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表1-1所式。该工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元。问应如何安排计划使该工厂获利最多？2020/1/11上海交通大学安泰管理学院42020/1/11上海交通大学安泰管理学院52工作人员安排问题•联邦航空公司2020/1/11上海交通大学安泰管理学院6以上例子可以看出，他们都是一类优化问题。它们的共同特征：(1)每一个问题都用一组决策变量表示某一方案；这组决策变量的值就代表一个具体方案。一般这些变量取值是非负的。),...,,(21mxxx2020/1/11上海交通大学安泰管理学院7(2)存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。(3)都有一个要求达到的目标，它可用决策的线性函数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化。2020/1/11上海交通大学安泰管理学院8满足以上三个条件的数学模型成为线性规划的数学模型。其一般形式为：2020/1/11上海交通大学安泰管理学院9)3.1()2.1(0,,,),(),(),()1.1(max(min)21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxaxcxcxcz满足约束条件：目标函数2020/1/11上海交通大学安泰管理学院10在线性规划的数学模型中，方程（1.1）称为目标函数；（1.2）（1.3）成为约束条件；（1.3）也称为变量的非负约束条件。2020/1/11上海交通大学安泰管理学院11线性规划的图解法.36)(max,6,2:0,78102..46)(max21212212121xfxxxxxxxxxtsxxxf最优解2020/1/11上海交通大学安泰管理学院1212121212max2328416412,0zxxxxxxxx2020/1/11上海交通大学安泰管理学院132020/1/11上海交通大学安泰管理学院14线性规划的解•唯一解•无穷多解•无可行解•无界解•MaxZ=x1+x2•-2x1+x2=4•X1-x2=2•X1=0,x2=02020/1/11上海交通大学安泰管理学院15线性规划问题的几个特点：•线性规划问题的可性解的集合是凸集•线性规划问题的基础可行解一般都对应于凸集的极点•凸集的极点的个数是有限的•最优解只可能在凸集的极点上，而不可能发生在凸集的内部2020/1/11上海交通大学安泰管理学院161122nn1111221nn12112222nn2m11m22mnnm12nmaxZ=cx+cx++cxax+ax++ax=bax+ax++ax=bax+ax++ax=bx,x,x0nijjj1ax,1,2,...,0,1,2,...,ijbimxjnnjjjxC1maxZ=1.2.1线性规划问题的标准形式2020/1/11上海交通大学安泰管理学院17标准型•向量形式•矩阵形式2020/1/11上海交通大学安泰管理学院18变换的方法：•目标函数为min型，价值系数一律反号。令f(x)=-f(x)=-CX,有minf(x)=-max[-f(x)]=-maxf(x)•第i个约束的bi为负值，则该行左右两端系数同时反号，同时不等号也要反向•第i个约束为型，在不等式左边增加一个非负的变量xn+i，称为松弛变量；同时令cn+i=0•第i个约束为型，在不等式左边减去一个非负的变量xn+i，称为剩余变量；同时令cn+i=0•若xj0，令xj=-xj，代入非标准型，则有xj0•若xj不限，令xj=xj-xj，xj0，xj0，代入非标准型2020/1/11上海交通大学安泰管理学院19变换举例：0,,,,,,2004006653004432..0004423)(max:0,,20040065300432..423)(min:65433216332153321433216543321213321321321321xxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxfxxxxxxxxxxxxtsxxxxf标准型不限原非标准型2020/1/11上海交通大学安泰管理学院20线性规划标准型解的若干基本概念：•标准型有n+m个变量，m个约束行•“基”的概念–在标准型中，技术系数矩阵有n+m列，即A=(P1,P2,…,Pn+m)–A中线性独立的m列，构成该标准型的一个基，即B=(P1,P2,…,Pm)，|B|0–P1,P2,…,Pm称为基向量–与基向量对应的变量称为基变量，记为XB=(x1,x2,…,xm)T，其余的变量称为非基变量，记为XN=(xm+1,xm+2,…,xm+n)T，有X=XB+XN–最多有个基2020/1/11上海交通大学安泰管理学院21关于标准型解的若干基本概念：•可行解–满足约束条件和非负条件的解X称为可行解，•基础解–令非基变量XN=0，求得基变量XB的值称为基础解即XB=B-1b–XB是基础解的必要条件为XB的非零分量个数m•基础可行解–基础解XB的非零分量都0时，称为基础可行解，否则为基础非可行解–基础可行解的非零分量个数m时，称为退化解2020/1/11上海交通大学安泰管理学院22线性规划标准型问题解的关系约束方程的解空间基础解可行解非可行解基础可行解退化解2020/1/11上海交通大学安泰管理学院23线性规划几何意义•凸集•凸组合•顶点2020/1/11上海交通大学安泰管理学院24线性规划基本定理•定理1若线性规划问题存在可行域,则其可行域是凸集.•引理线性规划问题的可行解X为基可行解的充要条件是X的正分量对应的系数列向量是线性独立的.•定理2线性规划问题的基可行解X对应于可行域D的顶点•定理3若可行域有界,线性规划问题的目标函数一定可以在其可行域的顶点上达到.2020/1/11上海交通大学安泰管理学院25单纯型法•思路•举例0,,,,1241648200032max54321524132154321xxxxxxxxxxxxxxxxxz2020/1/11上海交通大学安泰管理学院26单纯型法•初始基可行解的确定•最优性检验:–检验数–解的判别•基变换1imijcjciaij2020/1/11上海交通大学安泰管理学院27关于检验数的数学解释•设B是初始可行基，则目标函数可写为两部分(1)•约束条件也写为两部分，经整理得XB的表达式(2)，注意XB中含有非基变量作参数•把XB代入目标函数，整理得到(3)式•第j个非基变量的机会成本如(4)式•若有cj-zj0,则未达到最优(5)(4))3()()()((2))((1))(1'jjmiijijzcaczxfxf检验数机会成本NN1BN1BNN1BNNNN1BNNBBNNBBNNXABCCbBCXAbBCXCXAbBXXAbBXbBXXAXCXC2020/1/11上海交通大学安泰管理学院28标准型的单纯型算法1找初始基础可行基–对于(max,)，松弛变量对应的列构成一个单位阵2检验当前基础可行解是否为最优解–所有检验数cjzj0，则为最优解，否则3确定改善方向–从(cjzj)0中找最大者，选中者称为入变量，xj*–第j*列称为主列4确定入变量的最大值和出变量–最小比例原则(1.2.4)0min**ijijiiaab2020/1/11上海交通大学安泰管理学院29标准型的单纯型算法4确定入变量的最大值和出变量–设第i*行使最小，则第i*行对应的基变量称为出变量，第i*行称为主行5迭代过程–主行i*行与主列j*相交的元素ai*j*称为主元，迭代以主元为中心进行–迭代的实质是线性变换，即要将主元ai*j*变为1，主列上其它元素变为0，变换步骤如下：(1)变换主行nmjaaajijiji,,2,1****2020/1/11上海交通大学安泰管理学院30单纯型表及其格式2020/1/11上海交通大学安泰管理学院31例试列出下面线性规划问题的初始单纯型表0,,12023310032..244540)(max321321321321xxxxxxxxxtsxxxxfx1x2x3x4x5CBXBb404524000x4100231100x512033201OBJ=0zj00000cj-zj404524002020/1/11上海交通大学安泰管理学院32单纯型表中元素的几点说明–任何时候，基变量对应的列都构成一个单位矩阵–当前表中的b列表示当前基变量的解值，通过变换B1b得到(资源已变成产品)–当前非基变量对应的向量可通过变换B1AN得到，表示第j个变量对第i行对应的基变量的消耗率–非基变量的机会成本由给出–注意基变量所对应的行ijamiijijacz1'2020/1/11上海交通大学安泰管理学院33人工变量的引入当约束条件为“”型，引入剩余变量和人工变量•由于所添加的剩余变量的技术系数为1，不能构成初始基变量，为此引入一个人为的变量（注意，此时约束条件已为“=”型），以便取得初始基变量，故称为人工变量•由于人工变量在原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的价值系数应具有惩罚性，称为罚系数。罚系数的取值视解法而定•两种方法–大M法–二阶段法2020/1/11上海交通大学安泰管理学院34解法思路•桥梁•等价2020/1/11上海交通大学安泰管理学院35大M法的求解过程0,,,,,462..)7810max()](max[0,,462..7810)(min65432153216421632132132121321xxxxxxxxxxxxxxtsMxxxxxfxxxxxxxxtsxxxxf2020/1/11上海交通大学安泰管理学院36表1.3.1例1.3.1的单纯型表迭代过程x1x2x3x4x5x6序号CBXBb108700Mbi/aij*Mx66(2)10101(3)7x3411101046M28-2M7M77M7MI初始解cjzj2M3M10M7010x1311/201/201/267x310(1/2)11/211/2(2)371017/273/273/2IIcjzj01/203/27M+3/210x121011118x22012121361086262III最优解cjzj00126M+2答：最优解为x1=2,x2=2,x3=0,OBJ=362020/1/11上海交通大学安泰管理学院37大M法的一些说明–大M法实质上与原单纯型法一样，M可看成一个很大的常数–人工变量被迭代出去后就不会再成为基变量–当检验数都满足最优条件，但基变量中仍有人工变量，说明原线性规划问题无可行解–大M法手算很不方便–因此提出了二阶段法•计算机中常用大M法•二阶段法手算可能容易2020/1/11上海交通大学安泰管理