运筹学第四章整数规划与分配问题.ppt

该【运筹学第四章整数规划与分配问题 】是由【落意心冢】上传分享，文档一共【70】页，该文档可以免费在线阅读，需要了解更多关于【运筹学第四章整数规划与分配问题 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。运筹学第四章整数规划与分配问题整数线性规划的一般形式:不考虑整数要求时,最优解为:X=(,)TZ=13(见下页图解法)考虑整数要求时,最优解为:X=(4,1)TZ=14凑整(3,2)可行,非最优,Z=13。(4,3),(4,2),(3,3)不可行二、整数规划的分类决策变量全部取整数,约束系数和约束常数项也取整数的整数线性规划。决策变量全部取整数,约束系数和约束常数项可取非整数的整数线性规划。纯整数线性规划可化为全整数线性规划。决策变量中有一部分取整数值,另一部分可取非整数值的整数线性规划。-1整数线性规划决策变量只能取0或1的整数线性规划。三、0-1变量(或称逻辑变量)在模型中的应用整数规划模型对研究管理问题有重要意义。很多不能归结为线性规划数学模型的管理问题,却可以通过设置逻辑变量建立起整数规划数学模型。匈牙利法的步骤:第一步效率矩阵每行都减去该行的最小元素;第二步效率矩阵每列都减去该列的最小元素;此时,效率矩阵的每行每列都有0元素。第三步寻找位于不同行不同列的0元素,也就是寻找能覆盖所有0元素的最少直线数。方法:,对0元素打上()号,然后对打()的0元素所在列画一条直线,依次进行到最后一行;,对0元素打上()号,然后对打()的0元素所在行画一条直线,依次进行到最后一列;.、,可能出现三种情况:(1)若能找到m个位于不同行不同列的0元素(即带()的0元素),则令(0)处的xij=1,求解结束;(2)若有形成闭回路的0元素,则任选一个打(),然后对每个间隔的0元素打(),同时对打()的0元素所在行(或列)画一条直线。(3)若位于不同行不同列的0元素[即带()的0元素]少于m,转第四步。第四步为产生m个位于不同行不同列的0元素,用定理一对效率矩阵进行调整,使之生成新的0元素。方法:;;;。