{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "6a6eebf6-87bb-4213-b779-06b973bcfa34",
   "metadata": {},
   "source": [
    "**Example 3.5.** A large construction firm is currently excavating at three sites.\n",
    "Meanwhile, they are also building at four additional sites, where they require fill\n",
    "dirt. The excavations at sites 1, 2, and 3 produce 150, 400, and 325 cubic yards\n",
    "of dirt per day. The building sites A, B, C, and D require 175, 125, 225, and\n",
    "450 cubic yards of dirt per day. Additional fill dirt can also be obtained from\n",
    "site 4 at a cost of 5 dollars per cubic yard. The cost of shipping fill dirt is about\n",
    "20 dollars per mile for one truckload, and a truck carries 10 cubic yards of dirt.\n",
    "Table 3.3 gives the distance between sites in miles. Find the transportation plan\n",
    "that minimizes the cost to the company."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "5a04bc3c-1e09-4a64-bcd8-5dbf22a4e0fe",
   "metadata": {},
   "source": [
    "**Table 3.3**\n",
    "\n",
    "|site|A|B|C|D|\n",
    "|:--:|:--:|:--:|:--:|:--:|\n",
    "|**1**|5|2|6|10|\n",
    "|**2**|4|5|7|5|\n",
    "|**3**|7|6|4|4|\n",
    "|**4**|9|10|6|2|"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "a4988841-5024-443f-b786-6df9969f5761",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4×4 Matrix{Int64}:\n",
       " 5   2  6  10\n",
       " 4   5  7   5\n",
       " 7   6  4   4\n",
       " 9  10  6   2"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "D=[5 2 6 10; 4 5 7 5; 7 6 4 4; 9 10 6 2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "8c9087b7-5daf-4821-95f4-347606252de8",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4×4 Matrix{Int64}:\n",
       " 10   4  12  20\n",
       "  8  10  14  10\n",
       " 14  12   8   8\n",
       " 23  25  17   9"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "C=2*D\n",
    "C[4,:].+=5\n",
    "C"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "26113623-6e86-4261-bbc2-c6f6a0e3a357",
   "metadata": {},
   "outputs": [],
   "source": [
    "using JuMP, HiGHS"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "989eb0bc-de1d-4c17-94f2-6be027079715",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "A JuMP Model\n",
       "├ solver: HiGHS\n",
       "├ objective_sense: FEASIBILITY_SENSE\n",
       "├ num_variables: 0\n",
       "├ num_constraints: 0\n",
       "└ Names registered in the model: none"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "model=Model(HiGHS.Optimizer)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "29fe4479-cb12-4291-9976-50d0f01285cc",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4×4 Matrix{VariableRef}:\n",
       " x[1,1]  x[1,2]  x[1,3]  x[1,4]\n",
       " x[2,1]  x[2,2]  x[2,3]  x[2,4]\n",
       " x[3,1]  x[3,2]  x[3,3]  x[3,4]\n",
       " x[4,1]  x[4,2]  x[4,3]  x[4,4]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@variable(model,x[1:4,1:4].>=0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "07479977-8276-47c5-88f8-222286a820c6",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$ 10 x_{1,1} + 8 x_{2,1} + 14 x_{3,1} + 23 x_{4,1} + 4 x_{1,2} + 10 x_{2,2} + 12 x_{3,2} + 25 x_{4,2} + 12 x_{1,3} + 14 x_{2,3} + 8 x_{3,3} + 17 x_{4,3} + 20 x_{1,4} + 10 x_{2,4} + 8 x_{3,4} + 9 x_{4,4} $"
      ],
      "text/plain": [
       "10 x[1,1] + 8 x[2,1] + 14 x[3,1] + 23 x[4,1] + 4 x[1,2] + 10 x[2,2] + 12 x[3,2] + 25 x[4,2] + 12 x[1,3] + 14 x[2,3] + 8 x[3,3] + 17 x[4,3] + 20 x[1,4] + 10 x[2,4] + 8 x[3,4] + 9 x[4,4]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "cost(x)=sum(C.*x)\n",
    "cost(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "0bbdfc56-dec4-421f-a04b-e91900798659",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10 x[1,1] + 8 x[2,1] + 14 x[3,1] + 23 x[4,1] + 4 x[1,2] + 10 x[2,2] + 12 x[3,2] + 25 x[4,2] + 12 x[1,3] + 14 x[2,3] + 8 x[3,3] + 17 x[4,3] + 20 x[1,4] + 10 x[2,4] + 8 x[3,4] + 9 x[4,4]\n"
     ]
    }
   ],
   "source": [
    "# Fix it so it doesn't scroll off the edge\n",
    "println(cost(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "ac7134d0-e23e-4b5c-8bf5-cf72b903ae8b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$ 10 x_{1,1} + 8 x_{2,1} + 14 x_{3,1} + 23 x_{4,1} + 4 x_{1,2} + 10 x_{2,2} + 12 x_{3,2} + 25 x_{4,2} + 12 x_{1,3} + 14 x_{2,3} + 8 x_{3,3} + 17 x_{4,3} + 20 x_{1,4} + 10 x_{2,4} + 8 x_{3,4} + 9 x_{4,4} $"
      ],
      "text/plain": [
       "10 x[1,1] + 8 x[2,1] + 14 x[3,1] + 23 x[4,1] + 4 x[1,2] + 10 x[2,2] + 12 x[3,2] + 25 x[4,2] + 12 x[1,3] + 14 x[2,3] + 8 x[3,3] + 17 x[4,3] + 20 x[1,4] + 10 x[2,4] + 8 x[3,4] + 9 x[4,4]"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "@objective(model,Min,cost(x))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "d4324889-bb0b-4eef-b2bf-81b26bac66ef",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4-element Vector{AffExpr}:\n",
       " x[1,1] + x[2,1] + x[3,1] + x[4,1]\n",
       " x[1,2] + x[2,2] + x[3,2] + x[4,2]\n",
       " x[1,3] + x[2,3] + x[3,3] + x[4,3]\n",
       " x[1,4] + x[2,4] + x[3,4] + x[4,4]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Amount of dirt received by site j\n",
    "r=[sum(x[:,j]) for j=1:4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "99876ac8-aaa3-45b9-b053-27b835624d9b",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4-element Vector{ConstraintRef{Model, MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.GreaterThan{Float64}}, ScalarShape}}:\n",
       " x[1,1] + x[2,1] + x[3,1] + x[4,1] ≥ 175\n",
       " x[1,2] + x[2,2] + x[3,2] + x[4,2] ≥ 125\n",
       " x[1,3] + x[2,3] + x[3,3] + x[4,3] ≥ 225\n",
       " x[1,4] + x[2,4] + x[3,4] + x[4,4] ≥ 450"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c1=@constraint(model,r.>=[175,125,225,450])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "c6c3aabf-fdfe-499c-8659-ed8f4f2cbdcb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4-element Vector{AffExpr}:\n",
       " x[1,1] + x[1,2] + x[1,3] + x[1,4]\n",
       " x[2,1] + x[2,2] + x[2,3] + x[2,4]\n",
       " x[3,1] + x[3,2] + x[3,3] + x[3,4]\n",
       " x[4,1] + x[4,2] + x[4,3] + x[4,4]"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Amount of dirt produced by site i\n",
    "s=[sum(x[i,:]) for i=1:4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "c4e1d7ef-be44-44d1-902e-1b96a4a5f3dd",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3-element Vector{ConstraintRef{Model, MathOptInterface.ConstraintIndex{MathOptInterface.ScalarAffineFunction{Float64}, MathOptInterface.LessThan{Float64}}, ScalarShape}}:\n",
       " x[1,1] + x[1,2] + x[1,3] + x[1,4] ≤ 150\n",
       " x[2,1] + x[2,2] + x[2,3] + x[2,4] ≤ 400\n",
       " x[3,1] + x[3,2] + x[3,3] + x[3,4] ≤ 325"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c2=@constraint(model,s[1:3].<=[150,400,325])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "c07a34e8-9218-475a-b50f-87b65ed0bd80",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/latex": [
       "$$ \\begin{aligned}\n",
       "\\min\\quad & 10 x_{1,1} + 8 x_{2,1} + 14 x_{3,1} + 23 x_{4,1} + 4 x_{1,2} + 10 x_{2,2} + 12 x_{3,2} + 25 x_{4,2} + 12 x_{1,3} + 14 x_{2,3} + 8 x_{3,3} + 17 x_{4,3} + 20 x_{1,4} + 10 x_{2,4} + 8 x_{3,4} + 9 x_{4,4}\\\\\n",
       "\\text{Subject to} \\quad & x_{1,1} + x_{2,1} + x_{3,1} + x_{4,1} \\geq 175\\\\\n",
       " & x_{1,2} + x_{2,2} + x_{3,2} + x_{4,2} \\geq 125\\\\\n",
       " & x_{1,3} + x_{2,3} + x_{3,3} + x_{4,3} \\geq 225\\\\\n",
       " & x_{1,4} + x_{2,4} + x_{3,4} + x_{4,4} \\geq 450\\\\\n",
       " & x_{1,1} + x_{1,2} + x_{1,3} + x_{1,4} \\leq 150\\\\\n",
       " & x_{2,1} + x_{2,2} + x_{2,3} + x_{2,4} \\leq 400\\\\\n",
       " & x_{3,1} + x_{3,2} + x_{3,3} + x_{3,4} \\leq 325\\\\\n",
       " & x_{1,1} \\geq 0\\\\\n",
       " & x_{2,1} \\geq 0\\\\\n",
       " & x_{3,1} \\geq 0\\\\\n",
       " & x_{4,1} \\geq 0\\\\\n",
       " & x_{1,2} \\geq 0\\\\\n",
       " & x_{2,2} \\geq 0\\\\\n",
       " & x_{3,2} \\geq 0\\\\\n",
       " & x_{4,2} \\geq 0\\\\\n",
       " & x_{1,3} \\geq 0\\\\\n",
       " & x_{2,3} \\geq 0\\\\\n",
       " & x_{3,3} \\geq 0\\\\\n",
       " & x_{4,3} \\geq 0\\\\\n",
       " & x_{1,4} \\geq 0\\\\\n",
       " & x_{2,4} \\geq 0\\\\\n",
       " & x_{3,4} \\geq 0\\\\\n",
       " & x_{4,4} \\geq 0\\\\\n",
       "\\end{aligned} $$"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "print(model)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "id": "125af725-1e03-46d4-91eb-f29535e7de66",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Min 10 x[1,1] + 8 x[2,1] + 14 x[3,1] + 23 x[4,1] + 4 x[1,2] + 10 x[2,2] + 12 x[3,2] + 25 x[4,2] + 12 x[1,3] + 14 x[2,3] + 8 x[3,3] + 17 x[4,3] + 20 x[1,4] + 10 x[2,4] + 8 x[3,4] + 9 x[4,4]\n",
      "Subject to\n",
      " x[1,1] + x[2,1] + x[3,1] + x[4,1] ≥ 175\n",
      " x[1,2] + x[2,2] + x[3,2] + x[4,2] ≥ 125\n",
      " x[1,3] + x[2,3] + x[3,3] + x[4,3] ≥ 225\n",
      " x[1,4] + x[2,4] + x[3,4] + x[4,4] ≥ 450\n",
      " x[1,1] + x[1,2] + x[1,3] + x[1,4] ≤ 150\n",
      " x[2,1] + x[2,2] + x[2,3] + x[2,4] ≤ 400\n",
      " x[3,1] + x[3,2] + x[3,3] + x[3,4] ≤ 325\n",
      " x[1,1] ≥ 0\n",
      " x[2,1] ≥ 0\n",
      " x[3,1] ≥ 0\n",
      " x[4,1] ≥ 0\n",
      " x[1,2] ≥ 0\n",
      " x[2,2] ≥ 0\n",
      " x[3,2] ≥ 0\n",
      " x[4,2] ≥ 0\n",
      " x[1,3] ≥ 0\n",
      " x[2,3] ≥ 0\n",
      " x[3,3] ≥ 0\n",
      " x[4,3] ≥ 0\n",
      " x[1,4] ≥ 0\n",
      " x[2,4] ≥ 0\n",
      " x[3,4] ≥ 0\n",
      " x[4,4] ≥ 0\n"
     ]
    }
   ],
   "source": [
    "# Fix the scrolling left to right\n",
    "print(sprint(print,model))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "1c42a60e-9460-4752-8f9a-a870e6409ce4",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Running HiGHS 1.13.1 (git hash: 1d267d97c): Copyright (c) 2026 under Apache 2.0 license terms\n",
      "Using BLAS: blastrampoline \n",
      "LP has 7 rows; 16 cols; 28 nonzeros\n",
      "Coefficient ranges:\n",
      "  Matrix  [1e+00, 1e+00]\n",
      "  Cost    [4e+00, 2e+01]\n",
      "  Bound   [0e+00, 0e+00]\n",
      "  RHS     [1e+02, 4e+02]\n",
      "Presolving model\n",
      "7 rows, 16 cols, 28 nonzeros  0s\n",
      "7 rows, 14 cols, 24 nonzeros  0s\n",
      "Presolve reductions: rows 7(-0); columns 14(-2); nonzeros 24(-4) \n",
      "Solving the presolved LP\n",
      "Using dual simplex solver\n",
      "  Iteration        Objective     Infeasibilities num(sum)\n",
      "          0     0.0000000000e+00 Pr: 4(975) 0.0s\n",
      "          5     7.6500000000e+03 Pr: 0(0) 0.0s\n",
      "\n",
      "Performed postsolve\n",
      "Solving the original LP from the solution after postsolve\n",
      "\n",
      "Model status        : Optimal\n",
      "Simplex   iterations: 5\n",
      "Objective value     :  7.6500000000e+03\n",
      "P-D objective error :  0.0000000000e+00\n",
      "HiGHS run time      :          0.00\n"
     ]
    }
   ],
   "source": [
    "optimize!(model)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "id": "c8a89858-855c-4e86-8d65-ecda18490416",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7650.0"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "objective_value(model)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "3cd9e5a2-ec86-419f-927f-c63c6a377d19",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4×4 Matrix{Float64}:\n",
       "   0.0  125.0    0.0    0.0\n",
       " 175.0    0.0    0.0    0.0\n",
       "   0.0    0.0  225.0  100.0\n",
       "   0.0    0.0    0.0  350.0"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "value(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "961287a8-4a0d-4e21-b3d4-228981ceaccb",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.10",
   "language": "julia",
   "name": "julia-1.10"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.10.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}