LP.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# LP Code"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 常见的解决LP问题的Python工具包\n",
    "\n",
    "- Scipy\n",
    "- PuLP"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 工具包介绍\n",
    "\n",
    "SciPy是一个开源的Python算法库和数学工具包。\n",
    "\n",
    "SciPy包含的模块有最优化、线性代数、积分、插值、特殊函数、快速傅里叶变换、信号处理和图像处理、常微分方程求解和其他科学与工程中常用的计算。\n",
    "\n",
    "PuLP是一个开源的线性规划包\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 使用方法\n",
    "\n",
    "\n",
    "### scipy\n",
    "![title](img/5.png)\n",
    "\n",
    "\n",
    "其中，\n",
    "\n",
    "- c为线性目标函数的系数\n",
    "- A_ub和b_ub对应线性不等式约束\n",
    "- A_eq和b_eq对应线性等式约束\n",
    "- bounds确定边界，如x≥0为（0，None）x无约束则为（None，None）\n",
    "- method是求解器的类型，'revised simplex’为修改的单纯形法\n",
    "\n",
    "要使用linprog,目标函数要变成求最小值，如果原题目要求求max（最大值），只需对目标函数取负，但要注意求解的最终值是取负后的目标函数的最小值，取负即为最大值\n",
    "\n",
    "![title](img/6.png)\n",
    "\n",
    "![title](img/7.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### PuLP\n",
    "\n",
    "- 导入库函数\n",
    "\n",
    "```\n",
    "from pulp import *\n",
    "```\n",
    "\n",
    "- 定义线性规划问题\n",
    "\n",
    "```\n",
    "PB = LpProblem(problem name, sense)\n",
    "```\n",
    "\n",
    "构造一个LP问题实例，其实name指定问题名，sense指是LpMaximize, LpMinimize 中的一个，用来指定目标函数是求最大值还是最小值\n",
    "\n",
    "- 定义决策变量\n",
    "\n",
    "```\n",
    "DV = LpVariable(decision variable name, lowbound, upbound, category)\n",
    "\n",
    "```\n",
    "\n",
    "decision variable name 用来指定变量名，lowbound 和 upbound是下界和上界，默认分别是负无穷和正无穷，category用来指定变量是离散还是连续\n",
    "\n",
    "- 添加目标函数\n",
    "\n",
    "```\n",
    "PB += linear object from object name\n",
    "```\n",
    "\n",
    "- 添加约束条件\n",
    "\n",
    "```\n",
    "PB += linear object from constraint name \n",
    "```\n",
    "\n",
    "- 简单举例\n",
    "\n",
    "```\n",
    "x = LpVariable(\"x\", 0, 3)\n",
    "y = LpVariable(\"y\", 0, 1)\n",
    "prob = LpProblem(\"myProblem\", LpMinimize)\n",
    "prob += x + y <= 2\n",
    "prob += -4*x + y\n",
    "```\n",
    "\n",
    "- 写入LP文件\n",
    "\n",
    "```\n",
    "PB.writeLP(filename)\n",
    "```\n",
    "\n",
    "- 模型求解\n",
    "\n",
    "```\n",
    "PB.solver()\n",
    "```\n",
    "\n",
    "可以是用不同的solver\n",
    "\n",
    "- 结果显示\n",
    "\n",
    "```\n",
    "LpStatus(PB.status)\n",
    "```\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 采购问题\n",
    "\n",
    "原题目：\n",
    "有2000元经费，需要采购单价为50元的若干桌子和单价为20元的若干椅子，你希望桌椅的总数尽可能的多，\n",
    "\n",
    "但要求椅子数量不少于桌子数量，且不多于桌子数量的1.5倍，那你需要怎样的一个采购方案呢？\n",
    "\n",
    "解：要采购x1张桌子，x2把椅子\n",
    "```\n",
    "max z= x1 + x2\n",
    "s.t. x1 - x2 <= 0\n",
    "1.5x1 >= x2\n",
    "50x1 + 20x2 <= 2000\n",
    "x1, x2 >=0\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "求解第一步，转换成标准形式\n",
    "\n",
    "```\n",
    "min  -x1 - x2\n",
    "s.t. x1 - x2 <= 0\n",
    "-1.5x1 + x2 <= 0\n",
    "50x1 + 20x2 <= 2000\n",
    "x1, x2 >=0\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Scipy solver"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "在python中此类线性规划问题可用lp solver解决\n",
    "scipy.optimize._linprog def linprog(c: int,\n",
    "            A_ub: Optional[int] = None,\n",
    "            b_ub: Optional[int] = None,\n",
    "            A_eq: Optional[int] = None,\n",
    "            b_eq: Optional[int] = None,\n",
    "            bounds: Optional[Iterable] = None,\n",
    "            method: Optional[str] = 'simplex',\n",
    "            callback: Optional[Callable] = None,\n",
    "            options: Optional[dict] = None) -> OptimizeResult\n",
    "\n",
    "矩阵A：就是约束条件的系数（等号左边的系数）\n",
    "矩阵B：就是约束条件的值（等号右边）\n",
    "矩阵C：目标函数的系数值\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "     con: array([], dtype=float64)\n",
      "     fun: -62.5\n",
      " message: 'Optimization terminated successfully.'\n",
      "     nit: 3\n",
      "   slack: array([12.5,  0. ,  0. ])\n",
      "  status: 0\n",
      " success: True\n",
      "       x: array([25. , 37.5])\n"
     ]
    }
   ],
   "source": [
    "from scipy import  optimize as opt\n",
    "import numpy as np\n",
    "#参数\n",
    "#c是目标函数里变量的系数\n",
    "c=np.array([1,1])\n",
    "#a是不等式条件的变量系数\n",
    "a=np.array([[1,-1],[-1.5,1],[50,20]])\n",
    "#b是是不等式条件的常数项\n",
    "b=np.array([0,0,2000])\n",
    "#a1，b1是等式条件的变量系数和常数项，这个例子里无等式条件,不要这两项\n",
    "#a1=np.array([[1,1,1]])\n",
    "#b1=np.array([7])\n",
    "#限制\n",
    "lim1=(0,None) #(0,None)->(0,+无穷)\n",
    "lim2=(0,None)\n",
    "#调用函数\n",
    "ans=opt.linprog(-c,a,b,bounds=(lim1,lim2),method='revised simplex')\n",
    "#输出结果\n",
    "print(ans)\n",
    "\n",
    "#注意：我们这里的应用问题，椅子不能是0.5把，所以最后应该采购37把椅子\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Pulp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/supinyu/anaconda3/lib/python3.7/site-packages/pulp/pulp.py:1199: UserWarning: Spaces are not permitted in the name. Converted to '_'\n",
      "  warnings.warn(\"Spaces are not permitted in the name. Converted to '_'\")\n"
     ]
    }
   ],
   "source": [
    "from pulp import *\n",
    "PB = LpProblem(\"Shopping Problem\", LpMinimize)\n",
    "x1 = LpVariable(\"x1\", lowBound=0, cat=LpInteger)\n",
    "x2 = LpVariable(\"x2\", lowBound=0, cat=LpInteger)\n",
    "PB += x1 - x2 <= 0\n",
    "PB += -1.5 * x1 + x2 <= 0\n",
    "PB += 50 * x1 + 20* x2 <= 2000\n",
    "PB += -x1 - x2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Shopping_Problem:\n",
       "MINIMIZE\n",
       "-1*x1 + -1*x2 + 0\n",
       "SUBJECT TO\n",
       "_C1: x1 - x2 <= 0\n",
       "\n",
       "_C2: - 1.5 x1 + x2 <= 0\n",
       "\n",
       "_C3: 50 x1 + 20 x2 <= 2000\n",
       "\n",
       "VARIABLES\n",
       "0 <= x1 Integer\n",
       "0 <= x2 Integer"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "PB"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "status = PB.solve()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Optimal'"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "LpStatus[status]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "25.0"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "value(x1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "37.0"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "value(x2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x1 = 25.0\n",
      "x2 = 37.0\n",
      "-62.0\n"
     ]
    }
   ],
   "source": [
    "for variable in PB.variables():\n",
    "    print(\"{} = {}\".format(variable.name, variable.varValue))\n",
    "\n",
    "print(value(PB.objective))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 最大流问题"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![title](img/8.png)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "如图，假设有四个城市，s，u，v，t。\n",
    "连线表示，城市之间有道路。连线上的数字表示这条道路每天最多能够运送货物的吨数。\n",
    "\n",
    "比如，城市 s，u 之间有条路，这条路每天最多运 5 吨货物。\n",
    "如果你是调度员，请设计一个调度方案，\n",
    "使得从 s 到 t 一天之内能够运送的货物越多越好。\n",
    "\n",
    "现在我们形式化这个问题，将 5 条路的运输量分别为 x1，x2，x3，x4，x5。\n",
    "然后写出约束条件和目标函数\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```\n",
    "max x1 + x2\n",
    "s.t. x1 - x3 - x4 = 0  node U\n",
    "x2 + x3 - x5 = 0  node V\n",
    "5 ≥ x1 ≥ 0\n",
    "8 ≥ x2 ≥ 0\n",
    "1 ≥ x3 ≥ 0\n",
    "6 ≥ x4 ≥ 0\n",
    "2 ≥ x5 ≥ 0\n",
    "```\n",
    "因为 u，v 是中间节点，所以必须满足运入 u，v 的货物必须在当天运\n",
    "出。\n",
    "\n",
    "另外要满足每条路的运输量不超过其最大运量。我们的目标是要从 s 运出的货\n",
    "物越多越好。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### scipy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "     con: array([0., 0.])\n",
      "     fun: -7.0\n",
      " message: 'Optimization terminated successfully.'\n",
      "     nit: 4\n",
      "   slack: array([], dtype=float64)\n",
      "  status: 0\n",
      " success: True\n",
      "       x: array([5., 2., 0., 5., 2.])\n"
     ]
    }
   ],
   "source": [
    "from scipy import  optimize as opt\n",
    "import numpy as np\n",
    "#参数\n",
    "#c是目标函数里变量的系数\n",
    "c=np.array([1,1,0,0,0])\n",
    "#a是不等式条件的变量系数\n",
    "a=np.array([[1,0,-1,-1,0],[0,1,1,0,-1]])\n",
    "#b是是不等式条件的常数项\n",
    "b=np.array([0,0])\n",
    "#限制\n",
    "lim1 = (0,5) #(0,None)->(0,+无穷)\n",
    "lim2 = (0,8)\n",
    "lim3 = (0,1)\n",
    "lim4 = (0,6)\n",
    "lim5 = (0,2)\n",
    "#调用函数\n",
    "ans=opt.linprog(c = -c, A_eq = a, b_eq=b, bounds = [lim1,lim2,lim3,lim4,lim5], method='revised simplex')\n",
    "#输出结果\n",
    "print(ans)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Pulp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stderr",
     "output_type": "stream",
     "text": [
      "/Users/supinyu/anaconda3/lib/python3.7/site-packages/pulp/pulp.py:1199: UserWarning: Spaces are not permitted in the name. Converted to '_'\n",
      "  warnings.warn(\"Spaces are not permitted in the name. Converted to '_'\")\n"
     ]
    }
   ],
   "source": [
    "from pulp import *\n",
    "PB = LpProblem(\"Max Flow Problem\", LpMinimize)\n",
    "x1 = LpVariable(\"x1\", lowBound=0, upBound=5, cat=LpContinuous)\n",
    "x2 = LpVariable(\"x2\", lowBound=0, upBound=8, cat=LpContinuous)\n",
    "x3 = LpVariable(\"x3\", lowBound=0, upBound=1, cat=LpContinuous)\n",
    "x4 = LpVariable(\"x4\", lowBound=0, upBound=6, cat=LpContinuous)\n",
    "x5 = LpVariable(\"x5\", lowBound=0, upBound=2, cat=LpContinuous)\n",
    "PB += x1 - x3 - x4 <= 0\n",
    "PB += -x1 + x3 + x4 <= 0\n",
    "PB += x2 + x3 - x5 <= 0\n",
    "PB += -x2 - x3 + x5 <= 0\n",
    "PB += -x1 - x2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "Max_Flow_Problem:\n",
       "MINIMIZE\n",
       "-1*x1 + -1*x2 + 0\n",
       "SUBJECT TO\n",
       "_C1: x1 - x3 - x4 <= 0\n",
       "\n",
       "_C2: - x1 + x3 + x4 <= 0\n",
       "\n",
       "_C3: x2 + x3 - x5 <= 0\n",
       "\n",
       "_C4: - x2 - x3 + x5 <= 0\n",
       "\n",
       "VARIABLES\n",
       "x1 <= 5 Continuous\n",
       "x2 <= 8 Continuous\n",
       "x3 <= 1 Continuous\n",
       "x4 <= 6 Continuous\n",
       "x5 <= 2 Continuous"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "PB"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "status = PB.solve()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'Optimal'"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "LpStatus[status]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "x1 = 5.0\n",
      "x2 = 2.0\n",
      "x3 = 0.0\n",
      "x4 = 5.0\n",
      "x5 = 2.0\n",
      "-7.0\n"
     ]
    }
   ],
   "source": [
    "for variable in PB.variables():\n",
    "    print(\"{} = {}\".format(variable.name, variable.varValue))\n",
    "\n",
    "print(value(PB.objective))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 参考资料\n",
    "\n",
    "- https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linprog.html\n",
    "\n",
    "- https://www.hrwhisper.me/introduction-to-simplex-algorithm/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}