当前位置：首页> 正在进行安全检测...

正在进行安全检测...

时间：下载该word文档

线性规划问题
一、线性规划问题的基本概念
先看几个典型实例例1生产计划问题
某工厂拥有a、b两种原材料生产A、B两种产品，现有设备使用限量为8台时，已知每件产品的利润、所需设备台时及原材料的消耗如下表所示：产品
原材料a(kgb(kg利润(万元设备(台
A4021B0432质材料总量
1612

试问：在计划期内应如何安排计划才能使工厂获得的利润最大？
解设x1、x2分别表示在计划期内产品A、B的产量，则所用设备的有效台时必须满足x1＋2x2≤8同样，由原材料的限量，可以得到4x1≤16，4x2≤12因此，生产计划就是满足如下约束条件的一组变量x1、x2的值：
x1＋2x2≤8，4x1≤16，4x2≤12，x1≥0，x2≥0显然，可行的生产计划有限多个，现在问题就是要在很多个可行计划中找一个利润最大的，即求一组变量x1、x2的值，使它满足约束条件，并使目标函数L=2x1＋3x2的值最大（即利润最大）
例2资金分配问题
某商店拥有100万元资金，准备经营A、B、C三种商品，其中A商品有A1、A2两种型号，B商品有B1、B2两种型号，每种商品的利润率如下表所示：商品
A1
利润率（%）

AA2
10.3B1
6.41BB2
7.5C
4.57.3
在经营中有以下限制：
(1经营A或B的资金各自都不能超过总资金的50%；(2经营C的资金不能少于经营B的资金的25%；(3经营A2的资金不能超过经营A的总资金的60%；试问应怎样安排资金的使用才能使利润最大？
解设经营A1、A2、B1、B2、C的资金分别为x1，x2,x3,x4，x5（万元），这一问题的数学模型为求一组变量x1、x2，…，x5的值，使它满足

x1＋x2＋…＋x5=100，x1＋x2≤50，x3＋x4≤50，025x3＋0.25x4－x5≤00.6x1－0.4x2≥0，
xj≥0（j=1，2，…，5）
并使目标函数L=0.073x1＋0.103x2＋0.064x4＋0.075x4＋0.045x5的值最大(利润最大
上面我们建立了几个实际问题的数学模型，虽然实际问题各不相同，但是它们的数学模型却有相同的数学形式，这就是：表示约束条件的数学式子都是线性等式或线性不等式，表示问题最优化指标的目标函数都是线性函数，因为约束条件和目标函数都是线性的，所以把具有这种模型的问题称为线性规划问题。
线性规划问题的数学模型的一般形式是

Max(MinL=c1x1＋c2x2＋…＋cnxn.

(1a11x1＋a12x2＋…＋a1nxn≤b1(或≥b1，或=b1,a21x1＋a22x2＋…＋a2nxn≤b2(或≥b2，或=b2

(2

am1