整数规划下的最小生成树模型

求解最小生成树的方法虽然很多 ,但是利用LINGO建立相应的整数规划模型是一种新的尝试。本文利用树根和节点级数的概念 ,借助于LINGO建立了求解最小生成树的整数规划模型 ,并对模型中的难点给出了详细的注释。

基于最小生成树的渠道系统优化布局模型

针对平原地区农田灌溉渠道优化布局问题,当前普遍采用渠道布局原则进行布局,但其不能取得成本最优的布局。通过简化平原地区农田灌溉渠道优化布局问题,该文构建了基于最小生成树的渠道优化布局模型。与传统最小生成树模型不同的是该模型涵盖了2级渠道的优化布局问题,而且该模型得到的方案要大于等于1棵最小生成树。为了能利用成熟的最小生产树理论的求解方法,该文通过创建虚拟点概念去除渠道优化布局模型和传统最小生成树模型的区别,运用凸壳理论讨论求解该模型的4种情况,编写求解该模型的LINGO程序,然后将基于最小生成树的渠道优化布局模型用于案例,得到了研究区渠道布局方案。该方案的工程量是16 095 m3,而采用渠道布局原则得到的渠道布局方案的工程量是16 938.25 m3。结果表明基于最小生成树的渠道优化布局模型能得到成本更少的渠道布局方案,即最大程度地控制土地整治费用。研究为控制土地整治项目的费用提供了一条有效途径。