Java调用cplex求解运输问题

举报
xia1111 发表于 2020/11/23 23:23:14 2020/11/23
【摘要】 Java调用cplex求解运输问题 Java调用cplex求解运输问题运输问题(Transportation Problem)描述运输问题的数学模型Java调用cplex求解运输问题transportation_node类transportation_relation类读取数据在cplex中建立运输问题模型主函数main求解结果 Java调用cp...

Java调用cplex求解运输问题

本文中的课件来自清华大学深圳国际研究生院,物流与交通学部张灿荣教授《生产管理》课程。

运输问题(Transportation Problem)描述

运输问题是一种特殊的最小费用网络流问题,其中每个节点都是一个纯供给节点或一个纯需求节点。
即所有的流都从供给它的某个源头节点出发,而后直接到达一个需要它的需求节点,中间不经过其它中间步骤或转运环节。一个运输问题中的商品流可能是任何东西,唯一必要的条件就是需要从供给源头节点流入需求节点。
总结一下,运输问题具有以下的特点:
在这里插入图片描述

运输问题的数学模型

首先定义运输问题的参数与决策变量:
在这里插入图片描述
目标函数为最小化运输成本:
min ⁡ ∑ i = 1 m ∑ j = 1 m c i j x i j (1) \min \sum_{i=1}^m\sum_{j=1}^m c_{ij} x_{ij} \tag{1} mini=1mj=1mcijxij(1)
约束一为从每个供给节点运出的商品总和等于该节点可用商品的数量:
∑ j n x i j = a i ,   ∀   1 ≤ i ≤ m (2) \sum_j^n x_{ij} = a_i ,\ \forall \ 1\le i \le m \tag{2} jnxij=ai,  1im(2)
约束二为每个需求节点流入的商品总和等于该节点需求商品的数量:
∑ i m x i j = b j ,   ∀   1 ≤ j ≤ n (3) \sum_i^m x_{ij} = b_j ,\ \forall \ 1\le j \le n \tag{3} imxij=bj,  1jn(3)
最后决策变量的取值范围:
x i j ≥ 0 ,   ∀   1 ≤ i ≤ m   a n d   1 ≤ j ≤ n (4) x_{ij} \ge 0 ,\ \forall \ 1\le i \le m \ and\ 1\le j \le n \tag{4} xij0,  1im and 1jn(4)
综上,1~4式即为运输问题的数学模型,且为一个线性规划模型。

Java调用cplex求解运输问题

本节介绍如果使用Java语言调用cplex求解器对运输问题进行求解。
问题相关参数如下:
在这里插入图片描述
Java是一种面向对象的编程语言,故编写过程中主要涉及以下几个类:

transportation_node类

package transportation_problem;

/**
 * This class is to define the transportation_node
 * @param Property of node
 * @return a node object
 */

public class transportation_node {
	String NodeName;
	int quantity;
	int isSource; int id;
	public transportation_node(String NodeName,int quantity,int isSource,int id) {
		this.NodeName = NodeName;
		this.quantity = quantity;
		this.isSource = isSource;
		this.id = id;
	} public boolean isSource() {
		if(this.isSource == 1) { return true;
		}
	return false;
	}
}

  
 
  • 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

transportation_relation类

package transportation_problem;

/**
 * This class is to define the transportation_relation
 * @param Property of node
 * @return a relation object
 */

public class transportation_relation {
	int [] distance ;
	public transportation_relation(int[] distance) {
		this.distance = distance;
	}
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

读取数据

package transportation_problem;

import java.io.*;
import java.util.*;

/**
 * This class is to read data from txt file
 * @param path: the file path to be read
 * @return return a data object
 * @throws IOException
 */
 
public class Readfile {
	List<transportation_node> transportationNodeList = new ArrayList<transportation_node>();
	transportation_relation transportationRelation; public Readfile(String path1,String path2) throws IOException { readtransportation_node(path1);
		transportation_relation(path2);
	} public void readtransportation_node(String path) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader(path));
		String line = new String(); //读取变量 br.readLine(); line = br.readLine(); String[] tokens = line.split("\\s+");
		while(tokens.length > 0) { transportation_node Temp = new transportation_node(tokens[0],Integer.parseInt(tokens[1]),Integer.parseInt(tokens[2]),Integer.parseInt(tokens[3])); transportationNodeList.add(Temp); line = br.readLine(); tokens = line.split("\\s+");
		}
		br.close(); } public void transportation_relation(String path) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader(path));
		String line[] = new String[100];
		int row = 0;
		line[row] = br.readLine();
		while(line[row] != null) { row++; line[row] = br.readLine();
		} String[] tokens = line[0].split("\\s+");
		int column = tokens.length;
		int [] dis = new int[(row-1)*column]; for (int i = 1; i < row; i++) { tokens = line[i].split("\\s+"); for (int j = 1; j <= column; j++) { dis[(column)*(i-1)+j-1] = Integer.parseInt(tokens[j]); }
		}
		transportationRelation = new transportation_relation(dis);
		br.close();
	}
}

  
 
  • 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

在cplex中建立运输问题模型

package transportation_problem;

import java.util.List;
import ilog.concert.IloException;
import ilog.concert.IloNumExpr;
import ilog.concert.IloNumVar;
import ilog.cplex.IloCplex;

/**
 * This class is to conduct a model in cplex and solve
 * @param problem parameter
 * @return return solve result
 * @throws IloException
 */

public class model_transportation {
	IloCplex cplex ;
	double objectiveValue;
	IloNumVar x[];
	int numOfPlants = 0;
	int numOfdestination = 0;
	/**
	 * This method is to bulidModel
	 * @param transportation_problem's data
	 * @return transportation_problem's model
	 * @throws IloException
	 */
	public void bulidModel(List<transportation_node> transportationNodeList,transportation_relation transportationRelation)throws IloException {
		this.cplex = new IloCplex();
		for(transportation_node tsNode : transportationNodeList){ if (tsNode.isSource()) { numOfPlants++; }else { numOfdestination++; }
		}
		CreatDecisionVariab();
		CreatObjFunc(transportationRelation);
		CreatConstraints(transportationNodeList);
		Solve(transportationNodeList);
	}
	/**
	 * This method is to create decision variables
	 * @throws IloException
	 */
	public void CreatDecisionVariab() throws IloException{
		x = new IloNumVar[numOfPlants*numOfdestination];
		for (int i = 0; i < numOfPlants; i++) { for (int j = 0; j < numOfdestination; j++) { x[i*numOfdestination+j] = cplex.numVar(0, Double.MAX_VALUE,"x"+(i+1)+(j+1)); }
		}
	}
	/**
	 * This method is to create objective function
	 * @throws IloException
	 */
	public void CreatObjFunc(transportation_relation transportationRelation) throws IloException{
		cplex.addMinimize(cplex.scalProd(x,transportationRelation.distance));
	}
	/**
	 * This method is to add constraints
	 * @throws IloException
	 */
	public void CreatConstraints(List<transportation_node> transportationNodeList) throws IloException {
		for(transportation_node tsNode : transportationNodeList){ IloNumExpr left = cplex.linearNumExpr(); if (tsNode.isSource()) { for(int i = 0;i<numOfdestination;i++) { left = cplex.sum(left,cplex.prod(1,x[tsNode.id*numOfdestination+i])); } cplex.addEq(left,tsNode.quantity); }else { for(int i = 0;i<numOfPlants;i++) { left = cplex.sum(left,cplex.prod(1,x[tsNode.id+i*numOfdestination])); } cplex.addEq(left,tsNode.quantity); }
		}
	}
	/**
	 * This method is to solve model
	 * @return values of objective function and decision variables
	 * @throws IloException
	 */
	public void Solve(List<transportation_node> transportationNodeList) throws IloException{
		cplex.setOut(null);
		if (cplex.solve()) { cplex.exportModel("111.lp"); objectiveValue = cplex.getObjValue(); System.out.println("最小运费为:" + objectiveValue); for (int i = 0; i < numOfPlants; i++) { for (int j = 0; j < numOfdestination; j++) { System.out.print(transportationNodeList.get(i).NodeName+" to "+transportationNodeList.get(numOfPlants+j).NodeName+" : "); System.out.println(cplex.getValue(x[i*numOfdestination+j])); } }
		}
	}
}

  
 
  • 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
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100

主函数main

package transportation_problem;

import java.io.IOException;
import java.util.List;
import ilog.concert.IloException;

public class Main {
	public static void main(String[] args) throws IOException, IloException {
		Readfile file = new Readfile("transportation_node.txt","transportation_relation.txt");
		List<transportation_node> transportationNodeList = file.transportationNodeList;
		transportation_relation transportationRelation = file.transportationRelation; model_transportation model = new model_transportation();
		model.bulidModel(transportationNodeList, transportationRelation);
	}
}

  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

求解结果

在这里插入图片描述
导出模型:
在这里插入图片描述
这样就完成了,感谢大家的阅读。
作者:夏旸,清华大学,工业工程系/深圳国际研究生院 (硕士在读)
邮箱:xia970201@gmail.com

完整Project文件请关注运小筹公众号,回复【运输问题】获取。
在这里插入图片描述

文章来源: blog.csdn.net,作者:旸1111,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/qq_35008055/article/details/109880741

【版权声明】本文为华为云社区用户原创内容,未经允许不得转载,如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200