故目标函数为: minz=(32x1+24x2)+(8x+12x2)=40x1+36x2 约束条件为: 8×25×x,+8×15×x≥1800 8×25×x,<1800 8×15×x<1800 x≥0,x2≥0
故目标函数为： 1 2 1 2 40 1 36 2 min z = (32x + 24x ) + (8x +12x ) = x + x 约束条件为： + 0, 0 8 15 1800 8 25 1800 8 25 8 15 1800 1 2 2 1 1 2 x x x x x x
线性规划模型:minz=40x1+36x 5x.+3x>45 x,<9 x<15 XI ≥0 x≥0 解答
线性规划模型： min 40 1 36 2 z = x + x + 0, 0 15 9 5 3 45 . . 1 2 2 1 1 2 x x x x x x st 解答 返 回
线性规划的基本算法单纯形法 1.线性规划的标准形式: mn z=f(x) s.g;(x)≤0(i=1,2,,m) 其中目标函数f(x)和约束条件中g;(x)都是线性函数 2.线性规划的基本算法单纯形法 用单纯法求解时,常将标准形式化为 min S.t。Ax=b (1) 0 这里A=(an)n,x=(1x2…x) bn)
1.线性规划的标准形式： x min z = f (x) s.t. g (x) i 0 （ i = 1,2,,m) 其中目标函数 f (x) 和约束条件中 g (x) i 都是线性函数 min f = c x s.t. Ax = b （1） x 0 这里 A = (ai j )m,n , x = ( ) T 1 2 n x x x b = ( ) T b1 b2 bn , c = ( ) n c c c 1 2 用单纯法求解时，常将标准形式化为： 2. 线性规划的基本算法——单纯形法 线性规划的基本算法——单纯形法
例minz=10x1+9x2 s.t.6x1+5x2≤60 10x1+20X,≥150 X1≤8 0 引入松弛变量x3,x4,x3,将不等式化为等式,即单纯形标准形 min z=10x,+9x s.t.6X1+5X2+x3=60 10X1+20X =150 XI+xs= 8 X≥0(i=1,2,3,4,5) 系数矩阵为 65100 A=|10200-10=(P1P2P3P4P) 000 b=(60,150,8) 显然A的秩ran(A)=3,任取3个线性无关的列向量如P3P4P称为 组基,记为B.其余列向量称为非基,记为N
例 min z = 10x1 + 9x2 s．t．6x1 + 5x2 ≤ 60 10x1 + 20x2 ≥ 150 x1 ≤ 8 x1 , x2 ≥ 0 引入松弛变量x3 , x4 , x5 , 将不等式化为等式, 即单纯形标准形: min z = 10x1 + 9x2 s．t．6x1 + 5x2 + x3 = 60 10x1 + 20x2 - x4 = 150 x1 + x5 = 8 xi≥ 0 (i = 1,2,3,4,5) 系数矩阵为: 6 5 1 0 0 A = 10 20 0 -1 0 = (P1 P2 P3 P4 P5 ) 1 0 0 0 1 b = (60, 150, 8 ) T 显然A的秩ran(A)=3, 任取3个线性无关的列向量,如P3 P4 P5称为 一组基, 记为B. 其余列向量称为非基, 记为N
将A的列向量重排次序成A=(B,N),相应x=(x,x),c=(cB,cN) 基对应的变量x称为基变量,非基对应的变量x称为非基变量 于是f=cBxB+cNxN,Ax=BxB+Nxy=b AU XB=B-b-B- NXN, f=CBB- b+(CN-CBB-NXN 令非基变量x=0,解得基变量xB=Bb,称(xB,x)为基解 基解的所有变量的值都非负,则称为基可行解,此时的基称为可行基 若可行基进一步满足:c-cBB-N≥0,即:cBB-N-cN≤0 则对一切可行解x,必有(x)≥cB1b,此时称基可行解x=(Bb,0)T 为最优解 3.最优解的存在性定理 定理1如果线性规划(1)有可行解,那么一定有基可行解. 定理2如果线性规划(1)有最优解,那么一定存在一个基可行解 是最优解
于是 f = cBxB + cNxN , Ax = BxB + NxN = b, 则 xB = B-1b-B-1NxN , f = cBB-1b + (cN – cBB-1N)xN 令非基变量 xN = 0, 解得基变量 xB = B−1 b, 称(xB, xN)为基解. 基解的所有变量的值都非负，则称为基可行解，此时的基称为可行基. 若可行基进一步满足: cN – cBB-1N≥0, 即: cBB-1N - cN≤0 则对一切可行解x, 必有f(x) ≥ cBB-1b, 此时称基可行解x = (B-1b, 0) T 为最优解. 3. 最优解的存在性定理 将A的列向量重排次序成A = (B, N), 相应x = (xB, xN) T , c = (cB, cN) 基对应的变量xB称为基变量, 非基对应的变量xN称为非基变量. 定理1 如果线性规划(1)有可行解，那么一定有基可行解. 定理2 如果线性规划(1)有最优解，那么一定存在一个基可行解 是最优解