認識求解器

這篇我要化身為 LibreOffice 小老師帶大家認識求解器，下面用實際的例子說明。

在會找錢的自助結帳機中，假設要找的錢是 12,345，那我們可以預期，客人應該不會想收到由一千多個十元和五元硬幣的零錢，而更想收到一些大面額鈔票加上少數幾個硬幣，那問題來了，究竟我們的自助結帳機要給出怎樣的貨幣組合才能滿足客人的期待呢？

對於上面的問題，我們可以在 LibreOffice Calc 如此表示：

其中：

• 找零金額為 12,345，這是絕對不可違背的先決條件，不管找錢的組合怎麼拼怎麼湊，金額一定得要是 12,345，對於這種無法拒絕的條件，稱為硬約束。
• 在貨幣面額表中，有各貨幣的數量，以及面額乘以數量的金額，最下面一列分別是合計的金額，應該要等於 12,345，以及合計的貨幣數量，目前暫時先填入 0。
• 所謂客人的期待，具體而言就是要讓貨幣數量盡可能的少，能給大鈔的就不給硬幣，我們的目標就是任意異動各種面額的數量，讓合計金額為 12,345，且貨幣數量盡可能的少。

了解以上三點後，先來個工人智慧求出的結果：

上圖中，客人拿到了貨幣組合為 12 張千元鈔票、3 張百元鈔、4 枚十元硬幣、1 枚五元硬幣，合計共 20 個貨幣。

接著動用求解器算算看，打開 LibreOffice Calc 選單列的「工具」，「求解器」，輸入一些儲存格參數：

其中：

• 目標儲存格為「C17」，即貨幣的合計數量，並希望結果為「最小」。
• 可變動的儲存格為「C5:C15」，即各個面額的數量。
• 硬約束為「D17 = D2」，即找零金額應為 12,345。

此外，求解器還有一些選項：

這邊我們又設定了變數為非負數、變數為整數兩項，其他選項可以自行把玩。

選項確定之後，就可以按下「求解」了，求解的結果如下：

求解器的結果，客人拿到了貨幣組合為 6 張兩千元鈔票、1 張兩百元鈔票、1 張百元鈔、2 枚二十元硬幣、1 枚五元硬幣，合計共 11 個貨幣。

相較於原始的工人智慧，是不是客人更開心了呢。

上面的例子是以 LibreOffice Calc 示範，但求解器也存在其他試算表應用中，在 Gnumeric 稱為「解答器」，在 Excel 稱為「規劃求解」，網路上也很多人寫規劃求解的範例。

除了這個簡單的例子，求解器還可以應用在排班表、排課表、排排程、路徑規劃這類事務上，而這類需求往往也需要動用更專業的求解器，例如 Timefold 等等，以後有機會再來介紹。

Share