{ "cells": [ { "cell_type": "markdown", "id": "2595a3a1-1834-4acc-b70a-3e11f538091e", "metadata": {}, "source": [ "**Example 3.6.** Reconsider the family farm problem of Example 3.4. The family\n", "has 625 acres available for planting. There are 5 plots of 120 acres each and\n", "another plot of 25 acres. The family wants to plant each plot with only one\n", "crop: corn, wheat, or oats. As before, 1,000 acre–ft of water will be available\n", "for irrigation, and the farmers will be able to devote 300 hours of labor per\n", "week. Additional data are presented in Table 3.2. Find the crop that should be\n", "planted in each plot for maximum profit." ] }, { "cell_type": "markdown", "id": "e3a43366-9901-4305-9cd3-8136d4504da5", "metadata": {}, "source": [ "**Table 3.2.**\n", "\n", "|Requirements|Corn|Wheat|Oats|\n", "|-|-|-|-|\n", "|Irrigation (acre-ft)|3.0|1.0|1.5|\n", "|Labor (person-hrs/week)|0.8|0.2|0.3|\n", "|Yield ($)|400|200|250|" ] }, { "cell_type": "markdown", "id": "2038a56f-f1ac-41ee-8786-ed533fb17a30", "metadata": {}, "source": [ "$x_1 = {}$number of 120 acre plots of corn planted\\\n", "$x_2 = {}$number of 120–acre plots of wheat planted\\\n", "$x_3 = {}$number of 120–acre plots of oats planted\\\n", "$x_4 = {}$number of 25–acre plots of corn planted\\\n", "$x_5 = {}$number of 25–acre plots of wheat planted\\\n", "$x_6 = {}$number of 25–acre plots of oats planted\\\n", "$w = {}$irrigation required (acre–ft)\\\n", "$l = {}$labor required (person–hrs/wk)\\\n", "$t = {}$total acreage planted\\\n", "$y = {}$total yield (\\$)" ] }, { "cell_type": "code", "execution_count": 1, "id": "1d2c456f-00e8-4732-8018-242a6555f4d3", "metadata": {}, "outputs": [], "source": [ "using JuMP,HiGHS" ] }, { "cell_type": "code", "execution_count": 2, "id": "b293b593-60b8-44e3-be4d-34f3135b2ebc", "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": 2, "metadata": {}, "output_type": "execute_result" } ], "source": [ "model=Model(HiGHS.Optimizer)" ] }, { "cell_type": "code", "execution_count": 3, "id": "be75fef0-822e-4657-b329-3ae66a485a8a", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "6-element Vector{VariableRef}:\n", " x[1]\n", " x[2]\n", " x[3]\n", " x[4]\n", " x[5]\n", " x[6]" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@variable(model,x[1:6].>=0,Int)" ] }, { "cell_type": "code", "execution_count": 4, "id": "426d6c72-0c4c-4646-b56b-774b921d8773", "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$$ \\begin{aligned}\n", "\\text{feasibility}\\\\\n", "\\text{Subject to} \\quad & x_{1} \\geq 0\\\\\n", " & x_{2} \\geq 0\\\\\n", " & x_{3} \\geq 0\\\\\n", " & x_{4} \\geq 0\\\\\n", " & x_{5} \\geq 0\\\\\n", " & x_{6} \\geq 0\\\\\n", " & x_{1} \\in \\mathbb{Z}\\\\\n", " & x_{2} \\in \\mathbb{Z}\\\\\n", " & x_{3} \\in \\mathbb{Z}\\\\\n", " & x_{4} \\in \\mathbb{Z}\\\\\n", " & x_{5} \\in \\mathbb{Z}\\\\\n", " & x_{6} \\in \\mathbb{Z}\\\\\n", "\\end{aligned} $$" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "print(model)" ] }, { "cell_type": "markdown", "id": "0ff271a8-0c2b-4215-99f2-3203a47cda8b", "metadata": {}, "source": [ "$w(x) = {}$The total amount of water used\\\n", "$l(x) = {}$The total labor needed\\\n", "$t(x) = {}$The total acres planted\\\n", "$y(x) = {}$The yield (objective function)" ] }, { "cell_type": "code", "execution_count": 5, "id": "6571d363-a129-4c14-934a-c4e5b3d5dbd5", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "y (generic function with 1 method)" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Note the function definitions that extend over two lines extend\n", "# to the next line by placing the + at the end of the first line. \n", "w(x)=120*(3.0*x[1]+1.0*x[2]+1.5*x[3])+\n", " 25*(3.0*x[4]+1.0*x[5]+1.5*x[6])\n", "l(x)=120*(0.8*x[1]+0.2*x[2]+0.3*x[3])+\n", " 25*(0.8*x[4]+0.2*x[5]+0.3*x[6])\n", "t(x)=120*(x[1]+x[2]+x[3])+25*(x[4]+x[5]+x[6])\n", "y(x)=120*(400*x[1]+200*x[2]+250*x[3])+\n", " 25*(400*x[4]+200*x[5]+250*x[6])" ] }, { "cell_type": "code", "execution_count": 6, "id": "8db6b5d8-f221-43f1-82b7-849ba8e399aa", "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$ 48000 x_{1} + 24000 x_{2} + 30000 x_{3} + 10000 x_{4} + 5000 x_{5} + 6250 x_{6} $" ], "text/plain": [ "48000 x[1] + 24000 x[2] + 30000 x[3] + 10000 x[4] + 5000 x[5] + 6250 x[6]" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "@objective(model,Max,y(x))" ] }, { "cell_type": "code", "execution_count": 7, "id": "410a4df7-31d3-483c-a2cd-26d39312a93f", "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$$ 360 x_{1} + 120 x_{2} + 180 x_{3} + 75 x_{4} + 25 x_{5} + 37.5 x_{6} \\leq 1000 $$" ], "text/plain": [ "360 x[1] + 120 x[2] + 180 x[3] + 75 x[4] + 25 x[5] + 37.5 x[6] ≤ 1000" ] }, "execution_count": 7, "metadata": {}, "output_type": "execute_result" } ], "source": [ "c1=@constraint(model,w(x)<=1000)" ] }, { "cell_type": "code", "execution_count": 8, "id": "e39cae60-5fa7-45a7-a17f-757c17ae0c95", "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$$ 96 x_{1} + 24 x_{2} + 36 x_{3} + 20 x_{4} + 5 x_{5} + 7.5 x_{6} \\leq 300 $$" ], "text/plain": [ "96 x[1] + 24 x[2] + 36 x[3] + 20 x[4] + 5 x[5] + 7.5 x[6] ≤ 300" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "c2=@constraint(model,l(x)<=300)" ] }, { "cell_type": "code", "execution_count": 9, "id": "51ce2638-8a64-498f-9bab-15b9fd7744b3", "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$$ x_{1} + x_{2} + x_{3} \\leq 5 $$" ], "text/plain": [ "x[1] + x[2] + x[3] ≤ 5" ] }, "execution_count": 9, "metadata": {}, "output_type": "execute_result" } ], "source": [ "c3=@constraint(model,x[1]+x[2]+x[3]<=5)" ] }, { "cell_type": "code", "execution_count": 10, "id": "4b154f4f-b24c-4064-8617-e29e3bd93fe6", "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$$ x_{4} + x_{5} + x_{6} \\leq 1 $$" ], "text/plain": [ "x[4] + x[5] + x[6] ≤ 1" ] }, "execution_count": 10, "metadata": {}, "output_type": "execute_result" } ], "source": [ "c4=@constraint(model,x[4]+x[5]+x[6]<=1)" ] }, { "cell_type": "code", "execution_count": 11, "id": "7acce9c6-5ee0-4526-a30e-2adeecac8e7f", "metadata": {}, "outputs": [ { "data": { "text/latex": [ "$$ \\begin{aligned}\n", "\\max\\quad & 48000 x_{1} + 24000 x_{2} + 30000 x_{3} + 10000 x_{4} + 5000 x_{5} + 6250 x_{6}\\\\\n", "\\text{Subject to} \\quad & 360 x_{1} + 120 x_{2} + 180 x_{3} + 75 x_{4} + 25 x_{5} + 37.5 x_{6} \\leq 1000\\\\\n", " & 96 x_{1} + 24 x_{2} + 36 x_{3} + 20 x_{4} + 5 x_{5} + 7.5 x_{6} \\leq 300\\\\\n", " & x_{1} + x_{2} + x_{3} \\leq 5\\\\\n", " & x_{4} + x_{5} + x_{6} \\leq 1\\\\\n", " & x_{1} \\geq 0\\\\\n", " & x_{2} \\geq 0\\\\\n", " & x_{3} \\geq 0\\\\\n", " & x_{4} \\geq 0\\\\\n", " & x_{5} \\geq 0\\\\\n", " & x_{6} \\geq 0\\\\\n", " & x_{1} \\in \\mathbb{Z}\\\\\n", " & x_{2} \\in \\mathbb{Z}\\\\\n", " & x_{3} \\in \\mathbb{Z}\\\\\n", " & x_{4} \\in \\mathbb{Z}\\\\\n", " & x_{5} \\in \\mathbb{Z}\\\\\n", " & x_{6} \\in \\mathbb{Z}\\\\\n", "\\end{aligned} $$" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "print(model)" ] }, { "cell_type": "code", "execution_count": 12, "id": "e0ae4f63-94cf-493e-b37a-93c95bb1caf7", "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", "MIP has 4 rows; 6 cols; 18 nonzeros; 6 integer variables (0 binary)\n", "Coefficient ranges:\n", " Matrix [1e+00, 4e+02]\n", " Cost [5e+03, 5e+04]\n", " Bound [0e+00, 0e+00]\n", " RHS [1e+00, 1e+03]\n", "Presolving model\n", "4 rows, 6 cols, 18 nonzeros 0s\n", "4 rows, 6 cols, 18 nonzeros 0s\n", "Presolve reductions: rows 4(-0); columns 6(-0); nonzeros 18(-0) - Not reduced\n", "Objective function is integral with scale 0.004\n", "\n", "Solving MIP model with:\n", " 4 rows\n", " 6 cols (3 binary, 3 integer, 0 implied int., 0 continuous, 0 domain fixed)\n", " 18 nonzeros\n", "\n", "Src: B => Branching; C => Central rounding; F => Feasibility pump; H => Heuristic;\n", " I => Shifting; J => Feasibility jump; L => Sub-MIP; P => Empty MIP; R => Randomized rounding;\n", " S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution; Y => HiGHS solution;\n", " Z => ZI Round; l => Trivial lower; p => Trivial point; u => Trivial upper; z => Trivial zero\n", "\n", " Nodes | B&B Tree | Objective Bounds | Dynamic Constraints | Work \n", "Src Proc. InQueue | Leaves Expl. | BestBound BestSol Gap | Cuts InLp Confl. | LpIters Time\n", "\n", " z 0 0 0 0.00% inf -0 Large 0 0 0 0 0.0s\n", " J 0 0 0 0.00% inf 150000 Large 0 0 0 0 0.0s\n", " R 0 0 0 0.00% 162500 155000 4.84% 0 0 0 4 0.0s\n", " L 0 0 0 0.00% 162250 162250 0.00% 10 3 3 8 0.0s\n", " 1 0 1 100.00% 162250 162250 0.00% 10 3 3 8 0.0s\n", "\n", "Solving report\n", " Status Optimal\n", " Primal bound 162250\n", " Dual bound 162250\n", " Gap 0% (tolerance: 0.01%)\n", " P-D integral 0.00268704875823\n", " Solution status feasible\n", " 162250 (objective)\n", " 0 (bound viol.)\n", " 3.99680288865e-15 (int. viol.)\n", " 0 (row viol.)\n", " Timing 0.04\n", " Max sub-MIP depth 1\n", " Nodes 1\n", " Repair LPs 0\n", " LP iterations 8\n", " 0 (strong br.)\n", " 4 (separation)\n", " 0 (heuristics)\n" ] } ], "source": [ "optimize!(model)" ] }, { "cell_type": "code", "execution_count": 13, "id": "1cb414b9-1474-44b7-8484-feaa2d5fb6d4", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "162250.00000000003" ] }, "execution_count": 13, "metadata": {}, "output_type": "execute_result" } ], "source": [ "objective_value(model)" ] }, { "cell_type": "code", "execution_count": 14, "id": "de1588a5-bf6b-4e27-8831-2e4f32816ab4", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "6-element Vector{Float64}:\n", " 0.9999999999999998\n", " 2.0\n", " 2.0000000000000004\n", " 3.9968028886505635e-15\n", " -0.0\n", " 0.999999999999996" ] }, "execution_count": 14, "metadata": {}, "output_type": "execute_result" } ], "source": [ "value(x)" ] }, { "cell_type": "markdown", "id": "21c6944d-b5f3-47b4-a9ca-45b6c4859ae4", "metadata": {}, "source": [ "Solution was $[1,2,2,0,0,1]$ with optimal yield 162250." ] }, { "cell_type": "code", "execution_count": null, "id": "ec10a5a0-b7b5-46e4-a3ed-a15bb6223561", "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 }