第一章-线性规划课件

第一讲线性规划第一章线性规划的数学模型(1)第一节线性规划一般模型(4)第二节线性规划的图解法(16)第三节线性规划的标准型（23）第四节线性规划解的概念(32)第二章线性规划的单纯形法(40)第一节单纯形法原理(41)第二节表格单纯形法(53)第三节人工变量问题(67)第四节单纯形法补遗(76)第三章线性规划的对偶理论(93)第四章线性规划灵敏性分析(123)1第一章线性规划的数学模型线性规划LinearProgrammingLP规划论中的静态规划解决有限资源的最佳分配问题求解方法：图解法单纯形解法2第一章线性规划的数学模型第一节线性规划一般模型第二节线性规划的图解法第三节线性规划的标准型第四节线性规划解的概念3第一节线性规划一般模型一、线性规划问题的三个要素

决策变量决策问题待定的量值称为决策变量。决策变量的取值要求非负。约束条件任何问题都是限定在一定的条件下求解，把各种限制条件表示为一组等式或不等式，称之为约束条件。LP的约束条件，都是决策变量的线性函数。目标函数衡量决策方案优劣的准则，如时间最省、利润最大、成本最低。目标函数是决策变量的线性函数。有的目标要实现极大，有的则要求极小。4第一节线性规划一般模型例1.生产计划问题

某厂生产甲乙两种产品，各自的零部件分别在A、B车间生产，最后都需在C车间装配，相关数据如表所示：

问如何安排甲、乙两产品的产量，使利润为最大。二、线性规划模型的构建

产品车间工时单耗甲乙生产能力ABC

10023481236单位产品获利355第一节线性规划一般模型(1)决策变量。要决策的问题是甲、乙两种产品的产量，因此有两个决策变量：设x1为甲产品产量，x2为乙产品产量。(2)约束条件。生产这两种产品受到现有生产能力的制约，用量不能突破。生产单位甲产品的零部件需耗用A车间的生产能力1工时，生产单位乙产品不需耗用A车间的生产能力，A车间的能力总量为8工时，则A车间能力约束条件表述为

x1≤8同理，B和C车间能力约束条件为

2x2≤123x1+4x2≤36建立模型6第一节线性规划一般模型(3)目标函数。目标是利润最大化，用Z表示利润，则

maxZ=

3x1+5x2

(4)非负约束。甲乙产品的产量不应是负数，否则没有实际意义，这个要求表述为

x1

≥0，x2

≥0综上所述，该问题的数学模型表示为

maxZ=

3x1+5x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0S.t.7第一节线性规划一般模型某名牌饮料在国内有三个生产厂，分布在城市A1、A2、A3,其一级承销商有4个，分布在城市B1、B2、B3、B4，已知各厂的产量、各承销商的销售量及从Ai到Bj的每吨饮料运费为Cij，为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。例2.运输问题

销地产地B1B2B3B4产量A1A2A3

632575843297523销量

23148第一节线性规划一般模型(1)决策变量。设从Ai到Bj的运输量为xij，(2)目标函数。运费最小的目标函数为minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34

(3)约束条件。产量之和等于销量之和,故要满足：供应平衡条件x11+x12+x13+x14=5x21+x22+x23+x24=2x31+x32+x33+x34=3销售平衡条件x11+x21+x31=2x12+x22+x32=3x13+x23+x33=1x14+x24+x34=4非负性约束xij≥0(i=1,2,3；j=1,2,3,4)

9例3有四项工作分给4个人效率表如下。（整数规划之0-1规划）工作工人ABCD甲6231乙7432丙81073丁775410

要求合理分配，使总效率最大

（i=1.2.3.4j=1.2.3.4)2.约束条件①每个人只任一项工作

解：1.确定决策变量11

②每项工作必由一人承担

3．目标函数。12例4：合理下料问题

在180cm材料上，需切割三种毛坯（70cm、52cm、35cm），其需要量分别为100、150、100根，问如何切割，余料最省？13下料方式一二三四五六七八零件需要量A70cm21110000100B52cm02103210150C35cm10130235100余料5623524623514

决策变量j——第j种下料方式的次数，J=1.2,…，8。

约束条件：A：B：C：目标函数：余料最省。15第一节线性规划一般模型用一组非负决策变量表示一个决策问题，存在一定的等式或不等式的线性约束条件，有一个希望达到的目标，可表示成决策变量的线性函数。可能是最大化，也可能是最小化。线性规划一般模型的代数式为：三、线性规划的一般模型

max(min)Z=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn≤(≥,＝)b1a21x1+a22x2+…+a2nxn≤(≥,＝)b2……………am1x1+am2x2+…+amnxn≤(≥,＝)bmx1,x2,…,xn≥(≤)016第二节线性规划的图解法图解法即是用图示的方法来求解线性规划问题。一个二维的线性规划问题，可以在平面图上求解，三维的线性规划则要在立体图上求解，比较麻烦，而维数再高以后就不能图示了。一、图解法的基本步骤17第二节线性规划的图解法1.可行域的确定例1的数学模型为

maxZ=

3x1+5x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0S.t.x1=82x2=123x1+4x2

=36x1x248123690ABC(4,6)D五边形OABCD内(含边界)的任意一点(x1，x2)都是满足所有约束条件的一个解，称之可行解。满足所有约束条件的解的集合，称之为可行域。即所有约束条件共同围成的区域。18第二节线性规划的图解法2.最优解的确定Z=30Z=42Z=15目标函数Z=

3x1+5x2代表以Z为参数的一族平行线。x1=82x2=123x1+4x2

=36x1x248123690ABC(4,6)D等值线：位于同一直线上的点的目标函数值相同。最优解：可行解中使目标函数最优(极大或极小)的解19第二节线性规划的图解法由线性不等式组成的可行域是凸集(凸集的定义是：集合内部任意两点连线上的点都属于这个集合)。目标函数最优值一定在可行域的边界达到，而不可能在其内部。二、几点说明20第二节线性规划的图解法三、解的可能性x1=82x2=123x1+4x2

=36x1x248123690ABC(4,6)D例1的数学模型变为

maxZ=

3x1+4x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0S.t.Z=24Z=36Z=12唯一最优解：只有一个最优点。多重最优解：无穷多个最优解。若在两个顶点同时得到最优解，则它们连线上的每一点都是最优解。21第二节线性规划的图解法无界解：线性规划问题的可行域无界，使目标函数无限增大而无界。（缺乏必要的约束条件）三、解的可能性（续）例如

maxZ=

3x1+2x2-2x1+x2≤2x1-3x2≤3x1≥0,x2≥0-2x1+x2=2x1-3x2=3x2123-1x1123-1Z=6Z=12S.t.22第二节线性规划的图解法无可行解：若约束条件相互矛盾，则可行域为空集三、解的可能性（续）例如

maxZ=

3x1+2x2-2x1+x2≥2x1-3x2≥3x1≥0,x2≥0-2x1+x2=2x1-3x2=3x2123-1x1123-1S.t.23第三节线性规划的标准型线性规划问题的数学模型有各种不同的形式，如目标函数有极大化和极小化；约束条件有“≤”、“≥”和“＝”三种情况；决策变量一般有非负性要求，有的则没有。为了求解方便，特规定两种线性规划的标准形式，非标准型可以转化为标准型。标准形式为：目标函数极大化（或极小化），约束条件为等式，右端常数项bi≥0，决策变量非负。一、标准型24第三节线性规划的标准型1.代数式二、标准型的表达方式有代数式、矩阵式：MaxZ=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn＝b1a21x1+a22x2+…+a2nxn＝b2……………am1x1+am2x2+…+amnxn＝bmx1,x2,…,xn≥0简记maxZ=cjxj

aijxj＝bi

(i=1,2,…,m)xj≥0(j=1,2,…,n)25第三节线性规划的标准型2.矩阵式

26第三节线性规划的标准型目标函数极小化问题

minZ=CTX，只需将等式两端乘以-1即变为极大化问题。

右端常数项非正

两端同乘以-1约束条件为不等式当约束方程为“≤”时，左端加入一个非负的松弛变量，就把不等式变成了等式；当约束条件为“≥”时，不等式左端减去一个非负的剩余变量(也可称松弛变量)即可。

决策变量xk没有非负性要求令xk=xk′-x

k〃，

xk=xk′，xk〃

≥0，用xk′、xk〃

取代模型中xk三、非标准型向标准型转化

27例1

解为自由变量28

例2．

解：

29例3

minZ=

x1+2x2-3x3x1+2x2-x3≤52x1+3x2-x3≥6

-x1-x2+x3≥-2x1≥0,x3≤0S.t.30标准化1

minZ=

x1+2x2+3x3′x1+2x2+x3′≤52x1+3x2+x3′≥6

-x1-x2-x3′≥-2x1≥0,x3′≥0

第三节线性规划的标准型31第三节线性规划的标准型标准化2

minZ=

x1+2(x2′-x2〃)

+3x3′x1+2(x2′-x2〃)

+x3′≤52x1+3(x2′-x2〃)

+x3′≥6

-x1-(x2′-x2〃)

-x3′≥-2x1,

x2′,x2〃

,x3′≥0

标准化3

minZ=

x1+2(x2′-x2〃)

+3x3′x1+2(x2′-x2〃)

+x3′≤52x1+3(x2′-x2〃)+x3′≥6

x1+(x2′-x2〃

)

+x3

′≤2x1,

x2′,x2〃,x3′≥032第三节线性规划的标准型标准化4

minZ=

x1+2(x2′-x2〃)

+3x3′

x1+2(x2′-x2〃)

+x3′+x4=52x1+3(x2′-x2〃)+x3′≥6

x1+(x2′-x2〃)

+x3′≤2x1,

x2′,x2〃,x3′,x4≥0标准化5

minZ=

x1+2(x2′-x2〃)

+3x3′x1+2(x2′-x2〃)

+x3′+x4=5

2x1+3(x2′-x2〃)+x3′-x5=

6

x1+(x2′-x2〃)

+x3′≤2x1,

x2′,x2〃,x3′,x4,x5≥033第三节线性规划的标准型标准化6

minZ=

x1+2(x2′-x2〃)

+3x3′x1+2(x2′-x2〃)

+x3′+x4=52x1+3(x2′-x2〃)+x3′-x5=

6

x1+(x2′-x2〃)

-x3′+x6=2

x1,

x2′,x2〃,x3′,x4,x5,x6

≥0标准化7

maxZ=-x1-2(x2′-x2〃)

-3x3′+0x4+0x5+0x6

x1+2(x2′-x2〃)

+x3′+x4=52x1+3(x2′-x2〃)+x3′-x5=

6

x1+(x2′-x2〃)

-x3′+x6=2x1,

x2′,x2〃,x3′,x4,x5,x6≥0

34第四节线性规划解的概念一、解的概念标准型

①②③1．可行解：满足②③式的解2．可行域：所有可行解的集合3．最优解：满足①的可行解。4．基本解：看②式的解，AX=b35几种情况：①若m=n系数矩阵的秩r（A）=n,即≠0，这时方程组有维一解。②若m＜n，r(A)≠r(A/b)。这时方程组不相容，即无解。③若m＜n，r(A)=r(A/b)=m＜n这时有无穷多组解。线性规划的约束方程通常就是这样的，下面讨论。

36375．基本可行解。若基本解中即X≥0，满足③式，称基本可行解。

38第四节线性规划解的概念

非可行解可行解基解基可行解39二、凸集和极点1.线段设X（1）和X（2）是n维空间的两个点，则满足条件的点X的集合，叫做以X（1）和X（2）为端点的线段。证：二维比例关系：令令40

代入上式

同理y轴：即41

2．凸集。设K是n维空间的一个点集，任意两点的连线上的一切点则称K为凸集。

性质：即凸集中任意两点连线上的任一点在凸集中。3.极点。在凸集中找不到任何另外两点X（1）、X（2），使成立，称X为极点。三、解的几何意义1．可行解。凸集中的任一点。2．基本可行解。凸集中的极点。42第四节线性规划解的概念定理1.若线性规划问题存在可行域，则其可行域一定是凸集。定理2.线性规划问题的基可行解对应可行域的顶点。定理3.若可行域有界，线性规划的目标函数一定可以在可行域的顶点上达到最优。

四、线性规划的基本定理

43第四节线性规划解的概念五、线性规划的解题思路线性规划问题可以有无数个可行解，最优解只可能在顶点上达到，而有限个顶点对应的是基可行解，故只要在有限个基可行解中寻求最优解即可。从一个顶点出发找到一个可行基，得到一组基可行解，拿目标函数做尺度衡量一下看是否最优。如若不是，则向邻近的顶点转移，换一个基再行求解、检验，如此迭代循环目标值逐步改善，直至求得最优解。44

作业：化标准型。

1.

2.45第二章线性规划单纯形法单纯形法(SimplexMethod)是美国人丹捷格(G.Dantzig)1947年创建的。这种方法简捷、规范，是举世公认的解决线性规划问题行之有效的方法。单纯形法的表现形式：代数法表格法矩阵法46第二章线性规划单纯形法第一节单纯形法原理第二节表格单纯形法第三节人工变量问题第四节单纯形法补遗47第一节单纯形法原理例1.生产计划问题

某厂生产甲乙两种产品，各自的零部件分别在A、B车间生产，最后都需在C车间装配，相关数据如表所示：

问如何安排甲、乙两产品的产量，使利润为最大。

产品车间工时单耗甲乙生产能力ABC

10023481236单位产品获利3548第一节单纯形法原理该问题的数学模型表示为

maxZ=

3x1+5x2x1≤82x2≤123x1+4x2≤36x1≥0,x2≥0S.t.49第一节单纯形法原理一、代数解法

例1x1+x3=82x2+x4=123x1+4x2+x5=36-Z+3x1+5x2+0x3+0x4+0x5=0x1,x2,x3,x4,x5≥0x1x2x3x4x5x3x4x5非奇异子阵，做为一个基基变量x3,x4,x5非基变量x1,x250第一节单纯形法原理将基变量用非基变量线性表示，即x3=8-x1x4=12-2x2x5=36-3x1-4x2

令非基变量x1=0，x2=0，找到一个初始基可行解：

x1=0，

x2=0，x3=8，x4=12，

x5=36即X0=(0,0,8,12,36)T一个可行解就是一个生产方案，在上述方案中两种产品都不生产，利润Z=0

。1.求初始基可行解

51第一节单纯形法原理确定进基变量

x1+x3=82x2+x4=123x1+4x2+x5=36-Z+3x1+5x2+0x3+0x4+0x5=0

从目标函数-Z+3x1+5x2+0x3+0x4+0x5=0可知：非基变量x1和x2的系数均为正数，生产哪种产品都会增加利润。因为x2的系数大于x1的系数，即生产单位乙产品比甲产品利润更高一些，故应优先多生产乙产品。2.第一次迭代

52第一节单纯形法原理确定离基变量基变量用非基变量线性表示x3=8–x1x4=12-2x2

x5=36-3x1-4x2保持原非基变量x1=0，x2变成基变量时应保证x3,x4,,x5非负，即有2.第一次迭代（续）x3=8≥0x4=12-2x2≥0x5=36-4x2≥0x2≤12/2x2≤36/453第一节单纯形法原理2.第一次迭代（续）主行主列主元x1+0x2+x3=82x2+x4=123x1+4x2+x5=36-Z+3x1+5x2+0x3+0x4+0x5=0进基变量所在列为主列，离基变量所在行为主行54第一节单纯形法原理基变换进行初等变换，变主元为1，主列为单位列向量。2.第一次迭代（续）

x1+x3=8

x2+1/2x4=63x1+-2x4+x5=12

-Z+3x1+0x2+0x3–5/2x4+0x5=-30

x1+x3=8

x2+1/2x4=6

3x1+-2x4+x5=12

-Z+3x1+5x2+0x3+0x4+0x5=0x1+0x2+x3=82x2+x4=123x1+4x2+x5=36-Z+3x1+5x2+0x3+0x4+0x5=0

x1+x3=8

x2+1/2x4=63x1+4x2+x5=36-Z+3x1+5x2+0x3+0x4+0x5=055第一节单纯形法原理2.第一次迭代（续）将基变量用非基变量线性表示，即x3=8–x1x2=6-1/2x4

x5=12-3x1+4x4令非基变量x1=0，x4=0，找到另一个基可行解

x1=0，

x2=6，x3=8，x4=0，

x5=12即X1=(0,6,8,0,12)T目标函数Z=3056第一节单纯形法原理确定进基变量3.第二次迭代

第一次迭代结果

x1+x3=8

x2+1/2x4=63x1+-2x4+x5=12

-Z+3x1+0x2+0x3–5/2x4+0x5=-30目标函数-Z+3x1+0x2+0x3–5/2x4+0x5=-30，非基变量x1的系数1=3（检验数）为正数，确定x1为进基变量。57第一节单纯形法原理确定离基变量3.第二次迭代（续）x3=8-x1≥0x2=6≥0

x5=12-3x1≥0x1≤8/1x1≤12/3基变量用非基变量线性表示

x3=8–x1x2=6-1/2x4x5=12-3x1+4x4保持原非基变量x4=0，x1变成基变量时应保证

x2,x3,,x5非负，即

58第一节单纯形法原理基变换变主元为1，主列为单位列向量。3.第二次迭代（续）

x1+x3=8

x2+1/2x4=6

x1+-2/3x4+1/3x5=4

-Z+3x1+0x2+0x3–5/2x4+0x5=-30

x3+2/3x4-1/3x5=4

x2+1/2x4=6x1+-2/3x4+1/3x5=4

-Z+3x1+0x2+0x3–5/2x4+0x5=-30x3+2/3x4-1/3x5=4

x2+1/2x4=6x1+-2/3x4+1/3x5=4

-Z+0x1+0x2+0x3-1/2x4-x5=-42

1x1+x3=8

x2+1/2x4=63x1+-2x4+x5=12

-Z+3x1+0x2+0x3–5/2x4+0x5=-3059第一节单纯形法原理3.第二次迭代（续）将基变量用非基变量线性表示，即x3=4–2/3x4+1/3x5x2=6-1/4x4x1=4+2/3x4-1/3x5

令非基变量x4=0，x5=0，又找到一个基可行解

目标函数-Z+0x1+0x2+0x3-1/2x4-x5=-42

x1=4，

x2=6，x3=4，x4=0，

x5=0即X2=(4,6,4,0,0)TZ=42

检验数σj非正，得最优解X*=(4,6,4,0,0)T，Z*=4260第一节单纯形法原理二、单纯形法的几何意义x1=82x2=123x1+4x2

=36x1x248123690ABC(4,6)DX0=(0,0,8,12,36)TX1=(0,6,8,0,12)TX1=(4,6,4,0,0)T61第二节表格单纯形法表格单纯形法，是对上节讨论的方法步骤进行具体化、规范化、表格化的结果。

一、单纯形法表CjC1C2…Cj…Cn比值CBXBbx1x2…xj…xnCB1xB1b1a11a12…a1j…a1n1CB2xB2b2a21a22…a2j…a2n2………………………CBnxBnbmam1am2…amj…amnm检验数j-Z12…j…n62第二节表格单纯形法①将线性规划问题化成标准型。②找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。③计算各非基变量xj的检验数j=Cj-CBPj

′，若所有j≤0，则问题已得到最优解，停止计算，否则转入下步。④根据max{j｜j＞0}=k原则，确定xk为换入变量(进基变量)，再按规则计算：=min{bi′/aik′|aik′＞0}=bl′/aik′

确定xBl为换出变量。建立新的单纯形表，此时基变量中xk取代了xBl的位置。⑤以aik′为主元素进行迭代，把xk所对应的列向量变为单位列向量，即aik′变为1，同列中其它元素为0，转第③

步。

二、单纯形法的计算步骤

63第二节表格单纯形法

maxZ=3x1+5x2+0x3+0x4+0x5=0x1+x3=82x2+x4=123x1+4x2+x5=36

三、单纯形法计算举例(上例)Cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=964第二节表格单纯形法检验数j81010060101/2012300-21x3x2x5050-30300-5/208-4Cj比值CBXBb检验数jx1x2x3x4x53500081010012020103634001x3x4x5000035000-12/2=636/4=965第二节表格单纯形法Cj比值CBXBb检验数jx1x2x3x4x53500081010060101/2012300-21x3x2x5050-30300-5/208-4检验数j40012/3-1/360101/204100-2/31/3x3x2x1053-42000-1/2-1最优解:X*=(4,6,4,0,0)T，Z*=4266

例267

-3-1-1-1X1X2X3X4bX3-221042X4310166Cj-ZJ-2200X2-111/202X440-1/214Cj-Zj00-1068

例3

（j=1、2、3）

6911300X1X2X3X4X5bX43211033X52120121Cj-zj113000X423/201-1/22X311/2101/21Cj-Zj-2-1/200-3/2370

例4

7172

例5

xj≥0（j=1、2、3）

73747576第三节人工变量问题采用人造基的办法：人工构造单位矩阵处理方法有两种：大M法两阶段法77第三节人工变量问题大M法例6

maxZ=

3x1-x2-2x33x1+2x2-3x3=6x1-2x2+x3=4x1,x2,x3≥0S.t.78第三节人工变量问题按大M法构造人造基，引入人工变量x4,x5的辅助问题如下：

maxZ=

3x1-x2-2x3-Mx4-Mx53x1+2x2-3x3+x4=6x1-2x2+x3+x5=4x1,x2,x3,x4,x5≥0Cj比值CBXBb检验数jx1x2x3x4x53-1-2-M-M632-31041-2101-10M3+4M-1-2-2M00x4x5-M-M2479第三节人工变量问题Cj比值CBXBb检验数jx1x2x3x4x53-1-2-M-M632-31041-21013+4M-1-2-2M00x4x5-M-M24检验数j212/3-11/3020-8/32-1/310-3-8M/31+2M-1-4M/30x1x53-M-1检验数j31-2/301/61/210-4/31-1/61/20-5/30-M-5/6-M-1/2x1x33-280例7xj≥0，（j=1、2、3、）

818283解

xj≥0，（j=1……6）84二、二阶段法

例9xj≥0（j=1、2、3）解：第一阶段：引入人工变量，并构造一个新的目标函数为人工变量之和，并取最小值。

xj≥0（j=1……4）85二、二阶段法求解中可出现以下情况：①在最优解中，人工变量全是非基变量，即minz’=0。这表示得到了原问题一个基可行解（去掉人工变量列）。②最优解中含有人工变量，即minz’≠0，这说明原线性规划无可行解，这说明了“只有在采用并不存在的人造活动时约束条件才得到满足。”868788899091第四节单纯形法补遗一、无可行解：最终表中存在人工变量是基变量。例1192第四节单纯形法补遗93二、无界解例12maxZ=

3x1+2x2-2x1+x2≤2x1-3x2≤3x1,x2≥0S.t.标准化

maxZ=

3x1+2x2-2x1+x2+x3=2x1-3x2+x4=3x1,x2,x3,x4≥0Cj比值CBXBb检验数jx1x2x3x432002-211031-301x3x40003200-3检验数j80-512x3x103--31-301-90110-394第四节单纯形法补遗三、多重最优解：最优单纯形表中，存在非基变量的检验数j=0。让这个非基变量进基，继续迭代，得另一个最优解。例1395969798第四节单纯形法补遗四、退化解。有基变量为0，称这种情况为退化解。（原因，模型中存在多余的约束，使多个基可行解对应同一顶点）1．退化是暂时的，最终得非退化解。2．最后得退化最优解。3．产生循环。99如何避免循环：1976年布兰德提出两法则：法则1：若有几个正检验数，选其中下标最小的非基变量为换入变量。法则2：若有几个θ值同时达到最小，就选其中下标最小的基变量为退出变量。100第四节单纯形法补遗101102103104105106107第五节

检验数的讨论已知标准型设Ｘ(0)与Ｘ(1)

是相邻两个顶点，由Ｘ(0)向Ｘ(1)转换108第五节检验数的讨论将x（0）代入约束条件得得可行解X（1）

109第五节

检验数的讨论则x（1）就不可能为基本可行解，将x（1）代入目标函数110第五节

检验数的讨论讨论：1．若：2．若：这时若把可行解x（1）不是基可行解，无界解。111第五节

检验数的讨论3．可行解Ｘ(1)的各分量就可确定出一个换出变量选这时，新解比原解大。112第五节

检验数的讨论4．若有无穷最优解。1132.3．114第三章对偶理论115从生产角度考虑这个问题116现从另一角度考虑这个问题；假设不生产Ⅰ、Ⅱ，而将所有资源出租或外售，就须给各种资源定价。由y1,y2,y3表示外销单位资源利润。生产一件Ⅰ所耗资源的外销应不低于2元。同理：总利润：从企业出发：从消费者出发：企业只能在满足约束条件下，使其总利润尽可能小，这样，才能实现外销的愿望。称这个问题为原问题的对偶问题。每一个线性规划问题，都伴随另一个线性规划问题，二者互为对偶。117118119120121122123第三章对偶理论

§3-2对偶问题的基本性质定理1，若X是原问题的可行解，Y是对偶问题的可行解，则存在证：AX≤bYA≥C

YAX≤YbYAX≥CX

Yb≥CX推理1：若Y为对偶问题的任一可行解，则Yb为原问题目标函数值的上界；若X为原问题的任一可行解。则CX为其对偶问题目标函数值的下界。推理2：若原问题有可行解，但其CX无上界，则对偶问题无可行解；若对偶问题有可行解，但目标函数值无下界，则原问题，无可行解。124125定理2：若原问题和对偶问题分别有可行解X*和Y*且其目标函数值相等。即CX*=bY*。则X*和Y*分别为原问题和对偶问题的最优解。定理3：若B是原问题的最优基，则最优单纯形乘子Y*=CBB-1

是其对偶问题的最优解。126127第三章对偶理论12

128129