线性规划基本模型课件

主讲：范建平博士第一章线性规划基本模型1.1线性规划的实用模型06六月2023山西大学经济与管理学院范建平2在管理中一些典型的线性规划应用3合理利用线材问题：如何在保证生产的条件下，下料最少配料问题：在原料供应量的限制下如何获取最大利润投资问题：从投资项目中选取方案，使投资回报最大产品生产计划：合理利用人力、物力、财力等，使获利最大劳动力安排：用最少的劳动力来满足工作的需要运输问题：如何制定调运方案，使总运费最小06六月2023山西大学经济与管理学院范建平1、资源分配模型例1.1某装配厂拟生产甲、乙两种新产品，每件利润分别为300元和200元。甲、乙产品的部件分别在A、B两个车间生产，每件甲、乙产品的部件分别消耗A、B车间1、2工时。两种产品的部件最后都要在C车间装配，装配每件甲、乙产品分别消耗2工时和3工时。已知A，B，C三个车间每周可用于这两种产品的最大生产能力分别为6工时、8工时、18工时，则每周各生产甲、乙产品多少件？试建立该问题的数学模型。06六月20234山西大学经济与管理学院范建平解：列出数据表产品车间单耗/（工时/件）最大生产能力/(工时/周)甲乙A106B028C2318利润/（1×100元/件）321、资源分配模型06六月20235山西大学经济与管理学院范建平1、资源分配模型设x1,x2分别为甲、乙产品的周产量（决策变量）

z为这两种产品每周的总利润，则由于，z取值受限于x1,x2，而x1,x2受限于A，B，C三个车间的生产能力，则

式（0）称为目标函数，z为目标值产品车间单耗/（工时/件）最大生产能力/(工时/周)甲乙A106B028C2318利润/（1×100元/件）3206六月20236山西大学经济与管理学院范建平1、资源分配模型上述函数约束和非负性约束，统称为约束条件或约束方程，简称约束。综上所述，例题1.1的数学模型简记如下：又因产量x1,x2取值不能为负，则非负性约束06六月20237山西大学经济与管理学院范建平1、资源分配模型—小结由目标函数和约束方程构成的一组数学表达式，称为数学规划（模型）；若全为线性表达式，则称为线性规划（模型）；若组中有一个或更多表达式非线性，则称为非线性规划（模型）。06六月20238山西大学经济与管理学院范建平线性规划的三个要素9决策变量决策问题待定的量值取值要求非负约束条件任何管理决策问题都是限定在一定的条件下求解把各种限制条件表示为一组等式或不等式称约束条件约束条件是决策方案可行的保障约束条件是决策变量的线性函数目标函数衡量决策优劣的准则，如时间最省、利润最大、成本最低目标函数是决策变量的线性函数有的目标要实现极大，有的则要求极小06六月2023山西大学经济与管理学院范建平模型隐含假定10（1）线性化假定目标函数、约束条件（2）同比例假定决策变量变化引起目标函数和约束方程的改变量比例。（3）可加性假定决策变量对目标函数和约束方程的影响是独立于其他变量的。目标函数值是决策变量对目标函数贡献的总和。（4）连续性假定决策变量取值连续。（5）确定性假定所有参数都是确定的，不包含随机因素。06六月2023山西大学经济与管理学院范建平1、资源分配模型—小结小结：对于例题1.1的资源分配问题（经营规划问题），一般可表述为：某企业拟将现有的m种资源（用i=1,2，···，m表示）投入n项生产或商务活动（用j=1，2，···，n表示）。其中第i种资源的数量为bi，项目j每经营1个单位所创造的利润（或价值）为cj，所消耗的第i种资源的数量为aij。为履行合同，项目j的经营数量至少为ej；而市场调查，其最高需求量为dj。试建立其数学模型。06六月202311山西大学经济与管理学院范建平1、资源分配模型—小结建立线性规划模型的一般步骤：1.正确设立决策变量设xj（j=1,2,···,n）为项目j的经营数量。2.恰当建立目标函数n项经营活动的总利润（或总产值，总收入）为3.适度构建约束方程（1）合同约束（2）需求约束（3）资源约束06六月202312山西大学经济与管理学院范建平1、资源分配模型—小结综上所述可得LP模型如下：06六月202313山西大学经济与管理学院范建平2、产品配套模型例1.2某厂生产一种部件，由3个A零件和5个B零件配套组装成品。该厂有甲、乙、丙三种机床可加工A，B两种零件，每种机床的台数，以及每台机床每个工作日全部用于加工某一种零件的最大产量（即生产率：件/日）见表1-2。则应如何安排生产？试建立其数学模型。机床种类现有数量/台每台机床生产率/（件/日）A零件B零件甲23040乙32535丙42730表1-206六月202314山西大学经济与管理学院范建平2、产品配套模型求解本题，不能单纯追求两种零件的总产量达到最大，而应要求每个工作日按3:5的比例生产出来的A，B两零件的套数达到最大。1.决策变量：

2.约束条件：

（1）工时约束06六月202315山西大学经济与管理学院范建平2、产品配套模型06六月2023山西大学经济与管理学院范建平16（2）配套约束(表1.3)机床种类每种机床生产率/(件/日)A零件B零件甲6080乙75105丙108120表1-3每台机床的生产率非线性2、产品配套模型06六月2023山西大学经济与管理学院范建平17非线性约束等价转换2、产品配套模型06六月2023山西大学经济与管理学院范建平18LP模型如下：3、下料模型例1.3某项管网工程，要用某一口径的管材，其原材长5m，但用材的长度、数量不尽相同，见表1-4。应如何下料才能耗材最省？试建立其数学模型。用材长度/m需求量/根A2.6150B1.8200C1.1360表1-406六月202319山西大学经济与管理学院范建平3、下料模型解：首先需要找出全部省料截法(见表1-5)。（所谓省料截法，这里指一个原材截后的余料长度小于最短的用材C的长度的各种截法）

截法j用材一根原材所截各种用材的数量（根）需求量/根12345A（2.6）11000150B（1.8）10210200C（1.1）02124300余料/m0.60.20.31.00.6表1-506六月202320山西大学经济与管理学院范建平3、下料模型设xj表示第j种截法下料的根数（j=1,2,3,4,5），z为下料总根数则LP模型如下：

截法j用材一根原材所截各种用材的数量（根）需求量/根12345A（2.6）11000150B（1.8）10210200C（1.1）02124300余料/m0.60.20.31.00.606六月202321山西大学经济与管理学院范建平4、配料模型例1.4某食品厂拟用A，B两种紧俏原料和一种普通原料C，加工制作甲、乙、丙三种食品。食品的规格、加工费、销价，以及原料的购价、供量见表1-6。应如何为三种食品配料？试建立其数学模型。表1-6

原料食品食物规格（配用的原料所占比率）/%食品ABC加工费销价甲不少于50不少于30不限210乙不少于60不少于20不限28丙不少于40不限不多于6036原料购价562元/kg供量10060不限kg/天06六月202322山西大学经济与管理学院范建平4、配料模型解题要点：决策变量：约束条件：规格约束；原料供应量约束目标函数：总利润=总收益-原料总费用06六月202323山西大学经济与管理学院范建平4、配料模型06六月2023山西大学经济与管理学院范建平24决策变量：设xij表示每天给食品I所配用的原料j的数量（kg/天）（i=1,2,3;j=1,2,3）原料j食品iABC甲x11x12x13乙x21x22x23丙x31x32x334、配料模型06六月2023山西大学经济与管理学院范建平25约束条件—规格约束整理得：4、配料模型约束条件—原料供应约束总收益（未扣除原料费）原料总费用目标函数：总利润=总收益-原料总费用06六月202326山西大学经济与管理学院范建平

原料食品食物规格（配用的原料所占比率）/%食品ABC加工费销价甲不少于50不少于30不限210乙不少于60不少于20不限28丙不少于40不限不多于6036原料购价562元/kg供量10060不限kg/天4、配料模型综上可得LP模型如下：06六月202327山西大学经济与管理学院范建平

原料食品食物规格（配用的原料所占比率）/%食品ABC加工费销价甲不少于50不少于30不限210乙不少于60不少于20不限28丙不少于40不限不多于6036原料购价562元/kg供量10060不限kg/天1.2线性规划的一般模型06六月202328山西大学经济与管理学院范建平1.2.1线性规划的通式山西大学经济与管理学院范建平291.基本概念线性规划的通用模型（简称通式）目标函数函数约束非负（正）性约束目标要求约束边界方程aij,bi,cj称谓LP模型的参数，其中aij称为消耗系数，bi称为右端常数，cj称为价值系数。通式不便于研究线性规划的有效解法。于是，模型的各种标准型及典式（典范模式）便应运而生。本书介绍其中一种有效方法——单纯形方法。1.2.1线性规划的通式06六月2023山西大学经济与管理学院范建平302.解的概念（1）可行解方程组(1-1b)，(1-1c)的解X=(x1,x2,…,xn)T称为LP问题的可行解，其集合称为可行集，或可行域，记为:

R={X|(1-1b),(1-1c)}.（2）最优解

满足(1-1a)，即能使目标函数达到最优化的可行解，称为LP问题的最优解，简称为解，记为：X*=(x1*,x2*,…,xn*)T

它对应的目标函数值称为最优值，记为：

z*=c1x1*+c2x2*+…+cnxn*1.2.2线性规划的标准型06六月2023山西大学经济与管理学院范建平31单纯形法要求LP模型必须为下述特定形式右端常数取值为非负，即基于单纯形法的线性规划标准型，简称LP标准型3.101.2.2线性规划的标准型06六月2023山西大学经济与管理学院范建平32LP标准型也可简记为：1.2.2线性规划的标准型06六月2023山西大学经济与管理学院范建平33LP标准型矩阵向量的形式：本书约定：向量原型均为列向量，行向量用转置形式表示上述标准型的三种形式（M1），（M2），（M3）统称为标准型（问题）M1.2.3线性规划的标准化06六月2023山西大学经济与管理学院范建平34实际问题的LP模型通常都不是标准型，但可通过等价变换最终都能化成标准型。这类转化工作称为标准化。非标准型包括以下几种情况：1.min型目标函数2.非标准型约束方程3.取值非正的变量（1）bi<0,两端同乘以-1.（2）某个方程为≤形式，左端加非负的松弛变量化为等式.（3）某个方程为≥形式，左端减非负的剩余变量化为等式.松弛变量和剩余变量可统称为松弛变量，其价值系数为0（1）若xk≤0，只需通过变量代换xk=-xkˊ

则xkˊ≥0，用以取代xk，即可符合标准.（2）若xk为自由变量（可正，可负，可0），只需通过变量代换.

xk=xkˊ-xk〞,且xkˊ,xk〞≥0用以xkˊ-xk〞取代xk，即可符合标准.（3）当有多个自由变量xj时，为避免无谓增加变量个数，可令xj=xjˊ-x〞,x〞对其所在式中的一切j都是同一个变量。对于最小化目标函数minz=CTX,由于-max（-z）=minz=CTX因此只需令z’=-z,就可将原目标函数化成标准型：maxz’=-CTX例1-5将（例1-1）问题化为标准型06六月2023山西大学经济与管理学院范建平35产品车间单耗/（工时/件）最大生产能力/(工时/周)甲乙A106B028C2318利润/（1×100元/件）32例1-5将（例1-1）问题化为标准型06六月2023山西大学经济与管理学院范建平36将(1)、(2)、(3)式加上松弛变量，化为等式即可A，B，C三个车间的生产能力的松弛变量，即未被甲、乙产品耗用的生产能力。其价值系数为0例1-6将下述LP问题化为标准型06六月2023山西大学经济与管理学院范建平37例1-6将下述LP问题化为标准型06六月2023山西大学经济与管理学院范建平381.2.4线性规划的典式06六月2023山西大学经济与管理学院范建平39标准化是单纯形法的预备步骤，还需化成下述典式，才能用单纯形方法

典式标准型是单纯形法的唯一必要前提.06六月2023山西大学经济与管理学院范建平40方程组（1-3）的系数矩阵为前m列是一个满秩单位阵，这是典式的本质属性（1）标准型（M）为典式的充要条件是：在其函数约束方程组的系数矩阵中，存在一个满秩排列阵，即每行每列仅有一个元素为1，其他元素全为0的m阶方阵。（2）LP问题的标准型多为非典式，将标准型转化为典式需要加人工变量1.3线性规划的图解法所谓图解法，是指借助几何图形来求解LP问题的方法。图解法并非通用，只适合二维LP问题。06六月2023山西大学经济与管理学院范建平411.3.1基本步骤06六月2023山西大学经济与管理学院范建平421.建立平面直角坐标系2.画出可行域3.画出目标函数等值线及其法线4.平移目标函数等值线，确定问题的解【例1-7】用图解法求范例的的LP问题06六月2023山西大学经济与管理学院范建平43D(0,4)A(6,0)O(0,0)x1=62x2=8x1x2G(0,6)E(9,0)F(6,4)C(3,4)B(6,2)【例1-7】用图解法求范例的的LP问题06六月2023山西大学经济与管理学院范建平44D(0,4)A(6,0)O(0,0)x1x2C(3,4)B(6,2)z法向z*=22

沿着法线方向平行移动目标函数等值线，当与可行域相切时，恰在边界点B处，B点就是最优点，其坐标（6,2）就是最优解，代入目标函数，得最优值z=22.1.3.2求解结果06六月2023山西大学经济与管理学院范建平451.唯一解如范例，只有一个最优解B2.多重解【例1-8】若将范例的目标函数改为:z=3x1+4.5x2D(0,4)A(6,0)O(0,0)x1x2C(3,4)B(6,2)z法向z*=271.3.2求解结果06六月2023山西大学经济与管理学院范建平463.解无界【例1-9】求解下列LP问题O(0,0)x1x2z法向R

建模错误，缺少了约束条件。06六月2023山西大学经济与管理学院范建平474.无可行解【例1-10】考虑范例,若该厂从产量管理上规定，甲、乙两种产品每周总量不低于10件，试就此做出分析。G(0,6)O(0,0)x1x2

⑤x1+x2≥10

③2x1+3x2≤18R=∅E(9,0)1.4标准线性规划的解06六月2023山西大学经济与管理学院范建平481.4.1基本概念06六月2023山西大学经济与管理学院范建平491.基本解3阶单位阵，记为其系数矩阵为：A满秩，方程组（1-4b）行数=3<列数=5，有无穷多个解基向量基变量非基变量令非基变量x1=x2=0由方程组（1-4b）得：x3=6，x4=8,x5=18方程组（1-4b）的一个特解为：基本解1.基本解06六月2023山西大学经济与管理学院范建平50考虑标准形线性规划：假设A=(aij)m×n是满秩阵，且秩数为r(A)=m<n，将其系数阵A记为：

则有下述定义：1.基本解06六月2023山西大学经济与管理学院范建平51（1）基矩阵设B为A的一个m阶子矩阵，若其行列式|B|≠0，则称B为方程组（1-5b）或线性规划（1-5）的一个基矩阵，简称一个基。1.基本解06六月2023山西大学经济与管理学院范建平52（2）基变量1.基本解06六月2023山西大学经济与管理学院范建平531.基本解06六月2023山西大学经济与管理学院范建平54（3）基本解2.最优基本解06六月2023山西大学经济与管理学院范建平55（1）基本可行解既是基本解，又是可行解，就是基本可行解。满足非负约束的基本解为基本可行解。2.最优基本解06六月2023山西大学经济与管理学院范建平56（2）最优基本解满足式（1-5a），能使目标函数z=CTX取得最大值的基本可行解，称为标准型LP问题（1-5）的最优基本解，记为X*,它所对应的目标函数值称为最优值，记为z*=CTX*2.最优基本解06六月2023山西大学经济与管理学院范建平57（3）可行基与最优基基本可行解对应的基称为可行基，最优基本解对应的基称为最优基，记为B*。（4）退化基本（可行）解如果一个基本（可行）解中，有一个或更多个基变量取值为0，则称之为退化基本（可行）解，否则称为非退化的基本（可行）解。如何找到可行基？3.凸性的基本概念06六月2023山西大学经济与管理学院范建平58（1）凸组合线性组合由线性代数知道，k个n维向量X1,X2,…,Xk,各与一个任意实数μ1,μ2,…,μk可分别相乘以后再相加，得到一个新的n维向量Y即有：

Y=μ1X1+μ2X2+…+μkXk则称Y是这k个n维向量X1,X2,…,Xk的一个线性组合。凸组合若再规定各实数μ1,μ2,…,μk的取值：①非负；②总和为1，

则称Y是这k个n维向量X1,X2,…,Xk的一个凸组合。3.凸性的基本概念06六月2023山西大学经济与管理学院范建平59（1）凸组合3.凸性的基本概念06六月2023山西大学经济与管理学院范建平60（2）凸集3.凸性的基本概念06六月2023山西大学经济与管理学院范建平61（3）极点1.4.2基本性质06六月2023山西大学经济与管理学院范建平62【性质1】线性规划的可行域是凸集1.4.2基本性质06六月2023山西大学经济与管理学院范建平63【性质