线性规划模型例题

线性规划常见题型及解法

一、求线性目标函数的取值范围

?x?2?例1、 若x、y满足约束条件?y?2，则z=x+2y的取值范围是 （ ）

?x?y?2?A、[2,6] B、[2,5] C、[3,6] D、（3,5]

解：如图，作出可行域，作直线l：x+2y＝0，将

y 2 O 2 B y =2 x x + y =2 A l向右上方平移，过点A（2,0）时，有最小值

2，过点B（2,2）时，有最大值6，故选A

x=2 二、求可行域的面积

?2x?y?6?0?例2、不等式组?x?y?3?0表示的平面区域的面积为 （ ）

?y?2? A、4 B、1 C、5 D、无穷大

解：如图，作出可行域，△ABC的面积即为所求，由梯形OMBC

的面积减去梯形OMAC的面积即可，选B

y x＋y – 3 = 0 M A O B y =2 C x 2x + y – 6= 0 = 5 三、求可行域中整点个数

例3、满足|x|＋|y|≤2的点（x，y）中整点（横纵坐标都是整数）有（ ） A、9个 B、10个 C、13个 D、14个

y ?x?y?2?x?y?2?解：|x|＋|y|≤2等价于???x?y?2???x?y?2(x?0,y?0)(x?0,y?0)

线性规划模型研究

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

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.

篇一：典型例题：简单的线性规划问题

典型例题

【例1】求不等式｜x－1｜+｜y－1｜≤2表示的平面区域的面积.

【例2】某矿山车队有4辆载重量为10 t的甲型卡车和7辆载重量为6 t的乙型卡车，有9名驾驶员此车队每天至少要运360 t矿石至冶炼厂.已知甲型卡车每辆每天可往返6次，乙型卡车每辆每天可往返8次甲型卡车每辆每天的成本费为252元，乙型卡车每辆每天的成本费为160元.问每天派出甲型车与乙型车各多少辆，车队所花成本费最低?

参考答案

例1：

【分析】依据条件画出所表达的区域，再根据区域的特点求其面积.

【解】｜x－1｜+｜y－1｜≤2可化为

或其平面区域如图：

或或

∴面积S=×4×4=8

【点拨】画平面区域时作图要尽量准确，要注意边界.

例2：

【分析】弄清题意，明确与运输成本有关的变量的各型车的辆数，找出它们的约束条件，列出目标函数，用图解法求其整数最优解.

【解】设每天派出甲型车x辆、乙型车y辆，车队所花成本费为z元，那么

z=252x+160y，

作出不等式组所表示的平面区域，即可行域，如图

作出直线l0：252x+160y=0，把直线l向右上方平移，使其经过可行域上的整点，且使在y轴上的截距最小.

观察图形，可见当直线252x+160y=t经过点（2，5）时，满

数学建模

第七章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

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

线性规划常见题型及解法

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

一、求线性目标函数的取值范围

?x?2?例1、 若x、y满足约束条件?y?2，则z=x+2y的取值范围是 （ ）

?x?y?2?A、[2,6] B、[2,5] C、[3,6] D、（3,5]

解：如图，作出可行域，作直线l：x+2y＝0，将

l向右上方平移，过点A（2,0）时，有最小值 2，过点B（2,2）时，有最大值6，故选A

y 2 O 2 B y =2 x x + y =2 A x=2 二、求可行域的面积

?2x?y?6?0?例2、不等式组?x?y?3?0表示的平面区域的面积为 （ ）

?y?2? A、4 B、1 C、5 D、无穷大

解：如图，作出可行域，△ABC的面积即为所求，由梯形OMBC

的面积减去梯形OMAC的面积即可，选B

y x＋y – 3 = 0 M A O B y =2 三、求可行域中整点个数

例3、满足|x|＋|y|≤2的点（x，y）中整点（横纵坐标都是整数）有（ ） A、9个 B、10个 C、13个 D、14个

C x 2x + y