Java 中的線性規劃：求解指派問題

1. 概述

線性規劃是一種最佳化演算法，用於在滿足一組線性約束條件的前提下，最小化或最大化目標函數。

在本教程中，我們將探討如何使用 Java 解決賦值問題。我們將主要專注於純 Java 的數值運算庫，包括 ojAlgo 和 Apache Commons Math，並示範如何使用它們來解決這個問題。

2. 賦值問題

指派問題是一個經典的最佳化問題，它涉及將一組人員專門分配給一組任務。現在，讓我們透過以下場景來詳細闡述這個問題。

我們有三名志工和三個工作地點。目標是為每位志工分配一個工作地點，並盡可能減少志工的總出行時間。此問題受以下兩個約束條件限制：

1. 每位志工只能被分配到一個地點，
2. 每個地點只需要一名志工。

每位志工到每個地點的行程時間都是已知且固定的。我們可以將這些出行時間表示為一個成本矩陣。讓我們在後面的章節中舉例如何求解：

	地點 1	地點 2	地點 3
志工 1	27	6	21
志工 2	18	12	9
志工 3	15	24	3

3. 數學定義

在深入探討實作方法之前，我們先從數學角度定義這個賦值問題。這將有助於我們明確後續實現中將採用的目標函數和約束條件。

3.1 目標函數

基於此公式，我們將目標函數定義如下：

目標是最大限度地減少志願者與地點之間的總旅行時間，其中i表示志願者， j表示地點。

t ij表示志工i和地點j之間的旅行時間，如第 2 節定義的旅行時間成本矩陣所規定。最後， x ij表示志工i是否被分配到地點j 。

3.2. 約束條件

鑑於我們在第 2 節中所描述的約束條件，我們將第一個約束條件定義為：

對於單一志願者i ，透過所有可能的位置j分配x ij求和。將求和限制為 1 可確保每位志工被分配到且僅分配到一個位置。

第二個限制條件與第一個類似：

這樣一來，每個地點就只能有一名志工。

最後，我們需要一個額外的約束條件。由於每個分配x ij都是一個離散事件，即我們是否將志願者分配到某個地點，因此我們將分配變數限制為二元變數：

其中，1 表示志願者i被分配到地點j ，0 表示未進行任何分配。此約束確保志工不會部分分配到同一地點。

4. 使用 ojAlgo 求解

在定義了分配問題的數學公式之後，讓我們進入實際部分，我們將使用 ojAlgo 以程式設計方式將函數和約束組合在一起。

ojAlgo是一個用於數值最佳化的開源 Java 函式庫，支援多種最佳化演算法，包括線性規劃。這使其成為解決這一經典問題的理想選擇。

要開始使用 ojAlgo，讓我們將以下 Maven依賴項新增到pom.xml中：

<dependency>

 <groupId>org.ojalgo</groupId>

 <artifactId>ojalgo</artifactId>

 <version>56.2.0</version>

 </dependency>

4.1 模型創建

我們首先填入前面介紹的成本矩陣，該矩陣是二維數組。每一行代表一名志願者，每一列代表一個地點。因此， t[i][j]的值對應於志願者i和地點j之間的旅行時間，該時間在上一節中表示為t ij ：

double[][] t = {

 {27, 6, 21},

 {18, 12, 9},

 {15, 24, 3}

 };

接下來，我們使用ExpressionsBasedModel建立一個最佳化模型，並使用二維Variable數組x來儲存分配變數。每個分配變數表示志願者i是否被分配到位置j ，這對應於上一節中的x ij ：

int volunteers = t.length;

 int locations = t[0].length;

 ExpressionsBasedModel model = new ExpressionsBasedModel();

 Variable[][] x = new Variable[volunteers][locations];

4.2 目標函數

現在，我們使用binary(),這將強制賦值x ij的值只能是 0 或 1。這樣，ojAlgo 就能將模型當作整數線性規劃問題來運作。

我們將每個分配變數x ij與對應的行程成本t ij 關聯起來，權重為weight(t[i][j]) 。分配變數和權重共同定義了目標函數：

for (int i = 0; i < volunteers; i++) {

 for (int j = 0; j < locations; j++) {

 x[i][j] = model

 .newVariable("Assignment_" + i + "_" + j)

 .binary()

 .weight(t[i][j]);

 }

 }

值得注意的是，我們在這個階段只定義了目標函數，但還沒有具體說明是要最小化還是要最大化它。

4.3. 約束條件

在定義目標函數時，我們已經定義了一個限制條件，即賦值必須是二元的。現在讓我們定義其餘兩個約束條件：

for (int i = 0; i < volunteers; i++) {

 Expression volunteerConstraint = model.addExpression("Volunteer_" + i).level(1);

 for (int j = 0; j < locations; j++) {

 volunteerConstraint.set(x[i][j], 1);

 }

 }

這段程式碼片段定義了志工約束。對於每個志願者，它透過.level(1)建立一個值為 1 的線性表達式。

內循環將志工的所有分配變數相加，這意味著此約束將每個志工分配到且僅分配到一個地點。

同樣，每個地點只能有一名志工。我們將以類似的方式定義地點限制：

for (int j = 0; j < locations; j++) {

 Expression locationConstraint = model.addExpression("Location_" + j).level(1);

 for (int i = 0; i < volunteers; i++) {

 locationConstraint.set(x[i][j], 1);

 }

 }

這兩個限制條件確保了志工與地點之間的一一對應關係。

4.4 模型求解

在確定了目標函數和約束條件後，我們最終可以透過呼叫.minimize()來最佳化模型，該函數指示 ojAlgo 找到使總旅行時間最短的分配方案：

var result = model.minimise();

如果我們檢查Variable數組x中儲存的值，我們可以看到最終賦值等於：

new double[][] {

 {0, 1, 0},

 {1, 0, 0},

 {0, 0, 1}

 }

下表顯示了成本矩陣，其中選定的任務已高亮顯示：

	地點 1	地點 2	地點 3
志工 1	27	6	21
志工 2	18	12	9
志工 3	15	24	3

將每項分配的行程時間相加，總出行時間為 27，這是此分配範例的最佳解。從已求解的模型中，我們還可以透過以下方式獲得最短出行時間：

double totalCost = result.getValue();

5. 使用 Apache Commons Math 求解

除了 ojAlgo，我們還可以使用 Apache Commons Math 來解決這個作業問題。它是一個開源的數學庫，包含了數學和統計組件。

要開始使用，我們需要在 pom.xml 檔案中新增以下 Maven 依賴項：

<dependency>

 <groupId>org.apache.commons</groupId>

 <artifactId>commons-math3</artifactId>

 <version>3.6.1</version>

 </dependency>

5.1. 輔助函數

我們首先建立一個輔助函數。 Commons Math 會將目標定義為一維數組。我們需要一個函數將二維的分配變數（志願者，地點）映射到一維索引：

private int index(int i, int j, int locationsAvailable) {

 return i * locations + j;

 }

5.2 目標函數

與 ojAlgo 中的做法類似，我們使用行程時間成本矩陣t建立目標函數。我們將使用輔助函數將成本矩陣轉換為 Commons Math 所需的一維數組：

int volunteers = t.length;

 int locations = t[0].length;

 int vars = volunteers * locations;



 double[] x = new double[vars];

 for (int i = 0; i < volunteers; i++) {

 for (int j = 0; j < locations; j++) {

 x[index(i, j, locations)] = t[i][j];

 }

 }



 LinearObjectiveFunction objective = new LinearObjectiveFunction(x, 0);

LinearObjectiveFunction的第二個參數是常數項。但是，我們不需要它來解決賦值問題，因為我們的係數只是t ij · x ij沒有任何固定的偏移量。

5.3. 約束條件

接下來，我們定義賦值問題的線性限制。 Commons Math 將每個約束表示為一個LinearConstraint實例。我們將把約束放入一個Collection中：

Collection<LinearConstraint> constraints = new ArrayList<>();

第一條限制條件是每位志工只能在一個地點活動：

for (int i = 0; i < volunteers; i++) {

 double[] x_i = new double[vars];

 for (int j = 0; j < locations; j++) {

 x_i[index(i, j, locations)] = 1.0;

 }

 constraints.add(new LinearConstraint(x_i, Relationship.EQ, 1.0));

 }

第二個限制條件是每個地點只能有一名志工：

for (int j = 0; j < locations; j++) {

 double[] x_j = new double[vars];

 for (int i = 0; i < volunteers; i++) {

 x_j[index(i, j, locations)] = 1.0;

 }

 constraints.add(new LinearConstraint(x_j, Relationship.EQ, 1.0));

 }

儘管這次我們使用了不同的 Java 實現，但約束定義基本上相同，即將賦值變數的總和限制為 1。

5.4 模型求解

我們已經準備好了目標函數和限制條件，可以使用SimplexSolver解算器來求解線性規劃問題。由於我們要最小化總行程時間，因此我們將最佳化目標指定為GoalType.MINIMIZE ：

SimplexSolver solver = new SimplexSolver();

 PointValuePair solution = solver.optimize(

 objective,

 new LinearConstraintSet(constraints),

 GoalType.MINIMIZE,

 new NonNegativeConstraint(true)

 );

最後一個參數限制賦值變數x ij為非負數。

我們可以透過呼叫以下函數來獲取最佳化後的成本和最終分配方案：

double totalCost = solution.getValue();

 double[] point = solution.getPoint();

如果我們把解point組轉換回二維表示，我們會發現該賦值與totalCost為 27 的 ojAlgo 完全相同。

6. 結論

本文提出了一個可以用線性規劃解決的經典指派問題。

我們也示範如何使用 ojAlgo 和 Apache Commons Math 函式庫以程式設計方式解決這個問題。這些庫被證明是解決數值最佳化問題的強大工具。

像往常一樣，我們的完整程式碼範例都可以在 GitHub 上找到。