current position:Home>Python solution of linear programming model

Python solution of linear programming model

2022-09-09 03:16:26The end of the world with you

1.线性规划

线性规划(Linear programming,简称LP),是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,是辅助人们进行科学管理的一种数学方法,It is a mathematical theory and method to study the extremum problem of linear objective function under linear constraints. 线性规划是运筹学的一个重要分支,广泛应用于军事作战、经济分析、经营管理和工程技术等方面.

The objective function and constraints of linear programming problems are both linear functions;约束条件记为 s.t.(即 subject to).目标函数可以是求最大值,也可以是求最小值,约束条件的不等号可以 是小于号也可以是大于号.

一般线性规划问题的(数学)标准型为 :

在这里插入图片描述

Common linear programming problems in mathematical modeling:

题目中提到“怎样安排/分配”“尽量多(少)”“最多(少)”“利润最大”“最合理”等词

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述


2.Python的解决方案

线性规划求解

在这里插入图片描述

案例代码:

''' Linear programming algorithm '''

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]}')

The program will output the final optimization result:

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]

vegetable growing problem

在这里插入图片描述

案例代码:

''' Linear programming algorithm,vegetable growing problem '''

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]]

copyright notice
author[The end of the world with you],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/252/202209090315386624.html

Random recommended