整数规划问题求解算法

104 阅读 0 评论 69 点赞

我是靠谱客的博主发嗲马里奥，这篇文章主要介绍整数规划问题求解算法，现在分享给大家，希望可以做个参考。

前言：

通过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("nn最优解为: "+finalValue);
    </script>
</body>
</html>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
<!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("nn最优解为: "+finalValue);
    </script>
</body>
</html>