线性规划模型的应用与灵敏度分析

中国石油大学胜利学院本科毕业设计(论文）

am1x1+am2x2+am3x3+????amnxn?bm (1-6)

x1,x2,x3???xn?0

其简缩形式为

MinZ?c1x1?c2x2?c3x3?...?cnxn

?axijj?1nj?bi

xj?0,j?1,2,3??????,n

模型的简缩形式可用向量表示

MaxZ?CX

C=(c1,c2,??????cn)

?n??pjxj?b ?j?1?x?0?j

?x1????x2?X??????????x??n??a1j???a?2j?Pj??????????a??mj??b1????b2?b??????????bm??? 例1 生产安排模型，某工厂生产I、II两种产品，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如表所示。

设备 原材料A 原材料B

I 1 4 0

II 2 0 4

资源总量 8/台时 16/千克 12/千克

该工厂生产一单位产品I可获利2元，生产产品II可获利3元，问如何安排生产获利最大？ 解：

本问题是目标最大化问题：

(1)决策变量，设x1, x2为产品I、II的生产数量；

4

中国石油大学胜利学院本科毕业设计(论文）

(2)目标函数，2x1+3x2； (3)约束条件，

设备限制： x1+2x2 ≤ 8 原材料A限制： 4x1 ≤ 16 原材料B限制： 4x2 ≤ 12 基本要求：x1?0 ， x2?0

该模型记为如下形式 maxZ=2x1+3x2

s.t.

x1+2x2 ≤ 8

4x1 ≤ 16 4x2 ≤ 12

x1 ，x2 ?0

其中max表示本问题是最大值问题（用min表示最小值问题）， s.t.(subject to的缩写)表示约束条件。这就是一个线性规划模型[5]。 4.4线性规划的性质

定理1 线性规划问题的可行解X是基可行解的充要条件是X的非零分量对应的系数矩阵A的列向量线性无关[6]。

定理2 若一个线性规划问题有可行解，则它必有基本可行解[7]。

定理3 若可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点达到最优。

5

中国石油大学胜利学院本科毕业设计(论文）

第二章 求解线性规划的方法

1. 图解法

图解法是求解线性规划模型的一种重要方法，线性规划中一些重要的性质、概念和求解思想都来源于此。当只有两个决策变量时，可以用图解法求解。它具有简单直观的特点。为了给后面的线性问题的基本理论提供较直观的几何说明，先介绍线性规划问题的图解法[8]。

图解法的求解步骤如下：

第一步，根据约束画出可行域，先以决策变量为坐标，建立直角坐标系，再根据 各约束条件，作出可行域。

第二步，作出一条目标函数等值线，并确定增值方法。

第三步，沿等值线的法线方向值增大方向移动，从而找到最大值。 图解法得出线性规划的几种情况：

表2-1 解旳几种情况

解旳几种情况 唯一解

约束条件图形特点 一般围成有限区域，最优值只在一个顶点达到

方程特点

无穷多解 在围成的的区域边界上，至少有两个顶点处达到

优解

目标和某一约束方程成

比例

无可行解（无解） 无界解(无解）

围不成区域 围成无界区域，且无有限

最优解

有矛盾方程 缺少一必要条件的方程

例：Min Z=10x1+20x2

s..t x1?x2?10

6

中国石油大学胜利学院本科毕业设计(论文）

3x1?x2?15x1?6x2?15 x1?0,x2?0

ZA?300 ZB?175 ZC?110 ZD?150

2. 单纯形法

单纯形法是美国数学家G.B.Dantzig于1947年首先提出的。它的理论根据是：线性规划问题的可行域是n维向量空间nR中的多面凸集，其最优值如果存在必在该凸集的某顶点处达到[9]。它的原理涉及到较多的数学理论上的推导和证明，我们在此仅介绍这种方法的具体操作步骤及每一步的经济上的含义。为更好地说明问题，我们仍结合实例介绍这种方法。 单纯形法（simplex methods），求解线性规划的通用方法。 2.1单纯形法的基本思路

单纯形法的基本思路是：根据线性规划问题的标准型，从可行域中某个基本可行 解（一个顶点）开始，转换到另一个基本可行解（顶点），并且当目标函数达到最大值时，问题就得到了解决，其基本思路的框架图如下图2-1。

7