第二章 物流运筹学——线性规划

好

第二章

线性规划

线性规划问题及其数学模型 线性规划模型的求解 线性规划对偶问题与灵敏度分析 线性规划在物流管理中的应用

好

学习目标知识目标掌握线性规划的基本形式及标准形式； 掌握单纯形法计算过程； 理解对偶问题； 掌握对偶问题的求法及性质； 了解灵敏度分析。

技能目标能够结合实际情况建立线性规划的模型，并可利用单 纯形法求解。

好

第一节 线性规划问题及其数学模型问题的提出 线性规划问题的标准形式

好

问题的提出【例2-1】某企业要将产品包装成Ⅰ、Ⅱ两种规格， 需要A、B两种原材料的数量、获利情况及两种材 料数量限制见表2-1,两种规格的产品各包装多少 件可获利最多？表2-1 产品 规格 Ⅰ Ⅱ 材料限制 A 4 5 20 B 2 1 8 利润/(元/件) 12 9

好

解 设 x1 , x2 分别为Ⅰ、Ⅱ两种规格产品的包装件数， 该包装问题可用数学模型表示为：

max z = 12 x1 + 9 x2 4 x1 + 5 x2 ≤ 20 s.t. 2 x1 + x2 ≤ 8 x , x ≥ 0 1 2

好

【例 2-2】某物流公司要把若干单位的产品从两个仓库 Ai ( i = 1, 2 ) 发送到零售点 B j ( j = 1, 2, 3, 4 ) ,仓库 Ai 供应的产品数量为 ai ,零 售点 B j 所需的产品的数量为 b j 。假设供给总量和需求总量相等， 且已知从仓库 Ai 运一个单位产品往 B j 的运价为 cij 。问应如何组织 运输才能使总运费最小？

好

解

设从仓库 Ai 运往 B j 的产品数量设为 xij , i = 1, 2 ,

j = 1, 2,3, 4 ,该运输问题可用数学模型表示为

min z = ∑∑ cij xiji =1 j =1

2

4

xi1 + xi 2 + xi 3 + xi 4 = ai ,i = 1, 2 s.t. x1 j + x2 j = b j ,j = 1, 3, 2,4 2; 2,4 xij ≥ 0 ,i = 1, j = 1, 3,

好

上面两个例子的共同特征： (1)每一个问题都由一组决策变量来表示某一方案， 一般情况下这些变量的取值是非负且连续的。 (2)存在一定的约束条件，这些约束条件可以用一 组线性的等式或不等式来表示。 (3)都有一个要求达到的目标，它用决策变量的线 性函数(称为目标函数)来表示。按照具体问题的不 同，要求目标实现最小或最大。

好

线性规划定义求取一组变量，使之既满足线性约束条件， 又使具有线性表达式的目标函数取得极大值或极 小值的一类最优化问题称为线性规划问题，简称 线性规划(LP)。决策变量、约束条件和目标函 数是其三个基本要素。

好

1.线性规划问题模型的一般形式 max(min) z = c1 x1 + L + cn xn a11 x1 + L + a1n xn ≤ (= , )b1 ≥ ≥ a21 x1 + L + a2 n xn ≤ (= , )b2 s.t. …… a x + L + a x ≤ (= , )b ≥ n m1 1 mn n j 2,…,n x j ≥ 0, = 1,

好

2.紧缩形式max(min) z = c1 x1 + L + cn xn n 2,…,m ∑ aij x j ≥ (=, ≤)bi ,i = 1,

s.t. j =1 x ≥ 0 , j = 1, 2,…,n j

好

3.矩阵和向量的形式max(min) z = CX ≥ AX ≤ (= , )b s.t. X ≥0

好

线性规划问题的标准形式max z = CX AX = b s.t. X ≥0

好

【例 2-3】将下列线性规划问题化为标准形： min z = x1 + 2 x2 + 3 x3

2 x1 + x2 + x3 ≤ 9 3 x + x + 2 x ≥ 4 1 2 3 s.t. 4x1 2 x2 3 x3 = 6 x1 ≤ 0,x2 ≥ 0,3取值无约束 x

好

第二节 线性规划模型的求解图解法 单纯形法

好

满足所有约束条件的向量称为线性规划问题的可行解 所有可行解构成的集合称为可行域。 在可行域中使得目标函数值最大(或最小)的可行解， 称为线性规划问题的最优解。 最优解的全体称为最优解集合。 最优解对应的目标函数值称为最优值。