单纯形法解线性规划问题.doc

单纯形法解线性计划问题
金融83 周慧媛 0812178
摘要: 线性计划是运筹学中研究较早、 发展较快、 应用广泛、 方法较成熟一个关键分支,它是辅助大家进行科学管理一个数学方法.研究线性约束条件下线性目标函数极值问题数学理论和方法,英文缩写LP。自1946年G.B.Dantizig提出单纯形法以来, 它一直是求解线性计划问题最有效数学方法之一。单纯形法理论依据是: 线性计划问题可行域是 n维向量空间Rn中多面凸集,其最优值假如存在必在该凸集某顶点处达成。顶点所对应可行解称为基础可行解。经过引入一般单纯形法, 依次迭代并判定, 逐步迫近, 最终得到最优解。
关键字: 线性计划, 单纯形法, 最优值, 最优解
一、 单纯形法基础思想
任何一个单纯形法迭代算法必需处理三个问题: 1.从哪一个顶点开始？2.用一条什
么样有效路径进行出一个顶点向另一个很好顶点移动？3.何时停止该过程？
单纯形法即从一个粗解开始, 成功改善现有解, 直到所要求目标满足为止。对
于一个迭代算法, 要求一个停止计划, 以检验是否达成目标。
单纯形法计算方法: 1.找出一个初始可行基B1
2.求出对应典式及检验数向量&
3.求&k = max {&j /j=1,2,3….n}
4.若&k<=0, 停止。
伴随经济全球化不停深化, 企业面临愈加猛烈市场竞争。企业须不停提升管理水平, 增强其赢利能力, 在生产、 销售、 新产品研发等一系列过程中只有自己优势, 提升企业效率, 降低成本, 形成企业关键竞争力。过去很多企业在生产、 运输、 市场营销等方面没有利用线性计划进行合理配置, 从而增加了企业生产, 使企业利润不能达成最大化。在竞争日益猛烈今天, 假如还根据过去方法, 是难以生存, 所以就有必需利用线性计划知识对战略计划、 生产、 销售各个步骤进行优化从而降低生产成本, 提升企业效率。
在各类经济活动中, 常常碰到这么问题: 在生产条件不变情况下, 怎样经过统筹安排, 改善生产组织或计划, 合理安排人力、 物力资源, 组织生产过程, 使总经济效益最好。这么问题常常能够化成所谓“线性计划”（Linear Programming,简记为LP）问题, 在利用单纯形法去处理。
二、 单纯形法在企业中应用
案例分析: 某工厂生产甲、 乙、 丙三种产品, 多种产品每件所需原料A分别为2、 4、 2kg; 每件所需原料B分别为4、 6、 5kg; 消耗工时为6、 3、 8小时; 各产品利润分别为每件160、 180、 120元。每七天企业可用于这些产品工时为900小时, 可提供原料A、 B分别为480kg和800kg。以总利润最大为目标考虑各产品生产计划。
经过计算, 得到下列最优单纯形表:

160
180
120
0
0
0
c(B)
X(B)
RHS
x1
x2
x3
x4
x5
x6
180
x2
50
*
*
*
0
1/4
-1/6
160
x1
125
*
*
*
0
-1/8
1/4
0
x4
30
*
*
*
1
-3/4
1/6
-z
-29000
*
*
*
0
-25
-10
请解答下列问题:
（1） 写出此问题线性计划模型及其最优解、 最优基和最优基逆;
（2） 把最优单纯形表中“*”格中数字补充完整;
（3） 若产品乙利润从180变为250而其她参数均不变时, 问题最优解和最优值是什么？
解: 设每七天分别生产甲、 乙、 丙三种产品x1,x2,x3件, z表示一周企业总利润
（1） 此问题线性计划模型为:
Max z = 160x1 + 180x2 + 120x3
2x1 + 4x2 + 2x3 <= 480
4x1 + 6x2 + 5x3 <= 800
6x1 + 3x2 + 8x3 <= 900
x1、 x2、 x3 >= 0
此问题最优解为x1=125,x2 = 50, x3=0,最大利润为29000
最优基为B = 4 2 1 最优基逆 B = 0 1/4 -1/6
6 4 0 0 -1/8 1/4
3 6 0 1 -3/4 1/6
( 2 ) 用B-1左乘约束条件系数矩阵各列向量得最优表x1,x2,x3对应列向量, 并计算出待定检验数。

160
180
120
0
0
0
c(B)
X(B)
RHS
x1
x2
x3
x4
x5
x6
180
x2
50
0
1
-1/12
0
1/4
-1/6
160
x1
125
1
0
11/8
0
-1/8
1/4
0
x4
30
0
0
-5/12
1
-3/4
1/6
-z
-29000
0
0
-85
0
-25
-10
（3）当产品乙利润从180 变为250 而其它参数均不变时, 原最优表变为:

160
250
120
0
0
0
c(B)
X(B)
RHS
x1
x2
x3
x4
x5
x6
250
x2
50
0
1
-1/12
0
1/4
-1/6
160
x1
125
1
0
11/8
0
-1/8
1/4
0
x4
30
0
0
-5/12
1
-3/4
1/6
-z
-29000
0
0
-475/6
0
-25
-10
最优解改变, 接续迭代得:

160
250
120
0
0
0
c(B)
X(B)
RHS
x1
x2
x3
x4
x5
x6
250
x2
80
0
1
-1/2
1
-0.5
0
160
x1
80
1
0
2
-1.5
1
0
0
x4
180
0
0
-5/2
6
-4.5
1
-z
-32800
0
0
-75
-10
-35
0
最优解为x1=80,x2=80,x3=0 ,最大利润为32800
三、 单纯形法利用到企业中作用和意义
把单纯形法知识利用到企业中去, 能够使企业适应市场猛烈竞争, 立刻、 正确、 科学制订生产计划、 投资计划、 对资源进行合理配置。过去企业在制订计划, 调整分配方面很困难, 既要考虑生产成本, 又要考虑赢利水平, 人工测算需要很长时间, 不易做到机动灵活, 利用线性计划并配累计算机进行测算非常简便易行, 几分钟就能够拿出最优方案, 提升了企业决议科学性和可靠性。其决议理论是建立在严格理论基础之上, 利用大量基础数据, 经严格数学运算得到, 从而在使企业能够在生产各个步骤中优化配置, 提升了企业效率, 对企业是大有益处。