第1章线性规划及单纯形法详解.pptVIP

5.3 单纯形法中的循环问题 什么是循环？ 勃兰特规则: 小的进，小的出 5.4 L.P.的解及其在单纯形表中的体现 1.唯一的最优解 2.无穷多最优解 3.褪化的基可行解 4.无解/无有界最优解 4.2单纯形法原理 讨论的模型为： （1）确定初始基及其基可行解 对经过标准化的LP模型，总会存在一个初始可行基与其基可行解。不失一般性，记： （2）从一个可行基转到相邻的可行基 定义：两个基可行解称为相邻的，如果它们之间变换且仅变换一个基变量。 对X（0）而言有,(1)是为： 因为： 是一个基，且是一个单位阵，故其它向量总可可用这个基的线性组合来表示（注意找主元列），故有： 将(3)式乘上一个正数：θ0,得： (2)+(4)式并经过整理后有： 由(5)式可找到满足约束条件方程组： 的另一个点X(1)（还不是基可行解），即有： 其中θ0是第j个分量的值,为使x(1)是 一个可行解，还需满足非负性，故有： （6） 即下面的初等变换： 但在单纯型表中，就是做初等变换： x（1）各分量，对方称右端是： 如此，则单纯形表中又出现新的单位矩阵： 且有： 现在得到的x(1)是否是基可行解，稍后根据引理判断。 （3）最优性检验和解的判别（3.1）启发性规则 将“基可行解”x(0)和x(1)分别代入目标函数得: （3.2）最优性检验 （3.3）新基的存在性 6.应用举例 （1）资源分配问题 商场售货人员每周工作5天，连续休息2天，如何安排其作息，既能满足工作需要，又能使所需售货人员最少（讨论） 时间 所需售货人数 星期日 28 一 15 二 24 三 25 四 19 五 31 六 28 （2）下料问题 制造某种机床，需要A,B,C三种轴件，其规格与数量如下表；各类轴件都用5.5米长的同一种圆钢下料。计划生产100台机床，最少需要多少根圆钢？ 轴类 长度 每台机床需要 A 3.1 1 B 2.1 2 C 1.2 4 出材 截法 轴件 需要 1 2 3 4 5 A(3.1) 1 1 0 0 0 100 B(2.1) 1 0 2 1 0 200 C(1.2) 0 2 1 2 4 400 余料 0.3 0 0.1 1 0.7 （3）配料问题 用n种原料A1,A2,…An,配成具有m种成分B1,B2,…Bm的某种产品，规定单位产品所含Bi种成分bi;原料单价分别为cj,数量限制为dj,其所含成分aij. 要求产品产量不低于t，问如何配料，成本最低。 A1 A2 … An B1 B2 … aij bi Bm cj,dj 设为配制该产品j种原料取用xj 6.应用举例 时代服装公司生产一款时装，预测今后6个月需求量如表； 每件服装用工2h，材料费10元，售价40元； 公司1月初有4名工人，每月工作200h，月薪2000元。 公司可于月初雇佣新工人，招募费用1500元；也可解雇工人，补偿费1000元/人； 供不应求，短缺不补；但若超产，库存费5元/件.月； 试作决策，使6个月利润最大。 月 1 2 3 4 5 6 需求 500 600 300 400 500 800 K-1月 K月 K+1月 童心玩具厂下一年度的现金流（万元）如表所示，表中负号表示该月现金流出大于流入，为此该厂需借款。借款有两种方式：一是于上一年末借一年期贷款，一次得全部贷款额，从1月底起每月还息1%，于12月归还本金和最后一次利息；二是得到短期贷款，每月初获得，于月底归还，月息1.5%。当该厂有多余现金时，可短期存款，月初存入，月末取出，月息0.4%。问该厂应如何进行存贷款来操作，既能弥补可能出现的负现金流，又可使年末现金总量为最大。 月 1 2 3 4 5 6 7 8 9 10 11 12 现金流 -12 -10 -8 -10 -4 5 -7 -2 15 12 -7 45 月 现金流入 现金流出 净 现金 净 现值 1 xy x1 xyi x1 x1i NV NPV k xk xyi xk xki 12 x12 xy xyi x12 x12i K-1月 K月 K+1月 1月 12月 设k月初的净现金流为sk 各月给定净现金为dk 1月初年期贷款xy k月初月期贷款xmk 宏银公司承诺为某建设项目从2003年起的4年中每年初分别提供以下数额贷款：2003年——100万元，2004年——150万元，2005年——120万元，2006年——110万元。以上贷款资金均需于2002年底前集齐。但为了充分发挥这笔资金的作用，在满足每年贷款额情况下，可将多余资金分别用于下列投资项目： （1）于2003年初购买A种债券，期限3年，到期后本息合计为投资额的140%，但限购60万元； （2）于2003年初购买B种债券，期