运筹学之线性规划

管理运筹学1第二章线性规划及单纯形法线性规划问题的数学模型图解法模型的标准型及其解与基的概念单纯形法大M法和两阶段法管理运筹学2第二章线性规划问题的数学模型问题的提出例2-1某工厂在计划期内要安排生产I、II两种产品，已知生产单位产品所需设备台时及A、B两种原材料的消耗如表所示。该工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元，问应如何安排计划使该工厂获利最多？ⅠⅡ资源量设备128台时原材料A4016kg原材料B0412kg管理运筹学3解析：设、分别表示在计划期内产品I、II的产量。该工厂的目标是在不超过所有资源限量的条件下，如何确定产量、以得到最大的利润。若用表示利润，该问题可用数学模型表达如下：目标函数约束条件1x2x12max23zxx8221xx1641x1242x0,21xxz管理运筹学4例2-2某农场有男劳力22人，女劳力10人，要求在一天内完成割麦任务30亩，且使除草的亩数最多。已知一个男劳力每天能割麦1.5亩，除草2亩；一个女劳力一天能割麦1.2亩，除草1.4亩。问如何安排现有劳力，既能完成割麦任务，又能使除草的亩数最多？割麦工效（亩/天）除草工效（亩/天）劳力限制量男劳力（人）1.5222女劳力（人）1.21.410任务量（亩）30越多越好管理运筹学5解析：设安排割麦的男女劳力分别为、，安排除草的男女劳力分别为、，在一定的劳力资源限制条件下，既要完成割麦任务，又要使除草越多越好。该问题的数学模型为:目标函数约束条件1x3x2x4x424.12maxxxz2221xx1043xx302.15.131xx)4,3,2,1(0jxj管理运筹学6线性规划（linearprogramming）数学模型的一般形式线性规划数学模型由三个要素构成：决策变量、目标函数和约束条件。nnxcxcxczz2211)max(min或0,,,2122112222212111212111nmnmnmmnnnnxxxbxaxaxabxaxaxabxaxaxa），（或），（或），（或管理运筹学7第二节图解法图解法求解步骤：1、建立平面直角坐标系2、图示约束条件，找出可行域例2-3用图解法求解线性规划目标函数约束条件x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图2-12110050maxxxZ30021xx400221xx2502x0,21xx管理运筹学83、图示目标函数，寻求最优解等值线最优解B（50，250）最优目标值Z=27500x1x2z=20000=50x1+100x2图2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE100/)100/50(12zxx2110050maxxxZ管理运筹学9例2-4某公司共需要可相互替代的A，B两种原料至少350吨，其中A原料至少购进125吨。加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？解：目标函数：Minf=2x1+3x2约束条件：s.t.x1+x2≥350x1≥1252x1+x2≤600x1,x2≥0采用图解法。如下图：得Q点坐标（250，100）为最优解。管理运筹学10例2-4图解法求解线性规划目标函数约束条件最优解Q（250，100）最优值Z=800图2-32132minxxz100200300400500600100200300400600500x1=125x1+x2=3502x1+3x2=8002x1+3x2=9002x1+x2=6002x1+3x2=1200x1x2Q35021xx1251x600221xx0,21xx管理运筹学11例2-5无穷多最优解例2-6无界解1641x8221xx1242x0,21xx2142maxxxz0Q2x1x2Q321maxxxz0,242212121xxxxxx240x1x2管理运筹学12例2-7无可行解线性规划解的结论：1.可行解区域都是“凸”区域。2.最优解在可行解区域的顶点或边界上达到。无界解有可行解唯一解无穷多个解3.解的结果无可行解121xx2123minxxz63221xx0,21xx1210x223x1管理运筹学13第三节线性规划的标准型及其解与基的概念线性规划模型的标准形式标准型的特点1.决策变量非负2.约束条件是等式3.常数项非负4.求目标函数的最小值nnxcxcxcz2211min0,,,;0,,,212122112222212111212111mnmnmnmmnnnnbbbxxxbxaxaxabxaxaxabxaxaxa管理运筹学14非标准型化为标准型1.约束条件为“”时，加一个非负松弛变量；约束条件为“”时，减一个非负松弛变量。松弛变量在目标函数中的系数为零，不影响目标函数值。2.约束条件右端项为负数时，可在方程两端同乘以。3.目标函数为时，可令，把目标函数改为。4.决策变量没有非负要求时，当时，可引入新变量，令；当对无约束要求时，可引入新变量和，令且，。)1(zzzmaxzmin0kx'kxkkxx'kx'kxkx'kkkxxx0'kx0kxib管理运筹学15例2-8把下面的线性规划模型变换为标准形式：解（1）约束条件为不等式，引入松弛变量和，且，原模型可变换为：3212maxxxxz无约束321321321,0,084123xxxxxxxxx4x5x0,54xx3212maxxxxz0,0,0,0841235432153214321,xxxxxxxxxxxxx无约束管理运筹学16续解（2）第一个约束条件右端项为负数，将该方程两端同乘以；（3）该问题的目标函数是要求，令；（4）对于，引入新变量，令；（5）对于无约束，引入新变量和，令则上述模型可变换为：即为原问题的标准型)1(maxzz02x0'2x2'2xx3x0'3x03x3'33xxx3'3'2112minxxxxz0,00,0,0,0841223543'3'2153'3'2143'3'21,xxxxxxxxxxxxxxxx管理运筹学17线性规划模型的解与基线性规划模型向量形式:线性规划模型矩阵形式：式中12(,,,)ncccC12nxxxXmjjjjaaaP2112mbbbb111212122212nnmmmnaaaaaaaaaACXzmin0XbAXCXzmin01XbxPnjjj管理运筹学181.可行解、最优解。满足，的解，称为可行解。全部可行解的集合称为可行域。使目标函数达到最优值的可行解，称为最优解。2.基、典则基。对于，，设的秩为，由的个列向量构成阶方阵，若，则为一个基，或称为一个基矩阵。若为单位矩阵，则称为典则基。3.基变量、非基变量。若变量对应的列向量包含在基中，则称其为基变量；否则称其为非基变量。4.基解、基可行解、基最优解。当一个基确定后，令非基变量等于零，再由方程组解得基变量的唯一解。于是可得方程组的一个解，称为对应于基的基解。若基解满足称为基可行解。使目标函数达到最优值的基可行解，称为基最优解。bAX0XbAXA)(nmm),,,(21nPPPAAm),,,(21mPPPB0BmBjxjPB),,,(21mPPPBbBXBB0XB管理运筹学19第四节单纯性法单纯形法原理例2-9以例2-1为例。首先引入松弛变量，化为标准形式解析：系数矩阵543,,xxx5432100032minxxxxxz)5,,2,1(,0124164825241321jxxxxxxxxj100400100400121),,,,(54321PPPPPA管理运筹学20第一步：寻找初始基可行解。典则基：基变量被非基变量表达令非基变量，得到初始基可行解，同时得到目标函数值100010001),,(543PPPB543,,xxx21,xx251421341241628xxxxxxx021xxTX)12,16,8,0,0()0(0z管理运筹学21第二步：检验所得解用非基变量表示目标函数，由可见目标函数可以进一步减少第三步：确定换入变量（最小负系数原则）和换出变量（最小正比值原则）选择负系数最小的那个非基变量为换入变量。仍为非基变量。令，决定的最大取值和换出变量的取值由第三约束式决定，相应的为换出变量21320xxz2x1x01xjc2x041201602825423xxxxx34/1242/8222xxx3)3,,4min(2x2x5x管理运筹学22第四步：求以为基变量的一个基可行解用表达：用矩阵表达就是:初等变换令非基变量，得到一个基可行解，同时得到目标函数243,,xxx51,xx243,,xxx251421341241628xxxxxxx5214513413416212xxxxxxx1210040160100480012131624/10010010042/10101051xxTX)0,16,2,3,0()1(9z管理运筹学23第五步：检验。若所有，则基可行解为最优解，否则转向第三步。续：用非基变量表示目标函数：确定为换入变量，令，由取为换出变量。0jc2132xxz514329xxz1x05x0304160221413xxxxx11142xxx2),4,2min(1x3x管理运筹学24用非基变量表达基变量和目标函数53,xx421,,xxx52534531413248212xxxxxxxx5214513413416212xxxxxxx514329xxz5341213xxz31624/10010010042/101013824/10010214002/10101管理运筹学25由，决定换出，换入令，得到基可行解和目标函数及其值：即为最优解和最优值。3824/10010214002/101014/15c4)12,4,min(5x5x4x52534531413248212xxxxxxxx43243541812122124414xxxxxxxx043xx24408/12/11012/120004/1001TX)4,0,0,2,4()3(14412314431xxz管理运筹学26单纯形法的计算步骤jcbBcBx1x2x3x4x5x3x4x5xj-2-30000121008404001016-00[4]001123-2-300003x4x2xj01010-1/222040010164-301001/43-20