下部分2015本科线性规划

1、1案例1：伟恩德公司的组合zP26z两种性能极佳的新y门与木框窗z市场需求与定价调研z是否安排生产？z各生产多少为最优？第二章线性LinearProgramming雷 明OPERATIONS RESEARCH(运筹学/管理科学)光华管理学院雷 明leiming21.1.2线性问题的一般数学模型1.相关概念（1）决策变量：（2）目标函数：（3）约束条件： 模型结构的三要素。1.1一般线性问题及数学模型1 1 1 问题的提出例：某企业计划生产甲、乙两种 ，该两种 均需经A、B、C、D四种不同设备上 ，按工艺资料规定，在各种不同设备上的 时间及设备 能力、 利润如表中所示。问:如何安排 的生产计划,

2、才能使企业获利最大?设 备 ABCD利润甲乙2212400423能力1281612生产条件生产能力、所需、利润：4hr/wk12hr/wk18hr/wk工厂1工厂2工厂31hr3hr2hr2hr门窗利润：300/unit利润：500/unit3例1：某工厂在生产过程中需要使用浓度为80%的硫酸100 吨，而市面上只有浓度为30%，45%，73%，85%，92%的硫酸出售， 每吨的价格分别为400、700、1400、1900和2500元。 问：采用怎样的方案，才能使所需总费用最小？1.1.3 简单线性模型的建立步骤：（1） 分析问题：（2） 具体构造模型：2.线性模型的一般要求（1）变量：（2）

3、目标函数：（3）约束条件：4例4：有A、B两种，都需要经过前、后两到化学反应过程。每种产品需要的反应时间及其可供使用的总时间如表示。每生产一个B的同时，会产生2个的副C，且不需外加任何费用。副C的一部分可以出售，其余的只能加以销毁。副C每卖出一个可获利3元，但是如果卖不出去，则每需销毁费用2元。表明，最多可售出5个的副C。要求确定使利润最大的生产计划。过程AB可利用时间前道过程后道过程23341624利润410例3：一家昼夜服务的饭店，24小时中需要的服务员数如下表所示。每个服务员每天连续工作8小时，且在时段开始时上班。问： 最少需要多少名服务员？试建立该问题的线性模型。起迄时 间服务员 人

4、数2- - - - 6 时6- - - 10 时10 - - 1 4 时14 - - 1 8 时18 - - 2 2 时22 - - - 2 时4810 712 4例2：设有下面四个投资机会：甲：在三年内，投资人应在每年年初投资，每年每元投资可获利0 2元，每年取息后可重新将本息用于投资。乙：在三年内，投资人应在第一年年初投资，每两年每元投资可获利0 5元，两年后取息，取息后可重新将本息用于投资。这种投资最多不得超过20,000元。丙：在三年内，投资人应在第二年年初投资，两年后每元投资可获利0 6元。这种投资最多不得超过15,000元。丁：在三年内，投资人应在第三年年初投资，一年后每元投资可获

5、利0 4元。这种投资最多不得超过10,000元。假定在这三年为一期的投资中，每期的开始有30,000元资金可供使用，问：采取怎样的投资计划，才能在第三年年底获得最大 ？5（3） 矩阵: max z=CXs.t. AXbX0n（4） 向量: max z=åcjxjj=1ns.t å pjxjb （i=1,2,m）j=1xj0（j=1,2,n)n(2) 和式： max z=å cjxjj=1ns.t.å aijxjbi （i=1,2,m)j=1xj 0（j=1,2,n)其中：cj表示目标函数系数aij表示约束条件系数bi表示约束右端项3 .线性问题的一般表示

6、方法（1）一般式：max z=c1x1+c2x2+cnxns.t.a11x1+a12x2+a1nxnb1 a21x1+a22x2+a2nxnb2 am1x1+am2x2+amnxnbm x1 ,x2, ,xn0s.t.-subject to6例：将下述LP模型标准化：obj.Min z=2x1- x2+3x3 st.x1+2 x2+4x3 £ 63x1- 2x2+ x3 = 42x1- x2 - 3x3 ³5 x1 ³ 0, x3 £ 0LP的标准化：（1）变量：（2） 目标函数：（3） 约束方程：；（4） 约束右端项：4. 线性模型的标准形式（1）变量

7、：（2） 目标函数：（3） 约束条件：（4） 约束右端项： 非标准形式情况有变量：目标函数：约束条件约束右端项：7各解之间的关系：最优解（如果存在）解集·可行解基解不可行解基可行解（4）基：（5） 基变量：（6） 非基变量：（7） 基本解（基解）：（8） 基本可行解（基可行解）：（9） 可行基：1.1.4线性问题解的有关概念设模型nmax z=åcjxjj 1ns t åaijxj=bi （i=1,2,m)j 1xj0（j=1,2,n)（1） 可行解：（2） 可行域：（3） 最优解：8唯一解无穷多解AA=B解无可行解x2642(4,2)zmax02468x1Z=6

8、Z=01.2 线性问题的图解方法* 利用作图方法求解。例：max z=2x1+3x2s.t 2x1+2x2£12x1+2x2£ 84x1£164x2 £12x1³0, x2³091.4.2 单纯形法计算：Cj 2300iCB XB bx1x2x3x40 x330 x44111012013/1=34/2= 2cj - zj23000 x313 x221/201-1/21/2101/224cj - zj1/200-3/22 x123 x21102-101-11cj - zj00-1-11.4 单纯形法的计算及程序求解例： max z=2x1+3x2s t x1+x2+x3=3x1+2x2+x4=4 xj³0, (j=1,2,3,4)1.3 单纯形法的基本原理（Simplex Method）1.3.1 两个概念：（1）凸集：对于集合C中任意两点连线上的点，若也在C内， 则称C为凸集。（2）顶点：凸集中不成为任意两点连线上的点，称为凸集顶点。1.3.2 三个基本定理：定理一：若线性LP模型存在可行解，则可行域为凸集。定理二：LP模型的基本可