Approche De La Programmation Linéaire En Nombres Entiers
Ce met en place naturellement comme un multi-étape Entier du Programme, avec la participation dans {les pommes, les poires, les oranges} à partir de l'étape précédente en prenant en compte le calcul de la variation relative des exploitations qui doivent être limitées. Il n'y a pas de notion de optimal ici, mais nous pouvons nous tourner le "chiffre d'affaires" contrainte dans un objectif et de voir ce qui se passe.
Les solutions fournies améliorer ceux dans le graphique ci-dessus, et sont minimes dans le sens de la variation totale dans le panier holdings.
Commentaires -
Je ne sais pas comment vous avez calculé le "% de changement" de la colonne de votre tableau. Un changement du jour 1 au Jour 2 de 20 pommes de 21 pommes est une 4.76% changement?
Tous les jours, le total de vos avoirs dans les fruits est exactement 100. Il y a une contrainte que la somme des participations est <= 100. En l'absence de violation, je veux juste confirmer.
On peut définir cela comme un programme linéaire en nombres entiers, en utilisant l'entier de l'optimisation de la routine d' ortools. Je n'ai pas utilisé un solveur ILP pour une longue période de temps, et c'est un genre de pâte feuilletée, je crois (le solveur.OPTIMALE drapeau est jamais vrai, il semble, même pour les jouets des problèmes. En outre, l' ortools LP solveur ne parvient pas à trouver une solution optimale dans le cas où scipy.linprog fonctionne sans accroc)
h1,d = holdings in apples (number of apples) at end of day d
h2,d = holdings in pears at end of day d
h3,d = holdings in oranges at end of day d
Je vais vous donner deux propositions, celle qui minimise l' l1 norme de l'erreur absolue, l'autre à l' l0norme.
L' l1 solution trouve le minimum de abs(h1,(d+1) - h1,d)/h1 + ... + abs(h3,(d+1) - h3,d)/h3), en espérant que la contrainte que chaque variation relative des exploitations est inférieure à 10% si la somme de la variation relative des exploitations est réduit au minimum.
La seule chose qui l'empêche d'être un programme linéaire (en dehors de l'entier exigence) est la fonction objective non linéaire. Pas de problème, nous pouvons introduire slack variables et de faire tout son linéaire. Pour l' l1 de la formulation, 6 slack variables sont introduites, 2 par les fruits, et 6 autres contraintes d'inégalité. Pour l' l0 de la formulation, 1 mou variable est introduite, et 6 autres contraintes d'inégalité.
C'est un processus en deux étapes, par exemple, le remplacement |apples_new - apples_old|/|apples_old| avec la variable |e|, et l'ajout de contraintes d'inégalité pour assurer l'e mesure de ce que nous aimerions. Nous avons ensuite remplacer|e| avec (e+ - e-), chacune de e+, e- >0. Il peut être montré que l'une de e+, e - sera de 0, et que (e+ + e-) est la valeur absolue de l'e. De cette façon, la paire (e+, e-) peut représenter un nombre positif ou négatif. Norme des choses, mais qui ajoute un tas de variables et de contraintes. Je peux vous expliquer cela en détail un peu plus si nécessaire.
import numpy as np
from ortools.linear_solver import pywraplp
def fruit_basket_l1_ortools():
UPPER_BOUND = 1000
prices = [[2,3,5],
[1,2,4],
[1,2,3]]
holdings = [20,43,37]
values = [348, 251, 213]
for day in range(len(values)):
solver = pywraplp.Solver('ILPSolver',
pywraplp.Solver.BOP_INTEGER_PROGRAMMING)
# solver = pywraplp.Solver('ILPSolver',
# pywraplp.Solver.CLP_LINEAR_PROGRAMMING)
c = ([1,1] * 3) + [0,0,0]
price = prices[day]
value = values[day]
A_eq = [[ 0, 0, 0, 0, 0, 0, price[0], price[1], price[2]]]
b_eq = [value]
A_ub = [[-1*holdings[0], 1*holdings[0], 0, 0, 0, 0, 1.0, 0, 0],
[-1*holdings[0], 1*holdings[0], 0, 0, 0, 0, -1.0, 0, 0],
[ 0, 0, -1*holdings[1], 1*holdings[1], 0, 0, 0, 1.0, 0],
[ 0, 0, -1*holdings[1], 1*holdings[1], 0, 0, 0, -1.0, 0],
[ 0, 0, 0, 0, -1*holdings[2], 1*holdings[2], 0, 0, 1.0],
[ 0, 0, 0, 0, -1*holdings[2], 1*holdings[2], 0, 0, -1.0]]
b_ub = [1*holdings[0], -1*holdings[0], 1*holdings[1], -1*holdings[1], 1*holdings[2], -1*holdings[2]]
num_vars = len(c)
num_ineq_constraints = len(A_ub)
num_eq_constraints = len(A_eq)
data = [[]] * num_vars
data[0] = solver.IntVar( 0, UPPER_BOUND, 'e1_p')
data[1] = solver.IntVar( 0, UPPER_BOUND, 'e1_n')
data[2] = solver.IntVar( 0, UPPER_BOUND, 'e2_p')
data[3] = solver.IntVar( 0, UPPER_BOUND, 'e2_n')
data[4] = solver.IntVar( 0, UPPER_BOUND, 'e3_p')
data[5] = solver.IntVar( 0, UPPER_BOUND, 'e3_n')
data[6] = solver.IntVar( 0, UPPER_BOUND, 'x1')
data[7] = solver.IntVar( 0, UPPER_BOUND, 'x2')
data[8] = solver.IntVar( 0, UPPER_BOUND, 'x3')
constraints = [0] * (len(A_ub) + len(b_eq))
# Inequality constraints
for i in range(0,num_ineq_constraints):
constraints[i] = solver.Constraint(-solver.infinity(), b_ub[i])
for j in range(0,num_vars):
constraints[i].SetCoefficient(data[j], A_ub[i][j])
# Equality constraints
for i in range(num_ineq_constraints, num_ineq_constraints+num_eq_constraints):
constraints[i] = solver.Constraint(b_eq[i-num_ineq_constraints], b_eq[i-num_ineq_constraints])
for j in range(0,num_vars):
constraints[i].SetCoefficient(data[j], A_eq[i-num_ineq_constraints][j])
# Objective function
objective = solver.Objective()
for i in range(0,num_vars):
objective.SetCoefficient(data[i], c[i])
# Set up as minization problem
objective.SetMinimization()
# Solve it
result_status = solver.Solve()
solution_set = [data[i].solution_value() for i in range(len(data))]
print('DAY: {}'.format(day+1))
print('======')
print('SOLUTION FEASIBLE: {}'.format(solver.FEASIBLE))
print('SOLUTION OPTIMAL: {}'.format(solver.OPTIMAL))
print('VALUE OF BASKET: {}'.format(np.dot(A_eq[0], solution_set)))
print('SOLUTION (apples,pears,oranges): {!r}'.format(solution_set[-3:]))
print('PCT CHANGE (apples,pears,oranges): {!r}\n\n'.format([round(100*(x-y)/y,2) for x,y in zip(solution_set[-3:], holdings)]))
# Update holdings for the next day
holdings = solution_set[-3:]
Une seule exécution donne:
DAY: 1
======
SOLUTION FEASIBLE: 1
SOLUTION OPTIMAL: 0
VALUE OF BASKET: 348.0
SOLUTION (apples,pears,oranges): [20.0, 41.0, 37.0]
PCT CHANGE (apples,pears,oranges): [0.0, -4.65, 0.0]
DAY: 2
======
SOLUTION FEASIBLE: 1
SOLUTION OPTIMAL: 0
VALUE OF BASKET: 251.0
SOLUTION (apples,pears,oranges): [21.0, 41.0, 37.0]
PCT CHANGE (apples,pears,oranges): [5.0, 0.0, 0.0]
DAY: 3
======
SOLUTION FEASIBLE: 1
SOLUTION OPTIMAL: 0
VALUE OF BASKET: 213.0
SOLUTION (apples,pears,oranges): [20.0, 41.0, 37.0]
PCT CHANGE (apples,pears,oranges): [-4.76, 0.0, 0.0]
L' l0 formulation est également présenté:
def fruit_basket_l0_ortools():
UPPER_BOUND = 1000
prices = [[2,3,5],
[1,2,4],
[1,2,3]]
holdings = [20,43,37]
values = [348, 251, 213]
for day in range(len(values)):
solver = pywraplp.Solver('ILPSolver',
pywraplp.Solver.BOP_INTEGER_PROGRAMMING)
# solver = pywraplp.Solver('ILPSolver',
# pywraplp.Solver.CLP_LINEAR_PROGRAMMING)
c = [1, 0, 0, 0]
price = prices[day]
value = values[day]
A_eq = [[0, price[0], price[1], price[2]]]
b_eq = [value]
A_ub = [[-1*holdings[0], 1.0, 0, 0],
[-1*holdings[0], -1.0, 0, 0],
[-1*holdings[1], 0, 1.0, 0],
[-1*holdings[1], 0, -1.0, 0],
[-1*holdings[2], 0, 0, 1.0],
[-1*holdings[2], 0, 0, -1.0]]
b_ub = [holdings[0], -1*holdings[0], holdings[1], -1*holdings[1], holdings[2], -1*holdings[2]]
num_vars = len(c)
num_ineq_constraints = len(A_ub)
num_eq_constraints = len(A_eq)
data = [[]] * num_vars
data[0] = solver.IntVar(-UPPER_BOUND, UPPER_BOUND, 'e' )
data[1] = solver.IntVar( 0, UPPER_BOUND, 'x1')
data[2] = solver.IntVar( 0, UPPER_BOUND, 'x2')
data[3] = solver.IntVar( 0, UPPER_BOUND, 'x3')
constraints = [0] * (len(A_ub) + len(b_eq))
# Inequality constraints
for i in range(0,num_ineq_constraints):
constraints[i] = solver.Constraint(-solver.infinity(), b_ub[i])
for j in range(0,num_vars):
constraints[i].SetCoefficient(data[j], A_ub[i][j])
# Equality constraints
for i in range(num_ineq_constraints, num_ineq_constraints+num_eq_constraints):
constraints[i] = solver.Constraint(int(b_eq[i-num_ineq_constraints]), b_eq[i-num_ineq_constraints])
for j in range(0,num_vars):
constraints[i].SetCoefficient(data[j], A_eq[i-num_ineq_constraints][j])
# Objective function
objective = solver.Objective()
for i in range(0,num_vars):
objective.SetCoefficient(data[i], c[i])
# Set up as minization problem
objective.SetMinimization()
# Solve it
result_status = solver.Solve()
solution_set = [data[i].solution_value() for i in range(len(data))]
print('DAY: {}'.format(day+1))
print('======')
print('SOLUTION FEASIBLE: {}'.format(solver.FEASIBLE))
print('SOLUTION OPTIMAL: {}'.format(solver.OPTIMAL))
print('VALUE OF BASKET: {}'.format(np.dot(A_eq[0], solution_set)))
print('SOLUTION (apples,pears,oranges): {!r}'.format(solution_set[-3:]))
print('PCT CHANGE (apples,pears,oranges): {!r}\n\n'.format([round(100*(x-y)/y,2) for x,y in zip(solution_set[-3:], holdings)]))
# Update holdings for the next day
holdings = solution_set[-3:]
Une seule exécution de cette donne
DAY: 1
======
SOLUTION FEASIBLE: 1
SOLUTION OPTIMAL: 0
VALUE OF BASKET: 348.0
SOLUTION (apples,pears,oranges): [33.0, 79.0, 9.0]
PCT CHANGE (apples,pears,oranges): [65.0, 83.72, -75.68]
DAY: 2
======
SOLUTION FEASIBLE: 1
SOLUTION OPTIMAL: 0
VALUE OF BASKET: 251.0
SOLUTION (apples,pears,oranges): [49.0, 83.0, 9.0]
PCT CHANGE (apples,pears,oranges): [48.48, 5.06, 0.0]
DAY: 3
======
SOLUTION FEASIBLE: 1
SOLUTION OPTIMAL: 0
VALUE OF BASKET: 213.0
SOLUTION (apples,pears,oranges): [51.0, 63.0, 12.0]
PCT CHANGE (apples,pears,oranges): [4.08, -24.1, 33.33]
Résumé
L' l1 formulation donne plus de résultats sensées, baisse du chiffre d'affaires, beaucoup plus bas. L'optimalité vérification échoue sur toutes les courses, cependant, qui est relatif. J'ai inclus un solveur linéaire trop et qui ne le feasiblity vérifier en quelque sorte, je ne sais pas pourquoi. Le Google de fournir de précieux peu de documentation pour la ortools lib, et la plupart des il est pour le C++ lib. Mais l' l1 formulation peut être une solution à votre problème, qui peut évoluer. PAI est en général NP-complet, et est donc votre problème le plus probable.
Aussi - n'est qu'une solution existe pas sur le jour 2? Comment définissez-vous la variation en % de sorte qu'il ne dans le graphique ci-dessus? Si je savais que je pouvais procéder à une refonte du les inégalités ci-dessus et nous avons la solution générale.
