管理科学基础-1线性规划03课件

1线性规划问题及其数学模型

图解法单纯形法线性规划模型的应用线性规划2

设备产品

A

B

C

D利润（元/件）

P121402

P222043有效台时1281612例：已知信息如右表所示，问如何安排生产才能获得最大利润？模型:maxZ=2x1+3x2

s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12x1≥0,x2≥0线性规划问题及其数学模型3目标函数：约束条件：①②③价值系数技术系数限额系数线性规划数学模型的一般形式4也可以记为如下形式：目标函数：约束条件：5向量形式：决策变量向量价值向量资源向量系数列向量6矩阵形式：系数矩阵7特征：⑴目标函数为求最大值；⑵所有约束条件（非负条件除外）都是等式，右端常数项大于零；⑶变量为非负。①②③线性规划模型的标准形式8标准型转换方式：(1)如果极小化原问题minZ=CX，则令Z'=-Z，转为求maxZ'=-CX(2)若某个bi<0，则以－1乘该约束两端，使之满足非负性的要求。(3)对于≤型约束，在左端加上一个非负松弛变量，使其为等式。(4)对于≥型约束，在左端减去一个非负剩余变量，使其为等式。(5)若某决策变量xk无非负约束，令xk=x'k-x"k

，(x'k≥0,x"k≥0)。9转换方式：

⑴目标函数的转换也就是：令，可得到上式。即如果是求最小值即，则可将目标函数乘以（－1），可化为求最大值问题。10⑵约束条件的转换：由不等式转换为等式。称为松弛变量称为剩余变量11⑶变量的变换例1：将下列线性规划问题化为标准形式为无约束（无非负限制）若存在取值无约束的变量，可令其中：12

解:用x4-x5替换x3，且x4,x5>=0，将第3个约束方程两边乘以（－1），再将最小值问题反号，变为求最大值。标准形式如下：引入变量13例2：将线性规划问题化为标准型为无约束解：作业1将下面的线性规划模型转换成标准形式（标准型）15⑴可行解：满足所有约束条件的解为可行解。所有解的集合称为可行解的集或可行域。⑵最优解：使目标函数达到最优值的可行解。⑶基：若B是矩阵A的一个m×m阶非奇异子矩阵（∣B∣≠0），则B是一个基。则称Pj

(1≤j≤m)为基向量。∴xj(1≤j≤m)为基变量，其他变量为非基变量。线性规划问题的解16

⑷基解(基本解)：非零分量的数目不大于约束方程个数m的解（对应着一个基），最多为个。

⑸基可行解：满足所有非负约束条件的基解

⑹可行基：对应于基可行解的基称为可行基。非可行解可行解基解基可行解17一般有两种方法图解法单纯形法两个变量、直角坐标三个变量、立体坐标适用于任意变量，但需将一般形式变成标准形式线性规划模型的求解方法18

建立直角坐标，图中阴影部分及边界上的点均为其解，是由约束条件来反映的。例一:⑴⑵⑶⑷图解法19012345678123456⑴⑵⑶⑷作图∴最优解：x1=4,x2=2，有唯一最优解，Z=14x2

x1(42)⑴⑵⑶⑷可行域20例二：例三：⑴⑵⑶无穷多最优解⑴⑵无界解x1x1x2

x2

21⑴⑵x1x2

无可行解例四:练习122解的情况唯一解无穷多最优解（多重最优解）无界解无可行解有最优解无最优解23凸集凸集不是凸集顶点线性规划问题的几何意义几个概念：1.凸集2.凸组合3.顶点24是否凸集？abcd25K是n维欧氏空间En的一个点集，若任意两点

的连线上的所有点，则称K为凸集。凸集：凸组合：26顶点：则称X为K的一个顶点（或极点）。27几个定理定理1.

若线性规划问题存在可行域，则其可行域证明.

设28引理1.

线性规划问题的可行解X为基可行解的充要条件是X的正分量对应的系数列向量线性无关。几个定理29定理2.

线性规划问题的基可行解X对应于可行域D的顶点。证明.

不失一般性，设基可行解X的前m个分量为正，则分两步证明：（1）若X不是基可行解，则它不是可行域D的顶点。根据引理1，若X不是基可行解，则其正分量对应的系数列向量

线性相关，即存在不全为0的数使得(1-8)-μ×(1-9)：(1-8)(1-9)几个定理30(1-8)-μ×(1-9)：(1-8)+μ×(1-9)：取当μ充分小时，有几个定理31（2）若X不是可行域D的顶点，则它不是基可行解。因为X不是可行域D的顶点，因此D内存在不同的两点设X是基可行解，对应的向量组线性无关。当j>m时，线性相关，矛盾！几个定理32引理2.

若K是有界凸集，则任何一点可表示为K的顶点的凸组合。定理3.

若可行域D有界，线性规划问题的目标函数一定可以在其可行域的顶点达到最优。几个定理33思路：先找一个基可行解（顶点），如不是最优，继续寻找下一个基可行解（顶点），直到找出最优为止。⑴线性规划问题的可行域（非空）是凸集（凸多边形）。（定理1）⑵若可行域是有界凸集，则最优解一定是在凸集的某一顶点实现（顶点数目不超过个）（定理3）结论：(3)线性规划如果有可行解，则一定有基可行解；如果有最优解，则一定有基可行解是最优解。求解线性规划的一种有效方法（1947，丹捷格/丹齐克），该方法被誉为20世纪十大算法之一。20世纪创造经济效益最多的算法。将模型的一般形式转化成标准形式，再根据标准型从可行域中找一个基可行解，并判断是否最优解。如果不是，继续寻找另一个基可行解，当目标函数达到最优时，得到最优解。基本思想单纯形法35例1：转换成标准型：单纯形法36约束条件的系数矩阵为基变量为非基变量I为单位矩阵37令：则：∴基可行解为（0，0，8，16，12）T

此时，Z=0然后，找另一个基可行解（需要将非基变量换入基变量中，并从基变量中找到一个换出变量）。如此循环下去，直到找到最优解为止。38找出一个初始可行解是否最优转移到另一个目标函数（找更优的基可行解）最优解是否循环结束其步骤总结如下：39为换入变量，令确定换出变量：为换出变量接下来将在x2与x5的位置对换，得到下式：40用高斯消去法，将的系数列向量换为单位列向量，其步骤是：结果是：41即将的系数列向量(2,0,4)T转化为单位列向量(0,0,1)T。此时线性规划变成：42把x2、x3、x4代入目标函数可得：

x1有正系数表明：还有潜力可挖，目标没有达到最大值；此时：令得到另一个基可行解（0，3，2，16，0）T如此循环进行，直到找到最优为止。再迭代两次，得到最优解：（4，2，0，0，4）T根据上式可知所有非基变量的系数都是负数，目标函数达到最大值。初始基可行解的确定最优性检验与解的判别唯一最优解的判别无穷多最优解的判别无界解判别基变换确定换入变量（进基变量）确定换出变量（出基变量或离基变量）

(*)迭代（旋转运算，用高斯消去法进行初等行变换）(*)一般线性规划模型的求解过程1.初始基可行解的确定方法：构造单位矩阵的可行基所有约束条件是“≤”的不等式1.初始基可行解的确定常用方法：构造单位矩阵的可行基所有约束条件是“≤”的不等式1.初始基可行解的确定约束条件是等式人造基方法人工变量1.初始基可行解的确定约束条件是等式人造基方法令非基变量为0，可得初始基解：1.初始基可行解的确定约束条件是“≥”的不等式人工变量2.最优性检验与解的判别2.最优性检验与解的判别（2-25）（2-26）（2-27）检验数2.最优性检验与解的判别最优解的判别定理无穷多最优解的判别定理无界解的判别定理2.最优性检验与解的判别无界解的判别定理证明：进基变量的确定3.基变换选择作为进基变量离基变量的确定最小比值规则：3.基变换4.迭代第l个分量增广矩阵的初等行变换主元素4.迭代主元列主元行增广矩阵的初等行变换4.迭代代数形式的单纯形法：例子

maxZ=3x1+5x2+0x3+0x4+0x52x1+x3=162x2+x4=103x1+4x2+x5=32

x3=16-2x1

x4=10-2x2x5=32-3x1-4x2

maxZ=3x1+5x2

+0x3+0x4+0x5

x3=16x4=10-2x2x5=32-4x2无关x2x22x1=162x2=103x1+4x2=32x1x24812590ABC(4,5)DX0=(0,0,10,10,32)TX1=(0,5,16,0,12)TX1=(4,5,8,0,0)T不断改进，不断追求完美！单纯形法的基本原理最优解解释最优解:X*=(4,5,8,0,0)T松弛变量解释：X3=8,设备A有8小时剩余X4=0,条件（2）等式成立，设备B是瓶颈设备X5=0,条件（3）等式成立，设备C是瓶颈设备61（四）单纯形表6263（四）单纯形表64表格形式的单纯形法：例题2008-9-1ByDr.HuangHuiyu65cj230000cBXBb

x1x2x3x4x5x60000x3x4x5x61281612221000120100400010040001σj0

23000012/28/2－12/4cj230000cBXBb

x1x2x3x4x5x6000x3x4x5

σj3x23010001/42620100-1/2100100-1/2初始单纯形表164000102008-9-1ByDr.HuangHuiyu66cj230000cBXBb

x1x2x3x4x5x60003x3x4x5x26216320100-1/210010-1/2400010010001/4σj-9

20000-3/46/2216/4－cj230000cBXBb

x1x2x3x4x5x60203x3x1x5x22283001-201/210010-1/2000-412010001/44－412σj-13000-201/42008-9-1ByDr.HuangHuiyu67cj230000cBXBb

x1x2x3x4x5x60203x6x1x5x2

4402

002-401101-10000-441001-1/2100σj-1400-1/2-100000-201/4-13σj4－412001-201/2

10010-1/2000-412010001/42283x3x1x5x20203

x1x2x3x4x5x6bXBcB230000cj2008-9-1ByDr.HuangHuiyu68cj230000cBXBb

x1x2x3x4x5x60203x3x1x6

x2

0442001-1-1/4010001/40

000-21/210101/2-1/80σj-14000-3/2-1/80000-201/4-13σj4－412001-201/210010-1/2000-412010001/42283x3x1x5x20203

x1x2x3x4x5x6bXBcB230000cj

maxZ=3x1+5x2+0x3+0x4+0x5=02x1+x3=162x2+x4=103x1+4x2+x5=32

Cj比值CBXBb检验数jx1x2x3x4x535000162010010020103234001x3x4x5000035000-10/2=532/4=8表格单纯形法：例子162010050101/2012300-21x3x2x5050300-5/205-4Cj比值CBXBb检验数jx1x2x3x4x535000检验数j80014/3-2/350101/204100-2/31/3x3x2x1053000-1/2-1最优解:X*=(4,5,8,0,0)T，Z*=37表格单纯形法：例子71

目标函数：max,min

设规划模型约束条件为，需加入人工变量

，而得到一个m×m的单位矩阵，即基向量组合。因人工变量为虚拟变量，且存在于初始基可行解中，需要将它们从基变量中替换出来。若基变量中没有非零的人工变量，表示原问题有解。若当，而还有非零人工变量时，则表示原问题无可行解。如何确定人工变量的目标价值系数而又不影响原来目标函数的取值?两种方法处理：大M法和两阶段法人工变量法72如果是求最小值，人工变量在目标函数中的系数为M（任意大的正数）；如果是求最大值，需取-M。⑴大M法如：73cj-31100MMcBXBbx1x2x3x4x5x6x70x4111-21100011Mx63-4120-1103/2Mx71-20100011σj-3+6M1-M1-3M0M00cBXBbx1x2x3x4x5x6x70x4103-20100-1－Mx610100-11-211x31-2010001－σj-11-M00M03M-174cj-31100MMcBXBbx1x2x3x4x5x6x70x4123001-22-541x210100-11-2－1x31-2010001－σj-2-10001M-1M+1cBXBbx1x2x3x4x5x6x7-3x141001/3-2/32/3-5/31x210100-11-21x390012/3-4/34/3-7/3σj20001/31/3M-1/3M-2/3∴最优解为（4，1，9，0，0）T，Z=－275用计算机处理数据时，只能用很大的数代替M,可能造成计算机上的错误，故多采用两阶段法。

第一阶段：在原线性规划问题中加入人工变量，构造如下模型：⑵两阶段法：76对上述模型求解（单纯形法），若W=0,说明问题存在基可行解，可以进行第二个阶段；否则，原问题无可行解，停止运算。第二阶段：在第一阶段的最终表中，去掉人工变量，将目标函数的系数换成原问题的目标函数系数，作为第二阶段计算的初始纯形表。例：第一阶段：2008-9-1ByDr.HuangHuiyu77cj0000011cBXBbx1x2x3x4x5x6x70x4111-211000111x63-4120-1103/21x71-20100011σj46-1-301000x4103-20100-1－1x610100-11-210x31-2010001－σj10-1001030x4123001-22-50x210100-11-20x31-2010000σj0000001178cj-31100cBXBbx1x2x3x4x50x4123001-241x210100-1－1x31-20100－σj-2-10001-3x141001/3-2/31x210100-11x390012/3-4/3σj20001/31/3第二阶段∴最优解为（4，1，9，0，0）T，目标函数Z=-279退化：计算出的θ（用于确定换出变量）存在有两个以上相同的最小比值，会造成下一次迭代中有一个或几个基变量等于零，这就是退化（会产生退化解）。其特例是出现循环,永远达不到最优解。需用勃兰特规则处理：⑴.选中下标最小的非基变量为换入变量；⑵.当θ中出现两个以上最小值时，选下标最小的基变量为换出变量。80-M0令z′=-ZminZ=－maxz′不处理减去xs加入xa加入人工变量xa加松弛变量xs约束条件两端同乘以-1不处理令

xj

=-xj令xj

=

xj′

-xj″

xj′

≥0xj″

≥0不处理单纯形法图解法、单纯形法求解

xaxs

minZmaxZ≥=≤bi<0

bi

≥0xj

≤0xj无约束xj≥0三个以上两个新加变量系数极大或极小等式或不等式右端项取值个数建立模型根据上表列出初始单纯形表A线性规划小结：81A基变量中有非零的人工变量关于线性规划的进一步讨论Subtitle学习要点线性规划的目标函数和约束条件的表达技巧了解企业管理中典型线性规划问题的数学模型理解灵敏度分析的基本原理和经济意义能够对价值系数和资源数量进行灵敏度分析计划链的层次粗能力计划定单可行不可行CRP主生产计划MPS物料需求计划MRP能力需求计划车间作业计划销售计划可行否作业统计与控制物料清单库存管理外购计划供应商成品、在制品信息生产计划大纲预测当前条件经营计划产值计划或利润计划绝对数量或增长幅度期限:年度单位:万元大类产品销售收入或台套

产品品种和数量如何确定期限:年度单位:万台具体产品在具体时段的出产计划合同订单和预测转换为生产任务将产品出产计划转换成物料需求表大类产品年度生产计划确定产品的品种和数量期限:年度单位:万台线性规划的适用层次某企业存在两个供货源（产地），已知原有供货源每月的供货能力是5万台产品，新增供货源的生产能力可以满足产品的需求，且两个货源的价格相同。有三个区域目标市场（销地或销售商），各销地每月的市场需求量为5万台、10万台、5万台。在分销渠道中，拟定在2个地点中选址设立分销中心，执行产品的转运任务。各地之间的单位运输物流成本（由距离和运输方式决定）如下图所示。应如何选址、调运？线性规划的典型案例——配送中心选择决策变量：设从供货源到分销中心的运输量为，从分销中心到需求市场的运输量为。选址规划在于二者的实际取值。如果，则不设置分销中心；反之，则设置,其规模为如果，则不设置分销中心；反之，则设置，其规模为目标函数：各条路段上的实际运输量乘以物流运输的单位费用之总和最小，即存在供应能力约束、市场需求约束、配送中转约束，如下：线性规划的典型案例——配送中心选择供应能力平衡约束：市场需求平衡约束配送中心不存留产品所有变量大于等于零线性规划的典型案例——配送中心选择例：现要做100套钢架，每套需用长为2.9m，2.1m和1.5m的元钢各一根。已知原料长7.4m，问应如何下料，使用的原材料最省。解：最简单做法是，在每一根原材料上截取2.9m，2.1m和1.5m的元钢各一根组成一套，每根原材料剩下料头0.9m（7.4-2.9-2.1-1.5=0.9)。为了做100套钢架，需用原材料100根，共有90m料头。若改为用套裁，这可以节约原材料。下面有几种套裁方案，都可以考虑采用。线性规划的典型案例——合理下料为了得到100套钢架，需要混合使用各种下料方案。设按Ⅰ方案下料的原材料根数为x1,Ⅱ方案为x2，Ⅲ方案为x3，Ⅳ方案为x4,Ⅴ方案为x5。根据表1-11的方案，可列出以下数学模型：线性规划的典型案例——合理下料例：某建筑公司要用铝型材作为构架，制作100个铝合金窗子，每个窗子需要2.8米的材料3根，1.8米的2根，1.17米的4根，0.6米的4根，原材料每根6米，怎样下料，才能使余料最少?123456789102.810000010101.811203001101.1712200223030.603010161124合计5.775.945.946.006.005.945.745.915.805.91余料0.230.060.06000.060.260.090.200.09下料的可能方案决策x1x2x3x4x5x6x7x8x9x10线性规划的典型案例——合理下料数学模型：设长度为2.8米的材料多余根数为s1，1.8米多余s2，1.17米多余s3，0.6米多余s4。线性规划的典型案例——合理下料例：假定一个成年人每天需要从食物中获得3000千卡的热量、55克蛋白质和800毫克的钙。如果市场上只有四种食品可供选择(当然可以扩充到n种食品)，它们每千克所含的热量和营养成分和市场价格见表2-3。问如何选择才能在满足营养的前提下使购买食品的费用最小？线性规划的典型案例——营养配餐问题建模：设xj为第种食品每天的购入量，则配餐问题的线性规划模型为：线性规划的典型案例——营养配餐问题例：某工厂要用三种原材料C、P、H混合调配出三种不同规格的产品A、B、D。已知产品的规格要求，产品单价，每天能供应的原材料数量及原材料单价，分别见表2-14和表2-15。该厂应如何安排生产，使利润收入为最大?

解：如以AC表示产品A中C的成分，AP表示产品A中P的成分，依次类推。表2-14线性规划的典型案例——配料问题根据表2-14有：这里AC+AP+AH=A；BC+BP+BH=B(1-40)将(1-40)逐个代入(1-39)并整理得到线性规划的典型案例——配料问题表2-15表明这些原材料供应数量的限额。加入到产品A、B、D的原材料C总量每天不超过100kg，P的总量不超过100kg，H总量不超过60kg。表2-15线性规划的典型案例——配料问题由此得约束条件AC+BC+DC≤100AP+BP+DP≤100AH+BH+DH≤60在约束条件中共有9个变量，为计算和叙述方便，分别用x1,…,x9表示。令x1=Ac,x2=Ap,x3=AH,x4=BC,x5=BP,x6=BH,x7=DC,x8=DP,x9=DH.线性规划的典型案例——配料问题约束条件可表示为：线性规划的典型案例——配料问题98目标函数目的是使利润最大，即产品价格减去原材料的价格为最大。产品价格为：50(x1+x2+x3)——产品A35(x4+x5+x6)——产品B25(x7+x8+x9)——产品D原材料价格为：65(x1+x4+x7)——原材料C25(x2+x5+x8)——原材料P35(x3+x6+x9)——原材料H为了得到初始解，在约束条件中加入松弛变量x10～x16，得到数学模型：线性规划的典型案例——配料问题线性规划模型例：某部门在今后五年内考虑给下列项目投资，已知：项目A，从第一年到第四年每年年初需要投资，并于次年末回收本利115%；项目B，第三年初需要投资，到第五年末能回收本利125%，但规定最大投资额不超过4万元；项目C，第二年初需要投资，到第五年末能回收本利140%，但规定最大投资额不超过3万元；项目D，五年内每年初可购买公债，于当年末归还，并加利息6%。该部门现有资金10万元，问它应如何确定给这些项目每年的投资额，使到第五年末拥有的资金的本利总额为最大?线性规划的典型案例——投资问题

解：

(1)确定决策变量这是一个连续投资问题，与时间有关。但这里设法用线性规划方法，静态地处理。以xiA,xiB,xiC,xiD(i=1,2,…，5)分别表示第i年年初给项目A，B，C，D的投资额，它们都是待定的未知变量。表2-17线性规划的典型案例——投资问题(2)投资额应等于手中拥有的资金额

由于项目D每年都可以投资，并且当年末即能回收本息。所以该部门每年应把资金全部投出去，手中不应当有剩余的呆滞资金。因此第一年：该部门年初拥有100000元，所以有x1A+x1D=100000第二年：因第一年给项目A的投资要到第二年末才能回收。所以该部门在第二年初拥有资金额仅为项目D在第一年回收的本息x1D(1+6%)。于是第二年的投资分配是x2A+x2C+x2D=1.06x1D第三年初的资金额是从项目A第一年投资及项目D第二年投资中回收的本利总和：x1A(1+15%)及x2D(1+6%)。于是第三年的资金分配为

x3A+x3B+x3D=