2015年6月线性规划VIP专享VIP免费

第一部分线性规划§1线性规划问题1.线性规划问题的数学模型例1选用饲料问题某饲养场饲养动物出售，设每头动物每天至少需700g蛋白质、30g矿物质、100mg维生素。现有五种饲料可供选用，各种饲料每kg营养成分含量及单价如下表，要求确定既满足动物生长的营养需要，又使费用最省的选用饲料的方案。饲料蛋白质(g)矿物质(g)维生素(mg)价格()1234532161810.50.220.50.51.00.220.80.20.70.40.30.8模型建立：引入决策变量：设每头动物每天需要选用第种饲料；本题的数学模型为：例2杂粮的买进卖出问题某贸易公司专门经营某种杂粮的批发业务。公司现有库容5000担的仓库。一月一日，公司拥有库存1000担杂粮，并有资金20000百元。估计第一季度杂粮价格如下表。如买进的杂粮当月到货，但需到下月才能卖出，且规定货到付款。公司希望本季度末库存为2000担，问应采取什么样的买进与卖出策略才能使三个月的总利润最大？1月份进货价（百元）出货价（百元）一月二月三月2.853.052.903.103.252.951模型建立（模型假定：假定每个月是先出货，再进货。）引入决策变量：设为每月买进的杂粮担数，为每月卖出的杂粮担数确定目标函数：三个月的总利润写出约束条件：存货限制；库容限制资金限制期末库存决策变量的非负约束：例3人员安排问题某昼夜服务的公交线路每天各时间区段所需司机和乘务员的人数如下表，设司机和乘务员分别在各时间区段一开始时上班，并连续工作八个小时，问该公交线路至少需要配备多少名司机和乘务人员？班次时间所需人数1234566:00~10:0010:00~14:0014:00~18:0018:00~22:0022:00~2:002:00~6:00607060502030模型建立引入决策变量：用表示有名司机和乘务人员在第班次开始时上班；确定目标函数：使配备的司机和乘务员总人数最少，即写出约束条件：为保证第1班所需的司机和乘务员人数，应有，，，，；决策变量的非负约束：22.线性规划问题的标准形式对于具体的线性规划问题；目标函数有的是极大化，有的是极小化；约束条件有的是≤，有的是≥，有的是＝；决策变量可以≥0，也可以≤0，还可以不受限制。为了方便线性规划问题的统一求解，我们规定一个标准形式。………；其中标准形式的特点：①目标函数要求是极大化；②约束条件要求等式约束；③决策变量满足非负约束；④右端常数项非负。引入矩阵和向量：记----目标函数的系数行向量----约束条件系数矩阵；----决策变量列向量；----右端常数项列向量；----的系数列向量则标准形式的矩阵描述为：向量描述为：3.标准形式的化法①极小化化成极大化；如：②化不等式约束为等式约束；如：，其中，并称为松弛变量如：，其中，并称为松弛（或剩余）变量③化决策变量满足非负约束；如：，则令，并用去代替如：符号不限，则令，其中，并用去代替3如：，则令，此时有如：，则令，此时有，并用去代替练习题4.线性规划问题中有关解的概念及线性规划问题的重要性质：①可行解：满足所有约束条件的解；②可行域：所有可行解构成的集合；③最优解：使目标函数值达到最优时的可行解；④基矩阵，基变量，非基变量，基本解，基本可行解。为了了解上述概念，我们先看如下例题对于线性规划问题：其中A为矩阵，且，B为A的任意一个阶满秩子方阵，则称B为线性规划问题的一个基矩阵；B中列向量所对应的决策变量称为基变量，其余的决策变量称为非基变量；令非基变量的取值为0，得基变量相应的取值，由此得到的解称为规划问题的一个基本解；如果基本解满足非负约束，则称它为基本可行解。⑤重要性质：如果线性规划问题存在可行解，则一定存在基本可行解；如果线性规划问题存在有界最优解，则它一定存在有界的最优基本可行解，即线性规划问题的最优解可以在基本可行解处得到。5.线性规划问题的求解方法—单纯形法1）单纯形法的基本思想从线性规划问题的一个基本可行解出发，判断它是否为最优解；如果不是，则将它进行迭代迭代至下一个基本可行解，每次迭代，要使目标函数值有所改善；这样经过有限次迭代后，最终可以找到最优解或判断问题无界。42）基本可行解的迭代过程下面通过实例来介绍例选取一个基矩阵，对应的基变量为，非基变量为，令非基变量的取值为0，得初始基...