线性规划研究的主要问题
一类是已有一定数量的资源（人力、物质、 时间等），研究如何充分合理地使用它们，才能 使完成的任务量为最大。
另一类是当一项任务确定以后，研究如何统 筹安排，才能使完成任务所耗费的资源量为最少。
—— 实际上，上述两类问题是一个问题的两个不同 的方面，都是求问题的最优解（ max 或 min ）。
例2 某航运局现有船只种类、数量以及计划期内各条航线 的货运量、货运成本如下表所示：问：应如何编队，才能既完 成合同任务，又使总货运成本为最小？
航线 船队 号 类型
1 1
2 3 2 4
编队形式
拖轮
A型 驳船
B型 驳船
1
2
—
1
—
4
2
2
4
1
—
4
货运成本 （千元／队）
36 36 72 27
货运量 （千吨）
25 20 40 20
船只种类 拖轮 A型驳船 B型驳船
船只数 30 34 52
航线号 1 2
合同货运量 200 400
解：设 xj 为第 j 号类型船队的队数( j = 1,2,3,4 ), z 为总货运 成本, 则：
min z = 36x1 + 36x2 + 72x3 + 27x4
x1 + x2 + 2x3 + x4≤ 30
2 1 1 1 00 00 0 2 1 0 32 10 1 0 1 3 02 34
7.3 7.1 6.5 7.4 6.3 7.2 6.6 6.0 0.1 0.3 0.9 0.0 1.1 0.2 0.8 1.4
方案 长度m
2.9 2.1 1.5 合计 料头
ⅠⅡ Ⅲ ⅣⅤ Ⅵ ⅦⅧ
x1 x2 x3 x4 x5 x6 x7 x8
例4 某厂生产三种药物， 解：
这些药物可以从四种不同的 原料中提取。下表给出了单 位原料可提取的药物量
1. 决策变量：设四种原料的使
用量分别为：x1、x2 、x3 、x4
药物
单位成本
原料
A B C (元／吨)
甲 123
5
2. 目标函数：设总成本为z， 则有：
min z = 5 x1 + 6 x2 + 7 x3 + 8 x4
2. 找出所有限定条件：即决策变量受到的所有的约 束；
3. 写出目标函数：即问题所要达到的目标，并明确 是max 还是 min。
三、建模案例
例1 某工厂生产A、B两种产品，有关资料如下表所示：
工序
产品
A
工序1
2
工序2
3
单位利润
（百元）
4
B
பைடு நூலகம்
C
销售
报废
工时限制
3
—
—
12
4
—
—
24
10
3
－2
注：每生产单位产品B可得到4单位副产品C，据预测，市场上产品C的 最大销量为5单位，若产品C销售不出去，则报废。
例3 合理利用线材问题 现要做100套钢架，每套用长2.9m，2.1m，1.5m，的圆钢
各一根。已知原料长7.4m，问应如何下料，使用的原材料最省？ 解：所有下料方案如下表：（xj - 第j种方案所用原材料的根数）
方案 长度m
2.9 2.1 1.5 合计 料头
ⅠⅡ Ⅲ ⅣⅤ Ⅵ ⅦⅧ
x1 x2 x3 x4 x5 x6 x7 x8
2x1 x2 x3 x4 0x5 0x6 0x7 0x8 100
0x1 2x2 x3 0x4 3x5 2x6 1x7 0x8 100
x1 0x2 x3 3x4 0x5 2x6 3x7 4x8 100
x1，x2，x3，x4，x5，x6，x7，x8 0
211 1 00 00 021 0 32 10 101 3 02 34 7.3 7.1 6.5 7.4 6.3 7.2 6.6 6.0 0.1 0.3 0.9 0.0 1.1 0.2 0.8 1.4
min z 0.1x1 0.3x2 0.9x3 0x4 1.1x5 0.2x6 0.8x7 1.4x8
线性规划应用举例
一、建模条件
一般讲，一个经济、管理问题满足以下条件时，才能 建立线性规划模型
1. 要求解问题的目标函数能用数值指标来反映，且为 线性函数；
2. 存在着多种方案； 3. 要求达到的目标是在一定约束条件下实现的，这些 约束条件可用线性等式或不等式来描述。
二、建模步骤
1. 确定决策变量：即需要我们作出决策或选择的量。 一般情况下，题目问什么就设什么为决策变量。
解：设总利润为z， max z = 4 x1 + 10 x2 + 3 x3 － 2 x4
A、B产品销量为x1、x2， 产 品 C 的 销 售 量 为 x3 ， 报废量为x4，则：
2 x1 + 3x2
≤ 12
3x1 + 4x2
≤ 24
－4x2 +x3 + x4 = 0
x3 ≤ 5
x1、x2 、x3 、x4≥ 0
2x1
+ 2x3
≤ 34
4x2 + 4x3 + 4x4 ≤ 52
25x1 + 20x2
＝ 200
40x3 + 20x4＝ 400
xj ≥ 0 j = 1,2,3,4
用单纯形法可求得：x1 = 8，x2 = 0 ，x3 = 7， x4 = 6 最优值： z = 954，即：四种船队类型的队数分别是8、0、7、6，此时可 使总货运成本为最小，为954千元。
线性规划问题求解程序设计要求
1. 线性规划问题的数学模型
max(min) z c1 x1 c2 x2 cn xn
a11 x1 a12 x2 a1n xn ( ，)b1
a21 x1 a22 x2 a2n xn ( ，)b2
am1 x1
am2 x2
amn xn
乙 201
6
3. 约束条件：
丙 141
7
丁 122
8
x1 + 2x2 + x3 + x4 ≥160
要求：生产A种药物至少 160单位；B种药物恰好200单 位，C种药物不超过180单位， 且使原料总成本最小。
2x1
+4 x3 +2 x4 ＝200
3x1 ＋ x2 + x3 +2 x4 ≤180
x1、x2 、x3 、x4 ≥0
( ，)bm
x1，x2， ，xn 0 (无约束)
2. 线性规划问题的求解方法 采用两阶段法求解
3. 求解程序的输入与输出
变量个数n= ( ) 约束条件个数m= ( )
max(min) z c1 x1 c2 x2 cn xn
a11 x1 a12 x2 a1n xn ( ，) b1
a21 x1 a22 x2 a2n xn ( ，) b2
am1 x1 am2 x2 amn xn ( ，) bm