![\"Open](\"https://colab.research.google.com/assets/colab-badge.svg\"){kind=icon}
"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "i_4QVqdV96a6"
},
"source": [
"# Linear Programming\n",
"\n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "woaZjkArTMAh"
},
"source": [
"## Introduction\n",
"\n",
"\n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "n0AD_VXnYiKq"
},
"source": [
"A local pillow company designs pillows especially for pregnant and nursing mothers. There are two pillows that they produce referred here as large and small. The large pillow requires six yards of fabric, one hour of sewing and eleven pounds of fill. The small pillow requires seven yards of fabric, three hours of sewing and four pounds of fill.\n",
"\n",
"The manager, trying to keep all of this straight creates a table.\n",
"\n",
"|Pillow|Fabric|Sewing|Fill|\n",
"|:------:|:------:|:------:|:----:|\n",
"|Large |6 |1 |11 |\n",
"|Small |7 |3 |4 |\n",
"\n",
"The manager being an astute business man, wants to limit inventory and labor. Each week they can source 1370 yards of fabric and 1540 pounds of fill. With a work crew that can do at most 540 hours of labour each week. He adds this information to his table feeling very satisfied.\n",
"\n",
"|Pillow|Fabric|Sewing|Fill|\n",
"|:------:|:------:|:------:|:----:|\n",
"|Large |6 |1 |11 |\n",
"|Small |7 |3 |4 |\n",
"|Weekly Max| 1370|540|1540|\n",
"\n",
"Using some hueristics, the manager cranks out some pillows of each type every week. One day an intrept intern asks, \"Are we maximizing our profit?\" The large pillow sells for a $\\$ $3 profit, while the small pillow sells for a $\\$ $2 profit. The intern adds this to the table but still does not know if they are maximizing profit.\n",
"\n",
"|Pillow|Fabric|Sewing|Fill|Profit|\n",
"|:------:|:------:|:------:|:----:|:---:|\n",
"|Large |6 |1 |11 |3\n",
"|Small |7 |3 |4 |2\n",
"|Weekly Max| 1370|540|1540|???\n",
"\n",
"The intern continues down this line of thought and comes up with a way to maximize the number of pillows produced. They let $x$ be the number of large pillows and $y$ be the number of small pillows. They create a system of inequalities:\n",
"\n",
"$$\n",
"\\left\\{\n",
"\\begin{array}{l}\n",
"6x+7y\\leq 1370\\\\\n",
"x+3y\\leq 540\\\\\n",
"11x+4y\\leq 1540\n",
"\\end{array}\n",
"\\right.\n",
"$$\n",
"\n",
"To graph this properly, we'll find the corner points."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "X39A7NEyRKdt",
"outputId": "41343264-65ac-4981-f0f1-f125cacf9a95"
},
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"array([ 30., 170.])"
]
},
"metadata": {},
"execution_count": 1
}
],
"source": [
"import numpy as np\n",
"\n",
"A = np.array([[6,7],[1,3],[11,4]])\n",
"b = np.array([1370,540,1540])\n",
"\n",
"np.linalg.solve(A[0:2,:],b[0:2])"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "p3YIV4RTU-_R",
"outputId": "32cf5665-ad23-4e11-90bd-ec3b6256864b"
},
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"array([ 84.82758621, 151.72413793])"
]
},
"metadata": {},
"execution_count": 2
}
],
"source": [
"np.linalg.solve(A[1:3,:],b[1:3])"
]
},
{
"cell_type": "code",
"execution_count": 3,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/"
},
"id": "VBS_jjUCVDKJ",
"outputId": "c5ed797f-ff1c-4164-984f-10f1cad42588"
},
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"array([100., 110.])"
]
},
"metadata": {},
"execution_count": 3
}
],
"source": [
"np.linalg.solve(A[[0,2],:],b[[0,2]])"
]
},
{
"cell_type": "markdown",
"metadata": {
"id": "0GbUkHE99XEH"
},
"source": [
"Three lines will have three intersections $\\binom32=3$ We note that the intersection point of the first line and the third line is outside of the feasible region by the second line. A graph of the feasible set is provided below."
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"colab": {
"base_uri": "https://localhost:8080/",
"height": 448
},
"id": "KhIcgYdm7VO_",
"outputId": "f840b4bb-2d04-4610-9a80-ceb4f22e8d3c"
},
"outputs": [
{
"output_type": "execute_result",
"data": {
"text/plain": [
"| \n", " | Variables Used | \n", "Solution | \n", "Profit | \n", "In Feasible | \n", "
|---|---|---|---|---|
| 0 | \n", "(large, small, slackFabric) | \n", "[84.82759, 151.72414, -201.03448] | \n", "557.93105 | \n", "False | \n", "
| 1 | \n", "(large, small, slackSewing) | \n", "[100.0, 110.0, 110.0] | \n", "520.00000 | \n", "True | \n", "
| 2 | \n", "(large, small, slackfill) | \n", "[30.0, 170.0, 530.0] | \n", "430.00000 | \n", "True | \n", "
| 3 | \n", "(large, slackFabric, slackSewing) | \n", "[140.0, 530.0, 400.0] | \n", "420.00000 | \n", "True | \n", "
| 4 | \n", "(large, slackFabric, slackfill) | \n", "[540.0, -1870.0, -4400.0] | \n", "1620.00000 | \n", "False | \n", "
| 5 | \n", "(large, slackSewing, slackfill) | \n", "[228.33333, 311.66667, -971.66667] | \n", "684.99999 | \n", "False | \n", "
| 6 | \n", "(small, slackFabric, slackSewing) | \n", "[385.0, -1325.0, -615.0] | \n", "770.00000 | \n", "False | \n", "
| 7 | \n", "(small, slackFabric, slackfill) | \n", "[180.0, 110.0, 820.0] | \n", "360.00000 | \n", "True | \n", "
| 8 | \n", "(small, slackSewing, slackfill) | \n", "[195.71429, -47.14286, 757.14286] | \n", "391.42858 | \n", "False | \n", "
| 9 | \n", "(slackFabric, slackSewing, slackfill) | \n", "[1370.0, 540.0, 1540.0] | \n", "0.00000 | \n", "True | \n", "
| \n", " | Variables Used | \n", "Solution | \n", "Profit | \n", "In Feasible | \n", "
|---|---|---|---|---|
| 1 | \n", "(large, small, slackSewing) | \n", "[100.0, 110.0, 110.0] | \n", "520.0 | \n", "True | \n", "
| 2 | \n", "(large, small, slackfill) | \n", "[30.0, 170.0, 530.0] | \n", "430.0 | \n", "True | \n", "
| 3 | \n", "(large, slackFabric, slackSewing) | \n", "[140.0, 530.0, 400.0] | \n", "420.0 | \n", "True | \n", "
| 7 | \n", "(small, slackFabric, slackfill) | \n", "[180.0, 110.0, 820.0] | \n", "360.0 | \n", "True | \n", "
| 9 | \n", "(slackFabric, slackSewing, slackfill) | \n", "[1370.0, 540.0, 1540.0] | \n", "0.0 | \n", "True | \n", "
| \n", " | Variables Used | \n", "Solution | \n", "Profit | \n", "In Feasible | \n", "
|---|---|---|---|---|
| 1 | \n", "(large, small, slackSewing) | \n", "[100.0, 110.0, 110.0] | \n", "520.0 | \n", "True | \n", "
| \n", " | Variables Used | \n", "Solution | \n", "Profit | \n", "In Feasible | \n", "
|---|---|---|---|---|
| 0 | \n", "(downhill, cross) | \n", "[2.0, 7.0] | \n", "622.0 | \n", "True | \n", "