运筹学第一章线性规划及单纯形法

LinearProgramming（LP）

线性规划问题及其数学模型

线性规划问题的求解方法

线性规划的图解法

线性规划的单纯形法

线性规划模型的应用第一章线性规划及单纯形法

线性规划问题及其数学模型第一章线性规划及单纯形法LinearProgramming（LP）

线性规划问题的求解方法

线性规划的图解法

线性规划的单纯形法

线性规划模型的应用一、问题的提出

为了完成一项任务或达到一定的目的，怎样用最少的人力、物力去完成或者用最少的资源去完成较多的任务或达到一定的目的，这个过程就是规划。例1、有一正方形铁皮，应如何裁剪能使容积最大？xa

无约束的极值问题例2、如何安排生产才能使利润最大？资料如图

设备产品ABCD利润（元）

Ⅰ21402

Ⅱ22043

有效台时1281612目标max

x1≥0,x2≥0s.t.2x1+2x2≤12

带约束的极值问题x1x2z=2x1+3x2

约束条件x1+2x2≤84x1≤164x2≤12subjectto函数数学模型例3、合理配料问题数学模型x1x2

x3

x4

x5

x6z=4x1+3x2+6x3+5x4+2.7x5+2.2x6mins.t.x1+0x2+2x3+2x4+x5+2x6≥9

0x1+x2+3x3+x4+3x5+2x6≥19

x1,x2,…,x6≥0

每天服用这六种营养物各多少克，才能既获得每日最少所需又使花费最省？二、数学模型组成要素：

决策变量

约束条件

目标函数线性规划：连续的（数值取实数）关于变量的线性等式或不等式关于变量的线性函数（一次方）

问题中有未知的变量，需要我们去求解，此外有目标函数及约束条件，一般有非负条件存在，由此组成规划问题的数学模型。线性规划数学模型的一般形式s.t.s.t.向量形式s.t.s.t.向量形式矩阵形式s.t.s.t.线性规划问题的数学模型s.t.s.t.s.t.s.t.三、线性规划问题的标准形式s.t.s.t.s.t.s.t.标准形式的主要特征s.t.③决策变量xj取值非负④约束条件右端常数项bi为非负值①目标函数为求极大值（也可用求极小值）②所有约束条件都是等式（非负条件除外）

√非标准形式化为标准形式的方法⑴目标函数的转换⑵约束方程的转换：由不等式转换为等式⑶变量的变换称为松弛变量称为剩余变量x1+x24x1+x2－

x3=4⑷

约束条件右端常数项的变换：bi﹤0x1+x23x1+x2+x3=3例1、将下列线性规划问题化为标准形式+0x5+0x4maxz

=－2x1

+

x2

－

3x3

maxz

=－2x1

+

(x2

－

x2)

+3x3

+0x4+0x53x1

－

2(x2

－

x2)－

x3

=－4－3x1

+2(x2

－

x2)+

x3

=4解：设min

x1≥0,x2取值无约束,x3≤0s.t.x1+2x2+4x3≤6z=2x1

－x2

+3x3

3x1

－

2x2+x3=－4

2x1

－

x2－

3x3≥

5

x1,x2

,x2

,x3

,x4,x5≥0

x1+2x2+4x3+x4

=6s.t.

2x1

－

x2－

3x3－

x5

=5引入变量令x1

+

2(x2

－

x2)－

4x3

+

x4=6第二个约束方程两边乘(－1),从而得到标准形式2x1

－

(x2

－

x2)＋

3x3

－

x5

=5－3x1

+2x2

－

2x2

+

x3

=4

x1,x2

,x2

,x3

,x4,x5≥0s.t.x1

+2x2

－

2x2

－

4x3

+

x4=62x1

－

x2

＋

x2

＋

3x3

－

x5

=5maxz

=－2x1

+

x2

－

x2

+3x3

+0x4+0x5例2、将下列线性规划问题化为标准形式x1

＋

2(x2

－

x2)＋

x3

＋

x4

=5x1,x2

,x2

,x3

,x4,

x5,

x6

≥0x1

＋

(x2

－

x2)＋

x3

＋

x6

=2maxz=x1

+2(x2

－

x2)

+3x3

+0x4+0x5+

0x6解：max

x1≥0,x2取值无约束,x3≤0s.t.x1+2x2－

x3≤5z=x1+2x2

－

3x3

2x1+

3x2－

x3≥6

－x1

－

x2+

x3≥

－2引入变量令第三个约束方程两边乘(－1),从而得到标准形式2x1

＋

3(x2

－

x2)＋

x3

－

x5

=6s.t.x1

＋

2x2

－

2x2

＋

x3

＋

x4

=5x1,x2

,x2

,x3

,x4,x5,x6≥0x1

＋

x2

－

x2

＋

x3

＋

x6

=2maxz=x1

+2x2

－

2x2

+3x3

+0x4+0x5+

0x62x1

＋

3x2

－

3x2

＋

x3

－

x5

=6练习：将下列线性规划问题化为标准形式min

x1,x2≥0,x3取值无约束s.t.x1

－

x2+x3≤10z=－2x1+3x2

－

x3

3x1+

2x2－

x3≥8x1

－

3x2+

x3=－1－x1

＋

3x2

－

x3

＋

x3

=1maxz

=2x1

－3x2+

x3

－

x3

+0x4+0x53x1

＋

2x2

－

x3

＋

x3

－

x5

=8

x1,x2,x3

,x3

,x4,x5≥0s.t.x1

－

x2

＋

x3

－

x3

＋

x4

=10解：设引入变量令第三个约束方程两边乘(－1),从而得到标准形式即：系数矩阵的秩为m且小于n，则根据线性代数定理可知，②若有解则必有无穷多解，这是线性规划问题能寻求最优解的余地所在。

四、线性规划问题的解s.t.③②①

可行解：满足约束条件②、③的解

最优解：使目标函数①达到最大值的可行解方程组②中：通常m＜n，且m个方程线性无关。

可行域：所有可行解构成的集合思考题：

某部门有一批资金用于甲、乙、丙、丁、戊五个工程项目的投资，由于某种原因，决定用于项目甲的投资不大于其他各项投资之和；而用于项目乙和戊的投资之和不小于项目丙的投资。已知用于各个工程项目时所得的净收益(投入资金的百分比)如上表所示。试确定使该部门收益最大的投资分配方案。要求：建立线性规划模型，并化为标准形式。工程项目甲乙丙丁戊收益（%）108659分析：z=0.1x1+0.08x2+0.06x3+0.05x4+0.09x5maxs.t.x1+x2+x3+x4+x5=1

x1－

x2－

x3－

x4－

x5≤0

x1,x2,…,x5≥0

工程项目甲乙丙丁戊收益（%）108659设xj表示用于第j个项目的投资百分比。目标函数约束条件

用于甲的投资不大于其他各项投资之和；而用于乙和戊的投资之和不小于丙的投资。x2－

x3+x5≥0

总投资的要求对甲的要求对乙、戊的要求非负要求标准形式z=0.1x1+0.08x2+0.06x3+0.05x4+0.09x5+0x6+0x7

maxs.t.x1+x2+x3+x4+x5=1

x1－

x2－

x3－

x4－

x5+0x6

=0

x1,x2,…,x5,x6,

x7≥0

x2－

x3+x5+x7

=0

线性规划问题的求解方法第一章线性规划及单纯形法LinearProgramming（LP）

线性规划问题及其数学模型

线性规划的图解法

线性规划的单纯形法

线性规划模型的应用一、预备知识：解的概念

可行解：满足约束条件的解

最优解：使目标函数达到极值的可行解

可行域：所有可行解构成的集合s.t.一、预备知识：凸集与顶点x1x2x2x1x1x2x1x2x1x2x1x2凸集：集合C中任意两点连线上的所有点还在C内

任给x1,x2

C,x=

x1+(1－

)x2

C(0<

<1)顶点：凸集C中不在任意两不同点连线上的点

对x,任给x1,x2

C,不存在x=

x1+(1－

)x2(0<

<1)凸集非凸集二、图解法步骤：将约束条件在图上表示建立直角坐标系确立满足约束条件的解的范围(可行域)绘制出目标函数的图形在可行域中确定最优解定义：用图示的方法求解线性规划问题的最优解优点：直观性强，计算方便缺点：只适用于问题中是两(三)个变量的情况123456781234562x1+2x2=12x1+2x2=84x1=164x2=12唯一最优解此时z=14。(4,2)示例1：s.t.①②③④0x2

x1z=0x1=4,x2=2,

123456781234563x1+2x2=12x1+2x2=6x2=2无穷多最优解示例2：0x2

x1s.t.①②③x1－x2=－1x1+2x2=2无界解(无最优解)示例3：s.t.①②x1x2

0思考：若目标函数改为minz=x1+x2呢？

若改为minz=x1+

2x2呢？无可行解示例4：s.t.①②x1+x2=1x1x2

02x1+3x2=62x2=12练习：s.t.x1=83x1+4x2

=36(4,6)x1812x243690唯一最优解此时z=42。x1=4,x2=6,

（4）无可行解：无可行域，模型约束条件矛盾图解法的几点启示线性规划问题解的情况有：（1）唯一最优解：只有一点为最优解点（2）无穷多最优解：有许多点为最优解点（3）无界解：最优解取值无界，无最优解LP问题的可行域若存在则一定是凸集(有限个顶点)LP问题若有最优解，则定能在可行域某顶点达到LP问题的解题思路：顶点→相邻顶点→……三、单纯形法（SimplexMethod）美国数学家丹齐格(G.B.Dantzig)1947年创建简捷、规范，是举世公认的解决线性规划问题行之有效的方法。

理论根据：基本思想：在凸集的有限个顶点上搜索最优解该搜索策略可极大地减少访问顶点的数量。

由可行域的一个顶点出发，沿着凸集边缘逐个计算与判定所遇到的顶点，直至找到最优解所对应的顶点为止。

线性规划问题的可行域是n维向量空间中的多面凸集，其最优值如果存在则必在该凸集的某顶点处达到。s.t.(一)基解与基可行解系数矩阵A是m×n矩阵（设m<n），其秩R(A)=m。线性规划问题的基：矩阵A中的m×m阶满秩子矩阵B。(|B|≠0)基解：令非基变量为零，对m个基变量求解后合并所得的解。最多个基向量：B中的m个列向量Pr。基变量：与基向量对应的m个变量xr。剩下n-m个非基变量。(一)基解与基可行解基解：令非基变量为零，对m个基变量求解后合并所得的解。设

，

令非基变量基变量为，|B|≠0基变量的唯一解基解最多个(一)基解与基可行解基解：令非基变量为零，对m个基变量求解后合并所得的解。基可行解：满足变量非负约束条件xj≥0的基解。可行基：对应于基可行解的基。基可行解可行解非可行解基解基基解是否基可行解目标函数值例题：列出全部基、基解、基可行解和指出最优解s.t.s.t.标准化系数矩阵:例题：用图解法求最优解s.t.x1+x2=3x1+2x2=4(2,1)12341230x2

x1基解对应于各直线交点基可行解是可行域的顶点(二)单纯形法的基本定理定理1：若线性规划问题存在可行解，则问题的可行域是凸集。定理3：若线性规划问题有最优解，则一定存在一个基可行解是最优解。定理2：线性规划问题的基可行解对应其可行域的顶点。理论根据：

线性规划问题的可行域是n维向量空间中的多面凸集，其最优值如果存在则必在该凸集的某顶点处达到。在有限个基可行解中搜索最优解（迭代）(三)单纯形法的求解思路确定一个初始基可行解是否最优改进为新的基可行解最优解是否循环结束化标准形1、确定初始基可行解s.t.s.t.标准化约束方程组的系数矩阵：基变量值：初始基可行解：记2、最优性检验s.t.初始基可行解：任一可行解：由约束方程组得代入目标函数可得：则有：检验数基变量的其中2、最优性检验当前基可行解是最优解若所有，则对任意可行解X，都有线性规划问题存在无界解（无最优解）若存在某个，且所有令只需保证由所有显然此时因找可行解X，使z无限大。线性规划问题无可行解2、最优性检验当前基可行解是最优解：所有线性规划问题有唯一最优解′线性规划问题有无穷多最优解′′线性规划问题存在无界解（无最优解）若存在某个，且所有存在和当前基可行解非最优解，但LP问题有最优解其中所有；

或

有非基变量,且3、寻找改进的基可行解

相邻的基可行解：若两个基可行解之间仅变换一个基变量。

将一个基变量变成非基变量（换出），一个非基变量变成基变量（换入），进而找出一个目标函数值更大的“相邻”基可行解。入基变量的确定由和越大，值上升的可能性越大因此，一般取对应的变量作为换入基的变量。3、寻找改进的基可行解出基变量的确定令换入变量为得到基可行解，需保证且至少一个为0（换出）则只需取其余非基变量，存在此时换出。确定为换出变量，由称为主元素。可行解：证明是基可行解？§3-1引理3、寻找改进的基可行解约束方程组的系数矩阵：初始基

，

变量换入,换出，新可行解对应向量：是线性无关的，故是基可行解。s.t.单纯形法的求解思路确定一个初始基可行解是否最优改进为新的基可行解最优解是否循环结束化标准形？步骤简单总结经过何种运算可转到第③步，实现循环迭代？①将线性规划问题化成标准形式;②找出或构造一个m阶单位矩阵作初始可行基，得到初始基可行解;③计算各非基变量xj的检验数

j，若所有

j≤0，则问题已得到最优解，停止计算，否则转入下步;④若存在某个

s>0，且对应的所有系数ais≤0，则此问题是无界解，停止计算，否则转入下步;⑤根据max{

j|

j＞0}=

k原则，确定xk为入基变量，再按

=min{bi/aik|aik＞0}=bl/alk规则，确定xl为出基变量，得到改进的基可行解。将其化为单位矩阵，

则LP问题形式为s.t.4、迭代运算初始基

，

变量换入,换出，新可行基：s.t.4、迭代运算①主元素所在行：②

其余行：4、迭代运算新检验数

s.t.整理后可得

①将线性规划问题化成标准形式;②找出或构造一个m阶单位矩阵作初始可行基，得到初始基可行解;③计算各非基变量xj的检验数

j，若所有

j≤0，则问题已得到最优解，停止计算，否则转入下步;④若存在某个

s>0，且对应的所有系数ais≤0，则此问题是无界解，停止计算，否则转入下步;⑤根据max{

j|

j＞0}=

k原则，确定xk为入基变量，再按

=min{bi/aik|aik＞0}=bl/alk规则，确定xl为出基变量；⑥以alk为主元素进行迭代，利用初等行变换将xk所在列化为单位向量，即alk化为1，其它元素化为0，得到改进的可行基，转入第③步。计算步骤总结(四)单纯形表格法——单纯形表s.t.……max

x1,x2≥0s.t.

2x1+2x2≤12z=2x1+3x2

4x1

≤

165x2≤15例题：用单纯形法求解线性规划问题+0x4+0x3maxz=2x1

+3x2s.t.引入变量得到标准形式解：+0x55x2+x5

=154x1

+

x4=162x1

+2x2+

x3=12x1,x2,x3,x4,x5≥0+0x4+0x3maxz=2x1

+3x2s.t.引入变量得到标准形式解：+0x55x2+x5

=154x1

+

x4=162x1

+2x2+

x3=12x1,x2,x3,x4,x5≥0此时所有检验数得到最优解最优值为①将线性规划问题化成标准形式;②找出或构造一个单位矩阵作初始可行基，确定初始基可行解，建立初始单纯形表;③检验各非基变量xj的检验数

j，若所有

j≤0，则问题已得到最优解，停止计算，否则转入下步;④若存在某个

s>0，且对应的所有系数ais≤0，则此问题是无界解，停止计算，否则转入下步;⑤根据max{

j|

j＞0}=

k原则，确定xk为入基变量，再按

=min{bi/aik|aik＞0}=bl/alk规则，确定xl为出基变量；⑥用xk替换基变量中的xl，利用初等行变换将xk所在列化为单位向量，得到新的单纯形表，转入第③步。单纯形法计算步骤标准化系数矩阵(五)单纯形法的进一步讨论

用单纯形法解题时，需要有个单位矩阵作为初始可行基当约束条件都是“≤”时，加入松弛变量就形成了初始基

但实际存在“≥”或“＝”型的约束，没有现成的单位矩阵s.t.－2x1＋

x2－x3

－

x5

=1解：引入变量从而得到标准形式s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9maxz=－3x1

+

0x2

+

x3+0x4+0x5约束方程组的系数矩阵：maxz=－3x1

+

0x2

+

x3+0x4+0x5(五)单纯形法的进一步讨论采用添加人工变量的方法

因是在等式中人为加进的，为保证约束条件的意义，最优解中人工变量只能等于0

在等式约束中加入若干人工变量，人为构造一个单位矩阵

人工变量的添加不能影响最优解的取值：－2x1＋

x2－x3

－

x5

=1s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9约束方程组的系数矩阵：两种处理方法

大M法两阶段法＋

x6

=1

＋

x7

=9=4,x6,x7≥0如何处理？1、大M法maxz=－3x1

+

0x2

+

x3+0x4+0x5－2x1＋

x2－x3

－

x5

=1s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9＋

x6

=1

＋

x7

=9=4,x6,x7≥0－Mx6－Mx7

为保证最优解中人工变量取值为0，可令目标函数中人工变量的系数为足够大的一个负值，用“－M”代表。

由于系数是一个足够大的负值，因此，只要人工变量的取值不为零，目标函数就不可能实现最大化。

计算时，把M看做一个代数符号直接参加单纯形法求解。

若最终单纯形表中，人工变量仍是基变量且值不为零，则说明该问题求不到最优解，即无可行解。－2x1＋

x2－x3

－

x5

=1s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9＋

x6

=1

＋

x7

=9=4,x6,x7≥0maxz=－3x1

+

0x2

+

x3+0x4+0x5－Mx6－Mx7使人工变量尽快出基此时所有检验数得到最优解最优值为－2x1＋

x2－x3

－

x5

=1s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9＋

x6

=1

＋

x7

=9=4,x6,x7≥0maxz=－3x1

+0x2

+

x3+0x4+0x5

用大M法处理人工变量，用手工计算不会出现任何问题。

但用计算机求解时，由于在程序中只能用很大的数代替M，有可能受计算机的误差影响，导致结果发生错误，使大M法失效。2、两阶段法

第一阶段：构造判断是否存在可行解的模型

构造仅含人工变量(系数为1)且要求极小化的目标函数

用单纯形法求解，若minw=0，说明人工变量为0，问题存在基可行解，进入第二个阶段；若minw≠0，说明最优解中人工变量非零，无可行解，停止。minw=x6+

x7minw=x6+

x72、两阶段法－2x1＋

x2－x3

－

x5

=1s.t.x1

＋

x2＋

x3＋

x4

=4x1,x2,x3,x4,x5≥03x2

＋

x3=9＋

x6

=1

＋

x7

=9=4,x6,x7≥02、两阶段法

第二阶段：从上阶段的最终单纯形表出发，去掉人工变量，引入原来的目标函数，继续迭代，找出问题的最终解maxz=－3x1

+

0x2

+

x3+0x4+0x5人工变量法总结约束方程组

在等式约束中加人工变量，人为构造单位矩阵作初始可行基目标函数

为保证原约束条件的意义，最优解中人工变量只能是0大M法

令目标函数中人工变量的系数为足够大的一个负值“－M”两阶段法1、构造仅含人工变量且求极小化的目标函数，单纯形法求解；2、去掉上阶段最终单纯形表中的人工变量，引入原目标函数，继续迭代，找出问题的最终解。

若最终单纯形表中，人工变量仍是基变量且值不为零，则说明该问题求不到最优解，即无可行解。3、由单纯形表判别解的类别无可行解唯一最优解所有无穷多最优解无界解（无最优解）最终单纯形表的基变量中仍有非零人工变量存在某个，且所对应的系数最优解某非基变量至少一个且≤0≥0保证当前的基可行解是最优解

至少有一个等于0，如

至少有一个大于0，如

＞0

存在，保证当xp入基时有xl出基说明能得到另一个最优基可行解两个基可行解连线上的所有点都是最优解无穷多最优解示例1：s.t.标准化s.t.此时所有检验数得到最优解最优值为此时所有检验数得另一最优解最优值为无界解(无最优解)示例2：s.t.标准化s.t.且所对应系数取值无限制160x2

x14x1=16无可行解示例3：s.t.标准化s.t.此时所有检验数但人工变量仍留在基变量中且不为零，问题无可行解。单纯形法小结

根据实际问题给出数学模型，首先化为标准形式，构造出单位矩阵作为基，列出初始单纯形表.单纯形法计算框图唯一最优解添加松弛变量、人工变量列出初始单纯形表计算非基变量各列的检验数бj所有бj

0基变量中有非零的人工变量

否某非基变量检验数为零﹡

否无可行解无穷多最优解对任一бj≥0有aik≤0无界解令бk=max{бj}xk为入基变量对所有aik>0计算θi=bi/aik

令θl=min{θi}xl为出基变量

alk为主元素迭代运算1、用非基变量xk替换基变量xl2、对主元素行(第l行)

令bl/alk→bl；alj/alk→ajl3、对主元素列(第k列)

令1→alk;0→其它元素4、表中其它行令ri－rl/alk·aik→ri列出新的单纯形表否否是是

是是循环补充说明单纯形法在计算中可能出现以下两种情况：同时出现多个相同的最大

j值同时出现多个相同的最小θ值

理论上可能出现死循环，但实际很罕见，一般不需特殊处理，任选其中一个对应的变量入基或出基即可。

若遇到极端情况，可利用勃兰特(bland)规则：当存在多个

j>0时，选取下标值最小的变量入基；当出现多个相同最小θ时，选取下标值最小的变量出基。

线性规划模型的应用第一章线性规划及单纯形法LinearProgramming（LP）

线性规划问题及其数学模型

线性规划问题的求解方法

线性规划的图解法

线性规划的单纯形法线性规划问题的建模

建模是运筹学方法的核心和精髓，建立一个正确的数学模型，是问题解决的关键，答案利用线性规划程序可很快获得。正确的建模要求建模者：理解生产和管理问题的本质，明确目标和错综复杂的约束条件，通过调查和统计资料获取原始可靠的数据。建模过程的规律：①通过对实际问题的分析、理解，明确那些是决策变量，目标要求是什么，有哪些资源限制条件；②把变量、常数、约束条件、目标要求的相互关系联系起来列出相应的方程式；③注意变量、系数、常数的计量单位要统一。线性规划问题的应用

问题需满足的条件

①目标函数能用数值指标来反映，且为线性函数；

②存在多种方案及有关数据；

③要达到的目标是在一定约束条件下实现的，这些条件可用线性等式或不等式描述。相关问题生产计划问题（合理利用资源，使利润最高或完成计划）合理配料问题（保证饮食、药品等效果前提下使成本最低）投资方案选择问题（固定资金投入时使效益最高）人员分派问题（多项任务分配，使人数最少或效率最大）合理下料问题（在给定材料中截取零件，使用料最省）运输问题＊（多个产销地及运价限制，安排方案使运费最低）……生产计划问题：如何安排生产使利润最大？资料如图

设备产品ABCD利润（元）

Ⅰ21402

Ⅱ22043

有效台时1281612max

x1,x2≥0s.t.2x1+2x2≤12z=2x1+3x2

x1+2x2≤84x1≤164x2≤12设xj表示第j种产品在计划期内的产量合理配料问题：资料如图

设xj表示第j种营养物所需克数z=4x1+3x2+6x3+5x4+2.7x5+2.2x6mins.t.x1+0x2+2x3+2x4+x5+2x6≥9

0x1+x2+3x3+x4+3x5+2x6≥19

x1,x2,…,x6≥0

每天服用6种营养物各多少克，才能既获得每日所需又使花费最省？投资方案选择问