第一讲线性规划应用举例与单纯形法

第一讲线性规划应用举例与单纯形法第1页，课件共68页，创作于2023年2月一、线性规划的数学模型与应用举例

【例1】最优生产计划问题。某企业在计划期内计划生产甲、乙、丙三种产品。这些产品分别需要在设备A、B上加工，需要消耗材料C、D，按工艺资料规定，单件产品在不同设备上加工及所需要的资源如表1所示。已知在计划期内设备的加工能力各为200台时，可供材料分别为360、300公斤；每生产一件甲、乙、丙三种产品，企业可获得利润分别为40、30、50元，假定市场需求无限制。企业决策者应如何安排生产计划，使企业在计划期内总的利润收入最大？第2页，课件共68页，创作于2023年2月

产品资源

甲

乙丙现有资源设备A312200设备B224200材料C451360材料D235300利润(元/件)

403050表1产品资源消耗线性规划的数学模型MathematicalModelofLP第3页，课件共68页，创作于2023年2月【解】设x1、x2、x3

分别为甲、乙、丙三种产品的产量,则数学模型为：

产品

资源甲

乙丙现有资源设备A312200设备B224200材料C451360材料D235300利润(元/件)403050线性规划的数学模型MathematicalModelofLP第4页，课件共68页，创作于2023年2月【例2】某饲料公司用甲、乙两种原料配制饲料，甲乙两种原料的营养成份及配合饲料中所含各营养成份最低量由表2给出。已知单位甲、乙原料的价格分别为10元和20元，求满足营养需要的饲料最小成本配方。

线性规划的数学模型MathematicalModelofLP第5页，课件共68页，创作于2023年2月【解】设x1、x2分别为甲、乙两种原料的用料数量,则数学模型为：线性规划的数学模型MathematicalModelofLP第6页，课件共68页，创作于2023年2月1．解决问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；2．解决问题的约束条件是一组多个决策变量的线性不等式或等式。线性规划数学模型的特征：线性规划数学模型的三要素：决策变量(Decisionvariables);

目标函数(Objectivefunction);约束条件(Constraints);建立一个问题的线性规划模型的一般步骤：确定决策变量；(2)确定目标函数；(3)确定约束条件；(4)确定变量是否有非负约束。线性规划的数学模型MathematicalModelofLP第7页，课件共68页，创作于2023年2月线性规划的一般模型一般地，假设线性规划数学模型中,有m个约束,有n个决策变量xj(j=1,2,…,n)，目标函数的变量系数用cj表示,

cj称为价值系数。约束条件的变量系数用aij表示，aij称为工艺系数。约束条件右端的常数用bi表示，bi称为资源限量。则线性规划数学模型的一般表达式可写成线性规划的数学模型MathematicalModelofLP第8页，课件共68页，创作于2023年2月在实际中一般xj≥0,但有时xj≤0或xj无符号限制。为了书写方便，上式也可写成：

线性规划的数学模型MathematicalModelofLP第9页，课件共68页，创作于2023年2月

【例3】某农户计划用12公顷耕地生产玉米，大豆和地瓜，可投入48个劳动日，资金360元。生产玉米1公顷，需6个劳动日，资金36元，可获净收入200元；生产1公顷大豆，需6个劳动日，资金24元，可获净收入150元；生产1公顷地瓜需2个劳动日，资金18元，可获净收入120元，问怎样安排才能使总的净收入最高。

【解】设农户种玉米、大豆及地瓜的数量分别为x1、x2、x3

公顷，则数学模型为：线性规划的数学模型MathematicalModelofLP第10页，课件共68页，创作于2023年2月线性规划的数学模型MathematicalModelofLP第11页，课件共68页，创作于2023年2月【例4】某商场决定：营业员每周连续工作5天后连续休息2天，轮流休息。根据统计，商场每天需要的营业员如表3所示。表3营业员需要量统计表问：商场人力资源部应如何安排每天的上班人数，使商场总的营业员最少？星期需要人数星期需要人数一300五480二300六600三350日550四400线性规划的数学模型MathematicalModelofLP第12页，课件共68页，创作于2023年2月线性规划的数学模型MathematicalModelofLP【解】设

(j=1,2,…,7)为休息2天后星期一到星期日开始上班的营业员，则这个问题的线性规划模型为第13页，课件共68页，创作于2023年2月【例5】投资问题。某投资公司在第一年有200万元资金，每年都有如下的投资方案可供考虑采纳：“假使第一年投入一笔资金，第二年又继续投入此资金的50%，那么到第三年就可回收第一年投入资金的一倍金额”。投资公司决定最优的投资策略使第六年所掌握的资金最多。

【解】设

x1：第一年的投资；

x2：第一年的预留资金；

x3：第二年新的投资；x4：第二年的预留资金；

x5：第三年新的投资；x6：第三年的预留资金；

x7：第四年新的投资；

x8：第四年的预留资金；

x9：第五年的预留资金；

线性规划的数学模型MathematicalModelofLP第14页，课件共68页，创作于2023年2月

第五年：(x7/2+x9)=x8+2x5

第三年：(x3/2+x5)+x6=x4+2x1

第四年：(x5/2+x7)+x8=x6+2x3

到第六年实有资金总额为x9+2x7，整理后得到下列线性规划模型

第一年：x1+x2=200(万元)第二年：(x1/2+x3)+x4=x2线性规划的数学模型MathematicalModelofLP第15页，课件共68页，创作于2023年2月【例6】均衡配套生产问题。某产品由2件甲零件和3件乙零件组装而成。两种零件必须经过设备A、B上加工，每件甲零件在A、B上的加工时间分别为5分钟和9分钟，每件乙零件在A、B上的加工时间分别为4分钟和10分钟。现有2台设备A和3台设备B，每天可供加工时间为8小时。为了保持两种设备均衡负荷生产，要求一种设备每天的加工总时间不超过另一种设备总时间1小时。怎样安排设备的加工时间使每天产品的产量最大。线性规划的数学模型MathematicalModelofLP第16页，课件共68页，创作于2023年2月【解】设x1、x2为每天加工甲、乙两种零件的件数，则产品的产量是设备A、B每天加工工时的约束为要求一种设备每台每天的加工时间不超过另一种设备1小时的约束为线性规划的数学模型MathematicalModelofLP第17页，课件共68页，创作于2023年2月目标函数线性化。产品的产量y等价于约束线性化。将绝对值约束写成两个不等式线性规划的数学模型MathematicalModelofLP第18页，课件共68页，创作于2023年2月线性规划模型为线性规划的数学模型MathematicalModelofLP第19页，课件共68页，创作于2023年2月线性规划的标准型线性规划的标准型StandardformofLP线性规划问题的标准型为:1．目标函数求最大值2．约束条件都为等式方程3．变量xj非负4．常数bi非负

在用单纯法求解线性规划问题时，为了讨论问题方便，需将线性规划模型化为统一的标准形式。第20页，课件共68页，创作于2023年2月线性规划的标准型StandardformofLP第21页，课件共68页，创作于2023年2月或写成下列形式：

或用矩阵形式线性规划的标准型StandardformofLP第22页，课件共68页，创作于2023年2月称Ａ为约束方程的系数矩阵，m是约束方程的个数，n是决策变量的个数，一般情况m≤n，且r(Ａ)＝m。其中:线性规划的标准型StandardformofLP第23页，课件共68页，创作于2023年2月一般形式线性规划模型的标准化准则:（前提bi

≥0

）5.xj≤0令xj

=－x'j,x'j≥0

线性规划的标准型StandardformofLP第24页，课件共68页，创作于2023年2月【例7】将下列线性规划化为标准型

【分析】(１)因为x3无符号要求，即x3可取正值也可取负值，标准型中要求变量非负，所以令线性规划的标准型StandardformofLP第25页，课件共68页，创作于2023年2月

(3)第二个约束条件是“≥”号，在“≥”号左端减去剩余变量(surplusvariable)x5，x5≥0，也称松驰变量；(2)第一个约束条件是“≤”号，在“≤”号左端加入松驰变量

(slackvariable)x4，x4≥0,化为等式；(4)第三个约束条件是“≤”号且常数项为负数，因此在“≤”左边加入松驰变量x6，x6≥0，同时两边乘以－1。

(5)目标函数是最小值，为了化为求最大值，令Z′=－Z,得到maxZ′=－Z，即当Z达到最小值时Z′达到最大值。线性规划的标准型StandardformofLP第26页，课件共68页，创作于2023年2月综合起来得到下列标准型线性规划的标准型StandardformofLP第27页，课件共68页，创作于2023年2月当某个约束是绝对值不等式时，将绝对值不等式化为两个不等式，再化为等式，例如约束

将其化为两个不等式

再加入松驰变量化为等式。

线性规划的标准型StandardformofLP第28页，课件共68页，创作于2023年2月

设线性规划的标准型

maxZ=CX(1.1)AX=b(1.2)X≥0(1.3)式中A是m×n矩阵，m≤n并且r(A)=m，显然A中至少有一个m×m子矩阵B，使得r(B)=m。线性规划的有关概念

可行解(feasiblesolution):

满足式(1.2)及(1.3)的解X=（x1,x2,…,xn)T称为可行解；基

(basis)：A中m×m子矩阵B并且有r(B)=m，则称B是线性规划的一个基(或基矩阵basismatrix)。线性规划的标准型StandardformofLP第29页，课件共68页，创作于2023年2月当确定某一矩阵为基矩阵时，则基矩阵对应的列向量称为基向量(basicvector)，其余列向量称为非基向量;

基向量对应的变量称为基变量(basicvariable)，非基向量对应的变量称为非基变量；注：基变量、非基变量是针对某一确定基而言的，不同的基对应的基变量和非基变量也不同。

基本概念BasicConcepts

基本可行解(basic

feasiblesolution):

若基本解是可行解则称为是基本可行解（也称基可行解）。

基本解(basicsolution):对某一确定的基B，令非基变量等于零，利用式(1.2)解出基变量，则这组解称为基Ｂ的基本解。第30页，课件共68页，创作于2023年2月

最优解(optimalsolution):满足式(1.1)的可行解称为最优解，即使得目标函数达到最大值的可行解就是最优解；非可行解(infeasiblesolution)

无界解

(unboundedsolution)注：（1）只要基本解中的基变量的解满足式(1.3)的非负要求，那么这个基本解就是基本可行解。

（2）可行解不一定是基本可行解，同样基本解也不一定是可行解。可行基:

基可行解对应的基称为可行基；最优基:基本最优解对应的基称为最优基；基本最优解:

最优解是基本解称为基本最优解。

基本概念BasicConcepts

第31页，课件共68页，创作于2023年2月凸集(Convexset):设K是n维空间Rn的一个点集，对任意两点

时，则称K为凸集。

就是以X(1)、X(2)为端点的线段方程,点X的位置由α的值确定,当α=0时,X=X(2),当α=1时X=X(1)。凸组合(Convexcombination)

:设是Rn中的点，若存在使得成立，称X为的凸组合

基本概念BasicConcepts

第32页，课件共68页，创作于2023年2月极点(Extremepoint)::

设K是凸集，，若X不能用K中两个不同的点的凸组合表示为<)10()1()2()1(<-+=aaaXXX则称X是K的一个极点或顶点。X是凸集K的极点，即X不可能是K中某一线段的内点，只能是K中某一线段的端点。O

基本概念BasicConcepts

第33页，课件共68页，创作于2023年2月【定理1.1】若线性规划可行解集K非空,则K是凸集。

【定理1.2】线性规划的可行解集合K的点X是极点的充要条件为X

是基本可行解。【定理1.3】若线性规划有最优解,则最优值一定可以在可行解集合的某个极点上达到,最优解就是极点的坐标向量。注：定理1.2刻划了可行解集的极点与基本可行解的对应关系，极点是基本可行解，反之，基本可行解一定是极点，但它们并非一一对应，有可能两个或几个基本可行解对应于同一极点(退化基本可行解时)。线性规划的基本定理

基本概念BasicConcepts

第34页，课件共68页，创作于2023年2月

单纯形计算方法(SimplexMethod)是先求出一个初始基可行解并判断它是否最优，若不是最优，再换一个基可行解并判断，直到得出最优解或判断出问题无最优解。它是一种逐步逼近最优解的迭代方法。

当系数矩阵A中可以观察得到一个可行基时(通常是一个单位矩阵或m个线性无关的单位向量组成的矩阵)，则可以通过解线性方程组求得基本可行解。单纯形法

SimplexMethod单纯形法第35页，课件共68页，创作于2023年2月【例8】用单纯形法求下列线性规划的最优解

【解】化为标准型:单纯形法

SimplexMethod第36页，课件共68页，创作于2023年2月系数矩阵A及可行基B1r(B1)=2,B1是一个初始基,x3、x4为基变量,x1、x2为非基变量,令x1=0、x2=0,由约束方程知x3=40、x4=30得到初始基本可行解X(1)=(0,0,40,30)T

问题：上述基本可行解是不是最优解？单纯形法

SimplexMethod第37页，课件共68页，创作于2023年2月我们可在目标函数中把基变量用非基变量来表示，则可根据非基变量的系数来判断目标函数有没有达到最优值，把判别线性规划问题是否达到最优解的数称为检验数，记作λj(j=1,2,…,n)。

本例中λ1=3,λ2=4,λ3=0,λ4=0。

最优解判断标准:

当所有检验数λj≤0(j=1，…，n)时，基本可行解为最优解。注：当目标函数中有基变量xi时，利用约束条件将目标函数中的xi消去即可求出检验数。

检验数:目标函数用非基变量表达时的变量系数。单纯形法

SimplexMethod第38页，课件共68页，创作于2023年2月典则形式(典式):(1)约束方程组中基变量的系数矩阵是的单位矩阵，移项后基变量可由非基变量表出；(2)目标函数中不含有基变量，只含非基变量(因为基变量可由非基变量表出)。

通常我们把典式中的相关数据列在一张表上，显得比较直观、简洁。若初始基可行解不是最优解，我们也可直接在表上进行作业，换到下一个基可行解，把这样的表叫做单纯形表。

如何通过观察第一个基本可行解并能判断是否为最优解，关键看模型是不是典则形式（简称典式）：单纯形法

SimplexMethod第39页，课件共68页，创作于2023年2月进基列出基行bi/ai2，ai2>0θi表6(1)XBx1x2x3x4bx3211040x4130130λj3400

(2)x3x2λj

(3)x1

x2

λj

基变量110001/301/3105/31-1/3405/30-4/330103/5-1/51801-1/52/5400-1-1将3化为1乘以1/3后得到3018单纯形法

SimplexMethod第40页，课件共68页，创作于2023年2月注:

(1)

在选进基变量时，一般选λk>0中较大者所对应的变量进基，也可任选一个λk>0所对应的变量进基，还可第一个λk>0所对应的变量进基。(2)选出基变量时，必须遵循最小比值原则(保证从一个可行基换到另一个可行基)，若有两个或两个以上相同最小的比值，则任选一个最小比值所对应的基变量出基，这时下一个基可行解中存在为0的基变量，称之为退化的基可行解。(3)表(1.5)中的每一张表对应的模型都是典式，从一个可行基换到另一个可行基，接下来的任务就是从当前典式换到另一个典式。(4)当目标函数是求最大值时,λj≤0(j=1，…，n)时达到最优解；当目标函数是求最小值时,λj≥0(j=1，…，n)时达到最优解。单纯形法

SimplexMethod第41页，课件共68页，创作于2023年2月单纯形法的计算步骤：1.找一个初始可行基，写出对应的典式，列出初始单纯形表,其中基变量的检验数必为零；

2.判断：(a)若λj≤０(j＝１，２，…，n)，则得到最优解；(b)若存在某个λk>0且aik≤０(i=1，2,…,m)，则线性规划具有无界解；(c)若存在λk>0且aik(i=1,…,m)不全非正，则进行换基；3.换基：(a)选进基变量：设λk=max｛λj|λj>0｝,选第k列所对应的变量xk为进基变量。单纯形法

SimplexMethod第42页，课件共68页，创作于2023年2月第Ｌ个比值最小，选最小比值对应行的基变量为出基变量，若有相同最小比值，则任选一个aLk为主元素。

(c)求新的基可行解：用初等行变换方法将aLk化为１,第k列其它元素化为零（包括检验数行）得到新的可行基及基本可行解，再判断是否得到最优解。(b)选出基变量：求最小比值单纯形法

SimplexMethod第43页，课件共68页，创作于2023年2月【例9】用单纯形法求解

【解】将数学模型化为标准型：单纯形法

SimplexMethod第44页，课件共68页，创作于2023年2月Cj12100bθCBXBx1x2x3x4x50x42－3210150x51/3150120λj12100

0x42x2λj

1x1

2x2

λj

表71/3150120301713751/30－90－2—2025601017/31/31250128/9－1/92/335/300－98/9－1/9－7/3最优解X=(25，35/3，0，0，0)T，最优值Z=145/3单纯形法

SimplexMethod第45页，课件共68页，创作于2023年2月【例10】用单纯形法求解

【解】

这是一个极小化的线性规划问题,可以将其化为极大化问题求解,也可直接求解,这时判断标准是:

λj≥0(j=1,…,n)得到最优解。容易观察到系数矩阵中有一个3阶单位矩阵,x3、x4、x5为基变量。单纯形法

SimplexMethod第46页，课件共68页，创作于2023年2月XBx1x2x3x4x5bθx3x4x51-16[1]121000100015→6215621/2λj1-1↑000

x2x4x51-241001-1-20100015111

λj20100

表中λj≥0(j=1,2,…,5),所以最优解为X=(0,5,0,1,11)T,最优值Z=2x1－2x2－x4=－2×5－1=－11。表8单纯形法

SimplexMethod第47页，课件共68页，创作于2023年2月

【例11】求解线性规划【解】化为标准型单纯形法

SimplexMethod第48页，课件共68页，创作于2023年2月初始单纯形表为XBx1x2x3x4bx3x432－2－1100114λj－1100

λ2=1>0,x2进基，而a12<0，a22<0，没有比值，故该线性规划问题具有无界解。另外由模型可以看出，当固定x1，而使x2→+∞且满足约束条件，从而原问题具有无界解。单纯形法

SimplexMethod第49页，课件共68页，创作于2023年2月【例12】求解线性规划用单纯形法计算如下表所示：【解】化为标准型为：单纯形法

SimplexMethod第50页，课件共68页，创作于2023年2月XBx1x2x3x4x5bθ(1)x3x4x5－111[2]2－11000100014→10225—λj24↑000(2)x2x4x5－1/2[2]1/21001/2－11/201000126→4—38λj4↑0－200(3)x2x1x50101001/4－1/23/41/41/2－1/40017/235/2→λj000－20(4)x2x1x30101000011/31/3－1/3－1/32/34/38/314/310/3λj000－201/4－1/2[3/4]0↑14—10/3单纯形法

SimplexMethod第51页，课件共68页，创作于2023年2月

表(3)中λj全部非正,此时已找到最优解，且最优解为:另外表(3)中非基变量x3的检验数λ3=0,x3若增加,目标函数值不变,即当x3进基时Z仍等于20。现使x3进基,x5出基继续迭代,得到表(4)的另一基本最优解X(1),X(2)是线性规划的两个最优解，它的凸组合

仍是最优解，从而原线性规划有多重最优解。单纯形法

SimplexMethod第52页，课件共68页，创作于2023年2月唯一最优解的判断：最优表中所有非基变量的检验数非零,则线性规划具有唯一最优解

。多重最优解的判断:最优表中存在非基变量的检验数为零,则线性规划具有多重最优解。无界解的判断:

某个λk>0且aik≤０(i=1,2,…,m)，则线性规划具有无界解。退化基本可行解的判断:存在某个基变量为零的基本可行解。单纯形法

SimplexMethod第53页，课件共68页，创作于2023年2月设有线性规划其中矩阵Am×n且r(A)=m,X≥0理解为X大于等于零的向量，即xj≥0(j=1,2,…,n)。计算公式单纯形法

SimplexMethod第54页，课件共68页，创作于2023年2月不妨假设A＝(P1,P2,…,Pn)中前m个列向量构成一个可行基，记为B=(P1,P2,…,Pm)。矩阵A中后n－m列构成的矩阵记为N＝(Pm+1,…,Pn),则A可以写成分块矩阵A=(B，N)。对于基B，基变量为XB=(x1,x2,…,xm

)T,非基变量为XN=(xm+1,xm+2,…,xn)T。

则X可表示成,同理将C写成分块矩阵C=(CB,CN)，CB=(C1,C2,…,Cm),

CN=(Cm+1,Cm+2,…,cn),

则AX=b可写成单纯形法

SimplexMethod第55页，课件共68页，创作于2023年2月因为r(B)=m(或|B|≠0)所以B-1存在，因此可有令非基变量XN=0，XB=B—1b，由B是可行基的假设，则得到基本可行解X=(B－1b，0)T消去目标函数中的基变量，于是目标函数可写成单纯形法

SimplexMethod第56页，课件共68页，创作于2023年2月得到下列五个计算公式：(令XN=0)

单纯形法

SimplexMethod第57页，课件共68页，创作于2023年2月上述公式可用下面较简单的矩阵表格运算得到，将目标函数写成CBXB+CNXN

－Z=0,约束为BXB+NXN=b将B化为E(E为m阶单位矩阵),即求基本可行解。用B－1左乘表中第二行,得到表10XBXNbXBEB-1NB-1bCBCN0XBXNbXBBNbCBCN0表10单纯形法

SimplexMethod第58页，课件共68页，创作于2023年2月将第二行左乘－CB后加到第三行,得到λΝXB－Z0XBXNbXBEB-1NB-1bλ＝Cj－Zj0CN-CBB－1N－CBB－1b表11将CB化为零,即求检验数:单纯形法