1.线性规划

线性规划（Linear programming,简称LP），是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支，是辅助人们进行科学管理的一种数学方法，是研究线性约束条件下线性目标函数的极值问题的数学理论和方法。 线性规划是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。

线性规划问题的目标函数及约束条件均为线性函数；约束条件记为 s.t.(即 subject to)。目标函数可以是求最大值，也可以是求最小值，约束条件的不等号可以 是小于号也可以是大于号。

一般线性规划问题的（数学）标准型为 ：

数学建模中常见的线性规划类赛题：

题目中提到“怎样安排/分配”“尽量多（少）”“最多（少）”“利润最大”“最合理”等词，例如：

---

2.Python的解决方案

线性规划求解

例如：某数学题：

案例代码：

'''
线性规划算法
'''

import pulp as pp

# 目标函数的系数
z = [2, 3, 1]
a = [[1, 4, 2], [3, 2, 0]]
b = [8, 6]
aeq = [[1, 2, 4]]
beq = [101]

# 确定最大最小化问题，当前确定的是最大化问题
m = pp.LpProblem(sense=pp.LpMaximize)

# 定义三个变量放到列表中
x = [pp.LpVariable(f'x{
      i}', lowBound=0) for i in [1, 2, 3]]

# 定义目标函数，并将目标函数加入求解的问题中
m += pp.lpDot(z, x)  # lpDot 用于计算点积

# 设置比较条件
for i in range(len(a)):
    m += (pp.lpDot(a[i], x) >= b[i])

# 设置相等条件
for i in range(len(aeq)):
    m += (pp.lpDot(aeq[i], x) == beq[i])

# 求解
m.solve()
# 输出结果
print(f'优化结果：{
      pp.value(m.objective)}')
print(f'参数取值：{
      [pp.value(var) for var in x]}')

程序会输出最终的优化结果：

Welcome to the CBC MILP Solver 
Version: 2.10.3 
Build Date: Dec 15 2019 

command line - D:\CodeBox\enpython\lib\site-packages\pulp\apis\..\solverdir\cbc\win\64\cbc.exe D:\ϵͳ��Դ\ϵͳ����\b98f86280e894d38805560900a38bbfe-pulp.mps max timeMode elapsed branch printingOptions all solution D:\ϵͳ��Դ\ϵͳ����\b98f86280e894d38805560900a38bbfe-pulp.sol (default strategy 1)
At line 2 NAME          MODEL
At line 3 ROWS
At line 8 COLUMNS
At line 20 RHS
At line 24 BOUNDS
At line 25 ENDATA
Problem MODEL has 3 rows, 3 columns and 8 elements
Coin0008I MODEL read with 0 errors
Option for timeMode changed from cpu to elapsed
Presolve 3 (0) rows, 3 (0) columns and 8 (0) elements
0  Obj -0 Primal inf 29.25 (3) Dual inf 5.9999997 (3)
0  Obj -0 Primal inf 29.25 (3) Dual inf 5.1666667e+10 (3)
2  Obj 202
Optimal - objective value 202
Optimal objective 202 - 2 iterations time 0.002
Option for printingOptions changed from normal to all
Total time (CPU seconds):       0.01   (Wallclock seconds):       0.01

优化结果：202.0
参数取值：[101.0, 0.0, 0.0]

种菜问题

某数学题目：

案例代码：

'''
线性规划算法，种菜问题
'''

import pulp
import numpy as np
from pprint import pprint


def transportation_problem(costs, x_max, y_max):
    row = len(costs)
    col = len(costs[0])
    prob = pulp.LpProblem('Transportation Proble', sense=pulp.LpMaximize)
    var = [[pulp.LpVariable(f'x{
      i}{
      j}', lowBound=0, cat=pulp.LpInteger) for j in range(col)] for i in range(row)]
    # 转为一维
    flatten = lambda x: [y for l in x for y in flatten(l)] if type(x) is list else [x]
    prob += pulp.lpDot(flatten(var), costs.flatten())
    for i in range(row):
        prob += (pulp.lpSum(var[i]) <= x_max[i])
    for j in range(col):
        prob += (pulp.lpSum([var[i][j] for i in range(row)]) <= y_max[j])
    prob.solve()
    return {
    'objective': pulp.value(prob.objective),
            'var': [[pulp.value(var[i][j]) for j in range(col)] for i in range(row)]}


costs = np.array([[500, 550, 630, 1000, 800, 700],
                  [800, 700, 600, 950, 900, 930],
                  [1000, 960, 840, 650, 600, 700],
                  [1200, 1040, 980, 860, 880, 780]])
max_plant = [76, 88, 96, 40]
max_cultivation = [42, 56, 44, 39, 60, 59]
res = transportation_problem(costs, max_plant, max_cultivation)
print(f'最大值为{
      res["objective"]}')
print("各个变量的取值为：")
pprint(res['var'])

结果数据：

最大值为284230.0
各个变量的取值为：
[[0.0, 0.0, 6.0, 39.0, 31.0, 0.0],
 [0.0, 0.0, 0.0, 0.0, 29.0, 59.0],
 [2.0, 56.0, 38.0, 0.0, 0.0, 0.0],
 [40.0, 0.0, 0.0, 0.0, 0.0, 0.0]]