[军事]大学本科运筹学教程第二章线性规划1.ppt

第二章 线性规划 与单纯性法 (Lp) Linear programming 线性规划模型的三要素 一组变量 x1 , x2 , …… xn ：模型需确定的未知量 一个目标函数：使函数最大或最小就是问题的目的 一组约束条件 例2 一个连锁店公司正在计划明年的广告预算，该公司计划用1000万元在报纸、广播电台和电视上做广告。下表是他们做规划用的统计数据： 该公司的目标是使广告影响的人数最多，并满足下列条件: 至少要影响500万人口 至少要影响100万已结婚的人口 至少要影响150万收入在平均收入以上的人口 在每种媒体上做的广告要在最高和最低限制数之间 筹划：报纸？电台？电视？ 注意事项 分析问题时,利用表格,条理清楚 问题要求确定什么量的值,就设什么量为变量; 考虑变量是否应为整数 约束条件中,有≤ 、≥、或 = ，不要用错；把所有的约束条件找完 目标函数：求最大或最小 例3：某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下： 线性规划问题的一般模型 Max(min)Z = c1x1 + c2x2 + … + cnxn s.t. a11x1 + a12x2 + … + a1nxn ≤ ( =, ≥) b1 a21x1 + a22x2 + … + a2nxn ≤ ( =, ≥) b2 ︰ ︰ am1x1 + am2x2 + … + amnxn ≤ ( =, ≥) bm x1 ， x2 ， … xn ≥ 0 矩阵形式： 如将上例用表格表示如下： 例：生产计划问题 总 结 线性规划解决问题的共性：一些稀缺或有限的资源必须被分配到一些指定的生产活动中去，而这些资源的使用会伴随着费用或效益的发生 线性规划可用于合理分配这些资源，并使付出的费用最大或获得的收益最大 适宜解决的问题：产品的最优组合，生产排序，最优投资方案，人力资源分配，营养分配问题等 例3 某人有一笔资金可用于长期投资，可供选择的投资机会包括购买国库券、购买公司债券、投资房地产、购买股票或银行保值储蓄等。不同的投资方式的具体参数见表。投资者希望投资组合的平均希望收益率不低于7%，风险系数不超过4，受益的增长潜力不低于10%。问在满足上述要求的情况下，投资者该如何选择投资组合使平均年收益率最高？ 设 x j 为第j种投资方式在总投资额中的比例 MaxZ = 4x1+8x2+15x3+10x4+2.5x5+5x6+x7 s.t. 4x1+8x2+15x3+10x4+2.5x5+5x6+x7 ≥ 7 x1 + 3x2 + 8x3 + 6x4 + x5 + 2x6 ≤ 4 10x2 + 25x3 + 10x4 + 5x5 + 10x6 ≥10 x1 + x2 + x3 + x4 + x5 + x6 + x7 =1 x1 ， x2 ， … x7 ≥ 0 线性规划的图解法 一、可行解和最优解 1、可行解：满足LP模型所有s.t. 的一组变量值； 可行解集：全部可行解组成的集合； 2、最优解：使目标函数取极值（max或min）的可行解； 3、最优值：取最优解时的目标函数值。 二、两变量LP问题的图解法 满足 s.t. 9x1 + 4x2 ≤360（1）的解的空间区域 9x1 + 4x2 =360 例1（生产计划问题）的可行域图示 （1） 目标函数线图示: 目标函数为一组平均线: ·同一条线上的Z值相等