运筹学 线性规划问题 及其数学模型

线性规划问题的提出线性规划的基本概念线性规划的数学模型线性规划问题的标准形式继续返回第一节线性规划问题及其数学模型上页下页返回•问题的提出【例1.1】:生产计划问题某工厂生产I.II两种产品。每件产品的利润，所耗A.B材料，设备及这两种材料，设备的限额如表III资源限量设备原材料A原材料B1402048台时16kg12kg利润23上页下页返回产品I产品2如何安排生产使利润最大？上页下页返回x1x2是问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。•第1步-确定决策变量x1x2z•设——I的产量——II的产量——利润上页下页返回MaxZ=x1+x2第2步--定义目标函数MaxZ=2x1+3x2上页下页返回第3步--表示约束条件x1+2x284x1164x212x1、x20III资源限量设备原材料A原材料B1402048台时16kg12kg利润23上页下页返回该计划的数学模型12121212max2328416.412,0Zxxxxxstxxx目标函数约束条件上页下页返回•第i种资源的拥有量为bi;i=1,2,…，m,生产一个单位第j种产品需要消耗第i种资源的数量为aij;第i种产品的单价（或利润产值等）为cj。j=1,2，…,n。•上述问题推广到一般情况如下：•有m种不同资源（例如原材料，动力资源，资金，劳力等）可以用来生产n种不同产品。假设有关的数据为：•设x1、x2、…、xn分别表示n种产品的产量，则其数学模型为：上页下页返回1122maxnnZcxcxcx1111221121122222112212.0,0,,0nnnnmmmnnmnaxaxaxbaxaxaxbstaxaxaxbxxx上页下页返回【例1.2】配料问题一饲养场饲养动物出售，每只动物每天至少需要700克蛋白质,30克矿物质，100毫克维生素。现有四种饲料可供选用，各种饲料每公斤营养成分含量及单价如下表所示；饲料营养成分ⅠⅡⅢⅣ需要量蛋白质3215700克矿物质10.50.2230克维生素0.510.32.5100毫克单价(元/公斤）0.81.20.62四种饲料各采购多少，才能使总费用最小？上页下页返回12341234123412343257000.50.2.230.0.50.32.5100,,,0xxxxxxxxstxxxxxxxx【解】设x1、x2、x3、x4分别表示四种饲料的采购量，那么该问题的数学模型可以表示为：1234min0.81.20.62Zxxxx上页下页返回•上述模型推广到一般情况为：•每只动物每天至少需要有m种不同营养成分bi；•有n种饲料可供选用，每公斤第j种饲料所含第i种营养成分量为aij;•第j种饲料的单价为cj。i=1,2,…，m,j=1,2，…,n。•设x1、x2、…、xn分别表示n种产品的产量，则其数学模型为：上页下页返回1122minnnZcxcxcx1111221121122222112212.0,0,,0nnnnmmmnnmnaxaxaxbaxaxaxbstaxaxaxbxxx上页下页返回【例1.3】运输问题设有两个砖厂A1、A2，产量分别为23万块、27万块，现将其产品联合供应三个施工现场B1、B2、B3，其需要量分别为17万块、18万块、15万块。各产地到各施工现场的单位运价如下表：问如何调运才能使总运费最省？现场砖厂B1B2B3A15147A26189上页下页返回【解】设xij表示从砖厂Ai运至现场Bj的数量(i=1，2;j=1,2，3),则其数学模型如下：111213212223112112221323232717.18150(1,2,1,2,3)ijxxxxxxxxstxxxxxij111213212223min51476189Zxxxxxx上页下页返回决策变量（Decisionvariables）目标函数（Objectivefunction）约束条件（Constraintconditions）可行解（Feasiblesolution）可行域（Feasibleregion)最优解（Optimalsolution)•基本概念问题中要确定的未知量，表明规划中的用数量表示的方案、措施，可由决策者决定和控制。它是决策变量的函数指决策变量取值时受到的各种资源条件的限制，通常表达为含决策变量的等式或不等式。满足约束条件的决策变量的取值范围可行域中使目标函数达到最优的决策变量的值满足约束条件的决策变量的取值上页下页返回线性规划问题的共同特征•一组决策变量X表示一个方案,一般X大于等于零。•约束条件是线性等式或不等式。•目标函数是线性的。求目标函数最大化或最小化上页下页返回线性规划模型的一般形式11221111221121122222112212max(min)......(,)...(,)......................................................(,),,...,0nnnnnnmmmnnmnZcxcxcxaxaxaxbaxaxaxbaxaxaxbxxx上页下页返回线性规划问题的标准形式•标准形式为:1122111122112112222211221212.......................................................,,...,0,,...0nnnnnnmmmnnmnmmaxZcxcxcxaxaxaxbaxaxaxbstaxaxaxbxxxbbb目标函数最大约束条件等式决策变量非负上页下页返回标准形的假定(.00,10-),irankAmmbbni(1)矩(2).若有可对第个约束方程两边同阵A时乘以的秩.上页下页返回–简写为11max1,2,....01,2,...,njjinijjijjZcxaxbimstxjn上页下页返回–用向量表示),...cc,(cC,...2,10max212121n211b...bbba...aaPx...xxXnjxbxPCXZmmjjjjnjnijj其中：上页下页返回–用矩阵表示决策变量向量-X价值向量-C资源向量0...000),...,,(.........................0max3211111bPPPaaaaAXbAXCXZmnmnC—价值向量b—资源向量X—决策变量向量A—资源消耗系数矩阵111121...................(,,...,)......nnmmnaaAPPPaa上页下页返回•minZ=CX等价于maxZ’=-CX•“”约束：加入非负松驰变量一般线性规划问题的标准形化例：12121212max2328416.412,0Zxxxxxstxxx目标函数约束条件上页下页返回•minZ=CX等价于maxZ’=-CX•“”约束：加入非负松驰变量一般线性规划问题的标准形化12345123142512345max2300028416.412,,,,0zxxxxxxxxxxstxxxxxxx例：上页下页返回•“”约束：减去非负松弛变量；0,''kkkkkxxxxx令123123123123123min2372.327,0,zxxxxxxxxxstxxxxxx无约束Maxx6x7例：kx•可正可负（即无约束）；'''333xxx上页下页返回解：标准形为'''123367'''12336'''12337'''1233'''123367max23()00()7()2.32()7,,,,,0Zxxxxxxxxxxxxxxxxstxxxxxxxxxx上页下页返回【例1.4】下料问题：某一机床需要用甲、乙、丙三种规格的钢轴各一根，这些轴的规格分别是2.9,2.1,1.5(m),这些钢轴需要用同一种圆钢来做，圆钢长度为7.4m。现在要制造100台机床，最少要用多少圆钢来生产这些钢轴？【解】第一步：设一根圆钢切割成甲、乙、丙三种钢轴的根数分别为y1,y2,y3,则切割方式可用不等式2.9y1+2.1y2+1.5y3≤7.4表示，求这个不等式的非负整数解共有8组，也就是有8种下料方式，如下表所示：方案规格12345678y1(2.9m)21110000y2(2.1m)02103210y3(1.5m)10130234余料0.10.30.901.10.20.81.4上页下页返回•设x1、x2、…、x8表示按8种方案下料的圆钢根数，则问题的数学模型为：82,1,010043231002321002.876431765324321，jxxxxxxxxxxxxxxxxtsj87654321minxxxxxxxxZ＋上页下页返回【例1.5】投资问题：某投资公司在第一年有100万元资金，每年都有如下的投资方案可供考虑采纳：“假使第一年投入一笔资金，第二年又继续投入此资金的50%，那么到第三年就可回收第一年投入资金的一倍金额。”投资公司要设法决定最优的投资策略使第六年所掌握的资金最多。【解】设x1为第一年的投资;x2为第一年的保留资金；100：21xx则设x3为第二年新的投资；x4为第二年的保留资金；2431)2(：xxxx则上页下页返回•设x5为第三年新的投资；x6为第三年的保留资金；146532)2(：xxxxx则368752)2(：xxxxx则•设x7为第四年新的投资；第四年的保留资金x8；•设x9为第五年的保留资金：第五年不再进行新的投资，因为这笔投资要到第七年才能回收。589722：xxxx则•约束条件保证每年满足如下的关系：追加投资金额+新投资金额+保留资金=可利用的资金总额。上页下页返回•到第六年实有资金总额为x9+2x7，整理后得到下列线性规划模型：maxZ=2x7+x99,,2,1,0022402224022240222100.98758765365431432121jxxxxxxxxxxxxxxxxxxxxxtsj上页下页返回【补充习题】三江购物中心第二分店决定：销售人员每周连续工作5天后连续休息2天，轮流休息。根据统计，该分店每天需要的销售人员如下表所示：05101520253035星期一星期三星期五星期日所需人员星期需要人员星期一15星期二24星期三25星期四19星期五31星期六28星期日28该分店最少安排多少销售人员，如何安排销售人员轮休？上页下页返回【解】设x1、x2、…、x7为星期一、…星期日休息完后第一天的上班人数，则7,,2,1,028283119252415min765436543254321743217632176521765417654321jxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxZj求解得到：（8，0，12，0，11，5，0）该分店共需要36名销售人员。星期一有12人休息，24人上班星