线性规划和单纯形法

线性规划和单纯形法第1页，课件共77页，创作于2023年2月目录线性规划实例与模型线性规划的图解法单纯形法原理改进单纯形法应用第2页，课件共77页，创作于2023年2月目录线性规划实例与模型第3页，课件共77页，创作于2023年2月实用举例

某公司通过市场调研，决定生产高中档新型拉杆箱。某分销商决定买进该公司3个月内的全部产品。拉杆箱生产需经过原材料剪裁、缝合、定型、检验和包装4过程。通过分析生产过程，得出：生产中档拉杆箱需要用7/10小时剪裁、5/10小时缝合、1小时定型、1/10小时检验包装；生产高档拉杆箱则需用1小时剪裁、5/6小时缝合、2/3小时定型、1/4小时检验包装。由于公司生产能力有限，3月内各部的最大生产时间为剪裁部630小时、缝合部600小时、定型部708小时、检验包装部135小时。通过市场调研部和会计部的调查核算得出结论：生产中档拉杆箱的利润是10元，高档拉杆箱的利润是9元。公司应各生产多少中档和高档拉杆箱才能使公司利润最大？第4页，课件共77页，创作于2023年2月实用举例某公司通过市场调研，决定生产高中档新型拉杆箱。某分销商决定买进该公司3个月内的全部产品。拉杆箱生产需经过原材料剪裁、缝合、定型、检验和包装4过程。通过分析生产过程，得出：生产中档拉杆箱需要用7/10小时剪裁、5/10小时缝合、1小时定型、1/10小时检验包装；生产高档拉杆箱则需用1小时剪裁、5/6小时缝合、2/3小时定型、1/4小时检验包装。由于公司生产能力有限，3月内各部的最大生产时间为剪裁部630小时、缝合部600小时、定型部708小时、检验包装部135小时。通过市场调研部和会计部的调查核算得出结论：生产中档拉杆箱的利润是10元，高档拉杆箱的利润是9元。公司应各生产多少中档和高档拉杆箱才能使公司利润最大？可以通过线性规划求解！第5页，课件共77页，创作于2023年2月线性规划模型的建立

设生产中、高档拉杆箱数量分别为：称为决策变量。目标函数约束条件第6页，课件共77页，创作于2023年2月一般线性规划模型Maxz=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn=b1(

0) a21x1+a22x2+…+a2nxn=b2

(

0) :am1x1+am2x2+…+amnxn=bm(

0)

x1,x2,…,xn

0s.t.

为约束限制（Subjectto）的缩写(LP)x1..xnb1..bma11…a1n…………am1…amnx=b= A=c1..cnc=其中c=(c1,c2,…,cn)，称为价值系数向量；第7页，课件共77页，创作于2023年2月称为资源限制向量

X=(x1,x2,…,xn)T

称为决策变量向量称为技术系数矩阵(也称消耗系数矩阵)一般线性规划模型第8页，课件共77页，创作于2023年2月线性规划模型的标准形式MaxZ=c1x1+c2x2+…+cnxnSubjectto(s.t.) a11x1+a12x2+…+a1nxn

=

b1

a21x1+a22x2+…+a2nxn

=

b2

…… am1x1+am2x2+…+amnxn=

bm

x1

0,x2

0,…,xn

0为了讨论方便，把最大化、等式约束型的线性规划称为线性规划的标准型，即第9页，课件共77页，创作于2023年2月标准化原问题标准化方法目标函数Maxf(x)Maxf(x)Minf(x)Max–f(x)约束条件引入松弛变量和人工变量引入松弛变量,不变变量不变对某个对某个是任意的

第10页，课件共77页，创作于2023年2月线性规划模型的标准化例:将如下线性规划模型标准化：minz=x1+5x2-8x3-x4s.t.2x1-3x2+x3+x4≤20

x1+2x2+3x3-x4≥302x2+2x3+3x4≥-50

x1,x3,x4≥0，x2取值无约束。

maxz1=-x1-5x2+8x3+x4s.t.2x1-3x2+x3+x4≤20

x1+2x2+3x3-x4≥302x2+2x3+3x4≥-50

x1,x3,x4≥0，x2取值无约束。

目标优化标准化第11页，课件共77页，创作于2023年2月线性规划模型的标准化Maxz2=-x1-5y2+5y3+8x3+x4s.t.2x1-3y2+3y3+x3+x4≤20-x1-2y2+2y3-3x3+x4≤

-30-2y2+2y3-2x3-3x4≤

50

x1,x3,x4,y2,y3≥0

决策变量的标准化:y2-y3=x2maxz1=-x1-5x2+8x3+x4s.t.2x1-3x2+x3+x4≤20

x1+2x2+3x3-x4≥302x2+2x3+3x4≥-50

x1,x3,x4≥0，x2取值无约束

第12页，课件共77页，创作于2023年2月线性规划模型的标准化Maxz2=-x1-5y2+5y3+8x3+x4

s.t.2x1-3y2+3y3+x3+x4+x5=20-x1-2y2+2y3-3x3+x4+x6=

-30-2y2+2y3-2x3-3x4+x7=50

x1,x3,x4,x5,x6,x7,y2,y3≥0约束关系标准化Maxz2=-x1-5y2+5y3+8x3+x4

s.t.2x1-3y2+3y3+x3+x4≤20-x1-2y2+2y3-3x3+x4≤

-30-2y2+2y3-2x3-3x4≤

50

x1,x3,x4,y2,y3≥0

第13页，课件共77页，创作于2023年2月可行解:满足所有约束条件的解x=（x1，x2，….，xn），所有可行解的集合称为可行域。基：设A是约束方程组的m×n阶系数矩阵，秩为m，是A中阶非奇异子矩阵（即），则称是线性规划问题的一个基矩阵，简称基。B中的列向量称为基向量，与基向量对应的变量x称为基变量，其它变量称为非基变量。

基本解：令非基变量值为0，由Ax=b可求出一个解，这个解x称为基本解。基本可行解：满足非负条件的基本解称为基本可行解。最优解：使目标函数达到最优值的可行解称为最优解。线性规划的解

第14页，课件共77页，创作于2023年2月可行解、基本解、基本可行解的关系可行解基本解基本可行解第15页，课件共77页，创作于2023年2月目录线性规划实例与模型线性规划的图解法与基本性质第16页，课件共77页，创作于2023年2月线性规划的图解法当只有两个决策变量时，可用图解法求解！例：用图解法求解以下线形规划问题。maxz=4x1+3x2

s.t.x1≤62x2≤82x1+3x2≤18x1≥0，x2≥0x1

x2

L3：2x1+3x2=18可行域L1：x1=6L2：x2=4最优解B4x1+3x2第17页，课件共77页，创作于2023年2月解的特殊情况——多个最优解第18页，课件共77页，创作于2023年2月解的特殊情况——无可行解第19页，课件共77页，创作于2023年2月解的特殊情况——无界解第20页，课件共77页，创作于2023年2月线性规划的基本性质

X可行域内部的点可行解?是最优解?不若线性规划有最

优解，则最优解必在可行域的顶点上达到。第21页，课件共77页，创作于2023年2月凸集的概念

凸集是线性规划中一个很重要的概念，凸集的一般定义为：如果在集合C中任意取两个点x1，x2，其连线上的所有点也都在集合C中，则称集合C为凸集合。用数学解析式表达为：对任意，均有，则称C是凸集合。非凸集非凸集凸集第22页，课件共77页，创作于2023年2月线性规划的基本性质定理2.1：线性规划的可行域：是凸集（凸多面体）。

引理2.1：线性规划的可行解为基本可行解的充分必要条件是x的正分量所对应的系数列向量是线性无关的，即每个正分量都是一个基变量。定理2.2：线性规划问题的基本可行解x对应于可行域的顶点

定理2.3：若线性规划有最优解，则最优解必在可行域的顶点上达到。第23页，课件共77页，创作于2023年2月目录线性规划实例与模型线性规划的图解法单纯形法原理第24页，课件共77页，创作于2023年2月一、初始基本可行解的确定考虑如下形式的线性规划问题maxz=c1x1+c2x2+…..+cnxns.t.a11x1+a12x2+……+a1nxn≤b1a21x1+a22x2+……+a2nxn≤b2(2.17）

……….am1x1+am2x2+…+amnxn≤bmx1，x2，….，xn≥0（2.18）对每个不等式约束引入一个非负松弛变量，得标准形式：maxz=c1x1+c2x2+…..+cnxns.t.a11x1+……+a1nxn+xn+1=b1a21x1+……+a2nxn+xn+2=b2（2.19）

……………..am1x1+……+amnxn+xn+m=bm

x1，x2，….，xn，xn+1，…，xn+m≥0第25页，课件共77页，创作于2023年2月是线性规划(2.19)的一个可行基。令

得由此得到一个初始基本可行解为第26页，课件共77页，创作于2023年2月二、最优性检验

定理2.4：在最大化问题中，对于某个基本可行解，如果所有的，则这个基本可行解是最优解。在最小化问题中，对于某个基本可行解，如果所有的，则这个基本可行解是最优解。第27页，课件共77页，创作于2023年2月单纯形法求解步骤将所给问题化为标准形找出一个初始可行基,建立初始单纯形表检查所有检验数(若全为非负,则已得到最优解,计算停止.否则继续下一步)考察是否无解(若是,计算停止,否则继续下一步)确定入基变量,出基变量对初始单纯形表进行单纯形变换第28页，课件共77页，创作于2023年2月单纯形方法的一般步骤确定一个初始可行角点根据某种法则进行角点的最优性判断不是最优角点是最优角点考察与当前角点相邻的“更好”的一个角点，并置为当前角点。根据某种法则进行LP的无界或不可行判断无界或不可行还不能做出判断求解结束第29页，课件共77页，创作于2023年2月单纯形法举例解：引进松驰变量x3,x4，化为标准形得：第30页，课件共77页，创作于2023年2月

4300CBXBb

x1

x2x3x4b/y00x3x42426

231024/2

320126/3

043004=4－（0×3+0×2）；3=3－（0×2+0×3）……

4300CBXBbx1x2x3x4b/y04x3x120/326/305/31-2/312/301/3

-104/301/30-4/3第31页，课件共77页，创作于2023年2月

4300CBXBbx1x2x3x434x2x146013/5-2/510-2/53/5

3600-1/5-6/5表中最后一行的所有检验数均为非正数，表明目标函数已达到最大值，上述表为最优表。从表中可得到最优解为X=（x1,x2,x3,x4）=（6，4，0，0），最优值为Z=36

4300CBXBbx1

x2x3x4b/y04x3x120/326/305/31-2/3412/301/313

-104/301/30-4/3第32页，课件共77页，创作于2023年2月单纯形法的进一步讨论人工变量法人工变量法： 前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。第33页，课件共77页，创作于2023年2月单纯形法的进一步讨论人工变量法例1.10用大M法解下列线性规划解：首先将数学模型化为标准形式系数矩阵中不存在单位矩阵，无法建立初始单纯形表。第34页，课件共77页，创作于2023年2月单纯形法的进一步讨论人工变量法故人为添加两个单位向量，得到人工变量单纯形法数学模型：其中：M是一个很大的抽象的数，不需要给出具体的数值，可以理解为它能大于给定的任何一个确定数值；再用前面介绍的单纯形法求解该模型，计算结果见下表。

第35页，课件共77页，创作于2023年2月单纯形法的进一步讨论人工变量法cj32-100-M-MCBXBbx1x2x3x4x5x6x7θi-Mx64-431-101040x5101-1201005-Mx712-21000113-2M2+M-1+2M↑-M0000x63-650-1013/5-Mx58-3300108/3-1x312-21000——5-6M5M↑0-M002x23/5－6/510－1/50——-Mx531/53/5003/5131/3-1x311/5－2/501－2/50——5↑00002x213010123x131/310015/3-1x319/300102/3000-5-25/3→→→第36页，课件共77页，创作于2023年2月单纯形法的进一步讨论人工变量法

解的判别：1）唯一最优解判别：最优表中所有非基变量的检验数非零,则线规划具有唯一最优解。（检验数为负数或0）2）多重最优解判别：最优表中存在非基变量的检验数为零,则线则性规划具有无穷多最优解（检验数为负数或0）。3）无界解判别：某个检验数>0且aik≤０（i=1，2,…,m）则线性规划具有无界解。4）无可行解的判断：当用大M单纯形法计算得到最优解并且存在Ri>0时，则表明原线性规划无可行解。5）退化解的判别：存在某个基变量为零的基本可行解。第37页，课件共77页，创作于2023年2月大M法基本思想：在约束条件中增加人工变量，同时修改目标函数，对目标函数加上具有很大正系数M的惩罚项，为使人工变量不影响目标函数取值，在迭代过程中，应把人工变量从基变量中退出，使其成为非基变量。

其中，M是很大的正数，同时增加两个人工变量。

不容易找到初始可行解第38页，课件共77页，创作于2023年2月找初始可行解11-300MMbi/yibx1X2x3x4x5x6x70X4111-21100011MX6321-40-1103/2MX71(1)0-2000111-3M1-M-3+6M0M00要求最后得到的基变量中不含人工变量X1进基，x7出基11-300MMbi/yibx1x2x3x4x5x6x7-3X340011/3-2/32/3-5/31X210100-11-211X191002/3-4/34/3-7/30001/31/3M-1/3M-2/3可以从表中移去，然后继续求解经过几次变换，得到基变量为x1，x2，x3第39页，课件共77页，创作于2023年2月两阶段法原理两阶段法的第一阶段是用单纯形法消去人工变量，即把人工变量都变为非基变量，求出原问题的一个基本可行解。如果第一阶段求解结果表明问题有可行解时，进行第二阶段，就是从得到的基本可行解出发，用单纯形方法求原问题的最优解。第40页，课件共77页，创作于2023年2月5.2退化

LP问题

有退化最优解第41页，课件共77页，创作于2023年2月单纯形法计算中用θ规则确定换出变量时，有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，这就出现退化解。

这时换出变量xl=0，迭代后目标函数值不变。这时不同基表示为同一顶点。有人构造了一个特例，当出现退化时，进行多次迭代，而基从B1,B2，…又返回到B1，即出现计算过程的循环，便永远达不到最优解。第42页，课件共77页，创作于2023年2月两阶段法举例例：第一阶段：第二阶段：用单纯形法求得第一阶段的解为：用单纯形法求解规划问题得最优解

目标函数的最优解是

第43页，课件共77页，创作于2023年2月ExcelSolver（规划求解）

Excel采用了电子表格的形式，帮助管理者提高数据管理的能力，因而得以广泛应用。Solver插件专门用于求解带约束的最优化问题。Solver——“规划求解”，可在Excel的工作表中根据对话框提示调用该项功能。第44页，课件共77页，创作于2023年2月

可能出现以下情况：①进行进基、出基变换后，虽然改变了基，但没有改变基本可行解（极点），目标函数当然也不会改进。进行若干次基变换后，才脱离退化基本可行解（极点），进入其他基本可行解（极点）。这种情况会增加迭代次数，使单纯形法收敛的速度减慢。②在特殊情况下，退化会出现基的循环，一旦出现这样的情况，单纯形迭代将永远停留在同一极点上，因而无法求得最优解。3.单纯形法第45页，课件共77页，创作于2023年2月

在单纯形法求解线性规划问题时，一旦出现这种因退化而导致的基的循环，单纯形法就无法求得最优解，这是一般单纯形法的一个缺陷。但是实际上，尽管退化的结构是经常遇到的，而循环现象在实际问题中出现得较少。尽管如此，人们还是对如何防止出现循环作了大量研究。1952年Charnes提出了“摄动法”，1954年Dantzig，Orden和Wolfe又提出了“字典序法”，3.单纯形法第46页，课件共77页，创作于2023年2月

这些方法都比较复杂，同时也降低了迭代的速度。1976年，Bland提出了一个避免循环的新方法，其原则十分简单。仅在选择进基变量和出基变量时作了以下规定：①在选择进基变量时，在所有j

>0的非基变量中选取下标最小的进基；②当有多个变量同时可作为出基变量时，选择下标最小的那个变量出基。这样就可以避免出现循环,当然，这样可能使收敛速度降低。3.单纯形法第47页，课件共77页，创作于2023年2月加载“规划求解”如果在您的Excel中，没有在“工具”菜单中发现“规划求解”，请在下图所示的界面中点击“加载宏”。第48页，课件共77页，创作于2023年2月加载“规划求解”点击“加载宏”后，显示界面如下：如果列表中没有“规划求解”，表明您还没有安装该插件。这时，您需要插入MicrosoftOffice安装盘，选择“添加安装”后选择该插件的安装。第49页，课件共77页，创作于2023年2月第1步导入已知数据可采用‘复制粘贴’或‘直接输入’的方式导入数据。第50页，课件共77页，创作于2023年2月第2步确定‘可变单元格’

可变单元格存放决策变量的取值，可变单元格数目等于决策变量个数图中，规定B16、C16为可变单元格第51页，课件共77页，创作于2023年2月第3步确定‘目标单元格’

在目标单元格中，需要填入计算目标函数值的公式。第52页，课件共77页，创作于2023年2月第4步确定‘约束单元格’

在约束单元格中，需要填入计算约束函数值的公式。第53页，课件共77页，创作于2023年2月第5步调用‘规划求解’模块在上图显示的界面中，需要输入目标单元格、可变单元格，添加约束条件，另外还可能需要进行选项设置。第54页，课件共77页，创作于2023年2月第6步填写目标单元格和可变单元格第55页，课件共77页，创作于2023年2月第7步添加约束第56页，课件共77页，创作于2023年2月第8步“选项”设置选择：采用线性模型，假定非负。如果求解过程在找到结果之前即达到最长运算时间或最大迭代次数，则会弹出“显示中间结果”对话框。第57页，课件共77页，创作于2023年2月第9步保存求解结果第58页，课件共77页，创作于2023年2月显示求解结果第59页，课件共77页，创作于2023年2月使用Excel求解例2.10第60页，课件共77页，创作于2023年2月第61页，课件共77页，创作于2023年2月

合理利用线材问题：如何下料使用材最少。

配料问题：在原料供应量的限制下如何获取最大利润。

投资问题：从投资项目中选取方案，使投资回报最大。4.线性规划应用建模

一、线性规划---第62页，课件共77页，创作于2023年2月

产品生产计划：合理利用人力、物力、财力等，使获利最大。

劳动力安排：用最少的劳动力来满足工作的需要。

运输问题：如何制定调运方案，使总运费最小。4.线性规划应用第63页，课件共77页，创作于2023年2月

数学规划的建模有许多共同点，要遵循下列原则：(1)容易理解。建立的模型不但要求建模者理解，还应当让有关人员理解。这样便于考察实际问题与模型的关系，使得到的结论能够更好地应用于解决实际问题。(2)容易查找模型中的错误。这个原则的目的显然与(1)相关。常出现的错误有：书写错误和公式错误。4.线性规划应用第64页，课件共77页，创作于2023年2月

(3)容易求解。对线性规划来说，容易求解问题主要是控制问题的规模，包括决策变量的个数和约束条件的个数。这条原则的实现往往会与(1)发生矛盾，在实现时需要对两条原则进行统筹考虑。4.线性规划应用第65页，课件共77页，创作于2023年2月

建立线性规划模型的过程可以分为四个步骤：

(1)设立决策变量；(2)明确约束条件并用决策变量的线性等式或不等式表示；(3)用决策变量的线性函数表示目标，并确定是求极大（Max）还是极小（Min）；(4)根据决策变量的物理性质研究变量是否有非负性。4.线性规划应用第66页，课件共77页，创作于2023年2月

例2.:明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如下表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？生产计划的问题第67页，课件共77页，创作于2023年2月解：设x1,x2,x3

分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。

生产计划的问题第68页，课件共77页，创作于2023年2月

求xi

的利润:利润=售价-各成本之和可得到xi（i=1,2,3,4,5）的利润分别为15、10、7、13、9元。这样我们建立如下数学模型：目标函数:Max15x1+10x2+7x3+13x4+9x5

约束条件：s.t.5x1+10x2+7x3≤80006x1+4x2+8x3+6x4+4x5≤120003x1+2x2+2x3+3x4+2x5≤10000x1,x2,x3,x4,x5≥0

生产计划的问题第69页，课件共77页，创作于2023年2月

例2.:永久机械厂生产Ⅰ、Ⅱ、Ⅲ三种产品，均要经过A、B两道工序加工。假设有两种规格的设备A1、A2能完成A工序；有三种规格的设备B1、B2、B3能完成B工序。Ⅰ可在A、B的任何规格的设备上加工；Ⅱ可在任意规格的A设备上加工，但对B工序,只能在B1设备上加工；Ⅲ只能在A2与B2设备上加工；数据如下表。问：为使该厂获得最大利润，应如何制定产品加工方案？

生产计划的问题第70页，课件共77页，创作于2023年2月解：设xijk表示第i种产品，在第j种工序上的第k种设备上加工的数量.

利润=[（销售单价-原料单价）×产品件数]之和-（每台时的设备费用×设备实际使用的总台时数）之和。

生产计划的问题第71页，课件共77页，创作于2023年2月这样我们建立如下的数学模型:Max

0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123

s.t

5x111+10x2