{ "cells": [ { "cell_type": "markdown", "metadata": { "nbpages": { "level": 0, "link": "[](https://jckantor.github.io/CBE30338/06.03-Linear-Programming.html)", "section": "" } }, "source": [ "\n", "*This notebook contains material from [CBE30338](https://jckantor.github.io/CBE30338);\n", "content is available [on Github](https://github.com/jckantor/CBE30338.git).*\n" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 0, "link": "[](https://jckantor.github.io/CBE30338/06.03-Linear-Programming.html)", "section": "" } }, "source": [ "\n", "< [6.2 Linear Production Model](https://jckantor.github.io/CBE30338/06.02-Linear-Production-Model.html) | [Contents](toc.html) | [Tag Index](tag_index.html) | [6.4 Linear Production Model in Pyomo](https://jckantor.github.io/CBE30338/06.04-Linear-Production-Model-in-Pyomo.html) >

\"Open

\"Download\"" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 1, "link": "[6.3 Linear Programming](https://jckantor.github.io/CBE30338/06.03-Linear-Programming.html#6.3-Linear-Programming)", "section": "6.3 Linear Programming" } }, "source": [ "# 6.3 Linear Programming\n", "\n", "Linear programming is the minimization (or maximization) of a linear objective subject to linear constraints. There are several widely adopted schemes for representing linear programming problems. Here we adopt a scheme corresponding where the linear objective is written in terms of decision variables $x_1, x_2, \\ldots, x_N$ as\n", "\n", "\\begin{align}\n", "\\min_{x_1, x_1, \\ldots, x_N} c_1x_1 + c_2x_2 + \\cdots + c_Nx_N\n", "\\end{align}\n", "\n", "subject to\n", "\n", "\\begin{align}\n", "x_i \\geq 0 & \\qquad i=1,\\ldots,N\\quad\\mbox{lower bounds on decision variables}\\\\\n", "\\sum_{j=1}^N a^{ub}_{ij}x_j \\leq b^{ub}_i & \\qquad i=1,\\ldots,M_{ub}\\quad\\mbox{upper bound constraints} \\\\\n", "\\sum_{j=1}^N a^{eq}_{ij}x_j = b^{eq}_i & \\qquad i=1,\\ldots,M_{eq}\\quad\\mbox{equality constraints}\\\\\n", "\\end{align}" ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 2, "link": "[6.3.1 Matrix/Vector format](https://jckantor.github.io/CBE30338/06.03-Linear-Programming.html#6.3.1-Matrix/Vector-format)", "section": "6.3.1 Matrix/Vector format" } }, "source": [ "## 6.3.1 Matrix/Vector format\n", "\n", "The notation can be simplified by adopting a matrix/vector formulation where\n", "\n", "\\begin{align}\n", "\\min_{x\\geq 0} c^T x\n", "\\end{align}\n", "\n", "subject to\n", "\n", "\\begin{align}\n", "A_{ub} x \\leq b_{ub} \\\\\n", "A_{eq} x = b_{eq}\n", "\\end{align}\n", "\n", "where $c$, $A_{ub}, b_{ub}$, and $A_{eq}, b_{eq}$, are vectors and matrices of coefficients constructed from the linear expressions given above." ] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 2, "link": "[6.3.2 Example 19.3: Refinery Blending Problem](https://jckantor.github.io/CBE30338/06.03-Linear-Programming.html#6.3.2-Example-19.3:-Refinery-Blending-Problem)", "section": "6.3.2 Example 19.3: Refinery Blending Problem" } }, "source": [ "## 6.3.2 Example 19.3: Refinery Blending Problem\n", "\n", "The decision variables are\n", "\n", "\n", "| Variable | Description | Units |\n", "| ---------|-------------| ------|\n", "| $x_1$ | crude #1 | bbl/day |\n", "| $x_2$ | crude #2 | bbl/day |\n", "| $x_3$ | gasoline | bbl/day |\n", "| $x_4$ | kerosine | bbl/day |\n", "| $x_5$ | fuel oil | bbl/day |\n", "| $x_6$ | residual | bbl/day |\n", "\n", "\n", "The overall objective is to maximize profit\n", "\n", "\\begin{align}\n", "\\mbox{profit} & = \\mbox{income} - \\mbox{raw_material_cost} - \\mbox{processing_cost}\n", "\\end{align}\n", "\n", "where the financial components are given by\n", "\n", "\\begin{align}\n", "\\mbox{income} & = 72x_3 + 48x_4 + 42x_5 + 20x_6 \\\\\n", "\\mbox{raw_material_cost} & = 48x_1 + 30x_2 \\\\\n", "\\mbox{processing_cost} & = 1 x_1 + 2x_2\n", "\\end{align}\n", "\n", "Combining these terms, the objective is to maximize\n", "\n", "\\begin{align}\n", "f & = c^T x = - 49 x_1 - 32 x_2 + 72 x_3 + 48x_4 + 42x_5 + 20x_6 \n", "\\end{align}\n", "\n", "The material balance equations are\n", "\n", "\\begin{align}\n", "\\mbox{gasoline: } x_3 & = 0.80 x_1 + 0.44 x_2 \\\\\n", "\\mbox{kerosine: } x_4 & = 0.05 x_1 + 0.10 x_2 \\\\\n", "\\mbox{fuel oil: } x_5 & = 0.10 x_1 + 0.36 x_2 \\\\\n", "\\mbox{residual: } x_6 & = 0.05 x_1 + 0.10 x_2\n", "\\end{align}\n", "\n", "Production limits\n", "\n", "\\begin{align}\n", "\\mbox{gasoline: } x_3 & \\leq 24,000 \\\\\n", "\\mbox{kerosine: } x_4 & \\leq 2,000 \\\\\n", "\\mbox{fuel oil: } x_5 & \\leq 6,000\n", "\\end{align}\n", "\n", "\\begin{align}\n", "\\underbrace{\\left[\\begin{array}{cccccc}\n", "0.80 & 0.44 & -1 & 0 & 0 & 0 \\\\\n", "0.05 & 0.10 & 0 & -1 & 0 & 0 \\\\\n", "0.10 & 0.36 & 0 & 0 & -1 & 0 \\\\\n", "0.05 & 0.10 & 0 & 0 & 0 & -1\n", "\\end{array}\\right]}_{A_{eq}}\n", "\\left[\\begin{array}{c}\n", "x_1 \\\\ x_2 \\\\ x_3 \\\\ x_4 \\\\ x_5 \\\\ x_6 \n", "\\end{array}\\right]\n", "& = \n", "\\underbrace{\\left[\\begin{array}{c}\n", "0 \\\\ 0 \\\\ 0 \\\\ 0\n", "\\end{array}\\right]}_{b_{eq}}\n", "\\end{align}" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "nbpages": { "level": 2, "link": "[6.3.2 Example 19.3: Refinery Blending Problem](https://jckantor.github.io/CBE30338/06.03-Linear-Programming.html#6.3.2-Example-19.3:-Refinery-Blending-Problem)", "section": "6.3.2 Example 19.3: Refinery Blending Problem" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "additional profit 175.035862069\n" ] } ], "source": [ "from scipy.optimize import linprog\n", "\n", "c = [49, 32, -72, -48, -42, -20]\n", "\n", "A_ub = [[0, 0, 1, 0, 0, 0],\n", " [0, 0, 0, 1, 0, 0],\n", " [0, 0, 0, 0, 1, 0]]\n", "\n", "b_ub = [24000, 2001, 6000]\n", "\n", "A_eq = [[0.80, 0.44, -1, 0, 0, 0],\n", " [0.05, 0.10, 0, -1, 0, 0],\n", " [0.10, 0.36, 0, 0, -1, 0],\n", " [0.05, 0.10, 0, 0, 0, -1]]\n", "\n", "b_eq = [0, 0, 0, 0]\n", "\n", "results = linprog(c, A_ub, b_ub, A_eq, b_eq)\n", "results\n", "p0 = 573517.24\n", "print('additional profit', -results.fun - p0)" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "nbpages": { "level": 2, "link": "[6.3.2 Example 19.3: Refinery Blending Problem](https://jckantor.github.io/CBE30338/06.03-Linear-Programming.html#6.3.2-Example-19.3:-Refinery-Blending-Problem)", "section": "6.3.2 Example 19.3: Refinery Blending Problem" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Optimization terminated successfully.\n", "x[ 1] = 26199.3 bbl/day\n", "x[ 2] = 6910.3 bbl/day\n", "x[ 3] = 24000.0 bbl/day\n", "x[ 4] = 2001.0 bbl/day\n", "x[ 5] = 5107.7 bbl/day\n", "x[ 6] = 2001.0 bbl/day\n" ] } ], "source": [ "print(results.message)\n", "if results.success:\n", " for k in range(len(results.x)):\n", " print('x[{0:2d}] = {1:7.1f} bbl/day'.format(k+1, results.x[k]))" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "nbpages": { "level": 2, "link": "[6.3.2 Example 19.3: Refinery Blending Problem](https://jckantor.github.io/CBE30338/06.03-Linear-Programming.html#6.3.2-Example-19.3:-Refinery-Blending-Problem)", "section": "6.3.2 Example 19.3: Refinery Blending Problem" } }, "outputs": [], "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": { "nbpages": { "level": 2, "link": "[6.3.2 Example 19.3: Refinery Blending Problem](https://jckantor.github.io/CBE30338/06.03-Linear-Programming.html#6.3.2-Example-19.3:-Refinery-Blending-Problem)", "section": "6.3.2 Example 19.3: Refinery Blending Problem" } }, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": { "nbpages": { "level": 2, "link": "[6.3.2 Example 19.3: Refinery Blending Problem](https://jckantor.github.io/CBE30338/06.03-Linear-Programming.html#6.3.2-Example-19.3:-Refinery-Blending-Problem)", "section": "6.3.2 Example 19.3: Refinery Blending Problem" } }, "source": [ "\n", "< [6.2 Linear Production Model](https://jckantor.github.io/CBE30338/06.02-Linear-Production-Model.html) | [Contents](toc.html) | [Tag Index](tag_index.html) | [6.4 Linear Production Model in Pyomo](https://jckantor.github.io/CBE30338/06.04-Linear-Production-Model-in-Pyomo.html) >

\"Open

\"Download\"" ] } ], "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.4" } }, "nbformat": 4, "nbformat_minor": 2 }