运筹学第4讲.ppt

1、运 筹 学,第四讲,知识回顾：线性规划问题：,1、可行解：满足约束条件的解称为线性规划问题的可行解，全部可行解的集合称为可行域 2、最优解：使目标函数达到最大值的可行解称为最优解。,s.t.,目标函数：,约束条件：,3、基：设A为约束方程组的mn阶系数矩阵（ 设nm），其秩为m。B是矩阵A中的一个mm阶的满秩子矩阵，称B是线性规划问题的一个基。不失一般性，设,B中的每一个列向量Pj ( j = 1 2 m) 称为基向量，与基向量pj对应的变量xj 称为基变量，否则为非基变量。,4、基解：在约束方程组中，令所有的非基变量xm+1 = xm+2 = xn =0，又因为有 ，根据克拉默规则，由m个约

2、束方程可解出m个基变量的惟一解 。将这个解加上非基变量取0的值有 ，称X为线性规划问题的基解。 5、基可行解：满足变量非负约束条件的基解称为基可行解。 6、可行基：对应于基可行解的基称为可行基。,凸集：如果集合C中任意两个点X1、X2，其连线上的所有点也都是集合C中的点，称C为凸集。 两个点X1、X2的连线可表示为（连线上任一点）：,顶点：设C是凸集， ，若X不能表示成任何 两点连线的内点，则称X为C的一个顶点。 也就是说，凸集中不成为任意两点连线上的点，称为凸集顶点。,4、三个定理 定理1 若线性规划问题存在可行解，则问题的可行域是凸集。 引理：线性规划问题的可行解X=(x1, x2,xn)

3、T 为基本可行解的充要条件是X的正分量所对应的系数列向量线性独立（无关）。 定理2：线性规划模型的基本可行解对应其可行域的顶点。 定理3：若线性规划模型有最优解，则一定存在一个基本可行解为最优解。,第一章 线性规划及单纯形法,1、确定初始基可行解 当线性规划的约束条件全部为 时,用直接观察法 否则，用人工变量法（大M法） 2、单纯形法计算步骤： 第一步：求出线性规划的初始基可行解，列出初始单纯形表 第二步：进行最优性检验 第三步：从一个基可行解转换到另一个目标函数值更大的基可行解，列出新的单纯形表 （1）确定换入基的变量：选择检验数最大所对应的变量 （2）确定换出基的变量： （3）用换入变量替

4、换基变量中的换出变量，得到一个新的基 第四步：重复第二、第三步一直到计算终止。,第一章 线性规划及单纯形法 4单纯形法的计算步骤,第一步：求出线性规划的初始基可行解，列出初始单纯形表。,cB为各基变量对应的目标函数中的系数值 检验数的计算： 将xj下面这一列数字与cB中同行的数字 相乘，再用xj上端的cj值减去上述乘积之和。,（1）化标准形，列初始单纯形表；,（2）计算检验数： j =z=cj-zj = cj- ciaij,（3）最优性判断：当所有检验数均有j 0时，则为最优解。否则迭代求新的基本可行解。,（4）迭代：换入基变量：取maxj 0 = kxk换出基变量：取min i=bi/aik

5、 aik0= l x(l)主元素： alk新单纯表：pk=单位向量,注：当所有检验数j 0时，若存在非基变量检验数为0时，则有无穷多解，否则只有唯一最优解。,例：,最优解为（0,1,1,12,0,0,0），Z = 2,第一章 线性规划及单纯形法,5-2 两阶段法：,用计算机处理数据时，只能用很大的数代替M,可能造成计算机上的错误，故多采用两阶段法。,第一阶段： 在原线性规划问题中加入人工变量，构造如下模型：,对上述模型求解（单纯形法），若人工变量为零，则W=0,说明问题存在基本可行解，可以进行第二个阶段；否则，原问题无可行解，停止运算。,第二阶段：在第一阶段的最终表中，去掉人工变量，将目标函数

6、的系数换成原问题的目标函数系数，作为第二阶段计算的初始表（用单纯形法计算）。,例：,第一阶段,此时解为（4，1，9，0，0，0，0）， 目标函数W= 0，说明存在最优解，可以进行第二阶段,第二阶段,最优解为（4，1，9，0，0），目标函数 Z = -2,线性规划小结,A,初始单纯形表,合理利用线材问题：如何下料使用材最少。 配料问题：在原料供应量的限制下如何获取最大利润。 投资问题：从投资项目中选取方案，使投资回报最大。 产品生产计划：合理利用人力、物力、财力等，使获利最大。 劳动力安排：用最少的劳动力来满足工作的需要。 运输问题：如何制定调运方案，使总运费最小。,建模,一、线性规划-,数学规

7、划的建模有许多共同点，要遵循下列原则： (1)容易理解。建立的模型不但要求建模者理解，还应当让有关人员理解。这样便于考察实际问题与模型的关系，使得到的结论能够更好地应用于解决实际问题。 (2)容易查找模型中的错误。这个原则的目的显然与(1)相关。常出现的错误有：书写错误和公式错误。 (3)容易求解。对线性规划来说，容易求解问题主要是控制问题的规模，包括决策变量的个数和约束条件的个数。这条原则的实现往往会与(1)发生矛盾，在实现时需要对两条原则进行统筹考虑。,建立线性规划模型的过程可以分为四个步骤： (1)设立决策变量； (2)明确约束条件并用决策变量的线性等式或不等式表示； (3)用决策变量的

8、线性函数表示目标，并确定是求极大（Max）还是极小（Min）； (4)根据决策变量的物理性质研究变量是否有非负性。,例：有A、B两种产品，都需要经过前、后两到化学反应过程。每种产品需要的反应时间及其可供使用的总时间如表所示。 每生产一个单位产品B的同时，会产生2个单位的副产品C，且不需外加任何费用。副产品C的一部分可以出售盈利，其余的只能加以销毁。 副产品C每卖出一个单位可获利3元，但是如果卖不出去，则每单位需销毁费用2元。预测表明，最多可售出5个单位的副产品C。 要求确定使利润最大的生产计划。,设 产品的产量为 Ax1单位，B x2单位，已售出的产品C x3 单位，销毁的产品C x4单位，则

9、,Max z=4x1+10 x2+3x32x4 st. 2x1+3x216 3x1+4x224 2x2=x3+x4 x3 5 xj0, (j=1,2,3,4),例: 泰和玩具公司,预计2001年里公司的月现金流量如表所示。负的现金流量表示流出的现金超过流入的现金。为应付它的债务，公司需要在年内提早借款。该公司可有两种借款方式：（1）可在1月份贷到所需要的一年期的长期贷款，从2001年2月份开始,每月需为这笔贷款支付1%的利息,贷款本金必须在2002年1月初归还。（2）公司还可获得短期的银行贷款，月利率为1.5%，公司需在下一个月里归还上一个月初的短期贷款本金与利息。所有的短期贷款必须在2002

10、年1月初归还。在每月末，现金余额可获得0.4%的利息。问：如何制定借款计划，可使公司在2002年1月初获得最大的现金余额？,应解决的问题: 长期贷款的数量 (L) 每月短期贷款的数量 (St) 每月月末的现金平衡（余额）(Cbt) 期间最后的现金平衡(2002年初现金余额) (Cb13) 每月所付的长期与短期的贷款利息 (I, It) 每月获得的上个月末现金余额的利息 (ICt) 月末的现金平衡（余额）公式： t月现金余额=（ t-1）月现金余额+（ t-1）月现金余额利息+ t月份的现金流+ t月份收到的贷款 - t月付长期贷款利息 - 付（t-1）月短期贷款利息 - 归还（t-1）月的短期

11、贷款-归还的长期贷款（仅对2002年1月）,1月（t=1）：Cb1=L+S1+w1 w1=1月份现金流量 Cb10 2月（t=2）：Cb2=Cb1+S2+IC2+w2S1II2 IC2=Cb1 0.4 ，I=L1，I2=S1 1.5 Cb2 0 t月：Cbt=Cbt-1+St+ICt+wtSt-1IIt (t=2,12) ICt=Cb t-1 0.4 ，I=L 1 ，It=St-1 1.5Cbt 0 2002年1月（t=13）： Cb13=Cb12+IC13LS12II13 IC13 = Cb12 0.4 ，I=L 1 ，I13=S12 1.5 objMax z=Cb13,菲克投资公司要确定未

12、来三年的投资策略。目前（时刻1）有10万元资金可供投资使用，且有A、B、C、D、E五个项目可供投资选择，各个项目有关的投资现金流量在表中给出。比如，在项目B上的投资，在时刻2需要1元的现金流出量，在时刻3时有0.5元的回报（现金流入），为了保证公司投资的多元化，要求在任何一个项目上的投资最多不得超过75,000元。没有投到项目上的资金可在资金市场上获得8的存款利息。来自投资项目上的收益可直接用于再投资，例如，在时刻2来自C项目上的现金流量1.2元可直接投资于项目B。菲克公司不能借款，因此，在任何时刻可用于投资的现金仅限于手中拥有的数额。试确定投资计划，能在时刻4时使手中的现金量最大。,资金流量

13、表,设 xij在时刻i对j项目的投资额， Fi 时刻i手中拥有的现金数额， IFi 第i时刻获得的利息,Obj.Max z=F4,St. 时刻1：x11+x13+x14F1F1=100,000 x1j75,000(j=1,3,4)时刻2：x22F2F2= F1（x11+x13+x14）（1+8）+0.5x11+1.2x13x2275,000时刻3：x35F3F3=（ F2x22）（1+8 ）+ 1.0 x11+0.5x22 x3575,000时刻4：F4=（F3x35）（1+8 ）+1.0 x22+1.9x14+1.5x3xij0,外汇交易市场日交易额常常超过100亿美元。分别在现汇市场、期货

14、市场上进行。交易的形式有现汇、现汇期权等。我们现在着眼于现汇市场的讨论。 简单地说，现汇交易就是用一种货币购买一定数量另一种货币的协议。例如，一个英国公司需要预付给一个日本供应商1.5亿日元购货款，设英镑对日元的现钞比价为154.7733 (一英镑兑换154.7733日元)，那么这个英国公司可以利用现汇交易市场以 969,159.41 (1.5亿154.7743) 英镑购买1.5亿日元。当日外汇交叉汇率样本如表中所示。 假如英国公司终止了同日本供应商的合同订单，并想把1.5亿日元兑换成英镑，日元对英镑的现钞比价为0.00645，则英国公司可用这1.5亿日元买回967,500 (=1.5亿 0.

15、00645)英镑。注意到967,500英镑低于原来的969,159.41英镑，其差额是由买卖差价引起的，代表公司的交易费用。偶然的情况也会发生市场价格脱离了一致性的现象，这时候存在着套汇的机会。所谓的“套汇”是指存在着一组这样的交易：经过一系列的交易后，手中的现钞额会大于初始的现钞额，如 1英镑马克法郎日元英镑，若最后多于1英镑，就说明有套汇的机会。 现问，表中给出的汇率是否存在这种套汇机会？试建立线性规划模型讨论该问题。,建模思路,1.确定能够“产生”套汇的货币链 2.变量的设计 xj-1美元中用来兑换第j种货币的数量; yj-换到的英镑中用于兑换第j种货币的数量; zj-换到的法郎中用于兑

16、换第j种货币的数量; uj-换到的马克中用于兑换第j种货币的数量; vj-换到的日元中用于兑换第j种货币的数量;,Obj. max z= a11x1+a21y1+a31z1+a41u1+a51v1 -美元数 st. x1+x2+x3+x4+x5=1 -美元兑其他货币； y1+y2+y3+y4+y5=a12x2 -英镑兑其他货币； z1+z2+z3+z4+z5=a13x3+a23y3 -法郎兑其他货币； u1+u2+u3+u4+u5=a14x4+a24y4+a34z4 -马克兑其他货币 v1+v2+v3+v4+v5=a15x5+a25y5+a35z5+a45u5 xj,yj,zj,uj,vj0 -日元兑其他货币,ai