第1章线性规划基本模型

1、山西大学经济与管理学院山西大学经济与管理学院主讲：范建平主讲：范建平 博士博士运筹学山西大学经济与管理学院山西大学经济与管理学院第一章 线性规划基本模型1.1 线性规划的实用模型2022年6月10日星期五山西大学经济与管理学院 范建平3在管理中一些典型的线性规划应用4p合理利用线材问题合理利用线材问题：如何在保证生产的条件下，下料最少：如何在保证生产的条件下，下料最少p配料问题配料问题：在原料供应量的限制下如何获取最大利润：在原料供应量的限制下如何获取最大利润p投资问题投资问题：从投资项目中选取方案，使投资回报最大：从投资项目中选取方案，使投资回报最大p产品生产计划产品生产计划：合理利用人力、

2、物力、财力等，使获利最大：合理利用人力、物力、财力等，使获利最大p劳动力安排劳动力安排：用最少的劳动力来满足工作的需要：用最少的劳动力来满足工作的需要p运输问题运输问题：如何制定调运方案，使总运费最小：如何制定调运方案，使总运费最小2022年6月10日星期五山西大学经济与管理学院 范建平1、资源分配模型p 例例1.1 某装配厂拟生产甲、乙两种新产品，每件利润分某装配厂拟生产甲、乙两种新产品，每件利润分别为别为300元和元和200元。甲、乙产品的部件分别在元。甲、乙产品的部件分别在A、B两个两个车间生产，每件甲、乙产品的部件分别消耗车间生产，每件甲、乙产品的部件分别消耗A、B车间车间1、2工时。

3、两种产品的部件最后都要在工时。两种产品的部件最后都要在C车间装配，装配每车间装配，装配每件甲、乙产品分别消耗件甲、乙产品分别消耗2工时和工时和3工时。已知工时。已知A，B，C三三个车间每周可用于这两种产品的最大生产能力分别为个车间每周可用于这两种产品的最大生产能力分别为6工工时、时、8工时、工时、18工时，则每周各生产甲、乙产品多少件？工时，则每周各生产甲、乙产品多少件？试建立该问题的数学模型。试建立该问题的数学模型。2022年6月10日星期五5山西大学经济与管理学院 范建平解：p 列出数据表 产品产品车间车间单耗单耗/ /（工时（工时/ /件）件）最大生产能力最大生产能力/(/(工时工时/

4、/周周) )甲乙A106B028C2318利润/（1100元/件）321、资源分配模型2022年6月10日星期五6山西大学经济与管理学院 范建平1、资源分配模型设设 x1, x2 分别为甲、乙产品的周产量（分别为甲、乙产品的周产量（决策变量决策变量） z为这两种产品每周的总利润，则由于，z取值受限于x1, x2 ，而x1, x2 受限于A，B，C三个车间的生产能力，则 式（0）称为目标函数目标函数，z为目标值目标值 产品产品车间车间单耗单耗/ /（工时（工时/ /件）件）最大生产能力最大生产能力/(/(工时工时/ /周周) )甲乙A106B028C2318利润/（1100元/件）32 1232

5、0zxx1212121060282318xxxxxx约束条件2022年6月10日星期五7山西大学经济与管理学院 范建平1、资源分配模型p上述函数约束和非负性约束，统称为约束条件或约束方程，上述函数约束和非负性约束，统称为约束条件或约束方程，简称简称约束约束。p综上所述，例题综上所述，例题1.1的数学模型简记如下：的数学模型简记如下：又因产量x1, x2 取值不能为负，则非负性约束非负性约束120,0 xx 12121212max3201628. .2318,0zxxxxstxxxx2022年6月10日星期五8山西大学经济与管理学院 范建平1、资源分配模型小结p由目标函数和约束方程构成的一组数学

6、表达式，称为由目标函数和约束方程构成的一组数学表达式，称为数数学规划学规划（模型）；（模型）；p若全为线性表达式，则称为若全为线性表达式，则称为线性规划线性规划（模型）；（模型）；p若组中有一个或更多表达式非线性，则称为若组中有一个或更多表达式非线性，则称为非线性规划非线性规划（模型）。（模型）。2022年6月10日星期五9山西大学经济与管理学院 范建平线性规划的三个要素10p决策变量决策变量n决策问题待定的量值决策问题待定的量值n取值要求非负取值要求非负p约束条件约束条件n任何管理决策问题都是限定在一定的条件下求解任何管理决策问题都是限定在一定的条件下求解n把各种限制条件表示为一组等式或不等

7、式称约束条件把各种限制条件表示为一组等式或不等式称约束条件n约束条件是决策方案可行的保障约束条件是决策方案可行的保障n约束条件是决策变量的约束条件是决策变量的线性函数线性函数p目标函数目标函数n衡量决策优劣的准则，如时间最省、利润最大、成本最低衡量决策优劣的准则，如时间最省、利润最大、成本最低n目标函数是决策变量的目标函数是决策变量的线性函数线性函数n有的目标要实现极大，有的则要求极小有的目标要实现极大，有的则要求极小2022年6月10日星期五山西大学经济与管理学院 范建平1、资源分配模型小结p小结小结：对于例题：对于例题1.1的资源分配问题（的资源分配问题（经营规划问题经营规划问题），），一

8、般可表述为：一般可表述为：n某企业拟将现有的某企业拟将现有的m种资源（用种资源（用i=1,2，m表示）投入表示）投入n项生产或商务活动（用项生产或商务活动（用j=1，2，n表示）。其表示）。其中第中第i种资种资源的数量为源的数量为bi，项目，项目j每经营每经营1个单位所创造的利润（或价值）个单位所创造的利润（或价值）为为cj，所消耗的第，所消耗的第i种资源的数量为种资源的数量为aij。为履行合同，项目。为履行合同，项目j的经营数量至少为的经营数量至少为ej；而市场调查，其最高需求量为；而市场调查，其最高需求量为dj。试。试建立其数学模型。建立其数学模型。2022年6月10日星期五11山西大学经

9、济与管理学院 范建平1、资源分配模型小结p建立线性规划模型的一般步骤：建立线性规划模型的一般步骤：p1.正确设立决策变量正确设立决策变量n设设xj（j=1,2,n）为项目）为项目j的经营数量。的经营数量。p2.恰当建立目标函数恰当建立目标函数nn项经营活动的总利润（或总产值，总收入）为项经营活动的总利润（或总产值，总收入）为p3. 适度构建约束方程适度构建约束方程n（1）合同约束）合同约束n（2）需求约束）需求约束n（3）资源约束）资源约束1njjjzc x1,2,jjxejn1,2,jjxdjn11,2,nijjija xbim2022年6月10日星期五12山西大学经济与管理学院 范建平1、

10、资源分配模型小结p综上所述可得综上所述可得LP模型如下：模型如下：11max1,2,. .1,2,1,2,njjjnijjijjjjjzc xa xbimstxejnxdjn2022年6月10日星期五13山西大学经济与管理学院 范建平2、产品配套模型p 例例1.2某厂生产一种部件，由某厂生产一种部件，由3个个A零件和零件和5个个B零件配套零件配套组装成品。该厂有甲、乙、丙三种机床可加工组装成品。该厂有甲、乙、丙三种机床可加工A，B两种两种零件，每种机床的台数，以及每台机床每个工作日全部零件，每种机床的台数，以及每台机床每个工作日全部用于加工某一种零件的最大产量（即生产率：件用于加工某一种零件的

11、最大产量（即生产率：件/日）见日）见表表1-2。则应如何安排生产？试建立其数学模型。则应如何安排生产？试建立其数学模型。机床种类机床种类现有数量现有数量/ /台台每台机床生产率每台机床生产率/ /（件（件/ /日）日）A零件B零件甲23040乙32535丙42730表1-22022年6月10日星期五14山西大学经济与管理学院 范建平2、产品配套模型p求解本题，不能单纯追求两种零件的总产量达到最大，求解本题，不能单纯追求两种零件的总产量达到最大，而应要求每个工作日按而应要求每个工作日按3:5的比例生产出来的的比例生产出来的A，B两零两零件的套数达到最大。件的套数达到最大。1. 决策变量： 2.

12、约束条件： （1）工时约束1,2,3;1,2A,B3:5ijijzxij设表示机床 每个工；为两种零件按作日加工零件 的时间（单位：工的比例配套的数量作日）（套 日）111221223132111xxxxxx2022年6月10日星期五15山西大学经济与管理学院 范建平2、产品配套模型2022年6月10日星期五山西大学经济与管理学院 范建平16p（2）配套约束）配套约束(表表1.3)机床种类机床种类每种机床生产率每种机床生产率/(/(件件/ /日日) )A A零件零件B B零件零件甲6080乙75105丙108120表表1-3 每台机床的生产率每台机床的生产率112131122232min607

13、51083, 801051205zxxxxxx2、产品配套模型2022年6月10日星期五山西大学经济与管理学院 范建平17p非线性约束等价转换非线性约束等价转换1121311221321121311221326075108/380105120/520253601621240zxxxzxxxzxxxzxxx即2、产品配套模型2022年6月10日星期五山西大学经济与管理学院 范建平18pLP模型如下：模型如下：112131122132111221223132max202536016212401. .110,1,2,3;1,2ijzzxxxzxxxxxstxxxxxij3、下料模型p 例例1.3 某

14、项管网工程，要用某一口径的管材，其原材长某项管网工程，要用某一口径的管材，其原材长5m，但用材的长度、数量不尽相同，见表，但用材的长度、数量不尽相同，见表1-4。应如何。应如何下料才能耗材最省？试建立其数学模下料才能耗材最省？试建立其数学模型。型。用材用材长度长度/m/m需求量需求量/ /根根A2.6150B1.8200C1.1360表1-42022年6月10日星期五19山西大学经济与管理学院 范建平3、下料模型解：首先需要找出全部省料截法(见表1-5) 。（所谓省料截法，这里指一个原材截后的余料长度小于最短的用材C的长度的各种截法） 截法截法j j用材用材一根原材所截各种用材的数量（根）一根

15、原材所截各种用材的数量（根）需求量需求量/ /根根12345A（2.6）11000150B（1.8）10210200C（1.1）02124300余料/m0.60.20.31.00.6表1-52022年6月10日星期五20山西大学经济与管理学院 范建平3、下料模型p设设xj表示第表示第j种截法下料的根数（种截法下料的根数（j=1,2,3,4,5），），z为下料为下料总根数总根数p则则LP模型如下：模型如下： 截法截法j j用材用材一根原材所截各种用材的数量（根）一根原材所截各种用材的数量（根）需求量需求量/ /根根12345A（2.6）11000150B（1.8）10210200C（1.1）02

16、124300余料/m0.60.20.31.00.61234512134234512345min1502200. .224360,0zxxxxxxxxxxstxxxxx x x x x2022年6月10日星期五21山西大学经济与管理学院 范建平4、配料模型p例例1.4 某食品厂拟用某食品厂拟用A，B两种紧俏原料和一种普通原料两种紧俏原料和一种普通原料C，加工制作甲、乙、丙三种食品。食品的规格、加工费、加工制作甲、乙、丙三种食品。食品的规格、加工费、销价，以及原料的购价、供量见表销价，以及原料的购价、供量见表1-6。应如何为三种食。应如何为三种食品配料？试建立其数学模型。品配料？试建立其数学模型。

17、表1-6 原料原料食品食品食物规格（配用的原料所占比率）食物规格（配用的原料所占比率）/%/%食品食品ABC加工费销价甲不少于50不少于30不限210乙不少于60不少于20不限28丙不少于40不限不多于6036原料购价562元/kg供量10060不限Kg/元2022年6月10日星期五22山西大学经济与管理学院 范建平4、配料模型解题要点：解题要点：p决策变量：决策变量：p约束条件：规格约束；原料供应量约束约束条件：规格约束；原料供应量约束p目标函数：总利润目标函数：总利润=总收益总收益-原料总费用原料总费用2022年6月10日星期五23山西大学经济与管理学院 范建平4、配料模型2022年6月1

18、0日星期五山西大学经济与管理学院 范建平24p决策变量：设决策变量：设xij表示每天给食品表示每天给食品i所配用的原料所配用的原料j的数量的数量（kg/天）（天）（i=1,2,3; j=1,2,3） 原原料料j食品食品iA AB BC C甲x11x12x13乙x21x22x23丙x31x32x334、配料模型2022年6月10日星期五山西大学经济与管理学院 范建平25p约束条件约束条件规格约束规格约束1112111213111213212221222321222331333132333132330.5;0.3;0.6;0.2;0.4;0.6;xxxxxxxxxxxxxxxxxxxxxxxx4、

19、配料模型p约束条件约束条件原理供应约束原理供应约束p总总收益收益p原原料总费料总费用用p目标函数目标函数：总利润总利润=总收益总收益-原料总费原料总费用用112131122232A10060Bxxxxxx原料原料 3332312322211312113628210 xxxxxxxxx332313322212312111265xxxxxxxxx2022年6月10日星期五26山西大学经济与管理学院 范建平1112132122233132331121311222321311121321233123323333863-326425-6-2=3xxxxxxxxxxxxxxxxxxxxxxxxxx4、配料

20、模型p综上可得综上可得LP模型如下：模型如下：)3 , 2 , 1; 3 , 2 , 1( , 0601000233022304033203730. .324623max3222123121113332313332312322212322211312111312113332312321131211jixxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxzij2022年6月10日星期五27山西大学经济与管理学院 范建平5、人力资源分配的问题28 班次时间所需人数16：00 10：0060210：00 14：0070314：00 18：0060418：00 22：0050522：

21、00 2：002062：00 6：0030某某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下： 设司机和乘务人员分别在各时间段一开始时上班，并连续工作八设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员又配备最少司机和乘务人员? ?2022年6月10日星期五山西大学经济与管理学院 范建平5、人力资源分配的问题29p解：设解：设 xi 表示第表示第i班次时开始上班的司机和乘务人员数

22、班次时开始上班的司机和乘务人员数,这这样我们建立如下的数学模型。样我们建立如下的数学模型。123456161223344556 123456 60 70 60. . 50 20 30, 0min xxxxxxxxxxxxstxxxxxxx x x x x x2022年6月10日星期五山西大学经济与管理学院 范建平5、人力资源分配的问题时间所需售货员人数星期日28星期一15星期二24星期三25星期四19星期五31星期六28 例例2 2一家中型的百货商场，它对售货员的需求经过统计分析如下表所一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作示。为

23、了保证售货人员充分休息，售货人员每周工作5 5天，休息两天，并要天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？要，又使配备的售货人员的人数最少？2022年6月10日星期五30山西大学经济与管理学院 范建平5、人力资源分配的问题31p 解：设解：设 xi ( i = 1,2,7)表示星期一至日开始休息的人表示星期一至日开始休息的人数数,这样我们建立如下的数学模型。这样我们建立如下的数学模型。1234567123452345634567456715671267123

24、71234 28 15 24. . 25 19 31 28min xxxxxxxxxxxxxxxxxxxxxxstxxxxxxxxxxxxxxxxxxxx2022年6月10日星期五山西大学经济与管理学院 范建平1.2 线性规划的一般模型2022年6月10日星期五32山西大学经济与管理学院 范建平1.2.1 线性规划的通式2022年6月10日星期五山西大学经济与管理学院 范建平33p1.基本概念基本概念p线性规划的通用模型（简称线性规划的通用模型（简称通式通式）1 12211 11221121 1222221 1221 1=1 1. .=01,2,1 1nnnnnnmmmnnmjopt zc x

25、c xc xaa xa xa xba xa xa xbbsta xaxaxbxjnc或或或或，或自由，aij,bi,cj称谓称谓LP模型的模型的参数参数，其中，其中aij称为称为消耗系数消耗系数，bi称为称为右端常数右端常数，cj称为称为价值系数价值系数。1.2.1 线性规划的通式2022年6月10日星期五山西大学经济与管理学院 范建平34p2. 解的概念解的概念（1）可行解）可行解 方程组方程组(1-1b)，(1-1c)的解的解X=(x1,x2,xn)T称为称为LP问题的问题的可可行解行解，其集合称为，其集合称为可行集可行集，或，或可行域可行域，记为，记为: R=X|(1-1b),(1-1c

26、).（2）最优解）最优解 满足满足(1-1a)，即能使目标函数达到最优化的可行解，称为，即能使目标函数达到最优化的可行解，称为LP问题的问题的最优解最优解，简称为解，记为：，简称为解，记为：X*=(x1*,x2 *,xn *)T 它对应的目标函数值称为它对应的目标函数值称为最优值最优值，记为：，记为： z*=c1x1*+c2x2 *+cnxn *1 12211 11221121 1222221 1221 1=. .=01,2,1 11 1nnnnnnmmmnnmjopt zc xc xc xaa xa xa xba xa xa xbsta xaxaxbxbcjn或或或或，或自由，1.2.2 线

27、性规划的标准型2022年6月10日星期五山西大学经济与管理学院 范建平35p单纯形法要求单纯形法要求LP模型必须为下述特定形式（模型必须为下述特定形式（LP标准型标准型）11 12211 11221121 1222221 122:max1 21 2. .01,2,1 2nnnnnnmmmnnmjMzc xc xc xaa xa xa xba xa xa xbbsta xaxaxbxjnc01,2,ibim1.2.2 线性规划的标准型2022年6月10日星期五山西大学经济与管理学院 范建平36pLP标准型标准型也可也可简记简记为：为：211:max1,2,m. .01,2,njjjnijjijj

28、Mzc xa xbistxjn1.2.2 线性规划的标准型2022年6月10日星期五山西大学经济与管理学院 范建平37pLP标准型标准型矩阵向量的形式矩阵向量的形式：3121112111212222212:max. .0=,TTnnnnnmmmnMzC XAXbstXCc ccaaaxbaaaxbAXbxbaaa其中上述标准型的三种形式（M1），（M2），（M3）统称为标准型（问题）M1.2.3 线性规划的标准化2022年6月10日星期五山西大学经济与管理学院 范建平38p实际问题的实际问题的LP模型通常都不是标准型，但可通过等价变模型通常都不是标准型，但可通过等价变换最终都能化成标准型。这类

29、转化工作称为换最终都能化成标准型。这类转化工作称为标准化标准化。p非标准型包括以下几种情况：非标准型包括以下几种情况：n1.min型目标函数型目标函数n2.非标准型约束方程非标准型约束方程n3.取值非正的变量取值非正的变量（1）bi0,两端同乘以-1.（2）某个方程为形式，左端加非负的松弛变量化为等式.（3）某个方程为形式，左端减非负的剩余变量化为等式.松弛变量和剩余变量可统称为松弛变量，其价值系数为0（1）若xk0，只需通过变量代换 xk=-xk 则 xk 0，用以取代 xk，即可符合标准.（2）若xk为自由变量（可正，可负，可0），只需通过变量 代换. xk=xk -xk ,且 xk ,

30、xk 0 用以xk -xk 取代 xk，即可符合标准.（3）当有多个自由变量xj时，为避免无谓增加变量个数，可令xj=xj -x , x 对其所在式中的一切j都是同一个变量。例1-5 将（例1-1）问题化为标准型2022年6月10日星期五山西大学经济与管理学院 范建平39 12121212max320161282. .23183,04zxxxxstxxxx 产品产品车间车间单耗单耗/ /（工时（工时/ /件）件）最大生产能力最大生产能力/(/(工时工时/ /周周) )甲乙A106B028C2318利润/（1100元/件）32例1-5 将（例1-1）问题化为标准型2022年6月10日星期五山西大

31、学经济与管理学院 范建平40p将将(1)、(2)、(3)式加上松弛变量，化为等式即可式加上松弛变量，化为等式即可12345132412512345max32+0001628. .2318,0zxxxxxxxxxstxxxx x x x x例1-6 将下述LP问题化为标准型2022年6月10日星期五山西大学经济与管理学院 范建平41 123412341234123423min23023313222. .32130,04zxxxxxxxxxxxxstxxxxxx 123412345123461234723567max2323+ 3322. .3210,0zxxxxxxxxxxxxxxstxxxxx

32、xx x x x 例1-6 将下述LP问题化为标准型2022年6月10日星期五山西大学经济与管理学院 范建平4211123411234511234611234711234567max23233+ 33222. .2321,0zxxxxxxxxxxxxxxxxxstxxxxxxxxxx x x x x1122,01,4 ;=- ;jjjxxxxxjxx令且 ，再令 分别代入上式，即可得原问题的标准型：1.2.4 线性规划的典式2022年6月10日星期五山西大学经济与管理学院 范建平43p标准化是单纯形法的预备步骤，还需化成下述标准化是单纯形法的预备步骤，还需化成下述典式，典式，才才能用单纯形方法

33、能用单纯形方法1 12211,111122,1122,11max. .1 301,2,nnmmnnmmnnmm mmmnnmjzc xc xc xxaxa xbxaxa xbstxaxaxbxjn2022年6月10日星期五山西大学经济与管理学院 范建平44p方程组（方程组（1-3）的系数矩阵为）的系数矩阵为1,112,12m,1100010001mnmnmmnaaaaaa（1）标准型（）标准型（M）为典）为典式的充要条件是：在其函式的充要条件是：在其函数约束方程组的系数矩阵数约束方程组的系数矩阵中，存在一个满秩排列阵，中，存在一个满秩排列阵，即每行每列仅有一个元素即每行每列仅有一个元素为为1，

34、其他元素全为，其他元素全为0的的m阶方阵。阶方阵。（2）LP问题的标准型多问题的标准型多为非典式，将标准型转化为非典式，将标准型转化为典式需要加人工变量为典式需要加人工变量1.3 线性规划的图解法2022年6月10日星期五山西大学经济与管理学院 范建平45p1.3.1 基本步骤基本步骤n1.建立平面直角坐标系建立平面直角坐标系n2.画出可行域画出可行域n3.画出目标函数等值线及其法线画出目标函数等值线及其法线n4.平移目标函数等值线，确定问题的解平移目标函数等值线，确定问题的解【例1-7】 用图解法求范例的的LP问题2022年6月10日星期五山西大学经济与管理学院 范建平46 12121212

35、max3201628. .2318,0zxxxxstxxxxD(0,4)A(6,0)O(0,0)x1=62x2=8x1x2G(0,6)E(9,0)F(6,4)C(3,4)B(6,2)【例1-7】 用图解法求范例的的LP问题2022年6月10日星期五山西大学经济与管理学院 范建平47 12121212max3201628. .2318,0zxxxxstxxxxD(0,4)A(6,0)O(0,0)x1x2C(3,4)B(6,2)z法向z*=22 沿着法线方向平行移动目标函数等值线，当与可沿着法线方向平行移动目标函数等值线，当与可行域相切时，恰在边界点行域相切时，恰在边界点B处，处，B点就是最优点，

36、其坐点就是最优点，其坐标（标（6,2）就是最优解，代入目标函数，得最优值）就是最优解，代入目标函数，得最优值z=22.1.3.2 求解结果2022年6月10日星期五山西大学经济与管理学院 范建平48p1. 唯一解唯一解n如范例，只有一个最优解如范例，只有一个最优解Bp2.多重解多重解n【例例1-8】若将范例的目标函数改为若将范例的目标函数改为: z=3x1+4.5x2D(0,4)A(6,0)O(0,0)x1x2C(3,4)B(6,2)z法向z*=271.3.2 求解结果2022年6月10日星期五山西大学经济与管理学院 范建平49p3. 解无界解无界n【例例1-9】求解下列求解下列LP问题问题1

37、2121212max322+2. . -+ 23,0zxxxxstxxxxO(0,0)x1x2z法向R2022年6月10日星期五山西大学经济与管理学院 范建平50p4. 无可行解无可行解n【例例1-10】考虑范例考虑范例, 若该厂从产量管理上规定，甲、乙两若该厂从产量管理上规定，甲、乙两种产品每周总量不低于种产品每周总量不低于10件，试就此做出分析。件，试就此做出分析。1212121212max321628. . 23181110,0zxxxxstxxxxxxG(0,6)O(0,0)x1x2 x1+x210 2x1+3x218R=E(9,0)1.4 标准线性规划的解2022年6月10日星期五山

38、西大学经济与管理学院 范建平51p1.基本解基本解12132412512345max321 416281 4. .2318,01 4zxxaxxxxbstxxxx x x x xc123451234510 10 00 2 01 02 3 00 1xxxxxAa aaaa0345Baaap其系数矩阵为：其系数矩阵为：12345,TXx x x x x令非基变量 x1=x2=0由方程组（1-4b）得： x3=6，x4=8, x5=18方程组（1-4b）的一个特解为：00,0,6,8,18TX 1. 基本解2022年6月10日星期五山西大学经济与管理学院 范建平52考虑标准形线性规划：考虑标准形线性

39、规划：max1 51 5. .01 5TzC XaAXbbstXc 假设假设A=(aij)mn是满秩阵，且秩数为是满秩阵，且秩数为r(A)=mn，将其系数，将其系数阵阵A记为：记为： 则有下述定义：则有下述定义：121,mmnAa aaaa1. 基本解2022年6月10日星期五山西大学经济与管理学院 范建平53p（1）基矩阵）基矩阵n设设B为为A的一个的一个m阶子矩阵，若其行列式阶子矩阵，若其行列式|B|0，则称，则称B为方为方程组（程组（1-5b）或线性规划（）或线性规划（1-5）的一个）的一个基矩阵基矩阵，简称一个，简称一个基基。1. 基本解2022年6月10日星期五山西大学经济与管理学院

40、 范建平54p（2）基变量）基变量12,0mBa aaB不失一般性，设基矩阵为：121212,mmmnmmnBmAnma aaaaaNaaaAB NA基向量非基则 中的 个向量为,矩阵 中其余个向量为。将所有非基向量构成的矩阵记为:则系数矩阵 可改写为：向量1. 基本解2022年6月10日星期五山西大学经济与管理学院 范建平5512,Bmx xxm称基向量对应的 个变为 以 为基量为的 基变量12,Bmmnxmxx称非基向量对应的n-为 以 为基的个变量为非基变量XB将所有基变量构成的向量记为，称为基变矢XN所有非基变量构成的向量记为，称为非基变矢,(1 5b )BABABNXXXAXbB N

41、bXBXNXb则变矢X可写为：X=而方程组可改写为即1. 基本解2022年6月10日星期五山西大学经济与管理学院 范建平56p（3）基本解）基本解- bBBXbB令非基变量全部取值为0,即X N=0,这是方程组（1 5 ）-1-110,B0- b0- b-BNBBBXB bXB b0由前假设 的行列式则可逆，用左乘上式两端，解得与一起构成方程组（1 5 ）的一个特解X =称为方程组（1 5 ）或线性规划（1 5）的一个以B为基的基本解，简称基本解2. 最优基本解2022年6月10日星期五山西大学经济与管理学院 范建平57p（1）基本可行解）基本可行解n既是既是基本解基本解，又是，又是可行解可行

42、解，就是基本可行解。，就是基本可行解。n满足非负约束的基本解为满足非负约束的基本解为基本可行解基本可行解。max1 51 5. .01 5TzC XaAXbbstXc034500,0,6,8,18TBaaaX00取，以B 为基的基本解为：X =所有分量取值为非负，是基本可行解。123411300,6,6,-4,0TBaaaBX14取为基，解为： X =x =-4，不是基本可行解。2124222306,2,0,4,0TBa aaBX取为基，解为： X =是基本可行解。2. 最优基本解2022年6月10日星期五山西大学经济与管理学院 范建平58p（2）最优基本解）最优基本解n满足式（满足式（1-5a），能使目标函数），能使目标函数z=CTX取得最大值的基本可取得最大值的基本可行解行解 ，称为标准型，称为标准型LP问题（问题（1-5）的最优基本解，记为）的最优基本解，记为X*,它所对应的目标函数值称为它所对应的目标函数值称为最优值最优值，记为，记为z*=CTX*max1 51 5. .01 5TzC XaAXbbstXc22- a6,2,0,4,0TX将代入目标函数（1 5 ）中，算的,由前面的图解法知这z=2是范例的最优值，故X =为范例的2最优基本解。2