企业管理MBA运筹学2第二 五章 线性规划课件

第二三四五章线性规划§2.1线性规划问题与标准形式§2.2线性规划问题的几何解释§2.3单纯型法方法第二三四五章线性规划问题的提出（1）【例】派公司是一个生产高尔夫器材的小型公司，公司决定生产中高价位的高尔夫袋。产品的生产过程有四个程序：切割并印染原材料、缝合、成型、检查和包装，不同价位高尔夫袋生产程序的耗时信息如下表，表中还列出了派公司在本轮生产过程中每个部门的最大生产时间。问题的提出（1）【例】派公司是一个生产高尔夫器材的小型公司，问题的提出（2）会计部门的数据表明，生产一个标准袋的利润是10美元，生产一个高级袋的利润是9美元。如何安排两种产品的生产才能使公司获得最大利润？耗时/标准袋耗时/高档袋最大生产时间切割印染0.71630缝合0.55/6600成型12/3708检查包装0.10.25135问题的提出（2）会计部门的数据表明，生产一个标准袋的利润是1问题的提出（3）设x1、x2分别为两种高尔夫袋的生产量，则该计划问题可用如下数学模型表示为：问题的提出（3）设x1、x2分别为两种高尔夫袋的生产量，则该§2.1线性规划问题与标准形式

典例1-----生产计划问题例2.某工厂在计划期内要生产产品I和产品II这两种产品，已知生产单位产品所需的设备台时及A、B两种设备计划期的有效台时，如下表：问如何安排生产最有利？解∶设产品I和产品II的产量分别为x1和x2件,利润为Z,则:

Z=x1+2x2Max目标函数2x1+2x2≤80x1+2x2≤4x1,x2≥0约束条件S.t.非负条件§2.1线性规划问题与标准形式

典例1-----[企业管理]MBA运筹学2第二五章线性规划课件above,above,[企业管理]MBA运筹学2第二五章线性规划课件[企业管理]MBA运筹学2第二五章线性规划课件典例2----配料问题

Z=3x1+2x2Min目标函数12x1+3x2≥42x1+3x2≥23x1+15x2≥5x1+x2=1x1,x2≥0约束条件S.t.典例2----配料问题Z=3x1+2x2Mi典例3----食谱问题[例3]问在满足营养的条件下,如何安排食谱最有利?解:设每人每周食用大米、白菜、鸡蛋、猪肉的数量分别为x1、x2、

x3、

x4Z=C1x1+C2x2+C3x3+C4x4Mina11x1+a12x2+a13x3+a14x4b1=a21x1+a22x2+a23x3+a24x4=

b2a31x1+a32x2+a33x3+a34x4=

b3x1,x2,x3,

x4≥0典例3----食谱问题[例3]问在满足营养的条件下,如何安排食谱问题的拓展问在满足营养的条件下,如何安排食谱最有利?Z=C1x1+C2x2+C3x3+C4x4+...+CnxnMina11x1+a12x2+a13x3+a14x4+…..+a1nxn=

b1a21x1+a22x2+a23x3+a24x4+…..+a2nxn=

b2a31x1+a32x2+a33x3+a34x4+…..+a3nxn=

b3am1x1+am2x2+am3x3+am4x4+…..+amnxn=

bmx1,x2,x3,...

xn≥0∶数学模型食谱问题的拓展问在满足营养的条件下,如何安排食谱最有利?NewBedfordSteel炼焦煤供应问题

AshleyBedfordConsolDunbyEarlamFlorenceGastonHopt供应量(千吨/年）300600510655575680450490工会（U）/非工会（N）

U

U

N

U

N

U

N

N卡车（T）/

铁路（R）

R

T

R

T

T

T

R

R可燃率（%）1516182021222325价格(＄/吨）49.5050.0061.0063.5066.5071.0072.5080.00NewBedfordSteel(NBS)是一家小型的炼钢企业。炼焦煤(cokingcoal)是NBS公司炼钢时所必需的一种原材料，每年的需求量是100至150万吨。现在到了该公司计划明年生产的时候了，他们收到了来自八家供应商的报价。NewBedfordSteel炼焦煤供应问题NewBedfordSteel炼焦煤供应问题根据对未来的形势估计和生产现状的考察，NBS计划明年要定购1,225千吨的炼焦煤。这些炼焦煤的平均可燃率至少要达到19%。为了不影响劳工关系，NBS决定至少50%的炼焦煤要来自于工会煤矿。另外，每年由火车运输的炼焦煤量至多不超过650千吨，而由卡车运输的炼焦煤量至多不超过720千吨。现在要解决以下问题：为了使炼焦煤的成本最小，应该从各个供应商处定购多少吨炼焦煤？NBS的总供应成本是多少？NBS的平均供应成本是多少？NewBedfordSteel炼焦煤供应问题根NBS供应问题的数学表达变量：A= 从Ashley 处定购的炼焦煤量（千吨）B= 从Bedford 处定购的炼焦煤量（千吨）C= 从Consol 处定购的炼焦煤量（千吨）D= 从Dunby 处定购的炼焦煤量（千吨）E= 从Earlam 处定购的炼焦煤量（千吨）F= 从Florence 处定购的炼焦煤量（千吨）G= 从Gaston 处定购的炼焦煤量（千吨）H= 从Hopt 处定购的炼焦煤量（千吨）NBS供应问题的数学表达变量：供应成本成：49.5A+50B+61C+63.5D+66.5E+71F+72.5G+80H供应约束：A+B+C+D+E+F+G+H=1,225工会煤矿的约束：A+B–C+D–E+F–G–H≥0卡车运输量约束：B+D+E+F≤720火车运输量约束：A+C+G+H≤650平均可燃率约束：可改写成：–4A–3B–C+D+2E+3F+4G+6H≥0各煤矿的炼焦煤供应量约束：A≤300，B≤600，C≤510，D≤655，E≤575，F≤680，G≤450，H≤490非负约束：A≥0，B≥0，C≥0，D≥0，E≥0，F≥0，G≥0，H≥0供应成本成：NBS的炼焦煤供应问题的线性最优化模型MINIMIZECOST=49.5A+50B+61C+63.5D+66.5E+71F+72.5G+80HSUBJECTTO：SUPPLY： A+B+C+D+E+F+G+H=1,225UNION： A+B–C+D–E+F–G–H≥0TRUCK： B+D+E+F≤720RAIL：A+C+G+H≤650VOL：–4A–3B–C+D+2E+3F+4G+6H≥0ACAP： A≤300BCAP： B≤600CCAP： C≤510DCAP： D≤655ECAP： E≤575FCAP： F≤680GCAP： G≤450HCAP： H≤490NONNEGATIVITYCONDITIONS：A≥0,B≥0,C≥0,D≥0,E≥0,F≥0,G≥0,H≥0NBS的炼焦煤供应问题的线性最优化模型MINIMIZECNBS的炼焦煤供应问题的线性最优化模型求解，得：A=55千吨，B=600千吨，C=0千吨，

D=20千吨，E=100千吨，F=0千吨，

G=450千吨，H=0千吨；最小成本=73,267.50千美元；平均供应成本=73,267.50/1,225=59.81美元/吨NBS的炼焦煤供应问题的线性最优化模型求解，得：二、线性规划数学模型的几种表达形式一般形式目标函数：Max（Min）z=c1x1+c2x2+…+cnxn

约束条件：s.t.a11x1+a12x2+…+a1nxn

≤（=,≥）b1

a21x1+a22x2+…+a2nxn

≤（=,≥）b2…………

am1x1+am2x2+…+amnxn

≤（=,≥）bm

x1，x2，…，xn≥0简写形式目标函数：Max（Min）z=

约束条件：s.t.

≤（=,≥）bi,i=1,2,…..m

xj≥0,j=1,2,….n二、线性规划数学模型的几种表达形式一般形式简写形式向量形式C=(c1,c2,…,cn)

价值向量,二、线性规划数学模型的几种表达形式限定向量变量xj对应的系数列向量向量形式二、线性规划数学模型的几种表达形式限定向量变量xj对二、线性规划数学模型的几种表达形式矩阵形式约束条件系数矩阵二、线性规划数学模型的几种表达形式矩阵形式约束条件系数矩阵第二节线性规划问题的标准形式一、标准形式目标函数：Maxz=c1x1+c2x2+…+cnxn

约束条件：s.t.a11x1+a12x2+…+a1nxn

=b1

a21x1+a22x2+…+a2nxn

=b2…………

am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn≥0或即:同时满足如下四个条件:目标函数求极大约束条件全为等式约束条件右端常数项全为非负变量取值全为非负第二节线性规划问题的标准形式一、标准形式或即:同时§2.1线性规划问题与标准形式为了今后讨论的方便，我们称以下两种形式的线性规划问题为线性规划的规范形式（CanonicalForm）： min z＝CTX s.t. AX≥b

X≥0 max z＝CTX s.t. AX≤b

X≥0

§2.1线性规划问题与标准形式为了§2.1线性规划问题与标准形式而称以下的形式为标准形式（StandardForm）： maxz＝CTX s.t. AX＝b

X≥0

对于各种非标准形式的线性规划问题，我们总可以通过以下的变换，将其转化为标准形式。1极小化目标函数的问题2约束条件不是等式的问题3变量无符号限制的问题§2.1线性规划问题与标准形式而1极小化目标函数的问题

设目标函数为令z’＝－z，则以上极大化问题和极小化问题有相同的最优解，即但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即min z＝－maxz’1极小化目标函数的问题

设目标函数为令z’＝－z，则以上极2约束条件不是等式的问题

设约束条件为

(i=1,2……,m)可以引进一个新的变量xn+i，使它等于约束右边与左边之差

显然xn+I也具有非负约束，即xn+i≥0，这时新的约束条件成为

当约束条件为2约束条件不是等式的问题

设约束条件为

2约束条件不是等式的问题时，类似地令则同样有xn+i≥0，新的约束条件成为为了使约束由不等式成为等式而引进的变量xn+i称为“松弛变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。

2约束条件不是等式的问题时，类似地令为3变量无符号限制的问题

在标准形式中，每一个变量都有非负约束。当一个变量xj没有非负约束时，可以令

xj=xj’-xj”

其中

xj’≥0，xj”≥0

即用两个非负变量之差来表示一个无符号限制的变量，当xj的符号取决于xj’和xj”的大小。3变量无符号限制的问题在标准形式中，每一个变量都§2.2线性规划问题的几何解释

对于只有两个变量的线性规划问题，可以在二维直角坐标平面上表示线性规划问题。Maxz=x1+3x2s.tx1+x2≤6-x1+2x2≤8x1,x2≥0例1.4.1的线性规划问题的可行域如图1.4.1中阴影部分所示。§2.2线性规划问题的几何解释

对于只有两个变量的线性规划§2.2线性规划问题的几何解释

§2.2线性规划问题的几何解释

§2.2线性规划问题的几何解释

在以上问题中，目标函数等值线在平行移动过程中与可行域的最后一个交点是B点，这就是线性规划问题的最优解，这个最优解可以由两直线

x1+x2=6 -x1+2x2=8的交点求得

最优解的目标函数值为

§2.2线性规划问题的几何解释

在以上问题中，目标函数等值§2.2线性规划问题的几何解释

定义1.4.3设S是n维空间中的一个点集。若对任意n维向量X1S，X2S，且X1X2，以及任意实数（01），有

X=X1+(1-)X2S则称S为n维空间中的一个凸集。点X称为点X1和X2的凸组合。以上定义有明显的几何意义，它表示凸集S中的任意两个不相同的点连线上的点（包括这两个端点），都位于凸集S之中。图1.4.2表示二维平面中一些凸集和非凸集的例子。§2.2线性规划问题的几何解释

定义1.4.3设S是n维§2.2线性规划问题的几何解释

(a)凸集

(b)凸集

(c)凸集

(d)非凸集

(e)非凸集 (d)非凸集

(f)非凸集

§2.2线性规划问题的几何解释

(a)凸集 (§2.2线性规划问题的几何解释

定义1.4.4设S为一凸集，且XS，X1S，X2S。对于01，若

X=X1+(1-)X2则必定有X=X1=X2，则称X为S的一个极点。运用以上的定义，线性规划的可行域以及最优解有以下性质：1、若线性规划的可行域非空，则可行域必定为一凸集。2、若线性规划有最优解，则最优解至少位于一个极点上。这样，求线性规划最优解的问题，从在可行域内无限个可行解中搜索的问题转化为在其可行域的有限个极点上搜索的问题。最后，来讨论线性规划的可行域和最优解的几种可能的情况。1、可行域为封闭的有界区域2、可行域为非封闭的无界区域§2.2线性规划问题的几何解释

定义1.4.4设S为一凸§2.2线性规划问题的几何解释

3、可行域为空集，因而没有可行解。以上几种情况的图示如下：(a)可行域有界(b)可行域有界(c)可行域无界

唯一最优解

唯一最优解

唯一最优解§2.2线性规划问题的几何解释

3、可行域为空集，因而没有§2.2线性规划问题的几何解释

(d)可行域无界

(e)可行域无界(f)可行域为空集

多个最优解 目标函数无界 无可行解图1.4.3线性规划可行域和最优解的几种情况§2.2线性规划问题的几何解释

(d)可行域无界§2.3单纯形法方法

设线性规划的约束条件为

AX=b

X≥0其中A为m×n的矩阵，n>m，秩A=m，b为m×1向量。定义2.6线性规划的基(Basis)设B是A矩阵中的一个非奇异的m×m子矩阵，则称B为线性规划的一个基(矩阵).定义2.7设B是线性规划的一个基（矩阵），线性规划的解:称为线性规划与基B对应的基础解。若其中B-1b0，则称以上的基础解为一基础可行解，相应的基B称为可行基。定理2.1线性规划的基础可行解就是可行域的极点。

§2.3单纯形法方法设线性规划的约束条件为§2.3单纯形法方法1单纯形原理的矩阵描述

2单纯形表

3初始基础可行解

4退化和循环

§2.3单纯形法方法1单纯形原理的矩阵描述1单纯形原理的矩阵描述

设标准的线性规划问题为

max z= CTX s.t. AX=b (1.6.1) X0并设

A=[a1，a2，…，an]其中aj(j=1，2，…，n)是A矩阵的第j个列向量。

B=[a1，a2，…，am]是A的一个基。1单纯形原理的矩阵描述

设标准的线性规划问题为1单纯形原理的矩阵描述这样，矩阵A可以分块记为A=[B，N]，相应地，向量X和C可以记为并设R为非基变量的下标集合。利用以上的记号，（1.6.1）中的等式约束AX=b可以写成

BXB+NXN=b即

XB=B-1b-B-1NXN (1.6.2)这就是在约束条件中，基变量用非基变量表出的形式。1单纯形原理的矩阵描述这样，矩阵A可以分块记为A=[B，N1单纯形原理的矩阵描述对于一个确定的基B，目标函数z可以写成

将(1.6.2)式代入以上目标函数表达式，得到目标函数z用非基变量表出的形式

1单纯形原理的矩阵描述对于一个确定的基B，目标函数z可以写1单纯形原理的矩阵描述(1.6.2)和(1.6.3)式表示，非基变量的任何一组确定的值，基变量和目标函数都有一组确定的值与之对应。特别，当XN=0时，相应的解

就是对应于基B的基础解。如果B是一个可行基，则有

1单纯形原理的矩阵描述(1.6.2)和(1.6.3)式表示1单纯形原理的矩阵描述下面我们来详细说明如何实现以上步骤。步骤1、获得初始基础可行解的一般化的方法将在下一节中叙述。在这里，我们假定已经获得了一个初始的可行基B，基B对应的基础解为

当前的目标函数值为

1单纯形原理的矩阵描述下面我们来详细说明如何实现以上步骤。1单纯形原理的矩阵描述步骤2、确定进基的非基变量xk由(1.6.1)可知，当前目标函数值用非基变量用非基变量表出的形式是

令

1单纯形原理的矩阵描述步骤2、确定进基的非基变量xk 令1单纯形原理的矩阵描述则

如果对于所有jR，有zj-cj0，则任何非基变量xj的值由0开始增加都不会使z减少，因此当前基B已是最优基，相应的基础可行解

如果有kR，使zk-ck>0，则非基变量xk的增加将会使目标函数值减少。为了使目标函数值下降得快一些，一般选取满足1单纯形原理的矩阵描述则 如果对于所有jR，有zj-1单纯形原理的矩阵描述

的非基变量xk为进基变量。由于除xk以外的非基变量的值均保持为0不变，这时目标函数可以表示为

步骤3、确定基变量中离基的变量xBr在(1.6.2)中，令1单纯形原理的矩阵描述 的非基变量xk为进基变量。由于除1单纯形原理的矩阵描述

则(1.6.2)可以表示为

当进基变量xk的值由0增加到某一正值，其余非基变量均保持为0时，上式成为

1单纯形原理的矩阵描述 则(1.6.2)可以表示为 当1单纯形原理的矩阵描述

即

1单纯形原理的矩阵描述 即 1单纯形原理的矩阵描述在(1.6.6)中，有以下几种情形：（1）如果向量Yk中所有的分量yik0，则xk的增加将不会使任何xBi(i=1，2，...，m)减少，这时xk可无限增加，同时所有的基变量仍保持非负。同时由于xk在目标函数中的系数zk-ck>0，由(1.6.5)可知当xk增加时目标函数将无限减少，即目标函数无界。（2）如果向量Yk中至少有一个分量yik>0，则xk由0开始增加将会使相应的基变量xBi的值由当前的值bi开始减少。当xk增加到

1单纯形原理的矩阵描述在(1.6.6)中，有以下几种情形：1单纯形原理的矩阵描述相应的基变量xBr=0，而其余的基变量xBi0（i=1，2，...，m，ir），这时基变量xBr离基，它在基B中相应的列向量aBr将换出基矩阵，进基变量xk在A矩阵中相应的列向量ak将取代基矩阵B中aBr的位置，得到新的可行基

B’=[aB1，aB2，…，aBr-1，ak，aBr+1，…，aBm]新的基B’相应的基变量的值为

1单纯形原理的矩阵描述相应的基变量xBr=0，而其余的基变1单纯形原理的矩阵描述B’相应的非基变量的值为

XN=0B’对应的目标函数值为步骤4、由新的基B’重新确定非基变量集合R’，并重新计算(1.6.4)以判定B’是否为最优基。若不是，计算(1.6.4)~(1.6.8)以实现进一步的基变换。

1单纯形原理的矩阵描述B’相应的非基变量的值为步骤4、由新2单纯形表

单纯形算法的实质是将非基变量视为一组参数，并将目标函数和基变量都表示成为由非基变量表示的形式。即（1.6.2）和（1.6.3）两式。这样就可以讨论当非基变量变化时，目标函数和基变量随之变化的情况。我们可以用一个矩阵来表示单纯形法迭代中所需要的全部信息，这就是所谓的单纯形表。设线性规划问题为

maxz=CTX s.t. AX=b (1.7.1)

X0并设B是A的一个可行基，并记A=[B，N]，相应地将目标函数系数向量C以及变量X表示为2单纯形表单纯形算法的实质是将非基变量视为一组参数，并将2单纯形表

则(1.7.1)可表为即2单纯形表 则(1.7.1)可表为即2单纯形表

将(1.7.3)的系数写成矩阵形式，有zXBXNRHS10-CBT-CNT0BNb2单纯形表 将(1.7.3)的系数写成矩阵形式，有zXB2单纯形表称以上矩阵为线性规划问题的系数矩阵（并不是单纯形表）。为了将约束中的基变量用非基变量表出，用B-1左乘以上系数矩阵的后m行，得到zXBXNRHS1-CBT0-CNT0IB-1NB-1b为了将第一行中的目标函数z用非基变量XN表出，在矩阵的后m行左乘CBT后加到第一行上，消去基变量在目标函数中的系数，得到2单纯形表称以上矩阵为线性规划问题的系数矩阵（并不是单纯形2单纯形表zXBXNRHS10TCBTB-1bCBTB-1N-CNT0IB-1NB-1b以上矩阵的第一行与(1.6.3)完全等价，后m行与(1.6.2)完全等价。这一矩阵称为与基B对应的单纯形表。单纯形表可以由系数矩阵经过一系列行变换得到，这些行变换使得系数矩阵中的基矩阵变为单位矩阵I，而将基变量在目标函数中的系数全消为零。

2单纯形表zXBXNRHS10TCBTB-1bCBTB-12单纯形表利用上一节中的记号，可以将表1.7.3的单纯形表用分量的形式表示如表1.7.4。

zx1..xr..xmxk…xjRHS10…0…0…y1k…y1j…b10001…0…00…1…00…0…1…y1k…y1j……yr

k…yrj……ym

k…ym

j…b1BrBm可以看出，单纯形表中直接包含了单纯形迭代所需要的一切信息。

2单纯形表利用上一节中的记号，可以将表1.7.3的单纯形表2单纯形表用单纯形表求解线性规划问题的步骤可以归纳如下：1、写出线性规划问题的系数矩阵表；2、找到一个可行基B，对系数矩阵进行变换，使得：（1）基矩阵成为单位矩阵；（2）基变量在目标函数中的系数为零。从而得到以B为基的单纯形表。3、根据单纯形表，确定进基变量xk和离基变量xr，并根据列指标k和行指标r确定主元yr

k；4、以yr

k为主元进行行变换（称为以yrk为主元的旋转运算），使得单纯形表中yr

k所在的列中其他元素为0，yr

k本身为1；重复步骤3、4，直至获得最优解或确定目标函数无界。

2单纯形表用单纯形表求解线性规划问题的步骤可以归纳如下：3

初始基础可行解

设线性规划问题为

minz=CTX s.t. AX=b X≥0 (2.14) 第一阶段：引进人工变量Xa=(xn+1，xn+2，…，xn+m)T，构造辅助问题

(2.15)

3初始基础可行解

设线性规划问题为3

初始基础可行解求解辅助问题。若辅助问题的最优基B全部在A中，即Xa全部是非基变量（minz’=0），则B为(2.14)的一个可行基。转第二阶段。若辅助问题的最优目标函数值minz’>0，则至少有一个人工变量留在第一阶段问题最优解的基变量中，这时(2.14)无可行解。第二阶段：以第一阶段(2.15)的最优基B作为(1.8.4)的初始可行基，求解(2.14)，得到(2.14)的最优基和最优解。3初始基础可行解求解辅助问题。若辅助问题的最优基B全部在A4退化和循环如何防止出现循环作了大量研究。1952年Charnes提出了“摄动法”，1954年Dantzig，Orden和Wolfe又提出了“字典序法”。这些方法都比较复杂，同时也降低了叠代的速度。

1976年，Bland提出了一个避免循环的新方法，其原则十分简单。仅在选择进基变量和离基变量时作了以下规定：1、在选择进基变量时，在所有zj-cj>0的非基变量中选取下标最小的进基；2、当有多个变量同时可作为离基变量时，选择下标最小的那个变量离基。这样就可以避免出现循环。当然，用Bland的方法，由于选取进基变量时不再考虑zj-cj绝对值的大小，将会导致收敛速度的降低。

4退化和循环如何防止出现循环作了大量研究。1952年Cha第二三四五章线性规划§2.1线性规划问题与标准形式§2.2线性规划问题的几何解释§2.3单纯型法方法第二三四五章线性规划问题的提出（1）【例】派公司是一个生产高尔夫器材的小型公司，公司决定生产中高价位的高尔夫袋。产品的生产过程有四个程序：切割并印染原材料、缝合、成型、检查和包装，不同价位高尔夫袋生产程序的耗时信息如下表，表中还列出了派公司在本轮生产过程中每个部门的最大生产时间。问题的提出（1）【例】派公司是一个生产高尔夫器材的小型公司，问题的提出（2）会计部门的数据表明，生产一个标准袋的利润是10美元，生产一个高级袋的利润是9美元。如何安排两种产品的生产才能使公司获得最大利润？耗时/标准袋耗时/高档袋最大生产时间切割印染0.71630缝合0.55/6600成型12/3708检查包装0.10.25135问题的提出（2）会计部门的数据表明，生产一个标准袋的利润是1问题的提出（3）设x1、x2分别为两种高尔夫袋的生产量，则该计划问题可用如下数学模型表示为：问题的提出（3）设x1、x2分别为两种高尔夫袋的生产量，则该§2.1线性规划问题与标准形式

典例1-----生产计划问题例2.某工厂在计划期内要生产产品I和产品II这两种产品，已知生产单位产品所需的设备台时及A、B两种设备计划期的有效台时，如下表：问如何安排生产最有利？解∶设产品I和产品II的产量分别为x1和x2件,利润为Z,则:

Z=x1+2x2Max目标函数2x1+2x2≤80x1+2x2≤4x1,x2≥0约束条件S.t.非负条件§2.1线性规划问题与标准形式

典例1-----[企业管理]MBA运筹学2第二五章线性规划课件above,above,[企业管理]MBA运筹学2第二五章线性规划课件[企业管理]MBA运筹学2第二五章线性规划课件典例2----配料问题

Z=3x1+2x2Min目标函数12x1+3x2≥42x1+3x2≥23x1+15x2≥5x1+x2=1x1,x2≥0约束条件S.t.典例2----配料问题Z=3x1+2x2Mi典例3----食谱问题[例3]问在满足营养的条件下,如何安排食谱最有利?解:设每人每周食用大米、白菜、鸡蛋、猪肉的数量分别为x1、x2、

x3、

x4Z=C1x1+C2x2+C3x3+C4x4Mina11x1+a12x2+a13x3+a14x4b1=a21x1+a22x2+a23x3+a24x4=

b2a31x1+a32x2+a33x3+a34x4=

b3x1,x2,x3,

x4≥0典例3----食谱问题[例3]问在满足营养的条件下,如何安排食谱问题的拓展问在满足营养的条件下,如何安排食谱最有利?Z=C1x1+C2x2+C3x3+C4x4+...+CnxnMina11x1+a12x2+a13x3+a14x4+…..+a1nxn=

b1a21x1+a22x2+a23x3+a24x4+…..+a2nxn=

b2a31x1+a32x2+a33x3+a34x4+…..+a3nxn=

b3am1x1+am2x2+am3x3+am4x4+…..+amnxn=

bmx1,x2,x3,...

xn≥0∶数学模型食谱问题的拓展问在满足营养的条件下,如何安排食谱最有利?NewBedfordSteel炼焦煤供应问题

AshleyBedfordConsolDunbyEarlamFlorenceGastonHopt供应量(千吨/年）300600510655575680450490工会（U）/非工会（N）

U

U

N

U

N

U

N

N卡车（T）/

铁路（R）

R

T

R

T

T

T

R

R可燃率（%）1516182021222325价格(＄/吨）49.5050.0061.0063.5066.5071.0072.5080.00NewBedfordSteel(NBS)是一家小型的炼钢企业。炼焦煤(cokingcoal)是NBS公司炼钢时所必需的一种原材料，每年的需求量是100至150万吨。现在到了该公司计划明年生产的时候了，他们收到了来自八家供应商的报价。NewBedfordSteel炼焦煤供应问题NewBedfordSteel炼焦煤供应问题根据对未来的形势估计和生产现状的考察，NBS计划明年要定购1,225千吨的炼焦煤。这些炼焦煤的平均可燃率至少要达到19%。为了不影响劳工关系，NBS决定至少50%的炼焦煤要来自于工会煤矿。另外，每年由火车运输的炼焦煤量至多不超过650千吨，而由卡车运输的炼焦煤量至多不超过720千吨。现在要解决以下问题：为了使炼焦煤的成本最小，应该从各个供应商处定购多少吨炼焦煤？NBS的总供应成本是多少？NBS的平均供应成本是多少？NewBedfordSteel炼焦煤供应问题根NBS供应问题的数学表达变量：A= 从Ashley 处定购的炼焦煤量（千吨）B= 从Bedford 处定购的炼焦煤量（千吨）C= 从Consol 处定购的炼焦煤量（千吨）D= 从Dunby 处定购的炼焦煤量（千吨）E= 从Earlam 处定购的炼焦煤量（千吨）F= 从Florence 处定购的炼焦煤量（千吨）G= 从Gaston 处定购的炼焦煤量（千吨）H= 从Hopt 处定购的炼焦煤量（千吨）NBS供应问题的数学表达变量：供应成本成：49.5A+50B+61C+63.5D+66.5E+71F+72.5G+80H供应约束：A+B+C+D+E+F+G+H=1,225工会煤矿的约束：A+B–C+D–E+F–G–H≥0卡车运输量约束：B+D+E+F≤720火车运输量约束：A+C+G+H≤650平均可燃率约束：可改写成：–4A–3B–C+D+2E+3F+4G+6H≥0各煤矿的炼焦煤供应量约束：A≤300，B≤600，C≤510，D≤655，E≤575，F≤680，G≤450，H≤490非负约束：A≥0，B≥0，C≥0，D≥0，E≥0，F≥0，G≥0，H≥0供应成本成：NBS的炼焦煤供应问题的线性最优化模型MINIMIZECOST=49.5A+50B+61C+63.5D+66.5E+71F+72.5G+80HSUBJECTTO：SUPPLY： A+B+C+D+E+F+G+H=1,225UNION： A+B–C+D–E+F–G–H≥0TRUCK： B+D+E+F≤720RAIL：A+C+G+H≤650VOL：–4A–3B–C+D+2E+3F+4G+6H≥0ACAP： A≤300BCAP： B≤600CCAP： C≤510DCAP： D≤655ECAP： E≤575FCAP： F≤680GCAP： G≤450HCAP： H≤490NONNEGATIVITYCONDITIONS：A≥0,B≥0,C≥0,D≥0,E≥0,F≥0,G≥0,H≥0NBS的炼焦煤供应问题的线性最优化模型MINIMIZECNBS的炼焦煤供应问题的线性最优化模型求解，得：A=55千吨，B=600千吨，C=0千吨，

D=20千吨，E=100千吨，F=0千吨，

G=450千吨，H=0千吨；最小成本=73,267.50千美元；平均供应成本=73,267.50/1,225=59.81美元/吨NBS的炼焦煤供应问题的线性最优化模型求解，得：二、线性规划数学模型的几种表达形式一般形式目标函数：Max（Min）z=c1x1+c2x2+…+cnxn

约束条件：s.t.a11x1+a12x2+…+a1nxn

≤（=,≥）b1

a21x1+a22x2+…+a2nxn

≤（=,≥）b2…………

am1x1+am2x2+…+amnxn

≤（=,≥）bm

x1，x2，…，xn≥0简写形式目标函数：Max（Min）z=

约束条件：s.t.

≤（=,≥）bi,i=1,2,…..m

xj≥0,j=1,2,….n二、线性规划数学模型的几种表达形式一般形式简写形式向量形式C=(c1,c2,…,cn)

价值向量,二、线性规划数学模型的几种表达形式限定向量变量xj对应的系数列向量向量形式二、线性规划数学模型的几种表达形式限定向量变量xj对二、线性规划数学模型的几种表达形式矩阵形式约束条件系数矩阵二、线性规划数学模型的几种表达形式矩阵形式约束条件系数矩阵第二节线性规划问题的标准形式一、标准形式目标函数：Maxz=c1x1+c2x2+…+cnxn

约束条件：s.t.a11x1+a12x2+…+a1nxn

=b1

a21x1+a22x2+…+a2nxn

=b2…………

am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn≥0或即:同时满足如下四个条件:目标函数求极大约束条件全为等式约束条件右端常数项全为非负变量取值全为非负第二节线性规划问题的标准形式一、标准形式或即:同时§2.1线性规划问题与标准形式为了今后讨论的方便，我们称以下两种形式的线性规划问题为线性规划的规范形式（CanonicalForm）： min z＝CTX s.t. AX≥b

X≥0 max z＝CTX s.t. AX≤b

X≥0

§2.1线性规划问题与标准形式为了§2.1线性规划问题与标准形式而称以下的形式为标准形式（StandardForm）： maxz＝CTX s.t. AX＝b

X≥0

对于各种非标准形式的线性规划问题，我们总可以通过以下的变换，将其转化为标准形式。1极小化目标函数的问题2约束条件不是等式的问题3变量无符号限制的问题§2.1线性规划问题与标准形式而1极小化目标函数的问题

设目标函数为令z’＝－z，则以上极大化问题和极小化问题有相同的最优解，即但必须注意，尽管以上两个问题的最优解相同，但他们最优解的目标函数值却相差一个符号，即min z＝－maxz’1极小化目标函数的问题

设目标函数为令z’＝－z，则以上极2约束条件不是等式的问题

设约束条件为

(i=1,2……,m)可以引进一个新的变量xn+i，使它等于约束右边与左边之差

显然xn+I也具有非负约束，即xn+i≥0，这时新的约束条件成为

当约束条件为2约束条件不是等式的问题

设约束条件为

2约束条件不是等式的问题时，类似地令则同样有xn+i≥0，新的约束条件成为为了使约束由不等式成为等式而引进的变量xn+i称为“松弛变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。

2约束条件不是等式的问题时，类似地令为3变量无符号限制的问题

在标准形式中，每一个变量都有非负约束。当一个变量xj没有非负约束时，可以令

xj=xj’-xj”

其中

xj’≥0，xj”≥0

即用两个非负变量之差来表示一个无符号限制的变量，当xj的符号取决于xj’和xj”的大小。3变量无符号限制的问题在标准形式中，每一个变量都§2.2线性规划问题的几何解释

对于只有两个变量的线性规划问题，可以在二维直角坐标平面上表示线性规划问题。Maxz=x1+3x2s.tx1+x2≤6-x1+2x2≤8x1,x2≥0例1.4.1的线性规划问题的可行域如图1.4.1中阴影部分所示。§2.2线性规划问题的几何解释

对于只有两个变量的线性规划§2.2线性规划问题的几何解释

§2.2线性规划问题的几何解释

§2.2线性规划问题的几何解释

在以上问题中，目标函数等值线在平行移动过程中与可行域的最后一个交点是B点，这就是线性规划问题的最优解，这个最优解可以由两直线

x1+x2=6 -x1+2x2=8的交点求得

最优解的目标函数值为

§2.2线性规划问题的几何解释

在以上问题中，目标函数等值§2.2线性规划问题的几何解释

定义1.4.3设S是n维空间中的一个点集。若对任意n维向量X1S，X2S，且X1X2，以及任意实数（01），有

X=X1+(1-)X2S则称S为n维空间中的一个凸集。点X称为点X1和X2的凸组合。以上定义有明显的几何意义，它表示凸集S中的任意两个不相同的点连线上的点（包括这两个端点），都位于凸集S之中。图1.4.2表示二维平面中一些凸集和非凸集的例子。§2.2线性规划问题的几何解释

定义1.4.3设S是n维§2.2线性规划问题的几何解释

(a)凸集

(b)凸集

(c)凸集

(d)非凸集

(e)非凸集 (d)非凸集

(f)非凸集

§2.2线性规划问题的几何解释

(a)凸集 (§2.2线性规划问题的几何解释

定义1.4.4设S为一凸集，且XS，X1S，X2S。对于01，若

X=X1+(1-)X2则必定有X=X1=X2，则称X为S的一个极点。运用以上的定义，线性规划的可行域以及最优解有以下性质：1、若线性规划的可行域非空，则可行域必定为一凸集。2、若线性规划有最优解，则最优解至少位于一个极点上。这样，求线性规划最优解的问题，从在可行域内无限个可行解中搜索的问题转化为在其可行域的有限个极点上搜索的问题。最后，来讨论线性规划的可行域和最优解的几种可能的情况。1、可行域为封闭的有界区域2、可行域为非封闭的无界区域§2.2线性规划问题的几何解释

定义1.4.4设S为一凸§2.2线性规划问题的几何解释

3、可行域为空集，因而没有可行解。以上几种情况的图示如下：(a)可行域有界(b)可行域有界(c)可行域无界

唯一最优解

唯一最优解

唯一最优解§2.2线性规划问题的几何解释

3、可行域为空集，因而没有§2.2线性规划问题的几何解释

(d)可行域无界

(e)可行域无界(f)可行域为空集

多个最优解 目标函数无界 无可行解图1.4.3线性规划可行域和最优解的几种情况§2.2线性规划问题的几何解释

(d)可行域无界§2.3单纯形法方法

设线性规划的约束条件为

AX=b

X≥0其中A为m×n的矩阵，n>m，秩A=m，b为m×1向量。定义2.6线性规划的基(Basis)设B是A矩阵中的一个非奇异的m×m子矩阵，则称B为线性规划的一个基(矩阵).定义2.7设B是线性规划的一个基（矩阵），线性规划的解:称为线性规划与基B对应的基础解。若其中B-1b0，则称以上的基础解为一基础可行解，相应的基B称为可行基。定理2.1线性规划的基础可行解就是可行域的极点。

§2.3单纯形法方法设线性规划的约束条件为§2.3单纯形法方法1单纯形原理的矩阵描述

2单纯形表

3初始基础可行解

4退化和循环

§2.3单纯形法方法1单纯形原理的矩阵描述1单纯形原理的矩阵描述

设标准的线性规划问题为

max z= CTX s.t. AX=b (1.6.1) X0并设

A=[a1，a2，…，an]其中aj(j=1，2，…，n)是A矩阵的第j个列向量。

B=[a1，a2，…，am]是A的一个基。1单纯形原理的矩阵描述

设标准的线性规划问题为1单纯形原理的矩阵描述这样，矩阵A可以分块记为A=[B，N]，相应地，向量X和C可以记为并设R为非基变量的下标集合。利用以上的记号，（1.6.1）中的等式约束AX=b可以写成

BXB+NXN=b即

XB=B-1b-B-1NXN (1.6.2)这就是在约束条件中，基变量用非基变量表出的形式。1单纯形原理的矩阵描述这样，矩阵A可以分块记为A=[B，N1单纯形原理的矩阵描述对于一个确定的基B，目标函数z可以写成

将(1.6.2)式代入以上目标函数表达式，得到目标函数z用非基变量表出的形式

1单纯形原理的矩阵描述对于一个确定的基B，目标函数z可以写1单纯形原理的矩阵描述(1.6.2)和(1.6.3)式表示，非基变量的任何一组确定的值，基变量和目标函数都有一组确定的值与之对应。特别，当XN=0时，相应的解

就是对应于基B的基础解。如果B是一个可行基，则有

1单纯形原理的矩阵描述(1.6.2)和(1.6.3)式表示1单纯形原理的矩阵描述下面我们来详细说明如何实现以上步骤。步骤1、获得初始基础可行解的一般化的方法将在下一节中叙述。在这里，我们假定已经获得了一个初始的可行基B，基B对应的基础解为

当前的目标函数值为

1单纯形原理的矩阵描述下面我们来详细说明如何实现以上步骤。1单纯形原理的矩阵描述步骤2、确定进基的非基变量xk由(1.6.1)可知，当前目标函数值用非基变量用非基变量表出的形式是

令

1单纯形原理的矩阵描述步骤2、确定进基的非基变量xk 令1单纯形原理的矩阵描述则

如果对于所有jR，有zj-cj0，则任何非基变量xj的值由0开始增加都不会使z减少，因此当前基B已是最优基，相应的基础可行解

如果有kR，使zk-ck>0，则非基变量xk的增加将会使目标函数值减少。为了使目标函数值下降得快一些，一般选取满足1单纯形原理的矩阵描述则 如果对于所有jR，有zj-1单纯形原理的矩阵描述

的非基变量xk为进基变量。由于除xk以外的非基变量的值均保持为0不变，这时目标函数可以表示为

步骤3、确定基变量中离基的变量xBr在(1.6.2)中，令1单纯形原理的矩阵描述 的非基变量xk为进基变量。由于除1单纯形原理的矩阵描述

则(1.6.2)可以表示为

当进基变量xk的值由0增加到某一正值，其余非基变量均保持为0时，上式成为

1单纯形原理的矩阵描述 则(1.6.2)可以表示为 当1单纯形原理的矩阵描述

即

1单纯形原理的矩阵描述 即 1单纯形原理的矩阵描述在(1.6.6)中，有以下几种情形：（1）如果向量Yk中所有的分量yik0，则xk的增加将不会使任何xBi(i=1，2，...，m)减少，这时xk可无限增加，同时所有的基变量仍保持非负。同时由于xk在目标函数中的系数zk-ck>0，由(1.6.5)可知当xk增加时目标函数将无限减少，即目标函数无界。（2）如果向量Yk中至少有一个分量yik>0，则xk由0开始增加将会使相应的基变量xBi的值由当前的值bi开始减少。当xk增加到

1单纯形原理的矩阵描述在(1.6.6)中，有以下几种情形：1单纯形原理的矩阵描述相应的基变量xBr=0，而其余的基变量xBi0（i=1，2，...，m，ir），这时基变量xBr离基，它在基B中相应的列向量aBr将换出基矩阵，进基变量xk在A矩阵中相应的列向量ak将取代基矩阵B中aBr的位置，得到新的可行基