第5章线性规划

1、第五章第五章 线性规划线性规划* 目标函数和约束条件都是线性的，像这类约束目标函数和约束条件都是线性的，像这类约束函数和目标函数都是为线性函数的优化问题，称作函数和目标函数都是为线性函数的优化问题，称作线性规划问题。它的解法在理论和方法上都很成熟，线性规划问题。它的解法在理论和方法上都很成熟，实际应用也很广泛。虽然大多数工程设计是非线性实际应用也很广泛。虽然大多数工程设计是非线性的，但是也有采用线性逼近方法求解的，但是也有采用线性逼近方法求解非线性问题的。非线性问题的。此外，线性规划方法还常被用作解决非线性问题的此外，线性规划方法还常被用作解决非线性问题的子问题的工具，如在可行方向法中可行方向

2、的寻求子问题的工具，如在可行方向法中可行方向的寻求就是采用线性规划方法。当然，对于真正的线性优就是采用线性规划方法。当然，对于真正的线性优化问题，线性规划方法就更有用了。化问题，线性规划方法就更有用了。*0024261553. .2max21212121xxxxxxtsxxz解：设生产解：设生产A、B两产品分别两产品分别为为x1, x2台，则该问题的优化台，则该问题的优化数学模型为：数学模型为：例例5-1： 某工厂要生产某工厂要生产A、B两种产品，两种产品，每生产一台产品每生产一台产品A 可获产值可获产值2万元；万元；需占用一车间工作日需占用一车间工作日3天，二车间工天，二车间工作日作日6天；

3、每生产一台产品天；每生产一台产品B 可获产可获产值值1万元；需占用一车间工作日万元；需占用一车间工作日5天，天，二车间工作日二车间工作日2天。现一车间可用于天。现一车间可用于生产生产A、B产品的时间产品的时间15天，二车间天，二车间可用于生产可用于生产A、B产品的时间产品的时间24天。天。试求出生产组织者安排试求出生产组织者安排A、B两种产两种产品的合理投资产数，以获得最大的总品的合理投资产数，以获得最大的总产值。产值。*例例5-2：生产甲种产品每件需使用材料生产甲种产品每件需使用材料9kg9kg、3 3个工时、个工时、4kw4kw电，获电，获利润利润6060元。生产乙种产品每件需用材料元。生

4、产乙种产品每件需用材料4kg4kg、1010个工时、个工时、5kw5kw电，电，可获利可获利120120元。若每天能供应材料元。若每天能供应材料360kg360kg，有，有300300个工时，能供个工时，能供200kw200kw电。试确定两种产品每天的产量，使每天可能获得的电。试确定两种产品每天的产量，使每天可能获得的利润利润最大最大？ 12,x x1212( ,)60120maxf x xxx112()94360gXxx分析：分析：每天生产的每天生产的分别为分别为 件件 （工时约束）（工时约束）（电力约束）（电力约束）（材料约束）（材料约束）( (利润最大利润最大) )212()310300

5、gXxx312()45200gXxx*将其化成线性规划标准形式：将其化成线性规划标准形式：12394360 xxx124310300 xxx12545200 xxx求求T12xxx12min( )60120f xxx 使使且满足且满足0(1,2,3,4,5)ixi *例5-3：某厂生产甲、乙两种产品，已知：两种产品分别由两条生产线生产。第一条生产甲，每天最多生产9件，第二条生产乙，每天最多生产7件；该厂仅有工人24名，生产甲每件用2工日，生产乙每件用3工日；产品甲、乙的单件利润分别为40元和80元。问工厂如何组织生产才能获得最大利润？*日利润最大日利润最大生产能力限制生产能力限制劳动力限制劳动

6、力限制变量非负变量非负.,21xx解解: 设甲、乙两种产品的日产件数分别为设甲、乙两种产品的日产件数分别为0,2432798040)(max212121221xxxxxxRDXxxXFs.t.机械优化设计*建模例建模例1： 某公司有钢材、铝材、铜材某公司有钢材、铝材、铜材1200t，800t和和650t，拟调往，拟调往物资紧张的地区甲、乙、丙。已知甲、乙、丙对上述物资的总需求物资紧张的地区甲、乙、丙。已知甲、乙、丙对上述物资的总需求分别为：分别为：900t，800t和和1000t。各种物资在各地销售每吨的获利如下。各种物资在各地销售每吨的获利如下表所示。试问公司应如何安排调运计划，才能获利最大

7、？建立该问表所示。试问公司应如何安排调运计划，才能获利最大？建立该问题的数学模型。题的数学模型。钢材钢材铝材铝材铜材铜材甲甲260300400乙乙210250550丙丙180400350物资物资获利获利地区地区*建模例建模例2： 某工厂生产某工厂生产A、B、C三种产品，现根据订货合同以及生产三种产品，现根据订货合同以及生产状况制定状况制定5月份的生产计划，已知合同甲为：月份的生产计划，已知合同甲为：A产品产品1000件，单件价件，单件价格为格为500元，违约金为元，违约金为100元元/件；合同乙为：件；合同乙为：B产品产品500件，单件价格件，单件价格为为400元，违约金为元，违约金为120元

8、元/件；合同丙为：件；合同丙为：B产品产品600件，单件价格为件，单件价格为420元，违约金为元，违约金为130元元/件；件；C产品产品600件，单件价格为件，单件价格为400元，违约元，违约金为金为90元元/件；有关各产品生产过程所需工时以及原材料的情况见下件；有关各产品生产过程所需工时以及原材料的情况见下表。试以利润为目标，建立该工厂的生产计划线性规划模型表。试以利润为目标，建立该工厂的生产计划线性规划模型 。工序工序1工序工序2工序工序3原材料原材料1 原材料原材料2其他成本其他成本产品产品A /件件2323410产品产品B /件件1132310产品产品C /件件2124210总工时或原

9、材料总工时或原材料460040006000100008000工时或原材料成本工时或原材料成本（元）（元）1510102040*建模例建模例3： 成批生产企业年度生产计划的按月分配成批生产企业年度生产计划的按月分配 。在成批生产的机械制造企业中，不同产品劳动量的结构上可能在成批生产的机械制造企业中，不同产品劳动量的结构上可能有很大差别。如：某种产品要求较多的车床加工时间，另一种有很大差别。如：某种产品要求较多的车床加工时间，另一种产品的劳动量可能集中在铣床和其他机床上。因此，企业在按产品的劳动量可能集中在铣床和其他机床上。因此，企业在按月分配年度计划任务时，应考虑到各种设备的均衡且最大负荷。月分

10、配年度计划任务时，应考虑到各种设备的均衡且最大负荷。 在年度计划按月分配时一般要考虑在年度计划按月分配时一般要考虑:1）从数量和品种上保从数量和品种上保证年度计划的完成；证年度计划的完成；2）成批的产品尽可能在各个月内均衡生）成批的产品尽可能在各个月内均衡生产或集中在几个月内生产；产或集中在几个月内生产；3）由于生产技术准备等方面原因，）由于生产技术准备等方面原因，某些产品要在某个月后才能投产；某些产品要在某个月后才能投产；4）根据合同要求，某些产）根据合同要求，某些产品要求在年初交货；品要求在年初交货；5）批量小的产品尽可能集中在一个月或）批量小的产品尽可能集中在一个月或几个月内生产出来，以

11、便减少各个月的品种数量等等。如何在几个月内生产出来，以便减少各个月的品种数量等等。如何在满足上述条件的基础上，使设备均衡负荷且最大负荷。满足上述条件的基础上，使设备均衡负荷且最大负荷。*线性规划数学模型的一般形式：线性规划数学模型的一般形式：11 11221121 1222221 122nnnnmmmnnma xa xa xba xa xa xba xaxaxb求求T12nxx xx1122( )minnnfxc xc xc x使使且满足且满足0(1,2, )ixin 0(1,2,)jbjm 说明：说明：1 1）m=n,m=n,唯一解唯一解2 2）mn,mn,无解无解3 3）mn,mm)为转轴

12、元素，此时为转轴元素，此时xt进入进入基，基， xs出基。这样就完成了从一个基本解到另一个基本出基。这样就完成了从一个基本解到另一个基本解的转换解的转换sta*1234512345541322058xxxxxxxxxx解：用解：用a11, a22作为轴元素进行两次转轴运算：作为轴元素进行两次转轴运算：例：给定如下方程组，试进行基本解的转换运算。例：给定如下方程组，试进行基本解的转换运算。134523450723120123420 xxxxxxxx 得到一组得到一组基本解：基本解： x1=-12 x2=-20 x3=x4=x5=0*用用a25作为轴元素进行第三次转轴运算：作为轴元素进行第三次转轴

13、运算：1234234531203441303544xxxxxxxx又得到一组又得到一组基本可行解：基本可行解： x1=3 x5=5 x2=x3=x4=0此时此时x5进入基，进入基， x2出基。出基。*二、从一个基本可行解转到另一个基本可行解二、从一个基本可行解转到另一个基本可行解121211111122112212100010000nnmmmkknmmmkknmxxxaxa xa xbxxxaxa xa xbxxx111211001lnmnlmmlkknlmmmmmkknmaxa xa xbxxxaxaxa xb当已经得到一组基本可行解，若要求把当已经得到一组基本可行解，若要求把xk选进基本变

14、量，选进基本变量，并使下一组基本解是可行解的话，并使下一组基本解是可行解的话，则在第则在第k k列要选取不为列要选取不为任何负值的元素作为转轴元素任何负值的元素作为转轴元素*alk作为转轴元素进行转轴运算：作为转轴元素进行转轴运算：121211111122112212100010000nnmmmkknmmmkknmxxxaxa xa xbxxxaxa xa xbxxx1112110101lnmnlmlmnlklklkmmmmmkkknmaabxxaaaxxxaxaxa xxb*1121111111211000100nlnmmmkknlmlmmnlklklkkxxxaxa xa xbaabxxx

15、xaaaxx1121111111211111100000nlnmmmkknlmlmkmknklklkklkkxxxaxa xa xbaabxxxaxaxaaaaa x*方程组第一行发生的变化：方程组第一行发生的变化：1121111111211111100000nlnmmmkknlmlmkmknklklkklkkxxxaxa xa xbaabxxxaxaxaaaaa x1112111111121111111100()0()000lnnlnlmmmkmkknlklklmlmkmkkknklkllklklkkbbaaaaxxxaaxxaaxaaaabxxxaxa xaxaaaa*alk作为轴元素，作

16、为轴元素，xk选进基本变量后，选进基本变量后， xk的取值由零变成了的取值由零变成了一个正值一个正值 ，则原来各基本变量的取值变为，则原来各基本变量的取值变为: :llkba11111222220000lllkkllkkkkkkkkmmmkkmmkxxba xbaxba xbaxbaxbaxba xba 若是基本可行解若是基本可行解, 应该应该保证保证各差值最小者为零各差值最小者为零 :min ()0iikibaminikiikbxa 决定了离基变量为决定了离基变量为xi*若想用若想用xk取代取代xl成为可行解中的基本变量，就应该选成为可行解中的基本变量，就应该选 所对应的行成为转轴行，即所选

17、取的行要满所对应的行成为转轴行，即所选取的行要满足条件足条件: :0llkba0lka min ()lkllkbxa规则规则*例：例：1234234531203441303544xxxxxxxx基本可行解：基本可行解： x1=3 x5=5 x2=x3=x4=0基本变量基本变量x1、x5 基本可行解的转换：基本可行解的转换： 1）x2、x4系数全部为负，只能选取系数全部为负，只能选取x3所在的第所在的第3列为转轴行列为转轴行 2） , 由于由于 ，则取第一行为转轴行，则取第一行为转轴行, 于是取于是取a13=2为转轴元素，使为转轴元素，使x3取代取代x1成为基本变量。成为基本变量。3523min

18、ikiikbxa*经转轴运算得：经转轴运算得：12341245131302882373102882xxxxxxxx得基本可行解：得基本可行解： 351243122xxxxx *结论结论：可把松驰变量作为初始基本可行解中的一部分基本可把松驰变量作为初始基本可行解中的一部分基本 变量。变量。12312352100,1,2,3ixxxxxxxi 123412350520100,1,2,3,4,5ixxxxxxxxxi 451235,10,0 xxxxx三、初始基本可行解的求法三、初始基本可行解的求法原始约束条件原始约束条件:引入松驰变量引入松驰变量:可得一组基本可行解：可得一组基本可行解：*一、单纯

19、形法的基本思想从一个初始基本可行解X0出发，寻找目标函数有较大下降的一个新的基本可行解X1,代替原来的基本可行解X0，如此完成一次迭代。随后作出判断，如果未达到最优解，则继续迭代下去。因为基本可行解的数目有限，所以经过有限次迭代一定能达到最优解。采用单纯形法求解线性规划问题，主要应解决以下三个问题：采用单纯形法求解线性规划问题，主要应解决以下三个问题：（1）如何确定初始基本可行解；）如何确定初始基本可行解；（2）如何由一个基本可行解迭代出另一个基本可行解，）如何由一个基本可行解迭代出另一个基本可行解，同同时保证目标函数的下降性时保证目标函数的下降性；（3）如何判断一个基本可行解是否为最优解。）

20、如何判断一个基本可行解是否为最优解。*二二. .最优解规则最优解规则 对应一组基本可行解：对应一组基本可行解： 前前m个变量组成基本可行解的基本变量个变量组成基本可行解的基本变量相应的目标函数值为相应的目标函数值为: :1 122( )00mmf xcbc bc b12 ,0,0TmXb bb1mlllcb*经过转轴运算得到另经过转轴运算得到另一组基本可行解为一组基本可行解为:111222kkssskmmmkkxbaxbaxXbaxbax其中：其中：0 ()ssskxbasm 进基变量进基变量xk出基变量出基变量xs*对应的目标函数为对应的目标函数为: :111222( )()()()()00

21、kkssskmmmkkf xc bac bac bacbac11mmllllkkllcbc ac1( )mkllklf xcc a( )kf xr*由于要求由于要求( )( )( )kf xf xrf x0kr结论结论: :一旦所有的一旦所有的 , , 即可停止即可停止 转轴运算转轴运算, ,对应的可行解就是对应的可行解就是最优解。最优解。r是是 对线性规划问题的解进行最优性检验的标对线性规划问题的解进行最优性检验的标 志，称之为检验数。志，称之为检验数。10mkkllklrcc a010mkkllklrcc a*1minmkllkklcc a具体计算时应选取具体计算时应选取: :由于有可能同

22、时有几组由于有可能同时有几组 都为负值都为负值1mkkllklrcc a最速变化规则最速变化规则( )( )( )kf xf xrf x*1minmkllkklcc a1）最速变化规则决定）最速变化规则决定进基的进基的非基本变量非基本变量结论结论：min ()lllkba2） 规则决定了规则决定了出基的出基的基本变量基本变量3）若对基本可行解）若对基本可行解X，所有检验数，所有检验数rk 0，则，则X 为最优解。为最优解。 *例例5-35-3某建筑单位拟盖一批二人、三人和四人的宿舍单元，要某建筑单位拟盖一批二人、三人和四人的宿舍单元，要确定每一种宿舍单元的数目，以获得最大利润。其限制条确定每一种宿舍单元的数目，以获得最大利润。其限制条件如下：件如下：1 1）预算不能超过）预算不能超过90009000千元。千元。2 2）宿舍单元总数不）宿舍单元总数不得少于得少于350350套。套。3 3）每类宿舍单元的百分比为：二人的不超）每类宿舍单元的百分比为：二人的不超过总数的过总数的20%20%，三人的不超过总数的，三人的不超过总数的60%60%，四人的不超过总，四人的不超过总数的数的40%40%（百分比总和超过（百分比总和超过100100，这是上限）。，这是上限）。4 4）建造价格）建造价格为：二人的宿舍单