《运筹学基础PPT(线性规划1)》由会员分享，可在线阅读，更多相关《运筹学基础PPT(线性规划1)（23页珍藏版）》请在金锄头文库上搜索。
1、线性规划线性规划 I (Linear Programming, Part I) 应用举例应用举例 合理利用线材问题合理利用线材问题 一批长度一定的钢管，要求截出不同规格的钢管若干。 问：如何下料，既满足生产需要，又使得耗费原材料钢 管数量最少。 配料问题配料问题 若干种不同价格不同成分含量的原料，用不同的配比混 合调配出一些价格不同、规格不同的产品，在原料供应 量的限制和保证产品成分的含量的前提下，如何获取最 大利润。 应用举例应用举例 投资问题投资问题 从不同的投资项目中选出一个投资方案，使得投资的回 报最大。 产品生产计划产品生产计划 合理充分利用现有的人力、物力、财力，作出最优的产 品生
2、产计划，使得利润最大。 应用举例应用举例 劳动力安排劳动力安排 某单位由于工作需要，在不同的时段需要不同数量的劳 动力，在每个劳动力工作日工作8小时的规则下，如何 安排劳动力，才能用最少的劳动力来满足工作需要。 运输问题运输问题 一个公司有若干个生产单位与销售单位，根据各生产单 位的产量及销售单位的销量，如何制定调运方案，将产 品运到各销售单位，而总的运费最小。 LP问题的特点问题的特点 达到某些数量上的最大化或最小化 所有线性规划问题都是在一定的约束 条件下追求其目标 例例1 市场对策市场对策 某家电公司准备将一种新型电视机在A、B、C三 家商场进行销售，每一个商场的批发价和推销费 及产品的
3、利润如表所示。由于该电视机的性能良 好，各商场都纷纷争购，但公司每月的生产能力 有限，只能生产1000台，故公司规定：A商场至少 经销300台，B商场至少经销200台，C商场至少经 销100台，至多200台。公司计划在一个月内的广 告预算费为8000元，推销人员最高可用工时数为 1500。同时，公司只根据经销数进行生产，试问 公司下个月的市场对策？ 表表1 经销商场经销商场 销售利润销售利润 （元（元/台）台） 广告费广告费 （元（元/台）台） 推销工时推销工时 （小时（小时/台）台） A 50 12 2 B 80 7 3 C 70 8 4 广告方式的选择广告方式的选择 某家电公司推销一种新型
4、洗衣机，有关数据见下 表。销售部第一月的广告预算为20000元，要求至 少有8次电视商业节目，15次报纸广告。电视广告 费不得超过12000元，电台广播至少隔日有一次。 现问该公司销售部应当采用怎样的广告宣传计划， 才能取得最好的效果？ 例例2 表表2 广告方式 广告费用 (元/次) 可用最高 次数/月 期望的宣传 效果/单位 电视台a(白天,1 分钟) 500 16 50 电视台b(晚上,30钞) 1000 10 80 每日晨报/(半版) 100 24 30 星期日报/(半版) 300 4 40 广播电台/(1分钟) 80 25 15 何谓线性规划何谓线性规划 上述二例： 模型中目标函数为变
5、量的线性函数 约束条件也为变量的线性等式或不等式。 故此类模型称之为线性规划。故此类模型称之为线性规划。 线性（linear）：指量与量之间按比例、成直线的关 系，在数学上可以理解为一阶导数为常数的函数； 非线性（non-linear）：量与量之间不按比例、不成 直线的关系，一阶导数不为常数。 如果目标函数是变量的非线性函数，或者约束条件中 含有变量非线性的等式或不等式，这类数学模型称之 为非线性规划。 关于解的基本概念关于解的基本概念 LP问题的建模过程问题的建模过程 搞清楚在什么条件下，要追求什么目标。 定义决策变量。每一个问题都用一组决策变量(x1, x2, , xn)表示某一方案，这组
6、决策变量的值就代表一个 具体方案。 用决策变量的线性函数形式写出所要追求的目标，称 之为目标函数目标函数。目标函数实现最大化或最小化。 用一组决策变量的等式或不等式来表示在解决问题的 过程中所必须遵循的约束条件约束条件。 LP问题的标准形式问题的标准形式 标准形式的转化方法标准形式的转化方法 目标函数为求极小化 令z=-z，一个数的极小化等价于其相反数的极大化 约束条件的右端项bi0 将等式或者不等式两段同时乘(-1) 约束条件为不等式 引入松弛变量 引入剩余变量 松弛变量和剩余变量在目标函数里的系数均为零 取值无约束的变量 非正变量 例子例子 图解法图解法 例子例子 某公司计划制造X，Y两种
7、产品。下表显示了制造一件产 品分别占用设备A，B的台时、调试工序时间及每天可用 于这两种产品的能力、各售出一件的获利情况。问：公 司应制造两种产品各多少件，使得利润最大。 项目项目 X Y 每天可用能每天可用能 力力 设备设备A(h) 0 5 15 设备设备B(h) 6 2 24 调试工序调试工序(h) 1 1 5 利润利润(元元) 2 1 LP问题解的若干可能问题解的若干可能 LP问题解的基本性质问题解的基本性质 1.凸集：凸集： 定义：在集合K中任意取两个点X1、X2，若其连线上的所 有点也都是集合K中的点，则称K为凸集。 X1、X2，的连线可表示为： X1 +(1-) X2 (01) 数
8、学描述：对任何X1 K , X2 K , 有X1 +(1-) X2 K (01) ，则称K为凸集。(数学描述适用于高维空间) 2. 顶点顶点 定义：凸集K中满足下列条件的点X称为顶点： 如果K中不存在任何两个不同的点X1、X2，使X成为 这两个点连线上的一个点。 或： 对任何X1C，X2C，不存在： X=X1 +(1-) X2 (01)，则称X为凸集C的顶点。 LP问题解的基本性质问题解的基本性质 定理定理1. 线性规划问题的可行域是一个凸集。 连接线性规划问题任意两个可行解的线段上的点，仍是可 行解。 定理定理2. 若可行域非空有界，则线性规划问题的 最优值一定可以在可行域的某个定点上达到。 如果一个线性规划问题有最优解，则一定可以从可行域的 有限个顶点中找到。 LP问题解的基本性质问题解的基本性质 图解法的启示图解法的启示 求解线性规划问题时，解的情况有四种：唯一最优解、无穷多 最优解、无界解、无可行解 若线性规划问题的可行域存在，则可行域是一个凸集 若线性规划问题的最优解存在，则最优解或最优解之一（如果 有无穷多的话）一定是可行域的凸集的某个顶点 解题思路： 先找出凸集任一顶点，计算在顶点处的目标函数值； 比较周围相邻顶点的目标函数值是否比这个值大： 为否，则该顶点就是最优解的点（或之一） 为是，则转到比这个点的目标函数值更大的另一个顶点，重复上述 过程 LOGO
