数学建模之数学模型-1：线性规划

文章目录 线性规划线性规划的基本概念线性规划的数学模型线性规划的标准模型对非标准形式标准化线性规划的典型建模：`运输问题`数学模型的建立

线性规划 线性规划的基本概念

线性规划问题可以分为两类问题： （1）如何合理地使用有限的资源以得到最大的效益。 （2）为了达到一定的目的，如何组织生产或安排相关计划以使消耗资源达到最少。 决策变量：问题中可以控制的变化的因素，通常记为： x i , i = 1 , 2 , . . . , n x_i,i=1,2,...,n xi​,i=1,2,...,n它的值可以至少在某一个范围内变化，决策变量可以分为两类：离散变量和连续变量。 目标函数：通过决策变量构造的函数来表达决策者的某种愿望。 约束条件：问题中所满足的条件。

线性规划的数学模型

此类规划问题具有以下特征： （1）用决策变量表示可控因素，变量的一组取值 ( x 1 , x 2 , . . . , x n ) (x_1,x_2,...,x_n) (x1​,x2​,...,xn​)代表一个解决方案，通常要求非负。 （2）存在一定的约束条件，可以用自变量的线性方程或者线性不等式来表示。 （3）都有一个需达成的目标，该目标是自变量的线性函数，称为目标函数，根据需要使目标函数最大化或者最小化。 其一般的模式： max ⁡ z = ∑ i = 1 n c i x i s . t . { ∑ j = 1 n a 1 j x j ⩽ b 1 ∑ j = 1 n a 2 j x j ⩽ b 2 . . . . . . ∑ j = 1 n a m j x j ⩽ b m x 1 . . . , x i . . . , x n ⩾ 0 \max z=\sum_{i=1}^n{c_ix_i} \\ s.t.\left\{ \begin{array}{c} \sum_{j=1}^n{a_{1j}x_j}\leqslant b_1\\ \sum_{j=1}^n{a_{2j}x_j}\leqslant b_2\\ ......\\ \sum_{j=1}^n{a_{mj}x_j}\leqslant b_m\\ x_1...,x_i...,x_n\geqslant 0\\ \end{array} \right. maxz=i=1∑n​ci​xi​s.t.⎩ ⎨ ⎧​∑j=1n​a1j​xj​⩽b1​∑j=1n​a2j​xj​⩽b2​......∑j=1n​amj​xj​⩽bm​x1​...,xi​...,xn​⩾0​

线性规划的标准模型

由于线性规划模型的目标函数和约束条件各有多种表现形式，为了得到一种普适的求解方法，要将其标准化：

目标函数一律是求最大值约束条件为等式约束条件右端的常数项 b i b_i bi​一律为非负值，即 b i ⩾ 0 b_i\geqslant0 bi​⩾0变量 x j x_j xj​取值一律为非负值，即 x j ⩾ 0 x_j\geqslant0 xj​⩾0 标准形式的表示方法有如下三种： max ⁡ z = ∑ i = 1 n c i x i s . t . { ∑ j = 1 n a 1 j x j ⩽ b 1 ∑ j = 1 n a 2 j x j ⩽ b 2 . . . . . . ∑ j = 1 n a m j x j ⩽ b m x 1 . . . , x i . . . , x n ⩾ 0 \max z=\sum_{i=1}^n{c_ix_i} \\ s.t.\left\{ \begin{array}{c} \sum_{j=1}^n{a_{1j}x_j}\leqslant b_1\\ \sum_{j=1}^n{a_{2j}x_j}\leqslant b_2\\ ......\\ \sum_{j=1}^n{a_{mj}x_j}\leqslant b_m\\ x_1...,x_i...,x_n\geqslant 0\\ \end{array} \right. maxz=i=1∑n​ci​xi​s.t.⎩ ⎨ ⎧​∑j=1n​a1j​xj​⩽b1​∑j=1n​a2j​xj​⩽b2​......∑j=1n​amj​xj​⩽bm​x1​...,xi​...,xn​⩾0​ max ⁡ z = ∑ i = 1 n c i x i s . t . { ∑ j = 1 n a i j x j ⩽ b i , i = 1 , . . . , m x j ⩾ 0 , j = 1 , 2 , . . . , n \max z=\sum_{i=1}^n{c_ix_i} \\ s.t.\left\{ \begin{array}{c} \sum_{j=1}^n{a_{ij}x_j}\leqslant b_i,i=1,...,m\\ x_j\geqslant 0,j=1,2,...,n\\ \end{array} \right. maxz=i=1∑n​ci​xi​s.t.{∑j=1n​aij​xj​⩽bi​,i=1,...,mxj​⩾0,j=1,2,...,n​ 3. max ⁡ z = C X s . t . { A X = b X ⩾ 0 \max z=\boldsymbol{CX} \\ s.t.\left\{ \begin{array}{c} \boldsymbol{AX}=\boldsymbol{b}\\ \boldsymbol{X}\geqslant 0\\ \end{array} \right. maxz=CXs.t.{AX=bX⩾0​ 对非标准形式标准化 目标函数的转化: 最小值的话就乘 − 1 -1 −1约束条件右端常数项化为非负值: 同乘 − 1 -1 −1,注意不等式要变号不等式约束转化为等式约束： 引入偏差变量：偏差变量恒正变量约束的转化： 如果 x j ⩽ 0 x_j\leqslant0 xj​⩽0,令 x j ′ = − x j x_{j}^{'}=-x_j xj′​=−xj​即可，显然 x j ′ ⩾ 0 x_{j}^{'}\geqslant0 xj′​⩾0 如果无约束是自由变量可以： x j x_{j} xj​= x j ′ − x j ′ ′ x_{j}^{'}-x_{j}^{''} xj′​−xj′′​ , x j ′ ⩾ 0 x_{j}^{'}\geqslant0 xj′​⩾0, x j ′ ′ ⩾ 0 x_{j}^{''}\geqslant0 xj′′​⩾0 线性规划的典型建模：运输问题

运输问题：某物资有 m m m个产地 A 1 A_1 A1​, A 2 A_2 A2​… A m A_m Am​,其产量分别为 a 1 a_1 a1​, a 2 a_2 a2​… a m a_m am​;有 n n n个销地 B 1 B_1 B1​, B 2 B_2 B2​… B m B_m Bm​,其销量分别为 b 1 b_1 b1​, b 2 b_2 b2​… b m b_m bm​;从产地 A i A_{i} Ai​到销地 B j B_{j} Bj​的单位运价为 c i j c_{ij} cij​,问怎样调运物资才能使得总运费最少？

数学模型的建立

设从 A i A_{i} Ai​到销地 B j B_{j} Bj​的运输量为 x i j x_{ij} xij​则该问题的数学模型： min ⁡ z = ∑ i = 1 m ∑ j = 1 n c i j x i j s . t . { ∑ i = 1 m x i j ⩾ b j , j = 1 , 2 , . . . , n ∑ j = 1 n x i j ⩽ a i , i = 1 , 2 , . . . , m x i j ⩾ 0 , j = 1 , 2 , . . . , n , i = 1 , 2 , . . . , m \min z=\sum_{i=1}^m{\sum_{j=1}^n{c_{ij}x_{ij}}} \\ s.t.\left\{ \begin{array}{c} \sum_{i=1}^m{x_{ij}}\geqslant b_j,j=1,2,...,n\\ \sum_{j=1}^n{x_{ij}}\leqslant a_i,i=1,2,...,m\\ x_{ij}\geqslant 0,j=1,2,...,n,i=1,2,...,m\\ \end{array} \right. minz=i=1∑m​j=1∑n​cij​xij​s.t.⎩ ⎨ ⎧​∑i=1m​xij​⩾bj​,j=1,2,...,n∑j=1n​xij​⩽ai​,i=1,2,...,mxij​⩾0,j=1,2,...,n,i=1,2,...,m​ 根据总供给量 ∑ i = 1 m a i \sum_{i=1}^{m}a_i ∑i=1m​ai​和总需求量 ∑ j = 1 n b j \sum_{j=1}^{n}b_j ∑j=1n​bj​之间的关系，可以将运输问题分为两类： （1）当 ∑ i = 1 m a i = ∑ j = 1 n b j \sum_{i=1}^{m}a_i=\sum_{j=1}^{n}b_j ∑i=1m​ai​=∑j=1n​bj​，称为产销平衡运输问题 （2）当 ∑ i = 1 m a i ≠ ∑ j = 1 n b j \sum_{i=1}^{m}a_i\ne\sum_{j=1}^{n}b_j ∑i=1m​ai​=∑j=1n​bj​,称为产销不平衡运输问题

产销平衡的运输问题数学模型建模为： min ⁡ z = ∑ i = 1 m ∑ j = 1 n c i j x i j s . t . { ∑ i = 1 m x i j = b j , j = 1 , 2 , . . . , n ∑ j = 1 n x i j = a i , i = 1 , 2 , . . . , m x i j ⩾ 0 , j = 1 , 2 , . . . , n , i = 1 , 2 , . . . , m ∑ i = 1 m a i = ∑ j = 1 n b j \min z=\sum_{i=1}^m{\sum_{j=1}^n{c_{ij}x_{ij}}} \\ s.t.\left\{ \begin{array}{c} \begin{array}{c} \sum_{i=1}^m{x_{ij}}=b_j,j=1,2,...,n\\ \sum_{j=1}^n{x_{ij}}=a_i,i=1,2,...,m\\ x_{ij}\geqslant 0,j=1,2,...,n,i=1,2,...,m\\ \end{array}\\ \sum_{i=1}^m{a_i}=\sum_{j=1}^n{b_j}\\ \end{array} \right. minz=i=1∑m​j=1∑n​cij​xij​s.t.⎩ ⎨ ⎧​∑i=1m​xij​=bj​,j=1,2,...,n∑j=1n​xij​=ai​,i=1,2,...,mxij​⩾0,j=1,2,...,n,i=1,2,...,m​∑i=1m​ai​=∑j=1n​bj​​

产销不平衡的运输问题 2.1 产大于销：构造一个假象的销售地 B n + 1 B_{n+1} Bn+1​，其需求量为总产量与总销量之差，即 b n + 1 = ∑ i = 1 m a i − ∑ j = 1 n b j b_{n+1}=\sum_{i=1}^m{a_i}-\sum_{j=1}^n{b_j} bn+1​=i=1∑m​ai​−j=1∑n​bj​ c i , n + 1 = 0 c_{i,n+1}=0 ci,n+1​=0 那么模型可改写为： min ⁡ z = ∑ i = 1 m ∑ j = 1 n + 1 c i j x i j s . t . { ∑ i = 1 m x i j = b j , j = 1 , 2 , . . . , n + 1 ∑ j = 1 n + 1 x i j = a i , i = 1 , 2 , . . . , m x i j ⩾ 0 , j = 1 , 2 , . . . , n + 1 , i = 1 , 2 , . . . , m \min z=\sum_{i=1}^m{\sum_{j=1}^{n+1}{c_{ij}x_{ij}}} \\ s.t.\left\{ \begin{array}{c} \sum_{i=1}^m{x_{ij}}=b_j,j=1,2,...,n+1\\ \sum_{j=1}^{n+1}{x_{ij}}=a_i,i=1,2,...,m\\ x_{ij}\geqslant 0,j=1,2,...,n+1,i=1,2,...,m\\ \end{array} \right. minz=i=1∑m​j=1∑n+1​cij​xij​s.t.⎩ ⎨ ⎧​∑i=1m​xij​=bj​,j=1,2,...,n+1∑j=1n+1​xij​=ai​,i=1,2,...,mxij​⩾0,j=1,2,...,n+1,i=1,2,...,m​ 2.2销大于产：构造一个假想的产地 A m + 1 A_{m+1} Am+1​，其产量为总产量与总销量之差，即 a m + 1 = ∑ j = 1 n b j − ∑ i = 1 m a i a_{m+1}=\sum_{j=1}^n{b_j}-\sum_{i=1}^m{a_i} am+1​=j=1∑n​bj​−i=1∑m​ai​ c m + 1 , j = 0 c_{m+1,j}=0 cm+1,j​=0 那么模型可改写为： min ⁡ z = ∑ i = 1 m + 1 ∑ j = 1 n c i j x i j s . t . { ∑ i = 1 m + 1 x i j = b j , j = 1 , 2 , . . . , n ∑ j = 1 n x i j = a i , i = 1 , 2 , . . . , m + 1 x i j ⩾ 0 , j = 1 , 2 , . . . , n , i = 1 , 2 , . . . , m + 1 \min z=\sum_{i=1}^{m+1}{\sum_{j=1}^{n}{c_{ij}x_{ij}}} \\ s.t.\left\{ \begin{array}{c} \sum_{i=1}^{m+1}{x_{ij}}=b_j,j=1,2,...,n\\ \sum_{j=1}^{n}{x_{ij}}=a_i,i=1,2,...,m+1\\ x_{ij}\geqslant 0,j=1,2,...,n,i=1,2,...,m+1\\ \end{array} \right. minz=i=1∑m+1​j=1∑n​cij​xij​s.t.⎩ ⎨ ⎧​∑i=1m+1​xij​=bj​,j=1,2,...,n∑j=1n​xij​=ai​,i=1,2,...,m+1xij​⩾0,j=1,2,...,n,i=1,2,...,m+1​

有转运的运输问题 实际生活中一个站点不可能只做输入输出，于是就存在了中转站。 转运问题的思路是将其转化为产销平衡问题，为此假设最大可能中转量 Q Q Q为某个大于等于总产量 ∑ i = 1 m a i \sum_{i=1}^{m}a_i ∑i=1m​ai​的数，具有以下特点： （1）产销平衡时候： Q = ∑ i = 1 m a i = ∑ j = 1 m b j Q=\sum_{i=1}^{m}a_i=\sum_{j=1}^{m}b_j Q=i=1∑m​ai​=j=1∑m​bj​ （2）纯中转站视为输入输出量为 Q Q Q的一个产地和销地 （3）兼中转站的产地 A i A_i Ai​视为输入量为 Q − a i Q-a_i Q−ai​的销地和输出量为 Q Q Q的产地 （3）兼中转站的销地 B j B_j Bj​视为输出量为 Q − b j Q-b_j Q−bj​的销地和输入量为 Q Q Q的销地