线性规划 毕业论文

数值减少（或增大），若现行解（极点）为最优解，则计算结束；否则继续这种极点之间的转移。 下面举例说明如何构造单纯形表 例1 设有线性规划问题

mins x1 2x2 x3 2x1 x2 x3 4

x 2x 6 12

x 0(i 1,2,3) i

试选择一个基，并构造单纯形表。 解 先将线性规划问题标准化，得

mins x1 2x2 x3 0x4 2x1 x2 x3 x4 4

x1 2x2 0x3 0x4 6 x 0(i 1,2,3,4) i

2 11 1 4

b x x,x,x,x本例中，A ,,,c 1,2,1,01234。构 6 1200

造单纯形表实际上是要计算cBB 1b,cBB 1A c,B 1b和B 1A。 (1). 确定基B P1,P3 或B P2,P4

21 2 1 B P,P （当然也可以选取12 12

10

1 1

等等。事实上，只要选择系数矩阵A的m 2个线

20

性无关的列向量组成B，使B为非奇异矩阵即可）。并由此得到

01

B x x,xx x,xcB c1,c3 1,1 ，cN c2,c4 2,0 。，， 13N24， B

1 2

1

(2).计算目标值b00 s cBB 1b 1,1 (3). 计算检验数

01 4

22

1 2 6