第六章 线性规划
线性规划是最简单的约束优化问题。这是因为线性规划的目标函数和约束函数都是线性函数。
1.线性规划的标准形式
n
min
c
j
xj
j 1n
s.t. aijxj bi,i 1,2,...,m
j 1
xj 0,j 1,2,...,n(m n)
为简便,标准形式还可写成:
mincT
x
s.t.Ax b
x 0
其中:x x1,x2, ,xT
n c c1,c2, ,cT
n b b1,b2, ,
bT
n
a a1n
A 11
am1
amn
还可以写成:
mincT
x
ns.t. xjaj b
j 1
x 0
其中a [aT
j
1j,a2j,...,amj]
称c1,c2,...,cn为变量x1,x2,...,xn的价格系数,c为价格系数向量。