运筹学第一章 .pdfVIP

第一章、线性规划和单纯形法

1.1线性规划的概念

一、线性规划问题的导出

1．(引例)配比问题——用浓度为45%和92%的硫酸配置100t

浓度为80%的硫酸。

取45%和92%的硫酸分别为x1和x2t,

则有：xx100



12



0.45x0.92x0.8100

12

求解二元一次方程组得解。

目的相同，但有5种不同浓度的硫酸可选（30%，45%，73%，

85%，92%）会出现什么情况？

设取这5种硫酸分别为x1、x2、x3、x4、x5t,则有：

xxxxx100



12345



0.3x0.45x0.73x0.85x0.92x0.8100

12345

请问有多少种配比方案？为什么？哪一种方案最好？

假设5种硫酸价格分别为：400，700，1400，1900，2500元/t，

则有：

MinZ400x700x1400x1900x2500x

12345



xxxxx100

12345



s.t.0.3x0.45x0.73x0.85x0.92x0.8100



12345

0,1,2,,5

xj

2.j

生产计划问题

ABC每天可利用资源量

工时（单位）1113

材料（t）1479

产品利润（元/t）200030001000

如何制定生产计划，使三种产品总利润最大？

考虑问题：

（1）何为生产计划？

（2）总利润如何描述？

（3）还要考虑什么因素？

（4）有什么需要注意的地方（技巧）？

（5）最终得到的数学模型是什么？

MaxZ2x3xx

123



xxx3

123



s.t.x4x7x9



123



x0,j1,2,3

j

二、线性规划的定义和数学描述（模

型）

1．定义：对于求取一组变量xj(j=1,2,,n)，使之既

满足线性约束条件，又使具有线性表达式的目标函数取得极大

值或极小值的一类最优化问题称为线性规划问题，简称线性规

划。

2.配比问题和生产计划问题的线性规划模型的特点：

用一组未知变量表示要求的方案，这组未知变量称为决

策变量；

存在一定的限制条件，且为线