Пропускная способность в задаче ветвей и границ ⇐ Python

[Anonymous]

Я пытаюсь найти решение транспортной проблемы с ограничением пропускной способности. Другими словами, у нас есть 3-тонный грузовик и нам нужно найти оптимальное решение. В это время код работает бесконечно, и я не могу понять, почему это происходит. Любая ваша помощь или решение будут оценены по достоинству.
import numpy as np
import heapq
import time

# Helper function to check if the solution is feasible
def is_feasible(supply, demand):
return np.all(supply >= 0) and np.all(demand >= 0)

# Function to calculate the cost of a solution
def calculate_cost(cost_matrix, allocation):
return np.sum(cost_matrix * allocation)

# Function to solve the transportation problem using Branch and Bound
def branch_and_bound_transportation(cost_matrix, supply, demand, capacity):
num_suppliers, num_consumers = cost_matrix.shape
best_cost = float('inf')
best_solution = None
nodes_explored = 0

# Priority queue for nodes in the form (cost, allocation, remaining_supply, remaining_demand)
queue = []
initial_allocation = np.zeros((num_suppliers, num_consumers))
heapq.heappush(queue, (0, initial_allocation.tolist(), supply.tolist(), demand.tolist()))

while queue:
current_cost, current_allocation, current_supply, current_demand = heapq.heappop(queue)
nodes_explored += 1

current_allocation = np.array(current_allocation)
current_supply = np.array(current_supply)
current_demand = np.array(current_demand)

# If this solution is feasible, calculate the cost
if is_feasible(current_supply, current_demand):
if np.all(current_supply == 0) and np.all(current_demand == 0):
# Feasible complete solution
total_cost = calculate_cost(cost_matrix, current_allocation)
if total_cost < best_cost:
best_cost = total_cost
best_solution = current_allocation
else:
# Branch by allocating to the cheapest route first
for i in range(num_suppliers):
for j in range(num_consumers):
if current_supply > 0 and current_demand[j] > 0:
new_allocation = np.copy(current_allocation)
# Calculate the maximum amount that can be allocated
allocation_amount = min(current_supply, current_demand[j], capacity)
new_allocation[i, j] += allocation_amount

new_supply = np.copy(current_supply)
new_demand = np.copy(current_demand)
new_supply -= allocation_amount
new_demand[j] -= allocation_amount

# Calculate the new cost for this allocation
new_cost = current_cost + allocation_amount * cost_matrix[i, j]
heapq.heappush(queue, (new_cost, new_allocation.tolist(), new_supply.tolist(), new_demand.tolist()))

return best_solution, best_cost, nodes_explored

# Updated data: supplies, demands, cost matrix, and transportation capacity
cost_matrix = np.array([
[10, 8, 5, 9, 16],
[4, 3, 4, 11, 12],
[5, 10, 29, 7, 6],
[9, 2, 4, 1, 3]
])
supply = np.array([17, 8, 10, 9])
demand = np.array([6, 15, 7, 8, 8])
capacity = 3 # Example truck capacity

# Start timer
start_time = time.strftime("%Y-%m-%d %H:%M:%S", time.localtime())
start = time.time()

# Solve the transportation problem using Branch and Bound
solution, cost, nodes_explored = branch_and_bound_transportation(cost_matrix, supply, demand, capacity)

# End timer
finish_time = time.strftime("%Y-%m-%d %H:%M:%S", time.localtime())
end = time.time()

# Output results
print("Optimal transportation allocation:")
print(solution)
print(f"Minimum cost: {cost}")
print(f"Number of nodes explored (iterations): {nodes_explored}")
print(f"Start time: {start_time}")
print(f"Finish time: {finish_time}")
print(f"Total execution time: {end - start:.4f} seconds") ```


Подробнее здесь: https://stackoverflow.com/questions/791 ... nd-problem