线性规划图解法几何意

关于线性规划图解法几何意1.3．线性规划问题的标准形式(其中bi≥0(i=1,2,...,m)称下列形式为线性规划问题的标准形式:目标函数求极大,约束条件为等式,决策变量及右边常数项为非负第2页,共59页，2024年2月25日，星期天线性规划问题的几种表示形式第3页,共59页，2024年2月25日，星期天用向量表示为：第4页,共59页，2024年2月25日，星期天则标准形式的矩阵表示：若令A－－称为系数矩阵b－－称为资源向量C－－称为价值向量X－－称为决策变量向量用矩阵表示为：第5页,共59页，2024年2月25日，星期天非标准形式化为标准形式的方法1.当目标函数为求极小值,即

minz=c1x1+c2x2+...+cnxn因为求minz等价于max(-z)

故可令则目标函数化为:2.当右端项bi<0时只需将等式或不等式两端同乘(-1),则右端项必大于03.当约束条件为ai1x1+ai2x2+...+ainxn≤bi引入一个变量xn+i≥0

可使成为等式即ai1x1+ai2x2+...+ainxn＋xn+i＝bi变量xn+i称为松弛变量第6页,共59页，2024年2月25日，星期天4.

当约束条件为ai1x1+ai2x2+...+ainxn≥bi时则引入一个变量xn+i≥0可使不等式成为等式,即

ai1x1+ai2x2+...+ainxn－xn+i＝bi变量xn+i称为剩余变量5.当变量xi为无约束的变量时则我们引入两个变量令:将其代入线性规划模型中6.当变量xi≤0时则令再代入线性规划模型中第7页,共59页，2024年2月25日，星期天

例3

将例1的数学模型化为标准形

该线性规划问题加入三个松驰变量x3,x4,x5≥0后：第8页,共59页，2024年2月25日，星期天例4

将下述线性规划问题化为标准形

解：分以下步骤进行处理(1)令z′=-z，把求minz改为求maxz′;(2)在第一个约束不等式≤号的左端加入松弛变量x4；(3)在第二个约束不等式≥号的左端减去剩余变量x5；(4)用x’3-x”3替换x3，其中x’3，x”3≥0,即可得到该问题的标准形.第9页,共59页，2024年2月25日，星期天得原问题的标准形为：

第10页,共59页，2024年2月25日，星期天1.4线性规划问题的解的概念1.可行解2.基3.基可行解4.可行基第11页,共59页，2024年2月25日，星期天一.线性规划问题解的概念线性规划问题1.可行解:满足线性规划问题的约束条件的解X=(x1，x2，...，xn)

T称为线性规划问题的可行解。2.可行域:

全部可行解构成的集合称为可行域。3.最优解:

使目标函数达到最优的可行解称为最优解。4.基:

设系数矩阵Am×n(n>m)其秩为m,B是矩阵A中的一个m×m阶的满秩子矩阵,称B是线性规划问题的一个基。第12页,共59页，2024年2月25日，星期天一.线性规划问题解的概念（2）=(P1,P2,...,Pm)

B中的每一列向量Pj(j=1,2,...m)称为基向量

基向量：

与基向量Pj的对应的变量xj

称为基变量

基变量：

非基变量：

线性规划中的其余变量称为非基向量

5.基解

设X是（LP）的约束方程AX=b的一个解，B是一个基，若X中对应基B的非基变量取值全为零，则称X为(LP)关于基B的基解，记作X(B)

不妨设基为

基解的个数不会超过个第13页,共59页，2024年2月25日，星期天一.线性规划问题解的概念（3）可证明:一个基唯一地确定一个基解.

6.基可行解：若基解X(B)满足非负条件X(B)≥0，则称基解X(B)为基可行解

7.基最优解：若基可行解X(B)是(LP)的最优解,则称X(B)为(LP)的基最优解.

最优基：基最优解对应的可行基B称为最优基.

可行基：基可行解对应的基B称为可行基.

注:基解没有X≥0的限制,故基解不一定是可行解.

X(B)=第14页,共59页，2024年2月25日，星期天一.线性规划问题解的概念（4）8.退化解：若基本可行解X的所有基变量的值均大于0，则称X是非退化的，否则称X为退化的。若(LP)的所有基本可行解都是非退化的,则称线性规划问题是非退化的.

第15页,共59页，2024年2月25日，星期天二.例题考虑线性规划问题：

约束方程的系数矩阵A很显然A中的后3列是线性无关的，它们构成一个基基B1对应的变量x3,x4,x5是基变量,x1,x2是非基变量第16页,共59页，2024年2月25日，星期天二.例题（2）若令：

得该解是对应B1的基解，它是基可行解，B1是可行基；如取是（LP）的一个基，若令：

基B2对应的变量x1,x2,x3是基变量，,x4,x5是非基变量得该解是对应B2的基解，它不是基可行解，B2不是可行基；第17页,共59页，2024年2月25日，星期天三.线性规划问题解的关系图AX=b的解

基解若非基变量为0

基可行解

基最优解B是A的m阶子矩阵基B若|B|

0可行基B当B-1b

0最优基B若基变量取非负若对应目标函数值最优第18页,共59页，2024年2月25日，星期天非可行解三.线性规划问题解的关系图（2）可行解基可行解基解基可行基最优基第19页,共59页，2024年2月25日，星期天第2节线性规划问题的几何意义2.1基本概念2.2几个定理第20页,共59页，2024年2月25日，星期天一.凸集与顶点凸集:

如果集合K中任意两个点X(1),X(2),其连线上的所有点也都是集合K中的点,则称集合K为凸集.或K={X|X=αX(1)+(1-α)X(2),X(1)

K,X(2)

K,0≤α≤1}

定理:D＝｛x∈Rn|Ax=b,x≥0}是凸集顶点:凸集K中满足下列条件的点X称为顶点:如果K中不存在任何两个不同的点X1,X2,使X成为这两个点连线上的一个点.定理:

有限个凸集的交集还是凸集凸组合:设是n维欧氏空间中的k个点则称X是的凸组合第21页,共59页，2024年2月25日，星期天凸集的概念：凸集凸集不是凸集顶点不是凸集第22页,共59页，2024年2月25日，星期天二.几个基本定理定理1若线性规划问题存在可行解,则问题的可行域是凸集.定理2若线性规划问题有非零可行解，则其必有基可行解。定理4若线性规划问题有最优解，一定存在一个基可行解是最优解。定理3线性规划问题的基可行解X对应线性规划问题可行域(凸集)的顶点.引理1线性规划的可行解X＝(x1,x2,…,xn)T为基可行解的充要条件是X的正分量所对应的系数列向量是线性无关的。第23页,共59页，2024年2月25日，星期天第3节单纯形法第24页,共59页，2024年2月25日，星期天一.单纯形法迭代的基本思想

开始于某一个可行基及其对应的基可行解，从一个基可行解迭代到另一个基可行解，并且使目标函数值不断增大，经过有限步必能求得线性规划问题的最优解或者判定线性规划问题无有界的最优解（无界解）。第25页,共59页，2024年2月25日，星期天二.单纯形法引例考虑线性规划问题：

约束方程的系数矩阵A很显然A中的后3列是线性无关的，它们构成一个基基B对应的变量x3,x4,x5是基变量，则第26页,共59页，2024年2月25日，星期天二.单纯形法引例（2）即：

将它们代入目标函数中得令非基变量x1=x2=0,得目标值

z＝0

一个基可行解X(0)＝(0,0,8,16,12)为了使目标函数能更大，让x2变成基变量，原基变量的x3，x4，x5要有一个变为非基变量当x1=0,由最上式得从上式可看出，当x2=3仍可保证所有变量非负，并使目标函数增大第27页,共59页，2024年2月25日，星期天二.单纯形法引例（3）为了得到以x3,x4,x2为基变量的一个基可行解，则对左边方程中的x2与x5互换得再令非基变量x1=x5=0,得目标值

z＝9

一个基可行解X(0)＝(0,3,2,16,0)为了使目标函数能更大，让x1变成基变量，原基变量的x3，x4，x2要有一个变为非基变量目标函数变为第28页,共59页，2024年2月25日，星期天二.单纯形法引例（4）这样如此下去，可得X(2)＝(2,3,0,8,0)为了使目标函数能更大，让x1变成基变量，原基变量的x3，x4，x2要有一个变为非基变量此时目标函数变为X(3)＝(4,2,0,0,4)由于目标函数中的变量系数都小于等于0，所以X(3)＝（4,2,0,0,4)为最优解，最优值z＊＝14▲下面从几何角度分析一下最优解的寻求过程：第29页,共59页，2024年2月25日，星期天几何意义：顶点转移，目标增大第30页,共59页，2024年2月25日，星期天三.单纯形法原理1.确定初始基可行解：对标准型的LP问题在约束条件(1.1)的变量的系数矩阵中总会存在一个单位矩阵。(2)当线性规划的约束条件都为≤号时，其松弛变量对应的系数列向量构成的矩阵即为单位阵；(3)当线性规划的约束条件为≥或＝的情况，引入人工变量后也可实现。(1)系数矩阵中可以直接观察得到一个单位子矩阵；第31页,共59页，2024年2月25日，星期天三.单纯形法原理（2）2.从一个基可行解转换为相邻的基可行解：定义：两个基可行解称为相邻的，如果他们之间变换且仅变换一个基变量。设初始基可行解为：可知：其对应的系数矩阵的增广矩阵为：第32页,共59页，2024年2月25日，星期天三.单纯形法原理（3）易得：(1.3)+(1.4)×θ(θ>0),得令：显然：为使X(1)成为可行解，令：可证明:将(1.6)式代回到X(1)中,X(1)

为基可行解，此时完成了从一个基可行解到另一个与其相邻的基可行解的转换。第33页,共59页，2024年2月25日，星期天三.单纯形法原理（4）证明：将与变量x1,…,xl-1,xl+1…,xm,xj对应的列向量，经重新排列后加上b列有如下形式：因为P1,P2,…,Pl-1，Pj,Pl+1,…Pm线性无关，故X(1)为基可行解。第34页,共59页，2024年2月25日，星期天三.单纯形法原理（5）3.最优性检验与解的判别：将2中的基可行解X(0)与X(1)分别代入目标函数，得

称为检验数第35页,共59页，2024年2月25日，星期天三.单纯形法原理（6）(1)当所有的λj≤0时，现行基可行解为最优解；①当所有的λj<0时，该线性规划问题有唯一最优解；②当所有的λj≤0，且对某个非基变量xk，有λk=0,该线性规划问题有无穷多最优解。(2)当存在某个λj>0且对应的列向量Pj≤0时，该线性规划问题有无界解；(4)对线性规划问题无可行解的判别将在后面讨论。(2)当存在某个λj>0且对应的列向量Pj

中有正分量时，说明目标函数值还可以增大，需要进行基变换；第36页,共59页，2024年2月25日，星期天第4节

单纯形法的计算步骤第37页,共59页，2024年2月25日，星期天一.单纯形法的计算步骤第一步：求初始基可行解，列出初始单纯形表XB

bx1x2...xmxm+1

...xj...xnx1x2...xmb1b2...bm

10...0a1,m+1...a1j...a1n01...0a2,m+1...a2j...a2n...........................00...1am,m+1...amj...amnc

c1c2...cm

cm+1

...cj

...cn首先写出关于价值系数的表：（非单纯形表）第38页,共59页，2024年2月25日，星期天一.单纯形法的计算步骤（2）将基变量下方的价值系数通过变换化为零，得初始单纯形表XB

bx1x2...xmxm+1

...xj...xnx1x2...xm

b1b2...bm

10...0a1,m+1...a1j...a1n01...0a2,m+1...a2j...a2n...........................00...1am,m+1...amj...amn

-z

00...0

......

第39页,共59页，2024年2月25日，星期天一.单纯形法的计算步骤（3）第二步：最优性检验(1)当所有的λj≤0时，现行基可行解为最优解；①当所有的λj<0时，该线性规划问题有唯一最优解；②当所有的λj≤0，且对某个非基变量xk，有λk=0,该线性规划问题有无穷多最优解。(2)当存在某个λj>0且对应的列向量Pj≤0时，该线性规划问题有无界解；(3)当存在某个λj>0且对应的列向量Pj

中有正分量时，说明目标函数值还可以增大，需要进行基变换。第40页,共59页，2024年2月25日，星期天一.单纯形法的计算步骤(4)第三步：换基迭代

(1)确定进基变量选择检验数最大的非基变量为进基变量λk=max{λj|λj>0,j=1,2,...,n}则xk为进基变量

(2)确定出基变量

根据下列原则确定出基变量则λl所对应的基变量xl为出基变量元素alk为轴心项(或称为主元素)(3)以alk为轴心项进行换基迭代

即利用矩阵的初等行变换把元素alk所在的列化为单位向量.得到新的单纯形表第41页,共59页，2024年2月25日，星期天一.单纯形法的计算步骤（5）第四步：重复第二、三步，一直到计算结束为止。第42页,共59页，2024年2月25日，星期天二．单纯形法例1(1)例用单纯形法解下列线性规划

解:将原问题化为标准形为：得单纯形初表为:第43页,共59页，2024年2月25日，星期天

XB

b

x1x2x3x4x5

x3x4x5

81612

121004001004001

－z

0

23000二．单纯形法例1(2)

T(B1)x3x4x2-z21010-1/21640010301001/4-92000-3/4

T(B2)第44页,共59页，2024年2月25日，星期天

XB

b

x1x2x3x4x5

x3x4x2

2163

1010-1/24001001001/4

-z

-9

2000-3/4

T(B2)x1x4x2-z21010-1/2800-412301001/4-1300-201/4

T(B3)二．单纯形法例1(3)第45页,共59页，2024年2月25日，星期天

XB

b

x1x2x3x4x5

x1x4x2

283

1010-1/200-41201001/4

-z

-13

00-201/4

T(B3)x1x5x2-z41001/40400-21/212011/2-1/80-1400-3/2-1/80

T(B4)二．单纯形法例1(4)第46页,共59页，2024年2月25日，星期天二．单纯形法例1(4)在单纯形终表中，x3,x4为非基变量，所有非基变量检验数均小于零，故该线性规划问题有唯一最优解X*=(4,2,0,0,4)T

，最优值为

Z*=14。第47页,共59页，2024年2月25日，星期天二．单纯形法例2(1)例2:用单纯形法解下列线性规划

解:将原问题化为标准形为：得单纯形初表为:第48页,共59页，2024年2月25日，星期天

XB

b

x1x2x3x4x5

x3x4x5

438

101000101012001

-z

012000

T(B1)x3x2x5-z4101003010102100-21-6100-20

T(B2)二．单纯形法例2(2)第49页,共59页，2024年2月25日，星期天

XB

b

x1x2x3x4x5

x3x2x5

432

1010001010100-21

-z-6

100-20

T(B2)x3x2x1-z2001221-80000-1

T(B3)二．单纯形法例2(3)第50页,共59页，2024年2月25日，星期天二．单纯形法例2(4)在单纯形终表中，x4,x5为非基变量，非基变量检验数均小于等于零，且λ4=0,λ5=-1<0;故该线性规划问题有无穷多最优解。注：在上述单纯形终表中，以x4为进基变量，按照极小化原则确定出基变量x3，进行基变换，可得该线性规划问题的另一个最优解。第51页,共59页，2024年2月25日，星期天

XB

b

x1x2x3x4x5

x3x2x1

232

0012-101010100-21-z-8

0000-1

T(B3)x4x2x1-z1001/21-1/2201-1/201/2410100-80000-1

T(B4)最优解X*=(2,3,2,0,0)T

最优值Z*=8六．单纯形法举例2(5)

最优值Z*=8最优解X*=(4,2,0,1,0)T第52页,共59页，2024年2月25日，星期天开始判断所有检验数是否小于等于0得到最优解构造单纯形表NO

输入结束Yes

是否存在某个大于0的检验数所对应的列的元素全小于等于0？原问题为无界解换基迭代选择出基变量Yes

选择进基变量NO

单纯形法的框图表示为如下:第53页,共59页，2024年2月25日，星期天注：㈠退化情形的处理为避免出现计算的循环，1947年勃兰特（Bland）提出了一个简单有效的规则：(1)当存在多个λj>0时，始终选取下标值为最小的变量为进基变量；(2)当计算θ值出现两个以上相同的最小比值时，始终选取下标值为最小的变量为出基变量。按最小比值θ来确定出基变量时，有时会出现两个以上相同的最小比值，从而使下一个单纯形表中出现一个或多个基变量