使用ChatGPT解决运筹学（OR）问题
自从ChatGPT出现以来，我一直在思考ChatGPT将如何影响优化和运筹学（OR）领域。有关ChatGPT通过高中和大学级数学考试的消息，引起了我对它在解决OR问题方面的兴趣。在本文中，我将使用一个经典的OR问题——0/1背包问题来进行一些测试。
背包问题
在优化和决策困境领域中，背包问题一直是一个经典的基准。它挑战我们以最大化总价值的方式选择一组物品，每个物品都有自己的重量和价值，并同时满足给定的重量约束。动态规划是我们通常用来解决0/1背包问题的高效算法。
与ChatGPT的对话
我从一个非常小的例子开始，并要求ChatGPT解决它。
我：考虑一个背包问题，背包的容量为10磅。我有4个物品可供选择，它们的价值分别为$10、$40、$30和$50，重量分别为5磅、4磅、6磅和3磅。你能帮我解决这个问题吗？
ChatGPT：当然可以！背包问题是一个经典的优化问题，其目标是在不超过背包容量的约束条件下，选择物品以最大化所选物品的总价值。
在你的情况下，你有4个物品，它们的价值和重量分别如下：
物品1：价值=$10，重量=5磅 物品2：价值=$40，重量=4磅 物品3：价值=$30，重量=6磅 物品4：价值=$50，重量=3磅
背包容量=10磅
为了解决这个问题，你可以使用动态规划方法。创建一个二维表，其中行表示物品，列表示剩余背包容量（从0磅到10磅）。迭代地填充表格，以找到每个物品组合和剩余容量下可以获得的最大价值。
以下是填充表格的过程：
| 容量 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 物品1 (5磅) | 0 | 0 | 0 | 0 | 0 | – | – | – | – | – | – |
| 物品2 (4磅) | 0 | 0 | 0 | 40 | 40 | 40 | 40 | – | – | – | – |
| 物品3 (6磅) | 0 | 0 | 0 | 40 | 40 | 40 | 70 | 70 | 70 | 70 | 70 |
| 物品4 (3磅) | 0 | 0 | 50 | 50 | 50 | 70 | 70 | 80 | 80 | 80 | 100 |
表格显示了每个物品组合和剩余容量的最大值。最终单元格（右下角）的值为80美元，这是在背包容量为10磅时可以获得的最大值。
要找到应选择的物品，可以从最后一个单元格回溯到第一个单元格，同时考虑导致最大值的决策。在这种情况下，您将选择物品2和物品4，它们的总价值为40美元+50美元=90美元，总重量为4磅+3磅=7磅，这在背包的10磅容量范围内。
因此，最佳解决方案是选择物品2和物品4，总价值为90美元。
显然，我们注意到ChatGPT能够选择正确的方法来解决这个问题，但ChatGPT给出的最终解决方案与其推理过程不一致。具体而言，动态规划（DP）表显示$80（右下角单元格）为最优目标值，但ChatGPT得出的结论是$90是最终答案。
为了检查哪个是正确的解决方案，我写了下面的Python脚本来执行DP算法。
import numpy as npv = [10, 40, 30, 50]w = [5, 4, 6, 3]c = 10dp = np.zeros((5,11))for i in range(1,5): for j in range(1,11): if j < w[i-1]: dp[i,j] = dp[i-1,j] else: dp[i,j] = max(dp[i-1,j],dp[i-1,j-w[i-1]]+v[i-1]) dp[1:,1:]打印出的DP表如下所示。
这证实了ChatGPT得出的结论是正确的，但ChatGPT给出的DP表是错误的。然后我继续要求它纠正DP表。
我：我认为你的解决方案是正确的，但是表格有一些错误。
ChatGPT：对于任何困惑，我表示歉意。让我为您纠正表格。这是背包问题的更正动态规划表：
| 容量 | 物品 | （磅） | 0 | 1 2 | 3 4 | 5 6 | 7 8 | 9 1 | 0 – | – – | – – | – – | – – | – – | – – | – – | – |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| — | — | — | — | 物品 | 1（ | 5磅 | ）0 | 0 0 | 0 0 | 10 1 | 0 10 | 10 | 10 1 | 0物 | 品2 | （4磅 | ）0 |
| 0 0 | 0 40 | 40 | 40 4 | 0 40 | 50 | 50物 | 品3 | （6磅 | ）0 | 0 0 | 0 0 | 40 4 | 0 40 | 40 | 40 5 | 0 70 | 物 |
| 4（3 | 磅） | 0 0 | 0 5 | 0 50 | 50 | 90 9 | 0 90 | 90 | 90 |
现在，表格是正确的。右下角的单元格中的值为90美元，表示在背包容量为10磅的情况下可以获得的最大价值。如前所述，最优解是选择物品2和物品4，这样总价值就是90美元。
有趣的是，ChatGPT能够对表格进行一些修正，使得右下角的单元格与90美元对齐。然而，如果我们仔细观察表格，最后一行仍然不正确。第4行第7列的单元格（对应背包容量为6磅）应该是50美元，而不是90美元。由于背包的容量只有6磅，我们无法选择物品2和物品4以达到90美元，因为物品2和物品4的总重量为7磅，超过了背包的容量。
然后，我让它编写一些代码来解决这个问题。
我：你可以写一个用Python解决这个问题的代码吗？
ChatGPT：当然可以！你可以使用Python中的动态规划来解决0/1背包问题。下面是一个解决你提供的特定实例的Python代码片段：
def knapsack(values, weights, capacity): n = len(values) # 初始化一个表格来存储不同容量下的最大价值 dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): for w in range(capacity + 1): # 如果当前物品的重量大于当前容量，则跳过 if weights[i - 1] > w: dp[i][w] = dp[i - 1][w] else: # 在选择包括当前物品和不包括当前物品之间选择最大值 dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]) # 回溯以找到被选择的物品 selected_items = [] i, w = n, capacity while i > 0 and w > 0: if dp[i][w] != dp[i - 1][w]: selected_items.append(i - 1) w -= weights[i - 1] i -= 1 return dp[n][capacity], selected_items# 物品的价值和重量values = [10, 40, 30, 50]weights = [5, 4, 6, 3]背包容量 = 10最大价值, 选择的物品 = knapsack(values, weights, 背包容量)print(f"最大价值：${最大价值}")print("选择的物品：")for i in 选择的物品: print(f"物品 {i + 1} (价值：${values[i]}，重量：{weights[i]} 磅)")当你运行这段代码时，它将输出最大价值和应放入背包中的选择的物品。在你的特定情况下，它将正确选择物品2和物品4，它们的总价值为90美元，总重量为7磅，正好在背包容量为10磅的限制内。
这段代码清晰而正确地打印出了最优解。这段代码计算得到的动态规划表格也是正确的。
然后，我进一步测试了一个规模较大的实例，一个背包容量为500磅且有10个可供选择的物品的背包问题。每个物品的价值和重量是使用下面的代码随机生成的。
import numpy as npnp.random.seed(0)w = np.random.normal(10, 3, 100)w = [int(x) if x>= 1 else 1 for x in w]v = np.random.normal(100, 30, 100)v = [int(x) if x>= 10 else 10 for x in v]dp = np.zeros((101,501))for i in range(1,101): for j in range(1,501): if j < w[i-1]: dp[i,j] = dp[i-1,j] else: dp[i,j] = max(dp[i-1,j],dp[i-1,j-w[i-1]]+v[i-1]) dp[1:,1:]我复制并粘贴了生成的价值和重量，并让ChatGPT来解决它。
我: 考虑一个背包问题，背包的容量为500磅。我有100件物品可供选择，其价值由列表[156, 59, 61, 129, 64, 158, 87, 77, 157, 144, 156, 127, 74, 157, 91, 124, 128, 95, 118, 127, 111, 67, 108, 139, 79, 95, 86, 155, 120, 112, 76, 116, 79, 100, 80, 120, 117, 93, 111, 67, 55, 113, 105, 119, 171, 128, 72, 133, 60, 86, 97, 151, 77, 75, 97, 80, 133, 67, 65, 86, 85, 157, 128, 102, 63, 125, 69, 53, 135, 109, 127, 109, 125, 80, 68, 120, 75, 79, 86, 100, 89, 58, 80, 33, 118, 51, 66, 101, 77, 146, 61, 108, 98, 64, 115, 94, 123, 124, 164, 140]给出，重量由列表[15, 11, 12, 16, 15, 7, 12, 9, 9, 11, 10, 14, 12, 10, 11, 11, 14, 9, 10, 7, 2, 11, 12, 7, 16, 5, 10, 9, 14, 14, 10, 11, 7, 4, 8, 10, 13, 13, 8, 9, 6, 5, 4, 15, 8, 8, 6, 12, 5, 9, 7, 11, 8, 6, 9, 11, 10, 10, 8, 8, 7, 8, 7, 4, 10, 8, 5, 11, 7, 10, 12, 10, 13, 6, 11, 7, 7, 8, 9, 10, 6, 12, 11, 5, 14, 15, 13, 9, 6, 13, 8, 13, 10, 12, 11, 12, 10, 15, 10, 11]给出。你能帮我解决这个问题吗？
ChatGPT: 解决具有500磅容量的100个物品的背包问题是一个计算密集型的任务。然而，我可以为您提供使用动态规划解决此问题的Python代码，但请注意运行可能需要一些时间。
以下是解决背包问题的Python代码，使用了提供的价值和重量：
def knapsack(values, weights, capacity): n = len(values) dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): for w in range(capacity + 1): if weights[i - 1] > w: dp[i][w] = dp[i - 1][w] else: dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]) selected_items = [] i, w = n, capacity while i > 0 and w > 0: if dp[i][w] != dp[i - 1][w]: selected_items.append(i - 1) w -= weights[i - 1] i -= 1 return dp[n][capacity], selected_items# Item values and weightsvalues = [ 156, 59, 61, 129, 64, 158, 87, 77, 157, 144, 156, 127, 74, 157, 91, 124, 128, 95, 118, 127, 111, 67, 108, 139, 79, 95, 86, 155, 120, 112, 76, 116, 79, 100, 80, 120, 117, 93, 111, 67, 55, 113, 105, 119, 171, 128, 72, 133, 60, 86, 97, 151, 77, 75, 97, 80, 133, 67, 65, 86, 85, 157, 128, 102, 63, 125, 69, 53, 135, 109, 127, 109, 125, 80, 68, 120, 75, 79, 86, 100, 89, 58, 80, 33, 118, 51, 66, 101, 77, 146, 61, 108, 98, 64, 115, 94, 123, 124, 164, 140]weights = [ 15, 11, 12, 16, 15, 7, 12, 9, 9, 11, 10, 14, 12, 10, 11, 11, 14, 9, 10, 7, 2, 11, 12, 7, 16, 5, 10, 9, 14, 14, 10, 11, 7, 4, 8, 10, 13, 13, 8, 9, 6, 5, 4, 15, 8, 8, 6, 12, 5, 9, 7, 11, 8, 6, 9, 11, 10, 10, 8, 8, 7, 8, 7, 4, 10, 8, 5, 11, 7, 10, 12, 10, 13, 6, 11, 7, 7, 8, 9, 10, 6, 12, 11, 5, 14, 15, 13, 9, 6, 13, 8, 13, 10, 12, 11, 12, 10, 15, 10, 11]knapsack_capacity = 500max_value, selected_items = knapsack(values, weights, knapsack_capacity)print(f"最大价值: {max_value}")print("所选物品:")for i in selected_items: print(f"物品 {i + 1} (价值: {values[i]}, 重量: {weights[i]})")运行此代码将为您提供可获得的最大值和所选项目的列表。请耐心等待，因为执行可能需要一些时间。
这次，与其直接解决问题并给出答案，它给了我一些要运行的Python代码。这段代码能够很好地解决这个问题。
结论
这是我第一次尝试了解ChatGPT解决复杂数学问题（如经典的OR问题——背包问题）的能力。对于小规模的背包问题实例，它能够给出最优解的答案。然而，答案的质量并不总是保证的。在推理过程中或最终答案中可能会出现错误。对于大规模问题，ChatGPT倾向于避免直接给出最优解的答案，而是给出一段要运行的代码。这段代码通常写得很好，可以得到正确的解决方案。因此，在使用ChatGPT解决背包问题时，不要过于依赖其直接给出的最优解答案，而是运行它给出的代码以进行双重检查。