线性规划与单纯形法

线性规划与单纯形法第1页，共120页，2023年，2月20日，星期六第二章线性规划与单纯形法2.1线性规划问题与数学模型2.2图解法2.3线性规划的应用2.4单纯形法基本原理及计算步骤2.5单纯形法的进一步讨论2.6线性规划的对偶问题第2页，共120页，2023年，2月20日，星期六2.1线形规划(LinearProgramming)问题及其数学模型【引例】某工厂在计划期内要安排甲乙两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗，以及资源的限制如下表所示：甲乙资源限制设备11300台时原料A21400千克原料B01250千克单件利润50（元/件）100（元/件）问:工厂应分别生产多少个产品甲、乙才能使工厂获利最多？第3页，共120页，2023年，2月20日，星期六设生产甲产品x1个，生产乙产品x2个目标函数maxZ=50x1+100x2

约束条件x1+x2

≤300

2x1+x2

≤400

x2

≤250

x1≥0,x2

≥0第4页，共120页，2023年，2月20日，星期六线性规划模型1.适用条件：（1）优化条件:问题目标最大化、最小化的要求；（2）约束条件:问题目标受一系列条件的限制；（3）选择条件:实现目标存在多种备选方案；（4）非负条件的选择:根据问题的实际意义决定是否非负。2.构建线性规划模型的步骤（1）科学选择决策变量（2）明确目标要求（3）根据实际问题的背景材料，找出所有的约束条件（4）确定是否增加决策变量的非负条件

第5页，共120页，2023年，2月20日，星期六线性规划模型表示形式——决策变量；——目标函数系数、价值系数或费用系数；——右端项或资源常数；

——称为约束系数或技术系数。（1）一般形式：第6页，共120页，2023年，2月20日，星期六（2）集合形式：（3）向量形式：（4）矩阵形式：第7页，共120页，2023年，2月20日，星期六【例】

将线性规划模型一般表达式化为矩阵形式。解:设:第8页，共120页，2023年，2月20日，星期六例1.目标函数：

Maxz=50x1+100x2约束条件：

s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最优解：

x1=50，x2=250

最优目标值z=27500§2图解法对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解其方法：第9页，共120页，2023年，2月20日，星期六步骤：

(1)分别取决策变量X1,X2

为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。x2x1X2≥0X2=0x2x1X1≥0X1=0第10页，共120页，2023年，2月20日，星期六（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400第11页，共120页，2023年，2月20日，星期六（3）把五个图合并成一个图，取各约束条件的公共部分，如图2-1所示。100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图2-1第12页，共120页，2023年，2月20日，星期六（4）目标函数z=50x1+100x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。x1x2z=20000=50x1+100x2图2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE第13页，共120页，2023年，2月20日，星期六解的几种可能结果唯一最优解解无穷多个最优解无界解(可行域无界，常为模型遗漏了某些必要的约束条件)无可行解（可行域为空集，约束条件自相矛盾,资源满足不了人们的需求）可行解：满足LP问题所有约束条件的解最优解：满足目标要求的可行解第14页，共120页，2023年，2月20日，星期六四种结局:x1x2唯一最优解x2x1无穷多最优解x1x2无界解x2x1无可行解第15页，共120页，2023年，2月20日，星期六

无界解

第16页，共120页，2023年，2月20日，星期六无可行解：可行域为空集增加的约束条件第17页，共120页，2023年，2月20日，星期六线性规划标准形式线性规划标准模型的一般表达式：

非标准形式标准化方法：

1.目标函数

2.约束条件为不等式:引进松驰变量xs:引进剩余变量xs:4.决策变量为自由变量:

5.约束右端项为负:两端乘-1:≥03.约束条件为不等式:第18页，共120页，2023年，2月20日，星期六引入松驰变量（含义是资源的剩余量）

【引例】中引入s1，s2，s3模型化为目标函数：Maxz=50x1+100x2+0s1+0s2+0s3

约束条件：s.t.x1+x2+s1=3002x1+x2+s2=400x2+s3=

250x1,x2,s1,s2,s3≥0

对于最优解

x1=50x2=250，s1=0s2=50s3=0

说明：生产50单位Ⅰ产品和250单位Ⅱ产品将消耗完所有可能的设备台时数及原料B，但对原料A则还剩余50千克。第19页，共120页，2023年，2月20日，星期六

【例】将线性规划模型转化为标准式解:无约束(4)在第一、第三约束左端加上松弛变量x4,x6≥0，在第二约束左端减去剩余变量x5≥0

第20页，共120页，2023年，2月20日，星期六习题1.用图解法求解下列LP问题（1）minZ=6x1+4x2(2)maxZ=3x1-2x2

2x1+x2≥1x1+x2≤1

3x1+4x2≥32x1+2x2≥4

x1，x2≥0x1，x2≥0第21页，共120页，2023年，2月20日，星期六2、对下面LP问题(1)用图解法求解(2)写出此问题的标准形式(3)求剩余变量的值

minZ=11x1+8x2

s.t.10x1+2x2≥203x1+3x2≥184x1+9x2≥36

x1,x2≥0第22页，共120页，2023年，2月20日，星期六图解法的灵敏度分析1、目标函数中的系数Ci的灵敏度分析分析Ci在什么范围内变化，原最优解不变

C1=50C2=100第23页，共120页，2023年，2月20日，星期六EADCBF第24页，共120页，2023年，2月20日，星期六

直线BC的斜截式为：x2=-x1+300

斜率为-1

直线BF的斜截式为：x2=0×x1+250

斜率为0

目标函数Z=c1x1+c2x2的斜截式为：

x₂=-c1/c2x1+z/c2

斜率为-c1/c2

所以,当-1≤-c₁/c₂≤0时，顶点B仍然是最优解假设c2

不变,则有-1≤-c1/100≤0，解之得0≤c1≤100，第25页，共120页，2023年，2月20日，星期六练习：计算C₂在什么范围内变化时顶点B仍然是最优解第26页，共120页，2023年，2月20日，星期六2、约束条件右边b系数的灵敏度分析

b变化时通常引起可行域的变化从而引起最优解的变化。设例1中的设备台时增加了10个台时数,则约束变为：x1+x2≤310代入求得新的最优解为x1=60,x2=250Z=50×60+100×250=28000比原来最大的利润27500增加了500元,可知每增加一个台时的设备可多获利润500/10=50元在约束条件右边常量每增加一个单位而使最优目标函数得到改进的量称为这个约束条件的对偶价格第27页，共120页，2023年，2月20日，星期六

练习：将原料A增加10千克计算最优解和最优值某一约束条件的对偶价格仅仅在某一范围内有效总结当约束条件右边常数增加一个单位时：(1)如果对偶价格大于零,则最优目标函数值得到改进,即求最大值时变得更大;求最小值时变得更小(2)如果对偶价格小于零,则最优目标函数值变坏,即求最大值时变得小了;求最小值时变得大了(3)如果对偶价格等于零,则最优目标函数值不变第28页，共120页，2023年，2月20日，星期六练习:某公司目前正生产甲乙两种产品,产量分别为

30个和120个,公司经理希望了解是否通过改变这两种产品的数量而提高公司的利润.公司制造每个产品所需的加工工时和各个车间的加工能力如下表:车间产品甲产品乙车间能力(每天加工工时数)12030020354032244041.21.5300利润/每个产品(元)500400第29页，共120页，2023年，2月20日，星期六(1)假设生产的全部产品都能销售出去,用图解法确定最优产品组合(2)在上面求得的最优产品组合中,那些车间的能力还有剩余,剩余多少?是剩余变量还是松弛变量?(3)各车间的能力分别增加一个加工工时数给公司带来多少额外的利润.(4)当产品甲的利润不变时,产品乙的利润在什么范围内变化时此最优解不变?当产品乙的利润不变时,

产品甲的利润在什么范围内变化时最优解不变.(5)当产品甲的利润从500降为450元,而产品乙的利润从400元增加为430元时,原来产品组合是否依然是最优产品组合.第30页，共120页，2023年，2月20日，星期六第31页，共120页，2023年，2月20日，星期六第32页，共120页，2023年，2月20日，星期六第33页，共120页，2023年，2月20日，星期六第34页，共120页，2023年，2月20日，星期六2.3LP的应用一.人力资源分配问题例1.某昼夜服务的公交线路每天各时间段所需司机和乘务人员数如下：班次时间所需人数

1

6：00-10：0060

2

10：00-14：0070

3

14：00-18：0060

4

18：00-22：0050

5

22：00-2：0020

6

2：00-6：0030第35页，共120页，2023年，2月20日，星期六设司机和乘务人员分别在各时段一开始时上班,并连续工作8小时,问该公交线路怎样安排人员,既能满足工作需要又配备最少司机和乘务人员。第36页，共120页，2023年，2月20日，星期六设xi表示第i班次开始上班的人员s.t.minZ=X1+X2+X3+X4+X5+X6

X1+X6≥

60

X1+X2≥

70

X2+X3≥

60

X3+X4≥

50

X4+X5≥

20

X5+X6≥30

X1,X2,X3,X4,X5,X6≥0第37页，共120页，2023年，2月20日，星期六最优解：x₁=50x₂=20x₃=50x₄=0x₅=20x₆=10

最优目标函数值Z=150第38页，共120页，2023年，2月20日，星期六【练习】某中型百货商场对售货人员的需求统计如下表,并规定售货员每周工作5天且连续休息2天，问如何安排人员的作息既满足工作需要又使配备人员最少？时间所需售货员人数星期日28星期一15星期二24星期三25星期四19星期五31星期六28第39页，共120页，2023年，2月20日，星期六解：设x1为星期一开始休息的人数,x2为星期二开始休息的人数,…x7为星期日开始休息的人数目标函数:minZ=x1+x2+x3+x4+x5+x6+x7x1+x2+x3+x4+x5≥28x2+x3+x4+x5+x6≥15x3+x4+x5+x6+x7≥24x4+x5+x6+x7+

x1≥25x5+x6+x7+x1+x2≥19x6+x7+

x1+x2+x3≥31x7+x1+x2+x3+x4≥28xi

≥0

第40页，共120页，2023年，2月20日，星期六最优解：x1=12x2=0x3=11x4=5

x5=0x6=8x7=0

目标函数最小值为：36第41页，共120页，2023年，2月20日，星期六二生产计划问题例2、某公司生产甲，乙，丙三种产品，这三种产品都要经过铸造，机加工和装配三个车间。甲乙两种产品的铸件可以外包协作也可自行生产，但丙产品必须本厂铸造才能保证质量。有关情况见下表；公司中可利用的总工时为铸造8000小时机加工12000小时和装配10000小时。公司为了获得最大利润，甲，乙，丙三种产品各生产多少件，甲乙两种产品的铸造应多少由本公司完成？多少由外包协作？第42页，共120页，2023年，2月20日，星期六工时与成本甲乙丙每件铸造工时5107每件机加工工时648每件装配工时322自产铸件每件成本354外协铸件每件成本56—机加工每件成本213装配每件成本322每件产品售价231816第43页，共120页，2023年，2月20日，星期六解：设x1，x2，x3分别为三道工序都由本公司加工的甲，乙，丙三种产品的件数，设x4，x5分别为由外协铸造再由本公司机加工和装配的甲乙两种产品的件数。计算每件产品的利润分别如下：产品甲全部自制的利润=23-（3+2+3）=15产品甲铸造外协，其余自制的利润=23-（5+2+3）=13产品乙全部自制的利润=18-（5+1+2）=10产品乙铸造外协，其余自制的利润=18-（6+1+2）=9产品丙的利润=16-（4+3+2）=7第44页，共120页，2023年，2月20日，星期六目标函数：maxZ=15X1+10X2+7X3+13X4+9X5

5X1+10X2+7X3≤80006

X1+4X2+8X3+6X4+4X5≤12000

3X1+2X2+2X3+3X4+2X5≤

10000X1,X2,X3,X4,X5≥0第45页，共120页，2023年，2月20日，星期六三套裁下料问题例3、某工厂要做100套钢架，每套用2·9m、2·1m和1·5m的原钢各一根。已知原料每根长7·4m，问应如何下料，可使所用原料最省。第46页，共120页，2023年，2月20日，星期六

下料方案长度ⅠⅡⅢⅣⅤ2·9120102·1002211·531203合计7·47·37·27·16·6余料00·10·20·30·8第47页，共120页，2023年，2月20日，星期六设按各方案下料的原材料根数分别为X1，X2，X3，X4，X5。目标函数：minZ=X1+X2+X3+X4+X5约束条件：X1+2X2+X4≥1002X3+2X4+X5≥1003X1+X2+2X3+3X5≥100X1，X2，X3，X4，X5≥0最优解X1=30X2=10X3=0X4=50X5=0Z=90第48页，共120页，2023年，2月20日，星期六四、投资问题例4、某部门现有资金200万元，今后五年内考虑以下的项目投资，已知项目A：第一年到第五年年初都可投资，当年末能收回本利110%。已知项目B：第一年到第四年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元。项目C：第三年初需要投资，到第五年末能回收本利140%，但规定最大投资额不超过80万元。项目D：第二年初需要投资，到第五年末能回收本利155%，但规定最大投资额不超过100万元。问：应如何确定这些项目的每年投资，使得第五年末拥有资金的本利和金额最大？第49页，共120页，2023年，2月20日，星期六这是一个连续投资的问题，设：Xij=第i年初投资j项目的金额，见表：

年份项目12345AX1AX2AX3AX4AX5ABX1BX2BX3BX4BCX3CDX2D第50页，共120页，2023年，2月20日，星期六目标函数：

maxz=1·1X5A＋1·25X4B

＋1·40X3C＋1·55X2DX1A＋X1B=200，

X2A＋

X2B＋

X2D=

1·1X1A，

X3A＋

X3B＋

X3C=

1·1X2A＋

1·25X1B，

X4A＋

X4B=

1·1X3A＋1·25X2B，

X5A=

1·1X4A＋

1·25X3B，

XiB≤

30（i=1，2，3，4），

X3C≤80，

X2D≤100，

Xij≥0，第51页，共120页，2023年，2月20日，星期六五、配料问题

例5：某工厂要用三种原料1、2、3混合调配出三种不同规格的产品甲、乙、丙，数据如右表。问：该厂应如何安排生产，使利润收入为最大？

第52页，共120页，2023年，2月20日，星期六解：设xij

表示第i种（甲、乙、丙）产品中原料j的含量。这样我们建立数学模型时，要考虑：对于甲：x11，x12，x13；对于乙：x21，x22，x23；对于丙：x31，x32，x33；对于原料1：x11，x21，x31；对于原料2：x12，x22，x32；对于原料3：x13，x23，x33；目标函数：利润最大，利润=收入-原料支出约束条件：规格要求4个；供应量限制3个第53页，共120页，2023年，2月20日，星期六利润=总收入-总成本=甲乙丙三种产品的销售单价*产品数量-甲乙丙使用的原料单价*原料数量，故有目标函数Max50（x11+x12+x13）+35（x21+x22+x23）+25（x31+x32+x33）-65（x11+x21+x31）-25（x12+x22+x32）-35（x13+x23+x33）=-15x11+25x12+15x13-30x21+10x22-40x31-10x33

约束条件：从第1个表中有：

x11≥0.5(x11+x12+x13)x12≤0.25(x11+x12+x13)x21≥0.25(x21+x22+x23)x22≤0.5(x21+x22+x23)第54页，共120页，2023年，2月20日，星期六从第2个表中，生产甲乙丙的原材料不能超过原材料的供应限额，故有

(x11+x21+x31)≤100(x12+x22+x32)≤100(x13+x23+x33)≤60

第55页，共120页，2023年，2月20日，星期六习题1、某锅炉制造厂要制造一种新锅炉10台，每台锅炉需要不同长度的锅炉钢管数量如下：规格（mm）2640165117701440需要数量（根）835421库存的原材料的长度只有5500mm一种规格，问如何下料才能使总的用料根数最少？第56页，共120页，2023年，2月20日，星期六2.、前进电器厂生产A，B，C三种产品有关资料如下表：产品材料消耗（千克/件）台时消耗（台时/件）产品利润（元/件）市场容量（件）A1.0210200B1.51.212250C4.0114100资源限制2000千克1000台时问:在资源及市场允许的条件下如何安排生产获利最大第57页，共120页，2023年，2月20日，星期六3.某公司在今后四个月内需租用仓库堆放物资已知各个月所需的仓库面积数字如下表：月份1234所需仓库面积(百平方米)15102012合同租借期限1个月2个月3个月4个月合同期内每百平方米仓库面积的租借费用2800450060007300表2表1第58页，共120页，2023年，2月20日，星期六仓库的租借费用,当租借合同期限越长时,享受的折扣优惠也越大,具体数字如表2,租借仓库的合同每月初都可办理,每份合同具体规定租用面积数和期限.因此该厂可根据需要在任何一个月初办理租借合同,且每次办理可签一份也可同时签若干份租用面积和租借期限不同的合同.求一个所付的租借费为最小的租借方案.第59页，共120页，2023年，2月20日，星期六设xij(i=1,2,3,4)(j=1,…4-i+1)为第i个月初签定的租借期为j个月的合同的租界面积minZ=2800x11+4500x12+6000x13+7300x14+2800x21+4500x22+6000x23+2800x31+4500x32+2800x41

x11+x12+x13+x14≥15s.tx12+x13+x14+x21+x22+x23≥10x13+x14+x22+x23+x31+x32≥20x14+x23+x32+x41≥15xij≥0第60页，共120页，2023年，2月20日，星期六4、某公司从两个产地A1,A2将货物运往三个销地B1,B2B3,各产地的产量及各销地的销量和各产地运往各销地的每件物品的运费如下表,问如何调运使得总运输费用最小?运费销地单价产地B1B2B3产量(件)A1646200A2655300销量150150200第61页，共120页，2023年，2月20日，星期六设xij表示从产地Ai调运到Bj的运输量(i=1,2;j=1,2,3)minf=6x11+4x12+6x13+6x21+5x22+5x23x11+x12+x13=200x21+x22+x23=300x11+x21=150x12+x22=150x13+x23=200xij≥0s.t.第62页，共120页，2023年，2月20日，星期六班次时间所需人数

1

6：00-10：0015

2

10：00-14：0025

3

14：00-18：0020

4

18：00-22：0018

5

22：00-2：0012

6

2：00-6：00105、某医院昼夜24h各时段内需要的护士数量如下：若医院可聘用合同工护士，上班时间同正式护士。护士于每班开始上班，并连续工作8小时，若正式工护士报酬为10元/h,合同工为15元/h,问医院是否应聘用合同工护士及聘用多少名？第63页，共120页，2023年，2月20日，星期六6、红英公司承诺为某建设项目从2003年起的4年中每年年初分别提供以下数额的贷款：2003年100万元、2004年150万元、2005年120万元、2006年110万元。为了充分发挥这笔资金的作用，在满足每年贷款额的情况下，可将多余资金分别用于下列投资项目：（1）于2003年初购买A种债券，期限3年，到期后本息合计为投资额的140%，但限购60万元。（2）于2003年初购买B种债券，期限2年，到期后本息合计为投资额的125%，但限购90万元。（3）于2004年初购买C种债券，期限2年，到期后本息合计为投资额的130%，但限购50万元。（4）于年初将任意数额的资金存放于银行，年息4%，于年底取出。问：该公司应如何运用好这笔筹集到的资金，使2002年底需筹集到的资金数额为最少？第64页，共120页，2023年，2月20日，星期六7、某厂生产甲乙丙丁四种产品，产品甲需经过A、B两种机器加工，产品乙需经过A、C两种机器加工，产品丙需经过B、C两种机器加工，产品丁需经过A、B两种机器加工。有关数据如下，试为该厂制定一个最优的生产计划。产品机器生产率（件/小时）原料成本（元）产品价格（元）ABC甲10201665乙20102580丙10151250丁20101870机器成本元/小时200150225每周可用小时数15012070第65页，共120页，2023年，2月20日，星期六8、某快餐店坐落于一个旅游景点，平时游客不多，而在每周六游客猛增。该快餐店雇佣了两名正式员工，正式员工每天工作8小时，其余工作由临时工来担任，临时工每班工作4小时。根据游客就餐情况，在星期六每个营业小时所需职工数（包括正式工和临时工）如下表。已知一名正式工11点开始上班，工作4小时后休息1小时而后再工作4小时；另一名正式工13点开始上班，工作4小时后休息1小时，而后再工作4小时。又知临时工每小时的工资为4元。在满足对职工需求的条件下，如何安排临时工的班次，使得使用临时工的成本最小？第66页，共120页，2023年，2月20日，星期六时间所需职工数时间所需职工数11:00-12:00917:00-18:00612:00-13:00918:00-19:001213:00-14:00919:00-20:001214:00-15:00320:00-21:00715:00-16:00321:00-22:00716:00-17:003第67页，共120页，2023年，2月20日，星期六x2＋x3＋x4＋x5＋1≥3x3＋x4＋x5＋x6＋2≥3x4＋x5＋x6＋x7＋1≥6x5＋x6＋x7＋x8＋2≥12x6＋x7＋x8＋x9＋2≥12x7＋x8＋x9＋x10＋1≥7x8＋x9＋x10＋x11＋1≥7minf=16（x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11）

s．t．

x1＋1≥9x1

＋x2＋1≥9x1

＋x2＋x3＋2≥9x1＋x2＋x3＋x4＋2≥3第68页，共120页，2023年，2月20日，星期六9、某厂按合同规定于当年每个季度末分别提供10、15、25、20台同一规格的柴油机。已知该厂各季度的生产能力及每台柴油机的成本如下表所示，又如果生产出来的柴油机当季不交货，每台每积压一个季度需储存、维护等费用0.15元。要求在完成合同的情况下，做出使该厂全年生产费用最小的决策。

季度1234生产能力25353010单位成本（万元）10.811.111.011.3第69页，共120页，2023年，2月20日，星期六2.4单纯形法基本原理及计算步骤一、单纯形法的基本思路

从可行域中某一个顶点开始判断此顶点是否是最优解，如不是则再找另一个使得目标函数值更优的顶点，称之为迭代。再判断此点是否是最优解。直到找到一个顶点为最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解第70页，共120页，2023年，2月20日，星期六最优解一定在可行域的顶点上,将顶点坐标代入目标函数有:(0,0):z=3×0+2×0=0(5,0):z=3×5+2×0=15(0,8):z=3×0+2×8=16(2,6):z=3×2+2×6=18单纯形法的基本思路就是基本可行解的转移，先找到一个初始基本可行解，如果不是最优解，设法转移到另一个基本可行解，并使目标函数值不断增加，直到找到最优解。(5,0)(2,6)10830258x2(0,8)x1第71页，共120页，2023年，2月20日，星期六二、单纯形法计算步骤：

1、找出一个初始基本可行解单纯形法中可行域的顶点叫做基本可行解，找到的第一个基本可行解叫做初始基本可行解第72页，共120页，2023年，2月20日，星期六目标函数maxZ=50x1+100x2

x1+x2+s1=3002x1+x2+s2=400

x2+s3=250x1,x2,s1,s2,s3,≥0系数矩阵A=111002101001001由于A中存在一个不为零的三阶子式，可知A的秩为3因为A的秩m小于此方程组的变量的个数n，可知其有无穷多组解第73页，共120页，2023年，2月20日，星期六基本概念

基：已知A是约束条件的m×n系数矩阵，其秩为m，若B是A中m×m阶可逆矩阵，则称B是线形规划问题中的一个基。B是由A中m个线形无关的系数列向量组成的。本例中111与100210010010001

都是该线性规划的一个基。它们都是由3个线性无关的系数列向量组成。第74页，共120页，2023年，2月20日，星期六基向量:基B中的一列称为一个基向量。基B中共有m

个基向量非基向量:在A中除了基B之外的一切列称为基B的非基向量基变量:与基向量pi对应的变量xi叫做基变量,基变量有m个非基变量:与非基向量pj对应的变量xj叫做非基变量,基变量有n-m个.例中对基B1=111来说111210210010010

都是基B1的基向量,对应的变量x1,x2,s1叫做基变量,s2,s3是基B1的非基变量.第75页，共120页，2023年，2月20日，星期六例中对基B2=100来说100010010001001

都是基B2的基向量,对应的变量s1,,s2,s3叫做基变量,x2,x3是基B2非基变量.在约束方程系数矩阵中找到一个基,令这个基的非基变量为零,再求解这个m元线性方程组就可得到唯一的解了,这个解称之为线性规划的基本解.第76页，共120页，2023年，2月20日，星期六例取B3=110为A的一个基,令非基变量x1,s2100为零,这时约束方程就变为仅含

101基变量的约束方程.

x2+s1=300求解得x2=400s1=-100s3=-100x2=400x1=0s2=0x2+s3=250由于s1,s3＜0,显然不是此线性规划的可行解一个基本解可以是可行解,也可以是非可行解,它们之间的主要区别在于其所有变量的解是否满足非负的条件.把满足非负条件的一个基本解叫做基本可行解,并把这样的基叫做可行基.第77页，共120页，2023年，2月20日，星期六它们之间的关系第78页，共120页，2023年，2月20日，星期六选B1=110200001令其非基变量x2,s2为零,约束方程变为基变量的约束方程

x1

+s1=3002x1=400

s3=250求解得到基变量的唯一解,基变量s3=250x1=200s1=100非基变量x2=0s2=0所有变量都大于等于零,此基本解为基本可行解.

只要找到一个基是单位矩阵,或者说一个基是由单位矩阵各列向量组成(列向量前后顺序无关紧要),那么所求得的基本解一定是基本可行解.练习:设B2为基,求一组基本解,并判别其是否为基本

可行解.第79页，共120页，2023年，2月20日，星期六2、最优性检验---判断已求得的基本可行解是否为最优解最优性检验的依据----检验数σj

要求只用非基变量来表示目标函数,这只要在约束等式中通过移项处理就可以用非基变量来表示基变量,然后用非基变量的表示式代替目标函数中基变量,这样目标函数中就只含非基变量了,或者说目标函数中基变量的系数都为零了.此时目标函数中所有变量的系数即为各变量的检验数,把变量xi的检验数记为σi.显然所有基变量的检验数必为零.第80页，共120页，2023年，2月20日，星期六第81页，共120页，2023年，2月20日，星期六基变量的非基变量表达式：

令所有的非基变量取值为零，即，由此求出初始基本可行解为：第82页，共120页，2023年，2月20日，星期六把以上的表达式代入目标函数，就有第83页，共120页，2023年，2月20日，星期六最优解判别定理对于求最大目标函数的问题中,对于某个基本可行解,如果所有检验数σj≤0,则这个基本可行解是最优解.第84页，共120页，2023年，2月20日，星期六3、基变换从可行基中换一个列向量,得到一个新的可行基,使得求解得到新的基本可行解,使得目标函数值更优.（1）入基变量的确定选检验数大于0的非基变量换到基变量中去(称为入基变量).若有两个以上的σj>0,则为了使目标函数增加得更大些,一般选其中的σj最大者的非基变量为入基变量第85页，共120页，2023年，2月20日，星期六（2）出基变量的确定把已确定的入基变量在各约束方程的系数除以其所在约束方程中的常数项的值,把其中最小比值所在的约束方程中的原基变量确定为出基变量.第86页，共120页，2023年，2月20日，星期六单纯形法的表格形式目标函数

maxZ=50x1+100x2

+0s1+0s2+0s3

x1+x2+s1=3002x1+x2+s2=400

x2+s3=250x1,x2,s1,s2,s3,≥0第87页，共120页，2023年，2月20日，星期六基变量CBx1x2s1s2s3B-1b50100000s1011100300s2021010400s3001001250检验数50100000s101010-150s202001-1150x210001001250检验数50000-100x1501010-150s2000-21150x210001001250检验数00-500-50第88页，共120页，2023年，2月20日，星期六单纯形法求解步骤：找出：σk=max{σj|σj>0}以alk为中心元素进行迭代列初始单纯形表所有aik≤0?所有σj≤0？得到最优解YESYESNONO无界结束第89页，共120页，2023年，2月20日，星期六2.5单纯形法的进一步讨论大M法：加入人工变量使系数构成单位矩阵，规定人工变量在目标函数中的系数为-M，这里M为任意大的数.这样只要人工变量大于零,所求的目标函数最大值就是一个任意小的数.这样为了使目标函数实现最大就必须把人工变量从基变量中换出.如果人工变量直到最后仍不能从基变量中换出,也就是说人工变量仍不为零,则该问题无可行解.第90页，共120页，2023年，2月20日，星期六Minf=2x1+3x2x1+x2≥350x1≥1252x1+x2≤600x1,x2≥0

maxZ=-2x1-3x2x1+x2-s1=350x1–s2=1252x1+x2+s3=600x1,x2,s1,s2,s3≥0令z=-f

maxZ=-2x1-3x2-Ma1-Ma2x1+x2-s1+a1=350x1–s2+a2=1252x1+x2+s3=600x1,x2,s1,s2,s3≥0第91页，共120页，2023年，2月20日，星期六解的几种特殊情况无可行解

若线性规划的最优解里有人工变量大于零,则该线性规划问题无可行解第92页，共120页，2023年，2月20日，星期六目标函数：maxZ=20X1+30X2约束条件：3X1+10X2≤1503X1+10X2+

S1=150X1≤30X1+

S2=30X1+X2≥40X1+X2-

S3=40X1，X2≥0X1，X2,S1,S2,S3≥0

maxZ=20X1+30X2+0S1+

0S2+0S3-Ma13X1+10X2+

S1=150X1+

S2=30X1+X2-

S3+a1=40X1，X2,S1,S2,S3≥0

第93页，共120页，2023年，2月20日，星期六2无界解

在某次迭代的单纯形表中,如果存在一个大于零的检验数σj,并且该列的系数向量的每个元素aij(i=1,2,…,m)都小于或等于零,则此线性规划问题是无界的.第94页，共120页，2023年，2月20日，星期六maxZ=x1+x2x1-x2≤1-3x1+2x2≤6x1,x2≥0maxZ=x1+x2+0s1+0s2x1-x2+s1=1-3x1+2x2+s2=6x1,x2,s1,s2≥0第95页，共120页，2023年，2月20日，星期六基变量CBX1X2S1S2b比值

1100s1s20

1-110

16

1—0

-3-201

zjcj-zj

000011000X1S2

10

1-1100-131

19

zjcj-zj

1-11002-101第96页，共120页，2023年，2月20日，星期六3无穷多最优解

对某个最优的基本可行解,如果存在某个非基变量的检验数为零,则此线性规划问题有无穷多最优解.

maxZ=50x1+50x2x1+x2≤3002x1+x2≤400x2≤250x1，x2≥0第97页，共120页，2023年，2月20日，星期六4退化问题特点：(1)退化解的基变量中至少有一个取零值.(2)退化迭代中基在不断变化,但是解不变.(3)退化迭代不会引起目标函数值的变化.勃兰特法则:把松弛变量、人工变量都用Xj表示,一般松弛变量的下标号列在决策变量之后,人工变量的下标号列在松弛变量之后,计算中遵循以下规则:(1)在所有检验数大于零的非基变量中,选一个下标号最小的作为入基变量.(2)在存在两个和两个以上最小比值时,选一个下标号最大的基变量为出基变量.第98页，共120页，2023年，2月20日，星期六习题1、已知LP问题maxZ=x1+3x2x1+x3=5………………①x1+x2+x4≤10…………②x2+x5=4………………③xi≥0……④下表所列的解均满足约束①②③,指出那些是可行解,那些是基本解,那些是基本可行解第99页，共120页，2023年，2月20日，星期六序号x1x2x3x4x5

a

24300b100-504c3027 4d1 4.540-0.5e02562f04520第100页，共120页，2023年，2月20日，星期六2、考虑下面给出的不完全初始单纯形表迭代次数基变量CBx1x2x3s1s2s3b630250000310100400210105021-100120ZjCj-Zj第101页，共120页，2023年，2月20日，星期六把上面表格填写完整按照上面完整的表格,写出此线性规划模型这个初始解的基是什么,并写出这个初始解和其对应的目标函数值在进行第一次迭代时确定入基变量和出基变量,并标明主元。第102页，共120页，2023年，2月20日，星期六3、下表为用单纯形法计算时某一步的表格,已知该线性规划的目标函数为maxZ=5x1+3x2

约束形式为≤,x3,x4为松弛变量.表中解代入目标函数后得Z=10,填空并求a-g的值.基变量CBx1x2x3x4bjx3x1c011/53de01aσjb-1fg第103页，共120页，2023年，2月20日，星期六4、下表给出某线性规划问题计算过程中的一个单纯形表,目标函数为maxZ=28x4+x5+2x6.约束形式为≤,表中x1,x2,x3为松弛变量.表中解的目标函数值为Z=14，求a-g的值基变量CBx1x2x3x4x5x6bjx630-14/3011ax26d205/205x40ef1000

σj

bc00-1g第104页，共120页，2023年，2月20日，星期六基变量x1x2x3x4x5bjc1c2c3xmxn

bcd10-13e0161σj

a