线性规划及单纯形法课件

运筹学

OPERATIONAL

RESEARCH--运筹学

OPERATIONALRESEARCH--1第一章线性规划及单纯形法--2第一章--2第四节单纯形法计算步骤第二节图解法第三节单纯形法原理第一节线性规划问题及其数学模型第五节单纯形法的进一步讨论第六节数据包络分析第七节其他应用例子--第四节单纯形法计算步骤第二节图解法第三节单3第一节线性规划问题及其数学模型一、问题的提出二、线性规划问题的与模型三、线性规划的数学模型四、线性规划模型的应用五、线性规划问题的标准形式--第一节线性规划问题及其数学模型一、问题的提出--4Ⅰ

Ⅱ每天可用能力设备A0515

设备B6224

调试工序115

利润21一、问题提出例1生产计划问题两种家电各生产多少,可获最大利润?--一、问题提出例1生产计划问题两种家电各生产多少,可获最5

5x2

156x1+2x2

24

x1+x2

5

x1，x2

0maxZ=2x1+x2解:设两种家电产量分别为变量x1

，x2--maxZ=2x1+x2解:设两种家电产量分别为变量x16

5x2

153、约束条件

6x1+2x2

24

x1+x2

5

x1，x2

02、目标函数maxZ=2x1+x2LP问题的三要素1、决策变量x1

，x2--2、目标函数maxZ=2x1+x2LP问题的三要素-7例2--例2--8例2解：设表示捷运公司在第i(i=1,2,3,4)月初签订的租期为j(j=1,2,3,4)个月的仓库面积的合同（单位为100m2)。--例2解：设表示捷运公司在第i(i=1,2,3,49ⅠⅡⅢⅣⅤ∑≥15∑≥10∑≥20∑≥12--ⅠⅡⅢⅣⅤ∑≥15∑≥10∑≥20∑≥12--10经过上面的讨论，得到下面的LP模型：目标函数约束条件--经过上面的讨论，得到下面的LP模型：目标函数约束条件--11二、线性规划模型特点决策变量：向量(x1…

xn)T决策人要考虑和控制的因素非负约束条件：线性等式或不等式目标函数：Z=ƒ(x1

…

xn)线性式，求Z极大或极小--二、线性规划模型特点决策变量：向量(x1…xn)T12（一）一般式Max(min)Z=C1X1+C2X2+…+CnXna11X1+a12X2+…+a1nXn(=,)b1a21X1+a22X2+…+a2nXn

(=,)b2………am1X1+am2X2+…+amnXn

(=,)bmXj0(j=1,…,n)--（一）一般式Max(min)Z=C1X1+C2X2+…+C13目标函数价值系数技术系数右端项常数决策变量--目标函数价值系数技术系数右端项常数决策变量--14（二）隐含的假设比例性：决策变量变化引起目标的改变量与决策变量改变量成正比可加性：每个决策变量对目标和约束的影响独立于其它变量连续性：每个决策变量取连续值确定性：线性规划中的参数aij

,bi,ci为确定值--（二）隐含的假设比例性：决策变量变化引起目标的改变量与决策变15线性规划的标准化一般形式目标函数：Max（Min）z=c1x1+c2x2+…+cnxn

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

≤（=,≥）b1

a21x1+a22x2+…+a2nxn

≤（=,≥）b2…………

am1x1+am2x2+…+amnxn

≤（=,≥）bm

x1，x2，…，xn≥0标准形式目标函数：Maxz=c1x1+c2x2+…+cnxn

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

=b1

a21x1+a22x2+…+a2nxn

=b2…………

am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn≥0，bi≥0三、线性规划问题的标准形式--线性规划的标准化三、线性规划问题的标准形式--16

可以看出，线性规划的标准形式有如下四个特点：目标最大化；约束为等式；决策变量均非负；右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:三、线性规划问题的标准形式--可以看出，线性规划的标准形式有如下四个特三、线性规划171.极小化目标函数的问题：设目标函数为

Minf=c1x1

+c2x2

+…+cnxn

(可以)令z

＝-f

，则该极小化问题与下面的极大化问题有相同的最优解，即Maxz=-c1x1

-c2x2-…-cnxn

但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即

Minf

＝-Maxz三、线性规划问题的标准形式--1.极小化目标函数的问题：三、线性规划问题的标准形式--182、约束条件不是等式的问题：设约束条件为

ai1x1+ai2x2+…+ainxn

≤bi

可以引进一个新的变量s

，使它等于约束右边与左边之差

s=bi–(ai1x1

+ai2x2

+…+ainxn

)显然，s

也具有非负约束，即s≥0，这时新的约束条件成为

ai1x1+ai2x2+…+ainxn+s=bi三、线性规划问题的标准形式--2、约束条件不是等式的问题：三、线性规划问题的标准形式--19当约束条件为

ai1x1+ai2x2+…+ainxn

≥bi

时，类似地令

s=(ai1x1+ai2x2+…+ainxn)-bi

显然，s

也具有非负约束，即s≥0，这时新的约束条件成为

ai1x1+ai2x2+…+ainxn-s=bi三、线性规划问题的标准形式--当约束条件为三、线性规划问题的标准形式--20为了使约束由不等式成为等式而引进的变量s,当不等式为“小于等于”时称为“松弛变量”；当不等式为“大于等于”时称为“剩余变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。

3.右端项有负值的问题：

在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如bi<0，则把该等式约束两端同时乘以-1，得到：-ai1x1-ai2x2-…-ainxn

=-bi。三、线性规划问题的标准形式--为了使约束由不等式成为等式而引进的变量s,当3.右端21例：将以下线性规划问题转化为标准形式

Minf=2x1-3x2+4x3s.t.3x1

+4x2-5x3≤62x1+x3≥8

x1+x2+x3=-9

x1,x2,x3

≥0

解：首先,将目标函数转换成极大化：令z=-f=-2x1+3x2-4x3

其次考虑约束，有2个不等式约束，引进变量x4，x5

≥0。第三个约束条件的右端值为负，在等式两边同时乘-1。三、线性规划问题的标准形式--例：将以下线性规划问题转化为标准形式

三、线性规划问题的标准22通过以上变换，可以得到以下标准形式的线性规划问题：

Maxz=-2x1

+3x2-4x3s.t.3x1+4x2-5x3+x4=62x1+x3-x5=8-x1-x2-x3=9

x1,x2,x3,x4,x5

≥0***变量无符号限制的问题***：

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

xj=xj’-xj”

其中

xj’≥0，xj”≥0

即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj’和xj”的大小。三、线性规划问题的标准形式--通过以上变换，可以得到以下标准形式的线性规划问题：三、线性23课堂练习

某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）ABCD价格M0.50.20.30300N0.10.30.40.2200每头日需10587养分饲料--课堂练习某蓄场每日要为每头牲畜购买饲料，以使其获取所24课堂练习

某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）ABCD价格M0.50.20.30300N0.10.30.40.2200每头日需10587养分饲料答案：设购买M饲料x1，N饲料x20.5x1+0.1x2≥100.2x1+0.3x2≥50.3x1+0.4x2≥80.2x2≥7x1,x2≥0s.t.MinZ=300x1+200x2--课堂练习某蓄场每日要为每头牲畜购买饲料，以使其获取所25第二节图解法

对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。--第二节图解法对于只有两个决策变量的线性26第二节图解法一、图解法的目的和步骤--第二节图解法一、图解法的目的和步骤--27

5x2

156x1+2x2

24

x1+x2

5

x1，x2

0maxZ=2x1+x2例1模型的图解法第二节图解法--maxZ=2x1+x2例1模型的图解法第二节图解28第二节图解法例2.目标函数：

Maxz=50x1+100x2约束条件：

s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)--第二节图解法例2.目标函数：--29第二节图解法x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图2--第二节图解法x1x2x2=0x1=0x2=250x1+30第二节图解法目标函数z=50x1+100x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。x1x2z=20000=50x1+100x2图2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE--第二节图解法目标函数z=50x31第二节图解法例2.目标函数：

Maxz=50x1+100x2约束条件：

s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最优解：

x1=50，x2=250

最优目标值z=27500--第二节图解法例2.目标函数：--32第二节图解法最优解：x1=0，x2=1

最优目标值z=3课堂练习图解法求解线性规划012341234x1x2O-1-2(1)(2)(3)--第二节图解法最优解：x1=0，x2=33第二节图解法（1）唯一解（2）多重最优解（3）无可行解注：出现（3）、（4）情况时，建模有问题（4）无有限最优解二、图解法的求解结果分类--第二节图解法（1）唯一解（2）多重最优解（3）无可行解34第二节图解法三、图解法的几点启示从图解法中我们了解到以下事实：①若LP问题的可行域存在，则可行域一定是凸集。②若LP问题的最优解存在，则最优解或最优解之一（如果有无穷多最优解的话）一定是可行域凸集的某个极点（顶点）。思路：①最优解先在可行域中找。（可行域为空集，则无可行解，故无最优解。）②最优解在可行域的极点中找。③极点是有限个，若两个极点都是最优解，则两个极点所连线段上的所有点均是最优解）定义：LP问题的可行域的极点（顶点）称为基本可行解。--第二节图解法三、图解法的几点启示从图解法中我们了解到以35第三节单纯形法凸集凸集：在点集中任取两点，则其连线仍在其中。即没有凹入的部分；没有空洞。⑴⑵⑶⑷⑸⑹在凸集⑵中，点A，B，C，D称为极点（或顶点）。ABCD--第三节单纯形法凸集凸集：在点集中任取两点，则其连线仍在36第四节单纯形法--37第四节单纯形法--3738第四节单纯形法单纯形法的基本思路：根据线性规划问题的标准，从可行域中某个基可行解（一个顶点）开始，转换到另一个基可行解（顶点），并且使目标函数达到最大值时，线性规划问题就得到了最优解。(1)确定初始基可行解(2)最优性检验和解的判别(3)由一个基可行解→另一个基可行解。--38第四节单纯形法单纯形法的基本思路：根据线性规划问题3839第四节单纯形法理论基础--39第四节单纯形法理论基础--3940第四节单纯形法单纯形法的步骤及解法--40第四节单纯形法单纯形法的步骤及解法--40(1)确定初始基可行解(2)最优性检验和解的判别(3)由一个基可行解→另一个基可行解。一、单纯形法的基本思路第四节单纯形法--41(1)确定初始基可行解(2)最优性检验和解的判别(3)x1+a1m+1xm+1+……+a1nxn=b1x2+a2m+1xm+1+……+a2nxn=b2xm+amm+1xm+1+……+amnxn=bn10…0a1m+1…a1n01…0a2m+1…a2n………00…1amm+1…amnA=第四节单纯形法标准化模型，确定初始基可行解--42x143单纯形表X1X2…XmXm+1…

Xm+k…XnCBXBbC1C2…

CmCm+1…

Cm+k…CnC1X1b110…0a1m+1…a1m+k…a1nC2X2b201…0a2m+1…a2m+k…

a2nCrXrbr00…0arm+1…arm+k…

arnCmXmbm00…1amm+1…amm+k…

ann……………………………………z00

…0σm+1…σm+k…

σn--43单纯形表4344例1第四节单纯形法

5x2

156x1+2x2

24

x1+x2

5

x1，x2

0maxZ=2x1+x2--44例1第四节单纯形法maxZ=2x1+x2--4445第一步：标准化第四节单纯形法

5x2+x3

=

156x1+2x2

+x4

=

24

x1+x2

+x5

=5

x1，x2

，x3，x4，x5

0maxZ=2x1+x2+0x3

+0x4+0x5--45第一步：标准化第四节单纯形法maxZ=2x14546第二步：根据增广矩阵找一个初始基可行解第四节单纯形法--46第二步：根据增广矩阵找一个初始基可行解第四节单纯形法4647第三步：列出初始单纯形表第四节单纯形法--47第三步：列出初始单纯形表第四节单纯形法--4748第四步：判断是否最优，否则找出下一个基可行解，并写出新单纯形表第四节单纯形法--48第四步：判断是否最优，否则找出下一个基可行解，并写出新单4849第四步：判断是否最优，否则找出下一个基可行解，并写出新单纯形表第四节单纯形法--49第四步：判断是否最优，否则找出下一个基可行解，并写出新单4950第五步：再写出新单纯形表第四节单纯形法--50第五步：再写出新单纯形表第四节单纯形法--5051习题第四节单纯形法--51习题第四节单纯形法--5152习题第四节单纯形法--52习题第四节单纯形法--5253习题第四节单纯形法--53习题第四节单纯形法--5354习题第四节单纯形法--54习题第四节单纯形法--5455习题第四节单纯形法--55习题第四节单纯形法--5556习题第四节单纯形法--56习题第四节单纯形法--5657一、人工变量法（大M法）第五节单纯形法的进一步讨论没有初始基可行解时怎么办？借助人工变量求初始的基本可行解

--57一、人工变量法（大M法）第五节单纯形法的进一步讨论5758一、人工变量法（大M法）第五节单纯形法的进一步讨论--58一、人工变量法（大M法）第五节单纯形法的进一步讨论5859一、人工变量法（大M法）第五节单纯形法的进一步讨论--59一、人工变量法（大M法）第五节单纯形法的进一步讨论5960一、人工变量法（大M法）第五节单纯形法的进一步讨论--60一、人工变量法（大M法）第五节单纯形法的进一步讨论6061一、人工变量法（大M法）第五节单纯形法的进一步讨论--61一、人工变量法（大M法）第五节单纯形法的进一步讨论6162一、人工变量法（大M法）第五节单纯形法的进一步讨论--62一、人工变量法（大M法）第五节单纯形法的进一步讨论6263一、人工变量法（大M法）第五节单纯形法的进一步讨论--63一、人工变量法（大M法）第五节单纯形法的进一步讨论6364二、两阶段法（大M法）第五节单纯形法的进一步讨论--64二、两阶段法（大M法）第五节单纯形法的进一步讨论-6465二、两阶段法（大M法）第五节单纯形法的进一步讨论--65二、两阶段法（大M法）第五节单纯形法的进一步讨论-6566二、两阶段法（大M法）第五节单纯形法的进一步讨论--66二、两阶段法（大M法）第五节单纯形法的进一步讨论-6667二、两阶段法（大M法）第五节单纯形法的进一步讨论--67二、两阶段法（大M法）第五节单纯形法的进一步讨论-6768二、两阶段法（大M法）第五节单纯形法的进一步讨论--68二、两阶段法（大M法）第五节单纯形法的进一步讨论-6869二、两阶段法（大M法）第五节单纯形法的进一步讨论--69二、两阶段法（大M法）第五节单纯形法的进一步讨论-6970二、两阶段法（大M法）第五节单纯形法的进一步讨论--70二、两阶段法（大M法）第五节单纯形法的进一步讨论-7071二、两阶段法（大M法）第五节单纯形法的进一步讨论--71二、两阶段法（大M法）第五节单纯形法的进一步讨论-7172三、关于解的判断第五节单纯形法的进一步讨论--72三、关于解的判断第五节单纯形法的进一步讨论--7273三、关于解的判断第五节单纯形法的进一步讨论--73三、关于解的判断第五节单纯形法的进一步讨论--7374三、关于解的判断第五节单纯形法的进一步讨论--74三、关于解的判断第五节单纯形法的进一步讨论--7475三、关于解的判断第五节单纯形法的进一步讨论--75三、关于解的判断第五节单纯形法的进一步讨论--7576三、关于解的判断第五节单纯形法的进一步讨论--76三、关于解的判断第五节单纯形法的进一步讨论--7677三、关于解的判断第五节单纯形法的进一步讨论--77三、关于解的判断第五节单纯形法的进一步讨论--7778三、关于解的判断第五节单纯形法的进一步讨论--78三、关于解的判断第五节单纯形法的进一步讨论--7879应用--79应用--7980一、人工变量法（大M法）第五节单纯形法的进一步讨论--80一、人工变量法（大M法）第五节单纯形法的进一步讨论8081--81--8182--82--8283本章内容结束--83本章内容结束--83运筹学

OPERATIONAL

RESEARCH--运筹学

OPERATIONALRESEARCH--84第一章线性规划及单纯形法--85第一章--2第四节单纯形法计算步骤第二节图解法第三节单纯形法原理第一节线性规划问题及其数学模型第五节单纯形法的进一步讨论第六节数据包络分析第七节其他应用例子--第四节单纯形法计算步骤第二节图解法第三节单86第一节线性规划问题及其数学模型一、问题的提出二、线性规划问题的与模型三、线性规划的数学模型四、线性规划模型的应用五、线性规划问题的标准形式--第一节线性规划问题及其数学模型一、问题的提出--87Ⅰ

Ⅱ每天可用能力设备A0515

设备B6224

调试工序115

利润21一、问题提出例1生产计划问题两种家电各生产多少,可获最大利润?--一、问题提出例1生产计划问题两种家电各生产多少,可获最88

5x2

156x1+2x2

24

x1+x2

5

x1，x2

0maxZ=2x1+x2解:设两种家电产量分别为变量x1

，x2--maxZ=2x1+x2解:设两种家电产量分别为变量x189

5x2

153、约束条件

6x1+2x2

24

x1+x2

5

x1，x2

02、目标函数maxZ=2x1+x2LP问题的三要素1、决策变量x1

，x2--2、目标函数maxZ=2x1+x2LP问题的三要素-90例2--例2--91例2解：设表示捷运公司在第i(i=1,2,3,4)月初签订的租期为j(j=1,2,3,4)个月的仓库面积的合同（单位为100m2)。--例2解：设表示捷运公司在第i(i=1,2,3,492ⅠⅡⅢⅣⅤ∑≥15∑≥10∑≥20∑≥12--ⅠⅡⅢⅣⅤ∑≥15∑≥10∑≥20∑≥12--93经过上面的讨论，得到下面的LP模型：目标函数约束条件--经过上面的讨论，得到下面的LP模型：目标函数约束条件--94二、线性规划模型特点决策变量：向量(x1…

xn)T决策人要考虑和控制的因素非负约束条件：线性等式或不等式目标函数：Z=ƒ(x1

…

xn)线性式，求Z极大或极小--二、线性规划模型特点决策变量：向量(x1…xn)T95（一）一般式Max(min)Z=C1X1+C2X2+…+CnXna11X1+a12X2+…+a1nXn(=,)b1a21X1+a22X2+…+a2nXn

(=,)b2………am1X1+am2X2+…+amnXn

(=,)bmXj0(j=1,…,n)--（一）一般式Max(min)Z=C1X1+C2X2+…+C96目标函数价值系数技术系数右端项常数决策变量--目标函数价值系数技术系数右端项常数决策变量--97（二）隐含的假设比例性：决策变量变化引起目标的改变量与决策变量改变量成正比可加性：每个决策变量对目标和约束的影响独立于其它变量连续性：每个决策变量取连续值确定性：线性规划中的参数aij

,bi,ci为确定值--（二）隐含的假设比例性：决策变量变化引起目标的改变量与决策变98线性规划的标准化一般形式目标函数：Max（Min）z=c1x1+c2x2+…+cnxn

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

≤（=,≥）b1

a21x1+a22x2+…+a2nxn

≤（=,≥）b2…………

am1x1+am2x2+…+amnxn

≤（=,≥）bm

x1，x2，…，xn≥0标准形式目标函数：Maxz=c1x1+c2x2+…+cnxn

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

=b1

a21x1+a22x2+…+a2nxn

=b2…………

am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn≥0，bi≥0三、线性规划问题的标准形式--线性规划的标准化三、线性规划问题的标准形式--99

可以看出，线性规划的标准形式有如下四个特点：目标最大化；约束为等式；决策变量均非负；右端项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:三、线性规划问题的标准形式--可以看出，线性规划的标准形式有如下四个特三、线性规划1001.极小化目标函数的问题：设目标函数为

Minf=c1x1

+c2x2

+…+cnxn

(可以)令z

＝-f

，则该极小化问题与下面的极大化问题有相同的最优解，即Maxz=-c1x1

-c2x2-…-cnxn

但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即

Minf

＝-Maxz三、线性规划问题的标准形式--1.极小化目标函数的问题：三、线性规划问题的标准形式--1012、约束条件不是等式的问题：设约束条件为

ai1x1+ai2x2+…+ainxn

≤bi

可以引进一个新的变量s

，使它等于约束右边与左边之差

s=bi–(ai1x1

+ai2x2

+…+ainxn

)显然，s

也具有非负约束，即s≥0，这时新的约束条件成为

ai1x1+ai2x2+…+ainxn+s=bi三、线性规划问题的标准形式--2、约束条件不是等式的问题：三、线性规划问题的标准形式--102当约束条件为

ai1x1+ai2x2+…+ainxn

≥bi

时，类似地令

s=(ai1x1+ai2x2+…+ainxn)-bi

显然，s

也具有非负约束，即s≥0，这时新的约束条件成为

ai1x1+ai2x2+…+ainxn-s=bi三、线性规划问题的标准形式--当约束条件为三、线性规划问题的标准形式--103为了使约束由不等式成为等式而引进的变量s,当不等式为“小于等于”时称为“松弛变量”；当不等式为“大于等于”时称为“剩余变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。

3.右端项有负值的问题：

在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如bi<0，则把该等式约束两端同时乘以-1，得到：-ai1x1-ai2x2-…-ainxn

=-bi。三、线性规划问题的标准形式--为了使约束由不等式成为等式而引进的变量s,当3.右端104例：将以下线性规划问题转化为标准形式

Minf=2x1-3x2+4x3s.t.3x1

+4x2-5x3≤62x1+x3≥8

x1+x2+x3=-9

x1,x2,x3

≥0

解：首先,将目标函数转换成极大化：令z=-f=-2x1+3x2-4x3

其次考虑约束，有2个不等式约束，引进变量x4，x5

≥0。第三个约束条件的右端值为负，在等式两边同时乘-1。三、线性规划问题的标准形式--例：将以下线性规划问题转化为标准形式

三、线性规划问题的标准105通过以上变换，可以得到以下标准形式的线性规划问题：

Maxz=-2x1

+3x2-4x3s.t.3x1+4x2-5x3+x4=62x1+x3-x5=8-x1-x2-x3=9

x1,x2,x3,x4,x5

≥0***变量无符号限制的问题***：

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

xj=xj’-xj”

其中

xj’≥0，xj”≥0

即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj’和xj”的大小。三、线性规划问题的标准形式--通过以上变换，可以得到以下标准形式的线性规划问题：三、线性106课堂练习

某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）ABCD价格M0.50.20.30300N0.10.30.40.2200每头日需10587养分饲料--课堂练习某蓄场每日要为每头牲畜购买饲料，以使其获取所107课堂练习

某蓄场每日要为每头牲畜购买饲料，以使其获取所需的A、B、C、D四种养分。有关数据如下表，现饲料可从市场上出售的M、N两种饲料中选择，试决定总花费最小的购买方案。（列出模型）ABCD价格M0.50.20.30300N0.10.30.40.2200每头日需10587养分饲料答案：设购买M饲料x1，N饲料x20.5x1+0.1x2≥100.2x1+0.3x2≥50.3x1+0.4x2≥80.2x2≥7x1,x2≥0s.t.MinZ=300x1+200x2--课堂练习某蓄场每日要为每头牲畜购买饲料，以使其获取所108第二节图解法

对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。--第二节图解法对于只有两个决策变量的线性109第二节图解法一、图解法的目的和步骤--第二节图解法一、图解法的目的和步骤--110

5x2

156x1+2x2

24

x1+x2

5

x1，x2

0maxZ=2x1+x2例1模型的图解法第二节图解法--maxZ=2x1+x2例1模型的图解法第二节图解111第二节图解法例2.目标函数：

Maxz=50x1+100x2约束条件：

s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)--第二节图解法例2.目标函数：--112第二节图解法x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图2--第二节图解法x1x2x2=0x1=0x2=250x1+113第二节图解法目标函数z=50x1+100x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。x1x2z=20000=50x1+100x2图2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE--第二节图解法目标函数z=50x114第二节图解法例2.目标函数：

Maxz=50x1+100x2约束条件：

s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最优解：

x1=50，x2=250

最优目标值z=27500--第二节图解法例2.目标函数：--115第二节图解法最优解：x1=0，x2=1

最优目标值z=3课堂练习图解法求解线性规划012341234x1x2O-1-2(1)(2)(3)--第二节图解法最优解：x1=0，x2=116第二节图解法（1）唯一解（2）多重最优解（3）无可行解注：出现（3）、（4）情况时，建模有问题（4）无有限最优解二、图解法的求解结果分类--第二节图解法（1）唯一解（2）多重最优解（3）无可行解117第二节图解法三、图解法的几点启示从图解法中我们了解到以下事实：①若LP问题的可行域存在，则可行域一定是凸集。②若LP问题的最优解存在，则最优解或最优解之一（如果有无穷多最优解的话）一定是可行域凸集的某个极点（顶点）。思路：①最优解先在可行域中找。（可行域为空集，则无可行解，故无最优解。）②最优解在可行域的极点中找。③极点是有限个，若两个极点都是最优解，则两个极点所连线段上的所有点均是最优解）定义：LP问题的可行域的极点（顶点）称为基本可行解。--第二节图解法三、图解法的几点启示从图解法中我们了解到以118第三节单纯形法凸集凸集：在点集中任取两点，则其连线仍在其中。即没有凹入的部分；没有空洞。⑴⑵⑶⑷⑸⑹在凸集⑵中，点A，B，C，D称为极点（或顶点）。ABCD--第三节单纯形法凸集凸集：在点集中任取两点，则其连线仍在119第四节单纯形法--120第四节单纯形法--37121第四节单纯形法单纯形法的基本思路：根据线性规划问题的标准，从可行域中某个基可行解（一个顶点）开始，转换到另一个基可行解（顶点），并且使目标函数达到最大值时，线性规划问题就得到了最优解。(1)确定初始基可行解(2)最优性检验和解的判别(3)由一个基可行解→另一个基可行解。--38第四节单纯形法单纯形法的基本思路：根据线性规划问题121122第四节单纯形法理论基础--39第四节单纯形法理论基础--122123第四节单纯形法单纯形法的步骤及解法--40第四节单纯形法单纯形法的步骤及解法--123(1)确定初始基可行解(2)最优性检验和解的判别(3)由一个基可行解→另一个基可行解。一、单纯形法的基本思路第四节单纯形法--124(1)确定初始基可行解(2)最优性检验和解的判别(3)x1+a1m+1xm+1+……+a1nxn=b1x2+a2m+1xm+1+……+a2nxn=b2xm+amm+1xm+1+……+amnxn=bn10…0a1m+1…a1n01…0a2m+1…a2n………00…1amm+1…amnA=第四节单纯形法标准化模型，确定初始基可行解--125x1126单纯形表X1X2…XmXm+1…

Xm+k…XnCBXBbC1C2…

CmCm+1…

Cm+k…CnC1X1b110…0a1m+1…a1m+k…a1nC2X2b201…0a2m+1…a2m+k…

a2nCrXrbr00…0arm+1…arm+k…

arnCmXmbm00…1amm+1…amm+k…

ann……………………………………z00

…0σm+1…σm+k…

σn--43单纯形表126127例1第四节单纯形法

5x2

156x1+2x2

24

x1+x2

5

x1，x2

0maxZ=2x1+x2--44例1第四节单纯形法maxZ=2x1+x2--127128第一步：标准化第四节单纯形法

5x2+x3

=

156x1+2x2

+x4

=

24

x1+x2