1. 模型

常見的線性規(guī)劃模型如下：
max z = cx
s.t. Ax = b

2. 求解步驟

假設(shè)B是基變量集合，通過矩陣的線性變換，基變量可由非基變量表示：
x'_i = c_i + Σ_j?Bm_i,jx'_j （i∈B）
目標(biāo)函數(shù)z也可以完全由非基變量表示：
z = z₀ + Σ_j?Bc_jx'_j
當(dāng)達到最優(yōu)解時，目標(biāo)函數(shù)中所有的系數(shù)c≤0，這樣非基變量等于0時，目標(biāo)函數(shù)可以取到最大值。以此為目標(biāo)，每次將最大的正系數(shù)max{c_i}對應(yīng)的非基變量替換為基變量，同時將min{b_j/a_i,j}對應(yīng)的基變量替換為非基變量。這個進基/出基的過程稱為pivoting。

3. python算法實現(xiàn)

這里假設(shè)原問題都是小于等于約束，這樣添加松弛變量之后，問題一定有初始可行解；同時假設(shè)問題存在有限最優(yōu)解。特殊情況將在下一節(jié)進行處理。代碼為：

import numpy as np

def pivot():
    l = list(d[0][:-2])
    jnum = l.index(max(l)) #轉(zhuǎn)入編號
    m = []
    for i in range(bn):
        if d[i][jnum] == 0:
            m.append(0.)
        else:
            m.append(d[i][-1]/d[i][jnum])
    inum = m.index(min([x for x in m[1:] if x!=0]))  #轉(zhuǎn)出下標(biāo)
    s[inum-1] = jnum
    r = d[inum][jnum]
    d[inum] /= r
    for i in [x for x in range(bn) if x !=inum]:
        r = d[i][jnum]
        d[i] -= r * d[inum]
        
def solve():
    flag = True
    while flag:
        if max(list(d[0][:-1])) <= 0: #直至所有系數(shù)小于等于0
            flag = False
        else:
            pivot()
            
def printSol():
    for i in range(cn - 1):
        if i in s:
            print("x"+str(i)+"=%.2f" % d[s.index(i)+1][-1])
        else:
            print("x"+str(i)+"=0.00")
    print("objective is %.2f"%(-d[0][-1]))

調(diào)用的例子：

d = np.loadtxt("data.txt", dtype=np.float)
(bn,cn) = d.shape
s = list(range(cn-bn,cn-1)) #基變量列表
solve()
printSol()

data.txt文件中的內(nèi)容為：

1 14 6 0 0 0 0 0

1 1 1 1 0 0 0 4

1 0 0 0 1 0 0 2

0 0 1 0 0 1 0 3

0 3 1 0 0 0 1 6

代表的求解模型是：

max z = x0+14*x1+6*x2

s.t.

x0 + x1 + x2 <= 4

x0 <= 2

x2 <= 3

3*x1 + x2 <= 6

運行后輸出結(jié)果為：

x0=0.00

x1=1.00

x2=3.00

x3=0.00

x4=2.00

x5=0.00

x6=0.00

objective is 32.00

4. 后感

將simplex用代碼寫出來，才覺得以前糾結(jié)那么久的問題原來那么簡單。兩三行代碼能說清楚的事，何必寫一堆看得人眼花繚亂的數(shù)學(xué)公式呢。
另外，線性規(guī)劃還有一些很基礎(chǔ)的理論要掌握好：

1. 極點和極方向的理論，這個是單純型法的理論基礎(chǔ)?？梢詤⒖?a target="_blank" rel="nofollow">https://wenku.baidu.com/view/1a60ce6125c52cc58bd6be23.html
2. 對偶理論，這個在以后經(jīng)常會用到。