1.　线性规划数学模型的一般形式

为了能更容易理解线性规划模型，我们先看下面的例子.

5.1.1生产计划问题

例1某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品.每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：

表51

每件产品占用的

机时数（小时/件）产品甲产品乙产品丙产品丁设备能力

（小时）

设备A1.51.02.41.02000

设备B1.05.01.03.58000

设备C1.53.03.51.05000

利润（元/件）5.247.308.344.18

用线性规划制订使总利润最大的生产计划.

设变量xi为第i种产品的生产件数（i＝1，2，3，4），目标函数z为相应的生产计划可以获得的总利润.在加工时间以及利润与产品产量成线性关系的假设下，可以建立如下的线性规划模型：

maxz=5.24x1+7.30x2+8.34x3+4.18x4目标函数〖1〗

s.t.1.5x1+1.0x2+2.4x3+1.0x4≤2000〖1〗

1.0x1+5.0x2+1.0x3+3.5x4≤8000约束条件〖1〗

1.5x1+3.0x2+3.5x3+1.0x4≤5000〖1〗

x1,x2,x3,x4≥0变量非负约束

这是一个典型的利润最大化的生产计划问题.其中max表示极大化（maximize），s.t.是subject　to的缩写.利用计算机程序可求解这个线性规划，可以得到最优解为：

x1=294.12x2=1500x3=0x4=58.82（件）

最大利润为z=12737.06（元）

请注意最优解中利润率最高的产品丙在最优生产计划中不安排生产.说明按产品利润率大小为优先次序来安排生产计划的方法有很大局限性.尤其当产品品种很多，设备类型很多的情况下，用手工方法安排生产计划很难获得满意的结果.

5.1.2配料问题

例2某工厂要用四种合金T1，T2，T3和T4为原料，经熔炼成为一种新的不锈钢G.这四种原料含元素铬（Cr），锰（Mn）和镍（Ni）的含量（%），这四种原料的单价以及新的不锈钢材料G所要求的Cr，Mn和Ni的最低含量（%）如下表所示：

表52

T1T2T3T4G

Cr3.214.532.191.763.20

Mn2.041.123.574.332.10

Ni5.823.064.272.734.30

单价（元/公斤）115978276

设熔炼时重量没有损耗，要熔炼成100公斤不锈钢G，应选用原料T1，T2，T3和T4各多少公斤，使成本最小.

设选用原料T1，T2，T3和T4分别为x1，x2，x3，x4公斤，根据条件，可建立相应的线性规划模型如下：

minz=115x1+97x2+82x3+76x4〖1〗

s.t.0.0321x1+0.0453x2+0.0219x3+0.0176x4≥3.20〖1〗

0.0204x1+0.0112x2+0.0357x3+0.0433x4≥2.10〖1〗

0.0582x1+0.0306x2+0.0427x3+0.0273x4≥4.30〖1〗

x1+x2+x3+x4=100〖1〗

x1≥0,x2≥0,x3≥0,x4≥0

这是一个典型的成本最小化的问题.其中min表示极小化（minimize）.这个线性规划问题的最优解是

x1=26.58x2=31.57x3=41.84x4=0（公斤）

最低成本为z=9549.87（元）

5.1.3运输问题

例3设某种物资从两个供应地A1，A2运往三个需求地B1，B2，B3.各供应地的供应量、各需求地的需求量、每个供应地到每个需求地的单位物资运价如下表所示.

表53

运价（元/吨）B1B2B3供应量（吨）

A123535

A247825

需求量（吨）103020

图51

这个问题也可以用图解表示如下，其中节点A1、A2表示供应地，节点B1、B2、B3表示需求，从每一供应地到每一需求地都有相应的运输路线，共有6条不同的运输路线.

设xij为从供应地Ai运往需求地Bj的物资数量（i=1,2；j=1,2,3），z为总运费，则总运费最小的线性规划模型为：

minz=2x11+3x12+5x13+4x21+7x22+8x23〖1〗

s.t.x11+x12+x13=35（1）〖1〗

x21+x22+x23=25（2）〖1〗

x11+x21=10（3）〖1〗

x12+x22=30（4）〖1〗

x13+x23=20（5）

xij≥0

以上约束条件（1）、（2）称为供应地约束，（3）、（4）、（5）称为需求地约束.这个问题的最优解为：x11=0，x12=30，x13=5，x21=10，x22=0，x23=15（吨）；最小运费为：z=275元.