线性规划模型课件

1、第一节线性修订问题和模型，一、线性修订模型从招聘总经理开始，1、学习交流PPT、泰山工厂的生产情况，泰山工厂可以生产销售两种产品，需要三种资源，知道各种产品的利益、各种资源的限量和各种产品的资源消耗系数：当前的生产现状：不生产产产品a 在现有资源的情况下，利润可以达到4280的建议是：生产a产品20，生产b产品24的可能性：9* 204 * 24=2763604 * 205 * 24=2003 * 2010 * 24=300， 3、学习交流PPT的方法，约翰使用了运筹学中的线性修正计划模型问题：如何安排生产修正计划，利润最多的步骤： 1、确定决策变量：生产a产品x1kg、b产品x2kg 2、确

2、定目标函数： maxZ=70X1 120X2 3； 确定制约条件：设备制约9X1 4X2360人力制约4X1 5X2 200产品材料制约3X1 10X2 300非负制约x10x10数学知识可知，y=ax b为直线，同理： Z=70 x1 120 x2x2=70/120 x1-Z/120也为直线，将z设为残奥计9x1 4x2 360 x1 360/9-4/9x2是直线x1=360/9-4/9x2以下的半平面。 所有半平面的交叉点被称为可执行结构域，可执行结构域内的任意点是满足所有限制条件的解，被称为可行解。 学习交流PPT，例1图示，、9080604020，020406080100 z=70 x

3、1120 x 2，6，交流PPT，最佳解： X1=20， 对应于x2=24的生产方案：生产a产品20生产b产品24的利润：学习70 * 20120 * 24，8，交流PPT，二，线性修订图解法，例2 .某工厂在修订期内安排，进行两种产品的生产，知道生产单位产品所需的设备台时和a 资源的限制如下表所示：问题：工厂应该分别生产多少单位、资源，线性修订模型：目标函数： Max z=50 x1 100 x2学习约束： s.t. x1 x2 300 2 x1 x2 400 x2 250 x1、x2、9、交流PPT， 目标函数： Max z=50 x1 100 x2约束： s.t.x1x 2300 (a

4、)2x1x 2400 (b ) x 2250 (c ) x1(d ) x 20 (d )图解法对于只有两个决策变量的线性校正像素问题在平面正交坐标系上绘制了表示线性校正像素问题的概念以下，在例1中详细说明其方法：10、学习交流PPT，分别取线性修正图像解法(续)、(1)的决策变量X1、X2，制作坐标向量的正交坐标系。 在笛卡尔坐标系中，图上的任意点的坐标表示决策变量值的定径套，示例1中的每个约束表示半平面。 学习11、交流PPT，针对每个线性修正规划解法(续)、(2)不等式(约束条件)，首先取其等式在坐标系中建立直线，确定由不等式确定的半平面。 学习交流PPT，将线性修正图解法(续)、(3)5

5、个图合并为一个图，取各制约条件的共同部分。 学习交流PPT，在线性修正图解法(续)，(4)目标函数z=50 x1 100 x2，z取某一定值时得到直线，直线上的各点具有相同的目标函数值，称为“等值线”。 平行移动等值线，移动到b点时，z在可执行区域内最大化。 a、b、c、d、e是可执行区域的顶点，对于有限个限制条件，其可执行区域的顶点也是有限的。 14、交流PPT、线性修正图解法(续)、重要结论：线性修正图有最佳解，必定可行区顶点对应最佳解的无限最佳解。假定例子1中的目标函数是max z=50x-1到50x-2，则线段BC上的所有点表示最佳解的无界解。 也就是说，加载域的范围可以扩展到无限远，

6、营销对象函数值可以是无限大或无限小。 一般来说，这表示模型存在错误，必要的约束被忽略。没有可行的解。 如果在例1的数学模型中再追加另一个制约条件4x1 3x21200，则可执行区域为空域，不存在满足制约条件的解，当然也不存在最佳解。15、交流PPT、线性修正图解法(续)、例2某公司因生产需求，a、b两种原料至少需要350吨(a、b两种材料有一定的替代性)，其中a的原料至少购买了125吨。 但是，由于a、b两种原料的规格不同，各自所需的加工时间也不同，a原料每吨需要2小时，b原料每吨需要1小时，公司需要合订600小时的加工时间。 另外，知道a原料每吨的价格是2万元，b原料每吨的价格是3万元，在满

7、足生产需求的基础上，在公司加工能力的范围内，如何购买a、b两种原料，以最低购买成本，16，学习交流PPT，线性修正计划解：目标函数： Min f=2x1 3 x2约束条件： s.t.x1x2350x1125x1600x1，x2采用图解法。 下图：q点坐标(250，100 )为最佳解。 学习17、交流PPT、三、线性规划的一般形式，企业管理的重点内容之一在于各种生产要素和产品的采购问题。 另一方面，在一定阶段，企业管理者可以“投入”的生产要素：原料、人力、设备时间有一定的限制。 在一段时间内，任何工厂的现场、工厂、机械，所有的固定资本都不变动，一盏茶的资本也是有限的。 再从流动资本来看，原料的来

8、源和库存，各种技术人员的人数和时间，在相当短期内也有一定的限度。 18、学习交流PPT，线性规划一般形式，另一方面，企业管理者“投入”生产要素时，一定要有完整的目标。 在商言商中，企业管理者的目标当然是追求最高利益和最低成本。 如何“适当”地配置受时间、空间、数量限制的“投入”生产要素，达到最佳区域，获得最佳“生产”量，获得最大利益。 以上是企业管理者必须面对的问题的两个方面。 企业管理者不仅要知道如何安排手头有限的生产要素，还要从同一安排中找到最佳安排，最低成本他的企业经营目标，达到最高利益。 19、学习交流PPT，线性修订计划的一般形式，实际上，以最低的成本追求最高的收获，本来就是合理的要

9、求，所以在任何合理的活动中，都存在着要求“最好”的问题。 学习20，交流PPT，例题3配方问题，海狸鼠饲料中的营养要求： VA每天至少700克，VB每天至少30克，VC每天正好200克。 现结合使用5种饲料，饲料成分如下表：21，学习交流PPT，例题3模型化，抓取饲料I x1kg。 饲料II x2kg； 饲料III x3kg的目标函数：最节约minZ=2x1 7x2 4x3 9x4 5x5限制：3x2x26x418x5700营养要求： x1.5x2.2x 32 x 40.5 x1.2x 32 x 40.8 x5=200使用要求x2 60、x3 50、x4 70 x2 0、x3 0、x4 0、x

10、50、22、学习交流PPT、例题4 :根据人员配置问题、医院护士24小时值班、每次8小时值班时间段的不同，所需护士的数量也不同。根据统一修订，23、学习交流PPT、例题4建模、目标函数： min Z=x1 x2 x3 x4 x5 x6约束： x1x270 x2x3x3x450 x4x5x5x630非负约束： xj 0、j=1目标函数： max(min ) Z=c1x1 c2x2 c3x3 cnxn约束条件： a 11 x1a 12 x2a 13 x3a1nxn (=) b1a 21 x1a 22 x2a 23 x3a2n xn (=) b2am1x1am2n x 20、xn0、25、学习交流P

11、PT、四、线性校正像素的标准类型、一般形式目标函数： Max (Min z=c1 x1 c2 x2 cn xn限制条件： s.t.a 11 x1a 12 x2a1n b1a 21 x1a 22 x2a2n xn (=)、b2 am1 x1 am2 x2 amn xn (=)、bm x1、x2， xn 0标准格式的目标函数： Max z=c1 x1 c2 x2 cn xn约束条件： s.t.a 11 x1a 12 x2a1nxn=b1a 21 x1a 22 x2a2nxn=b2am1x1am2amn xn=BM x 1，x2，xn 0，bi 0，26，学习交流PPT，线性可以看出线性修正画的标准

12、形式有以下4个特征点：限制于目标最大化方程式的意思决策变量并非全部为负；右端的项不是负。 对于各种非标准形式的线性校正图像问题，我们总是通过使目标函数为Min f=c1x1 c2x2 cnxn (可能)指令z的变换而得到标准形式： 学习交流PPT、线性修正图像的标准类型，1 .可以极小化目标函数的这个极小化问题具有与下一个极大化问题相同的最佳解，即Max z=- c1x1 - c2x2 - - cnxn，尽管两个这些个问题的最佳解相同， 2 .限制条件并不是等式的问题：当将限制条件设为ai1 x1 ai2 x2 ain xn bi时，引入新的变量s并且在限制的右边和左边之间的差s=bi (ai

13、1x1ai2x2a ) 此时，新的制约条件为ai1 x1 ai2 x2 ain xn s=bi，29，学习交流PPT、线性修订图的标准形，制约条件为ai1 x1 ai2 x2 ain xn bi时， 相似地，s=(ai1 x1 ai2 x2 ain xn)- bi，即s0，这时的新约束条件为ai1 x1 ai2 x2 ain xn-s=bi，30，为了学习交流PPT、线性校正图的标准并使约束从不等式变为等式而引入的变量s，不等式为“以下” 如果原始问题有一些非等式约束，则在将其转换为标准格式时，必须为每个约束引入不同的松弛变量。 3 .右端项存在负值的问题。 在标准形式中，右端项要求各成分不为

14、负。 当右端项的系数为负时，将该等式约束的两端乘以-1，得到-ai1 x1-ai2 x2- -ain xn=-bi，如bi0。 31、学习交流PPT、线性修正图像的标准类型，例如将以下的线性修正图像问题转换为标准形式minf=2x1-3x24 x3s.t.3 x 14 x2-5x 36 x1x3x1x2x3=-9 x 1、x 2。 将目标函数转换为极大化：考虑z=-f=-2x1 3x2-4x3之后的约束，有两个不等式约束，导入松弛变量x4，x5 0。 第三个约束的右端值为负，表达式的两侧将-1与云同步相乘。 学习交流PPT、线性修正像素的标准型，通过以上的变换，能够得到maxz=-2 x1x2-4x3s.t.3 x 14 x2-5x3x4=6x1x3- x5=的标准形式的线性修正像素问题的变量xj没有非负制约时，xj=xj- xj” 当然，xj的符号取决于xj和xj”的大小。学习33，交流PPT，5，修正