Python整数规划—分枝定界法

拼搏现实的明天。 2023-09-28 20:48 9阅读 0赞

> 分枝定界法可用于解纯整数或混合的整数规划问题。在本世纪六十年代初由 Land Doig 和 Dakin 等人提出的。由于这方法灵活且便于用计算机求解，所以现在它已是解 整数规划的重要方法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂 选址问题、背包问题及分配问题等。

--------------------

### 分枝定界法 ###

### 1.定义 ###

对有约束条件的最优化问题（其可行解为有限数）的所有可行解空间恰当地进行系 统搜索，这就是分枝与定界内容。通常，把全部可行解空间反复地分割为越来越小的子 集，称为分枝；并且对每个子集内的解集计算一个目标下界（对于最小值问题），这称 为定界。在每次分枝后，凡是界限超出已知可行解集目标值的那些子集不再进一步分枝，这样，许多子集可不予考虑，这称剪枝。这就是分枝定界法的主要思路。

设有最大化的整数规划问题 A ，与它相应的线性规划为问题 B ，从解问题 B 开始， 若其最优解不符合 A 的整数条件，那么 B 的最优目标函数必是 A 的最优目标函数 ![z^\{\*\}][z] 的 上界，记作 ![\\overline\{z\}][overline_z] ；而 A 的任意可行解的目标函数值将是 ![z^\{\*\}][z] 的一个下界 ![\\underline\{z\}][underline_z]。分枝定界法就是将 B 的可行域分成子区域的方法。逐步减小 ![\\overline\{z\}][overline_z] 和增大 ![\\underline\{z\}][underline_z]，最终求到 ![z^\{\*\}][z] 。现用下例来 说明：

###  ###

### 2.例题解说 ###

**例 3 求解下述整数规划：**

![\\begin\{aligned\} &\\operatorname\{Max\} \\quad z=40 x\_\{1\}+90 x\_\{2\} \\\\ &\\left\\\{\\begin\{array\}\{l\} 9 x\_\{1\}+7 x\_\{2\} \\leq 56 \\\\ 7 x\_\{1\}+20 x\_\{2\} \\leq 70 \\\\ x\_\{1\}, x\_\{2\} \\geq 0 \\ \\end\{array\}\\right. \\end\{aligned\}][begin_aligned_ _operatorname_Max_ _quad z_40 x_1_90 x_2_ _ _left_begin_array_l_ 9 x_1_7 x_2_ _leq 56 _ 7 x_1_20 x_2_ _leq 70 _ x_1_ x_2_ _geq 0 _ _end_array_right. _end_aligned]且为整数

（i）先不考虑整数限制，即解相应的线性规划B，得最优解为：

使用python单纯形表得出：

objctive        |                   355.88                   |
            solution        |  4.81  |  1.82  |   0    |   0    |

最优解为：![x\_\{1\}=4.81, x\_\{2\}=1.82, z=355.88][x_1_4.81_ x_2_1.82_ z_355.88]

可见它不符合整数条件。这时 ![z][z 1]是问题![A][]的最优目标函数值 ![z^\{\*\}][z] 的上界，记作 ![\\overline\{z\}][overline_z] 。而 ![x\_\{1\}=0,x\_\{2\}=0][x_1_0_x_2_0]显然是问题 ![A][] 的一个整数可行解，这时![z=0][z_0] ，是 ![z^\{\*\}][z]的一个下界，记作 ![\\underline\{z\}][underline_z]， 即![0\\leq z^\{\*\}\\leq 356][0_leq z_leq 356]。

（ii）因为![x\_\{1\},x\_\{2\}][x_1_x_2]当前均为非整数，故不满足整数要求，任选一个进行分枝。设选 1 x 进行分枝，把可行集分成 2 个子集：

![x\_\{1\}\\leq \[4.81\]=4,x\_\{1\}\\geq \[4.81\]+1=5][x_1_leq _4.81_4_x_1_geq _4.81_1_5]

因为 4 与 5 之间无整数，故这两个子集的整数解必与原可行集合整数解一致。这 一步称为分枝。这两个子集的规划及求解如下：

问题![B\_\{1\}][B_1]：

![\\begin\{aligned\} &\\quad \\operatorname\{Max\} \\quad z=40 x\_\{1\}+90 x\_\{2\} \\\\ &\\left\\\{\\begin\{array\}\{l\} 9 x\_\{1\}+7 x\_\{2\} \\leq 56 \\\\ 7 x\_\{1\}+20 x\_\{2\} \\leq 70 \\\\ 0 \\leq x\_\{1\} \\leq 4, x\_\{2\} \\geq 0 \\end\{array\}\\right. \\end\{aligned\}][begin_aligned_ _quad _operatorname_Max_ _quad z_40 x_1_90 x_2_ _ _left_begin_array_l_ 9 x_1_7 x_2_ _leq 56 _ 7 x_1_20 x_2_ _leq 70 _ 0 _leq x_1_ _leq 4_ x_2_ _geq 0 _end_array_right. _end_aligned]

最优解为：![x\_\{2\}=4.0,x\_\{2\}=2.1,z\_\{1\}=349][x_2_4.0_x_2_2.1_z_1_349]

问题![B\_\{2\}][B_2]：

![\\begin\{aligned\} & \\quad \\text \{ Max \} \\quad z=40 x\_\{1\}+90 x\_\{2\} \\\\ &\\left\\\{\\begin\{array\}\{l\} 9 x\_\{1\}+7 x\_\{2\} \\leq 56 \\\\ 7 x\_\{1\}+20 x\_\{2\} \\leq 70 \\\\ x\_\{1\} \\geq 5, x\_\{2\} \\geq 0 \\end\{array\}\\right. \\end\{aligned\}][begin_aligned_ _ _quad _text _ Max _ _quad z_40 x_1_90 x_2_ _ _left_begin_array_l_ 9 x_1_7 x_2_ _leq 56 _ 7 x_1_20 x_2_ _leq 70 _ x_1_ _geq 5_ x_2_ _geq 0 _end_array_right. _end_aligned]

最优解为：![x\_\{2\}=5.0,x\_\{2\}=1.57,z\_\{1\}=341.4][x_2_5.0_x_2_1.57_z_1_341.4]

再定界：![0\\leq z^\{\*\}\\leq 349][0_leq z_leq 349]

（iii）对问题 B1 再进行分枝得问题 B11和 B12 ，它们的最优解为

![\\begin\{array\}\{ll\} B\_\{11\}: & x\_\{1\}=4, x\_\{2\}=2, z\_\{11\}=340 \\\\ B\_\{12\}: & x\_\{1\}=1.43, \\mathrm\{x\}\_\{2\}=3.00, z\_\{12\}=327.14 \\end\{array\}][begin_array_ll_ B_11_ _ x_1_4_ x_2_2_ z_11_340 _ B_12_ _ x_1_1.43_ _mathrm_x_2_3.00_ z_12_327.14 _end_array]

再定界：![340\\leq z^\{\*\}\\leq 341][340_leq z_leq 341]，并将![B\_\{12\}][B_12]剪枝。

（iv）对问题 ![B\_\{2\}][B_2]再进行分枝得问题 ![B\_\{21\}][B_21]和![B\_\{22\}][B_22]，它们的最优解为

![B\_\{21\}:x\_\{1\}=5.44,x\_\{2\}=1.00,z\_\{22\}=308][B_21_x_1_5.44_x_2_1.00_z_22_308]。

![B\_\{22\}:][B_22 1] 无可行解。

将 ![B\_\{21\},B\_\{22\}][B_21_B_22] 剪枝。

于是可以断定原问题的最优解为：

![x\_\{1\}=4,x\_\{2\}=2,z^\{\*\}=340][x_1_4_x_2_2_z_340]

### **3.数学建模过程：** ###

#### **分枝定界法求解整数规划（最大化）问题的步骤为：** ####

开始，将要求解的整数规划问题称为问题 A ，将与它相应的线性规划问题称为问 题 B 。

解问题 B 可能得到以下情况之一：

（a） B 没有可行解，这时 A 也没有可行解，则停止．

（b） B 有最优解，并符合问题 A 的整数条件， B 的最优解即为 A 的最优解，则 停止。

（c） B 有最优解，但不符合问题 A 的整数条件，记它的目标函数值为![\\overline\{z\}][overline_z] 。

用观察法找问题 A 的一个整数可行解，一般可取![x\_\{j\}=0,j=1,...,n,][x_j_0_j_1_..._n] 试探， 求得其目标函数值，并记作![\\underline\{z\}][underline_z]。以 ![z^\{\*\}][z] 试探， 求得其目标函数值，并记作![\\underline\{z\}\\leq z^\{\*\}\\leq \\overline\{z\}][underline_z_leq z_leq _overline_z]进行迭代。

#### 建模过程 ####

第一步：分枝，在 B 的最优解中任选一个不符合整数条件的变量![x\_\{j\}][x_j] ，其值为![b\_\{j\}][b_j] ， 以\[ ![b\_\{j\}][b_j] \] 表示小于![b\_\{j\}][b_j] 的最大整数。构造两个约束条件

![x\_\{j\}\\leq \[b\_\{j\}\]][x_j_leq _b_j]和![x\_\{j\}\\geq \[b\_\{j\}\]+1][x_j_geq _b_j_1]

将这两个约束条件，分别加入问题 B ，求两个后继规划问题 ![B\_\{1\}][B_1] 和 ![B\_\{2\}][B_2] 。不考虑整数条件 求解这两个后继问题。

定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出 最优目标函数值最大者作为新的上界 ![\\overline\{z\}][overline_z] 。从已符合整数条件的各分支中，找出目标函数 值为最大者作为新的下界 ![\\underline\{z\}][underline_z] ，若无作用 ![\\underline\{z\}][underline_z] 不变。

第二步：比较与剪枝，各分枝的最优目标函数中若有小于 z 者，则剪掉这枝，即 以后不再考虑了。若大于 ![\\underline\{z\}][underline_z] ，且不符合整数条件，则重复第一步骤。一直到最后得到 ![z^\{\*\}][z]= ![\\underline\{z\}][underline_z] 为止。得最优整数解 ![x\_\{j\}^\{\*\}][x_j 1]，![j=1,...,n][j_1_..._n]。

### 4.编程实现 ###

#### **使用python实现分枝定界法算法：** ####

from scipy.optimize import linprog
    import numpy as np
    from math import floor, ceil
    import copy
    
    
    class Node(object):
        def __init__(self, x_bounds=[], freeze_var_list=[], index=0, upper_or_lower=0):
            self._x_bounds = x_bounds
            self._freeze_var_list = freeze_var_list
            self._index = index
            self._upper_or_lower = upper_or_lower
    
            print("创建节点: {}".format(index))
            print('')
    
        def freeze_var(self, index, val):
            self._x_bounds[index][0] = val
            self._x_bounds[index][1] = val
            self._freeze_var_list.append(index)
    
        def set_lp_res(self, res):
            self._res = res
            s = ""
            for l in range(len(self._res['x'])):
                if l in self._freeze_var_list:
                    s += "[" + str(self._res['x'][l]) + "]"
                else:
                    s += " " + str(self._res['x'][l])
            print("x: ", s)
    
        def check_integer_val_solved(self, m):
            return True if m == len(self._freeze_var_list) else False
    
    
    class BbAlgorithm(object):
        def __init__(self, c, a_ub, b_ub, x_b, integer_val):
            self.c = c
            self.a_ub = a_ub
            self.b_ub = b_ub
            self.x_b = x_b
            self._integer_val = integer_val
            self.best_solution = float('inf')
            self.best_node = None
            self.nodes = []
            self.nodes_solution = []
    
        def solve_lp(self, cur_x_b):
            return linprog(self.c, A_ub=self.a_ub, b_ub=self.b_ub, bounds=cur_x_b)
    
        def check_fessible(self, res):
            if res['status'] == 0:
                return True
            elif res['status'] == 2:
                return False
            else:
                raise ("问题无界")
    
        def add_node(self, node):
            res = self.solve_lp(node._x_bounds)
            if self.check_fessible(res) and res['fun'] < self.best_solution:
                node.set_lp_res(res)
                self.nodes_solution.append(res['fun'])
                self.nodes.append(node)
                if node.check_integer_val_solved(len(self._integer_val)):
                    self.best_solution = res['fun']
                    self.best_node = node
                    print("----------------当前解决方案-------------------")
                    print("x: ", node._res['x'])
                    print("z: ", node._res['fun'])
                    print("---------------------------------------------------\n")
                print("==> 将节点添加到树列表: ", node._index)
                print("==> 当前节点: ", self.nodes_solution)
                print("")
                return True
            else:
                print("==> 节点不可行: ", node._index)
                print("==> 当前节点: ", self.nodes_solution)
                print("")
                return False
    
        def del_higher_val_node(self, z_s):
            del_list = []
            for i in range(len(self.nodes_solution)):
                if self.nodes_solution[i] >= z_s:
                    del_list.append(i)
            s = ""
            for i in del_list:
                s += " " + str(self.nodes[i]._index)
            print("删除节点: ", s)
            self.nodes = list(np.delete(self.nodes, del_list))
            self.nodes_solution = list(np.delete(self.nodes_solution, del_list))
            print("当前节点: ", self.nodes_solution)
            print("")
    
        def del_item(self, index):
            print("删除节点: ", self.nodes[index]._index)
            self.nodes = list(np.delete(self.nodes, index))
            self.nodes_solution = list(np.delete(self.nodes_solution, index))
            print("当前节点: ", self.nodes_solution)
            print("")
    
        def check_bounds(self, temp_x_b, index, u_or_l):
            if u_or_l == 1:
                if self.x_b[index][0] is not None and temp_x_b[index][0] is None:
                    return False
                elif self.x_b[index][0] is None and temp_x_b[index][0] is not None:
                    return True
                elif self.x_b[index][0] is not None and temp_x_b[index][0] is not None:
                    return False if(self.x_b[index][0] > temp_x_b[index][0]) else True
            elif u_or_l == 2:
                if self.x_b[index][1] is not None and temp_x_b[index][1] is None:
                    return False
                elif self.x_b[index][1] is None and temp_x_b[index][1] is not None:
                    return True
                elif self.x_b[index][1] is not None and temp_x_b[index][1] is not None:
                    return False if(self.x_b[index][1] < temp_x_b[index][1]) else True
            else:
                print("界限误差")
                exit()
    
        def run(self):
            print("####################### 开始 B & B #####################\n")
            node_count = 0
            node = Node(copy.deepcopy(self.x_b), [], node_count)
            node_count += 1
            res = self.solve_lp(self.x_b)
    
            lower = floor(res['x'][self._integer_val[0]])
            upper = lower + 1
    
            lower_node = Node(copy.deepcopy(self.x_b), [], node_count, 1)
            lower_node.freeze_var(self._integer_val[0], lower)
            self.add_node(lower_node)
            node_count += 1
    
            upper_node = Node(copy.deepcopy(self.x_b), [], node_count, 2)
            upper_node.freeze_var(self._integer_val[0], upper)
            self.add_node(upper_node)
            node_count += 1
    
            while len(self.nodes) > 0:
                index = np.argmin(self.nodes_solution)
                x_b = self.nodes[index]._x_bounds
                freeze_list = self.nodes[index]._freeze_var_list
                res = self.nodes[index]._res
                freeze_var_index = len(freeze_list)
    
                lower = floor(res['x'][self._integer_val[freeze_var_index]])
                upper = lower + 1
                lower_node = Node(copy.deepcopy(x_b), copy.deepcopy(freeze_list), node_count, 1)
                lower_node.freeze_var(self._integer_val[freeze_var_index], lower)
                self.add_node(lower_node)
                node_count += 1
    
                upper_node = Node(copy.deepcopy(x_b), copy.deepcopy(freeze_list), node_count, 2)
                upper_node.freeze_var(self._integer_val[freeze_var_index], upper)
                self.add_node(upper_node)
                node_count += 1
    
                self.del_item(index)
                self.del_higher_val_node(self.best_solution)
                print("############################################################")
            print("")
            print("######################### 最佳解决方案 #######################")
            print(self.best_node._res)
    
    
    if __name__ == "__main__":
        integer_val = [0,1]
        c = [-40, -90]
        A = [[9, 7], [7, 20]]
        b = [56,70]
        x_bounds = [[0, None] for _ in range(len(c))]
        bb_algorithm = BbAlgorithm(c, A, b, x_bounds, integer_val)
        bb_algorithm.run()

输出结果：

####################### 开始 B & B #####################
    
    创建节点: 0
    
    创建节点: 1
    
    x:  [4.0] 2.0999999999901706
    ==> 将节点添加到树列表:  1
    ==> 当前节点:  [-348.99999999911535]
    
    创建节点: 2
    
    x:  [5.0] 1.5714285714280996
    ==> 将节点添加到树列表:  2
    ==> 当前节点:  [-348.99999999911535, -341.4285714285289]
    
    创建节点: 3
    
    x:  [4.0][2.0]
    ----------------当前解决方案-------------------
    x:  [4. 2.]
    z:  -340.0
    ---------------------------------------------------
    
    ==> 将节点添加到树列表:  3
    ==> 当前节点:  [-348.99999999911535, -341.4285714285289, -340.0]
    
    创建节点: 4
    
    ==> 节点不可行:  4
    ==> 当前节点:  [-348.99999999911535, -341.4285714285289, -340.0]
    
    删除节点:  1
    当前节点:  [-341.4285714285289, -340.0]
    
    删除节点:   3
    当前节点:  [-341.4285714285289]
    
    ############################################################
    创建节点: 5
    
    ==> 节点不可行:  5
    ==> 当前节点:  [-341.4285714285289]
    
    创建节点: 6
    
    ==> 节点不可行:  6
    ==> 当前节点:  [-341.4285714285289]
    
    删除节点:  2
    当前节点:  []
    
    删除节点:  
    当前节点:  []
    
    ############################################################
    
    ######################### 最佳解决方案 #######################
         con: array([], dtype=float64)
         fun: -340.0
     message: 'The solution was determined in presolve as there are no non-trivial constraints.'
         nit: 0
       slack: array([6., 2.])
      status: 0
     success: True
           x: array([4., 2.])

[z]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20z%5E%7B*%7D
[overline_z]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20%5Coverline%7Bz%7D
[underline_z]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20%5Cunderline%7Bz%7D
[begin_aligned_ _operatorname_Max_ _quad z_40 x_1_90 x_2_ _ _left_begin_array_l_ 9 x_1_7 x_2_ _leq 56 _ 7 x_1_20 x_2_ _leq 70 _ x_1_ x_2_ _geq 0 _ _end_array_right. _end_aligned]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20%5Cbegin%7Baligned%7D%20%26%5Coperatorname%7BMax%7D%20%5Cquad%20z%3D40%20x_%7B1%7D&plus;90%20x_%7B2%7D%20%5C%5C%20%26%5Cleft%5C%7B%5Cbegin%7Barray%7D%7Bl%7D%209%20x_%7B1%7D&plus;7%20x_%7B2%7D%20%5Cleq%2056%20%5C%5C%207%20x_%7B1%7D&plus;20%20x_%7B2%7D%20%5Cleq%2070%20%5C%5C%20x_%7B1%7D%2C%20x_%7B2%7D%20%5Cgeq%200%20%5C%20%5Cend%7Barray%7D%5Cright.%20%5Cend%7Baligned%7D
[x_1_4.81_ x_2_1.82_ z_355.88]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20x_%7B1%7D%3D4.81%2C%20x_%7B2%7D%3D1.82%2C%20z%3D355.88
[z 1]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20z
[A]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20A
[x_1_0_x_2_0]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20x_%7B1%7D%3D0%2Cx_%7B2%7D%3D0
[z_0]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20z%3D0
[0_leq z_leq 356]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%200%5Cleq%20z%5E%7B*%7D%5Cleq%20356
[x_1_x_2]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20x_%7B1%7D%2Cx_%7B2%7D
[x_1_leq _4.81_4_x_1_geq _4.81_1_5]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20x_%7B1%7D%5Cleq%20%5B4.81%5D%3D4%2Cx_%7B1%7D%5Cgeq%20%5B4.81%5D&plus;1%3D5
[B_1]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20B_%7B1%7D
[begin_aligned_ _quad _operatorname_Max_ _quad z_40 x_1_90 x_2_ _ _left_begin_array_l_ 9 x_1_7 x_2_ _leq 56 _ 7 x_1_20 x_2_ _leq 70 _ 0 _leq x_1_ _leq 4_ x_2_ _geq 0 _end_array_right. _end_aligned]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20%5Cbegin%7Baligned%7D%20%26%5Cquad%20%5Coperatorname%7BMax%7D%20%5Cquad%20z%3D40%20x_%7B1%7D&plus;90%20x_%7B2%7D%20%5C%5C%20%26%5Cleft%5C%7B%5Cbegin%7Barray%7D%7Bl%7D%209%20x_%7B1%7D&plus;7%20x_%7B2%7D%20%5Cleq%2056%20%5C%5C%207%20x_%7B1%7D&plus;20%20x_%7B2%7D%20%5Cleq%2070%20%5C%5C%200%20%5Cleq%20x_%7B1%7D%20%5Cleq%204%2C%20x_%7B2%7D%20%5Cgeq%200%20%5Cend%7Barray%7D%5Cright.%20%5Cend%7Baligned%7D
[x_2_4.0_x_2_2.1_z_1_349]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20x_%7B2%7D%3D4.0%2Cx_%7B2%7D%3D2.1%2Cz_%7B1%7D%3D349
[B_2]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20B_%7B2%7D
[begin_aligned_ _ _quad _text _ Max _ _quad z_40 x_1_90 x_2_ _ _left_begin_array_l_ 9 x_1_7 x_2_ _leq 56 _ 7 x_1_20 x_2_ _leq 70 _ x_1_ _geq 5_ x_2_ _geq 0 _end_array_right. _end_aligned]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20%5Cbegin%7Baligned%7D%20%26%20%5Cquad%20%5Ctext%20%7B%20Max%20%7D%20%5Cquad%20z%3D40%20x_%7B1%7D&plus;90%20x_%7B2%7D%20%5C%5C%20%26%5Cleft%5C%7B%5Cbegin%7Barray%7D%7Bl%7D%209%20x_%7B1%7D&plus;7%20x_%7B2%7D%20%5Cleq%2056%20%5C%5C%207%20x_%7B1%7D&plus;20%20x_%7B2%7D%20%5Cleq%2070%20%5C%5C%20x_%7B1%7D%20%5Cgeq%205%2C%20x_%7B2%7D%20%5Cgeq%200%20%5Cend%7Barray%7D%5Cright.%20%5Cend%7Baligned%7D
[x_2_5.0_x_2_1.57_z_1_341.4]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20x_%7B2%7D%3D5.0%2Cx_%7B2%7D%3D1.57%2Cz_%7B1%7D%3D341.4
[0_leq z_leq 349]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%200%5Cleq%20z%5E%7B*%7D%5Cleq%20349
[begin_array_ll_ B_11_ _ x_1_4_ x_2_2_ z_11_340 _ B_12_ _ x_1_1.43_ _mathrm_x_2_3.00_ z_12_327.14 _end_array]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20%5Cbegin%7Barray%7D%7Bll%7D%20B_%7B11%7D%3A%20%26%20x_%7B1%7D%3D4%2C%20x_%7B2%7D%3D2%2C%20z_%7B11%7D%3D340%20%5C%5C%20B_%7B12%7D%3A%20%26%20x_%7B1%7D%3D1.43%2C%20%5Cmathrm%7Bx%7D_%7B2%7D%3D3.00%2C%20z_%7B12%7D%3D327.14%20%5Cend%7Barray%7D
[340_leq z_leq 341]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20340%5Cleq%20z%5E%7B*%7D%5Cleq%20341
[B_12]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20B_%7B12%7D
[B_21]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20B_%7B21%7D
[B_22]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20B_%7B22%7D
[B_21_x_1_5.44_x_2_1.00_z_22_308]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20B_%7B21%7D%3Ax_%7B1%7D%3D5.44%2Cx_%7B2%7D%3D1.00%2Cz_%7B22%7D%3D308
[B_22 1]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20B_%7B22%7D%3A
[B_21_B_22]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20B_%7B21%7D%2CB_%7B22%7D
[x_1_4_x_2_2_z_340]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20x_%7B1%7D%3D4%2Cx_%7B2%7D%3D2%2Cz%5E%7B*%7D%3D340
[x_j_0_j_1_..._n]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20x_%7Bj%7D%3D0%2Cj%3D1%2C...%2Cn%2C
[underline_z_leq z_leq _overline_z]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20%5Cunderline%7Bz%7D%5Cleq%20z%5E%7B*%7D%5Cleq%20%5Coverline%7Bz%7D
[x_j]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20x_%7Bj%7D
[b_j]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20b_%7Bj%7D
[x_j_leq _b_j]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20x_%7Bj%7D%5Cleq%20%5Bb_%7Bj%7D%5D
[x_j_geq _b_j_1]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20x_%7Bj%7D%5Cgeq%20%5Bb_%7Bj%7D%5D&plus;1
[x_j 1]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20x_%7Bj%7D%5E%7B*%7D
[j_1_..._n]: https://latex.csdn.net/eq?%5Cdpi%7B120%7D%20j%3D1%2C...%2Cn