《运筹学课件op1》由会员分享，可在线阅读，更多相关《运筹学课件op1（49页珍藏版）》请在金锄头文库上搜索。
1、Operation Research运运 筹筹 学学什么是运筹学： 运用科学的方法研究管理和工程中各种决策的问题 ，为决策者提供科学的决策依据的学科。 包括线性规划、非线性规划、整数规划、目标规划 、动态规划、图和网络规划、存储论、排队论、对 策论和决策论等等。运筹学的工作步骤1. 提出和形成问题。弄清问题的目标，可能的约束、问题 的可控变量以及有关参数，搜集有关资料；2. 建立模型。把问题中可控变量、参数和目标及约束之间 的关系用一定的模型表示出来；3. 求解。用各种手段将模型求解，所得解可以是最优解、 次优解、满意解；4. 解的检验。检查求解步骤和程序有无错误，检查解是否 反映现实问题；5
2、. 向决策者提供建议，辅助解的实施。运筹学的学习要求 运用所学知识，能够建立相应的数学模型； 掌握各种模型的基本的解题方法； 正确理解和应用数学运算中各种参数的经济管 理意义。第一章 线性规划 线性规划问题及其数学模型 线性规划图解法及其几何意义 用 Excal 求解线性规划问题 线性规划问题求解的几种可能结果在生产管理和经营活动中经常提出一类问题，即 如何合理地利用有限的人、财、物等资源，得到最好 的经济效果。线性规划以数学为工具，研究在一定的人、财、 物等资源条件下，用最少的资源耗费，取得最大的 经 济效果。 1. 线性规划问题及其数学模型1. 1 资源合理利用问题【例1 】 某工厂要生产
3、门、窗两种产品，生产一扇门 需要1车间加工1小时，3车间加工3小时；生产一扇窗需要2 车间，3车间各加工2小时。而1车间每周用于这两种产品 的的时间为4小时、另两车间为12、18小时。已知每扇门 的利润为300元，每扇窗为500元。据市场调查得到，其销 路不成问题。问管理者如何安排两种产品的产量，获得利 润最大。 这个问题的决策目标是利润的最大化。线性规划问题的三个因素 决策变量待确定的未知因素 目标函数问题所追求的目标的数学描述 约束条件实现目标的限制因素车间车间门门窗每周生产时间产时间 1104 20212 33218 单单位利润润（元 ）300500分析 （1）决策变量。 - 产品的产量
4、。设x1 和x2（单位:扇）分别表示产品门、窗的产量。（2）目标函数。设 Z 表示企业利润，则有：Z = 300x1 + 500x2（元）（3）约束条件。可建立资源限制的约束条件：x1 4, 2x2 12, 3x1 + 2x2 18x1 0, x2 0归纳上述条件，可得该问题的线性规划数学模型如下：Max Z = 300x1+ 500x2 x1 42 x2 123x1 + 2x2 18x1, x2 0s.t.线性规划模型一组决策变量；一个线性目标函数；一组线性约束方程。线性规划问题的三要 素满足这三要素的问题称 为线性规划问题。1. 2 最小投资风险问题【例 2】 某公司有 100 万元的资金
5、可供投资，该公司有六个可选的投资项目。公司希望：投资风险最小，每年至 少 6.5 万元红利，最低平均增长率为 12%，最低平均信 用度为 7。请用线性规划求解该问题。投资项资项 目风险风险 （%）红红利（%）增长长率（%）信用度11842242657103109122447810512615468886（1）确定决策变量。设 xi = 项目 i 的投资额(万元） i = 1, ,6（2）目标函数。总投资风险最低，即：（3）约束条件。各项目投资总和为 100 万元每年红利至少 6.5 万元最低平均增长率 12%最低平均信用度 7非负约束线性规划模型为：1.3 运输问题的数学模型【例 3 】某地有
6、3个有色金属矿A1、A2、A3，生产同一种 金属矿石，A1矿的年产量为100万吨，A2矿为80万吨，A3矿 为50万吨。矿石全部供应4个冶炼厂，B1厂的全部需求量为 50万吨，B2厂为70万吨，B3厂为80万吨，B4厂为30万吨。总 产量恰好等于总需求量，矿石由各矿山运到冶炼厂的单位运 价已知，如下表。运价表 单单位：元/吨冶炼炼厂 矿矿山B1B2B3B4A11.520.33 A270.81.42A31.20.322.5问如何安排运输，使 各矿山的矿石运到各 冶炼厂，满足各厂的 需要，且运输费用最 小？（1）确定变量。设xij 表示第i 个矿山运到第j 个冶炼厂的 矿石量，可列表如下。运输输量
7、 （万吨） B1B2B3B4产产量 （万吨） A1x11x12x13x14100A2x21x22x23x2480 A3x31x32x33x3450 需要量（万吨）50708030230（2）目标函数。设Z表示总费用，目标函数为（3）约束条件。各矿山的运输量与产量 的平衡条件各冶炼厂的输入量与需求 量的平衡条件运输问题的一般数学模型;设某产品有 m 个生产地， 其产量分别为 ai（i=1,2, ,m)；有 n 个消费地，需要量分 别为 bj，(j=1,2, ,n), 并且产销平衡，即Cij 表示第 i 产地 到第 j 消费地的单 位产品运价。则线性规划的建模步骤：确定一组决策变量；确定一组线性约
8、束条件和一个线性目标函数（最大或最小）一般，设有n个决策变量，m个约束方程，则线性 规划问题的一般表达形式如下：线性规划问题一般表达式：目标函数约 束 条 件cj 价值系数,费用系数bi 右端常数，资源常数aij 约束方程系数，技 术系数，工艺系数可行解：满足式的解可行解域：所有可行解的集合最优解：的可行解线性规划数学模型的简写形式或矩阵形式：2 线性规划图解法及其几何意义线性规划求解法目前最常用的方法有： 图解法：利用模型中方程几何图形寻找最优解 。 单纯形法:求解线性规划的一般方法2.1 图解法只适合于两个变量，但是利用它的直观图形看问题，有助于了解和剖析线性规划的原理及过程。图解 法的重
9、点是说明线性规划的几何意义。举例说明图解法的求解过程。max Z = 4x1+ 3x2 x1 62 x2 82x1 + 3x2 18x1, x2 0s.t.在以x1, x2 为坐标轴的直角坐标系中，非负条件是指第一象限。每一个约束条件都代表一个半平面。同时满足 x1, x2 0x1 62x2 82x1 + 3x2 18必落在由这三个半 平面交成的第一象 限区域内。L1:x1=6L3：2x1+3x2=18L2:X2=4Q0Q3Q2Q1Q4x1x2目标函数Z = 4x1 + 3x2在坐标平面上， 表示以Z为参数 、-4/3 为斜率的 平行线族：x2 = -4x1 / 3 + Z / 3x1x20
10、1 2 3 4 5 6 7 8 96 5 4 3 2 1L1:x1=6L3：2x1+3x2=18L2:X2=4Q0Q3Q2Q1Q4可行解：满足约束条件的解。绿色区域中的每一个点（ 包括边界点）都是可行解。此区域是线性规划问题的解 的集合（可行解域）。位于同一直线上的点，具有 相同的目标函数，称为“等值线” 。当 Z 值由小变大时，直线 x2 = -4x1/3 + Z/3 沿其法线方向 （4, 3）向右上方移动。当移动到 Q2 时，Z 值在 可行域的边界上实现最大 化。最优解 Q2(6, 2)，Z = 32。图解法的计算步骤：（1）绘出每个约束方程的约束半平面设约束方程为画出直线若约束方程为 ，
11、则半平面在其直 线的-(a1,a2)方向。若约束方程为 ，则半平面在其直 线的(a1,a2)方向。若约束方程为 ，则半平面即为该 直线。（2）绘出可行解域 各个约束半平面相交的区域。（3）设目标函数为 作与 方向相垂 直的目标函数等值线在可行解域中移动若目标为求“max”，则目标函数等值线沿 方 向同方向移动若目标为求“min”，则目标函数等值线沿 相 反方向移动移动确定使目标函数达到最优可行解，即最优解。（4）求出最优解3. 用EXCEL求解线性规划问题一个优化模型有目标函数、决策变量、约束条件 三部分组成。回忆前面的例 1。Max Z = 300x1+ 500x2 x1 42 x2 123
12、x1 + 2x2 18x1, x2 0在 Excel 窗口输入这个模型打开 Excal 系统，输入原始数据：数据单元格输出单元格目标单元格可变单元格(E8) = C8*C12+D8*D12 (E9) = C9*C12+D9*D12 (E10) = C10*C12+D10*D12(G12) = C5*C12+D5*D12输入计算公式：模型求解： 单击 “工具 规划求解”模型求解：求解选项： 线性模型非负变量求解结果：公式拷贝：单元格的绝对地址，$C$5单元格的相对地址，C5，$C5，C$5在单元格 E5 中输入$C$5$C5C$5C5 复制到单元格 E6 为$C$5$C6C$5C6 复制到单元格
13、 F5 为$C$5$C5D$5D5 复制到单元格 F6 为$C$5$C6D$5D6例如：（可用 F4 将绝对地址转换成相对地址）运用函数功能：在输出单元格中键入计算公式时，常常用到两个函数：sumproduct() 对相等行数和相等列数的两个单元格区域中 的对应单元格分别相乘后再求和。sum() 对单元格区域中所有单元格求和。单元格命名：单位利润、可用公式、每周产量、实际使用、总利润选定命名区域点击“指定”选择名称位置定义名称：查看、更改 或删除已定义的名称。应用名称：将公式中的 单元格引用更改为名称黏贴名称：将单元格名称黏贴到电 子表格中（黏贴列表）。例2 某公司有 100 万元的资金可供投
14、资，该公司有六个可选的投资 项目。公司希望：投资风险最小，每年至少 6.5 万元红利，最低平 均增长率为 12%，最低平均信用度为 7。请用线性规划求解该问题 。4. 线性规划问题求解的几种可能结果线性规划问题具有唯一解指该规划问题有且仅有 一个既在可行域内、又使目标值达到最优的解。如Max Z = 300x1+ 500x2 x1 42 x2 123x1 + 2x2 18x1, x2 0x1x20 1 2 3 4 5 6 7 8 96 5 4 3 2 1L1:x1=6L3：2x1+3x2=18L2:X2=4Q0Q3Q2Q1Q4线性规划问题求解可能情况：除唯一解外有1) 无穷多最优解（多重解）：
15、 将上例中的目标函数变为求x1,x20x162x282x1+3x218s.t.当移动到Q2Q3线段时，Z值在 线段Q2Q3上实现最大化。线段Q2Q3上的任意一点都使Z 取得相同的最大值，这个线性 规划问题有无穷多最优解。2) 无界解 考虑下述线性规划问题：x1x201 2 3 4 5 6 7 8 96 5 4 3 2 1该问题可行域无界 ，目标函数可以增 大到无穷大可行域无界是 否一定 没有最 优解？L1L23) 无可行解 在例 1 中增加一个约束条件：x1x201 2 3 4 5 6 7 8 96 5 4 3 2 1可行域为空集，无 可行解，当然也无 最优解。唯一解无穷组解无可行解无界解线性规划的几何意义
