Linear Programming Models

Introduction

We will talk about two categories of models: allocation and blending models. Then, we will talk about converting some non-linear objective functions into linear models. Allocation models are used to allocate resources to different activities. Blending models are used to blend different ingredients to produce a product. \[ \begin{equation} \begin{aligned} & \text{minimize or maximize} & & f(x_1, \dots, x_n) \\ & \text{subject to} & & g_i(x_1, \dots, x_n) \begin{cases} \leq b_i & i = 1, \dots, m \\ = b_i & i = 1, \dots, m \\ \geq b_i & i = 1, \dots, m \end{cases} \end{aligned} \end{equation} \]

We distinguish classes of mathematical programs according to whether functions \(f, g_1,...,g_m\) are linear or nonlinear in the decision variables. A function is linear if it is a constant-weighted sum of decision variables. Otherwise, it is nonlinear. See example 2.13 of the textbook.

An optimization model in functional form is a linear program (LP) if its (single) objective function f and all constraint functions \(g_1,...,g_m\) are linear in the decision variables. Also, decision variables should be able to take on whole-number or fractional values. An optimization model in functional form is a nonlinear program (NLP) if its (single) objective function f or any of the constraint functions \(g_1,...,g_m\) is nonlinear in the decision variables. Also, decision variables should be able to take on whole-number or fractional values. See example 2.14 of the textbook.

Allocation Models

‘One of the simplest forms of linear programs that occurs widely in application might be termed allocation models.’ reference 1

‘The main issue is how to divide or allocate a valuable resource among competing needs. The resource may be land, capital, time, fuel, or anything else of limited availability.’ reference 1

See example 4.1 and exercise 4.1 of the textbook. Here is a python code to solve the problem in example 4.1.

Code

%pip install -q amplpy matplotlib pandas
%pip install -q amplpy
from amplpy import AMPL, ampl_notebook
ampl = ampl_notebook(
    modules=["cbc", "highs"],  # modules to install
    license_uuid="cf1b53af-8068-4af6-85e2-41060092fde9",  # license to use
)  # instantiate AMPL object and register magics

[notice] A new release of pip is available: 24.0 -> 24.2
[notice] To update, run: /Library/Developer/CommandLineTools/usr/bin/python3 -m pip install --upgrade pip
Note: you may need to restart the kernel to use updated packages.

[notice] A new release of pip is available: 24.0 -> 24.2
[notice] To update, run: /Library/Developer/CommandLineTools/usr/bin/python3 -m pip install --upgrade pip
Note: you may need to restart the kernel to use updated packages.
Licensed to AMPL Community Edition License for <harun.pirim@ndsu.edu>.

/Users/harunpirim/Library/Python/3.9/lib/python/site-packages/urllib3/__init__.py:35: NotOpenSSLWarning: urllib3 v2 only supports OpenSSL 1.1.1+, currently the 'ssl' module is compiled with 'LibreSSL 2.8.3'. See: https://github.com/urllib3/urllib3/issues/3020
  warnings.warn(

Code

%%ampl_eval
reset;
param d{1..4};
var x{1..4} >=0;
maximize p: 1.6 * x[1] + 1.4 * x[2] + 1.9*x[3] + 1.2*x[4];
capacity: sum{i in 1..4}x[i]<= 1200;
demand1{i in 1..4}: x[i] >=0.5*d[i];
demand2{i in 1..4}: x[i] <= 0.7*d[i];
data;
param d:= 1 620 2 490  3 510 4 380;

Code

# exhibit the model that has been built
ampl.eval("expand;");
# solve using 'highs' solver and display the result
ampl.option["solver"] = "highs";
ampl.solve();
ampl.display("_varname", "_var");

maximize p:
    1.6*x[1] + 1.4*x[2] + 1.9*x[3] + 1.2*x[4];

subject to capacity:
    x[1] + x[2] + x[3] + x[4] <= 1200;

subject to demand1[1]:
    x[1] >= 310;

subject to demand1[2]:
    x[2] >= 245;

subject to demand1[3]:
    x[3] >= 255;

subject to demand1[4]:
    x[4] >= 190;

subject to demand2[1]:
    x[1] <= 434;

subject to demand2[2]:
    x[2] <= 343;

subject to demand2[3]:
    x[3] <= 357;

subject to demand2[4]:
    x[4] <= 266;

HiGHS 1.6.0: HiGHS 1.6.0: optimal solution; objective 1902.1
1 simplex iterations
0 barrier iterations
 
: _varname  _var    :=
1   'x[1]'   408
2   'x[2]'   245
3   'x[3]'   357
4   'x[4]'   190
;

References

1: Optimization in OR textbook by R. Rardin