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=1∑m?j=1∑m?cij?xij?(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} j∑n?xij?=ai?, ? 1≤i≤m(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} i∑m?xij?=bj?, ? 1≤j≤n(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} xij?≥0, ? 1≤i≤m and 1≤j≤n(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;
	}
}

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;
	}
}

讀取資料

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();
	}
}

在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]));
				}
			}
		}
	}
}

主函式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);
	}
}

求解結果

匯出模型：

這樣就完成了，感謝大家的閱讀，
作者：夏旸，清華大學，工業工程系/深圳國際研究生院 (碩士在讀)
郵箱：xia970201@gmail.com

完整Project檔案請關注運小籌公眾號，回復【運輸問題】獲取，