{ "cells": [ { "cell_type": "markdown", "metadata": { "id": "sQ2IMEwWOOTE" }, "source": [ "# A Production Planning Problem" ] }, { "cell_type": "markdown", "metadata": { "id": "LHajl8VAOOTF" }, "source": [ "## Problem Statement\n", "\n", "A company produces two versions of a product. Each version is made from the same raw material that costs \\$10 per gram, and each version requires two different types of specialized labor to finish.\n", "\n", "* $U$ is the higher priced version of the product. $U$ sells for $\\$270$ per unit and requires 10 grams of raw material, one hour of labor type $A$, two hours of labor type $B$. The market demand for $U$ is limited to forty units per week.\n", "\n", "* $V$ is the lower priced version of the product with unlimited demand that sells for $\\$210$ per unit and requires 9 grams of raw material, 1 hour of labor type $A$ and 1 hour of labor type $B$.\n", "\n", "This data is summarized in the following table:\n", "\n", "| Version | Raw Material
required | Labor A
required | Labor B
required | Market
Demand | Price |\n", "| :-: | :-: | :-: | :-: | :-: | :-: |\n", "| U | 10 g | 1 hr | 2 hr | $\\leq$ 40 units | \\$270 |\n", "| V | 9 g | 1 hr | 1 hr | unlimited | \\$210 |\n", "\n", "Weekly production at the company is limited by the availability of labor and by the inventory of raw material. The raw material has a shelf life of one week and must be ordered in advance. Any raw material left over at the end of the week is discarded. The following table details the cost and availability of raw material and labor.\n", "\n", "| Resource | Amount
Available | Cost |\n", "| :-: | :-: | :-: |\n", "| Raw Material | ? | \\$10 / g |\n", "| Labor A | 80 hours | \\$50 / hour |\n", "| Labor B | 100 hours | \\$40 / hour |\n", "\n", "The company wishes to maximize gross profits.\n", "\n", "1. How much raw material should be ordered in advance for each week?\n", "2. How many units of $U$ and $V$ should the company produce each week?" ] }, { "cell_type": "markdown", "metadata": { "id": "b67yy_EiOOTH" }, "source": [ "## Mathematical Model\n", "\n", "The problem statement above describes an optimization problem. Reformulating the problem statement as a mathematical model involves three kinds of elements:\n", "\n", "* **decision variables**\n", "* **objective function**\n", "* **constraints**\n", "\n", "The starting point in developing a mathematical model is to list decision variables relevant to the problem at hand. Decision variables are quantities that can be modified to achieve a desired outcome. While some decision variables introduced at this stage may prove redundant later, the goal at this point is to create a comprehensive list of variables that will be useful in expressing the problem's objective and constraints.\n", "\n", "For this problem statement, listed below are decision variables with symbols, descriptions, and any lower and upper bounds that are known from the problem data.\n", "\n", "| Decision Variable | Description | lower bound | upper bound |\n", "| :-: | :--- | :-: | :-: |\n", "| $x_M$ | amount of raw material used | 0 | - |\n", "| $x_A$ | amount of Labor A used | 0 | 80 |\n", "| $x_B$ | amount of Labor B used | 0 | 100 |\n", "| $y_U$ | number of $U$ units to produce | 0 | 40 |\n", "| $y_V$ | number of $V$ units to produce | 0 | - |\n", "\n", "The next step is to formulate an **objective function** describing that describes how we will measure the value of candidate solutions to the problem. In this case, the value of the solution is measured by profit, which is to be maximized.Profit is equal to the difference between total revenue from sales and total cost of operations:\n", "\n", "$$\n", "\\begin{aligned}\n", " \\text{profit} & = \\text{revenue} - \\text{cost} \\\\\n", "\\end{aligned}\n", "$$\n", "\n", "Total revenue, in turn, is the sum of the revenues from the two products, and total cost is the sum of the costs of the three resources:\n", "\n", "$$\n", "\\begin{aligned}\n", " \\text{revenue} & = 270 y_U + 210 y_V \\\\\n", " \\text{cost} & = 10 x_M + 50 x_A + 40 x_B \\\\\n", "\\end{aligned}\n", "$$\n", "\n", "Putting these together, we have the following objective function expressing maximization of profit:\n", "\n", "$$\n", "\\begin{aligned}\n", " {\\rm maximize} \\quad & 270 y_U + 210 y_V - 10 x_M - 50 x_A - 40 x_B\n", "\\end{aligned}$$\n", "\n", "Finally, the decision variables $y_U, y_V, x_M, x_A, x_B$ need to satisfy the specific conditions given in the problem statement. **Constraints** are mathematical relationships among decision variables or expressions, formulated either as equalities or inequalities. In this problem, for each resource there is a requirement that the amount used in production of $U$ plus the amount used in the production of $V$ must not exceed the amount available. These requirements can be expressed mathematicaly as linear inequalities:\n", "\n", "$$\n", "\\begin{aligned}\n", " 10 y_U + 9 y_V & \\leq x_M & & \\text{raw material}\\\\\n", " 2 y_U + 1 y_V & \\leq x_A & &\\text{labor A} \\\\\n", " 1 y_U + 1 y_V & \\leq x_B & & \\text{labor B}\\\\\n", "\\end{aligned}\n", "$$\n", "\n", "We are now ready to formulate the full mathematical optimization problem in the following canonical way: First we state the objective function to be maximized (or minimized), then we list all the constraints, and lastly we list all the decision variables and their bounds:\n", "\n", "$$\n", "\\begin{align}\n", "{\\rm maximize} \\quad & 270 y_U + 210 y_V - 10 x_M - 50 x_A - 40 x_B \\\\\n", "\\text{subject to} \\quad & 10 y_U + 9 y_V \\leq x_M \\nonumber \\\\\n", " & 2 y_U + 1 y_V \\leq x_A \\nonumber \\\\\n", " & 1 y_U + 1 y_V \\leq x_B \\nonumber \\\\\n", " & 0 \\leq x_M \\nonumber \\\\\n", " & 0 \\leq x_A \\leq 80 \\nonumber \\\\\n", " & 0 \\leq x_B \\leq 100 \\nonumber \\\\\n", " & 0 \\leq y_U \\leq 40 \\nonumber \\\\\n", " & 0 \\leq y_V.\\nonumber\n", "\\end{align}\n", "$$\n", "\n", "This completes the mathematical description of this example of a production planning problem.\n", "\n", "An **optimal solution** of this problem is any assignment of values to the decision variables that meets the constraints and that achieves the maximum/minimum objective.\n", "\n", "However, even for a simple problem like this one, it is not immediately clear what the optimal solution is. This is exactly where mathematical optimization algorithms come into play. They are generic procedures that can find the optimal solutions of problems as long as these problems can be formulated in a standardized fashion as above.\n", "\n", "For a practitioner, mathematical optimization often boils down to formulating the problem as a model above, then passing it over to one of the many software packages that can solve such a model regardless of what was the original *story* behind the model. To do so, we need an interface of communication between the models and the algorithms. In this book, we adopt an interface based on the AMPL modeling language and the Python programming language. AMPL is based on the same mathematical formulation that practitioners use, but is standardized so that it can be read and translated by a computer system. Python provides access to powerful tools for processing data and presenting results.\n", "\n", "Thus the next step is to create the corresponding AMPL model." ] } ], "metadata": { "colab": { "include_colab_link": true, "provenance": [] }, "kernelspec": { "display_name": "Python 3 (ipykernel)", "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.10.6" }, "latex_envs": { "LaTeX_envs_menu_present": true, "autoclose": false, "autocomplete": true, "bibliofile": "biblio.bib", "cite_by": "apalike", "current_citInitial": 1, "eqLabelWithNumbers": true, "eqNumInitial": 1, "hotkeys": { "equation": "Ctrl-E", "itemize": "Ctrl-I" }, "labels_anchors": false, "latex_user_defs": false, "report_style_numbering": false, "user_envs_cfg": false } }, "nbformat": 4, "nbformat_minor": 0 }