中国石油大学胜利学院本科毕业设计(论文）
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
相关推荐：
loading