How

How to solve a linear program using scipy

A general linear program of the form

\[\begin{split} \begin{align} \text{minimise: } c^t x& \\ \text{subject to: } & \nonumber \\ A_{\text{ub}}x&\leq b_{\text{ub}}\\ A_{\text{eq}}x&= b_{\text{eq}}\\ \end{align} \end{split}\]

can be solved using:

Tip

scipy.optimize.linprog(c, A_ub, b_ub, A_eq, b_eq)

For example:

import numpy as np
import scipy.optimize

c = np.array((-2, -2, -3, -1))
A_ub = np.array(
        [[2, -3, -3, 1], [3, 4, 1, 1], [-2, 1, 1, 1]]
    )
b_ub = np.array([[3], [2], [1]])
A_eq = np.array([[1, 1, 2, 1]])
b_eq = np.array([1])

scipy.optimize.linprog(c=c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq)

        message: Optimization terminated successfully. (HiGHS Status 7: Optimal)
        success: True
         status: 0
            fun: -1.8000000000000005
              x: [ 6.000e-01  0.000e+00  2.000e-01  0.000e+00]
            nit: 2
          lower:  residual: [ 6.000e-01  0.000e+00  2.000e-01  0.000e+00]
                 marginals: [ 0.000e+00  2.000e-01  0.000e+00  6.000e-01]
          upper:  residual: [       inf        inf        inf        inf]
                 marginals: [ 0.000e+00  0.000e+00  0.000e+00  0.000e+00]
          eqlin:  residual: [ 0.000e+00]
                 marginals: [-1.400e+00]
        ineqlin:  residual: [ 2.400e+00  0.000e+00  2.000e+00]
                 marginals: [-0.000e+00 -2.000e-01 -0.000e+00]
 mip_node_count: 0
 mip_dual_bound: 0.0
        mip_gap: 0.0