第一章线性规划与单纯形法 §2 线性规划问题的标准型与解的概念 ⊙2.1线性规划的标准型 我们规定线性规划的标准型如下: maxZ=C xj+C2x2.+CnXn a11X1+a12x2+……+a1nXn=b1 a21X1+a22x2+……+a2nxn=b2 am1x1+a2x2+……+amXn=bm X1,X2 …,Xn≥0 通常称c(j1,2n)为价值系数,b(i=1,2,.m)为资源 系数;a为技术系数,或约束系数。在模型中它们是常数
第一章 线性规划与单纯形法 §2 线性规划问题的标准型与解的概念 2.1 线性规划的标准型 我们规定线性规划的标准型如下: maxZ=c1 x1 +c2 x2 +‥‥+cn xn a11x1 +a12x2 +‥‥+a1nxn =b1 a21x1 +a22x2 +‥‥+a2nxn =b2 …………………………… am1x1 +am2x2 +‥‥+amnxn =bm x1 ,x2 ,‥,xn≥0 通常称cj (j=1,2…n)为价值系数,bi(i=1,2,…m)为资源 系数;aij为技术系数,或约束系数。在模型中它们是常数
若记 X=(xj,x2...x)C=(c,c2...cn),b=(bi,b2...bm) A=(aij)nxn=(P1,P2...Pn) 则标准型亦可记作 maxZ=CX AX=b X≥0 或 max-c. ΣPxb X:≥0,j1,2.n
若记 X=(x1 ,x2…xn)T ,C=(c1 ,c2…cn),b=( b1,b2…bm)T A=(aij)n×n =(P1,P2…Pn) 则标准型亦可记作 maxZ= CX AX=b X≥0 或 maxZ= = n j j x 1 cj Σ Pjxj = b xj≥0, j=1,2…n
任何形式的线性规划都可以化为与其等价的标准形式。 (1)如果目标函数是minZ=cx,则可令Z=-Z,将目标函 数变为:maxZ=-cx (2)如果某约束条件为不等式:ai1x1+a2x2……+anxn≤bi 则在约束条件的左端加一个非负变量x+,称之为松弛变量, 即可变为等式: ailxtai2x2.tain Xni=bi 如果某约束条件为不等式:a1x1+a2x2+…+ainXn≥b; 则可在约束条件的左端减一个非负变量x+,称之为剩余变量 或松弛变量,即可变为等式:a1X1+a2x2+…+ainx,X+ib (3)如果x,没有非负限制,则可令x=x -x;”,其中x ≥0,代入目标函数及约束条件即可
任何形式的线性规划都可以化为与其等价的标准形式。 (1)如果目标函数是 minZ=cx,则可令 Z=-Z,将目标函 数变为:maxZ =-cx (2)如果某约束条件为不等式:ai1x1 +ai2x2 +‥‥+ainxn≤bi 则在约束条件的左端加一个非负变量xn+i,称之为松弛变量, 即可变为等式: ai1x1 +ai2x2 +‥‥+ainxn + xn+i =bi 如果某约束条件为不等式:ai1x1 +ai2x2 +‥‥+ainxn≥bi 则可在约束条件的左端减一个非负变量xn+i,称之为剩余变量 或松弛变量,即可变为等式: ai1x1 +ai2x2 +‥‥+ainxn -xn+i =bi (3)如果xj没有非负限制,则可令xj =xj ′ -xj″,其中xj ′ , xj″ ≥0,代入目标函数及约束条件即可
例3将线性规划 minZ-3x1-X2 X1+x2≤1 X1-x2≥-1 X1≥0 化为标准型。 解: nLULn
例3 将线性规划 minZ=3x1 -x2 x1 +x2≤1 X1 -x2≥-1 x1≥0 化为标准型。 解:
。2.1线性规划解的概念 我们把决策变量的一组取值称为线性规划问题的一个解 满足约束条件的解称为可行解。所有可行解的集合称为可行 域。使目标函数达到最优的可行解称为最优解。 在上一节图解法中,我们求得例1问题的最优解是唯一的 但是线性规划问题的解还可能出现以下几种情况: (1)无穷多个最优解。若例1的目标函数变为maxZ=4x1+2x2 就会出现这种情况。见图1-1
2.1 线性规划解的概念 我们把决策变量的一组取值称为线性规划问题的一个解。 满足约束条件的解称为可行解。所有可行解的集合称为可行 域。使目标函数达到最优的可行解称为最优解。 在上一节图解法中,我们求得例1问题的最优解是唯一的, 但是线性规划问题的解还可能出现以下几种情况: (1)无穷多个最优解。若例1的目标函数变为maxZ=4x1+2x2, 就会出现这种情况。见图1-1
图1-1 X2 60 4x1+2X2=120 50 maxZ=4x+2X2 Z-6x1+4X2 40 30 20 2x1+3x2=100 10 10203040 50
O X2 60 50 40 30 20 10 10 20 30 40 50 x1 4x1+2x2=120 2x1+3x2=100 Q3 Q2 Q1 图1-1 maxZ=4x1+2x2 Z=6x1+4x2
(2)无可行解。如果约束中存在相互矛盾的约束条件,则 导致可行域是空集,此时问题无可行解。 (3)无有限最优解。对下述线性规划问题 maxZ=X+X -X1+x2≤4 X1-X2≤2 X1,X2≥0 用图解法求解结果见图1-2
(2)无可行解。如果约束中存在相互矛盾的约束条件,则 导致可行域是空集,此时问题无可行解。 (3)无有限最优解。对下述线性规划问题 maxZ=x1+x2 -x1+x2 ≤4 x1 -x2 ≤2 x1 ,x2 ≥0 用图解法求解结果见图1-2
图1-2 -X1十X2=4 X1X2=2 Z-X+X 2 XI 从图中可以看出可行域无界,在可行域中 找不到最大值点,目标函数值可以增大到无穷 大,称这种情况为无有限最优解或无界解
图1-2 x2 4 2 2 4 0 x1 从图中可以看出可行域无界,在可行域中 找不到最大值点,目标函数值可以增大到无穷 大,称这种情况为无有限最优解或无界解。 x1 -x -x 2 =2 1+x2=4 Z=x1+x2
⊙线性规划基解的概念 记线性规划问题为 maxZ=CX AX=b X≥0 基:设A是m×n阶约束系数矩阵(m≤n),秩A=m: A=(P1,P2,…,Pn),则A中一定存在m个线性无关的列向 量, 设为P,Pj2,,P,称可逆矩阵B=(PP2,Pn) 为线性规划(L)的一个基,称B中的列向量对应的变量 x,X2,,xm为基变量,其余变量称为非基变量。 基本解:记基变量为X(x1,x2,x)T,非基变量 构成的列向量记为X,并令XN=O,则有AX=ΣPX;=BXb, 于是有X=Bb。称XBb,Xv=0为线性规划CL)的 个基本解。 基可行解:若基本解中XBb≥0,则称该解为基可行解, 这时基B也称为可行基
线性规划基解的概念 记线性规划问题为 maxZ= CX (L) AX=b X≥0 基:设A是m×n阶约束系数矩阵(m≤n),秩A=m. A=( P1 ,P2 ,…,Pn ),则A中一定存在m个线性无关的列向 量,设为Pj1,Pj2,…,Pjm,称可逆矩阵B=(Pj1,Pj2,…,Pjm) 为线性规划(L)的一个基,称B中的列向量对应的变量 xj1,xj2,…,xjm为基变量,其余变量称为非基变量。 基本解:记基变量为XB =(xj1,xj2,…,xjm)T ,非基变量 构成的列向量记为XN,并令XN =0,则有AX=ΣPjxj =BXB =b, 于是有 XB =B -1b。称XB =B -1b, XN =0为线性规划(L)的一 个基本解。 基可行解:若基本解中XB=B-1b≥0,则称该解为基可行解, 这时基B也称为可行基
显然,基可行解的数目<基解的数目≤ 例4求出下面线性规划的所有基本解,并指出哪些 是基可行解。 maxZ-2x +X2 3x1+5x≤15 6x1+2x224 X1,X2≥0 解:标准化得 maxZ-2x+X 3x1+5x2+x3 =15 6x1+2x2++x,=24 X1X2,X33X4≥0
显然,基可行解的数目≤基解的数目≤ m C n 例4 求出下面线性规划的所有基本解,并指出哪些 是基可行解。 maxZ=2x1+x2 3x1+5x2 ≤15 6x1+2x2 ≤24 x1 ,x2 ≥0 解 :标准化得 maxZ=2x1+x2 3x1+5x2 + x3 = 15 6x1+2x2 + +x4 = 24 x1 ,x2 , x3,, x4 ≥0