我是猿童学，本文是根据司守奎老师《数学建模算法与程序》的书本内容编写，使用其书中案例，书中的编程语言是MATLAB、Lingo，我将使用Python来解决问题。接下来的一个月我将学习使用Python来解决数学建模问题。将记录下学习中的笔记和部分案例。

1、线性规划

1.1 线性规划的实例与定义

例 1 某机床厂生产甲、乙两种机床每台销售后的利润分别为 4000 元与3000元。 生产甲机床需用 A、B 机器加工，加工时间分别为每台 2 小时和1小时生产乙机床需用 A、B、C 三种机器加工，加工时间为每台各一小时。若每天可用于加工的机器时数分别为 A 机器 10 小时、B 机器 8 小时和C 机器 7 小时，问该厂应生产甲、乙机床各几台，才能使总利润最大？

上述问题的数学模型：设该厂生产 乙机床时总利润最大，则

这里变量 （3）

其中，c是价值向量；A和b对应线性不等式约束；Aeq和beq对应线性等式约束；bounds对应公式中的lb和ub，决策向量的下界和上界。

scipy.optimize.linprog(c,A_ub=None,b_ub=None,A_eq=None,b_eq=None,bounds=None,method=’simplex’,callback=None,options=None)

输入参数解析：

• c：线性目标函数的系数
• A_ub（可选参数）：不等式约束矩阵，x的上限
• A_eq（可选参数）：等式约束矩阵，的每个元素必须等于）
• slack：不等式约束的松弛值（名义上为正值）
• success：当算法成功找到最佳解决方案时为 True
• status：表示算法退出状态的整数
  • 0 : 优化成功终止
  • 1 : 达到了迭代限制
  • 2 : 问题似乎不可行
  • 3 : 问题似乎是不收敛
  • 4 : 遇到数值困难
• nit：在所有阶段中执行的迭代总数
• message：算法退出状态的字符串描述符

使用scipy库来解决例1：

from scipy.optimize import linprogc = [-4, -3]   #目标函数的系数A= [[2, 1], [1, 1],[0,1]]  #<=不等式左侧未知数系数矩阵b = [10,8,7]    # <=不等式右侧常数矩阵#A_eq = [[]]   #等式左侧未知数系数矩阵#B_eq = []     #等式右侧常数矩阵x1 = [0, None]  #未知数取值范围x2 = [0, None]  #未知数取值范围res =linprog(c, A, b, bounds=(x1, x2))#默认求解最小值，求解最大值使用-c并取结果相反数print(res)

输出结果：

     con: array([], dtype=float64)     fun: -25.999999999841208 message: 'Optimization terminated successfully.'     nit: 5   slack: array([8.02629074e-11, 3.92663679e-11, 1.00000000e+00])  status: 0 success: True       x: array([2., 6.])

fun为目标函数的最优值，slack为松弛变量，status表示优化结果状态，x为最优解。

此模型的求解结果为：当x1=2，x2=6时，函数取得最优值25.999999999841208。

例 2求解下列线性规划问题：

使用Python编写：

from scipy import optimizeimport numpy as npc = np.array([2,3,1])A = np.array([[1,4,2],[3,2,0]])B = np.array([8,6])x1 = [0, None]  #未知数取值范围x2 = [0, None]  #未知数取值范围x3 = [0, None]  #未知数取值范围res = optimize.linprog(c,-A,-B,bounds=(x1, x2, x3))print(res)

输出结果：

     con: array([], dtype=float64)     fun: 6.999999994872993 message: 'Optimization terminated successfully.'     nit: 3   slack: array([ 3.85261245e-09, -1.41066261e-08])  status: 0 success: True       x: array([1.17949641, 1.23075538, 0.94874104])

此模型的求解结果为：当x1=1.1，x2=1.2，x3=0.9时，函数取得最优值6.999999994872993

2、运输问题

2.1产销平衡的数学建模过程：

例 6 某商品有个销地，各产地的产量分别为。若该商品由销地的单位运价为 ，其取值为由销地的该商品数量，数学模型为

其约束条件的系数矩阵相当特殊，可用比较简单的计算方法，习惯上称为表上作业法（由 康托洛维奇和希奇柯克两人独立地提出，简称康—希表上作业法），下面使用例子来讲解。

2.2 产销平衡的运输问题

1.问题描述

某公司下属有甲、乙、丙三个工厂，分别向A、B、C、D四个销地提供产品，产量、需求量及工厂到销售地的运价（单位：元/吨）如下表所示，求使费用最少的最佳运输方案。

2.问题解析

总产量=18+18+19=55

总销量=16+15+7+17=55

产量等于销量，即这是产销平衡的运输问题。直接采用表上作业法进行求解。

3.使用python求解：

# 运输问题求解：使用Vogel逼近法寻找初始基本可行解import numpy as npimport copyimport pandas as pddef main():    # mat = pd.read_csv('表上作业法求解运输问题.csv', header=None).values    # mat = pd.read_excel('表上作业法求解运输问题.xlsx', header=None).values    a = np.array([18, 18, 19])  # 产量    b = np.array([16, 15, 7, 17])  # 销量    c = np.array([[8, 6, 10, 9], [9, 12, 13, 7], [14, 12, 16, 5]])    # [c, x] = TP_vogel(mat)    [c,x]=TP_vogel([c,a,b])def TP_split_matrix(mat):  # 运输分割矩阵    c = mat[:-1, :-1]    a = mat[:-1, -1]    b = mat[-1, :-1]    return (c, a, b)def TP_vogel(var):  # Vogel法代码，变量var可以是以numpy.ndarray保存的运输表，或以tuple或list保存的(成本矩阵,供给向量,需求向量)    import numpy    typevar1 = type(var) == numpy.ndarray    typevar2 = type(var) == tuple    typevar3 = type(var) == list    if typevar1 == False and typevar2 == False and typevar3 == False:        print('>>>非法变量<<<')        (cost, x) = (None, None)    else:        if typevar1 == True:            [c, a, b] = TP_split_matrix(var)        elif typevar2 == True or typevar3 == True:            [c, a, b] = var        cost = copy.deepcopy(c)        x = np.zeros(c.shape)        M = pow(10, 9)        for factor in c.reshape(1, -1)[0]:            p = 1            while int(factor) != M:                if np.all(c == M):                    break                else:                    print('第1次迭代！')                    print('c:\n', c)                    # 获取行/列最小值数组                    row_mini1 = []                    row_mini2 = []                    for row in range(c.shape[0]):                        Row = list(c[row, :])                        row_min = min(Row)                        row_mini1.append(row_min)                        Row.remove(row_min)                        row_2nd_min = min(Row)                        row_mini2.append(row_2nd_min)                    # print(row_mini1,'\n',row_mini2)                    r_pun = [row_mini2[i] - row_mini1[i] for i in range(len(row_mini1))]                    print('行罚数：', r_pun)                    # 计算列罚数                    col_mini1 = []                    col_mini2 = []                    for col in range(c.shape[1]):                        Col = list(c[:, col])                        col_min = min(Col)                        col_mini1.append(col_min)                        Col.remove(col_min)                        col_2nd_min = min(Col)                        col_mini2.append(col_2nd_min)                    c_pun = [col_mini2[i] - col_mini1[i] for i in range(len(col_mini1))]                    print('列罚数：', c_pun)                    pun = copy.deepcopy(r_pun)                    pun.extend(c_pun)                    print('罚数向量：', pun)                    max_pun = max(pun)                    max_pun_index = pun.index(max(pun))                    max_pun_num = max_pun_index + 1                    print('最大罚数：', max_pun, '元素序号：', max_pun_num)                    if max_pun_num <= len(r_pun):                        row_num = max_pun_num                        print('对第', row_num, '行进行操作：')                        row_index = row_num - 1                        catch_row = c[row_index, :]                        print(catch_row)                        min_cost_colindex = int(np.argwhere(catch_row == min(catch_row)))                        print('最小成本所在列索引：', min_cost_colindex)                        if a[row_index] <= b[min_cost_colindex]:                            x[row_index, min_cost_colindex] = a[row_index]                            c1 = copy.deepcopy(c)                            c1[row_index, :] = [M] * c1.shape[1]                            b[min_cost_colindex] -= a[row_index]                            a[row_index] -= a[row_index]                        else:                            x[row_index, min_cost_colindex] = b[min_cost_colindex]                            c1 = copy.deepcopy(c)                            c1[:, min_cost_colindex] = [M] * c1.shape[0]                            a[row_index] -= b[min_cost_colindex]                            b[min_cost_colindex] -= b[min_cost_colindex]                    else:                        col_num = max_pun_num - len(r_pun)                        col_index = col_num - 1                        print('对第', col_num, '列进行操作：')                        catch_col = c[:, col_index]                        print(catch_col)                        # 寻找最大罚数所在行/列的最小成本系数                        min_cost_rowindex = int(np.argwhere(catch_col == min(catch_col)))                        print('最小成本所在行索引：', min_cost_rowindex)                        # 计算将该位置应填入x矩阵的数值（a,b中较小值）                        if a[min_cost_rowindex] >>供求平衡<<>>供不应求，需求方有余量<<>>供大于求，供给方有余量<<>>无法找到初始基可行解<<>>初始基本可行解x*：\n', x)        print('>>>当前总成本：', total_cost)        [m, n] = x.shape        varnum = np.array(np.nonzero(x)).shape[1]        if varnum != m + n - 1:            print('【注意：问题含有退化解】')    return (cost, x)if __name__ == '__main__':    main()

输出结果：

D:\Anaconda\python.exe D:/PyCharm/数学建模/线性规划/www.py第1次迭代！c: [[ 8  6 10  9] [ 9 12 13  7] [14 12 16  5]]行罚数： [2, 2, 7]列罚数： [1, 6, 3, 2]罚数向量： [2, 2, 7, 1, 6, 3, 2]最大罚数： 7 元素序号： 3对第 3 行进行操作：[14 12 16  5]最小成本所在列索引： 3本次迭代后的x矩阵： [[ 0.  0.  0.  0.] [ 0.  0.  0.  0.] [ 0.  0.  0. 17.]]a: [18 18  2]b: [16 15  7  0]c: [[         8          6         10 1000000000] [         9         12         13 1000000000] [        14         12         16 1000000000]]【迭代未完成】------------------------------------------------------------第2次迭代！第1次迭代！c: [[         8          6         10 1000000000] [         9         12         13 1000000000] [        14         12         16 1000000000]]行罚数： [2, 3, 2]列罚数： [1, 6, 3, 0]罚数向量： [2, 3, 2, 1, 6, 3, 0]最大罚数： 6 元素序号： 5对第 2 列进行操作：[ 6 12 12]最小成本所在行索引： 0本次迭代后的x矩阵： [[ 0. 15.  0.  0.] [ 0.  0.  0.  0.] [ 0.  0.  0. 17.]]a: [ 3 18  2]b: [16  0  7  0]c: [[         8 1000000000         10 1000000000] [         9 1000000000         13 1000000000] [        14 1000000000         16 1000000000]]【迭代未完成】------------------------------------------------------------第3次迭代！第1次迭代！c: [[         8 1000000000         10 1000000000] [         9 1000000000         13 1000000000] [        14 1000000000         16 1000000000]]行罚数： [2, 4, 2]列罚数： [1, 0, 3, 0]罚数向量： [2, 4, 2, 1, 0, 3, 0]最大罚数： 4 元素序号： 2对第 2 行进行操作：[         9 1000000000         13 1000000000]最小成本所在列索引： 0本次迭代后的x矩阵： [[ 0. 15.  0.  0.] [16.  0.  0.  0.] [ 0.  0.  0. 17.]]a: [3 2 2]b: [0 0 7 0]c: [[1000000000 1000000000         10 1000000000] [1000000000 1000000000         13 1000000000] [1000000000 1000000000         16 1000000000]]【迭代未完成】------------------------------------------------------------第4次迭代！第1次迭代！c: [[1000000000 1000000000         10 1000000000] [1000000000 1000000000         13 1000000000] [1000000000 1000000000         16 1000000000]]行罚数： [999999990, 999999987, 999999984]列罚数： [0, 0, 3, 0]罚数向量： [999999990, 999999987, 999999984, 0, 0, 3, 0]最大罚数： 999999990 元素序号： 1对第 1 行进行操作：[1000000000 1000000000         10 1000000000]最小成本所在列索引： 2本次迭代后的x矩阵： [[ 0. 15.  3.  0.] [16.  0.  0.  0.] [ 0.  0.  0. 17.]]a: [0 2 2]b: [0 0 4 0]c: [[1000000000 1000000000 1000000000 1000000000] [1000000000 1000000000         13 1000000000] [1000000000 1000000000         16 1000000000]]【迭代未完成】------------------------------------------------------------第5次迭代！第1次迭代！c: [[1000000000 1000000000 1000000000 1000000000] [1000000000 1000000000         13 1000000000] [1000000000 1000000000         16 1000000000]]行罚数： [0, 999999987, 999999984]列罚数： [0, 0, 3, 0]罚数向量： [0, 999999987, 999999984, 0, 0, 3, 0]最大罚数： 999999987 元素序号： 2对第 2 行进行操作：[1000000000 1000000000         13 1000000000]最小成本所在列索引： 2本次迭代后的x矩阵： [[ 0. 15.  3.  0.] [16.  0.  2.  0.] [ 0.  0.  0. 17.]]a: [0 0 2]b: [0 0 2 0]c: [[1000000000 1000000000 1000000000 1000000000] [1000000000 1000000000 1000000000 1000000000] [1000000000 1000000000         16 1000000000]]【迭代未完成】------------------------------------------------------------第6次迭代！第1次迭代！c: [[1000000000 1000000000 1000000000 1000000000] [1000000000 1000000000 1000000000 1000000000] [1000000000 1000000000         16 1000000000]]行罚数： [0, 0, 999999984]列罚数： [0, 0, 999999984, 0]罚数向量： [0, 0, 999999984, 0, 0, 999999984, 0]最大罚数： 999999984 元素序号： 3对第 3 行进行操作：[1000000000 1000000000         16 1000000000]最小成本所在列索引： 2本次迭代后的x矩阵： [[ 0. 15.  3.  0.] [16.  0.  2.  0.] [ 0.  0.  2. 17.]]a: [0 0 0]b: [0 0 0 0]c: [[1000000000 1000000000 1000000000 1000000000] [1000000000 1000000000 1000000000 1000000000] [1000000000 1000000000 1000000000 1000000000]]【迭代完成】------------------------------------------------------------>>>供求平衡<<>>初始基本可行解x*： [[ 0. 15.  3.  0.] [16.  0.  2.  0.] [ 0.  0.  2. 17.]]>>>当前总成本： 407.0进程已结束，退出代码为 0

上面使用的方法是表上作业法，属下所示：

最终最优的总成本： 407.0

2.3产大于销的运输问题

1.问题描述

有三个牧业基地向4个城市提供鲜奶，4个城市每日的鲜奶需求量、3个基地的每日鲜奶供应量以及运送每千升鲜奶的费用如下表所示，试确定最经济的鲜奶运输方案。

2.问题解析

总供应量=30+40+50=120

总需求量=16+30+24+30=100

供过于求，即产量大于销量，这是一个产大于销的运输问题。要将问题转化为产销平衡的运输问题，需进行以下几个方面的调整。

（1）增加一个虚拟销地E，使其总需求量为120-100=20。

（2）由于销地是虚拟的，实际上是产量过剩的物资在产地就地储存，所以不会产生实际的运输，即不会产生运费。

因此新的供需量及单位运价表如下所示。

3.问题求解

使用python来实现：

这里也可以使用（最小元素法）来解决:

'----------------------------------------最小元素法------------------------------------' \'最小元素法是指有限满足单位运价最小的供销服务'import numpy as npimport copysupplyNum = 3  # 供应商数量demandNum = 5  # 需求商数量A = np.array([30,40,50])  # 产量B = np.array([16,30,24,30,20])  # 销量C = np.array([[3,2,4,5,0], [2,3,5,3,0], [1,4,2,4,0]])  # 成本X = np.zeros((supplyNum, demandNum))  # 初始解c = copy.deepcopy(C)maxNumber = 10000  # 极大数def pivot(A, B, c, X):    index = np.where(c == np.min(c))  # 寻找最小值的索引    minIndex = (index[0][0], index[1][0])  # 确定最小值的索引    # 确定应该优先分配的量，并且改变价格    if A[index[0][0]] > B[index[1][0]]:        X[minIndex] = B[index[1][0]]        c[:, index[1][0]] = maxNumber  # 改变价格        A[index[0][0]] = A[index[0][0]] - B[index[1][0]]        B[index[1][0]] = 0  # 改变销量    else:        X[minIndex] = A[index[0][0]]        c[index[0][0], :] = maxNumber        B[index[1][0]] = B[index[1][0]] - A[index[0][0]]        A[index[0][0]] = 0    return A, B, c, X# 最小元素法def minimumElementMethod(A, B, c, X):    while (c < maxNumber).any():        A, B, c, X = pivot(A, B, c, X)    return XsolutionMin = minimumElementMethod(A, B, c, X)print('最小元素法得到的初始解为：')print(solutionMin)print('最小元素法得到的总运费为:', ((solutionMin * C).sum()))

输出结果：

最小元素法得到的初始解为：[[ 0. 10.  0.  0. 20.] [ 0. 20.  0. 20.  0.] [16.  0. 24. 10.  0.]]最小元素法得到的总运费为: 244.0

2.4 产小于销的运输问题

1.问题描述

某三个煤炭厂供应4个地区，假定等量的煤炭在这些地区使用效果相同，已知各煤炭厂年产量，各地区的需要量及从各煤炭厂到各地区的单位运价表如下所示，试决定最优的调运方案。

2.问题解析

总供应量=30+40+50=120

总需求量=16+30+24+30=100

供过于求，即产量大于销量，这是一个产大于销的运输问题。要将问题转化为产销平衡的运输问题，需进行以下几个方面的调整。

（1）增加一个虚拟销地E，使其总需求量为120-100=20。

（2）由于销地是虚拟的，实际上是产量过剩的物资在产地就地储存，所以不会产生实际的运输，即不会产生运费。

因此新的供需量及单位运价表如下所示。

3.问题求解

使用python求解：

这里可以使用（Vogel逼近法）寻找初始基本可行解

'-----------------------------------Vogel法---------------------------------'supplyNum = 4  # 供应商数量demandNum = 4  # 需求商数量A = np.array([90,40,70,20])  # 产量B = np.array([30,50,100,40])  # 销量C = np.array([[5,3,10,4], [2,6,9,6], [14,10,5,7],[0,0,0,0]])  # 成本X = np.zeros((supplyNum, demandNum))  # 初始解c = copy.deepcopy(C)numPunish = [0] * (supplyNum + demandNum)  # 整体罚数def pivot(X, A, B, C):    # 求解罚数，其中列罚数排在行罚数后面    for i in range(supplyNum):        sortList = np.sort(C[i, :])        numPunish[i] = sortList[1] - sortList[0]    for i in range(demandNum):        sortList = np.sort(C[:, i])        numPunish[i + supplyNum] = sortList[1] - sortList[0]    maxIndex = np.argmax(numPunish)  # 寻找最大罚数的索引    # 若最大的罚数属于行罚数    if maxIndex  B[minIndex]:            X[index] = B[minIndex]  # 更新解            C[:, minIndex] = maxNumber  # 将已经满足的一列中的运价增大替代删除操作            A[maxIndex] -= B[minIndex]  # 更新剩余产量            B[minIndex] = 0  # 更新已经满足的销量        # 若销量大于产量        else:            X[index] = A[maxIndex]            C[maxIndex, :] = maxNumber            B[minIndex] -= A[maxIndex]  # 更新销量            A[maxIndex] = 0    # 若最大的罚数为列罚数    else:        minIndex = np.argmin(C[:, maxIndex - supplyNum])  # 这时maxIndex-supplyNum是罚数最大的列        index = (minIndex, maxIndex - supplyNum)        if A[minIndex] > B[maxIndex - supplyNum]:  # 这里是产量大于销量，因此有限满足销量            X[index] = B[maxIndex - supplyNum]            C[:, maxIndex - supplyNum] = maxNumber            A[minIndex] -= B[maxIndex - supplyNum]            B[maxIndex - supplyNum] = 0        else:            X[index] = A[minIndex]            C[minIndex, :] = maxNumber            B[maxIndex - supplyNum] -= A[minIndex]            A[minIndex] = 0    return X, A, B, C# 沃格尔法得到初始解def Vogel(A, B, C):    X = np.zeros((supplyNum, demandNum))  # 初始解    numPunish = [0] * (supplyNum + demandNum)  # 整体罚数    # 迭代，直到所有的产量和销量全部满足    while (A != 0).any() and (B != 0).any():        X, A, B, C = pivot(X, A, B, C)    return X# 上面对于条件的判断，还需要对销量和需求量进行改变solutionVogel = Vogel(A, B, c)print('Vogel法得到的初始解为：')print(solutionVogel)print('Vogel法得到的总运费为:', (C * solutionVogel).sum())

输出结果：

Vogel法得到的初始解为：[[ 0. 50.  0. 40.] [30.  0. 10.  0.] [ 0.  0. 70.  0.] [ 0.  0. 20.  0.]]Vogel法得到的总运费为: 810.0

上面三种产销问题是常见的情况，除了产销问题还有弹性需求的运输问题、中间转运的运输问题。

这里就不罗嗦了，自己查资料噢！

3、指派问题

3.1 指派问题的数学模型

例 7 拟分配项工作，每人干且仅干一项工作，若分配第项工作，需花费 ， ，若分配工作，则取 = 0 。上述指派问题的数学模型为：

中的一个置换表示。

问题中的变量只能取 0 或 1，从而是一个 0-1 规划问题。一般的 0-1 规划问题求解 极为困难。但指派问题并不难解，其约束方程组的系数矩阵十分特殊（被称为全单位模矩阵，其各阶非零子式均为 ±1），其非负可行解的分量只能取 0 或 1，故约束 ≥ 0而不改变其解。此时，指派问题被转化为一个特殊的运输问题，其中 。

3.2 求解指派问题的匈牙利算法

算法主要依据以下事实：如果系数矩阵 ，则以C 或 B 为系数矩阵的 指派问题具有相同的最优指派。

例 8 求解指派问题，其系数矩阵为

再将第 3 列元素各减去 1，得

为系数矩阵的指派问题有最优指派

python实现：

from scipy.optimize import linear_sum_assignmentimport numpy as npcost = np.array([[12, 7, 9 ,7, 9],                  [8, 9, 6, 6, 6],                  [7, 17, 12, 14, 12],                 [15,14, 6 ,6, 10],                 [4,10 ,7 ,10 ,6]])row_ind, col_ind = linear_sum_assignment(cost)print('row_ind:', row_ind)  # 开销矩阵对应的行索引print('col_ind:', col_ind)  # 对应行索引的最优指派的列索引print('cost:', cost[row_ind, col_ind])  # 提取每个行索引的最优指派列索引所在的元素，形成数组print('cost_sum:', cost[row_ind, col_ind].sum())  # 最小开销

输出结果：

row_ind: [0 1 2 3 4]col_ind: [1 2 0 3 4]cost: [7 6 7 6 6]cost_sum: 32

4、对偶理论与灵敏度分析

4.1 原始问题和对偶问题

考虑下列一对线性规划模型：

（D）

称（P）为原始问题，（D）为它的对偶问题。

不太严谨地说，对偶问题可被看作是原始问题的“行列转置”：

（1） 原始问题中的第 j 列系数与其对偶问题中的第 j 行的系数相同；

（2） 原始目标函数的各个系数行与其对偶问题右侧的各常数列相同；

（3） 原始问题右侧的各常数列与其对偶目标函数的各个系数行相同；

（4） 在这一对问题中，不等式方向和优化方向相反。

考虑线性规划：

它的对偶问题是

和和，则上式又可写成

口诀：

不等号方向相同：Max变量的不等号与min约束条件的不等号方向相同

不等号方向相反：Max约束条件的不等号与min变量的不等号方向相反等号对应无约束:

约束条件的“=”对应变量“无约束”

例题1：

试求下列线性规划的对偶问题。

4.2 对偶问题的基本性质

原问题和对偶问题：

是原问题(max)的可行解，，证：

max问题： 右乘

(3)无界性
若原问题（对偶问题）为无界解，则其对偶问题(原问题）无可行解

(4）最优性
设是对偶问题的可行解，当是最优解

(5）对偶定理
若原问题有最优解，则对偶问题也有最优解，且日标函数值相等

(6）互补松弛性
设分别是其松弛变量的可行解，则和。试用对偶理论找出原问题的最优

解 先写出它的对偶问题

代入最优解

求解 由于 将

解

4.3 灵敏度分析

提出这样两个问题：当这些系数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化；或者这些系数在什么范围内变化时，线性规划问题的最优解或最优基不变。这里我们就不讨论了。

4.4 参数线性规划

参数线性规划是研究

（1）标准化

最优值：运筹说 第16期 | 线性规划硬核知识点梳理—单纯形法 – 知乎

4.4.2 对偶单纯形法：

例题：用对偶单纯形法求解LP：

将两个等式约束两边分别乘以-1，得

以此形式进行列表求解,满足对偶单纯形法的基本条件，具体如下：

=======原始表=======       x1  x2  x3  x4  x5  bx4     -1  -2  -1   1   0 -3x5     -2   1  -3   0   1 -4sigma  -2  -3  -4   0   0  0需要继续迭代！================================      x1    x2   x3 x4    x5   bx4     0  -5/2  1/2  1  -1/2  -1x1     1  -1/2  3/2  0  -1/2   2sigma  0    -4   -1  0    -1   4需要继续迭代！================================      x1 x2    x3    x4    x5     bx2     0  1  -1/5  -2/5   1/5   2/5x1     1  0   7/5  -1/5  -2/5  11/5sigma  0  0  -9/5  -8/5  -1/5  28/5迭代结束！

最优解：