管理数量方法与分析 第五章 线性规划

第五章线性规划简介管理数量方法与分析第五章线性规划简介5.1线性规划问题的数学模型5.2线性规划问题的基本技巧5.3运输问题5.1线性规划问题的数学模型线性规划是运筹学—规划论的重要分支之一,主要解决的问题：任务确定的情况下,如何统筹安排,使人力、物力用的最少；或者在人力、物力给定的情况下,如何安排使其完成的工作最多.规划论—给定条件下,按照某一衡量指标寻找最优方案,以期合理安排人力物力等有限资源,使经济效果达到最好.线性规划---线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。线性规划的数学模型由三个要素构成决策变量需要我们作出决策或选择的量.一般情况下，题目问什么就设什么为决策变量；用xij(i=1,2,…,m,j=1,2,…,n.)表示。目标函数问题所要达到的目标，并明确是max还是min。约束条件决策变量受到的所有的约束；用等式或不等式表示。5.1线性规划问题的数学模型说明本课程的任务不是对线性规划的理论进行研究与阐述,而仅限于在一定数学模型下,介绍解决线性规划问题的常用的、基本的方法。常用的方法---表上作业法、图上作业法（1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；（2）问题的约束条件是一组多个决策变量的线性不等式或等式。线性规划模型其特征是目标函数约束条件线性规划数学模型的一般形式nnxcxcxcS2211)maxmin(或nixbbbxaxaxabbbxaxaxabbbxaxaxaimmmnmnmmnnnn,,2,10),(),(),(221122222221211111212111或或或特点（1）目标函数求最大值、最小值（2）约束条件都为等式方程或不等式,且右端常数项bi都大于或小于零。（3）决策变量xi为非负。目标函数约束条件线性规划数学模型的一般形式简写为)21(j0)21(i)(Z(min)max11nxmbxaxcjnjijijnjjj例5.1.1（生产计划问题）假设某厂计划生产甲、乙两种产品,其主要原材料有钢材3600kg,铜材2000kg及专用设备能力3000台时,已原材料和设备的单件消耗定额以及单位产品所获利润如下表所示,问如何安排生产方使该厂所获利润最大？甲（件）乙（件）现有材料与设备钢材943600kg铜材452000kg专用设备能力3103000台单位产品利润70120目标函数约束条件2112070maxxxR0,0300010320005436004921212121xxxxxxxx解设甲、乙两种产品的计划产量分别为x1,x2件.由题意知例5.1.2P161例题5.1例5.1.3P162例题5.2例5.1.4P162例题5.35.2线性规划的基本技巧效率比法图解法表上作业法（下一节讲）图上作业法（下一节讲）效率比法生产能力的如何合理分配用此法图解法资源有限的情况下，如何安排生产，使产量最大。本书针对两种产品进行。表示作业法物资调运问题用此法。图上作业法物资调运问题，车辆运输的调度问题。匈牙利算法指派问题与旅行商问题。一、效率比法例5.2.1P163例题5.4解由题意知单位时间的产量比。A1A2A3B1503020B2609080B1/B250/60=10/1230/90=4/1220/80=3/12B2/B16/53/1=15/54/1=20/5由上表知A1生产B1的效率最大，A3生产B2的效率最大.由于配套产品需B1=B2,设A2生产B1用t时间，生产B2用(1-t)时间,则有50+30t=80+90(1-t).1t解之得例5.2.2P187习题4解由题意知单位时间的产量比。甲乙丙A352B181216B/A18/3=612/5=2.416/2=8A/B3/18=1/65/122/16=1/8根据上表知丙生产B的效率最大，乙生产A的效率最大，则丙生产完全B为16件，而乙完全生产A为5件；故甲分配2/3的时间生产A产品，1/3的时间生产B产品，乙完全生产B产品，丙完全生产A由于配套产品需1A=2B,设甲生产A用t时间，生产B用(1-t)时间,则有2(5+3t)=8+18(1-t).3/2t解之得二、图解法这里只分析只有两个决策变量线性规划问题的简单情况,可以通过图解的方法进行求解.图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点.目标函数约束条件其数学模型的一般形式2211)maxmin(xcxcS或2,10),(),(),(2211222222121111212111ixbbbxaxabbbxaxabbbxaxaimmmmm或或或说明1.满足上述约束条件的解（x1,x2）称为线性规划问题的可行解.所有可行解的集合称为可行域或可行解集.使目标函数达到最大（小）可行解（x1,x2）称为此线性规划的最优解.2.由于上述约束条件与目标函数均为二元一次方程或不等式,故利用其几何直观,可以借助于平面直角坐标系,先确定问题所有解,再确定最优解.例5.2.3用图解法求解线性规划问题目标函数212XXSmax约束条件2,108.39.12.109.18.39.18.39.121212121iXXXXXXXXXimaxS=3X1+5.7X2minS=5X1+4X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)4=2X1+X220=2X1+X217.2=2X1+X211=2X1+X2Lo：0=2X1+X2（7.6，2）DmaxSminS此点是唯一最优解，且最优目标函数值maxZ=17.2可行域maxS=2X1+X22,108.39.12.109.18.39.18.39.121212121iXXXXXXXXXimaxS=3X1+5.7X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)（7.6，2）DL0：0=3X1+5.7X2maxS（3.8，4）34.2=3X1+5.7X2蓝色线段上的所有点都是最优解这种情形为有无穷多最优解，但是最优目标函数值maxS=34.2是唯一的。可行域2,108.39.12.109.18.39.18.39.121212121iXXXXXXXXXi•minS=5X1+4X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1+1.9X2=10.2(≤)DL0：0=5X1+4X2maxSminS8=5X1+4X243=5X1+4X2（0，2）可行域此点是唯一最优解X1-1.9X2=-3.8(≥)例5.2.4P164例题5.5约束条件2,104044601052121ixxxxximaxS=6x1+8x2解用x1表示生产甲的件数，用x2表示生产甲的件数。则有目标函数x1x2ox1+x2=10(≤)x1+2x2=12(≤)30=6x1+8x268=6x1+8x2Lo：0=6x1+8x2（8，2）DmaxSminS此点是唯一最优解，且最优目标函数值maxZ=64可行域maxS=6x1+8x264=6X1+8X22,104044601052121ixxxxxi5.3运输问题物资调运问题—表上作业法物资调运问题—图上作业法车辆运输的调度问题—图上作业法运输问题一般表述：设某种物资有m个产地A1,A2,…,Am,生产量分别为a1，a2,…,am;n个销地B1,B2,…,Bn,销售量分别为b1,b2,…,bn;cij表示i地往j地的单位运价.在产销平衡条件下,求总运费最小的调运方案.B1B2…Bn产量A1c11c12…c1nA1A2c21c22…c2nA2………………Amcm1cm2…cmnam销量b1b2…bnnjjmiiba11（产销平衡：）一、资调运问题—表上作业法表上作业法是求解运输问题的一种简便而有效的方法,其求解工作在运输表上进行,其实质是单纯形法.表上作业法的步骤资调运问题在不同的运输工具、不同的单位运价的情况下,如何组织调运使总运费最小或总吨公里数最小的问题.1.编制运费表与产销平衡表,并用最小元素法编制初始方案.2.用闭回路法,求检验数检验初始方案是否最优.3.若不是最优,再用闭回路法,求调整数,以调整初始方案.循环使用,直至调整至最优.例5.3.1某公司从三个产地A1、A2、A3将物品运往四个销地B1、B2、B3、B4,各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如下表所示,问：应如何调运可使总运输费用最小？单位销地运价产地产量4124111621039108514622销量8141214484321BBBB321AAA运费表销地产地B1B2B3B4产量A116A210A322销量814121448412431110285119682101486解第1步求初始方案最小元素法最小元素法基本思想是就近供应,即从运价最小的地方开始供应(调运),然后次小,直到最后供完为止。销地产地B1B2B3B4产量A116A210A322销量814121448412431110285119682101486此时初始方案已确定，总运费为说明1.若产销平衡表的发点个数为m个收点个数为n个，则初始方案表中填有运量的格子是m+n-1个.(8×2)+(14×5)+(10×4)+(2×3)+(6×11)+(8×6)=246元说明2.确定初始方案时在填运量xij后,Ai处的发量已发完,Bj处的收量也收齐,那么运费表会同时划去第i行与第j列,此时只划去其一(如第j列,剩下第i行),当再出现第i行时,在相应的格子处填上0.保证初始方案表中填有运量的格子是m+n-1个.如下例B1B2B3B4产量A14A24A312销量3656311310192741058341660B1B2B3B4A1x11x12x13x14A2x21x22x23x24A3x31x32x33x34注：X33、X21不是闭回路的顶点。闭回路的形式闭回路可在运输问题数据表上画出,它是一条封闭的折线,折线的每一条边或者是水平的,或者是垂直的.对于一条给定的闭回路,数据表上的每一行、每一列至多只有两个变量是闭回路的顶点（要么没有变量、要么有两个变量是闭回路的顶点）.解第2步求检验数判断是否为最优方案闭回路法与位势法.销地产地B1B2B3B4产量A116A210A322销量814121448412431110285119682101486若检验数λ均大于或等于0,则此方案为最优方案.若检验数λ有小于0，则此方案需调整。检验数λ=空格的闭回路上,第偶数个拐点处的运费之和减去第奇数个拐点处的运费之和.共有(m×n)-(m+n-1).销地产地B1B2B3B4产量A116A210A322销量81412144841243111028511968210148612212561112122同理，12410,1233311234411销地产地B1B2B3B4产量A11216A21-110A3101222销量814121448412431110285119682101486检验数λ24=-10,说明此方案非最优方案。销地产地B1B2B3B4产量A11216A21-110A3101222销量814121448412431110285119682101486第3步再用闭回路法,求调整数,以调整初始方案.循环使用,直至调整至最优.针对检验数为负数中的最小数,由此数对应的空格出发作闭回路法,求调整数。销地产地B1B2B3B4产量A11216A21-110A3101222销