第十章 线性规划.pptVIP

10. 1 引例 1. 问题分析 2. 模型建立 广告公司的期望 1. 问题分析 2. 模型建立 1. 问题分析 2. 模型建立 10. 2 线性规划模型 线性规划问题 线性规划的主要应用领域 线性规划的数学模型 线性规划的数学模型 线性规划模型的实用形式 线性规划模型的实用形式的矩阵表示 10. 3 有关线性规划解的概念 1.可行解: 满足全部约束条件的决策向量x(∈Rn) 2.可行域: 全部可行解构成的集合 3.最优解: 使目标函数达到最优值(最大或最小值，且有界)的可行解 4.无界解: 求极大化时目标函数在可行域中无上界，求极小化时目标函数在可行域中无下界的可行解 定理 线性规划问题如果有最优解，则最优解必是可行域的某个顶点(极点) 可行域的性质 线性规划的可行域是凸集(“凸多面体”) 线性规划的最优解在极点上 线性规划算法 单纯形法 单纯形法(simplex methods)是解决线性规划问题最常用、最有效的算法之一。 单纯形法的基本思路是：从可行域的一个顶点到相邻的另一个顶点，保证使目标函数值严格下降，直到达到最优点的一种迭代方法。 单纯形法是在实践中久经考验的算法，目前仍是一种比较好的方法。 许多线性规划软件中实现了单纯形算法。 简单线性规划的图解法 10.4 灵敏度分析 对线性规划模型 min z= cTx s.t. Ax≤b L≤x≤U 10.5 线性规划问题的MATLAB求解 线性规划问题求解的MATLAB命令为linprog 引例1的求解 引例2的求解 引例2的求解 引例2的求解程序 程序运行结果 引例3的求解 引例3的求解 引例3的求解程序 程序运行结果 c=[-400;-900;-500;-200]; A=[40,75,30,15;-300,-400,-200,-100; 40,75,0,0]; b=[800;-2000;500]; L=[3;2;5;5]; U=[inf;inf;10;10]; x=linprog(c,A,b,[],[],L,U); y=round(x) total=round(-c*x) women=round(-A(2,:)*x) y =3 3 10 10 total =10960 women = 5127 结论：白天电视、最佳时间电视、广播、杂志广告次数分别为3，3，10，10，则可以满足广告公司的要求。 在此情况下，受广告影响的总人数为10960千人；受广告影响的女顾客人数为5127千人。 min z=? cij xij s.t. x11+x12+x13+x14=60 x21+x22+x23+x24=40 x31+x32+x33+x34=60 x11+x21+x31 =30 x12+x22+x32 =50 x13+x23+x33 =40 x14+x24+x34 =40 xij≥0 (i=1,2,3;j=1,2,3,4) eye(4) eye(4) eye(4) * * x y o 3 2 4 利润（元/件） 5 4 4 原材料（kg/件） 6 3 7 劳动力（h/件） C B A 如果每天可供使用的劳动力为150h，可供生产的原材料为200kg，试制定生产计划使总利润最大，并求各种产品的日产量。 引例1 已知某工厂利用两种资源—劳动力和原材料生产A、B、C三种产品的数据如下： 设xA，xB，xC分别表示 A，B，C三种产品的日 产量，由已知数据可得 ?7xA+3xB+6xC≤150 (1) ?4xA+4xB+5xC≤200 (2) ?xA，xB，xC≥0 (3) ?z=4xA+2xB+3xC 销售所得利润 劳动力限制 原材料限制 产品日产量非负 3 2 4 利润 5 4 4 原材料(200) 6 3 7 劳动力(150) C B A 显然，满足条件(1),(2)和(3)的变量xA, xB, xC的取值可以有多种方法。而工厂的目标是在不超过所有资源限量的条件下，得到最大的利润，即使目标函数z具有最大值。因此问题变成： 求xA, xB, xC ，使得 max z=4xA+2xB+3xC s.t. 7xA+3xB+6xC≤150 4xA+4xB+5xC≤200 xA，xB，xC≥0 特点 线性性！ 引例2 某广告公司想在电视、广播和杂志上做广告，其目的是尽可能多地招揽顾客。已知市场调查的结果如下： 100 200 15 杂志 200 500 3