线性规划与单纯形法样本.doc

资料内容仅供您学习参考，如有不当或者侵权，请联系改正或者删除。
§1.1　线性规划问题及其数学模型
一、 问题的提出
在生产经营管理中, 需要经常进行计划或者规划, 虽然各行业的计划或规划千差万别, 但其共同点可归纳为: 在各项资源条件的限制下, 如何确定方案, 使预期的目标达到最优。
例1.1　某工厂在计划期内要安排生产Ⅰ、 Ⅱ两种产品, 已知生产单位产品所需的设备台时及A、 B两种原材料的消耗如下表所示:

Ⅰ
Ⅱ
资源限制
设备
1
2
8台时
原材料A
4
0
16㎏
原材料B
0
4
12㎏
利润
2
3

该工厂生产一件产品Ⅰ、 Ⅱ的利润分别为2元、 3元, 问应如何安排生产才使该工厂的获利最大?
二、 数学模型的建立
L.P问题数学模型的三要素:
1.决策变量: 一般是根据所问问题假设决策变量, 一组决策变量( ) 表示某一方案, 这一组决策变量的值就代表一个具体方案。

2.目标函数: 经过决策变量, 将要实现的目标用函数式表示出来, 常见的目标函数有两种表示式。
（1） 目标是求最大化:
（2） 目标是求最小化:

3.约束条件: 主要是对变量或目标的约束, 一般见未知量的线性等式或不等式来表示。

例1.3: 某公司经销一种产品, 它下设三个生产点, 每日产量分别为, , , 该公司把这些产品分别运往四个销售点, 各销售点每日销量分别为, 已知每吨产品从各生产点到各销售点的运价如下表所示, 问该公司应如何调运产品, 在满足各销售点需要前提下, 使总运费最少?
销量
运价

4
11
3
10

1
9
2
8

7
4
10
5
解:

三、 L.P数学模型的一般形式

st.　
上述模型的简写形式为:
st.
用向量形式表示时, 上述模型可写为:
st.
式中: ;
价值系数

用矩阵形式来表示可写为:
技术系数
工艺系数
资源系数
st.　

( 假定线性规划问题中含n个变量, 分别用表示, 在目标函数中的系数为, 称为价值系数; 的取值受m种资源的限制, 用表示i第种资源的拥有量, 用表示变量取值为1单位时所消耗或含有的第i种资源的数量, 一般称为技术系数或工艺系数)
§1.2 图解法
图解法简单直观, 能帮助我们了解L.P的基本原理。
一、 图解法基本步骤
1. 在平面上建立直角坐标系;
2. 图示全部约束条件, 找出可行域;
3. 图示目标函数和寻找最优解。
例1.4: 经过例1.1来说明图解法的具体运用
　　　　　　 ①
　　　　　　　②
s.t　　 ③
④
⑤

二、 L.P求解的几种解的情况
1. 有唯一最优解。( 如上例所示)
2. 有无穷多最优解( 多重解)
如上例中, 若将目标函数改为, 则表示目标函数中以参数z的这族平行直线与约束条件的边界线平行。当z值由小变大时, 将与线段Q2Q3重合, 则点Q2与Q3之间的可行域边界上各点均为最优点, 它们对应同一最优值。
3.无可行解
若上例中再增加一个约束条件, 时, 该问题的可行域为空集, 即该LP模型无可行解也不存在最优解。如出现这种情况表明数学模型中存在矛盾的约束条件。
4.无界解
如果全部约束条件构成的可行域是无界的, 则有可能出现最优解无界, 产生无界解的原因是由于在建立实际问题的数学模型时, 遗漏了某些必要的资源约束条件。
如下述线性规划问题:

三、 由图解法得到的启示
从LP图解法能够得出以下几点启示:
1.LP的解的情况有四种: 唯一最优解、 无穷多最优解、 无界解、 无可行解。
2.LP的可行域为凸集, 特殊情况下为无界域或空集;
3.LP若有最优解, 一定能够在其可行域的顶点上得到;
4.解题思路是: 先找出凸集的任一顶点, 计算在顶点处的目标函数值。比较周围相邻顶点的目标函数值是否比这个值大, 如果否, 则该顶点是最优解的点若最优解的点之一, 否则, 转到比这个点的目标函数值更大的另一顶点, 重复上述过程, 一起到找到使目标函数值最大的顶点为止。
图解法虽然直观、 简便, 但当变量数多于三个以上时, 它就无能为力, 只能用另外一种代数法～～单纯形法来求解。
作业:
1.用图解法求解下列线性规划问题, 并指出问题具有惟一最优解、 无穷多最优解、 无界解还是无可行解。

( 1) 　　　　
4　　　　　　　
s.t　　

(2)

s.t　　

(3)

s.t　　

(4)

s.t　　

2.美佳公司计划制造I、 II两种家电产品。已知各制造一件时分别占用的设备A,B的台时、 调试时间及调试设备和调试工序每天可用于这两种家电的能力、 各售出一件时的获利情况如表1—1所示。问该公司应制造A、 B两种家电各多少件, 使获取的利润为最大。
表1-1
项目
I
II
每天可用能力
设备A(h)
0
5
15
设备B(h)
6
2
24
调试工序(h)
1
1
5
利润( 元)
2
1

3.(仓库租用问题)捷运公司拟在下一年度的1-4月的4个月内需租用仓库堆放物资.已知各月份所需仓库面积数列于表1.仓库租借费用随合同期而定,期限越长,折扣越大,具体数字见表2.租借仓库的合同每月初都可办理,每份合同具体规定租用面积数和期限.因此该厂可根据需要,在任何一个月初办理租借合同.每次办理时可签一份,也可签若干份租用面积和租借期限不同的合同,试确定该公司签订租借合同的最优决策,目的是使所付租借费用最小.
月份
1
2
3
4
所需仓库面积(100m2)
15
10
20
12

合同租借期限
1个月
2个月
3个月
4个月
所需仓库面积(元/100m2)
2800
4500
6000
7300

§1.3　线性规划问题的标准形式
一、 标准形式
LP的数学模型有各种不同的形式, 为了便于讨论和制定统一的算法, 有必要用统一的标准形式来表示。规定LP的标准形式如下:

二、 LP一般式转化为标准形式
1.决策变量
在标准形式中要求所有决策变量, 但一般式中决策变量不一定才是大于等于0。
（1） 若
（2） 若
（3） 若
2.目标函数
（1） 若目标函数是求极大值, 则不变;
（2） 若目标函数是求极小值, 即:
因为求, 令, 即可化为
3.资源系数
标准形式中要求, 若时, 只需将等式或不等式两端同乘( -1) , 则等式右端必大于0。
4.约束条件不等式
（1） 若约束条件为”＝”, 则不变;
（2） 若约束条件为””, 则在不等式左侧增加一个非负松驰变量, 使其转化为”＝”;
（3） 若约束条件为””, 则在不等式左侧减去一个非负剩余变量( 也称松驰变量) , 使其转化为”＝”。
松驰变量或剩余变量在实际问题中分别表示未被充分利用的资源和超出的资源数, 均未转化为价值和利润, 因此, 引进模型后它们在目标函数中的系数均为0。
例1.5, 经过例1.1来说明一般形式向标准形式的转化:

s.t　　　　　　

例1.6将下列LP转化为形式: ( 让学生演算)

st.　　

　作业习题
1、 将下列线性规划问题化为标准型
(1) Max z = 3x1+ 5x2- 4x3+ 2x4
s.t. 2x1+ 6x2- x3+ 3x4 ≤ 18
x1- 3x2+ 2x3- 2x4 ≥ 13
-x1+ 4x2- 3x3- 5x4 = 9
x1, x2, x4 ≥ 0
(2) Min f = 3x1+ x2+ 4x3+ 2x4 ≤ 1
s.t. 2x1+ 3x2- x3- 2x4 ≤ -51
3x1- 2x2+ 2x3- x4 ≥ -7
2x1+ 4x2- 3x3+ 2x4 = 15
x1 , x2≥ 0, x4 ≤ 0
§1.4单纯形法原理
一、 线性规划问题的解的概念
LP　　
1.可行解: 满足上述约束条件的解, 称为LP的可行解。
2.最优解: 使目标函数达到最大值的可行解叫最优解。
3.基: 设A是约束方程组的阶系数矩阵( 设) , 则矩阵A的秩为, 若B是矩阵A中的一个阶的满秩子矩阵, 称B为LP的一个基。也就是说, 矩阵B是由m个线性独立的列向量组成的, 不失一般性地设:
　　　B中的每一个列向量称为基向量, 与基向量对应的变量称为基变量, LP中除基变量以外的变量称为非基变量。
4.基解: 在约束方程组中, 令所有非基变量, 又因有, 根据克莱姆法则, 则m个约束方程能够得出m个基变量的唯一解, 将这个解加上非基变量取0的值有:
, 称X为LP的基解。显然在基解中变量取非零值的个数不大于方程数m, 故基解的总数不超过个。
5.基可行解: 满足变量非负约束条件的基解称为基可行解。
6.可行基: 对应于基可行解的基称为可行基。
7.凸集及其顶点
凸集: 如果集合C中任意两点, 其连线上所有的点也都是集合C中的点, 则称C为凸集。
顶点: 凸集C中满足下述条件的点称为顶点, 如果C中不存在任何两个不同的点, 使X成为这两个点连线上的一个点。或对任何, 不存在则称X是凸集C的顶点。
二、 基本定理
定理1: 若线性规划问题存在可行解, 则问题的可行域是凸集。
引理: LP的可行解为基可行解的充要条件是X的正分量所对应的系数列向量是线性独立的。
定理2: LP的基可行解X对应LP可行域的顶点。
定理3: 若LP有最优解, 一定存在一个基可行解是最优解。
三、 单纯形法迭代原理
由上述定理3可知, 如果LP存在最优解, 一定有一个基可行解是最优解, 因此单纯形法迭代的基本思想是: 行找出一个基可行解, 判断其是否为最优解, 如为否, 则转换到相邻的基可行解, 并使目标函数值不断增大, 一直找到最优解为止。
四、 最优性检验与解的判定
对LP的求解结果可能出现唯一最优解、 无穷多最优解、 无界解、 和无可行解四种情况, 因此需要建立对解的差别准则。
若为一个基可行解:
（1） 若对一切, 有, 则为最优解;
（2） 若对一切, 有, 又存在某个非基变量检验数, 则线性规划有无穷多最优解;
（3） 若有一个, 而且对有, 那么该LP具有无界解;
（4） 若在最终单纯形表中, 所有, 而在其中含有某非零人工变量, 则表示无可行解。
§1.5单纯形法计算步骤
一、 单纯形表
为了书写规范和便于计算, 对单纯形法的计算设计了一种专门表格, 称为单纯形表。迭代计算中每找出一个新的基可行解时, 就重画一张单纯形表。初始基可行解的单纯形表称初始单纯形表, 含最优解的单纯形表称最终单纯形表。
单纯形表的基本结构:

…

…

…

…

…

…

1
…
0
…

…

0
…
…
…

…

。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。

0
…
1
…

…

0
…
0
…

…

二、 单纯形法计算步骤
根据上节中讲述的原理, 单纯形法的计算步骤如下:
1.将一般形式转化为标准形式;
2.从标准形式中求出初始基可行解, 建立初始单纯形表。对标准形式的LP, 在约束条件式的变量的系数矩阵中总会存在一个单位矩阵:
　　　其中: 称为基向量, 同其对应的变量称为基变量, 模型中其它变量称为非基变量。若令所有非基变量为0, 求出基变量的值, 能够得到初始其可行解, 将其数据代入单纯形表中, 能够得到初始单纯形表。
2.检验当前的基可行解是否最优: 根据解的检验, 是否是四种解中的一种, 若是则结束运算, 否则, 转入下一步。
3.从一个基可行解转换到相邻的目标函数值更大的基可行解, 列出新的单纯形表。
( 1) 确定换入的非基变量( 换入变量)
只要有检验数, 对应的变量就能够作为换入的基变量, 当有一个以上的检验数大于0时, 一般从中找出最大一个, 即, 其对应的变量作为换入的非基变量, 称为换入变量。
( 2) 确定换出变量
计算, 确定是换出的基变量, 元素决定了从一个基可行解到相邻基可行解的转移去向, 称为( 取名) 主元素。
(3)用换入变量替代换出变量, 得到新的基、 基可行解, 并相应得到新的单纯形表。
4.重复2、 3两步, 一直到计算结束为止。
例1.7用单纯形法求解LP　　

s.t　　

解:

§1.6　　单纯形法的进一步讨论
我们在前面介绍中讲到用单纯形法来求解LP时, 首选要得到一个初始基可行解, 某些LP标准化后就有一个初始基可行解, 但有一些标准化后没有初始基可行解, 必须经过给约束条件中加上人工变量来得到初始基可行解。
因为人工变量是后加入到原约束条件中的虚拟变量, 要求将她们从基变量中逐个替换出来, 基变量中不再含有非零人工变量, 这表明原问题有解, 若在最终单纯形表中, 当时, 而其中仍有某个非零人工变量, 表明原LP无解。
对加入人工变量的LP的解决方法有两种: 大M法和两阶段法。
一、 大M法
在一个LP的约束条件中加入人工变量后, 要求人工变量对目标函数取值不受影响, 为此假定人工变量在目标函数中的系数为－M( M为任意大的正数) 。这样, 目标函数要实现最大化时, 必须把人工变量从基变量换出, 否则, 目标不可能实现最大化。
例1.8: 用单纯形法求解下列LP

解:

二、 两阶段法
用大M法求解含人工变量的LP时, 用手工计算不会碰到麻烦, 但用电子计算机求解时, 对M就只能在计算机内输入一个机器最大字长的数字, 这就可能造成一种计算上的误差, 为克服这个困难, 对添加人工变量后的LP分两个阶段来计算, 称为两阶段法。
第一阶段: 不考虑原问题是否存在基可行解, 给原LP加入人工变量, 并构造仅含人工变量的目标函数Minw,然后用单纯形法求解, 若得w=0, 说明原LP存在基可行解, 可进行第二阶段计算, 否则, 停止计算。
第二阶段: 将第一阶段计算得到的最终单纯形表除去人工变量, 将目标函数行的系数换成原LP的目标函数, 作为第二阶段计算的初始表。然后按照前面的方法进行计算。
例1.9: 试用两阶段法计算例1.8
解:

三、 单纯形法计算中的几个问题:
1.目标函数极小化时解的最优性判别。
有些书中规定求目标的极小化为LP的标准形式, 这时只需以所有检验数作为表中解是否最优的标志。
2.退化:
单纯形法计算中用规则确定换出变量时, 有时存在两个以上相同的最小比例, 这样在下一次迭代中应有一个或几个基变量等于0, 这就出现退化现象。退化现象出现的原因是模型中存在多余的约束, 使多个基可行解对应同一顶点。当存在退化现象时, 就可能出现循环计算。为了避免循环计算, 1974年由勃兰特( Bland) 提出一种简便的规则:
（1） 选取中下标最小的非基变量为换入变量;
（2） 当计算出值存在两个和两个以上最小比值时, 选取下标最小的基变量为换出变量。
§1.7 应用举例
一般讲, 一个经济管理问题凡满足以下条件时, 才能建立线性规划模型:
（1） 要求解问题的目标函数能用数值指标来反映, 且为线性函数;
（2） 存在多种方案;
（3） 要求达到的目标是在一定约束条件下实现的, 这些约束条件可用线性等式或不等式来描述。
例1.下料问题
某工厂现要做100套钢架, 每套用长2.9m、 2.1m和1.5m的元钢各一根, 已知原材料长7.4m, 问应如何下料, 使用的原材料最少。
解: 最简单的做法是: 在每一根材料上截取2.9m、 2.1m和1.5m的元钢各一根组成一套, 每根原材料余下料头0.9m, 为了做100套钢架, 需用原材料100根, 有90m料头余下。
若改为套裁, 能够节约原材料, 假设有以下几种套裁方案都能够考虑采用:
方案
下料数( 根)
长度( m)
Ⅰ
Ⅱ
Ⅲ
Ⅳ
Ⅴ
2.9
1
2
0
1
0
2.1
0
0
2
2
1
1.5
3
1
2
0
3
合计
7.4
7.3
7.2
7.1
6.6
料头
0
0.1
0.2
0.3
0.8

例1.11: 配料问题: P40－1.9
例 2: 投资问题:
某部门在今后五年内考虑给下列项目投资, 已知:
项目A, 从第一年到第四年年初需要投资, 并于次年末回收本利和115%; 项目B, 第三年初需要投资, 到第五年末能回收本利125%, 但规定最大投资额不超过4万元; 项目C, 第二年初需要投资, 到第五年末能回收140本利%, 但规定最大投资额不超过3万元; 项目D, 五年内每年初可购买公债, 于当年末归还, 并加利息6%。该部门现有资金10万元, 问它应如何确定给这些项目每年的投资额, 使到第五年末拥有的资金本利总额最大?
解:

例3: 一艘货轮分前、 中、 后三个舱位, 它们的容体与最大允许载重量如下表1, 现有三种货物待运, 已知有关数据列于表2。
表一　　　　　　　　　　　　　　　

前舱
中舱
后舱
最大允许载重量( t)

3000
1500
容积( m3)
4000
5400
1500
表二
商品
数量( 件)
每件体积( m3) /件
每件重量( t/件)
运价( 元/件)
A
600
10
8
1000
B
1000
5
6
700
C
800
7
5
600
为了航运安全, 前、 中、 后舱的实际载重量大致上保持各舱最大允许载重量的比例。具体要求: 前、 后舱分别与中舱之间载重比例上偏差不超过15%, 前后舱之间不超过10%, 问该货轮应装载ABC各多少件运费收入才最大? 试建立该问题的L.P模型。