2.1　线性规划的标准形式

第1章中【例1-1】数学模型的特点是目标函数和约束条件均为线性，设计变量非负。例子中的约束条件仅含“≤”的约束条件。归纳起来线性规划问题的一般形式为

目标函数　　max（min）f（x）=c1x1+c2x2+…+cnxn

a11x1+a12x2+…+a1nxn≤（=，≥）b1

a21x1+a22x2+…+a2nxn≤（=，≥）b2

……

约束条件　　am1x1+am2x2+…+amnxn≤（=，≥）bm

xj≥0　j=1，2，…，n（m<n）

线性规划问题的常规求解方法是利用矩阵的初等变换，求解时引进非负的松弛变量（对“≥”的约束称为剩余变量）将不等式约束转化为等式约束，也就是将线性规划问题的一般形式变为标准形式。因此线性规划问题数学模型的标准形式为线性目标函数加上等式及变量非负的约束条件。用数学表达式表述为

min（max）c1x1+c2x2+…+cnxn

s.t.a11x1+a12x2+…+a1nxn=b1

a21x1+a22x2+…+a2nxn=b2

……

am1x1+am2x2+…+amnxn=bm

xj≥0，　j=1，2，…，n（m<n）

用矩阵表示为

min（max）cTx

s.t.Ax=b

xj≥0　j=1，2，…，n　　（2-1）

【例1-1】的模型化成标准形为

maxf （x）=220x1+250x2+0x3+0x4+0x5+0x6

s.t.x1+x2+x3=1200

2x1+x2+x4=1800

x1+x5=800

x2+x6=1000

xj≥0，　j=1，2，…，6