单纯形法步骤详解（附例题）

2024-02-08 13:23| 来源: 网络整理| 查看: 265

用单纯形法求解下列问题： M a x 6 x 1 + 14 x 2 + 13 x 3 Max 6x_1 + 14x_2 + 13x_3 Max6x1+14x2+13x3 s . t . { x 1 + 4 x 2 + 2 x 3 ≤ 48 x 1 + 2 x 2 + 4 x 3 ≤ 60 x 1 , x 2 , x 3 ≥ 0 s.t.\left\{ \begin{aligned} x_1+4x_2+2x_3&\le48\\ x_1+2x_2+4x_3&\le60\\ x_1,x_2,x_3&\ge0 \end{aligned} \right. s.t.⎩ ⎨ ⎧x1+4x2+2x3x1+2x2+4x3x1,x2,x3≤48≤60≥0

将模型转化为标准形式

首先进行标准化,线性规划的标准形式：（ L P ） { M a x C T X s . t . A x = b x ≥ 0 （LP）\left\{ \begin{aligned} &MaxC^TX\\ &s.t.Ax=b\\ &x\ge0 \end{aligned} \right. （LP）⎩ ⎨ ⎧MaxCTXs.t.Ax=bx≥0 即约束条件都是等式，等式约束的右端项为非负的常数，每个变量都要求取非负数值（无约束也不行）

方法若目标函数为最小值，将目标函数取一个负数转换为求最大值即可若约束为不等式。约束方程为“≤”不等式,则可在“≤”不等式的左端加入非负松弛变量，把原不等式变为等式；约束方程为“≥”不等式，则可在“≥”不等式的左端减去非负剩余变量（也可称松弛变量)，把原不等式变为等式约束条件。若表达式 x i x_i xi没有约束。用 x i − x j x_i-x_j xi−xj代替 x i x_i xi即可。例题

M i n − x 1 + 2 x 2 − 3 x 3 Min -x_1 + 2x_2 - 3x_3 Min−x1+2x2−3x3 s . t . { x 1 + x 2 + x 3 ≤ 7 x 1 − x 2 + x 3 ≥ 2 3 x 1 − x 2 − 2 x 3 = − 5 x 1 , x 2 ≥ 0 , x 3 无约束 s.t.\left\{ \begin{aligned} x_1+x_2+x_3&\le7\\ x_1-x_2+x_3&\ge2\\ 3x_1-x_2-2x_3&=-5\\ x_1,x_2\ge0,x_3&无约束 \end{aligned} \right. s.t.⎩ ⎨ ⎧x1+x2+x3x1−x2+x33x1−x2−2x3x1,x2≥0,x3≤7≥2=−5无约束将该LP问题转化为标准型： M a x x 1 − 2 x 2 + 3 ( x 3 − x 4 ) + 0 x 5 + 0 x 6 Max x_1 - 2x_2 + 3(x_3-x_4)+0x_5+0x_6 Maxx1−2x2+3(x3−x4)+0x5+0x6 s . t . { x 1 + x 2 + x 3 − x 4 + x 5 = 7 x 1 − x 2 + x 3 − x 4 − x 6 = 2 − 3 x 1 + x 2 + 2 ( x 3 − x 4 ) = 5 x 1 , x 2 , x 3 , x 4 , x 5 , x 6 ≥ 0 s.t.\left\{ \begin{aligned} x_1+x_2+x_3-x_4+x_5&=7\\ x_1-x_2+x_3-x_4-x_6&=2\\ -3x_1+x_2+2(x_3-x_4)&=5\\ x_1,x_2,x_3,x_4,x_5,x_6&\ge0 \end{aligned} \right. s.t.⎩ ⎨ ⎧x1+x2+x3−x4+x5x1−x2+x3−x4−x6−3x1+x2+2(x3−x4)x1,x2,x3,x4,x5,x6=7=2=5≥0

接原问题, \textbf{接原问题,} 接原问题,将原LP问题化为标准型可得： M a x 6 x 1 + 14 x 2 + 13 x 3 + 0 x 4 + 0 x 5 Max 6x_1 + 14x_2 + 13x_3+0x_4+0x_5 Max6x1+14x2+13x3+0x4+0x5 s . t . { x 1 + 4 x 2 + 2 x 3 + x 4 = 48 x 1 + 2 x 2 + 4 x 3 + x 5 = 60 x 1 , x 2 , x 3 , x 4 , x 5 ≥ 0 s.t.\left\{ \begin{aligned} x_1+4x_2+2x_3+x_4&=48\\ x_1+2x_2+4x_3+x_5&=60\\ x_1,x_2,x_3,x_4,x_5&\ge0 \end{aligned} \right. s.t.⎩ ⎨ ⎧x1+4x2+2x3+x4x1+2x2+4x3+x5x1,x2,x3,x4,x5=48=60≥0

初始化单纯形表

取初始基本可行解 x 1 = x 2 = x 3 = 0 ， x 4 = 48 ， x 5 = 60 x_1 = x_2 = x_3 = 0， x_4 = 48， x_5 = 60 x1=x2=x3=0，x4=48，x5=60；它的基 [p4, p5]= ∣ 1 0 0 1 ∣ \begin{vmatrix} 1 & 0\\ 0 & 1 \end{vmatrix} 1001 为单位矩阵。由标准形式可知 C = [ 6 , 14 , 13 , 0 , 0 ] T C=[6,14,13,0,0]^T C=[6,14,13,0,0]T, C B = [ 0 , 0 ] T C_B=[0,0]^T CB=[0,0]T, A= ∣ 1 4 2 1 0 1 2 4 0 1 ∣ \begin{vmatrix} 1 & 4 & 2 & 1 & 0\\ 1 & 2 & 4 & 0 & 1 \end{vmatrix} 1142241001 = [ P 1 , P 2 , P 3 , P 4 , P 5 ] [P_1,P_2,P_3,P_4,P_5] [P1,P2,P3,P4,P5], b = [ 48 , 60 ] T b=[48,60]^T b=[48,60]T 此时， − z = − 0 × 48 − 0 × 60 = 0 -z=-0\times48-0\times60=0 −z=−0×48−0×60=0 则初始的单纯形表为：

c 1 c_1 c1 c 2 c_2 c2 c 3 c_3 c3 c 4 c_4 c4 c 5 c_5 c5 C B C_B CB X B X_B XBb6141300 θ \theta θ0 x 4 x_4 x44814210120 x 5 x_5 x5601240130-z:06141300 检验数

其中，最后一行为检验数： σ i = c i − ∑ m k = 1 c k a k i \sigma_i=c_i-\displaystyle \sum{m \atop k=1}c_ka_{ki} σi=ci−∑k=1mckaki 即 σ 1 = 6 − 0 × 1 − 0 × 1 = 6 \sigma_1=6-0\times1-0\times1=6 σ1=6−0×1−0×1=6, σ 2 = 14 − 0 × 4 − 0 × 2 = 14 \sigma_2=14-0\times4-0\times2=14 σ2=14−0×4−0×2=14, σ 3 = 13 − 0 × 2 − 0 × 4 = 13 \sigma_3=13-0\times2-0\times4=13 σ3=13−0×2−0×4=13, σ 4 = 0 − 0 × 1 − 0 × 0 = 0 \sigma_4=0-0\times1-0\times0=0 σ4=0−0×1−0×0=0 σ 5 = 0 − 0 × 0 − 0 × 1 = 0 \sigma_5=0-0\times0-0\times1=0 σ5=0−0×0−0×1=0 易知第一次单纯性表的检验数分别为对应系数 c i c_i ci。

进基变量

取非负检验数中的最大值为进基变量（对于检验数这一行值，当检验数均为非正后，达到最优（一定是对Max问题），如果此时非基变量检验数有0值，则有无限多最优解；如果计算过程中出现检验数大于0的列对应的系数列向量中所有分量都有 a i k ≤ 0 a_{ik}\le0 aik≤0，则无有限最优解），在此题中，14为正数中的最大值，则 x 2 x_2 x2为进基变量。

离基变量

计算最后一列的 θ \theta θ值，设进基变量的下角标为k,即 x k x_k xk为进基变量， θ \theta θ = b i / a i k b_i/a_{ik} bi/aik,如果 a i k = 0 a_{ik}=0 aik=0,该 θ i \theta_i θi设为无穷大，选择最小的作为离基变量。即 θ 1 = b 1 / a 12 = 48 / 4 = 12 \theta_1=b_1/a_{12}=48/4=12 θ1=b1/a12=48/4=12， θ 2 = b 2 / a 22 = 60 / 2 = 30 \theta_2=b_2/a_{22}=60/2=30 θ2=b2/a22=60/2=30；该题中的最小值为12，所以离基变量为 x 4 x_4 x4。

初等行变换

继续计算单纯性表，将进基变量通过初等行变换为单位向量，即从 ∣ 4 2 ∣ \begin{vmatrix} 4\\ 2 \end{vmatrix} 42 变为 ∣ 1 0 ∣ \begin{vmatrix} 1\\ 0 \end{vmatrix} 10 为此，我们将第一行乘以1/4，在将第二行减去2倍的第一行，注意，加粗部分均需参与初等行变换。 C B C_B CB系数部分按照相应的进基变量、离基变量进行修改。

c 1 c_1 c1 c 2 c_2 c2 c 3 c_3 c3 c 4 c_4 c4 c 5 c_5 c5 C B C_B CB X B X_B XBb6141300 θ \theta θ0 x 2 x_2 x24814210120 x 5 x_5 x5601240130-z:06141300 c 1 c_1 c1 c 2 c_2 c2 c 3 c_3 c3 c 4 c_4 c4 c 5 c_5 c5 C B C_B CB X B X_B XBb6141300 θ \theta θ14 x 2 x_2 x2121/411/21/40240 x 5 x_5 x5361/203-1/2112-z:-1685/206-7/20

对斜体部分进行计算得到 − z = − 14 × 12 − 0 × 36 = − 168 -z=-14\times12-0\times36=-168 −z=−14×12−0×36=−168 计算检验数： σ 1 = 6 − 14 × 1 / 4 − 0 × 1 / 2 = 6 − 14 / 4 = 5 / 2 \sigma_1=6-14\times1/4-0\times1/2=6-14/4=5/2 σ1=6−14×1/4−0×1/2=6−14/4=5/2, σ 2 = 14 − 14 × 1 − 0 × 0 = 0 \sigma_2=14-14\times1-0\times0=0 σ2=14−14×1−0×0=0, σ 3 = 13 − 14 × 1 / 2 − 0 × 3 = 6 \sigma_3=13-14\times1/2-0\times3=6 σ3=13−14×1/2−0×3=6, σ 4 = 0 − 14 × 1 / 4 − 0 × （ − 1 / 2 ） = − 7 / 2 \sigma_4=0-14\times1/4-0\times（-1/2）=-7/2 σ4=0−14×1/4−0×（−1/2）=−7/2 σ 5 = 0 − 14 × 0 − 0 × 1 = 0 \sigma_5=0-14\times0-0\times1=0 σ5=0−14×0−0×1=0 基变量对应的检验数一定为0。 6最大， x 3 x_3 x3进基；计算 θ i \theta_i θi： θ 1 = b 1 / a 12 = 12 / （ 1 / 2 ） = 24 \theta_1=b_1/a_{12}=12/（1/2）=24 θ1=b1/a12=12/（1/2）=24， θ 2 = b 2 / a 22 = 36 / 3 = 12 \theta_2=b_2/a_{22}=36/3=12 θ2=b2/a22=36/3=12； 12最小， x 5 x_5 x5离基。同理继续进行变换、计算：

c 1 c_1 c1 c 2 c_2 c2 c 3 c_3 c3 c 4 c_4 c4 c 5 c_5 c5 C B C_B CB X B X_B XBb6141300 θ \theta θ0 x 4 x_4 x44814210120 x 5 x_5 x5601240130-z:06141300 c 1 c_1 c1 c 2 c_2 c2 c 3 c_3 c3 c 4 c_4 c4 c 5 c_5 c5 C B C_B CB X B X_B XBb6141300 θ \theta θ14 x 2 x_2 x2121/411/21/40240 x 5 x_5 x5361/203-1/2112-z:-1685/206-7/20 c 1 c_1 c1 c 2 c_2 c2 c 3 c_3 c3 c 4 c_4 c4 c 5 c_5 c5 C B C_B CB X B X_B XBb6141300 θ \theta θ14 x 2 x_2 x261/6101/3-1/63613 x 3 x_3 x3121/601-1/61/372-z:–2403/200-5/2-2 c 1 c_1 c1 c 2 c_2 c2 c 3 c_3 c3 c 4 c_4 c4 c 5 c_5 c5 C B C_B CB X B X_B XBb6141300 θ \theta θ6 x 1 x_1 x1361602-113 x 3 x_3 x360-11-1/21/2-z:–2940-90-11/2-1/2

此时，检验数全为非正数，当前解即为最优解， x ∗ = [ 36 , 0 , 6 , 0 , 0 ] T x^*=[36,0,6,0,0]^T x∗=[36,0,6,0,0]T,最优解为 z = 294 z=294 z=294。值得注意的是、变量非负约束是单纯形表中所隐含的,任何时候b列的值都应是非负的，如果出现负值，则表示当前基本解不是可行解，求解也就无法进行。

【本文地址】

公司简介

联系我们