第1章线性规划基本模型

1、管管 理理 运运 筹筹 学学管管 理理 运运 筹筹 学学赵明霞赵明霞山西大学经济与管理学院山西大学经济与管理学院管理运筹学管理运筹学 模型与方法模型与方法管管 理理 运运 筹筹 学学第第1 1章线性规划基本模型章线性规划基本模型1.11.1线性规划的实用模型线性规划的实用模型1.21.2线性规划的一般模型线性规划的一般模型1.31.3线性规划的图解法线性规划的图解法1.41.4标准形线性规划的解标准形线性规划的解2022-3-72管管 理理 运运 筹筹 学学1.1线性规划的实用模型线性规划的实用模型2022-3-73线性规划线性规划(LP, Linear Programming)(LP, Li

2、near Programming)的组成的组成：目标函数目标函数 opt（optimize） max z (f) 或或 min z(f)约束条件约束条件 s.t. (subject to) 满足于满足于决策变量决策变量 用符号来表示可控制的因素用符号来表示可控制的因素u资源分配模型资源分配模型u产品配套模型产品配套模型u下料模型下料模型u配料模型配料模型管管 理理 运运 筹筹 学学2022-3-74例例1.0 1.0 某工厂在计划期内要安排某工厂在计划期内要安排、两种产品的生产，两种产品的生产，已知生产单位产品所需的设备台时及已知生产单位产品所需的设备台时及A A、B B两种原材料的消两种原材

3、料的消耗、资源的限制，如下表：耗、资源的限制，如下表：问题：工厂应分别生产多少单位问题：工厂应分别生产多少单位、产品才能使工厂获利产品才能使工厂获利最多？最多？管管 理理 运运 筹筹 学学线性规划模型线性规划模型： max f = 50 x max f = 50 x1 1 + 100 + 100 x x2 2 s.t. x s.t. x1 1 + x + x2 2 300 300 2 x 2 x1 1 + x + x2 2 400 400 x x2 2 250 250 x x1 1 , , x x2 2 0 02022-3-75管管 理理 运运 筹筹 学学线性规划建模过程线性规划建模过程1.1

4、.理解要解决的问题，明确理解要解决的问题，明确目标和条件目标和条件；2.2.定义定义决策变量决策变量（ x x1 1 ，x x2 2 ， ，x xn n ），每一组值表示一个方），每一组值表示一个方案；案；3.3.用决策变量的线性函数形式写出用决策变量的线性函数形式写出目标函数目标函数，确定最大化或最，确定最大化或最小化目标；小化目标；4.4.用一组决策变量的等式或不等式表示解决问题过程中必须遵用一组决策变量的等式或不等式表示解决问题过程中必须遵循的循的约束条件约束条件2022-3-76管管 理理 运运 筹筹 学学资源分配模型资源分配模型2022-3-77例例1-11-1. . 某工厂要安排甲

5、、乙两种产品分别在车间某工厂要安排甲、乙两种产品分别在车间A A、B B生生产，然后都在产，然后都在C C车间装配。生产数据如下表：车间装配。生产数据如下表：问题：工厂应分别生产多少单位甲、乙问题：工厂应分别生产多少单位甲、乙产品？产品？管管 理理 运运 筹筹 学学解：设解：设 变量（单位）变量（单位）2022-3-7812121212max32628. .2318,0zxxxxstxxxx管管 理理 运运 筹筹 学学2022-3-79 例例1.1 1.1 某昼夜服务的公交线路每天各时间段内所需司机某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：和乘务人员数如下： 设司机和乘务人员

6、分别在各时间段一开始时上班，并设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员既能满足工作需要，又配备最少司机和乘务人员? ?管管 理理 运运 筹筹 学学2022-3-710 解：设解：设 x xi i 表示第表示第i i班次时班次时开始上班开始上班的司机和乘务人员的司机和乘务人员数数, , 这样我们建立如下的数学模型。这样我们建立如下的数学模型。 min min x x1 1 + + x x2 2 + + x x3 3 + + x x4 4 + +

7、x x5 5 + + x x6 6 s.t. s.t. x x1 1 + + x x6 6 60 60 x x1 1 + + x x2 2 70 70 x x2 2 + + x x3 3 60 60 x x3 3 + + x x4 4 50 50 x x4 4 + + x x5 5 20 20 x x5 5 + + x x6 6 30 30 x x1 1, ,x x2 2, ,x x3 3, ,x x4 4, ,x x5 5, ,x x6 6 0 0管管 理理 运运 筹筹 学学2022-3-711另另解：设解：设 x xi i ( i = 1,2,( i = 1,2,6),6)表示第表示第1

8、1班次至第班次至第6 6班次班次开始开始休息休息的人数的人数, ,这样我们建立如下的数学模型。这样我们建立如下的数学模型。 min min x x1 1 + + x x2 2 + + x x3 3 + + x x4 4 + + x x5 5 + + x x6 6 s.t. s.t. x x2 2 + + x x3 3 60 60 x x3 3 + + x x4 4 70 70 x x4 4 + + x x5 5 60 60 x x5 5 + + x x6 6 50 50 x x6 6 + + x x1 1 20 20 x x1 1 + + x x2 2 30 30 x x1 1, ,x x2

9、2, ,x x3 3, ,x x4 4, ,x x5 5, ,x x6 6 0 0管管 理理 运运 筹筹 学学2022-3-712 例例1.2 1.2 某公司面临一个是外包协作还是自行生产的问题。某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产

10、品各如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？外包协作各应多少件？管管 理理 运运 筹筹 学学2022-3-713管管 理理 运运 筹筹 学学2022-3-714解：设解：设 x x1 1, ,x x2 2, ,x x3 3 分别为三道工序都由本公司加工的甲、乙、分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，丙三种产品的件数，x x4 4, ,x x5 5 分别为由外协铸造再由本公司分别为由外协铸造再由本公司加工和装配的甲、乙两种产品的件数。加工和装配

11、的甲、乙两种产品的件数。max 15max 15x x1 1 + 10 + 10 x x2 2 + 7 + 7x x3 3 + 13 + 13x x4 4 + 9 + 9x x5 5 s.t. 5s.t. 5x x1 1 + 10 + 10 x x2 2 + 7 + 7x x3 3 8000 8000 6 6x x1 1 + 4 + 4x x2 2 + 8 + 8x x3 3 + 6 + 6x x4 4 + 4 + 4x x5 5 12000 12000 3 3x x1 1 + 2 + 2x x2 2 + 2 + 2x x3 3 + 3 + 3x x4 4 + 2 + 2x x5 5 1000

12、0 10000 x x1 1, ,x x2 2, ,x x3 3, ,x x4 4, ,x x5 5 0 0管管 理理 运运 筹筹 学学2022-3-715例例1.3 1.3 永久机械厂生产永久机械厂生产、三种产品，均要经过三种产品，均要经过A A、B B 两道工序加工。假设有两种规格的设备两道工序加工。假设有两种规格的设备A A1 1、A A2 2能完成能完成 A A 工工序；有三种规格的设备序；有三种规格的设备B B1 1、B B2 2、B B3 3能完成能完成 B B 工序。工序。可在可在A A、B B的任何规格的设备上加工；的任何规格的设备上加工； 可在任意规格的可在任意规格的A A设

13、备上加设备上加工，但对工，但对B B工序，只能在工序，只能在B B1 1设备上加工；设备上加工；只能在只能在A A2 2与与B B2 2设设备上加工；数据如下表。问：为使该厂获得最大利润，应备上加工；数据如下表。问：为使该厂获得最大利润，应如何制定产品加工方案？如何制定产品加工方案？管管 理理 运运 筹筹 学学2022-3-716管管 理理 运运 筹筹 学学2022-3-717解：设解：设 x xijkijk 表示第表示第 i i 种产品，在第种产品，在第 j j 种工序上的第种工序上的第 k k 种设备上加工的种设备上加工的数量。数量。max max f=0.75f=0.75x x11111

14、1+0.79+0.79x x112112-0.36-0.36x x121121-0.44-0.44x x122122-0.35-0.35x x123123 +1.15+1.15x x211211+1.38+1.38x x212212-0.48-0.48x x221221+1.94+1.94x x312312-1.21-1.21x x322322 s.t. 5 s.t. 5x x111111 + 10 + 10 x x211 211 6000 6000 （ 设备设备 A A1 1 ） 7 7x x112112 + 9 + 9x x212212 + 12 + 12x x312312 10000 1

15、0000 （ 设备设备 A A2 2 ） 6 6x x121121 + 8 + 8x x221221 4000 4000 （ 设备设备 B B1 1 ） 4 4x x122122 + 11 + 11x x322322 7000 7000 （ 设备设备 B B2 2 ） 7 7x x123123 4000 4000 （ 设备设备 B B3 3 ） x x111111+ + x x112112= = x x121121+ +x x122122+ +x x123123（产品在产品在A A、B B工序加工的数量相等）工序加工的数量相等） x x211211+ + x x212212= =x x2212

16、21 （产品在产品在A A、B B工序加工的数工序加工的数量相等）量相等） x x312 312 = = x x322322 （产品在产品在A A、B B工序加工工序加工的数量相等）的数量相等） x xijkijk 0 , i = 1,2,3; j = 1,2; k = 1,2,3 0 , i = 1,2,3; j = 1,2; k = 1,2,3管管 理理 运运 筹筹 学学产品配套模型产品配套模型例例1-21-2. . 某厂生产一种部件，由某厂生产一种部件，由3 3个个A A零件和零件和5 5个个B B零件配套组零件配套组装成品。该厂有甲、乙、丙三种机床可加工装成品。该厂有甲、乙、丙三种机床

17、可加工A A、B B两种零件，两种零件，数据见下表。则应如何安排生产？数据见下表。则应如何安排生产？2022-3-718管管 理理 运运 筹筹 学学2022-3-7190,53430273352524030. .max322212312111323122211211fxxxxfxxxfxxxxxxtsfij解：设解：设xij为为i机床生产机床生产j零件的件数零件的件数管管 理理 运运 筹筹 学学下料模型下料模型例例1-31-3. . 某项管网工程，要用某一口径的管材，其原材长某项管网工程，要用某一口径的管材，其原材长5m5m，但用材的长度、数量不尽相同，见下表。应如何下料，但用材的长度、数量不

18、尽相同，见下表。应如何下料才能耗材最省？才能耗材最省？2022-3-720管管 理理 运运 筹筹 学学2022-3-7211 12 23 34 45 5A(2.6)A(2.6)1 10 01 10 00 0B(1.8)B(1.8)0 02 21 10 01 1C(1.1)C(1.1)2 21 10 04 42 2余余0.20.20.30.30.60.60.60.61.01.0管管 理理 运运 筹筹 学学2022-3-72203602422002150. .min54215323154321ixxxxxxxxxxtsxxxxxf解：设解：设xi为按方案为按方案i下料下料的根数的根数管管 理理 运

19、运 筹筹 学学2022-3-723注意注意：在建立此类型数学模型时，约束条件用：在建立此类型数学模型时，约束条件用大于大于等于号等于号比用等于号要好。因为有时在套用一些下料比用等于号要好。因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这一方案就不是可行是最优方案。如果用等于号，这一方案就不是可行解了。解了。管管 理理 运运 筹筹 学学配料模型配料模型例例1-41-4. . 某食品厂拟用某食品厂拟用A A，B B两种紧俏原料和一种普通原料两种紧俏原料和一种普通原料C C，加工制作甲、乙、丙三种食品。如表所示

20、。应如何为，加工制作甲、乙、丙三种食品。如表所示。应如何为三种食品配料？三种食品配料？2022-3-724管管 理理 运运 筹筹 学学2022-3-725解：设解：设xij为为i食品含原料食品含原料j的量的量(kg)06 .04 .02 .06 .03 .05 .060100. .265368max313333133131222312213111231111312311313312311313312311ijjjjjjjjjjjjjiiiiiiiiiijjjjjjxxxxxxxxxxxxxxxtsxxxxxxf管管 理理 运运 筹筹 学学2022-3-7261.2 线性规划的一般模型线性规划的

21、一般模型1 12211 1122111 122jopt () . .() nnnnmmmnnmZc xc xc xa xa xa xbsta xa xa xbx （ ）0， 或自由通式通式管管 理理 运运 筹筹 学学2022-3-72711 opt Z () (i1 2) s.t. ( )0 (j 1 2)njjjnijjijjc xa xbmxn 管管 理理 运运 筹筹 学学2022-3-728 nxxX111111jnmmjmnaaaAaaa mbbb1opt () . .0TZCXAXbs tX （）nccC1管管 理理 运运 筹筹 学学解的概念解的概念可行解可行解满足约束条件的解满足约

22、束条件的解2022-3-729 最优解最优解是目标值最优的可行解是目标值最优的可行解*22*11*2*1*),(nnTnxcxcxczxxxX管管 理理 运运 筹筹 学学2022-3-7301 12211 1122111 122jmaxmin = . . = 0nnnnmmmnnmzc xc xc xa xa xa xbsta xa xa xbx（）标准形标准形M1管管 理理 运运 筹筹 学学2022-3-73111jmaxmin z = (1,2, ). .0 njjjnijjijc xa xb imstx（）M2管管 理理 运运 筹筹 学学2022-3-732maxmin = . .0 T

23、zC XAXbs tX（）M3管管 理理 运运 筹筹 学学 可以看出，线性规划的标准形式有如下可以看出，线性规划的标准形式有如下特点特点：目标最大化；（注：无要求，但为了单纯形表的目标最大化；（注：无要求，但为了单纯形表的统一解法，作最大化统一；亦可统一为最小化）统一解法，作最大化统一；亦可统一为最小化）约束为等式；约束为等式；决策变量均非负；决策变量均非负；右端项（常数项）非负。右端项（常数项）非负。 对于各种非标准形式的线性规划问题，我们总可对于各种非标准形式的线性规划问题，我们总可以通过变换将其转化为标准形式。以通过变换将其转化为标准形式。2022-3-733线性规划的标准化线性规划的标

24、准化管管 理理 运运 筹筹 学学1.1.极小化目标函数的问题：极小化目标函数的问题： 设目标函数为设目标函数为 min f = c1x1 + c2x2 + + cnxn ( (可以可以) )令令 z z -f-f ， 则该极小化问题与下面的极大化问题有相同的最优解，即则该极小化问题与下面的极大化问题有相同的最优解，即 max z = - c1x1 - c2x2 - - cnxn 但必须注意，尽管以上两个问题的最优解相同，但它们最但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即优解的目标函数值却相差一个符号，即 min f - max z2022-3-734管

25、管 理理 运运 筹筹 学学2 2、约束条件不是等式的问题、约束条件不是等式的问题：约束条件为约束条件为 ai1 x1+ai2 x2+ +ain xn bi 可以引进一个新的可以引进一个新的松弛变量松弛变量xn+1 ，使它等于约束右边与左，使它等于约束右边与左边之差边之差 xn+1=bi(ai1 x1 + ai2 x2 + + ain xn )显然，显然， xn+1也具有非负约束，即也具有非负约束，即xn+1 00，这时新的约束条件成，这时新的约束条件成为为 ai1 x1+ai2 x2+ +ain xn+ xn+1 = bi2022-3-735管管 理理 运运 筹筹 学学约束条件为约束条件为 a

26、i1 x1+ai2 x2+ +ain xn bi 时，时， 类似地令类似地令剩余变量剩余变量 xn+1 =(ai1 x1+ai2 x2+ +ain xn)- bi 显然，显然， xn+1也具有非负约束，即也具有非负约束，即xn+1 00，这时新的约束条件，这时新的约束条件成为成为 ai1 x1+ai2 x2+ +ain xn- xn+1 = bi2022-3-736管管 理理 运运 筹筹 学学2022-3-737 为了使约束由不等式成为等式而引进的为了使约束由不等式成为等式而引进的变量变量xn+1, ,当当不等式为不等式为“小于等于小于等于” ” 称为称为“松弛变量松弛变量”；当当不等式为不等

27、式为“大于等于大于等于”时称为时时称为时“剩余变量剩余变量”。 如果如果原问题中有若干个非等式约束，则将其转化原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的变量。为标准形式时，必须对各个约束引进不同的变量。 管管 理理 运运 筹筹 学学2022-3-7383.3.右端项有负值的问题：右端项有负值的问题： 在标准形式中，要求右端项必须每一个分量非负。当某一个在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如右端项系数为负时，如 bi00，则把该等式约束两端同时乘以，则把该等式约束两端同时乘以-1-1，得到得到： -ai1 x1-ai2 x2-

28、-ain xn = -bi4 4、变量无符号限制的变量无符号限制的问题问题： 在标准形式中，必须每一个变量均有非负约束。当某一个变在标准形式中，必须每一个变量均有非负约束。当某一个变量量xj没有没有非负约束时，可以令非负约束时，可以令 xj = xj- xj” 其中其中 xj0，xj”0 即用两个非负变量之差来表示一个无符号限制的变量，当然即用两个非负变量之差来表示一个无符号限制的变量，当然xj的的符号取决于符号取决于xj和和xj”的大小。的大小。管管 理理 运运 筹筹 学学例例1-6 1-6 将以下线性规划问题转化为标准形式将以下线性规划问题转化为标准形式 min z = 2 x1 -x2

29、+3x - x4 s.t. 2x1 + x2 - 3 x3 + x4 3 3x1 -2x2 + x3 - x4 2 -x1 -3x2 + 2x3 - x4 -1 x2 0, x3 0 2022-3-739管管 理理 运运 筹筹 学学2022-3-740线性规划的典式线性规划的典式njxbxaxaxbxaxaxbxaxaxtsxcxcxczjmnmnmmmmnnmmnnmmnn, 2 , 1, 0. .max(min)11,2211,221111, 112211标准形为标准形为典式的充要条件典式的充要条件：系数矩阵中存在一个满秩单位阵。：系数矩阵中存在一个满秩单位阵。典式标准形是单纯形法的唯一必

30、要前提。典式标准形是单纯形法的唯一必要前提。管管 理理 运运 筹筹 学学2022-3-741线性规划问题的求解方法线性规划问题的求解方法一般有一般有两种方法两种方法图图 解解 法法单纯形法单纯形法两个变量、直角坐标两个变量、直角坐标三个变量、立体坐标三个变量、立体坐标适用于任意变量、但需将适用于任意变量、但需将一般形式一般形式变成典式变成典式1.3线性规划的图线性规划的图 解解 法法管管 理理 运运 筹筹 学学2022-3-74212121212max32628. .2318,0zxxxxstxxxx例例1-7唯一解唯一解管管 理理 运运 筹筹 学学2022-3-743无界解无界解无可行解无可

31、行解无穷多解无穷多解管管 理理 运运 筹筹 学学重要结论：重要结论：如果线性规划有如果线性规划有最优解最优解，则一定有一个可行域的顶点对应一个，则一定有一个可行域的顶点对应一个最优解；最优解；无穷多个最优解无穷多个最优解。若将。若将例例1-71-7中的目标函数变为中的目标函数变为max z=2x1+3x2，则线段则线段BCBC上的所有点都代表了最优解；上的所有点都代表了最优解；无界解无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束

32、条件；约束条件；无可行解无可行解。若在。若在例例1-71-7的数学模型中再增加一个约束条件的数学模型中再增加一个约束条件x x1 1+x+x2 21010，则可行域为空域，不存在满足约束条件的解，当，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。然也就不存在最优解了。2022-3-744管管 理理 运运 筹筹 学学2022-3-745可行解可行解：满足约束条件和非负条件的决策变量的一组取值。：满足约束条件和非负条件的决策变量的一组取值。可行解集可行解集：所有可行解的集合。：所有可行解的集合。可行域可行域：LPLP问题可行解集构成问题可行解集构成n n维空间的区域，可以表示为：

33、维空间的区域，可以表示为：0,|XbAXXD最优解最优解: :使目标函数达到最优值的可行解。使目标函数达到最优值的可行解。最优值最优值：最优解对应目标函数的取值。：最优解对应目标函数的取值。求解求解LPLP问题问题: :求出问题的最优解和最优值。求出问题的最优解和最优值。管管 理理 运运 筹筹 学学1.4标准形线性规划的解标准形线性规划的解基本概念基本概念基本性质基本性质2022-3-746管管 理理 运运 筹筹 学学基本概念基本概念基本解基本解基（矩阵）基（矩阵）基变量基变量最优基本解最优基本解基本可行解基本可行解最优基本解最优基本解可行基、最优基可行基、最优基退化基本（可行）解退化基本（可

34、行）解凸性凸性凸组合凸组合凸集凸集极点极点2022-3-747管管 理理 运运 筹筹 学学2022-3-748基本解的概念只适用于标准形线性规划基本解的概念只适用于标准形线性规划例例1-1 1-1 在加上松弛变量之后我们可得到标准形如下：在加上松弛变量之后我们可得到标准形如下： max 3x max 3x1 1+ 2x+ 2x2 2 (1-4a) (1-4a) s.t. x s.t. x1 1 +x +x3 3 =6=6 2x 2x2 2 +x+x4 4 =8=8 (1-4b)(1-4b) 2x2x1 1+3x+3x2 2 +x+x5 5=18=18 x xj j0 0 （j=1,2,3,4,

35、5j=1,2,3,4,5） (1-4c)(1-4c)基本解基本解管管 理理 运运 筹筹 学学2022-3-749它的它的系数矩阵系数矩阵aj为系数矩阵为系数矩阵A第第j列的向量。列的向量。A的秩的秩R(A)=35=35,A,A的秩小于此方程组的秩小于此方程组(1-4b)(1-4b)的变量的个数，方程组的变量的个数，方程组(1-4b)(1-4b)有有无穷多解无穷多解。其中，单位阵其中，单位阵 为该为该线性规划问题中的一个线性规划问题中的一个基基。a3, a4, a5为为基向量基向量，a1, a2为为非基向量非基向量；x3, x4, x5为为基变量基变量，x1, x2为为非基变量。非基变量。令令x

36、1=x2=0=0, ,可得可得x3=6,x4=8, ,x5=18, ,得得方程组方程组(1-4b)(1-4b)的一个特解的一个特解 为为该该线性规划的一个线性规划的一个基本解基本解。1234510100(,)0201023001Aaaaaa1x2x3x4x5x12345=TX （x ,x ,x ,x ,x ）1345=a ,a ,a B0=0 0 6818TX（ , , , ）管管 理理 运运 筹筹 学学设设 是满秩阵，且是满秩阵，且R(A)=mnR(A)=mn，系数阵，系数阵则有：则有：设设B B为为A A的一个的一个m m阶子矩阵，若阶子矩阵，若 , ,则则B B为方程组为方程组(1-5b

37、)(1-5b)或线性规划（或线性规划（1-51-5）的一个）的一个基矩阵基矩阵，简称一个，简称一个基基。设基矩阵设基矩阵 则则B B中中m m个向量个向量a a1 1,a,a2 2,a,am m为为基向量基向量，其余，其余n-mn-m个向量个向量 为为非基向量非基向量。x1,x2,xm为为（以（以B B为基的）基变量为基的）基变量，其余为，其余为（以（以B B为基的）非基变量为基的）非基变量。所有基变量构成的向量所有基变量构成的向量X XB B为为基变矢基变矢，所有非基变量构成的向量，所有非基变量构成的向量X XN N为为非基变非基变矢。矢。2022-3-750=ij m nA（a ）12=a

38、 ,a ,a ,a mnA0B m axm in = . .0 TzCXA Xbs tX（）(1-5c)(1-5a)(1-5b),.,2,maaaB1,.,2,nmaaaNm1,NBA BNXXX,BNBNXB NbXBXNXb管管 理理 运运 筹筹 学学令令X XN N=0=0，则，则BXBXB B=b=b，得特解，得特解 为一个为一个以以B B为基的基为基的基本解本解，简称，简称基本解基本解。基本可行解基本可行解：既是基本解，又是可行解。满足非负性约束的基本解。：既是基本解，又是可行解。满足非负性约束的基本解。例例1-11-1中，以中，以 为基的基本解为基的基本解 为基本可行解。为基本可行解。另有另有 为基本解，但不是基本可为基本解，但不是基本可行解。行解。 为基本可行解。为基本可行解。最优基本解最优基本解：使目标值最优的基本可行解。：使目标值最优的基本可行解。可行基可行基：基本可行解对应的基。：基本可行解对应的基。最优基最优基：最优基本解对应的基。：最优基本解对应的基。退化基本（可行）解退化基本（可行）解：基本（可行）解中，有一个或多个基变量取：基本（可行）解中，有一个或多个