运筹学-第四版-第二章-线性规划及单纯形法

线性规划及单纯形法线性规划及单纯形法线性规划问题及其数学模型图解法单纯形法原理单纯形法的计算步骤第一节线性规划问题及其数学模型一、问题的提出线性规划主要解决：如何利用现有有限的资源，使得预期目标达到最优的问题。例1某工厂在计划期内要安排生产A、B两种产品（假定产品畅销）。已知生产单位产品的利润与所需的劳动力、设备台时及原材料的消耗，如表1.1所示问该厂应如何安排生产使获利最大？表1-1,1x2x产品A产品B资源限量劳动力设备原材料9434510360200300利润元/kg70120问题要求给出一个方案(产品A生产多少；产品B生产多少)设该工厂生产A、B两种产品产量分别为确定决策变量表1-1产品A产品B资源限量劳动力设备原材料9434510360200300利润元/kg70120制定方案的目标是什么？该厂获取的利润可表示为2112070xxZ问题的目标：2112070maxxxZ确定目标函数利润最大化表1-1产品A产品B资源限量劳动力设备原材料9434510360200300利润元/kg70120方案的制定受到那些现实条件制约：人力资源（劳动力）的限制：3604921xx设备工时的限制：2005421xx原材料资源的限制：30010321xx此外，决策变量的取值不应为负值即0,021xx确定约束条件2112070maxxxZ其中目标函数约束条件资源约束非负约束约束条件可记s.t(subjectto),意思为“以…为条件“、”假定“、”满足“之意。121212129436045200..310300,0xxxxstxxxx综上所述，我们得到了这个问题的数学模型建立问题的线性规划模型步骤1确定决策变量决策变量是模型所要决定的未知量，也是模型最重要的参数它用以表明规划中的用数量表示的方案、措施，可由决策者决定和控制2确定目标函数就是将决策者所追求的目标表示为决策变量的函数它决定了线性规划优化的方向，是线性规划的重要组成部分3确定约束条件这些约束条件可用含有决策变量的等式或不等式来表示例2给海狸鼠配饲料饲料中营养要求：Va每天至少700克，Vb每天至少30克，VC每天刚好200克。现有五种饲料，搭配使用，饲料成分如下表：饲料VaVbVc价格元/KG资源量IIIIIIIVV32161810.50.220.50.510.220.8274955060507040营养要求70030200问：应如何搭配饲料，使费用最小？确定决策变量：设抓取饲料Ix1kg;饲料IIx2kg;饲料IIIx3kg……确定目标函数：minZ=2x1+7x2+4x3+9x4+5x5确定约束条件：3x1+2x2+x3+6x4+18x5≥700x1+0.5x2+0.2x3+2x4+0.5x5≥300.5x1+x2+0.2x3+2x4+0.8x5=200x1≤50,x2≤60,x3≤50,x4≤70,x5≤40x1≥0,x2≥0,x3≥0,x4≥0,x5≥0营养要求用量要求非负约束综上所述，便得到如下的数学模型：0,0,0,0,040,70,50,60,502008.022.05.0305.022.05.070018623..59472min543215432154321543215432154321xxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxZ美佳公司计划制造Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试工序及每天可用于这两种家电的能力、各售出一件时的获利情况，如表1-2所示。问该公司应制造两种家电各多少件，使获取的利润最大？课堂练习项目ⅠⅡ每天可用能力设备A(h)设备B(h)调试工序(h)06152115245利润（元）21表1-2其数学模型为：212maxxxZ0,524261552121212xxxxxxx例3：捷运公司在下一年度的1～4月份的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于下表1-3。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1-4。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租用期限不同的合同。试确定该公司签订租借合同的最优决策，目的是使所租借费用最少。月份1234所需仓库面积15102012表1-3表1-4合同租借期限1个月2个月3个月4个月合同期内的租费2800450060007300单位：100m2单位；元/100m2月份1234所需仓库面积15102012表1-2表1-3合同租借期限1个月2个月3个月4个月合同期内的租费2800450060007300单位：100m2单位；元/100m2解：设表示捷运公司在第i(i=1,2,3,4)月初签订的租期为j(j=1,2,3,4)个月的仓库面积的合同（单位为100m2)。ijxⅠⅡⅢⅣⅤ11x12x13x14x21x22x23x31x32x41x∑≥15∑≥10∑≥20∑≥121514131211xxxx10232221141312xxxxxx1241322314xxxx20323123221413xxxxxx2800Z)(41312111xxxx4500)(322212xxx6000)(2313xx147300x经过上面的讨论，得到下面的LP模型：)4,,1;4,,1(012201015.4132231432312322141323222114131214131211jixxxxxxxxxxxxxxxxxxxxxstij)(4500)(2800min32221241312111xxxxxxxZ1423137300)(6000xxx目标函数约束条件①每一个问题都有一组变量---称为决策变量，一般记为下面从数学的角度来归纳上述三个例子的共同点。②每个问题中都有决策变量需满足的一组约束条件---线性的等式或不等式。.,,,21nxxx对决策变量每一组值：Tnxxx),,()0()0(2)0(1代表了一种决策方案。通常要求决策变量取值非负，即).,2,1(,0nixi二。线性规划问题的数学模型③都有一个关于决策变量的线性函数---称为目标函数。要求这个目标函数在满足约束条件下实现最大化或最小化。我们将约束条件和目标函数都是决策变量的线性函数的规划问题称为线性规划。有时也将线性规划问题简记为LP（linearprogramming)其数学模型为：nnxcxcxcZ2211max(min)),,2,1(,0),(),(),(.22112222212111212111njxbxaxaxabxaxaxabxaxaxatsjmnmnmmnnnn上述模型的简写形式为：njjjxcZ1max(min)),,2,1(0),,2,1(),(.1njxmibxatsjnjijij若令);,,,(21ncccC;21nxxxX;21mbbbb),,,(21212222111211nmnmmnnPPPaaaaaaaaaA线性规划问题可记为矩阵和向量的形式：CXZmax(min)0),(.XbAXtsCXZmax(min)0),(.1XbxPtsnjjj用向量表示时，上述模型可写为：三。线性规划问题的标准形式：LP问题的数学模型的标准形式为：nnxcxcxcZ2211max),,2,1(,0.22112222212111212111njxbxaxaxabxaxaxabxaxaxatsjmnmnmmnnnn其中常数项,0ib),,2,1(miLP问题标准形式的特征是：⑴求目标函数的最大值；⑵约束条件为等式；⑶决策变量非负。下面分析如何将LP问题标准化：⑴若目标函数为nnxcxcxcZ2211min引进新的目标函数,ZZ则Z的最小值即为Z的最大值，即：ZZmaxmin从而目标函数变换为：nnxcxcxcZ2211max（2）若约束条件为不等式，分为两种情况讨论：njjjijnjbxa1)...2,1(加入松弛变量njjjijnjbxa1)...2,1(加入剩余变量（3）对于决策变量非负的要求，分为两种情况讨论：①非正变量：即xk≤0令xkˊ=-xk即可②自由变量：即xk无约束令xk=xkˊ－xk〞例1将LP问题3212minxxxZ)2,1(0222.31321ixxxxxxtsi化为标准形。解：引进新的目标函数,ZZ于是原LP问题化为标准形式：)2,1(0222.31321ixxxxxxtsi3212maxxxxZ例2将LP问题0,03001032005436049..12070max2121212121xxxxxxxxtsxxZ0,0,00,03001032005436049..00012070max5432152142132154321xxxxxxxxxxxxxxtsxxxxxZ，＋化为标准形。松弛变量例3将LP问题0,03001032005436049..12070max2121212121xxxxxxxxtsxxZ0,0,00,03001032005436049..00012070max5432152142132154321xxxxxxxxxxxxxxtsxxxxxZ，＋化为标准形。剩余变量例4将LP问题无约束32132132132132100533229.32minxxxxxxxxxxxxtsxxxz化为标准形。0,0,0,0,0,05)(332)(29)(00)(32max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxstxxxxxxZ课堂练习例4将LP问题1234123412341234min3425422214.2321,2,30,4Zxxxxxxxxxxxxstxxxxxxxx无约束化为标准形。我们得到例4的标准形为：21420,0,0,,)(32)(2)(24..00)(5243max6544321644321544321443216544321xxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxZ§1.2线性规划问题的图解法1.2线性规划图解法所谓图解法，就是在平面直角坐标上画出各个约束条件所允许变化的范围，通过图上作业法求出最优解和目标函数值。一个线性规划问题有解，是指能找出一组xj(j=1,2,…n),满足所有约束条件，称这组xj为问题的可行解。通常线性规划问题总是含有多个可行解，称全部可行解的集合为可行域。在用图解法求解时，可形象的看到可行域。在可行域中使