线性规划问题的Lingo求解.ppt

说明：(1)从Excel中读取数据有两种方式，一种是根据Excel表格中指定的名称与Lingo程序中设定的名称一致来读取，另一种是采用指定位置的读取数据。 (2)Excel区域命名的方法 (3)Excel文件的位置需要指定文件的具体路径 求解结果为： 例5-10(面试顺序问题)4名同学到一家公司参加3个阶段的面试，要经过初试-复试-面试，不允许插队，面试时间如下表所示: 姓名 初试 复试 面试 13 15 20 乙 10 20 18 丙 20 16 10 丁 8 10 15 4名同学约定他们全部面试完以后一起离开公司，假定现在时间是早上8点，请问他们最早何时离开。 模型建立：记tij为第i名同学参加第j阶段面试需要的时间，xij表示第i名同学参加第j阶段面试的开始时刻(为了方便，记早上8点为0时刻)(i=1,...,4,j=1,..,3),T为完成全部面试的最少时间，则优化目标为： 个人时间的先后次序约束： 同阶段不同同学时间不相容(同阶段靠前同学的完成时间小于靠后同学的开始时间)： 不妨给定i,k的关系为ik。目标可写为如下线性优化： 程序编写： 计算结果： (2)从约束系数的矩阵看，一个模型为A，一个模型为AT，一个模型为m个约束，n个变量，另一个则为n个约束，m个变量。 (3)从数据b和c的位置看，在两个规划模型中两者互换。 (4)两个模型中的变量皆非负。 2、非对称形式的对偶规划 一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。 对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划。 （1）将模型统一为“max，≤”或“min，≥” 的形式，对于其中的等式约束按下面（2）、（3）中的方法处理； （2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制； （3）若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。 下面对关系（2）作一说明。对于关系（3）可以给出类似的解释。 设原规划中第一个约束为等式： a11x1 + … + a1nxn = b1 那么，这个等式与下面两个不等式等价： 则原规划模型可以写成如下形式： 此时已转化为对称形式，可以直接写出其对偶问题： 这里，把y1看作是y1=y1’ - y1’’，于是y1没有非负限制，关系（2）的说明完毕。 对偶定理：若互为对偶问题的线性规划问题(I)和(II)中有一个最优解，则另一个必有最优解，且目标函数值相同。 例5-5(生产决策问题)某工厂可以用A，B两种原料生产I,II,III三种产品，每种产品需要同时用两种原料，有关数据如下表(单位消耗与资源限制)： 产品I 产品II 产品III 现有原料/t 原料A 2 1 2 7 原料B 1 3 2 11 单位产品利润/万元 2 3 1 求：(1)若目前市场上原料A的实际价格为0.5万元/t，工厂应如何决策？ (2)若目前市场上原料B的实际价格为0.8万元/t，工厂应如何决策？ 解：建立模型，设x1,x2,x3分别表示I，II，III的生产量，则模型如下： 对偶问题 模型讨论：若把y1,y2当作原料A，B的定价，用两个单位的A，1个单位的B，若生产产品I只能赚2万元，现在考虑把资源拿到市场上卖，定价y1,y2,使得2y1+y2≥2,也就是一定比生产产品I赚得多。产品II，III同理。 亦即对偶问题的约束条件保证了资源直接在市场上出售一定不会比生产产品获得的利润低，另一方面，为了增强出售资源的市场竞争力，定价希望低一些，定价的目标是在比生产产品获得更多利润的前提下的最小利润，这个定价模型就是对偶问题。 如果把资源A的量由7增加到8，会导致什么结果呢？ 影子价格：在最有情况下，y1的值就是资源A的影子价格，所以要把影子价格与资源A的市场价格做比较，如果影子价格大于市场价格，考虑出售部分资源以获得更大利润，否则，则从市场买进该资源。 影子价格的经济意义：在资源得到最优配置，使总效益最大时，该资源投入量每增加一个单位所带来总收益的增加量。 影子价格是一种静态的资源最优配置价格，不能表现资源在不同时期动态配置时的最优价格，只反映某种资源的稀缺程度和资源与总体积极效益之间的关系，不能代替资源本身的价值。 程序编写： 执行结果如下： 说明：从红框部分知道，A的影子的价格为0.6，B的影子价格为0.8，松弛变量的值都是0，说明约束是紧约束(约束取等号)，即资源没有剩余，影子价格有意义必须是紧约束。 影子价格是对应最优基来说的，如果约束的改变使得最优基发生改变，当前的影子价格也就没有任何意义了。 通过对右端项的灵敏性分析： 在最优基不变时，A,B的右端项变化范围分别为(4.67,22)和(3.5,21) 对问题(1)0.50.6,应该购进原料A，扩大生