LINEAR_PROG

Overview

The linear_prog function solves linear programming (LP) problems using the scipy.optimize.linprog function. The function accepts the objective coefficients, constraint matrices, and bounds as arguments, and returns the optimal solution and value, or an error message (as a string) if the problem is infeasible or input is invalid.

The standard form of a linear programming problem is:

\text{Minimize: } c^T x

Subject to:

A_{ub} x \leq b_{ub} \\ A_{eq} x = b_{eq} \\ bounds_i^{min} \leq x_i \leq bounds_i^{max}

Where:

$x$ is the vector of decision variables
$c$ is the vector of objective coefficients
$A_{ub}$ and $b_{ub}$ define the inequality constraints
$A_{eq}$ and $b_{eq}$ define the equality constraints
$bounds$ specify lower and upper bounds for each variable

This example function is provided as-is without any representation of accuracy.

Usage

To use the function in Excel:


=LINEAR_PROG(c, [A_ub], [b_ub], [A_eq], [b_eq], [bounds], [method])

c (2D list, required): Objective coefficients (to minimize $c^T x$ ). Example: [[3, 5]]
A_ub (2D list, optional): Inequality constraint coefficients ( $A_{ub} x \leq b_{ub}$ ). Example: [[-1, -2], [-2, -1]]
b_ub (2D list, optional): Inequality constraint bounds. Example: [[-8], [-8]]
A_eq (2D list, optional): Equality constraint coefficients ( $A_{eq} x = b_{eq}$ ). Example: [[0, 0]]
b_eq (2D list, optional): Equality constraint bounds. Example: [[0]]
bounds (2D list, optional): Variable bounds [[min1, max1], [min2, max2], ...]. Example: [[0, None], [0, None]]
method (string, optional): LP algorithm to use. Possible values: "highs", "highs-ds", "highs-ipm", "revised simplex", "simplex", "interior-point". Example: "highs"

The function returns a 2D list: [[x1, x2, ..., optimal_value]] if successful, or an error message as a string if the problem is infeasible or input is invalid.

Examples

Example 1: Resource Allocation (Minimize Cost)

This example minimizes the cost function $3x_1 + 5x_2$ subject to two inequality constraints:

$x_1 + 2x_2 \geq 8$
$2x_1 + x_2 \geq 8$

In Excel:


=LINEAR_PROG({3,5}, {-1,-2;-2,-1}, {-8;-8})

Expected output:

x1	x2	Optimal Value
2.0	3.0	21.0

This means the minimum cost is 21.0 when $x_1 = 2.0$ and $x_2 = 3.0$ .

Example 2: Diet Problem (Maximize Protein)

This example maximizes $x_1 + x_2$ (by minimizing $-x_1 - x_2$ ) subject to $x_1 + 2x_2 \leq 10$ .

In Excel:


=LINEAR_PROG({-1,-1}, {1,2}, {10})

Expected output:

x1	x2	Optimal Value
10.0	0.0	-10.0

This means the maximum sum $x_1 + x_2$ is 10.0 (since the optimal value is the negative of the sum), achieved when $x_1 = 10.0$ and $x_2 = 0.0$ .

Python Code


from scipy.optimize import linprog
import numpy as np
 
def linear_prog(c, A_ub=None, b_ub=None, A_eq=None, b_eq=None, bounds=None, method=None):
    """
    Solves a linear programming problem using scipy.optimize.linprog.
 
    Args:
        c (2D list): Coefficients for the linear objective function to be minimized (as row or column vector).
        A_ub (2D list, optional): Inequality constraint coefficients (A_ub x <= b_ub).
        b_ub (2D list, optional): Inequality constraint bounds.
        A_eq (2D list, optional): Equality constraint coefficients (A_eq x == b_eq).
        b_eq (2D list, optional): Equality constraint bounds.
        bounds (2D list, optional): Variable bounds [[min, max], ...].
        method (str, optional): LP algorithm to use. Possible values: 'highs', 'highs-ds', 'highs-ipm', 'revised simplex', 'simplex', 'interior-point'.
 
    Returns:
        list[list[float]]: [[x1, x2, ..., optimal_value]] if successful, or error message as str if infeasible or input is invalid.
 
    This example function is provided as-is without any representation of accuracy.
    """
    try:
        c_vec = np.array(c).flatten()
        n_vars = c_vec.size
        A_ub_mat = np.array(A_ub) if A_ub is not None else None
        b_ub_vec = np.array(b_ub).flatten() if b_ub is not None else None
        A_eq_mat = np.array(A_eq) if A_eq is not None else None
        b_eq_vec = np.array(b_eq).flatten() if b_eq is not None else None
        bounds_list = None
        if bounds is not None:
            bounds_mat = np.array(bounds)
            if bounds_mat.shape[1] != 2 or bounds_mat.shape[0] != n_vars:
                return "bounds must be a 2D list of [min, max] pairs for each variable."
            bounds_list = [tuple(row) for row in bounds_mat]
        if method is not None and not isinstance(method, str):
            return "method must be a string or None."
        lp_method = method if method is not None else 'highs'
        result = linprog(
            c_vec,
            A_ub=A_ub_mat,
            b_ub=b_ub_vec,
            A_eq=A_eq_mat,
            b_eq=b_eq_vec,
            bounds=bounds_list,
            method=lp_method
        )
        if not result.success:
            return f"Linear programming failed: {result.message}"
        return [[*list(result.x), float(result.fun)]]
    except Exception as e:
        return f"Error during linear programming: {str(e)}"

Live Notebook

Edit this function in a live notebook .