我是猿童学，本文是根据司守奎老师《数学建模算法与程序》的书本内容编写，使用其书中案例，书中的编程语言是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四个销地提供产品，产量、需求量及工厂到销售地的运价（单位：元/吨）如下表所示，求使费用最少的最佳运输方案。
| 工厂 \ 销地 | A | B | C | D | 产量（吨） |
| 甲 | 8 | 6 | 10 | 9 | 18 |
| 乙 | 9 | 12 | 13 | 1 | 18 |
| 丙 | 14 | 12 | 16 | 5 | 19 |
| 销量（吨） | 16 | 15 | 7 | 17 | 55 |
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个基地的每日鲜奶供应量以及运送每千升鲜奶的费用如下表所示，试确定最经济的鲜奶运输方案。
| 城市\基地 | A | B | c | D | 供应量 |
| 甲 | 3 | 2 | 4 | 5 | 30 |
| 乙 | 2 | 3 | 5 | 3 | 40 |
| 丙 | 1 | 4 | 2 | 4 | 50 |
| 需求量 | 16 | 30 | 24 | 30 |
2.问题解析
总供应量=30+40+50=120
总需求量=16+30+24+30=100
供过于求，即产量大于销量，这是一个产大于销的运输问题。要将问题转化为产销平衡的运输问题，需进行以下几个方面的调整。
（1）增加一个虚拟销地E，使其总需求量为120-100=20。
（2）由于销地是虚拟的，实际上是产量过剩的物资在产地就地储存，所以不会产生实际的运输，即不会产生运费。
因此新的供需量及单位运价表如下所示。
| 城市\基地 | A | B | c | D | E | 供应量 |
| 甲 | 3 | 2 | 4 | 5 | 0 | 30 |
| 乙 | 2 | 3 | 5 | 3 | 0 | 40 |
| 丙 | 1 | 4 | 2 | 4 | 0 | 50 |
| 需求量 | 16 | 30 | 24 | 30 | 20 | 120 |
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.02.4 产小于销的运输问题
1.问题描述
某三个煤炭厂供应4个地区，假定等量的煤炭在这些地区使用效果相同，已知各煤炭厂年产量，各地区的需要量及从各煤炭厂到各地区的单位运价表如下所示，试决定最优的调运方案。
| 销地\产地 | B1 | B2 | B3 | B4 | 产量 |
| A1 | 5 | 3 | 10 | 4 | 90 |
| A2 | 2 | 6 | 9 | 6 | 40 |
| A3 | 14 | 10 | 5 | 7 | 70 |
| 销量 | 30 | 50 | 100 | 40 |
2.问题解析
总供应量=30+40+50=120
总需求量=16+30+24+30=100
供过于求，即产量大于销量，这是一个产大于销的运输问题。要将问题转化为产销平衡的运输问题，需进行以下几个方面的调整。
（1）增加一个虚拟销地E，使其总需求量为120-100=20。
（2）由于销地是虚拟的，实际上是产量过剩的物资在产地就地储存，所以不会产生实际的运输，即不会产生运费。
因此新的供需量及单位运价表如下所示。
| 销地\产地 | B | B | B3 | B4 | 产量 |
| A, | 5 | 3 | 10 | 4 | 90 |
| A2 | 2 | 6 | 9 | 6 | 40 |
| A3 | 14 | 10 | 5 | 7 | 70 |
| A4 | 0 | 0 | 0 | 0 | 20 |
| 销量 | 30 | 50 | 100 | 40 | 220 |
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: 324、对偶理论与灵敏度分析
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迭代结束！最优解：