simplex

simplex.py

def print_variable(basic_idx, none_basic_idx):
    b_name = [f'x_{i+1}' for i in basic_idx]
    nb_name = [f'x_{i+1}' for i in none_basic_idx]
    print(f'基变量有：{b_name}, 非基变量有:{nb_name}')



def get_matrix_for_exchange(none_basic_idx, exchange_none_basic_index):
    A = np.array([
        [1, 2, 1, 0, 0],
        [4, 0, 0, 1, 0],
        [0, 4, 0, 0, 1],
    ])
    b = np.array([[8, 16, 12]]).T
    LARGE_NUMBER = 1000000  # 很大的值

    for none_basic_index in none_basic_idx:
        if none_basic_index != exchange_none_basic_index:
            tmp = np.array([[0 if x != none_basic_index else 1 for x in range(size)]])
            A = np.insert(A, 0, values=tmp, axis=0)
            b = np.insert(b, 0, values=[[0]], axis=0)
        else:
            tmp = np.array([[0 if x != none_basic_index else 1 for x in range(size)]])
            A = np.insert(A, 0, values=tmp, axis=0)
            b = np.insert(b, 0, values=[[LARGE_NUMBER]], axis=0)

    return A, b


def get_matrix(none_basic_idx, size):
    A = np.array([
        [1, 2, 1, 0, 0],
        [4, 0, 0, 1, 0],
        [0, 4, 0, 0, 1]
    ])
    b = np.array([[8, 16, 12]]).T

    print('设定非基变量等于0作为切入定点')
    for none_basic_index in none_basic_idx:
        tmp = np.array([[0 if x != none_basic_index else 1 for x in range(size)]])
        A = np.insert(A, 0, values=tmp, axis=0)
        b = np.insert(b, 0, values=[[0]], axis=0)

    return A, b


def get_exchange(rs, basic_idx):
    exchange_basic_index = basic_idx[0]
    min_value = rs[f'x_{exchange_basic_index+1}']

    for basic_index in basic_idx:
        if rs[f'x_{basic_index+1}'] < min_value:
            exchange_basic_index = basic_index
            min_value = rs[f'x_{basic_index+1}']
    print(f'选中x_{exchange_basic_index+1}出基变量，因为它的解{min_value}最小')
    return exchange_basic_index


def get_exchange_none(none_basic_idx, target):
    exchange_none_basic_index = none_basic_idx[0]
    max_c = target[0][exchange_none_basic_index]

    for none_basic_index in none_basic_idx:
        if target[0][none_basic_index] > max_c:
            exchange_none_basic_index = none_basic_index
            max_c = target[0][exchange_none_basic_index]
    print(f'选中x_{exchange_none_basic_index+1}入基变量，因为它的系数{max_c}最大')
    return exchange_none_basic_index, max_c


def check(none_basic_idx):
    rs = all([target[0][x] <= 0 for x in none_basic_idx])
    print(f'最优?{rs}')
    return rs

def solve(A, b):
    s = np.linalg.solve(A, b)
    rs = {f'x_{i+1}': value for i, value in enumerate(s.T[0])}
    print(f'可行解为:{rs}')
    return rs


if __name__ == '__main__':
    import numpy as np
    """
    z = 2 x1 + 3 x2 + 0 x3 + 0 x4 + 0 x5
    x1 + 2 x2 + x3 = 8
    4 x1 + x4 = 16
    4 x2 + x5 = 12
    """
    target = np.array([[2, 3, 0, 0, 0]])
    size = len(target[0])
    none_basic_size = 2
    idx = list(range(size))
    none_basic_idx = idx[:none_basic_size]
    basic_idx = idx[none_basic_size:]
    print_variable(basic_idx, none_basic_idx)

    #  1.
    solve(*get_matrix(none_basic_idx, size))
    check(none_basic_idx)

    #  improve
    exchange_none_basic_index, max_c = get_exchange_none(none_basic_idx, target)
    rs = solve(*get_matrix_for_exchange(none_basic_idx, exchange_none_basic_index))
    exchange_basic_index = get_exchange(rs, basic_idx)

    pos_basic_idx = basic_idx.index(exchange_basic_index)
    pos_none_basic_idx = none_basic_idx.index(exchange_none_basic_index)
    basic_idx[pos_basic_idx], none_basic_idx[pos_none_basic_idx] = none_basic_idx[pos_none_basic_idx], basic_idx[pos_basic_idx]

    print_variable(basic_idx, none_basic_idx)
    
    # todo： 如何使用代码实现消元法，生成新的目标函数？