线性规划建模--基础篇

偏执的太偏执、 2021-09-25 02:44 489阅读 0赞

### 文章目录 ###

*  1. 题目
 *  2. 分析并建模
 *  3. 线性规划的原始问题与一般问题
 *  4. 一般形式
 *  5. 标准形式
 *  6. 基本概念
 *  参考

# 1. 题目 #

**(产品组合问题)** 某公司现有三条生产线来生产两种新产品，其主要数据如 Table 1 所示（时间单位为小时，利润单位为百元）。请问如何生产可以使公司每周利润最大？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70]

# 2. 分析并建模 #

*  **决策变量**。公司每周的利润是和甲、乙两种产品相关联的，因此，甲、乙两种产品每周的生产量就是决策变量。  
    设每周生产的产品甲为  x 1 x\_1 x1，生产的产品乙为  x 2 x\_2 x2。
 *  **约束条件**。每周的产品生产要收到三条生产线的可用生产时间的约束（限制），全为 “ ≤ \\leq ≤” 的不等式约束。
 *  **目标函数**。公司每周的生产利润（可记为  z z z，单位为百元）为最大。

确定目标函数：

*  每周两种产品的销售金额为  ( 7 x 1 + 9 x 2 (7x\_1 + 9x\_2 (7x1\+9x2)；
 *  生产甲、乙两种产品，  
    生产线一消耗资源的成本为  x 1 x\_1 x1，  
    生产线二消耗资源的成本为  2 x 2 2x\_2 2x2，  
    生产线三消耗资源的成本为  ( 3 x 1 + 2 x 2 ) (3x\_1 + 2x\_2) (3x1\+2x2)，  
    总消耗的资源成本为  ( 4 x 1 + 4 x 2 ) (4x\_1 + 4x\_2) (4x1\+4x2)；
 *  每周的利润为销售金额与资源消耗成本之差， z = ( 7 x 1 + 9 x 2 ) − ( 4 x 1 + 4 x 2 ) = ( 3 x 1 + 5 x 2 ) z = (7x\_1 + 9x\_2) - (4x\_1 + 4x\_2) = (3x\_1 + 5x\_2) z=(7x1\+9x2)−(4x1\+4x2)=(3x1\+5x2)。  
    目标是公司每周利润最大，  
     max ⁡ z = 3 x 1 + 5 x 2 \\max z = 3x\_1 + 5x\_2 maxz=3x1\+5x2

确定约束条件：

*  生产线一的使用时间不能超过 4 小时，即  x 1 ≤ 4 x\_1 \\leq 4 x1≤4；
 *  生产线二的使用时间不能超过 12 小时，即  2 x 2 ≤ 12 2x\_2 \\leq 12 2x2≤12；
 *  生产线三的使用时间不能超过 18 小时，即  3 x 1 + 2 x 2 ≤ 18 3x\_1 + 2x\_2 \\leq 18 3x1\+2x2≤18。  
     x 1 ≤ 4 2 x 2 ≤ 12 3 x 1 + 2 x 2 ≤ 18 \\begin\{aligned\} x\_1 &\\leq 4 \\\\ 2x\_2 &\\leq 12 \\\\ 3x\_1 + 2x\_2 &\\leq 18 \\end\{aligned\} x12x23x1\+2x2≤4≤12≤18  
    并且，甲、乙产品的生产数量应该大于等于 0 ，即  x 1 ≥ 0 ， x 2 ≥ 0 x\_1 \\geq 0，x\_2 \\geq 0 x1≥0，x2≥0。

综上，产品组合问题可抽象地归为一个数学模型：  
 max ⁡ z = 3 x 1 + 5 x 2 s.t. \{ x 1 ≤ 4 , 2 x 2 ≤ 6 , 3 x 1 + 2 x 2 ≤ 18 , x 1 ≥ 0 , x 2 ≥ 0 , \\begin\{aligned\} \\max & z = 3x\_1 + 5x\_2 \\\\ & \\text\{s.t.\} \\begin\{cases\} x\_ 1 \\leq 4, \\\\ 2x\_2 \\leq 6, \\\\ 3x\_1 + 2x\_2 \\leq 18, \\\\ x\_1 \\geq 0, x\_2 \\geq 0, \\\\ \\end\{cases\} \\end\{aligned\} maxz=3x1\+5x2s.t.⎩⎪⎪⎪⎨⎪⎪⎪⎧x1≤4,2x2≤6,3x1\+2x2≤18,x1≥0,x2≥0,  
其中， max ⁡ \\max max 是最大化（maximize）的英文简称；s.t. 是受约束于（subject to）的英文简称； x = ( x 1 , x 2 ) T ∈ ℜ 2 \\bm\{x\} = (x\_1, x\_2)^\\text\{T\} \\in \\Re^2 x=(x1,x2)T∈ℜ2 为 2 维向量。

在上面的数学模型中，决策变量为可控的连续变量，目标函数和约束条件都是线性的，称为线性规划问题。

# 3. 线性规划的原始问题与一般问题 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70 1]

# 4. 一般形式 #

对于最大化利润的一般产品组合问题，不妨设有  m m m 类资源用于生产  n n n 种不同产品，各种资源的拥有量分别为  b i ( i = 1 , 2 , … , m ) b\_i (i = 1, 2, \\dots, m) bi(i=1,2,…,m)。又生产单位第  j j j 种产品  ( j = 1 , 2 , … , n ) (j = 1, 2, \\dots, n) (j=1,2,…,n) 时将消费第  i i i 类资源  a i j a\_\{ij\} aij 单位，利润为  c j c\_j cj。Table 3 给出了线性规划模型的所需数据。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70 2]  
仍用  x j ( j = 1 , 2 , … , n ) x\_j (j = 1, 2, \\dots, n) xj(j=1,2,…,n) 代表第  j j j 种产品的生产数量，则线性规划模型为：  
 max ⁡ z = c 1 x 1 + c 2 x 2 + ⋯ + c n x n s.t. \{ a 11 x 1 + a 12 x 2 + ⋯ + a 1 n x n ≤ b 1 , a 21 x 1 + a 22 x 2 + ⋯ + a 2 n x n ≤ b 2 , ⋮ , a m 1 x 1 + a m 2 x 2 + ⋯ + a m n x n ≤ b m , x 1 ≥ 0 , x 2 ≥ 0 , … , x n ≥ 0 , \\begin\{aligned\} \\max & z = c\_1 x\_1 + c\_2 x\_2 + \\dots + c\_n x\_n \\\\ &\\text\{s.t.\} \\begin\{cases\} a\_\{11\} x\_1 + a\_\{12\} x\_2 + \\dots + a\_\{1n\} x\_n \\leq b\_1, \\\\ a\_\{21\} x\_1 + a\_\{22\} x\_2 + \\dots + a\_\{2n\} x\_n \\leq b\_2, \\\\ \\qquad \\qquad \\qquad \\qquad \\vdots, \\\\ a\_\{m1\} x\_1 + a\_\{m2\} x\_2 + \\dots + a\_\{mn\} x\_n \\leq b\_m, \\\\ x\_1 \\geq 0, x\_2 \\geq 0, \\dots, x\_n \\geq 0, \\\\ \\end\{cases\} \\end\{aligned\} maxz=c1x1\+c2x2\+⋯\+cnxns.t.⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧a11x1\+a12x2\+⋯\+a1nxn≤b1,a21x1\+a22x2\+⋯\+a2nxn≤b2,⋮,am1x1\+am2x2\+⋯\+amnxn≤bm,x1≥0,x2≥0,…,xn≥0,  
其中，目标函数可以为  min ⁡ \\min min 的形式，函数约束中 “ ≤ \\leq ≤” 可以为 “=” 或 “ ≥ \\geq ≥”，变量的非负性限制也可以取消。

以上的模型简写形式为：  
 max ⁡ z = ∑ j = 1 n c j x j s.t. \{ ∑ j = 1 n a i j x j ≤ b i ( i = 1 , 2 , … , m ) , x j ≥ 0 ( j = 1 , 2 , … , n ) . \\begin\{aligned\} \\max & z = \\sum\_\{j=1\}^\{n\} c\_j x\_j \\\\ & \\text\{s.t.\} \\begin\{cases\} \\sum\_\{j=1\}^\{n\} a\_\{ij\} x\_j \\leq b\_i \\quad(i = 1, 2, \\dots, m), \\\\ x\_j \\geq 0 \\quad \\quad \\quad \\quad \\quad (j = 1, 2, \\dots, n). \\\\ \\end\{cases\} \\end\{aligned\} maxz=j=1∑ncjxjs.t.\{ ∑j=1naijxj≤bi(i=1,2,…,m),xj≥0(j=1,2,…,n).

用向量形式表达时，上述模型可写为：  
 max ⁡ z = c x s.t. \{ ∑ j = 1 n p j x j ≤ b , x ≥ 0 , \\begin\{aligned\} \\max &z = \\bm\{cx\} \\\\ &\\text\{s.t.\} \\begin\{cases\} \\sum\_\{j=1\}^\{n\} \\bm\{p\}\_j x\_j \\leq \\bm\{b\}, \\\\ \\bm\{x\} \\geq 0, \\\\ \\end\{cases\} \\end\{aligned\} maxz=cxs.t.\{ ∑j=1npjxj≤b,x≥0,  
其中， c = ( c 1 , c 2 . … , c n ) \\bm\{c\} = (c\_1, c\_2. \\dots, c\_n) c=(c1,c2.…,cn)， x = ( x 1 , x 2 , … , x n ) T \\bm\{x\} = (x\_1, x\_2, \\dots, x\_n)^\\text\{T\} x=(x1,x2,…,xn)T， p j = ( a 1 j , a 2 j , … , a m j ) T \\bm\{p\}\_j = (a\_\{1j\}, a\_\{2j\}, \\dots, a\_\{mj\})^\\text\{T\} pj=(a1j,a2j,…,amj)T， b = ( b 1 , b 2 , … , b m ) T \\bm\{b\}=(b\_1, b\_2, \\dots, b\_m)^\\text\{T\} b=(b1,b2,…,bm)T。

用矩阵式来表示可写成：  
 max ⁡ z = c x s.t. \{ A x ≤ b , x ≥ 0 , \\begin\{aligned\} \\max & z = \\bm\{cx\} \\\\ &\\text\{s.t.\} \\begin\{cases\} \\bm\{Ax\} \\leq \\bm\{b\}, \\\\ \\bm\{x\} \\geq \\bm\{0\}, \\\\ \\end\{cases\} \\end\{aligned\} maxz=cxs.t.\{ Ax≤b,x≥0,  
其中， A = ( a i j ) m × n \\bm\{A\}=(a\_\{ij\})\_\{m \\times n\} A=(aij)m×n 称为约束方程组变量的系数矩阵（或者简称约束变量的系数矩阵）。

# 5. 标准形式 #

为求解方便，需要把上述模型变成标准形式，即模型的目标函数为求极大值（某些要求标准形式是求极小值），约束条件全为等式，约束条件右端常数项为非负值，变量取值为非负。  
 max ⁡ z = ∑ j = 1 n c j x j s.t. \{ ∑ j = 1 n a i j x j = b i ( i = 1 , 2 , … , m ) , x j ≥ 0 ( j = 1 , 2 , … , n ) . \\begin\{aligned\} \\max &z = \\sum\_\{j=1\}^\{n\} c\_j x\_j \\\\ &\\text\{s.t.\} \\begin\{cases\} \\sum\_\{j=1\}^\{n\} a\_\{ij\} x\_j = b\_i \\quad (i = 1, 2, \\dots, m), \\\\ x\_j \\geq 0 \\quad \\quad \\quad \\quad \\quad(j = 1, 2, \\dots, n). \\end\{cases\} \\end\{aligned\} maxz=j=1∑ncjxjs.t.\{ ∑j=1naijxj=bi(i=1,2,…,m),xj≥0(j=1,2,…,n).

对非标准形式的线性规划问题，可通过下列方法化为标准形式。

(1) 目标函数求极小值。即  min ⁡ z = ∑ j = 1 n c j x j \\min z = \\sum\_\{j=1\}^\{n\} c\_j x\_j minz=∑j=1ncjxj，令  z ′ = − z z' = - z z′=−z 即可。

(2) 约束条件为不等式。当 “ ≤ \\leq ≤” 时，如  x 1 ≤ 4 x\_1 \\leq 4 x1≤4，可  x 1 + x 3 = 4 x\_1 + x\_3 = 4 x1\+x3=4，则  x 3 ≥ 0 x\_3 \\geq 0 x3≥0。当 “ ≥ \\geq ≥”，如  0.6 x 1 + 0.4 x 2 ≥ 6 0.6x\_1 + 0.4 x\_2 \\geq 6 0.6x1\+0.4x2≥6，可  0.6 x 1 + 90.4 x 2 − x 4 = 6 0.6x\_1 + 90.4x\_2 - x\_4 = 6 0.6x1\+90.4x2−x4=6，则  x 4 ≥ 0 x\_4 \\geq 0 x4≥0。

x 3 x\_3 x3 和  x 4 x\_4 x4 是新加入的变量，取值均为非负，加到原约束条件中区的目的是使不等式转化为等式。其中， x 3 x\_3 x3 称为松弛变量， x 4 x\_4 x4 一般称为剩余变量，其实质与  x 3 x\_3 x3 相同，故也有统称为松弛变量。松弛变量或剩余变量在目标函数中的系数均为 0。

(3) 变量  x j ≤ 0 x\_j \\leq 0 xj≤0。令  x j ′ = − x j x\_j' = - x\_j xj′=−xj 即可。

(4) 取值无约束的变量。令  x j = x j ′ − x j ′ ′ x\_j = x\_j' - x\_j'' xj=xj′−xj′′，其中， x j ′ ≥ 0 x\_j' \\geq 0 xj′≥0， x j ′ ′ ≥ 0 x\_j'' \\geq 0 xj′′≥0。

# 6. 基本概念 #

*  **（可行解）** 满足约束条件的解  x = ( x 1 , x 2 , … , x n ) T \\bm\{x\} = (x\_1, x\_2, \\dots, x\_n)^\\text\{T\} x=(x1,x2,…,xn)T，称为线性规划问题的可行解。全部可行解的集合称为可行域。
 *  **（最优解）** 使目标函数达到最大值的可行解称为最优解，对应的目标函数值称为最优值。
 *  **（基）** 设  A m × n ( n > m ) \\bm\{A\}\_\{m \\times n\} (n > m) Am×n(n>m) 为约束方程组的系数矩阵，其秩为  m m m。 B m × m \\bm\{B\}\_\{m \\times m\} Bm×m 是矩阵  A \\bm\{A\} A 中的满秩子矩阵，则称  B \\bm\{B\} B 是线性规划问题的一个基（基矩阵）。设  
     B = ( a i j ) m × m = ( p 1 , p 2 , … , p m ) ， \\bm\{B\} = (a\_\{ij\})\_\{m \\times m\} = (\\bm\{p\}\_1, \\bm\{p\}\_2, \\dots, \\bm\{p\}\_m)， B=(aij)m×m=(p1,p2,…,pm)，  
    则称  B \\bm\{B\} B 中的每一个列向量  p j ( j = 1 , 2 , … , m ) \\bm\{p\}\_j (j = 1, 2, \\dots, m) pj(j=1,2,…,m) 为基向量。与基向量  p j \\bm\{p\}\_j pj 对应的变量  x j x\_j xj 称为基变量（basic variables），其他变量称为非基变量（nonbasic variables）。
 *  **（基解）** 在约束方程组中，令非基变量  x m + 1 x\_\{m+1\} xm\+1， x m + 2 x\_\{m+2\} xm\+2， … \\dots …， x n x\_\{n\} xn 为 0，则称由约束方程确定的唯一解  x = ( x 1 , x 2 , … , x m , 0 , … , 0 ) T \\bm\{x\} = (x\_1, x\_2, \\dots, x\_m, 0, \\dots, 0)^\\text\{T\} x=(x1,x2,…,xm,0,…,0)T 为线性规划问题的基解。  
    基解中变量取非零值的个数不大于方程数  m m m，且其总数不超过  C n m C\_\{n\}^\{m\} Cnm 个。
 *  **（基可行解）** 满足约束条件的基解称为基可行解。
 *  **（可行基）** 对应于基可行解的基称为可行基。
 *  **（退化基可行解与非退化基可行解）** 称含零值基变量的基可行解为退化基可行解，对应的基为退化可行基。称基变量都不为 0 的基可行解为非退化基可行解，对应的基为非退化可行基。  
    由此可知，退化基可行解中的非零分量一定小于  m m m，非退化基可行解中非零分量一定等于  m m m。若有关线性规划问题的所有基可行解都是非退化基可行解，则该问题为非退化线性规划问题；否则，称为退化线性规划问题。

**例**：  
写出 1 中线性规划的标准形式，以及其基、基变量、基解、基可行解和可行基。

**解**：显然，标准形式为  
 max ⁡ z = 3 x 1 + 5 x 2 + 0 x 3 + 0 x 4 + 0 x 5 s.t. \{ x 1 + x 3 = 4 , 2 x 2 + x 4 = 12 , 3 x 1 + 2 x 2 + x 5 = 18 , x j ≥ 0 ( j = 1 , 2 , … , 5 ) . \\begin\{aligned\} \\max &z = 3x\_1 + 5x\_2 + 0x\_3 + 0x\_4 + 0x\_5 \\\\ &\\text\{s.t.\} \\begin\{cases\} x\_1 + x\_3 = 4, \\\\ 2x\_2 + x\_4 = 12, \\\\ 3x\_1 + 2x\_2 + x\_5 = 18, \\\\ x\_j \\geq 0 \\qquad(j = 1, 2, \\dots, 5). \\end\{cases\} \\end\{aligned\} maxz=3x1\+5x2\+0x3\+0x4\+0x5s.t.⎩⎪⎪⎪⎨⎪⎪⎪⎧x1\+x3=4,2x2\+x4=12,3x1\+2x2\+x5=18,xj≥0(j=1,2,…,5).

由此，可写出约束方程组的系数矩阵：  
 A = \[ 1 0 1 0 0 0 2 0 1 0 3 2 0 0 1 \] \\bm\{A\} = \\begin\{bmatrix\} 1 & 0 & 1 & 0 & 0 \\\\ 0 & 2 & 0 & 1 & 0 \\\\ 3 & 2 & 0 & 0 & 1 \\\\ \\end\{bmatrix\} A=⎣⎡103022100010001⎦⎤  
矩阵  A \\bm\{A\} A 的秩不大于 3，而  
 B = ( p 3 , p 4 , p 5 ) = \[ 1 0 0 0 1 0 0 0 1 \] \\bm\{B\} = (\\bm\{p\}\_3, \\bm\{p\}\_\{4\}, \\bm\{p\}\_5) = \\begin\{bmatrix\} 1 & 0 & 0 \\\\ 0 & 1 & 0 \\\\ 0 & 0 & 1 \\\\ \\end\{bmatrix\} B=(p3,p4,p5)=⎣⎡100010001⎦⎤  
是一个  3 × 3 3 \\times 3 3×3 的满秩矩阵，故  B = ( p 3 , p 4 , p 5 ) \\bm\{B\} = (\\bm\{p\}\_3, \\bm\{p\}\_4, \\bm\{p\}\_5) B=(p3,p4,p5) 是一个基，对应的变量  x 3 x\_3 x3， x 4 x\_4 x4， x 5 x\_5 x5 是基变量， x 1 x\_1 x1， x 2 x\_2 x2 是非基变量。令  x 1 = x 2 = 0 x\_1 = x\_2 = 0 x1=x2=0，解得  x 3 = 4 x\_3 = 4 x3=4， x 4 = 12 x\_4 = 12 x4=12， x 5 = 18 x\_5 = 18 x5=18，则  x = ( 0 , 0 , 4 , 12 , 18 ) T \\bm\{x\} = (0, 0, 4, 12, 18)^\\text\{T\} x=(0,0,4,12,18)T 是一个基解。因该基解中所有变量取值为非负，故又是基可行解，对应的基  B = ( p 3 , p 4 , p 5 ) \\bm\{B\} = (\\bm\{p\}\_3, \\bm\{p\}\_4, \\bm\{p\}\_5) B=(p3,p4,p5) 是一个可行基。

# 参考 #

《运筹学》（第四版），徐玖平，胡知能 编著，第 1 章 线性规划

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70]: /images/20210923/45f6bdd002b84d3e900167ac05873573.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70 1]: /images/20210923/634ea9aca5a248dca23e915d183f1c74.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1B1cnN1ZUx1bw_size_16_color_FFFFFF_t_70 2]: /images/20210923/70fbe6541177457a998538adc0a2ca77.png