Мобильная версияВот мой код:
Код: Выделить всё
import numpy as np
from scipy.optimize import linprog
# Global variables
node_counter = 0
best_solution = (None, float('inf')) # (solution, total cost)
truck_capacity = 6 # in tons
def calculate_total_cost(solution, cost_per_ton):
"""
Calculate the total transportation cost considering truck capacity.
"""
total_cost = 0
for i, flow in enumerate(solution):
trucks_needed = int(np.ceil(flow / truck_capacity)) # Number of full truckloads
total_cost += trucks_needed * truck_capacity * cost_per_ton[i] # Cost for full truckloads
return total_cost
def branch_and_bound(bounds, depth=0):
global node_counter, best_solution
# Transportation cost matrix (flattened)
cost_per_ton = np.array([
10, 8, 5, 9, 16,
4, 3, 4, 11, 12,
5, 10, 29, 7, 6,
9, 2, 4, 1, 3
])
# Supply constraints
A_ub = np.zeros((4, 20))
A_ub[0, :5] = 1
A_ub[1, 5:10] = 1
A_ub[2, 10:15] = 1
A_ub[3, 15:] = 1
b_ub = [17, 8, 10, 9]
# Demand constraints
A_eq = np.zeros((5, 20))
for i in range(5):
A_eq[i, i::5] = 1
b_eq = [6, 15, 7, 8, 8]
# Solve LP relaxation
res = linprog(cost_per_ton, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=bounds, method='highs')
node_counter += 1
if res.success:
solution = res.x
total_cost = calculate_total_cost(solution, cost_per_ton)
# Debug output
print(f"Depth {depth}: Solution = {solution}, Total Cost = {total_cost}")
# Check for a new best integer solution
if all(val.is_integer() for val in solution):
if total_cost < best_solution[1]:
print(f"New best integer solution found at Depth {depth}: Total Cost = {total_cost}")
best_solution = (solution, total_cost)
return # Stop branching as the solution is already integer
# Branch on all fractional variables
for i, val in enumerate(solution):
if not val.is_integer():
# Floor and ceil values respecting truck capacity
floor_val = (int(val // truck_capacity)) * truck_capacity
ceil_val = floor_val + truck_capacity
# Branch lower: restrict variable to [0, floor_val]
new_bounds_lower = bounds[:]
new_bounds_lower[i] = (0, floor_val)
print(f"Branching Lower on variable {i} at Depth {depth}")
branch_and_bound(new_bounds_lower, depth + 1)
# Branch upper: restrict variable to [ceil_val, None]
new_bounds_upper = bounds[:]
new_bounds_upper[i] = (ceil_val, None)
print(f"Branching Upper on variable {i} at Depth {depth}")
branch_and_bound(new_bounds_upper, depth + 1)
break # Ensure this branch handles only one variable at a time
# Initialize bounds
initial_bounds = [(0, None)] * 20
# Execute the Branch-and-Bound algorithm
branch_and_bound(initial_bounds)
# Format the best solution for output
if best_solution[0] is not None:
solution_matrix = np.array(best_solution[0]).reshape(4, 5) # 4 sources x 5 destinations
print(f"Best integer result (matrix):\n{solution_matrix}")
else:
print("No feasible integer solution found.")
print(f"Objective value (considering truck capacity): {best_solution[1]}")
print(f"Number of explored nodes: {node_counter}")
Лучший целочисленный результат (матрица):
| | Д1 | Д2| Д3|Д4| D5|
| -- | -- |-- |-- |-- |-- |
| С1.| 0. |10. |7. | 0. |0.|
| С2.| 3. |5. |0. |0. |0.|
| С3.| 3. |0. |0. |0. |7.|
| С4.| 0. |0. |0. |8. |1.|
Цель объекта (с учетом грузоподъемности): 330$.
Количество исследованных узлов: 1
К сожалению, ответ неверный, потому что я решил проблему, используя другой метод, и для 6-тонных грузовиков распределение и общая цена составляют:
Общая цена: 276,00 долларов США
| | Д1 | Д2| Д3|Д4| D5|
| -- | -- |-- |-- |-- |-- |
| С1.| 0. |6. |5. | 6. |0.|
| С2.| 0. |6. |2. |0. |0.|
| С3.| 6. |0. |0. |0. |4.|
| С4.| 0. |3. |0. |2. |4.|
Любая ваша помощь или идеи, что изменить в коде, будут оценены по достоинству. Заранее спасибо.
Подробнее здесь: https://stackoverflow.com/questions/792 ... -algorithm
