管理运筹学I讲义.doc

第二章线性规划(LP)
§ 线性规划数学模型的建立
LP问题提出:苏联:康德洛维奇 1939
一、线性规划数学模型的三要素:
(decision variable):决策问题待定的量值。用字母(例如X1,X2,···,Xn)来表示可控制的因素。每一组决策变量的实际值就表示一个具体方案。
(objective function):MaxZ=CX 或 MinZ=CX;(衡量决策优劣的准则)
特点:(1)单一目标;(2)关于决策变量的线性函数。(定义:课本P20)
(constraint conditions):. (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
. …………
am1 x1 + am2 x2 + …+ amn xn ≤( =, ≥)bm
x1 ,x2 ,…,xn ≥ 0
(2)向量形式
目标函数:Max (Min) z = CX

≤(≥,=)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个约束条件。
,设出决策变量
根据实际问题定义决策变量( x1 ,x2 ,…,xn ),

目标函数一般表达式: MaxZ (或 MinZ)= c1 x1 + c2 x2 + …+ cn xn
注:目标函数是一个用决策变量表示的线性函数,其有两种基本形式:最大化目标或最小化目标。
本例中,目标函数为:

例1.[生产计划安排问题]某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产,已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制,单位产品的获利,如下表所示:
问题:计划期内工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多?
解:设工厂在计划期内应安排生产产品ⅠX1件, 产品ⅡX2件。
Max z = 50 x1 + 100 x2
x1 + x2 ≤ 300
. 2 x1 + x2 ≤ 400
x2 ≤ 250
x1 , x2 ≥ 0
练****请写出例1数学模型中的价值向量,决策变量向量,限定向量及约束条件系数矩阵
四、LP数学模型的特点

2. 双线性
(1)目标函数是关于决策变量的线性函数;(2)所有约束条件是关于决策变量的线性函数
建模例题讲解:见ppt
投资问题
,今后五年内考虑给以下的项目投资。已知:
项目A:从第一年到第五年每年年初都可投资,当年末能收回本利110%;
项目B:从第一年到第四年每年年初都可投资,次年末能收回本利125%,但规定每年最大投资额不能超过30万元;
项目C:需在第三年年初投资,第五年末能收回本利140%,但规定最大投资额不能超过80万元;
项目D:需在第二年年初投资,第五年末能收回本利155%,但规定最大投资额不能超过100万元。
据测定每万元每次投资的风险指数如下表:
问:
a)应如何确定这些项目的每年投资额,使得第五年年末拥有资金的本利金额为最大?
b)应如何确定这些项目的每年投资额,使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小?
解: 1)确定决策变量:连续投资问题。
设 xi