example_1.md 9.28 KB

【LP专题-1】你已经会用运筹学-线性规划

使用过程提示

Tips:

  • 您可点击右下角“下一步”,查看后续的建模讲解。
  • 本教程文档是 .md 格式,此讲解窗口采用阿里云 CloudShell 的teachme指令打开,如命令行输入 teachme doc/fileName.md 命令打开。

^___^ 还没体验过安装和运行求解器的同学,可以直接点击链接:一键安装MindOpt求解器,并一键用令行求解.mps或.lp文件~~

1. 线性规划简介

线性问题是运筹学中最简单的一类问题,线性规划是在实际生活中应用最广泛的运筹知识。我们每个人都可能用线性规划的方法,思考过线性问题,只是我们不知道这些问题就是数学上说的“线性问题”,不知道自己原来已经会用“线性规划”的方法来解决问题。

线性规划里的“线性”,指的是现实中最常见的事物之间“成比例对应”的关系。简单说就是“结果 = 系数*变量”(y=cx)。用坐标系画出来的图形会是一条线,如图1。如我们在抖音刷到的家长群不懂孩子老师说“一元一次”方程/函数、误以为一次要收一元钱的段子,这里的“一元一次”讲的就是这个“线性”关系。

实际例子,比如,小球在路面上直线匀速行驶,那么它走的路程和时间就是个线性的关系,同见图1;如果小球从楼上掉下来,受到地球重力加速度的影响,它走的路程就是和时间是个“二次”关系,见图2,不是成“线性”比例的。当然我们直线也可以线性正向上升的,也可以线性负向下降的,比如计算小车距离终点的距离,就是随着时间越来越小,如图3。

image.png

刚才的小球例子是单个变量(时间)的线性问题,现实生活中会更复杂,往往会有多个变量的线性关系交织在一起,并且受到了现实条件的制约,因此需要我们能找到这些变量的最优的一个或者多个方案,优秀的方案的目标是希望在制约条件下能实现效益大、损耗小等。这就是线性规划,简单说,线性规划的“线性”意味着问题包含的是线性关系,“规划”是指寻找问题的最优解决方案。

“求解器”是计算出这个最优方案的工具。可广泛应用于云计算、零售、金融、制造、交通、能源等领域,是深埋于智能决策场景底层的“终极利器”、“降本增效”的好工具。

2. 求解线性规划问题(案例建模)

为了更好地使用求解器工具,我们可以把线性规划的问题输入求解器的信息转换为:目标、变量、约束。

举个例子,如一个运筹学课程题目: 问题背景: 一个农民承包了6块耕地,共300亩,准备播种小麦、玉米、蔬菜、瓜果这4种农产品。每个地块由于土质地形不一样,单位面积不同作物的收益是不一样的,且地块的面积不一样,如下表所示。请问要如何安排种植计划,可以得到最大的总收益。

表1:单位面积不同收益(收益Cij)

地块1 地块2 地块3 地块4 地块5 地块6
小麦 500 550 630 1000 800 700
玉米 800 700 600 950 90 930
蔬菜 1200 1040 980 860 880 780
瓜果 1000 960 840 650 600 700

表2:地块面积和计划播种面积限制

地块1 地块2 地块3 地块4 地块5 地块6 计划播种面积上限
地块面积 42 56 44 39 60 59
小麦 76
玉米 88
蔬菜 40
瓜果 96

目标:

最大化总收益。

变量:

要安排种植计划,我们这里把每个地块上种不同作物的面积设个未知数,用 Xij代替。

约束:

由于地块面积不同有限制,计划播种面积也有不同,因此根据未知数可以列出不同未知数的加和是有限制的。 这样,变量和约束就如下表所示。

表3 地块面积 Xij 和约束

地块1 地块2 地块3 地块4 地块5 地块6 播种计划约束
小麦 X11 X12 X13 X14 X15 X16 X11+X12+...+X16≤76
玉米 X21 X22 X23 X24 X25 X26 X21+X22+...+X26≤88
蔬菜 X31 X32 X33 X34 X35 X36 X31+X32+...+X36≤40
瓜果 X41 X42 X43 X44 X45 X46 X31+X32+...+X36≤96
地块面积约束 X11+X21+X31+X41≤42 X12+X22+X32+X42≤56 X13+X23+X33+X43≤44 X14+X24+X34+X44≤39 X15+X25+X35+X45≤60 X16+X26+X36+X46≤59

目标的计算公式:

此时,我们就可以把目标定为:求 f(X) = sumproduct(收益Cij*面积Xij) 的最大值,即每个小作物地块对应收益总和的最大值:

f(X)=[C11*X11+C12*X12+...+C16*X26]+[C21*X21+C22*X22+...+C26*X26]+...+[C41*X41+C42*X42+...+C46*X46]

=[500*X11+550*X12+...+700*X26]+[800*X21+700*X22+...+930*X26]+...+[1000*X41+960*X42+...+700*X46]

即,求解Xij取值等于多少,可得到f(X)的值最大。

求解和应用

有了目标、变量、约束后,就可以输入到求解器里面进行优化求解,然后得到变量(Xij)的取值和对应的优化目标值(f)。Xij的取值即可用于实施方案的决策

具体的使用求解器的示例代码,大家可查看其他的案例教程中的说明,包含 C、C++、Python版本。学会了后可以拿本案例的问题练练手哟。

Tips:案例内容可能参考自互联网,如有侵权,请联系我们删除。

快捷查看案例:

以下的案例讲述了几个案例中的问题分析思路、示例代码。可点击下面list的标题链接打开(CloudShell默认是同时开控制台页面上限是5),或者点击下方示例指令框右上角的运行图标,复制指令到控制台命令行,然后按enter。 更多新案例均在 天池实验室 中更新,并卡片形式简述显示,可快捷查看内容或体验。

在安装方案后有提供指令。可采用该方法上传自己的mps或者lp文件进行求解,上传文件可用CloudShell左上角的按钮,或者git clone、wget等方式。

teachme doc/introcuction.md 

简介:内含 C、C++、Python 三种编程语言、多种建模输入方式、.mps或.lp文件输入方式,总共 12 份代码。

teachme doc/example_2.md 

简介:内含 1 份 Python 代码。

teachme doc/example_3.md 

简介:内含 1 份 C 代码(提交问题和获取结果分开)。

teachme doc/example_4.md 

简介:内含 C++ 、Python 代码,总共 2 份代码。

teachme doc/example_5.md 

简介:内含 1 份 Python 预处理数据、 1 份求解器 Python 代码(提交问题和获取结果分开)。

teachme doc/example_6.md