hw5

import xlrd import numpy as np from ortools.linear_solver import pywraplp

workbook = xlrd.open_workbook('./Time_distance.xlsx') #please change the path sheet = workbook.sheet_by_index(0) data = np.zeros([111,2],dtype=np.float) for i in range(111): data[i,:] = sheet.row_values(i+1) print(type(data))

x = [None for _ in range(400)] for i in [3,4,5]: print(x[i])

solver = pywraplp.Solver('q3', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING) objective=solver.Objective() objective.SetMinimization() # Constants n = len(data) y = [None for _ in range(n)] x = [None for _ in range(n)] for i in range(n): x[i] = data[i][0] y[i] = data[i][1] # Variables abs_errors = [None for _ in range(n)] pos_errors = [None for _ in range(n)] neg_errors = [None for _ in range(n)] pos_zs = [None for _ in range(n)] neg_zs = [None for _ in range(n)] # | y_i - a * x_i + b | a = solver.NumVar(-solver.infinity(), solver.infinity(), 'a') b = solver.NumVar(-solver.infinity(), solver.infinity(), 'b') one = solver.NumVar(1, 1, 'one') for i in range(n): abs_errors[i] = solver.NumVar(0, solver.infinity(), f'abs_error_{i}') pos_errors[i] = solver.NumVar(0, solver.infinity(), f'neg_error{i}') neg_errors[i] = solver.NumVar(0, solver.infinity(), f'pos_error_{i}') pos_zs[i] = solver.NumVar(0, solver.infinity(), f'pos_z_{i}') neg_zs[i] = solver.NumVar(0, solver.infinity(), f'neg_z_{i}-') # Objective Function objective.SetCoefficient(abs_errors[i], 1) # Constraints abs_err_consts = [None for _ in range(n)] pos_err_consts = [None for _ in range(n)] neg_err_consts = [None for _ in range(n)] # pos_x_consts = [None for _ in range(n)] # neg_x_consts = [None for _ in range(n)] # define positive error constraints for i in range(n): pos_err_consts[i] = solver.Constraint(0, \ 0, \ f'pos_err_const_{i}') pos_err_consts[i].SetCoefficient(pos_errors[i], -1) pos_err_consts[i].SetCoefficient(a, -x[i]) pos_err_consts[i].SetCoefficient(b, -1) pos_err_consts[i].SetCoefficient(one, y[i]) pos_err_consts[i].SetCoefficient(pos_zs[i], 1) # define negative error constraints for i in range(n): neg_err_consts[i] = solver.Constraint(0, \ 0, \ f'neg_err_const_{i}') neg_err_consts[i].SetCoefficient(neg_errors[i], -1) neg_err_consts[i].SetCoefficient(a, x[i]) neg_err_consts[i].SetCoefficient(b, 1) neg_err_consts[i].SetCoefficient(one, -y[i]) neg_err_consts[i].SetCoefficient(neg_zs[i], 1) # define absolute error constraints for i in range(n): abs_err_consts[i] = solver.Constraint(0, 0, f'abs_const_{i}') abs_err_consts[i].SetCoefficient(abs_errors[i], -1) abs_err_consts[i].SetCoefficient(pos_errors[i], 1) abs_err_consts[i].SetCoefficient(neg_errors[i], 1) status = solver.Solve() if status == solver.OPTIMAL: print('Problem solved in %f milliseconds' %solver.wall_time()) elif status == solver.FEASIBLE: print('Solver claims feasibility but not optimality') else: print('Solver ran to completion but did not find an optimal solution') print('objective value =', objective.Value()) print('\n')

print("a = ", a.solution_value()) print("b = ", b.solution_value())

solver = pywraplp.Solver('q4', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING) objective=solver.Objective() objective.SetMinimization() # Variables x[i][j] x_12 = solver.NumVar(0, solver.infinity(), 'x_12') x_17 = solver.NumVar(0, solver.infinity(), 'x_12') x_37 = solver.NumVar(0, solver.infinity(), 'x_12') x_34 = solver.NumVar(0, solver.infinity(), 'x_12') x_56 = solver.NumVar(0, solver.infinity(), 'x_12') x_57 = solver.NumVar(0, solver.infinity(), 'x_12') x_54 = solver.NumVar(0, solver.infinity(), 'x_12') x_62 = solver.NumVar(0, solver.infinity(), 'x_12') x_65 = solver.NumVar(0, solver.infinity(), 'x_12') x_72 = solver.NumVar(0, solver.infinity(), 'x_12') x_75 = solver.NumVar(0, solver.infinity(), 'x_12') # Objective function objective.SetCoefficient(x_12, 20) objective.SetCoefficient(x_17, 3) objective.SetCoefficient(x_72, 40) objective.SetCoefficient(x_62, 8) objective.SetCoefficient(x_65, 4) objective.SetCoefficient(x_56, 4) objective.SetCoefficient(x_54, 2) objective.SetCoefficient(x_57, 10) objective.SetCoefficient(x_75, 10) objective.SetCoefficient(x_34, 30) objective.SetCoefficient(x_37, 9) # Constraints # Supply node constraints node_1 = solver.Constraint(80,80,'node1') node_1.SetCoefficient(x_12,1) node_1.SetCoefficient(x_17,1) node_3 = solver.Constraint(70,70,'node3') node_3.SetCoefficient(x_37,1) node_3.SetCoefficient(x_34,1) # Demand node constraints node_2 = solver.Constraint(80,80, 'node2') node_2.SetCoefficient(x_12,1) node_2.SetCoefficient(x_62,1) node_2.SetCoefficient(x_72,1) node_4 = solver.Constraint(30,30,'node4') node_4.SetCoefficient(x_34,1) node_4.SetCoefficient(x_54,1) node_5 = solver.Constraint(40,40,'node5') node_5.SetCoefficient(x_75,1) node_5.SetCoefficient(x_65,1) node_5.SetCoefficient(x_54,-1) node_5.SetCoefficient(x_56,-1) node_5.SetCoefficient(x_57,-1) # Flow node constraints node_7 = solver.Constraint(0,0,'node7') node_7.SetCoefficient(x_57,1) node_7.SetCoefficient(x_37,1) node_7.SetCoefficient(x_17,1) node_7.SetCoefficient(x_72,-1) node_7.SetCoefficient(x_75,-1) node_6 = solver.Constraint(0,0,'node6') node_6.SetCoefficient(x_56,1) node_6.SetCoefficient(x_62,-1) node_6.SetCoefficient(x_65,-1) status = solver.Solve() if status == solver.OPTIMAL: print('Problem solved in %f milliseconds' %solver.wall_time()) elif status == solver.FEASIBLE: print('Solver claims feasibility but not optimality') else: print('Solver ran to completion but did not find an optimal solution') print('objective value =', objective.Value())

print('x_12', x_12.solution_value()) print('x_17', x_17.solution_value()) print('x_37', x_37.solution_value()) print('x_34', x_34.solution_value()) print('x_56', x_56.solution_value()) print('x_57', x_57.solution_value()) print('x_54', x_54.solution_value()) print('x_62', x_62.solution_value()) print('x_65', x_65.solution_value()) print('x_72', x_72.solution_value()) print('x_75', x_75.solution_value())