线性规划的图解法和标准化

线性规划的图解法和标准化第一页，共二十三页，2022年，8月28日1例1.目标函数：

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§1图解法

对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解其方法：第二页，共二十三页，2022年，8月28日2几何概念代数概念直线满足一个等式约束的解半平面满足一个不等式约束的解半平面的交集：凸多边形满足一组不等式约束的解目标函数等值线：一组平行线目标函数值等于一个常数的解§1图解法注：当目标函数求极大时，等值线向右移；当目标函数求极小时，等值线向左移。第三页，共二十三页，2022年，8月28日3§1图解法

(1)分别取决策变量X1和X2为横轴和纵轴，建立直角坐标系。在直角坐标系中，图上任意一点的坐标代表了决策变量的一组取值，例1的每个约束条件都代表一个半平面。x2x1X2≥0X2=0x2x1X1≥0X1=0第四页，共二十三页，2022年，8月28日4§1图解法（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400第五页，共二十三页，2022年，8月28日5§1图解法（3）把五个图合并成一个图，取各约束条件的公共部分，如图3-1所示。100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图3-1第六页，共二十三页，2022年，8月28日6§1图解法（4）目标函数Z=50x1+100x2，当Z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，Z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件，则其可行域的顶点也是有限的。x1x2z=20000=50x1+100x2图3-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE第七页，共二十三页，2022年，8月28日7例2max z=x1+3x2 s.t. x1+x2≤6 -x1+2x2≤8 x1≥0,x2≥0可行域目标函数等值线最优解64-860x1x2§1图解法第八页，共二十三页，2022年，8月28日8进一步讨论例3

某公司由于生产需要，共需要A、B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A、B两种原料，使得购进成本最低？第九页，共二十三页，2022年，8月28日9进一步讨论解：目标函数：MinZ=2x1+3x2

约束条件：

s.t.x1+x2≥350x1≥

1252x1+x2≤

600x1,x2≥0

采用图解法，如左图：得Q点坐标（250，100）为最优解。100200300400500600100200300400600500x1=125x1+x2=3502x1+3x2=8002x1+3x2=9002x1+x2=6002x1+3x2=1200x1x2Q第十页，共二十三页，2022年，8月28日10重要结论1：线性规划的可行域是凸集可行域的顶点为有限个线性规划的最优解一定可以在某个顶点上实现凸集凸集不是凸集顶点§1图解法第十一页，共二十三页，2022年，8月28日11§1图解法重要结论2：如果线性规划有唯一最优解（例1、2、3），则一定有一个可行域的顶点对应最优解；无穷多个最优解。若将例1中的目标函数变为maxz=50x1+50x2，则线段BC上的所有点都代表最优解；无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；无可行解。若在例1的数学模型中再增加一个约束条件4x1+3x2≥1200，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解。第十二页，共二十三页，2022年，8月28日12§2线性规划的标准化一般形式目标函数：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

注：只能使用一个脚码（变量连续编号），不能使用多重脚码第十三页，共二十三页，2022年，8月28日13§2线性规划的标准化可以看出，线性规划的标准形式有如下四个特点：目标极大化；约束条件为等式；决策变量均非负；约束条件右端常数项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:第十四页，共二十三页，2022年，8月28日14§2线性规划的标准化1、变量不是大于等于0的问题（1）若xj≤0,令xj’=-xj，则xj’≥0（2）若变量为无约束在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令：

xj=xj’-xj”

其中

xj’≥0，xj”≥0

即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj’和xj”的大小。第十五页，共二十三页，2022年，8月28日15§2线性规划的标准化2、目标函数为极小化的问题：设目标函数为：

MinZ=c1x1

+c2x2

+…+cnxn

(可以)令Z’

＝-Z

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

-c2x2-…-cnxn

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

MinZ

＝-MaxZ’3、右端常数项为负数的问题：在标准形式中，要求约束条件右端常数项必须全部是非负的。当某个右端常数项为负时，如bi<0，则把该约束条件两端同时乘以(-1)，得到：-ai1x1-ai2x2-…-ainxn

=-bi第十六页，共二十三页，2022年，8月28日16§2线性规划的标准化4、约束条件不是等式的问题：设约束条件为

ai1x1+ai2x2+…+ainxn

≤bi

可以引进一个新的变量s

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

s=bi–(ai1x1

+ai2x2

+…+ainxn

)显然，s

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

ai1x1+ai2x2+…+ainxn+s=bi第十七页，共二十三页，2022年，8月28日17§2线性规划的标准化当约束条件为

ai1x1+ai2x2+…+ainxn

≥bi

时，类似地令

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

显然，s

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

ai1x1+ai2x2+…+ainxn-s=bi第十八页，共二十三页，2022年，8月28日18§2线性规划的标准化

为了使约束由不等式成为等式而引进的变量s,当不等式为“小于等于”时称为“松弛变量”；当不等式为“大于等于”时称为“剩余变量”。如果原问题中有若干个非等式约束条件，则将其转化为标准形式时，必须对各个约束条件引进不同的松弛变量或剩余变量。

结论：当约束条件为：“≤”：在约束条件的左端加入非负的松弛变量“≥”：在约束条件的左端减去非负的剩余变量注：****松弛变量和剩余变量在目标函数中的系数为0****第十九页，共二十三页，2022年，8月28日19例4：将下列线性规划模型标准化：§2线性规划的标准化第二十页，共二十三页，2022年，8月28日20§2线性规划的标准化第二十一页，共二十三页，2022年，8月28日21§2线性规划的标准化例5：将以下线性规划问题转化为标准形式

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

+4x2-5x3≤6