(5.3.2)-2.1线性规划问题数学建模

脚本-线性规划问题（ppt1,ppt2）同学，你好！这节课我们来学习线性规划问题。(ppt3)首先，我们来探讨一下规划模型的重要性。(ppt4)（动画1）规划模型是一类有着广泛应用的确定性系统优化模型。（动画2）例如，嫦娥三号软着陆轨道确定和最优控制研究利用到了规划模型。（动画3）公交车的最优调度策略也是属于规划模型。(ppt5)（动画1）还有项目投资利润最大化，（动画2）以及医院病床的合理性安排，都离不开规划模型。(ppt6)接下来，我们来了解规划模型中最基本的模型，线性规划模型。(ppt7)（动画1）首先，什么是线性规划问题呢？（动画2）线性规划问题是在一组线性约束条件的限制下，求一线性目标函数最大或最小的问题。（动画3）他的特征是在满足一组线性约束和变量非负的条件下，求多变量线性函数值（最大值或最小值）。（动画4）因为他的这个特征，所以所有的线性规划模型可以化为相同的标准形式，这样就可以采用固定的方法求解，比如单纯形法。(ppt8)（动画1）然后我们来了解一下线性规划问题的标准形式。（动画2）线性规划问题的目标函数是：max𝑧=𝑐_1𝑥_1+𝑐_2𝑥_2+……+𝑐_𝑛𝑥_𝑛，（动画3）其约束条件为a_11*x_1加上a_12*x_2一直加到a_1n*x_n等于b_1，类似的可以得到第m个约束条件为a_m1*x_1加上a_m2*x_2一直加到a_mn*x_n等于b_m。并且x_1,x_2,…,x_n都是大于等于0的。B_1,b_2,…,b_m均为非负值。(ppt9)（动画1）若令C=(c_1,c_2,…,c_n)的转置，X=(x_1,x_2,…,x_n)的转置，A=约束条件的系数矩阵，B=(b_1,b_2,…,b_m)的转置。（动画2）那么，线性规划问题的标准形可以写为：（动画3）目标函数：maxz=C的转置乘以X。（动画4）约束条件可以写为：AX=B，且X大于等于0。(ppt10)（动画1）那么，一个非标准形的问题如何转化为标准形呢？（动画2）第一，若目标函数是求极小值，那么就等价于对标准形的目标函数求负。（动画3）第二，当右端的项𝑏_𝑖小于0时，只需将等式两端同乘以(−1),则等式右端(−𝑏_𝑖)就大于0。（动画4）第三，若约束条件为不等式时，当约束条件为小于等于时，如5𝑥_1+𝑥_2小于等于24，可以令𝑥_3=24−5𝑥_1−𝑥_2，则此约束条件就成为5𝑥_1+𝑥_2+𝑥_3=24,𝑥_3大于等于0。(ppt11)（动画1）当约束条件为“大于等于”时，如10𝑥_1+9𝑥_2大于等于18，则可以令𝑥_4=10𝑥_1+9𝑥_2−18得10𝑥_1+9𝑥_2−𝑥_4=18,𝑥_4大于等于0。𝑥_3,𝑥_4都是新加上去的变量，取值为非负，加到原约束条件上去的目的是将不等式转化为等式，其中𝑥_3称为松弛变量，𝑥_4称为剩余变量。（动画2）取值为无约束的变量。若𝑥_5的取值无约束，则令𝑥_5=x_5一撇减去x_5两撇，其中x_5一撇，和x_5两撇均大于等于0。（动画3）当𝑥_6小于等于0时，就令x_6一撇=−𝑥_6，即有x_6一撇大于等于0。(ppt12)然后我们来讲一下线性规划问题的python求解方法。（动画1）线性规划的目标函数和约束函数标准形式可写为：目标函数为：𝐦𝐢𝐧𝒛=𝐜^𝑻*𝐱，约束条件为：A*x小于等于b；Aeq*x=beq；x大于等于Lb小于等于Ub。（动画2）函数的linprog格式为（动画3）res=linprog(c,A,b,Aeq,beq,bound)（动画4）其中c代表目标向量；（动画5）A,b代表不等号约束；（动画6）Aeq，beq代表等号约束；（动画7）bound表示决策向量的下界和上界向量所组成的n个元素的元组。(ppt13)接下来我们通过案例来进一步了解线性规划模型。(ppt14)（动画1，2）先来看例一，一奶制品加工厂用牛奶生产A,B两种奶制品，1桶牛奶工人可以在甲类设备上用12小时加工成3千克A,或者工人在乙类设备上用8小时加工成4千克B。假定根据市场需求，生产的A,B全部能售出，且每千克A获利24元，每千克B获利16元。现在加工厂能得到50桶牛奶的供应。正式工人总的劳动时间为480小时，并且甲类设备至多能加工100千克A,乙类设备的加工能力没有限制。试为该厂制定一个生产计划，使获利最大，并进一步讨论以下问题：(1)若可以聘用临时工人以增加劳动时间，是否聘用临时工人？(2)假设由于市场需求变化，每千克A的获利增加到30元，应否改变生产计划？(ppt15)（动画1）我们来解这个线性规划问题，设该厂用𝑥_1桶牛奶生产A,用𝑥_2桶牛奶生产B,所得到的总利润为𝑧(元）。（动画2）先看第一问是否聘用临时工人。（动画3）确定目标函数：由题意知生产一千克A可得利润24元，生产一千克B可得利润16元，而一桶牛奶由一个设备加工，则总利润为：maxz=72*x_1+64*x_2。第二步，确定约束条件，第一个条件是牛奶供应数量的约束，x_1+x_2小于等于50。第二个条件是工人的劳动时间约束，12*x_1+8*x_2小于等于480。第三个条件是工厂的设备约束，3*x_1小于等于100。第四个条件为产品的产量不能为负数，因此x_i都大于等于0。(ppt16)（动画1）根据上面的分析，我们把目标函数与约束条件联立，就可以建立数学模型如下所示。（动画2）最后我们通过python求解，解得𝑥_1=20,𝑥_2=30，即最优解使得不等式的第二个约束条件达到了边界。所以增加劳动时间，会提高收益，因而应该聘用临时工人。(ppt17)（动画1）再来看第二个问题，假设由于市场需求变化，每千克A的获利增加到30元，应否改变生产计划。（动画2）我们可以得到目标函数为：max_z=90x_1+64x_2。约束条件为和问题一中的一样，（动画3）运用python求得结果如下：𝑥_1=20,𝑥_2=30，因为求得的最优解不变，所以不应该改变生产计划。(ppt18)（动画1）再来看第二个例子，一贸易公司专门经营某种杂粮的批发业务.公司现有库容量5000吨的仓库．1月1日，公司拥有库存1000吨杂粮，并有资金20000元．估计第一季度杂粮价格如下表所示，如果买进的杂粮当月到货，但需到下月才能卖出，且规定“货到付款”。公司希望季度末库存为2000吨，问应当采取什么样的买进和卖出政策，才能使三个月总的获利最大？(ppt19)（动画1）先来分析一下问题，首先确定决策变量：要确定每个月买进多少，卖出多少，故设：一、二、三月买进的杂粮吨数分别为分别为x_1，x_2，x_3；一、二、三月卖出杂粮的吨数分别为y_1，y_2，y_3。（动画2）再来确定目标函数：max𝑧=3.10𝑦_1+3.25𝑦_2+2.95𝑦_3−2.85𝑥_1−3.05𝑥_2−2.90𝑥_3（动画3）确定约束条件：依题意，共有四类约束即存货约束、库容约束、资金约束、期末库存约束。下面我们来分别讨论。(ppt20)（动画1）①存货约束：由于当月买进的杂粮只能在下月出售，故每个月卖出的杂粮不能超过上个月末的存货量，即得到存货约束为𝑦_1小于等于1000，𝑦_2小于等于1000−𝑦_1+𝑥_1，𝑦_3小于等于1000−𝑦_1+𝑥_1−𝑦_2+𝑥_2小于等于5000。（动画2）②库容约束：由于库容为5000吨，那么每个月的存货数量不能超过5000吨，不妨设贸易公司每个月都在月底进货，或者是当月在将杂粮卖出以后再进货，这样就会减少库存容量，这个假设是合理的．那么库存容量约束为1000−𝑦_1+𝑥_1小于等于5000；1000−𝑦_1+𝑥_1−𝑦_2+𝑥_2小于等于5000。(ppt21)（动画1）③资金约束：贸易公司的资金除了初始的以外，每个月都要出售杂粮回收资金，在回收资金以后，再进杂粮，每个月进杂粮的数量不能超过其拥有资金能购买的杂粮数量，即得资金约束为：𝑥_1小于等于(20000+3.1*𝑦_1)除以2.85；𝑥_2小于等于(20000+3.1*𝑦_1−2.85*𝑥_1+3.25*𝑦_2)除以3.05；𝑥_3小于等于(20000+3.1*𝑦_1−2.85*𝑥_1+3.25*𝑦_2−3.05*𝑥_2+2.95*𝑦_3)除以2.9。（动画2）④季末库存：题中要求季末的库存为2000吨，得到关系式：1000−𝑦_1+𝑥_1−𝑦_2+𝑥_2−𝑦_3+𝑥_3=2000。显然，每个月出售的杂粮数和买进的杂粮数不能为负，即：𝑥_1,𝑥_2,𝑥_3,𝑦_1,𝑦_2,𝑦_3均大于等于0.(ppt22)（动画1）将上述目标函数和约束条件联立，记可得到该公司的杂粮采购与销售计划的线性规划数学模型。（动画2）求得最终的结果为：𝑥_1=5000,𝑥_2=0,𝑥_3=2000;𝑦_1=1000,𝑦_2=5000,𝑦_3=0时总获利最大。(ppt23)最后我们来了解一些线性规划模型的应用。(ppt24)（动画1）线性规划模型可以用于合理规划线材问题，研究怎么样下料用料最