单纯形法基本原理(3)

n

aijxj ( , )bis.t j 1

xj 0

(i 1,2, ,m)(j 1,2, ,n)

若

C (c1,c2, ,cn);X

x1 b1 a1

x2b2a ;b ;A 2

xn b m am1

aa am2

an

(P,P, ,P)

12n

amn

n

令

a

则线性规划问题的矩阵形式：max(min)Z CX

AX ( , )bs.t

X 0

2.2 线性规划问题的标准形式

LP问题的数学模型的标准形式为：maxZ c1x1 c2x2 cnxn

n

aijxj bis.t j 1

xj 0

(i 1,2, ,m,且bi 0)

(j 1,2, ,n)

⑴ 若目标函数为 minZ c1x1 c2x2 cnxn，则可以引进新的目标函数Z Z,

Z 。从而目标函数变换为：则Z的最小值即为Z’的最大值，即：minZ max

maxZ c1x1 c2x2 cnxn

⑵ 当约束条件中含有不等式时， 如：maxZ 3x1 3x2

x1 2x2

s.t 2x1 x2

x 0 i

10 1 14 2 (i 1,2)

此时，对⑴ x1 2x2 10，引入变量x3 0, 使得⑴式变为：x1 2x2 x3 10，同理对⑵式2x1 x2 14引入变量x4 0,使得⑵式变为：2x1 x2 x4 14 于是原LP问题化为标准形式：maxZ 3x1 3x2