精华内容
下载资源
问答
  • 最短路径问题 什么是最短路径问题 最短路径问题和线性规划间的关系 Python调用Gurobi求解最短路径问题 Dijkstra’s Algorithm Dijkstra’s Algorithm 证明 Dijkstra’s Algorithm 实现

    Shortest Path Problem

    Problem Formulation

    Definition1.1 G=V,E,hG=\langle V, E, h\rangle is a weighted graph where the graph G=V,EG=\langle V, E\rangle is equipped with a positive cost function hh defined on all edges in EE.

    Definition1.2 Fix a weighted graph G=V,E,hG=\langle V, E, h\rangle and OVO \in V the origin, TVT \in V the termination. The shortest-path problem for GG is defined by looking for a path x0x1x1x2xN1xNx_{0} x_{1}-x_{1} x_{2}-x_{N-1} x_{N} withx0=Ox_{0} =O and $ x_{N}=T$ such that the total costt=1Nh(xt1xt)\sum_{t=1}^{N} h\left(x_{t-1} x_{t}\right)is minimized sum.

    Relationship with Mathematical Programming

    在这里插入图片描述
    Note:
    Explanation for the first constraint: Only need to find the shortest path from original to destination, and do not need to go through every vertices in the graph(while TSP needs).

    Using Python with package ‘Gurobi’ to solve the shortest path problem

    Here is an example.
    在这里插入图片描述
    min(i,j)Axijdij(0,j)Ax0j=1(j,t)Axjt=1(i,j)Axij(j,k)Axjk=0jV\{O,T}xij{0,1},(i,j)A\begin{array}{ll}\min & \sum_{(i, j) \in A} x_{i j} d_{i j} \\ & \sum_{(0, j) \in A} x_{0 j}=1 \\ & \sum_{(j, t) \in A} x_{j t}=1 \\ & \sum_{(i, j) \in A} x_{i j}-\sum_{(j, k) \in A} x_{j k}=0 \quad \forall j \in V \backslash\{O, T\} \\ & x_{i j} \in\{0,1\}, \quad \forall(i, j) \in A\end{array}

    from gurobi import *
    import pandas as pd
    import numpy as np
    
    Nodes = ['O','A','B','C','D','E','T']
    Arcs = {
        ('O','A'):2,
        ('O','B'):5,
        ('O','C'):4,
        ('A','B'):2,
        ('A','D'):7,
        ('B','C'):1,
        ('B','D'):4,
        ('B','E'):3,
        ('C','E'):4,
        ('D','E'):1,
        ('D','T'):5,
        ('E','T'):7
    }
    
    model = Model('Shortest Path Problem')
    # add decision variables
    X = {}
    for key in Arcs.keys():
        index = 'x_' + key[0] + ',' + key[1]
        X[key] = model.addVar(vtype = GRB.BINARY,name = index)
    #add objective function
    obj = LinExpr(0)
    for key in Arcs.keys():
        obj.addTerms(Arcs[key],X[key])
    model.setObjective(obj,GRB.MINIMIZE)
    
    # constraint1 1 and constraint 2
    lhs_1 = LinExpr(0) 
    lhs_2 = LinExpr(0)
    for key in Arcs.keys():
        if(key[0] == 'O'): 
            lhs_1.addTerms(1, X[key])
        elif(key[1] == 'T'): 
            lhs_2.addTerms(1, X[key])
    model.addConstr(lhs_1 == 1, name = 'Original flow') 
    model.addConstr(lhs_2 == 1, name = 'Termination flow')
    
    # constraints 3
    for node in Nodes: 
        lhs = LinExpr(0)
        if(node != 'O' and node != 'T'): 
            for key in Arcs.keys():
                if(key[1] == node):
                    lhs.addTerms(1, X[key]) 
                elif(key[0] == node):
                    lhs.addTerms(-1, X[key]) 
        model.addConstr(lhs == 0, name = 'flow conservation')
    
    model.write('model_spp.lp')
    model.optimize()
    print(model.ObjVal)
    for var in model.getVars():
        if(var.x>0):
            print(var.varName,'\t', var.x)
    
    Warning: constraint name "Original flow" has a space
    Gurobi Optimizer version 9.0.3 build v9.0.3rc0 (mac64)
    Optimize a model with 9 rows, 12 columns and 24 nonzeros
    Model fingerprint: 0x988b6d83
    Variable types: 0 continuous, 12 integer (12 binary)
    Coefficient statistics:
      Matrix range     [1e+00, 1e+00]
      Objective range  [1e+00, 7e+00]
      Bounds range     [1e+00, 1e+00]
      RHS range        [1e+00, 1e+00]
    Found heuristic solution: objective 15.0000000
    Presolve removed 9 rows and 12 columns
    Presolve time: 0.00s
    Presolve: All rows and columns removed
    
    Explored 0 nodes (0 simplex iterations) in 0.01 seconds
    Thread count was 1 (of 8 available processors)
    
    Solution count 2: 13 
    
    Optimal solution found (tolerance 1.00e-04)
    Best objective 1.300000000000e+01, best bound 1.300000000000e+01, gap 0.0000%
    13.0
    x_O,A 	 1.0
    x_A,B 	 1.0
    x_B,D 	 1.0
    x_D,T 	 1.0
    

    Dijkstra’s Algorithm

    在这里插入图片描述

    Proof of Dijkstra’s Algorithm

    Optimality of Dijkstra’s algorithm:
    once a node ii^{*} joins PP , its updated value L(i)L\left(i^{*}\right) is the shortest path(W)\left(W^{*}\right) distance. Dijkstra’s algorithm assigns distance labels (from node s) to all other nodes in the graph. Node labels are either temporary or permanent. Initially all nodes have temporary labels. At any iteration, a node with the least distance label is marked as permanent, and the distances to its successors are updated. This is continued until no temporary nodes are left in the graph.Then we prove the optimality of Dijkstra’s algorithm, that is, once a node ii^{*} joins PP , its updated value L(i)L(i^{*})is the shortest path WW^{*} distance. Note that TT is the set of vertices, T=V/PT=V/P, j1j_{1} is the first point of sub path.Note that TT is the set of vertices, T=V/PT=V/P.
    j1j_{1} is the first point of sub path.
    在这里插入图片描述

    Dijkstra’s Algorithm Implementation

    import pandas as pd
    import numpy as np
    import networkx as nx
    import matplotlib.pyplot as plt
    import copy
    import re
    import math
    
    Nodes = ['O','A','B','C','D','E','T']
    Arcs = {
        ('O','A'):2,
        ('O','B'):5,
        ('O','C'):4,
        ('A','B'):2,
        ('A','D'):7,
        ('B','C'):1,
        ('B','D'):4,
        ('B','E'):3,
        ('C','E'):4,
        ('D','E'):1,
        ('D','T'):5,
        ('E','T'):7
    }
    
    Graph = nx.DiGraph()
    # print(Graph.nodes)
    
    for node in Nodes:
        Graph.add_node(node,min_dis = 0, previous_node =None)
    for key in Arcs.keys():
        Graph.add_edge(key[0],key[1],length=Arcs[key])
    
    
    def Dijkstra(Graph , org ,des):
        Q = list(Graph.nodes())  #Q=V/P,the points excluding pionts in P
        for node in Q:
            #Initialization: Graph.nodes[org]['min_dis']=0, else: infinity
            if (node == org) :
                Graph.nodes[node]['min_dis']=0
            else:
                Graph.nodes[node]['min_dis'] =np.inf
        current_node = org
    
        while (len(Q)>0):
            min_dis =np.inf
            # Main parts of the algorithm, select k in Q=V/P, with the smallest L'(k) for all points
            for node in Q:
                if (Graph.nodes[node]['min_dis']<min_dis):
                    current_node =node
                    min_dis=Graph.nodes[node]['min_dis']
            #current_node can be destination,thus holds no current_node
            # Once find the smallest k^{*}, we remove it until no more points should be added to approach termination
            if (current_node !=None):
                Q.remove(current_node)
            #Main parts of the algorithm, update the L'(k) for all point in connected with current_node
            # graph.successsors: fined the point connected with current_node
            for child in Graph.successors(current_node):
                arc = (current_node, child)
                #update the  L'(k) for k in Q=V/P
                dis_temp = Graph.nodes[current_node]['min_dis']+Graph.edges[arc]['length']
                if (dis_temp< Graph.nodes[child]['min_dis']):
                    # If there are k which have the same L'(k), we use the former.
                    Graph.nodes[child]['min_dis']= dis_temp
                    #useful for generate shortest path, current-previous
                    Graph.nodes[child]['previous_node'] = current_node
        #des is the termination, and min_dis is the distance of the whole SP.
        min_dis = Graph.nodes[des]['min_dis']
        current_node = des
        #use list to record the path.
        shortest_path =[current_node]
        #generate shortest path
        while (current_node != org):
            current_node=Graph.nodes[current_node]['previous_node']
            # add current_node(nodes[current_node]['previous_node']) with index 0 in the list
            shortest_path.insert(0,current_node)
        return Graph, shortest_path, min_dis
    
    org ='O'
    des= 'T'
    print(Dijkstra(Graph,org,des))
    

    Author: Pengxiang Zhou, Tsinghua University, Tsinghua Berkeley Shenzhen College (PhD candidate)

    Reference link:

    1. The content of this courseware is from the course “Operations Research”, taught by Li Xiaoxi, department of Mathematical Economics and Mathematical Finance, School of Economics and Management, Wuhan University. \
    2. Dijkstra’s Algorithm Implementation refer to https://blog.csdn.net/zaowuyingshu/article/details/110590947

    Welcome to follow the public account
    在这里插入图片描述

    展开全文
  • % *lpint (BranchBound)- 线性整数规划 % *L01p_e - 0-1整数规划枚举法 % *L01p_ie - 0-1整数规划隐枚举法 % *bnb18 - 非线性整数规划(在MATLAB5.3使用) % *bnbgui - 非线性整数规划图形工具(在MATLAB5.3使用) % *...
  • 第一章 线性规划及单纯形法 线性规划线性规划(Linear Programming简称LP)是运筹学的一个重要分支,也是... 掌握最短路问题及其求解方法;  掌握最大流问题及其求解方法。  掌握最小费用流问题及其求解方法。
  • lingo算法实现最短路

    2014-05-15 20:05:19
    lingo算法实现单源单宿最短路问题代码 线性规划的学习内容 有完整代码,包括带整数约束的
  • 整数规划的分支定界法;用MATLAB优化工具箱解线性规划;用Lingo软件求解;运输问题的数学模型;生产计划安排问题;分段函数的处理方法;人力资源安排问题;投资问题;最短路问题;设备更新问题
  • 第2章 整数线性规划 2.1 割平面法 2.2 分枝定界法 2.3 习题 第3章 无约束优化 3.1 数学预备知识 3.2 无约束优化问题的解 3. 3 用MATLAB优化工具箱解无约束优化 3.4 习题 第4章 非线性...
  • 中文版的,内容有:最优化问题、单纯元型算法、对偶性、原始-对偶算法、最大流有效算法、最短路、最小费用流、算法与复杂性、匹配算法、赋权匹配、指派问题、拟阵、整数线性规划、NP完备问题、近似算法、分支界定、...
  • 离散优化程序,内含枚举法,蒙特卡洛法、线性整数规划,最小生成树、动态规划等等, %*enum - 枚举法 % *monte - 蒙特卡洛法 % *lpint (BranchBound)- 线性整数规划 % *L01p_e - 0-1整数规划枚举法 % *L01p_ie ...
  • matlab代码

    2018-04-14 13:50:56
    % *lpint (BranchBound)- 线性整数规划 % *L01p_e - 0-1整数规划枚举法 % *L01p_ie - 0-1整数规划隐枚举法 % *bnb18 - 非线性整数规划(在MATLAB5.3使用) % *bnbgui - 非线性整数规划图形工具(在MATLAB5.3使用) % *...
  • lpint - 线性整数规划分支定界法 L01p_e - 0-1整数规划枚举法 L01p_ie - 0-1整数规划隐枚举法 0-1 bnb18 - 非线性整数规划 mintreek - 最小生成树kruskal算法 minroute - 最短路dijkstra算法 dynprog - 动态规划 ...
  • 多项式规约

    2019-11-08 11:15:32
    有多项式时间算法的问题和可能没有多项式时间算法的问题 有多项式时间算法 可能没有多项式时间算法 最短路问题 最长路问题 最小割问题 ...整数线性规划问题 多项式规约...

    有多项式时间算法的问题和可能没有多项式时间算法的问题

    有多项式时间算法 可能没有多项式时间算法
    最短路问题 最长路问题
    最小割问题 最大割问题
    2元可满足性问题 3元可满足性问题
    平面图4着色问题 平面图3着色问题
    二部图顶点覆盖问题 一般图顶点覆盖问题
    匹配问题 3D匹配问题
    素性测试问题 质因子分解问题
    线性规划问题 整数线性规划问题

    多项式规约
    问题XX能多项式规约到问题YY:
    对于任意一个问题XX的实例,进行多项式时间的标准计算步骤,加上多项式时间对YY问题求解方法的调用,最终能求解出问题XX,则问题XX能多项式规约到问题YY
    Note:
    问题YY比问题XX要更难,或者难的核心在YY上。
    可以空跑问题YY算法,只是单纯的多项式时间的标准计算步骤

    如果问题XX和问题YY能够相互多项式时间规约,即XpYX\leq_p YYpXY\leq_p X,那么我们用XpYX\equiv_p Y,表示问题XX和问题YY能够相互多项式时间规约。

    由于自规约性,我们以下讨论的都是该问题的判定性问题(决策问题)

    ① 独立集问题 p\equiv_p 顶点覆盖问题
    即若SS是一个大小为kk的独立集当且仅当VSV-S是一个大小为nkn-k的顶点覆盖

    独立集问题
    问题描述:给定一个图G=(V,E)G=(V,E)和一个整数kk,是否存在一个大小为kk的顶点子集,使子集中任意两个顶点不邻接。
    顶点覆盖问题
    问题描述:给定一个图G=(V,E)G=(V,E)和一个整数kk,是否存在一个大小为kk的顶点子集,使图中每一条边至少有一个顶点在上述顶点子集中。

    如下图黑色顶点集合为大小为6的独立集,白色顶点集合为大小为4的顶点覆盖:
    在这里插入图片描述
    证明:
    \Rightarrow
    已知SS是一个大小为kk的独立集,则VSV-S是一个大小为nkn-k的顶点集合。
    考虑任意一条边(u,v)E(u,v)\in E:
    因为SS是一个独立集,要么uSu\notin S,要么vSv\notin S,要么都不属于SS。不可能都属于,因为那样SS就不是独立集了。
    所以要么uVSu\in V-S,要么vVSv\in V-S,要么都属于VSV-S
    根据顶点覆盖的定义,VSV-S覆盖了任意边(u,v)(u,v)
    \Leftarrow
    已知VSV-S是一个大小为nkn-k的顶点覆盖,则SS是一个大小为kk的顶点集合。
    考虑任意一条边(u,v)E(u,v)\in E:
    因为VSV-S是一个顶点覆盖,uVSu\in V-S,要么vVSv\in V-S,要么都属于VSV-S
    所以要么uSu\notin S,要么vSv\notin S,要么都不属于SS
    因此SS是一个独立集。
    证毕!

    ②顶点覆盖问题p\leq_p集合覆盖问题

    集合覆盖问题
    问题描述:给定集合UUSS集合中每个元素都是集合UU的子集,给定整数kk。问能否用SS集合中k\leq k个元素,使它们的并集等于原集合UU
    如图所示,下列集合覆盖大小为k=2k=2:
    在这里插入图片描述
    目标:任意给一个顶点覆盖问题的实例,都能构造出对应的集合覆盖实例。集合覆盖大小为kk当且仅当顶点覆盖大小为kk
    构图思路如下
    原顶点覆盖的顶点相当于集合覆盖中的子集合,原顶点覆盖的边相当于集合覆盖的子集合中元素。
    在这里插入图片描述
    \Rightarrow不妨令XVX\subseteq VGG中大小为kk的顶点覆盖,则Y={Sv:vx}Y = \{S_v: v\in x\}为大小为kk的集合覆盖。
    \Leftarrow不妨令YSY\subseteq S为大小为kk的集合覆盖,则X={v:SvY}X=\{v:S_v\in Y\}GG中大小为kk的顶点覆盖。证毕!

    ③三元可满足性问题P\leq_P独立集问题
    三元可满足性问题
    问题描述:多个文字的并集构成一个从句,多个从句的交集构成一个合取范式(CNF)(CNF)。给定一个合取范式,问是否存在使合取范式为真的分配方案,为一般的SATSAT问题。若限定每个从句中文字的数量为3个,则为三元可满足性问题(3SAT)(3-SAT)
    目标:给定一个3-SAT问题的实例ϕ\phi,我们都能构造出一个图G=(V,E)G=(V,E)独立集问题的实例。3-SAT问题有解,当且仅当GG中有个大小为k=ϕk=|\phi|ϕ|\phi|大小为合取范式中从句的个数。
    构图思路如下

    • GG中三个顶点构成一个三角形表示一个从句,每个节点表示一个文字
    • 每个顶点与其对立节点连线

    在这里插入图片描述
    证明:
    \Rightarrow(偏说明性)
    若对于合取范式ϕ\phi我们找到一个分配方案使其为真,则我们对于图GG每个三角形中选择分配方案中文字为真对应的一个顶点。一共ϕ|\phi|个三角形,每个三角形按照上述方案选择一个顶点,选完后构成的ϕ|\phi|个顶点的集合为图GG的独立集。
    \Leftarrow(偏说明性)
    SS是一个大小为kk的独立集,则由于构图性质,对于每个三角形中有且仅有独立集中的一个顶点。令这些顶点对应合取范式中的文字为真,则合取范式ϕ\phi可满足。

    总结

    3SATp3-SAT\leq_p独立集问题p\equiv_p顶点覆盖p\leq_p集合覆盖

    补充

    目标:决策问题、搜索问题、优化问题这三个问题可以相互多项式规约

    • 决策问题:是否存在一个大小为kk的顶点覆盖
    • 搜索问题:找到一个大小为kk的顶点覆盖
    • 优化问题:找到一个小的顶点覆盖

    由于上述三种问题多项式等价,因此我们之后只以决策问题为例,讨论该问题的性质(该问题属于PP问题、NPNP问题还是NPCNPC问题)。

    展开全文
  • 第3版韩伯棠主编的国家级精品课程 管理运筹学 随书软件 软件使用简单,包括线性规划线性规划、运输、整数规划、目标规划和对策论) 、图与网络(最短路、最小生成树、最大流、关键线路)、以及存储论模型、排队论...
  • 软件使用简单,包括线性规划线性规划、运输、整数规划、目标规划和对策论) 、图与网络(最短路、最小生成树、最大流、关键线路)、以及存储论模型、排队论模型、决策分析、预测、层次分析法模型
  • 管理运筹学软件2.5.zip

    2020-05-18 08:46:53
    韩伯棠管理运筹学配套运算软件,含线性规划、运输问题、整数规划、目标规划、对策论、最短路问题、最小生成树问题、最大流问题、最小费用最大流问题、关键路径问题、存储论、排队论、决策分析、预测、层次分析法等。
  • Python解运筹学问题

    2021-02-22 20:42:37
    Python解运筹学问题PuLP一般线性规划问题构造并求解混合0-1整数规划问题numpy和scipy标准问题(最小值,约束为<=)非标准形式运输问题指派问题(*scipy的linear_sum_assignment*)networkx 解图论问题最小支撑树...

    PuLP

    一般线性规划问题

    例题:无最优解问题

    from pulp import *
    
    #构建问题
    my_LpProblem = pulp.LpProblem("myProblem", LpMaximize)
    # 设置变量
    x1 = pulp.LpVariable("x1", 0, None)
    x2 = pulp.LpVariable("x2", 0, None)
    x3 = pulp.LpVariable("x3", 0, None)
    # 最有函数
    my_LpProblem += -x1+x2+x3
    # 约束条件
    my_LpProblem += x1 - x2 +2*x3 <= 10
    my_LpProblem +=-x1 + x2 +  x3 >= 4
    my_LpProblem +=-x1      +  x3 == 2
    # 求解
    status = my_LpProblem.solve()
    print("Status:", LpStatus[my_LpProblem.status])
    # 打印出最优解
    for v in my_LpProblem.variables():
        print(v.name, "=", v.varValue)
    # 打印最优目标函数值
    print("objective=", value(my_LpProblem.objective))
    

    构造并求解混合0-1整数规划问题

    例题:在这里插入图片描述

    from pulp import *
    
    my_MipProblem = LpProblem("myproblem", LpMinimize)
    
    solution = []
    
    x1 = LpVariable("x1", lowBound=0, cat=LpInteger)# LpInteger:整数型
    x2 = LpVariable("x2", cat=LpBinary)# LpBinary:0—1型
    
    
    x3 = LpVariable("x3", lowBound=0)
    
    my_MipProblem += 2 * x1 + 3 * x2 + x3, "obj"
    my_MipProblem += 2 * x1 -     x2 + 3 * x3 >= 6, "c1"
    my_MipProblem += 4 * x1 +     x2 + 5 * x3 == 24, "c2"
    
    my_MipProblem.solve()
    # 打印出已经求解问题的状态
    
    print("Status:", LpStatus[my_MipProblem.status])
    
    # 打印出最优解
    
    for v in my_MipProblem.variables():
        print(v.name, "=", v.varValue)
    
        solution.append(v.varValue)
    
    # 打印最优目标函数值
    print("objective=", value(my_MipProblem.objective))
    

    numpy和scipy

    用scipy的linprog求解以下线性规划问题

    标准问题(最小值,约束为<=)

    例题:在这里插入图片描述

    import numpy as np
    from scipy.optimize import linprog
    
    c = np.array([-6, -1, -2])
    A_ub = np.array([[1, 3, 1], [2, 0, 1], [1, 1, 0]])
    b_ub = np.array([12, 6, 2])
    x1_bounds = [0, None]
    x2_bounds = [0, None]
    x3_bounds = [0, None]
    
    my_linprog_result = linprog(c, A_ub, b_ub, A_eq=None, b_eq=None, bounds=(x1_bounds, x2_bounds, x3_bounds), callback=None)
    my_solution = my_linprog_result.x
    my_optimum_value = my_linprog_result.fun
    print(my_solution)
    print(my_optimum_value)
    
    
    

    非标准形式

    用linprog求解时,只能求解最小值且为小于约束的问题,如果要求解其他问题,则需先变换成规定的标准形式。

    例题:在这里插入图片描述

    import numpy as np
    from scipy.optimize import linprog
    
    c = np.array([-1,-1,2]) # 最大值变为最小值,取相反数
    A_ub = np.array([[1,2,3],[-2,-1,2]]) # >=约束转换为<=约束,取相反数
    b_ub = np.array([12,-8])
    x1_bounds = [0,None]
    x2_bounds = [0,None]
    x3_bounds = [0,None]
    
    my_linprog_result = linprog(c,A_ub,b_ub,A_eq=None,b_eq=None,bounds=(x1_bounds,x2_bounds,x3_bounds),method='simplex',callback=None)
    my_solution = my_linprog_result.x
    my_optimum_value = -my_linprog_result.fun # 将最优值转换为最大值
    print(my_solution)
    print(my_optimum_value)
    

    运输问题

    例题:在这里插入图片描述

    from pulp import *
    import numpy as np
    from itertools import product
    
    production = 3 #3个产地
    sale = 4       #3个销地+1个虚拟销地
    
    demand = [20, 40, 60, 10]  # 销量
    capacity = [45, 30, 55]  # 产量
    cost = np.array([[7, 2, 2, 0], [1, 6, 5, 0], [5, 4, 7, 0]])
    # 建立模型
    prob = LpProblem("Transportation", LpMinimize)
    x = LpVariable.dicts("x", product(range(production), range(sale)), lowBound=0, upBound=None, cat=LpInteger)  # product 作用未知
    prob += pulp.lpSum(cost[l, c] * x[l, c] for l in range(production) for c in range(sale))
    
    # 约束条件
    for l in range(production):
        prob += lpSum(x[l, c] for c in range(sale)) == capacity[l]
    for c in range(sale):
        prob += lpSum(x[l, c] for l in range(production)) == demand[c]
    # 求解
    prob.solve()
    
    min_cost = value(prob.objective)
    solution = []
    
    for v in prob.variables():
        solution.append(v.varValue)
    solution = np.array(solution).reshape(3, 4)
    
    print(solution)
    print(min_cost)
    

    指派问题(scipy的linear_sum_assignment

    学习阅读scipy.optimize.linear_sum_assignment

    注意

    1. linear_sum_assignment只能求解目标函数为最小值的线性指派问题
    2. 可以直接求解任务数与人数不对等的指派问题
    3. 输入参数必须为一个2D的numpy.array实例
    4. 返回的结果为最优指派对应在此2D array上的index

    例题1:
    在这里插入图片描述

    import numpy as np
    from scipy.optimize import linear_sum_assignment
    
    s1 = [11, 10, 11, 3, 11]
    s2 = [8, 11, 10, 12, 14]
    s3 = [15, 5, 16, 2, 3]
    s4 = [15, 3, 5, 17, 14]
    
    time_array_standardized = np.vstack((s1, s2, s3, s4,s4))
    
    row_ind, col_ind = linear_sum_assignment(time_array_standardized)
    print(row_ind)#开销矩阵对应的行索引
    print(col_ind)#对应行索引的最优指派的列索引
    print(time_array_standardized[row_ind,col_ind])#提取每个行索引的最优指派列索引所在的元素,形成数组
    minimum_time = time_array_standardized[row_ind,col_ind].sum()#数组求和
    print(minimum_time)
    

    例题2:
    在这里插入图片描述

    import numpy as np
    from scipy.optimize import linear_sum_assignment
    
    s1 = [-320, -300, -440, -470, -450]
    s2 = [-370, -490, -420, -550, -310]
    s3 = [-360, -510, -440, -490, -300]
    s4 = [-310, -420, -420, -450, -450]
    s5 = [-340, -330, -400, -450, -510]
    
    time_array_standardized = np.vstack((s1, s2, s3, s4, s5))
    
    row_ind, col_ind = linear_sum_assignment(time_array_standardized)
    print(row_ind)#开销矩阵对应的行索引
    print(col_ind)#对应行索引的最优指派的列索引
    print(time_array_standardized[row_ind,col_ind])#提取每个行索引的最优指派列索引所在的元素,形成数组
    maximum_sales = -time_array_standardized[row_ind,col_ind].sum()#数组求和
    print(maximum_sales)
    

    networkx 解图论问题

    Python的Networkx包

    NetworkX is a Python language software package for the creation, manipulation, and study of the structure, dynamics, and function of complex networks.

    With NetworkX you can load and store networks in standard and nonstandard data formats, generate many types of random and classic networks, analyze network structure, build network models, design new network algorithms, draw networks, and much more.

    官方文档
    入门教程
    算法
    networkx整理内容

    预习内容:

    1. nx.Graph(无向图)和nx.DiGraph(有向图)的生成
    2. 用Networkx的minimum_spanning_treeminimum_spanning_edges方法求解最小支撑树问题
    3. Networkx的最短路求解方法求解最短路问题

    最小支撑树问题

    用Networkx的minimum_spanning_treeminimum_spanning_edges方法求解以下最小支撑树问题,要求:

    1. 节点的编号从0开始
    2. 边的权重用weight表示
    3. 返回G,其为下图所对应的Graph.
    4. 返回T,为G对应的最小支撑树
    5. 返回T_edges,为T中的所有边,T_edges可以是一个list,或tuple,或generator.
    6. 返回T_weight,T的权重之和.
      提示:使用Graph.size会有帮助.

    例题:在这里插入图片描述

    import networkx as nx
    G = nx.Graph()
    # 设置节点
    v = {}
    for i in range(10):
        v[i] = f'v{i}'
    G.add_nodes_from(v)
    # 设置无向边
    weight = [(0,1,17), (0,2,21), (0,6,14), (0,8,24), (0,9,10),
              (1,4,10), (1,5,17), (1,6,11), (1,8,22),
              (2,3,18), (2,8,22),
              (3,5,11), (3,6,10), (3,7,14), (3,9,23),
              (4,7,7), (4,8,18),
              (5,9,18),
              (6,7,20),
              (7,8,11)]
    # 生成无向图
    for (start,end,flow) in weight:
        G.add_edge(start,end,weight=flow)
    # 求最小树和最小树的边
    T = nx.minimum_spanning_tree(G)
    T_edges = list(nx.minimum_spanning_edges(G))
    # 计算T_weight(从tuple中取出dict,再从dict中取出值)
    T_weight = 0 # 初始化
    for (start, end, weight) in T_edges:
        T_weight = T_weight + weight.get('weight') # dict没有value方法(T_weight = T_weight + weight.value())
        
    print(sorted(T.edges(data=True)))
    print(T_weight)
    

    最短路问题

    用Networkx的最短路求解方法求解以下最短路问题,要求:

    1. 节点的编号从0开始
    2. 返回G,其为下图所对应的DiGraph.
    3. 返回all_shortest_paths,为G中source和target之间的所有最短路径,例如如果v1到v8的最短路径有两条:v1→v2→v8和v1→v3→v4→v8,则返回一个list或generator,其格式为[[0,1,7], [0,2,3,7]].
    4. 返回shortest_path_length,为最短路的长度.

    例题1:求解下图中从v1至v8的最短路径及最短距离.
    在这里插入图片描述

    import networkx as nx
    # 生成有向图
    G = nx.DiGraph()
    edge = [(0, 1, 1), (0, 2, 4), (0, 3, 3),
            (1, 2, 3), (1, 4, 8),
            (2, 4, 5), (2, 5, 3), (2, 6, 6),
            (3, 2, 4), (3, 6, 5),
            (4, 5, 4), (4, 7, 3),
            (5, 7, 4),
            (6, 5, 2), (6, 7, 5)] #可以是list,也可以是tuple
    for (start, end, flow) in edge:
        G.add_edge(start, end, weight=flow)# 设置属性
    # 求解最短路径
    all_shortest_paths = list(nx.all_shortest_paths(G, source=0, target=7, weight='weight')) #默认算法是dijkstra,调出属性
    shortest_path_length = nx.shortest_path_length(G,source=0,target=7,weight='weight')
    print(all_shortest_paths)
    print(shortest_path_length)
    

    例题2:在这里插入图片描述

    import networkx as nx
    # 生成有向图
    G = nx.DiGraph()
    edge = [(0, 1, 3), (0, 2, 2), (0, 4, 3),
            (1, 3, -2), (1, 4, 7),
            (2, 4, 4), (2, 5, 1),
            (3, 4, 5), (3, 6, 4),
            (4, 5, 1), (4, 6, 4),
            (5, 6, 2), (5, 7, 5),
            (6, 7, 6), (6, 8, 4),
            (7, 8, 6)] #可以是list,也可以是tuple
    for (start, end, flow) in edge:
        G.add_edge(start, end, weight=flow)# 设置属性
    # 求解最短路径
    all_shortest_paths = list(nx.all_shortest_paths(G, source=0, target=8, weight='weight')) #默认算法是dijkstra,调出属性
    shortest_path_length = nx.shortest_path_length(G,source=0,target=8, weight='weight')
    print(all_shortest_paths)
    print(shortest_path_length)
    

    最大流问题

    用Networkx的Maximum Flow算法方法求解以下网络最大流问题。

    例题要求:

    1. 节点的编号从0开始

    2. 返回G,其为下图所对应的DiGraph,其中弧上的权重用capacity表示.

    3. 返回max_flow_value,为最大流的流量(数值).

    4. 返回cut_set,为最小割集,可以是一个list或set.

    5. 求解下图中从v1至v11的最大流及最小割,并思考最小割集是什么。图中弧上的数字表示其容量.

      在这里插入图片描述

    import networkx as nx
    G = nx.DiGraph()
    edge = [(0, 1, 155), (0, 2, 180), (0, 3, 30),
            (1, 4, 155), (1, 5, 185),
            (2, 4, 105), (2, 5, 65), (2, 6, 60),
            (3, 5, 120), (3, 6, 160),
            (4, 7, 110), (4, 8, 60),
            (5, 7, 180), (5, 8, 155), (5, 9, 60),
            (6, 8, 135), (6, 9, 135),
            (7, 10, 85),
            (8, 10, 85),
            (9, 10, 155)]
    for (start, end, flow) in edge:
        G.add_edge(start, end, capacity=flow)# 设置属性
    # 计算最大流的值
    max_flow_value = nx.maximum_flow_value(G, 0, 10, capacity="capacity")
    # 计算最小割
    cut_value, partition = nx.minimum_cut(G, 0, 10,capacity="capacity")# partition (u,v)
    reachable, non_reachable = partition
    # 设置弧
    cut_set = set()
    for u, nbrs in ((n, G[n]) for n in reachable):
        cut_set.update((u, v) for v in nbrs if v in non_reachable)
    
    
    展开全文
  • WINQSB 使用说明

    2010-06-15 21:34:40
    17.Linear and Integer Programming (缩写为 LP-ILP ,线性规划与整数线性规划) 用于求解线性规划、整数规划、对偶问题等,可进行灵敏度分析、参数分析。 18.Goal Programming (缩写为 GP ,目标规划) 用于...
  • 实用性模型算法研究

    2019-10-08 09:52:16
    线性规划整数规划、多元规划、二次规划等规划类4.图论算法(最短路、网络流、二分图等算法)5.动态规划、回溯搜索、分治算法、分支定界等计算机算法6.最优化理论的三大非经典算法:模拟退火法、神经网络、遗传...

    数据建模十类算法

    1、蒙特卡罗算法
    2.数据拟合、参数估计、插值等数据处理算法
    3.线性规划、整数规划、多元规划、二次规划等规划类
    4.图论算法(最短路、网络流、二分图等算法)
    5.动态规划、回溯搜索、分治算法、分支定界等计算机算法
    6.最优化理论的三大非经典算法:模拟退火法、神经网络、遗传算法
    7.网格算法和穷举法
    8.连续离散化方法
    9.数值分析算法
    10.图象处理算法

    以上十类算法开篇。

    转载于:https://www.cnblogs.com/bubblefu/p/3872064.html

    展开全文
  • 3:线性规划整数规划、多元规划、二次规划(用lingo、lingdo、matlab即可实现);4:图论算法(包括最短路、网络流、二分图);5:动态规划、回溯搜索、分治算法、分支界定;6:最优化理论的三大经典算法(模拟退火...
  • 运筹学软件 WinQsb2.0

    2012-12-20 00:35:36
    WinQSB是Quantitative Systems for Business的...内容包括:线性规划划及整数规划、目标规划、分配问题、运输问题、最短路问题、最小部分树问题、网络最大流问题、货郎担问题、计划评审技术、二人零和对策、决策分析。
  • WinqSB绿色2.0版

    热门讨论 2010-06-02 14:33:11
    WinQSB是Quantitative Systems for Business的...内容包括:线性规划划及整数规划、目标规划、分配问题、运输问题、最短路问题、最小部分树问题、网络最大流问题、货郎担问题、计划评审技术、二人零和对策、决策分析。
  • 运筹学软件WINQSB教程

    2009-06-16 13:59:29
    WinQSB是Quantitative Systems for Business的...内容包括:线性规划划及整数规划、目标规划、分配问题、运输问题、最短路问题、最小部分树问题、网络最大流问题、货郎担问题、计划评审技术、二人零和对策、决策分析。
  • 为解决考虑端口连通性限制的路由与波长分配问题,建立了其整数线性规划(ILP)模型,并提出了3种考虑端口连通性(IPCA)的动态路由机制,包括基于K最短路(KSP)的IPCA(IPCA-KSP)机制、IPCA-Dijkstra机制与全路径搜索机制...
  • 在 Q 的基础上,量化不同目标为有向赋权 图的不同权矩阵(见 5.2.0),以所求顶点u 到顶点v的路径是否包含 xij 弧为决策变量, 上述 5 项用户需求为目标,始、终点连通为约束建立 0-1 整数线性规划模型(见 5.2.3 模型...
  • 4、图与网络分析这是一门应用相当广的学科,要求掌握基本概念、树、最短路、最大源以及最大费用最大源问题的解法。会绘制生产计划管理的计划网络图。利用网络图进行成本、资源等优化分析。最好结合自己的工作实践...
  • % fmincon - 非线性规划(在MATLAB5.3使用) % % 离散优化 % *enum - 枚举法 % *monte - 蒙特卡洛法 % *lpint - 线性整数规划 % *L01p_e - 0-1整数规划枚举法 % *L01p_ie - 0-1整数规划隐枚举法 % *bnb18 - 非线性整数...
  • MATLAB数学建模工具箱

    热门讨论 2013-05-20 15:06:10
    % fmincon - 非线性规划(在MATLAB5.3使用) % % 离散优化 % *enum - 枚举法 % *monte - 蒙特卡洛法 % *lpint - 线性整数规划 % *L01p_e - 0-1整数规划枚举法 % *L01p_ie - 0-1整数规划隐枚举法 % *bnb18 - 非线性整数...
  • Matlab数学建模工具箱

    热门讨论 2010-03-15 12:14:21
    % fmincon - 非线性规划(在MATLAB5.3使用) % % 离散优化 % *enum - 枚举法 % *monte - 蒙特卡洛法 % *lpint - 线性整数规划 % *L01p_e - 0-1整数规划枚举法 % *L01p_ie - 0-1整数规划隐枚举法 % *bnb18 - 非线性整数...
  • 《运筹学上机实验指导》分为两个部分,第一部分12学时,是与运筹学理论课上机同步配套的4个实验(线性规划、灵敏度分析、运输问题与指派问题、最短路问题和背包问题)的Excel、LONGO和LINDO求解方法和3个大综合作业...
  •  ③回归分析、图论及最短路优化资料 ①赛题及赛题解析  ②优秀论文11篇  ③多元线性回归、决策树资料 ①赛题及赛题解析  ②优秀论文8篇+ `( \9 y' `; D5 E) B  ③微分方程、非线性拟合资料 ①赛题及赛题解析; ~...

空空如也

空空如也

1 2
收藏数 40
精华内容 16
关键字:

最短路整数线性规划