第一节线性规划问题及其数学模型 线性规划问题的标准形式 LP问题有许多不同的形式。其目标函数，有 的求最大，有的求最小；其约束，有“≤”，“=” 和“≥”三种形式；而决策变量， 有的要求非负值， 有的要求非正值，还有的要求自由取值。这种多样 性不仅给研讨带来不便，而且使你难以寻找到一种 通用解法。经过不断探索，人们发现：LP问题的 各种不同形式可以相互转化。因此只需给出其中一 种形式的解法，就可普遍适用于一切形式的LP问 题
18 二、线性规划问题的标准形式 LP问题有许多不同的形式。其目标函数，有 的求最大，有的求最小；其约束，有“≤” ， “=” 和“≥”三种形式；而决策变量，有的要求非负值， 有的要求非正值，还有的要求自由取值。这种多样 性不仅给研讨带来不便，而且使你难以寻找到一种 通用解法。经过不断探索，人们发现：LP问题的 各种不同形式可以相互转化。因此只需给出其中一 种形式的解法，就可普遍适用于一切形式的LP问 题。 第一节 线性规划问题及其数学模型
第一节线性规划问题及其数学模型 般LP问题的标准形为： m心Z=cX1+C2x2+.+Cr'n (1-3) a11X1+a12X2+.+a1mXn =b1 a2x+a22x2 +.+a2n =b2 1-4) amx+am2X2+.+amnxn =bm X X22.,Xn ≥0 19
19 一般LP问题的标准形为: max Z = c1x1 + c2 x2 + . + cn xn (1-3) + ++ = + ++ = + ++ = 1 2 0 1 1 2 2 2 1 1 2 2 2 2 2 1 1 1 1 2 2 1 1 n m m m n n m n n n n x x x a x a x a x b a x a x a x b a x a x a x b ， ， ， (1-4) 第一节 线性规划问题及其数学模型
第一节线性规划问题及其数学模型 或简记为： max Z- ∑cx, j=1 ∑a,=h,i=l2,.,m Xj≥0j=1,2,.,n 20
20 = = n j j j Z c x 1 max 或简记为: = = = = x j n a x b i m j n j i j j i 0 1,2, , , 1,2, , 1 第一节 线性规划问题及其数学模型
第一节线性规划问题及其数学模型 上式还可记为矩连形式： max CTX AX=b X≥0 其中 0 A= 0 02 02n X= 2 b= C= a n Xn 21
21 上式还可记为矩阵形式: max Z = CTX = X 0 AX b 其中 = = = = m m m n n m n n n c c c C b b b b x x x X a a a a a a a a a A 2 1 2 1 2 1 1 2 2 1 2 2 2 1 1 1 2 1 , , , 第一节 线性规划问题及其数学模型
第一节线性规划问题及其数学模型 矩阵A为约束方程组(1-4)中线性方程组的 系数矩阵。r(A)=m<n,即A为满秩矩阵。称m 为LP的阶数，n为LP的维数。 规定： 右端向量b大于等于0，即b20(i=1,2,m)。 对不符合标准形式（或称非标准形式）的线性 规划问题，可分别通过下列方法化为标准形式。 22
22 矩阵A为约束方程组（1-4）中线性方程组的 系数矩阵。r(A) = m<n，即A为满秩矩阵。称m 为LP的阶数，n为LP的维数。 规定： 右端向量b大于等于0，即bi≥0 (i = 1,2,.,m)。 对不符合标准形式(或称非标准形式)的线性 规划问题，可分别通过下列方法化为标准形式。 第一节 线性规划问题及其数学模型