线性规划的图解法与单纯形解法

线性规划的图解法与单纯形解法

线性规划的图解法与单纯形解法

线性规划单纯形求解的大M法 线性规划单纯形求解的两阶段法

线性规划求解的大M法 为了使加入人工变量后线性规划问题的最优目

标函数值不受影响，我们赋予人工变量一个很 大的负价值系数-M (M为任意大的正数)。 由于人工变量对目标函数有很大的负影响，单

纯形法的寻优机制会自动将人工变量赶到基外， 从而找到原问题的一个可行基。 这种方法我们通常称其为大M法。3

线性规划求解的大M法max z=c1 x1+ c2 x2+…+ cn xn - M (xn+1+…+ xn+m) a11 x1+ a12 x2+…+ a1nxn+ xn+1 = b1 a21 x1+ a22 x2+…+ a2nxn + xn+2= b2 … … am1 x1+ am2 x2+…+ amnxn+ xn+m = bm x1, x2,…, xn , xn+1…, xn+m≥0

线性规划求解的大M法举例【例2.12】用大M法解 下列线性规划

max Z 3 x1 2 x2 x3 4 x1 3 x2 x3 4 x x 2 x 10 1 2 3 2 x1 2 x2 x3 1 x1、x2、x3 0 5

【解】首先将数学模型化为标准形式max Z 3 x1 2 x2 x3 4 x1 3 x2 x3 x4 4 x x 2 x x 10 1 2 3 5 2 x1 2 x2 x3 1 x j 0, j 1,2, ,5 4 x1 3x 2 x3 x 4 x6 4 x x 2 x x 10 1 2 3 5 2 x1 2 x 2 x3 x7 1 x j 0, j 1,2, ,7

式中x4,x5为松弛变量，x5可作为 一个基变量，第一、三约束中分 别加入人工变量x 6 、x 7 ,目标函 数中加入―Mx6―Mx7一项，得到 人工变量单纯形法数学模型

max Z 3x1 2 x 2 x3-Mx6 Mx7

用前面介绍的单纯形法求 解，见下表。

Cj CB -M 0 -M λj -M 0 -1 λj 2 0 -1 λj 2 3 -1 λj x2 x1 x3 x2 x5 x3 x6 x5 x3 XB x6 x5 x7

3 x1 -4 1 2 3-2M -6 -3 2 5-6M -6/5 [3/5] -2/5 5↑ 0 1 0 0

2 x2 3 -1 -2 2+M [5] 3 -2 5M↑ 1 0 0 0 1 0 0 0

-1 x3 1 2 [1] -1+2M↑ 0 0 1 0 0 0 1 0 0 0 1 0

0 x4 -1 0 0 -M -1 0 0 -M -1/5 3/5 -2/5 0 1 1 0 -5

0 x5 0 1 0 0 0 1 0 0 0 1 0 0 2 5/3 2/3 25/3

-M x6 1 0 0 0 1 0 0 0

-M x7 0 0 1 0

b 4 10 1→

3→ 8 1

3/5 31/5 →11/ 5 13 31/3 19/37

最优解X=(31/3,13,19/3,0,0)T;最优值Z=152/3 (1)初始表中的检验数有两种算法，第一种算法是利用第 一、三约束将x6、x7的表达式代入目标涵数消去x6和x7,得 到用非基变量表达的目标函数，其系数就是检验数；第二种 算法是利用公式计算，如

注意：

1 3 ( M ) ( 4) 0 1 ( M ) 2 3 2M

(2)M是一个很大的抽象的数，不需要给出具体的数值， 可以理解为它能大于给定的任何一个确定数值；8

线性规划求解的两阶段法两阶段法的基本思路是： 第一阶段， 首先不考虑原问

题是否存在基可行解， 先求解一个目标函数中只包含 人工变量的线性规划问题，即令目标函数中其他变量的系数取零，人工变量的系数 取某个正的常数(一般取 1),在保持原问题约束条件不变的情况下求这个目标函数极 小化时的解。也就是，给原问题加入人工变量，构造仅含人工变量的目标函数，并 要求最小化。 我们可以构造如下辅助问题 min w=xn+1+…+xn+m+0x1+…+0xn1n n n+1 1 11 1 12 2 a21 x1+ a22 x2+…+ a2nxn + xn+2= b2 a x + a x +…+ a x + x mn n n+m = bm m1 1 m2 2 x1, x2,…, xn , xn+1,…, xn+m≥0

a x + a x +…+ a x + x

=b

…

…

线性规划求解的两阶段法然后用单纯形法求解所构造的新模型，若得到w=0, 这时，若基变量中不含人工变量，则说明原问题存在 基可行解，可进行第二步计算； 否则，原问题无可行解，应停止计算。第二阶段，单纯形法求解原问题 第一阶段计算得到的最终单纯形表中除去人工变量， 将目标函数行的系数，换成原问题的目标函数后，作 为第二阶段计算的初始表，继续求解。10

【例2.14】用两阶段单纯形法求解例【2.12】的线性规划。

max Z 3 x1 2 x2 x3 4 x1 3 x2 x3 4 x x 2 x 10 1 2 3 2 x1 2 x2 x3 1 x1、x2、x3 0

【解】标准型为max Z 3 x1 2 x 2 x3 4 x1 3 x 2 x3 x 4 4 x x 2 x x 10 1 2 3 5 2 x1 2 x 2 x3 1 x j 0, j 1,2, ,5

在第一、三约束方程中加入人工变量x6、x7后，第一阶段问题为min w x6 x7 4 x1 3x 2 x3 x 4 x6 4 x x 2 x x 10 1 2 3 5 2 x1 2 x 2 x3 x7 1 x j 0, j 1,2, ,7

用单纯形法求解，得到第一阶段问题的计算表如下：

CjCB 1 0 1 λj 1 0 0 λj 0 0 0 λj x2 x5 x3 x6 x5 x3 XB x6 x5 x7

0x1 -4 1 2 2 -6 -3 2 6 -6/5 3/5 -2/5 0

0x2 3 -1 -2 -1 [5] 3 -2 -5↑ 1 0 0 0

0x3 1 2 [1] -2↑ 0 0 1 0 0 0 1 0

0x4 -1 0 0 1 -1 0 0 1 -1/5 3/5 -2/5 0

0x5 0 1 0 0 0 1 0 0 0 1 0 0

1x6 1 0 0 0 1 0 0 0

1b x7 0 0 1 0 4 10 1→

3→ 8 1

3/5 31/5 11/513

最优解为 X (0, 3 , 11 ,0 31 ) 最优值w=0。第一阶段最后一张最优5 5 5

表说明找到了原问题的一组基可行解，将它作为初始基可行解，求原问题的最优解，即第二阶段问题为

max Z 3 x1 2 x2 x3 1 3 6 x4 5 x1 x2 5 5 3 31 3x x4 x5 1 5 5 5 2 2 11 x3 x4 x1 5 5 5 x j 0, j 1, 2, , 5

用单纯形法计算得到下表Cj 3 2 -1 0 0 b 3/5 31/5 → 11/5

CB2 0 -1 λj 2 3 -1 λj

XBx2 x5 x3 x2 x1 x3

x1-6/5 [3/5] -2/5 5↑ 0 1 0 0

x21 0 0 0 1 0 0 0

x30 0 1 0 0 0 10

x4-1/5 3/5 -2/5 0 1 1 0 -5

x50 1 0 0 2 5/3 2/3 -25/3 13 31/3 19/3

最优解X=(31/3,13,19/3,0,0)T;最优值Z=152/315

【例2.15】用两阶段法求解例【2.13】的线性规划。

min Z 5 x1 8 x 2 3 x1 x 2 6 x1 2 x 2 4 x , x 0 1 216

【解】第一阶段问题为

min w x5 3 x1 x 2 x3 6 x1 2 x 2 x 4 x5 4 x 0, j 1,2, ,5 j用单纯形法计算如下表：

Cj CB 0 1 λj 0 1 λj x1 x5 XB x3 x5

0 x1 [3] 1 -1↑ 1 0 0

0 x2 1 -2 2 1/3 -7/3 7/3

0 x3 1 0 0 1/3 -1/3 1/3

0 x4 0 -1 1 0 -1 1

1 x5 0 1 0 0 1 0

b

6→ 4

2 2

λj≥0,得到第一阶段的最优解X=(2,0,0,0,2)T,最优目标值w=2≠0,x5 仍在基变量中,从而原问题无可行解。 18

解的判断无界解的判断: 某个λk>0且aik≤0(i=1,2,…,m)则线性规 划具有无界解 无可行解的判断：(1)当用大M单纯形法计算得到最优解并 且存在人工变量i>0时，则表明原线性规划无可行解。 (2) 当第一阶段的最优值w≠0时，则原问题无可行解。

退化基本可行解的判断:存在某个基变量为零的基本可行解。19

本文来源：https://www.bwwdw.com/article/nyyj.html