同济大学线性规划教案

线性规划标准型线性规划(LP):minf=c1X1+……cjXj……+cnXn=ΣcjXjs.ta11x1+…+a1jxj+……+a1nxn=b1…ai1x1+…+aijxj+……+ainxn=bi…………am1x1+…+amjxj+……+amnxn=bmxj≥0,j=1,……,n.C=X=b=A=minf=Xs.tAX=bx≥0minf=c1X1+……cjXj……+cnXn=ΣcjXjs.tai1x1+…+aijxj+……+ainxn=bii=1,……,mxj≥0,j=1,……,n.在几何直观上告诉我们，若两个变量的线性规划问题的最优解存在且唯一，则最优解必为可行域K的一个顶点，而K为凸多边形．对于目标函数求min的两个变量的线性规划，根据目标函数的等值线与可行域K的各种关系，我们可以得知它的解可能会出现以下几种情况．最优解存在且唯一．这时，K是一个非空的、有界或无界的凸多边形，最优解X*必为K的一个顶点，最优值f*为一个有限值。(2)最优解x*存往但不唯一．这时，K是一个非空、有界或无界的凸多边形，最优值f*是一个有限值，f的等值线c1x1+c2x2=f*与K之交是K的一个边界，网此该边界上的点都为最优解；但是，我们至少可以取到K的一个顶点为最优解。(3)可行解存在但目标函数值在K内无下界(简称线性规划无下界)．这时，K必是一个非空无界的凸多边形，最优解不存在，minf→∞(4)可行解不存在(或称线性规划不可行)．这时，K为空集。通过以上各种情况的分析，关于2个变量的线性规划的解，我们可以得到以下两点结论：①如果K≠(空集)，则K必是x1ox2坐标平面第一象限内的一个凸多边形(今后，在线性规划理论中，称为凸集)，K的顶点一定存在．②如果最优解X*存在，则最优解中至少有一个为K的顶点．（请学生看书第9页，请教师朗读书上这些结论）§1．3基本可行解非基本变量（独立变量）基本变量（非独立变量）基本解基本可行解基B—若│B│≠O，称B为（LP）的一个基。Minf=c1X1+……cjXj……+cnXn=ΣcjXjs.tai1x1+…+aijxj+……+ainxn=biI=1,……,mxj≥0,j=1,……,n.令=b=X=A=B=minf=Xs.tAX=bx≥0A=IB对应的基本矩阵B：B=矩阵B为基本变量xB,…，xBm在A矩阵中的系数列向量。ai1x1+…+aijxj+……+ainxn=biI=1,……,mw+c1X1+……cjXj……+cnXn=0当IB给定时，将上述方程组变换为典型方程组：xBi+0•w+……+yijXj+……=,i=1,……,mw+……+rjXj+……=–f。 +=i,w+rjXj=–f。-f（X）+rjXj=–f。=f（X。）f（X）=f（X。）+rjxj§1．4单纯形法单纯形法的基本步骤是：求(LP)的初始基本可行解X。，并将(LP)的有关信息制成表格(称为单纯形表)。、判别X。是否为最优解?为此，需要给出一个基本可行解是否为最优解的判别准则。3、若X。不是最优解，则应另求基本可行解xˊ，且使CTXˊCTX。(至少CTXˊ≤CTX。)。同时，我们由X。相应的单纯形表给出xˊ相应的单纯形表。（该步骤称为转轴）(4)当xˊ不是最优解时，视xˊX。，重复上述步骤，直至(LP)求得最优解或判定f在K内无下界。定理1-2（3）如果T（B）中存在rt<0（t∈ID），且对于i=1，…，m均有yit≤0，则（LP）的目标函数在可行域上无下界。§1．5单纯形表的矩阵描述我们前面已经说明过：ai1x1+…+aijxj+……+ainxn=bii=1,……,mw+c1x1+……cjxj……+cnxn=0当IB给定时，将上述方程组变换为典型方程组：xBi+0•w+……+yijxj+……=,i=1,……,mw+……+rjxj+……=–f。这些信息就构成了单纯形表。即 +=w+rjXj=–f。若是记：yj=(y1j,…,yij,…ymj)T，=(由挂图的单纯形表中得到， XB+=,下面我们来推导和yj以及rj的公式。给定IB和基本矩阵B（│B│≠O），假设：A=[B，D]AX=b化成[B，D]=bBXB+DXD=b，两边左乘B-1XB+B-1DXD=B-1bXB+B-1[…，A.j,…]=B-1bXB+=B-1b进行比较可得：yj=B-1A.j,=B-1b由w+……+rjXj+……=–f。得：w+rjXj=–f。现在我们来推导rj的公式。得到由w+c1x1+……+cjxj……+cnxn=0即w+CTX=0，（结合挂图讲解CBT和CDT）w+[CBT，CDT]=0，即w+CBTXB+CDTXD=0由XB+=，得XB=-代入：得到rj=cj-CBTyj=cj-CBTB-1A.jf。=CBT=CBTB-1b请同学看书27页………………yj=B-1A.j=B-1brj=cj-CBTyj=cj-CBTB-1A.jf。=CBT=CBTB-1b§1．7大M法和两阶段法1．7．1大M法minf=s.t.i=1,…,m,xj≥0,j=1,…,n.引进松弛变量xn+1,…,xn+m,minf=s.t.i=1,…,m,xj≥0,j=1,…,n我们取IB={n+1，…，n+m}，由于b≥0,可以很方便地取得一个初始基本可行解。如果我们的规划是下列形式，问题就变得复杂：minf=s.t.≥（=，≤）bi，i=1,…,m,xj≥（=，≤）0,j=1,…,n.将它标准化后，不能够很快地观察出一个初始基本可行解。例1-14minf=-x1-3x2+x3s.t.x1+x2+2x3=4-x1+2x2+x3=4xj≥0,j=1,2，3.人工变量x4和x5x1+x2+2x3+x4=4-x1+2x2+x3+x5=4minf=-x1-3x2+x3+Mx4+Mx5s.t.x1+x2+2x3+x4=4-x1+2x2+x3+x5=4xj≥0,j=1，…，5.（LPM）C-1-31MMCBXBx1x2x3x4x5Mx4x511210-1210144Mr-1-3-3M1-3M00-8MC-1-31MMCBXBx1x2x3x4x5Mx4x511210-1210144Mr-1-3-3M1-3M00-8MXBx1x2x3x4x5x4x23/203/21-1/2-1/211/201/222r-1.5M-2.50-1.5M+2.501.5M+1.5-2M+6Y11=3/2作为转轴元素，带上括弧，得下表：XBx1x2x3x4x5X1X21012/3-1/30111/31/34/38/3r005M+（5/3）M+（2/3）28/3最优解X*=（4/3，8/3，0）T最优值f*=-28/3。15minf=-3x1-2x2s.t.2x1+x2≤23x1+4x2≥12xj≥0,j=1,2.其（LPM）为：minf=-3x1-2x2+Mx5s.t.2x1+x2+x3=23x1+4x2–x4+x5=12xj≥0,j=1,…，5.解：C-3-200MCBXBx1x2x3x4x50Mx3x52（1）100340-11212r-3M-3–4M-20M0-12MCBXBx1x2x3x4x5-2MX2x521100-50-4-1124r5M+104M+2M0-4M+4线性规划不可行。例1-16minf=2x1-x2s.t.2x1+3x2≥6x1-x2≤6xj≥0,j=1,2.其（LPM）为：minf=2x1-x2+Mx5s.t.2x1+3x2-x3+x5=6x1-x2+x4=6xj≥0,j=1,…，5.解：C2-100MCBXBx1x2x3x4x5M0X5X42（3）-1011-101066r2-2M–1-3MM00-6MCBXBx1x2x3x4x5-10X2X42/31-1/301/35/30-1/311/328r8/30-1/30M+1/32R3=-1/3<0，最小比值准则失效可知（LPM）无下界,又人工变量x5=0，因此原线性规划无下界。例1-17minf=-x1+x2+x3-x4s.t.x1-x2-3x3-2x4=2x1+x2-2x4=1xj≥0,j=1,…,4.minf=-x1+x2+x3-x4+Mx5+Mx6s.t.x1-x2-3x3-2x4+x5=2x1+x2-2x4+x6=1xj≥0,j=1,…,6.C-111-1MMCBXBx1x2x3x4x5x6MMx5x61-1-3-210110-20121r-2M-113M+14M-100-3MC-111-1MMCBXBx1x2x3x4x5x6M-1X5X10-2-301-1110-20111r02M+23M+1-302M+1-M+1r4=-3<0，最小比值准则失效可知（LPM）无下界。又由于x5>0，（LP）无可行解。标准型线性规划：minf=s.t.=bi，i=1,…,m,xj≥0,j=1,…,n.引进m个人工变量xn+1,…,xn+m：minf=+s.t.i=1,…,m,xj≥0,j=1,…,nxn+i≥0,i=1,…,m我们取IB={n+1，…，n+m}，由于b≥0,可以很方便地取得一个初始基本可行解：XB=b，XD=0。记XN=（x1，……，n）T，XM=（xn+1，……，xn+m）T，我们得下述定理。(结合书来进行总结)§1．8线性规划应用举例某工厂车间有30个工人，每人每周工作5天，车间每天开工，每天需要的人数是波动的。周i需要人数为ai（i=1，2，3，4，5，6），周日需要人数为a7。现车间调度科希望制定一个计划，以确保休息日不连续的工人数最少，为此，准备建立一个线性规划模型。请你回答下列三个问题：你准备设多少个变量？请列出。列出目标函数。在周一至周日所需人数的七个约束条件中，请列出周一所需人数18人这个约束条件。设xij（共21个）为在第i天、第j天休息的工人数。x13x14x15x16x12x17x24x25x26x27x21x23x35x36x37x31x32x34x41x42x46x47x43x45x51x52x53x57x56x54x61x62x63x64x65x67x72x73x74x75x76x71Minf=x13+x14+x15+x16+x24+x25+x26+x27x35+x36+x37+x46+x47+x57s．t．x24+x25+x26+x27+x23+x34+x35+x36+x37+x45+x46+x47+x57+x56+x67≥18例1—23(生产计划问题)某工厂明年根据合同，每个季度末向销售公司提供产品，有关信息如表。若当季生产的产品过多，季末有积余，则一个季度每积压一吨产品需支付存贮费0．2万元。现该厂考虑明年的最佳生产方案，使该厂在完成合同的情况下，全年的生产费用最低。试建立线性规划模型。季度j生产能力aj(吨)生产成本dj（万元/吨）需求量bj(吨)13015.02024014.02032015.33041014.810(1)设工厂第j季度生产产品xj吨。(2)设第j季度工厂生产的产品为xj吨，第j季度初存贮的产品为yj吨(显然y1=0)。(3)设第i季度生产而用于第j季度末交货的产品数量为xij吨。例1—24(多阶段投资问题)某公司现有资金30万元可用于投资，5年内有下列方案可供采纳：1#方案在年初投资1元，2年后可收回1．3元；2#方案在年初投资1元，3年后可收回1．45元；3#方案：仅在第1年年初有一次投资机会。每投资1元，4年后可收回1．65元；4#方案：仅在第2年年初有一次投资机会。每投资1元，4年后可收回1．7元；5#方案：在年初贷给其他企业，年息为10%，第二年初可收回。每年年初投资所得收益及贷款本金利息也可用作安排。问该公司在5年内怎样使用资金，才能在第6年年初拥有最多资金?解：设Xij为i#方案在第j年年初所使用的资金数。年份（年初）1234561.31.451.651.11.31.451.71.11.31.451.11.31.11.1设Xij为i#方案在第j年年初所使用的资金数。年份（年初）123456x111.3x11x121.45x12x131.65x13x151.1x15x211.3x21x221.45x22x241.7x24x251.1x25x311.3x31x321.45x32x351.1x35x411.3x41x251.1x25X551.1X55x11+x12+x13+x15=300000x21+x22+x24+x25=1.1x15例1-22（混料问题）某糖果厂用原料A、B和C按不同比率混合加工而成甲、乙、丙三种糖果(假设混合加工中不损耗原料)。原料A、B、C在糖果甲、乙、丙中的含量、原料成本、加工成本、原料限量及糖果售价如表所示。问该厂对这三种糖果各生产多少公斤，使得到的利润最大?含量j#糖果原料供应量（公斤）成本(元/公斤)甲（1#）乙（2#）丙（3#）i#原料A≥60%≥15%20002.50B25002.00C≤20%≤60%≤70%22001.70加工成本(元/公斤)2.001.801.60售价(元/公斤)12108设i#原料在j#糖果中的用量为Xij公斤。23（下料问题）用长度为7.4米的圆钢截断成制造某种机床所以需要的3个轴坯，长度分别为2.9米、2.1米和1.5米。现在要制造100台机床，问最少要圆钢多少根？轴坯长度截取方法需要量（米）x1x2x3x4x5x6x72.92.11.5211001002023111032013100100100剩余料头长度（米）0.10.300.21.10.90.8习题一第7题课堂练习某企业年初有现金30万元。该企业有两个方案可供选择：年初贷给其他企业，年息18%，第二年年初可收回；本企业投资扩大再生产，若年初投资一定金额，则第二年还需继续投资金额的60%，而第三年可有等于两年投资额的1。4倍收益。为使第五年年初企业对使用这部分资金有最大的收益，试确定企业每年资金的使用方案。请建立数学模型。习题讨论课讨论第一章习题一第20题（请同学上黑板逐个小问题回答）：XBX1X2X3X4X5X6X5X2X300001β1β310-1/203/21/201β40-1/2β221/21/2rβ500β601/2习题一第六题6．某厂月底安排某一产品在下个月四周的生产计划。估计每件产品在第一周和第二周的生产成本150元，后两周为170元，各周产品需求量分别为700，800，1000，1200件，工厂每周至多生产产品900件，在第二周和第三周可加班，加班生产时每周增产300件，但生产成本每件增加30元，过剩的产品存贮费为每件每周15元，问如何安排生产，使总成本最小？解：(1)设4周生产的产品件数分别为；第2，3周加班生产的件数为：=195x1+180x2+185x3+170x4+210y2+215y3-70500s.t.;;(2)设4周生产的产品件数分别为；第2，3周加班生产的件数为;第2，3，4周初存储量为z2、z3、z4。Minf=150x1+150x2+180y2+15z2+170x3+200y3+15z3+170x4+15z4S．t．x1=700+z2x2+y2+z2=800+z3x3+y3+z3=1000+z4x4+z4=1200；；；习题一、第7题7.某企业年出有现金30万元，该企业有两个方案选择年初贷给其它企业，年息18%，第二年初可以收回本企业投资扩大生产。若年初投资一定金额，则第二年还需要继续投资第一年的60%，而第三年可有等于第二年投资额的1.4倍收益为使第五年年初企业对这部分资金的最大收益，试确定企业每年资金的使用方案，列出数学模型。解：设为该企业在第j年初采用第一方案所使用的资金，为该企业在第j年初采用第二方案所使用的资金年份j(年初)12345