线性规划模型

1、第1节线性规划问题和模型，第1节线性规划模型从招聘总经理谈，第2节泰山工厂生产情况，泰山工厂可以生产两种产品，需要三种资源，已知每种产品的收益，每种资源的限制和每种产品的资源消耗系数如下表所示。目前生产现状：产品a不生产，生产产品b每日30，利润3600，3，招聘总经理！约翰：我申请！在现有资源情况下，可以实现4280的利益！案例为a产品20生产，b产品24生产的可能性：9 * 20 4 * 24=276360 4 * 20 5 * 24=200 3 * 20 10 * 24=300，4，如何达成？John使用运营研究的线性编程模型问题：如何安排生产计划以获得最多收益？步骤：1，确定决策变量：

2、a产品x1kg，B生产设置，B产品x2kg 2，确定目标功能：maxZ=70X1 120X2 3，确定约束条件：设备约束条件9X1 4x 2360人员约束条件4X1 5X2y=ax b是直线。同样，Z=70 x1 120 x2x2=70/120 x1-Z/120是一条直线，它是参数的等值线族。9x1 4x2 360 x1 360/9-4/9x2是线x1=360/9-4/9x2下的半平面。所有半平面相交称为可执行域，在可执行域中的任意位置满足所有约束条件的解决方案称为可执行解决方案。6，示例1图标，90 80 60 40 20，0 20 40 60 80 100，x1，x2，9x1 4x2 、9

3、、2、线性编程方法、示例2。工厂计划期间，生产、两种产品，生产单位产品所需的设备站和a、b两种原材料的消耗，资源的限制，下表：问题：工厂必须分别生产多少单位、产品，工厂获利最高？线性编程模型：目标函数：Max z=50 x1 100 x2约束：s . t . x1x 23002 x2400 x2250 x1，x2 0，10，示例1。目标函数：Max z=50 x1 100 x2约束：s . t . x1x 2300(a)2 x12400(b)X2250(c)x10(c)以下是范例1的详细说明，其分别使用11、线性程式设计方法(续)、(1)决定变数X1、X2设定座标向量的直角座标系统。直角坐标系

4、中任意点的坐标表示确定变量的一组值，示例1中的每个约束条件表示半平面。12，线性编程方法(继续)，(2)对于每个不等式(约束)，首先将该方程在坐标系中拉直，然后确定不等式确定的半平面。13，线性编程方法(继续)，(3)将五个图形合并为一个图形，以聚合每个约束的公共部分，如图2-1所示。14，线性编程方法(续)，(4)目标函数z=50 x1 100 x2，z获取固定值时得到直线。直线上的每个点都具有相同的目标函数值，称为“轮廓”。平行移动等值线，移动到b点时z在可行域内最大化。a、b、c、d、e是可执行域的顶点，受限制约束的可执行域的顶点也受到限制。15，线性规划方法(续)，重要结论：如果线性规

5、划具有最优解，则必须存在与最优解相对应的可行域的顶点。无限多个最优解。如果将示例1中的目标函数更改为max z=50 x1 50 x2，则线段BC上的所有点都表示最佳解决方案。无限解决方案。行字段的范围可以无限扩展，目标函数值可以无限扩展或无限扩展。通常，这表示模型中存在错误，并忽略某些必需的约束条件；没有可行的解决方案。如果在示例1的数学模型中再添加一个约束条件4x1 3x21200，则可执行域为空域，没有满足约束条件的解决方案，并且没有最佳解决方案。16，线性编程方式(续)，例2有些公司因生产要求，总a，b两种原料至少有350吨(a，b两种材料具有一定的替代性)，其中，a原料至少购买125

6、吨。但是因为a，b两种原料的规格不同，所以需要的加工时间也不同。加工1吨a原料2小时，加工1吨b原料1小时，公司总加工时间为600小时。我还知道1吨a原料的价格为2万元，1吨b原料的价格为3万元，为了满足生产需求，如何在公司加工能力范围内购买a，b两种原料，使购置成本最低？17，线性编程方法(续)，解决方案：目标函数：Min f=2x1 3 x2约束：s . t . x1x 2350 x1122 x600 x1，x2 0使用图形方法下图：qpoint坐标(250，100)是最佳解决方案。18，3，线性计划一般形式的业务管理的核心内容之一是各种生产要素和产品的部署问题。另一方面，在固定阶段，企业

7、管理者可以“投入”的生产要素原材料、人员、设备时间是有限的。任何工厂、工厂、机器、所有固定资本在一定时间内都不变，再坚固的资本也是有限度的。再从流动资本来看，原材料的来源和库存，各种技工的数量和时间在很大程度上短期也是有限的。19，与一般形式的线性编程不同，业务管理员“投入”生产元素时必须有完美的目标。企业经营者的目标当然是求得最高收益和最低成本。受时间、空间、数量限制的“投入”生产要素，如何“适当”分配，达到最佳领域，获得最佳“产出”量，获得最大利益。这就是企业管理者要面对的一个问题的两个方面。企业管理者不仅要了解如何配置有限的生产要素，还要在多个供应中找到最佳布局，实现自己的业务目标最低成

8、本、最高利益。20、线性规划的一般形式，实际上，以最低的成本追求最佳收获的原始合理要求，因此，在任何合理的活动中，都有寻找“最佳”问题的存在。21、问题333配方问题，海狸饲料营养要求：VA每天至少700克，VB每天至少30克，VC每天确切200克。现有5种饲料，配合使用，饲料成分如下：22，案例3建模，设置收集饲料I x1kg饲料II x2kg饲料III x3kg.目标函数：最经济实惠的minZ=2x1 7x2 4x3 9x4 5x5约束条件：3x 2 x3 6x 4 18x 5700营养要求：x1 0.5x 2 0.2x 3 2x 4 0.5x 530.5x 1 x2 0.2x 3 2x

9、4 0.8x 5=每个时期需要的护士数量各不相同。统计信息：24，示例4建模，目标函数：min Z=x1 x2 x3 x4 X5 X6约束：x1x 270x 2 x360x 3 x450x 4 X520x5x 630以外的.6，25，摘要：线性规划的一般模式，目标函数：max (min) z=c 1xn约束条件：a11a12x2 a13x3.a1 nxn；(=)B1 a21x 1 a22x 2 a23x 3.a2x80n；(=) B2.am1x1 am2x2 am3x3.amn xn(=)bn非负约束：x1 0，x2 0，xn 0，26，4，线性编程的标准格式，通用格式

10、目标函数：max (min) z=xn约束条件：s.t.a11x1a12x2.a1n xn；(=，B1 a21x1 a22x2.a2n；(=，) B2.am1x1am2x2.amn xn；(=，)BM x1，x2，Xn 0标准格式目标函数：max z=xn约束条件：s.t.a11a12x2.a1n xn=B1 a21 x1 a22x2.a2n xn=B2.am1x1 am2x 2 amn xn=BM x1、x 2、xn 0、bi 0，27，您可以看到线性编程的标准形式，线性编程的标准形式有四个特点：实现目标最大化；约束是方程式。决定变量不是负数。右端不

11、是负值。对于各种非标准形式的线性编程问题，始终采用标准格式：28，线性编程的标准，1 .最小化目标函数的问题：目标函数min f=c 1x1c2x2.如果设置为cnxn(可能)，则设置z=-f会导致最小化问题与以下最大化问题具有相同的最佳解决方案：也就是说，maxz=-c 1x1-c2x2-.需要注意的是，-cnxn对上述两个问题的最优解是相同的，但最优解的目标函数值不同于min f=-max z，29，一个名为线性编程标准的单个符号。2、约束不是等式问题。将约束设置为ai1 x1ai2x2.ainxnbi是约束右边和左边的差s=bi(ai1 x1 ai2x 2.ainxn)也可以导入非负约束

12、，即具有s0的新变量s。此时，新约束为ai1 x1ai2x2.ainxn s=bi，30，成为线性配置的标准，约束为ai1 x1ai2x2.ainxn bi时s=(ai1 x1ai2x2.ainxn)-bi显然在s中也有非负约束。也就是说，当s0时，新的约束条件为ai1 x1 ai2x2.ainxn-s=bi，31，成为线性编程的标准，为使约束不等式而引入的变量s在不等式“小于或等于”时称为“松弛变量”。如果不等式“大于或等于”，则称为“剩馀变量”。如果原始问题中存在多个等式约束，则将它们转换为标准形式时，必须为每个约束引入不同的松弛变量。3 .右端有负值的问题：在标准中，右端的项目必须分别是

13、非负元件。右端系数为负值(例如，bi 40将X2从0到8599；x1=0，x2=min (30/2，60/2，24/2)=12x2输入基准变量，X5输出基准变量。44，B2=(P3 P4 P2)，45， 1/2，替代，-，-，所以x1=X5=0 x (2)=(，(3)选取的X1为0，X5=0，X1=min(6/1，36/3，1)=6 X1输入基准，X3输出基准。47，B3=(P1 P4 P2)，因此x3=X5=0 x (3)=(6，12，0，18，0) t z (3)=840，48，49，B4=(P1 P5 P2)，因此x3=x4=0 x (4)=(15，15/2，0，0，9) t z (4)=975.pm)=I，54，XJ=0 (j=m 1，n)为55，1.5.2单纯形方法原理，56，此时b=(p1p2.pm)，相应的基本可能解决方案为，57，