线性规划.ppt

1、1，线性规划模型及其应用，1节线性规划模型和数学模型2节应用示例，2，1节线性规划问题和数学模型，1.1问题毽子1.2图形1.3线性规划问题的标准格式，3，1节线性规划方法问题和数学模型，线性规划是操作研究的重要组成部分。线性规划在理论上比较成熟，在实用中的应用越来越广泛和深入。特别是电子计算机能够处理数千个限制和决策变量的线性规划问题，线性规划应用领域进一步扩大。从解决技术问题的最优化设计到产业、农业、商业、交通运输业、军事、经济计划、管理决策等都可以发挥作用。它已经是现代科学管理中的重要手段之一。解决线性规划问题的方法有多种，目前可以使用LINGO编程处理简单的线性规划问题。4，1.1问题

2、毽子，1.1问题毽子实例1一家工厂必须在计划期间计划生产、两个茄子产品、生产单位产品所需的设备台和A，B两种茄子原材料的消耗(见表1-1)。每生产2元，每生产3元。如何计划使牙齿工厂获得最多利润？、5，1.1问题毽子，数学关系说明牙齿问题，6，1.1问题毽子，获得牙齿问题的数学模型3360，这是最简单的线性规划模型。7，1.1问题毽子，例2在一条河附近有两个化工厂(见图1-1)，通过第一化工厂的河水流每天有500万立方米，两个工厂之间每天有200万立方米支流。图1-1，化工厂1日含某些有害物质的工业污水2万立方米，化工厂2日排放的工业污水1万4千立方米。化学工厂1排出的污水在流向化学工厂2之前

3、，20%可以自然净化。根据环境保护要求，河川的工业废水含量不得超过0.2%。因此，两个工厂都要处理一些工业污水。化工厂1废水处理费用为1000韩元/万立方米，化工厂2废水处理费用为800韩元/万立方米。在：满足环境要求的条件下，每个工厂要处理多少工业污水，这样就可以最大限度地减少两个工厂处理工业污水的总成本。8，1.1问题毽子，设置：化工厂1牙齿每天处理的污水量为x1万立方米；化工厂2每天处理的污水量为X20，000立方米，建模前分析和计算，9，1.1问题的毽子，得到牙齿问题的数学模型：10，1.1问题的毽子，每个线性规划问题用决策变量集表示特定方案，牙齿决策变量的值表示具体方案。通常，这些变

4、量的值不是负值，而是连续的。有各种资源和资源使用的技术数据，创造新的价值。有可以用线性等式或线性不等式组表示的可量化约束。实现可以用决策变量的线性函数(目标函数)表示的目标有要求。根据问题的要求，要求最大化或最小化目标函数。上述两个茄子问题的共同特征：11，1.1问题毽子、决策变量和各种系数之间的对应关系、12，1.1问题毽子、线性规划模型的一般形式、13，1.2度法、1.2度法图例1是二维线性规划问题，可以用图解法可视化，14，1.2度法、目标值为请参阅图1-2。(2)无限解决方案，见图1-3。(3)没有可行的解决方案。请参阅图1-4。您可以通过图形方法观察线性规划解决方案可能出现的一些茄子

5、情况。16，1.2图形，目标函数max z=2x1 4x2，图1-2无限最优解决方案(多最优解决方案)，17，1.2图形，图1例如，如果在示例1的标准中添加约束：则该问题的可执行域在空集合中：没有可执行的解决方案，没有可执行的解决方案，1.2图表，19，图1-4中没有可执行的域。1.2图表，20，1.3线性规划问题的数学模型风格，要求解决1.3 (1)问题的目标函数可以用数值指标来表示，线性函数。(2)有多种节目和相关数据。(3)要实现的目标在线性等式或不等式可以说明的约束下实现。22，2节适用实例3合理利用先载问题。现在要做100套钢架，要用一个长度分别为2.9米、2.1米、1.5米的圆钢。

6、据悉，原料长度为7.4米，如何下衣，使用的原材料最省时。23，2节应用实例：最简单的方法是从每种原材料中截取2.9米、2.1米、1.5米的圆钢，每种原材料需要使用100个原材料，共90米的原料相反，如果应用切割，可以节约原材料。下面有几个茄子制裁方案，都可以考虑采用。请参阅表1-5。表1-5，24，2节应用的例子是为了得到100套钢架，需要混合各种下料方案。按程序降低的原材料的根数为x1，方案为x2，方案为x3，方案为x4，方案为X5。根据表1-11中的方案，应用、25、2节的示例、最终计算表(3次计算)、计算中可获得最佳下限的数学模型：25、2节的应用示例、最终计算表、3次计算节目空白10个

7、；方案下的50个。也就是说，需要90种原材料，才能制造100套钢框架。具有非标准变量的检查数为零，因此存在多个最佳解决方案。26，2节应用实例4(材料问题)一家工厂需要混合三种茄子原材料C、P、H，混合三种茄子规格的产品A、B、D。已知产品的规格要求、产品单价、每天可供应的原材料数量和原材料单价见表1-6和表1-7。牙齿厂如何安排生产，使利润收入最大化？解决方案：根据产品A的C表示AC，产品A的P表示AP，等等，表1-6，27，第2节应用实例，表1-6表示：其中AC AP AH=A；BC BP BH=B (1-9)通过指定(1-8)一个(1-9)来清理。对于第28，2节的应用，表1-7表示这些

8、原材料供应数量的限制。产品A、B、D中添加的原材料C总量每天不超过100公斤，P的总量不超过100公斤，H总量不超过60公斤。表1-7，29，2节应用示例，因此约束条件，AC BC DC100 AP BP DP100 AH BH DH60在约束条件中总共有9个变量，为了计算和说明，分别标记为x1、x9。X1=AC，x2=AP，x3=ah，x4=BC，X5=BP，X6=BH，x7=DC，x8=DP，x9=dh。制造产品价钱：50(x1 x2 x3)产品A 35(x4 X5 X6)产品B 25(x7 x8 x9)产品d原材料价钱：65(x1 x4 x7)原材料C 25(x2 X5 x8)原材料p3

9、5 (x3x8)x1=100，x2=50，x3=50表示原料C为100公斤，P为50公斤，H为50公斤，构成产品A。也就是说，每天要生产A万200公斤的产品，每个要生产100公斤的原料C，50公斤的P，50公斤的H。从最终计算表中获得的总收益为z=500韩元/日。34，2节应用实例，示例5生产和库存最优化问题如果一个工厂生产5茄子产品(i=1，5)，则上半年每个产品的最大市场需求为dij(i=1，5)。J=1，6)。每个产品的单一售价为Si元，生产每个产品所需的工时为ai，单一成本为Ci元。牙齿工厂上半年每月正常生产工作时间为rj(j=1，6)，每月允许的最大加班工作时间为rj。Ci是加班的单

10、一成本。另外，每月生产的各种产品如果这个月销售不结束，可以重新考虑。库存成本为Hi(元/月)。假设1月初所有产品的库存为零，六月末每个产品的库存均为ki。目前要求制定对牙齿工厂的生产计划，在充分利用生产能力的条件下获得最大利润。35，2节应用示例：分别将xij和xij设置为牙齿工厂第一类产品J月的正常时间和加班时间内的产量。Yij是J月份I种产品的销售量，wij是第一种产品J月底的库存。根据问题的意思，可以说明：(1)每个产品的每月产量不能超过允许的生产能力，(36，第2节应用实例，(2)每个产品的每月销售量不超过市场最大需求yi jdij (i=1，5)。J=1，6) (3)月末现有量与当月

11、产量减去当月销售量的数量(4)满足每个变量的非负约束条件，Xi j0，Xi j0，yi j0，(I=1，5；J=1，6) wi j0 (I=1，5；J=1，5)，37，2节应用实例，(5)牙齿工厂上半年总利润，38，2节应用实例，例6连续投资问题一个部门在未来5年内可以考虑以下项目投资。项目A，从第一年开始，项目B，3年初需要投资，到5年年底可以收回本利的125%，但规定最大投资额不超过4万韩元。项目C，2年级初需要投资，到5年底为止可以收回本利的140%，但规定最大投资额不超过3万韩元。项目D，5年内每年年初可以购买公债，当年年末返还，利息增加6%。牙齿部门目前有10万元的资金，如何确定对牙

12、齿项目的年度投资额，使到第5年底持有的资金本息总额最大化？39，2节应用示例：(1)确定决策变量是与时间相关的持续投资问题。但是在这里，我想用线性规划方法静态处理。XiA、xiB、xiC、xiD(i=1，2，5)，分别表示在I年初对项目a、b、c和d的投资额，这些都是未确定的未知变量。根据给定条件在表1-15中列出变量。表1-15，40，2节应用实例，(2)投资额应等于手头的资金额。因为项目D每年可以投资，年末可以收回本息。因此，牙齿部门每年必须全部投入资金，如果手头有剩余的停滞资金，就会渡边杏。所以第一年：牙齿部门年初拥有100，000韩元，因为x1A x1D=100000第二年：第一年对项

13、目A的投资直到第二年年底才收回。因此，牙齿部门仅保留第二年年初项目D第一年收回的韩元和x1D(1 6%)的资金。因此，第二年的投资分配是x2A x2C x2D=1.06x1D第三年年初的资金额是项目A第一年投资和项目D第二年投资收回的本益总和x1A(1 15%)和x2D(1 6%)。因此，第三年资金为x3A x3B x3D=1.15x1A 1.06x2D第四年：与上述分析一样，x4A x4D=1.15x2A 1.06x3D第五年：x5D=1.15x3A 1.06x4D，41，41即x3B因此，牙齿目标函数最大值为z=1.15x4a 1.40x2c 1.25x3b 1.06x5d，42，2节应用

14、实例，(4)通过数学模型以上分析，可以将时间相关投资问题描述为以下线性规划模型，43，X1D=28300元第二年：44，感兴趣的读者可以进入以下网站：http:/www . ifors . ms . unimelb . edu . au/tutorial/，45。谢谢！46，感兴趣的读者可以进入以下网站：http:/www . ifors . ms . unimelb . edu . au/tutorial/，47。实例1具有a1、a2个香蕉基地，产量各不相同2个产地至3个产地的单价为表131运费表(单位：元/吨)、销售地、单位东价、产地、练习、48、A1至B1的香蕉为X11、A1至B2的香蕉为X11，A2至B3的香蕉为x23min=600 * X11 300 * x12 400 * x13 400 * x21 700 * x22 300 * x23；X11 x12 x13=60X21 x22 x23=80X11 x21=50X12 x22=50X13 x23=40，49，例2某工厂以三种茄子原料生产三种茄子产品，已知条件如表2.1.1所示，假定生产的产品供应不足，想制定总利润最大的生产计划。50，最大值=3 * x1 3 * x2 4 * x32 * x1 3 * x2=15002 * x2 4 * x3=8003 * x1 2 * x2