13、単純形法(目標が最大、制約が以下)

# -*- coding: utf-8 -*-
"""
Created on Fri Mar  8 19:18:53 2019

@author: zhangchaoyu
"""

import copy

"""
    

     ：

max z = c1x1 + c2x2 + ... + cnxn

s.t. 
    ai1x1 + ai2x2 + ... + ainxn <= bi  i=1,2,...,m
    xj >=0 j=1,2,...,n
    
     C、    X n  ，    B m  ，     m*n  ，      

"""

def find_new(C, A, B):
    idex_positive = -1
    for i in range(len(C)):
        if C[i] > 0 and C[i] > idex_positive:
            idex_positive = i
    
    if idex_positive == -1:
        print("      0 ，    ")
        return -1
    
    flag = -1
    row = -1
    rate = -1
    for i in range(len(B)):
        if A[i][idex_positive] <= 0:
            continue
        if rate == -1 or (rate != -1 and rate > B[i]/A[i][idex_positive]):
            flag = 1
            row = i
            rate = B[i]/A[i][idex_positive]
    if flag == 1:
        return [row, idex_positive]
    else:
        print("      0 ，    ")
        return -1

def adjust(idex_row, idex_col, A, B, C, idexs, X, v):
    
    m = len(B)
    n = len(C)
    
    idexs[idex_row] = idex_col
    
    rate = A[idex_row][idex_col]
    for i in range(n):
        A[idex_row][i] /= rate
    B[idex_row] /= rate
    
    for i in range(m):
        if i == idex_row:
            continue
        rate = A[i][idex_col]/A[idex_row][idex_col]
        B[i] -= rate*B[idex_row]
        for j in range(n):
            A[i][j] -= rate*A[idex_row][j]
    
    rate = C[idex_col]/A[idex_row][idex_col]
    for i in range(n):
        C[i] -= rate*A[idex_row][i]
    v[0] -= rate*B[idex_row]
    
    for i in range(len(X)):
        if i not in idexs:
            X[i] = 0
        else:
            for j in range(len(idexs)):
                if i == idexs[j]:
                    X[i] = B[j]
    
    

def show(C, A, B, X, v):
    
    result = []
    result.append(copy.deepcopy(C+v))
    for i in range(len(A)):
        result.append(copy.deepcopy(A[i]+[B[i]]))
    for r in result:
        print(r)
    print("   X="+str(X))
    print()
    
def simplex(C0, A0, B0):
    
    C = copy.deepcopy(C0)
    A = copy.deepcopy(A0)
    B = copy.deepcopy(B0)
    
    #     
    m = len(A0)
    n = len(C0)
    
    #           ，      C   A C1 A1，       X（B      0）
    for i in range(m):
        C.append(0)
        temp = [0 for j in range(m)]
        temp[i] = 1
        A[i] = A[i] + copy.deepcopy(temp)
    idexs = [n+i for i in range(m)]
    X = [0 for i in range(n)] + copy.deepcopy(B)
    v = [0]
    
    #      
    """  ，C       ，        0           0      ，  ；
                  0  ，   """
    loop = 0
    print(" "+str(loop)+"    ：")
    show(C, A, B, X, v)
    idex = find_new(C, A, B)
    
    while True:
        if idex == -1:
            break
        idex_row = idex[0]
        idex_col = idex[1]
        adjust(idex_row, idex_col, A, B, C, idexs, X, v)
        loop += 1
        print(" "+str(loop)+"    ：")
        show(C, A, B, X, v)
        idex = find_new(C,A,B)
        
    return X 
    

examples = []
examples.append([[2,3],[[1,2],[4,0],[0,4]],[8,16,12]])
examples.append()


C0 = examples[-1][0]
A0 = examples[-1][1]
B0 = examples[-1][2]