特殊线性规划模型

《特殊线性规划模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、特殊线性规划模型——运输问题，整数规划，0－1规划一、运输问题1．一般模型：m个物资产地（发点）A1,A2,…,Am，n个物资销地（收点）B1,B2,…,Bn，ai为发点Ai的物资供应量（发量），bj为收点Bj对物资的需求量（收量），cij表示把物资从Ai运到Bj的单位运价，xij表示把物资从Ai运到Bj的运输量，问应如何运输才能使运费最小？（假定收发平衡）运输收发平衡单位运价表（简称运输表格）AiBjB1…Bj…BnaiA1c11…c1j…c1na1……………Aici1…cij…cinai……………

2、Amcm1…cmj…cmnambjb1…bj…bn从而得运输问题的线性规划模型称之为运输问题的标准模型，此为产销平衡模型，产销不平衡时，增加虚拟的收点和发点（松弛变量）即可达到产销平衡。2．求解方法：线性规划的解法也适用运输问题，但是针对运输问题的特殊性有其特殊解法——表上作业法（详见有关书籍）。一些名词：闭回路，孤立点，寻找初始基本可行解方法（西北角法，最小元素法），计算检验数方法（位势法）（LINDO和LINGO是美国LINDO系统公司开发的一套专门用于求解最优化问题的软件包。LINDO用于求解线

3、性规划和二次规划问题，LINGO除了具有LINDO的全部功能外，还可以用于求解非线性规划问题，也可以用于一些线性和非线性方程(组)的求解）3．运输模型建立运输模型，就是给出运输收发平衡单位运价表（简称运输表格）。一般模型有：平衡运输问题，不平衡运输问题，有界发量运输问题，运量有界的运输问题，转运问题，多品种物资运输问题，空车调度问题二、整数规划（IP）1．定义决策变量为整数时，该规划称为整数规划例1：解：去掉整数要求后的最优解为（1.5，3.33），是否通过作舍入处理，就可得到最优解？我们发现（2，3

4、），（1，3），（2，4），（1，4）都不是，其实（2,2）或（3,1）才是。另一方面，这种舍入的计算量也是相当大的（多大？）整数规划含纯整数规划（AIP）、混合整数规划（MIP）和0－1规划（BIP）2．求解方法：割平面法，柯莫力割，柯莫力割平面法,分支定界法（隐式枚举法）3．一些例子：例2：现有资金b可用于投资，共有n个项目可供决策者选择，假设j项目所需投资额为aj，投资后第二年年初可得利润cj，设b，aj，cj均为整数，试问为使第二年年初获得最大利润，决策者应选取哪些项目进行投资？解：令xj＝1

5、（对j项目投资），0（否则），得如下整数规划上述问题可以解释为一位旅行者在出发前，考虑他的背包内应装哪些物品，使物品重量之和不超过允许的负荷，而被装物品的使用价值最大。因而常称这类问题为0－1背包问题。