search - Other multi value optimisation using brute force search?

Question

I've 6 list of company possible orders (a,b,c,d,e,f) in dollars.The price changes every week (13 weeks) as below.

a1_list = [1075000, 1075000, 1072500, 1072500, 1070000, 1070000, 1050000, 1535000, 1535000, 1015000, 1015000, 1000000, 1000000]

b1_list = [1275000, 1275000, 1278000, 1278000, 1242000, 1242000, 1266000, 1806000, 1806000, 1191000, 1191000, 1191000, 1191000]

c1_list = [1530000, 1530000, 1822500, 1822500, 1813500, 1813500, 1804500, 1773000, 1773000, 1746000, 1746000, 1710000, 1710000]

d1_list = [1005000, 1005000, 1005000, 1005000, 1005000, 1005000, 1005000, 960000, 960000, 960000, 960000,
 960000, 960000]

e1_list = [2436000, 2436000, 2905000, 2905000, 2877000, 2877000, 2849000, 2814000, 2814000, 2779000, 2779000, 2730000, 2730000]

f1_list = [1881000, 1881000, 1890000, 1890000, 1863000, 1863000, 1854000, 1822500, 1822500, 1804500, 1804500, 1786500, 1786500]

I can only choose 1 order from a company every time. That is, if I choose the the order for 1st week to be comp A, then company B, C, D, E and F must not be on week1. Every number in the list correspond to a particular week.

For example, for company A order, the price in week 1 and 2 will be 1075000. If the order is not made in week 1 or 2, but made in week 3 and 4, the price will be 1072500.

This is sort of an optimisation problem.

I wrote a manual calculation to calculate the best combination that give me the best profit.

Below are my codes:

import numpy as np
from scipy import optimize

price = np.array([
    [430,   425,    340,    402,    348,    418],
    [429,   426,    405,    402,    415,    420],
    [428,   414,    403,    402,    411,    414],
    [420,   422,    401,    402,    407,    412],
    [614,   602,    394,    384,    402,    405],
    [406,   397,    388,    384,    397,    401],
    [400,   397,    380,    384,    390,    397],
    ])

a1Q = 2500
a2Q = 4000
b1Q = 3000
b2Q = 3500
c1Q = 4500
c2Q = 5500
c3Q = 4000
d1Q = 2500
d2Q = 4000
e1Q = 7000
e2Q = 2000
f1Q = 4500
f2Q = 1000
 

a1_price = price[:,0]*a1Q
a2_price = price[:,0]*a2Q
b1_price = price[:,1]*b1Q
b2_price = price[:,1]*b2Q
c1_price = price[:,2]*c1Q
c2_price = price[:,2]*c2Q
c3_price = price[:,2]*c3Q
d1_price = price[:,3]*d1Q
d2_price = price[:,3]*d2Q
e1_price = price[:,4]*e1Q
e2_price = price[:,4]*e2Q
f1_price = price[:,5]*f1Q
f2_price = price[:,5]*f2Q


a1_list = [a1_price[0]]*2 + [a1_price[1]]*2 + [a1_price[2]]*2 + [a1_price[3]] + [a1_price[4]]*2 + [a1_price[5]]*2 + [a1_price[6]]*2
a2_list = [a2_price[0]]*2 + [a2_price[1]]*2 + [a2_price[2]]*2 + [a2_price[3]] + [a2_price[4]]*2 + [a2_price[5]]*2 + [a2_price[6]]*2
b1_list = [b1_price[0]]*2 + [b1_price[1]]*2 + [b1_price[2]]*2 + [b1_price[3]] + [b1_price[4]]*2 + [b1_price[5]]*2 + [b1_price[6]]*2
b2_list = [b2_price[0]]*2 + [b2_price[1]]*2 + [b2_price[2]]*2 + [b2_price[3]] + [b2_price[4]]*2 + [b2_price[5]]*2 + [b2_price[6]]*2
c1_list = [c1_price[0]]*2 + [c1_price[1]]*2 + [c1_price[2]]*2 + [c1_price[3]] + [c1_price[4]]*2 + [c1_price[5]]*2 + [c1_price[6]]*2
c2_list = [c2_price[0]]*2 + [c2_price[1]]*2 + [c2_price[2]]*2 + [c2_price[3]] + [c2_price[4]]*2 + [c2_price[5]]*2 + [c2_price[6]]*2
c3_list = [c3_price[0]]*2 + [c3_price[1]]*2 + [c3_price[2]]*2 + [c3_price[3]] + [c3_price[4]]*2 + [c3_price[5]]*2 + [c3_price[6]]*2
d1_list = [d1_price[0]]*2 + [d1_price[1]]*2 + [d1_price[2]]*2 + [d1_price[3]] + [d1_price[4]]*2 + [d1_price[5]]*2 + [d1_price[6]]*2
d2_list = [d2_price[0]]*2 + [d2_price[1]]*2 + [d2_price[2]]*2 + [d2_price[3]] + [d2_price[4]]*2 + [d2_price[5]]*2 + [d2_price[6]]*2
e1_list = [e1_price[0]]*2 + [e1_price[1]]*2 + [e1_price[2]]*2 + [e1_price[3]] + [e1_price[4]]*2 + [e1_price[5]]*2 + [e1_price[6]]*2
e2_list = [e2_price[0]]*2 + [e2_price[1]]*2 + [e2_price[2]]*2 + [e2_price[3]] + [e2_price[4]]*2 + [e2_price[5]]*2 + [e2_price[6]]*2
f1_list = [f1_price[0]]*2 + [f1_price[1]]*2 + [f1_price[2]]*2 + [f1_price[3]] + [f1_price[4]]*2 + [f1_price[5]]*2 + [f1_price[6]]*2
f2_list = [f2_price[0]]*2 + [f2_price[1]]*2 + [f2_price[2]]*2 + [f2_price[3]] + [f2_price[4]]*2 + [f2_price[5]]*2 + [f2_price[6]]*2

best = 0
ind_a1,ind_b1,ind_c1,ind_d1,ind_e1,ind_f1 = 0,0,0,0,0,0

for a1 in a1_list:
    # print(f'A: {ind_a}')
    # ind_a+=1
    ind_b1 = 0
    # ind_c=0
    for b1 in b1_list:
        
        if ind_b1 != ind_a1:
            
            # print(ind_b)
            # total = a + b
            ind_c1 = 0
            
            for c1 in c1_list:
                
                if ind_c1 != ind_a1 and ind_c1 != ind_b1:
                    
                    
                    ind_d1 = 0
                    
                    for d1 in d1_list:
                        
                        if ind_d1 != ind_a1 \
                            and ind_d1 != ind_b1 \
                                and ind_d1!= ind_c1:
                            
                            ind_e1 = 0                               
                            
                            for e1 in e1_list:
                                
                                if ind_e1 != ind_a1 \
                                    and ind_e1 != ind_b1 \
                                        and ind_e1!= ind_c1 \
                                            and ind_e1!= ind_d1:
                                    
                                    ind_f1 = 0
                                    
                                    for f1 in f1_list:
                                        
                                        if ind_f1 != ind_a1 \
                                            and ind_f1 != ind_b1 \
                                                and ind_f1!= ind_c1 \
                                                    and ind_f1!= ind_d1 \
                                                        and ind_f1!= ind_e1:
                                    
                                            total = a1 + b1 + c1 + d1 + e1 + f1
                        
                                            if total >best:
                                                best = total
                                                print(a1,b1,c1,d1,e1,f1, ind_a1,ind_b1,ind_c1,ind_d1,ind_e1,ind_f1)
                                                print(best)
                                                
                                        ind_f1 +=1
                                ind_e1 +=1
                        ind_d1 += 1
                ind_c1+=1            
        ind_b1+=1
    ind_a1+=1
        

I'm wondering if there's a simpler and cleaner way to solve this problem, or to use built in scipy optimization functions like scipy.optimize.minimize or scipy.optimize.brute?

This is actually a portion of a huge problem optimisation function that I'm solving.

Just to give you an idea (but may be irrelevant to this question), below are some plot. I'm trying to maximize the revenue.

Any help would be greatly appreciated.

标签： searchoptimizationscipymaximizemaximum-profit-problem

Answer 1

这个问题最好使用 munkres 算法（或称为匈牙利算法）来解决。

要了解此算法的工作原理，

您可以观看下面的视频。

https://www.youtube.com/watch?v=cQ5MsiGaDY8

要在 Python 中做到这一点，首先安装 munkres 库。

pip install munkres

您可以参考此处了解更多信息。

http://software.clapper.org/munkres/

下面是我在不循环 60 亿次以上（13 个变量）-> O(n!) 的情况下解决此问题的示例代码。使用 munkres 算法，它是 O(n^3)。显然，有一些技巧可以通过一些数学矩阵缩减技术来优化值。上面的视频会给你一些想法。

from munkres import Munkres, print_matrix
import sys

matrix = [
    a1_list,
    b1_list,
    c1_list,
    d1_list,
    e1_list,
    f1_list,
    a2_list,
    b2_list,
    c2_list,
    d2_list,
    e2_list,
    f2_list,
    c3_list,
          ]

cost_matrix = []
for row in matrix:
    cost_row = []
    for col in row:
        cost_row += [sys.maxsize - col]
    cost_matrix += [cost_row]

m = Munkres()
indexes = m.compute(cost_matrix)
print_matrix(matrix, msg='Highest profit through this matrix:')
total = 0
for row, column in indexes:
    value = matrix[row][column]
    total += value
    print(f'({row}, {column}) -> {value}')

print(f'total profit={total}')

你会得到如下结果。

Highest profit through this matrix:
[1575000, 1575000, 1072500, 1072500, 1070000, 1070000, 1050000, 1035000, 1035000, 1015000, 1015000, 1000000, 1000000]
[1275000, 1275000, 1278000, 1278000, 1242000, 1242000, 1266000, 1806000, 1806000, 1191000, 1191000, 1191000, 1191000]
[1530000, 1530000, 1822500, 1822500, 1813500, 1813500, 1804500, 1773000, 1773000, 1746000, 1746000, 1710000, 1710000]
[1005000, 1005000, 1005000, 1005000, 1005000, 1005000, 1005000,  960000,  960000,  960000,  960000,  960000,  960000]
[2436000, 2436000, 2905000, 2905000, 2877000, 2877000, 2849000, 2814000, 2814000, 2779000, 2779000, 2730000, 2730000]
[1881000, 1881000, 1890000, 1890000, 1863000, 1863000, 1854000, 1822500, 1822500, 1804500, 1804500, 1786500, 1786500]
[2520000, 2520000, 1716000, 1716000, 1712000, 1712000, 1680000, 1656000, 1656000, 1624000, 1624000, 1600000, 1600000]
[1487500, 1487500, 1491000, 1491000, 1449000, 1449000, 1477000, 2107000, 2107000, 1389500, 1389500, 1389500, 1389500]
[1870000, 1870000, 2227500, 2227500, 2216500, 2216500, 2205500, 2167000, 2167000, 2134000, 2134000, 2090000, 2090000]
[1608000, 1608000, 1608000, 1608000, 1608000, 1608000, 1608000, 1536000, 1536000, 1536000, 1536000, 1536000, 1536000]
(0, 0) -> 1575000
(1, 7) -> 1806000
(2, 4) -> 1813500
(3, 12) -> 960000
(4, 3) -> 2905000
(5, 2) -> 1890000
(6, 1) -> 2520000
(7, 8) -> 2107000
(8, 5) -> 2216500
(9, 6) -> 1608000
total profit=19401000