线性规划模型的Python解法

世界尽头与你 2022-09-09 03:15:55 阅读数:376

Python线性规划模型规划线性

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]]
版权声明:本文为[世界尽头与你]所创,转载请带上原文链接,感谢。 https://blog.csdn.net/Gherbirthday0916/article/details/126771376