你的位置：
首页
>
IT圈
>
将以下线性规划问题转化为标准形式
2024年4月26日发(作者：缑靖)
第二章 线性规划（LP）
§2.1 线性规划数学模型的建立
LP问题提出：苏联：康德洛维奇 1939
一、线性规划数学模型的三要素：
1.决策变量(decision variable)：决策问题待定的量值。用字母（例如X1,X2,···,Xn）来表示可控制的因
素。每一组决策变量的实际值就表示一个具体方案。
2.目标函数（objective function）：MaxZ=CX 或 MinZ=CX；(衡量决策优劣的准则)
特点：（1）单一目标；（2）关于决策变量的线性函数。（定义：课本P20）
3.约束条件(constraint conditions)：s.t. (subject to) 受制于约束；AX≤(≥，=)b
特点：若干关于决策变量的线性函数。
二、LP数学模型的一般形式
（1）繁写形式
目标函数：Max （Min）z = c1 x1 + c2 x2 + … + cn xn
约束条件：
a11 x1 + a12 x2 + … + a1n xn ≤ （ =, ≥ ）b1
a21 x1 + a22 x2 + … + a2n xn ≤ （ =, ≥ ）b2
s.t. …… ……
am1 x1 + am2 x2 + … + amn xn ≤ （ =, ≥ ）bm
x1 ，x2 ，… ，xn ≥ 0
（2）向量形式
目标函数：Max （Min） z = CX
j
1
p
n
j
x
j
≤(≥，=)b
Xj≥ 0 (j=1,2, …,n)
其中，C=(c1 , c2 , … , cn )(价值向量)
X= (x1 , x2 , … , xn )T(决策变量向量)
b=(b1 , b2 , … , bm )T (限定向量)
pj= (a1j ， a2j … amj ) T (约束条件系数列向量)
注：矩阵相乘条件：左列=右行
(3)矩阵形式★
目标函数：Max （Min） z = CX
约束条件：
AX ≤ （ =, ≥ ）b
X≥ 0
其中，C=(c1 , c2 , … , cn )(价值向量)
X= (x1 , x2 , … , xn )T(决策变量向量)
b=(b1 , b2 , … , bm )T (限定向量、资源向量)
a11 a12 … a1n
a21 a22 … a2n (系数矩阵)
A= ……
am1 am2 … amn
三、建模的一般步骤
前提假设：假设模型中有n个决策变量，m个约束条件。
1.分析问题,设出决策变量
根据实际问题定义决策变量（ x1 ，x2 ，… ，xn ），
2.根据所提问题列出目标函数
目标函数一般表达式： MaxZ （或 MinZ）= c1 x1 + c2 x2 + … + cn xn
注：目标函数是一个用决策变量表示的线性函数，其有两种基本形式：最大化目标或最小化目标。
本例中，目标函数为：
3.根据已知条件列出所有约束条件
例1.[生产计划安排问题]某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需
的设备台时及A、B两种原材料的消耗、资源的限制，单位产品的获利，如下表所示：
设备
原料A
原料B
单位产品获利
产品Ⅰ
1
2
0
50元
产品Ⅱ
1
1
1
100元
资源限制
300台时
400千克
250千克
问题：计划期内工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？
解：设工厂在计划期内应安排生产产品ⅠX1件, 产品ⅡX2件。
Max z = 50 x1 + 100 x2
x1 + x2 ≤ 300
s.t. 2 x1 + x2 ≤ 400
x2 ≤ 250
x1 , x2 ≥ 0
练习：请写出例1数学模型中的价值向量，决策变量向量，限定向量及约束条件系数矩阵
四、LP数学模型的特点
1.单一目标
2. 双线性
2024年4月26日发(作者：缑靖)
第二章 线性规划（LP）
§2.1 线性规划数学模型的建立
LP问题提出：苏联：康德洛维奇 1939
一、线性规划数学模型的三要素：
1.决策变量(decision variable)：决策问题待定的量值。用字母（例如X1,X2,···,Xn）来表示可控制的因
素。每一组决策变量的实际值就表示一个具体方案。
2.目标函数（objective function）：MaxZ=CX 或 MinZ=CX；(衡量决策优劣的准则)
特点：（1）单一目标；（2）关于决策变量的线性函数。（定义：课本P20）
3.约束条件(constraint conditions)：s.t. (subject to) 受制于约束；AX≤(≥，=)b
特点：若干关于决策变量的线性函数。
二、LP数学模型的一般形式
（1）繁写形式
目标函数：Max （Min）z = c1 x1 + c2 x2 + … + cn xn
约束条件：
a11 x1 + a12 x2 + … + a1n xn ≤ （ =, ≥ ）b1
a21 x1 + a22 x2 + … + a2n xn ≤ （ =, ≥ ）b2
s.t. …… ……
am1 x1 + am2 x2 + … + amn xn ≤ （ =, ≥ ）bm
x1 ，x2 ，… ，xn ≥ 0
（2）向量形式
目标函数：Max （Min） z = CX
j
1
p
n
j
x
j
≤(≥，=)b
Xj≥ 0 (j=1,2, …,n)
其中，C=(c1 , c2 , … , cn )(价值向量)
X= (x1 , x2 , … , xn )T(决策变量向量)
b=(b1 , b2 , … , bm )T (限定向量)
pj= (a1j ， a2j … amj ) T (约束条件系数列向量)
注：矩阵相乘条件：左列=右行
(3)矩阵形式★
目标函数：Max （Min） z = CX
约束条件：
AX ≤ （ =, ≥ ）b
X≥ 0
其中，C=(c1 , c2 , … , cn )(价值向量)
X= (x1 , x2 , … , xn )T(决策变量向量)
b=(b1 , b2 , … , bm )T (限定向量、资源向量)
a11 a12 … a1n
a21 a22 … a2n (系数矩阵)
A= ……
am1 am2 … amn
三、建模的一般步骤
前提假设：假设模型中有n个决策变量，m个约束条件。
1.分析问题,设出决策变量
根据实际问题定义决策变量（ x1 ，x2 ，… ，xn ），
2.根据所提问题列出目标函数
目标函数一般表达式： MaxZ （或 MinZ）= c1 x1 + c2 x2 + … + cn xn
注：目标函数是一个用决策变量表示的线性函数，其有两种基本形式：最大化目标或最小化目标。
本例中，目标函数为：
3.根据已知条件列出所有约束条件
例1.[生产计划安排问题]某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需
的设备台时及A、B两种原材料的消耗、资源的限制，单位产品的获利，如下表所示：
设备
原料A
原料B
单位产品获利
产品Ⅰ
1
2
0
50元
产品Ⅱ
1
1
1
100元
资源限制
300台时
400千克
250千克
问题：计划期内工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？
解：设工厂在计划期内应安排生产产品ⅠX1件, 产品ⅡX2件。
Max z = 50 x1 + 100 x2
x1 + x2 ≤ 300
s.t. 2 x1 + x2 ≤ 400
x2 ≤ 250
x1 , x2 ≥ 0
练习：请写出例1数学模型中的价值向量，决策变量向量，限定向量及约束条件系数矩阵
四、LP数学模型的特点
1.单一目标
2. 双线性