整数规划问题求解算法

素颜马尾好姑娘i 2022-06-04 09:27 185阅读 0赞

### 前言： ###

通过JavaScript实现整数规划问题。

<!DOCTYPE html>
    <html lang="en">
    <head>
        <meta charset="UTF-8">
        <title>整数规划</title>
    </head>
    <body>
        <script> //说明： //1. 约束条件必须全部转化为小于等于 //价值系数 var valueCoefficient = [3, -2, 5]; //约束系数 var coefficients = [ [1, 2, -1, 2], [1, 4, 1, 4], [1, 1, 0, 3], [4, 0, 1, 6] ]; //列出所有结果集 var binary = Math.pow(2, valueCoefficient.length) - 1; var temp; var result; var possibleResult = []; for(var i=binary; i>=0; i--) { result = ""; temp = i.toString(2); for(var j=0; j< valueCoefficient.length-temp.length; j++) { result += "0"; } result = temp + result var array = []; for(var k=0; k<result.length; k++) { array.push(Number(result[k])); } possibleResult.push(array); } //满足条件的所有结果集 var feasibilityResult = []; //遍历所有可能结果集 for(var t=0; t<possibleResult.length; t++) { //是否全部满足约束条件标识符 var flag = 0; //遍历所有约束条件 for(var i=0; i<coefficients.length; i++) { var resultValue = 0; var limitValue = coefficients[i][coefficients[0].length-1]; for(var j=0; j<coefficients[0].length - 1; j++) { var resultValue = resultValue + coefficients[i][j] * possibleResult[t][j]; } //判断左边是否大于右边,如果大于则退出当前循环 if(resultValue > limitValue) { flag = 1; break; } } //如果满足条件则计算目标值 if(flag == 0) { var sum = 0; for(var m=0; m<possibleResult[t].length; m++) { sum = sum + possibleResult[t][m] * valueCoefficient[m]; } feasibilityResult.push(sum); console.table(possibleResult[t]); console.log(sum); } } //找出最优解 var finalValue = feasibilityResult.sort(function(pre, next) { return next - pre; })[0]; console.log("\n\n最优解为: "+finalValue); </script>
    </body>
    </html>

（完）