常见线性规划模型总结

线性规划模型研究

摘要：探讨线性规划在生活中的应用。方法：了解线性规划法及其特点；分析生活中某些问题适合利用线性规划求解的缘由；求解出所需值,同时观察其现实意义。结果：由于生活中很多关于利益最大化、成本最小化的问题，所以线性规划在生活中应用很广泛。而且线性规划求解方法多样；求出的结果能很好反映现实问题。结论：线性规划模型在生活中应用广泛。 关键词：线性规划；生活问题；求解相关值

Linear programming model

Abstract: discuss the application of linear programming in life. Method: to investigate the linear programming method and its characteristics; Analysis of some problems in the life is suitable for using the linear programming to solve the reason; Solving the required value and observe its realistic significance.

简单的线性规划常见题型

第Ⅰ类 求线性目标函数的最值(z?ax?by截距型)

?x?4y??3?例1.设x,y满足约束条件?3x?5y?25，求z?5x?2y的最值

?x?1?解：可行域是如图所示中?ABC的区域，得A(5,2),B(1,1),C(1,

22) 5作出直线L0：5x+10y=0，再将直线L0平移, 当L经过点B时，y轴截距最小，即z达到最小值，得zmin?7. 当L经过点A时，y轴截距最大，即z达到最大值，得zmax?29,所以最大值是29，最小值是7

?x?y≥0，?小试牛刀:1、若x，y满足约束条件?x?y?3≥0，则z?2x?y的最大值为

?0≤x≤3，??x?y??1,?2、设变量x,y满足约束条件?x?y?1,则目标函数z?4x?y的最大值

?3x?y?3,?

?y?x?3、设变量x、y满足约束条件?x?y?2，则目标函数z?2x?y的最小值为

?y?3x?6??2x?y?4,?4、设x,y满足?x?y?1,则z?x?y的最值为________w.w

?x?2y?2,?第Ⅱ类 求可行域的面积

关键是准确画出可行域，根据其形状来计算面积，基本

线性规划常见题型及解法

由已知条件写出约束条件，并作出可行域，进而通过平移直线在可行域内求线性目标函数的最优解是最常见的题型，除此之外，还有以下几种常见题型。

一、约束条件设计参数形式，考查目标函数最值范围问题。

?x?0例、在约束条件?下，当3?s?5时，目标函数 ?y?0??y?x?s??y?2x?4z?3x?2y的最大值的变化范围是（）

A.[6,15] B. [7,15] C. [6,8] D. [7,8] 解析：画出可行域如图3所示,当3?s?4时, 目标函数

z?3x?2y在B(4?s,2s?4)处取得最大值, 即zmax?3(4?s)?2(2s?4)?s?4?[7,8);当4?s?5时, 目标函数 z?3x?2yC

zmaxE(0,处取得最大值,即

?3?0?2?4?8,故z?[7,8],从而选D;

在点

点评：本题设计有新意，作出可行域，寻求最优解条件，然后转化为目标函数Z关于S的函 关系是求解的关键。

二、已知最优解成立条件，探求目标函数参数范围问题。

?1?x?y?4。若目标函数

??2?x?y?2a?0）仅在点(3,1处)取得最大值，则a的取值范围解析：如图5作出可行域，由z?ax?y?y??ax?z其

数学建模

第七章7.2

数学规划模型

7.1 奶制品的生产与销售自来水输送与货机装运

7.37.4 7.5

汽车生产与原油采购接力队选拔和选课策略 饮料厂的生产与检修

7.6 钢管和易拉罐下料y

数学建模

数学规划模型实际问题中 的优化模型 x~决策变量

Min(或Max) z f ( x), x ( x1 , x n ) s.t. g i ( x) 0, i 1,2, mf(x)~目标函数

T

gi(x) 0~约束条件 数 学 规 划 线性规划 非线性规划 整数规划

决策变量个数n和 多元函数 约束条件个数m较大 条件极值 最优解在可行域 的边界上取得

重点在模型的建立和结果的分析

数学建模

4.1 奶制品的生产与销售企业生产计划 空间层次

工厂级：根据外部需求和内部设备、人力、原料等 条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费 用参数等，以最小成本为目标制订生产批量计划。 时间层次 若短时间内外部需求和内部资源等不随时间变化，可 制订单阶段生产计划，否则应制订多阶段生产计划。 本节课题

数学建模

例1 加工奶制品的生产计划1桶 牛奶 或 12小时 8小时 3公斤A1 获利24元/公斤

4公斤A2

获利16元/公斤

每天：

数学建模

第七章7.2

数学规划模型

7.1 奶制品的生产与销售自来水输送与货机装运

7.37.4 7.5

汽车生产与原油采购接力队选拔和选课策略 饮料厂的生产与检修

7.6 钢管和易拉罐下料y

数学建模

数学规划模型实际问题中 的优化模型 x~决策变量

Min(或Max) z f ( x), x ( x1 , x n ) s.t. g i ( x) 0, i 1,2, mf(x)~目标函数

T

gi(x) 0~约束条件 数 学 规 划 线性规划 非线性规划 整数规划

决策变量个数n和 多元函数 约束条件个数m较大 条件极值 最优解在可行域 的边界上取得

重点在模型的建立和结果的分析

数学建模

4.1 奶制品的生产与销售企业生产计划 空间层次

工厂级：根据外部需求和内部设备、人力、原料等 条件，以最大利润为目标制订产品生产计划；车间级：根据生产计划、工艺流程、资源约束及费 用参数等，以最小成本为目标制订生产批量计划。 时间层次 若短时间内外部需求和内部资源等不随时间变化，可 制订单阶段生产计划，否则应制订多阶段生产计划。 本节课题

数学建模

例1 加工奶制品的生产计划1桶 牛奶 或 12小时 8小时 3公斤A1 获利24元/公斤

4公斤A2

获利16元/公斤

每天：

第一章 线性规划模型

第一章 线性规划模型

线性规划（Linear Programming）是数学规划的一个重要组成部分，是最优化与运筹学理论中的一个重要分支和常用的方法，是最优化理论的基础性内容。

第一节 线性规划问题及其数学模型

一、问题的提出

在生产管理和经营活动中经常提出一类问题，即如何利用有限的人力、物力、财力等资源，以便得到最好的经济效果。

例1 生产计划问题

某工厂在计划期内要安排生产Ⅰ、Ⅱ的两种产品，已知生产单位产品所需的设备台时，A、B两种原材料的消耗以及每件产品可获得的利润如下表所示。问应如何安排生产计划使该工厂获利最多？

设备 原材料A 原材料B 单位产品利润（元） Ⅰ 1 4 0 2 Ⅱ 2 0 4 3 资源限量 8(台时) 16(kg) 12(kg) 解：设x1,x2分别表示在计划期内生产产品Ⅰ、Ⅱ的产量。由于资源的限制，所以有：

机器设备的限制条件: x1?2x2?8

原材料A的限制条件： 4x1?16（称为资源约束条件） 原材料B的限制条件： 4x2?12

同时，产品Ⅰ、Ⅱ的产量不能是负数，所以有x1?0,x2?0（称为变量的非负约束）。

显然，在满足上述约束条件下的变量取值，均能构成可行方案，

第二章 线性规划的对偶理论与灵敏度分析习题

1. 写出下列线性规划问题的对偶问题。

minz?2x1?2x2?4x3?x1?3x2?4x3?2? (1)?2x1?x2?3x3?3??x1?4x2?3x3?5??x1,x2?0,x3无约束minz???cijxiji?1j?1mnmaxz?5x1?6x2?3x3?x1?2x2?2x3?5? (2) ??x1?5x2?x3?3

??4x1?7x2?3x3?8??x1无约束,x2?0,x3?0minz??cjxjj?1n?n?naijxj?bi(i?1,?,m1?m)(3)??xij?ai(i?1,?,m) (4)?? j?1j?1?????n?m??aijxj?bi(i?m1?1,m2?2,?,m)??xij?bj(j?1,?,n)?j?1?i?1?x?0无约束(j?1,?,n,?,n)?xij?0(i?1,?,m;j?1,?,n)1?j?????2. 判断下列说法是否正确，为什么?

(1)如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解； (2)如果线性规划的对偶问题无可行解，则原问题也一定无可行解； ( 3)在互为对偶的一对原问题与对偶问题中，不管原问题

第二章 线性规划的对偶理论与灵敏度分析习题

1. 写出下列线性规划问题的对偶问题。

minz?2x1?2x2?4x3?x1?3x2?4x3?2? (1)?2x1?x2?3x3?3??x1?4x2?3x3?5??x1,x2?0,x3无约束minz???cijxiji?1j?1mnmaxz?5x1?6x2?3x3?x1?2x2?2x3?5? (2) ??x1?5x2?x3?3

??4x1?7x2?3x3?8??x1无约束,x2?0,x3?0minz??cjxjj?1n?n?naijxj?bi(i?1,?,m1?m)(3)??xij?ai(i?1,?,m) (4)?? j?1j?1?????n?m??aijxj?bi(i?m1?1,m2?2,?,m)??xij?bj(j?1,?,n)?j?1?i?1?x?0无约束(j?1,?,n,?,n)?xij?0(i?1,?,m;j?1,?,n)1?j?????2. 判断下列说法是否正确，为什么?

(1)如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解； (2)如果线性规划的对偶问题无可行解，则原问题也一定无可行解； ( 3)在互为对偶的一对原问题与对偶问题中，不管原问题

（一）线性规划

案例分析1

例1.10 飞乐公司经营一个回收中心，专门从事用三种废弃原材料C、P、H混合调出三种不同规格的产品ABD。根据混合时候各种材料的比例，可将该产品分为不同的等级（参照表1.12）。尽管在混合各种等级产品时允许一定的机动性，但每一等级产品中各种材料的最大值和最小值必须符合下面质量标准的规定（最大值和最小值是根据该材料的重量在该等级产品总重量中的比例来确定的）。在两种较高等级的产品中，有一种特定材料的比例是固定的。已知产品的规格要求，产品单价，每天能供应的原材料数量及原材料单价，分别见表1.12和表1.13，问该厂应如何安排生产，使利润收入为最大？ 表1.12

产品名称 Ａ B D

规格要求 原材料C不少于５０％ 原材料Ｐ不多于２５％ 原材料C不少于２５％ 原材料P不多于５０％

不限

单价（元／kg）

50 35 25

回收中心可以从一些渠道定期收集到所需的固体废弃物，因此，可以获得维持稳定作业的处理量。表1.13给出了中心每天可以收集到每种材料的数量和原材料单价。

表1.13

原材料名称

C P H

每天最多供应量（kg）

100 100 60

单价（元／kg）

65 25 35

飞乐公司是绿地组织的全资公司，绿地组织

线性规划模型在物流管理中的应用

摘 要：本文引入权值的概念对物流管理的运输网络进行分析，用线性规划模型求解运输网络中最佳路径，在寻求最佳运输路线中取得满意的效果。

关键词：线性规划模型；物流管理 中图分类号：F224

20世纪中期，对物流管理的研究一直方兴未艾，不仅在理论上突出了一套完整的概念，也设计出了很多优化模型，如何降低物资消耗，降低运输成本，减少运输时间对物流企业的运营成本有着很大的影响，在一定程度上影响物流企业的成败，目前国内在运输管理中，仍然存在运输线路不合理，运输费用过高，如果运送线路的道路状况发生变化，不能形成有效的配送方案。从而导致企业运送成本过高。 1 运输线路的优化目标

如何在保证服务质量的前提下，用最少时间、最小运输成本将货物运送到目的地是运输管理的目的。有效的运输管理主要包括以下方面：（1）及时：在规定的时间内，完成物品的运送，物品在运送途中的时间尽量短，从而加快物品的流通，保证市场的物品供

应及时；（2）准确：保证物品能够准确的运送，既要保证物品在运送途中不被损坏：又要保证特殊商品（如海鲜类）不因运送时间长导致物品变质；（3）安全：运送过程中，物品、人员、车辆等安全；（4）经济