Cara menggunakan vector optimization python

Example 1

Let’s first solve the linear programming problem from above:

$ sudo dnf install glpk-utils

• Instead of maximizing z = x + 2y, you can minimize its negative(−z = −x − 2y).
• Instead of having the greater than or equal to sign, you can multiply the yellow inequality by −1 and get the opposite less than or equal to sign (≤).

After introducing these changes, you get a new system:

This system is equivalent to the original and will have the same solution. The only reason to apply these changes is to overcome the limitations of SciPy related to the problem formulation.

The next step is to define the input values:

>>>

>>> obj = [-1, -2]
>>> #      ─┬  ─┬
>>> #       │   └┤ Coefficient for y
>>> #       └────┤ Coefficient for x

>>> lhs_ineq = [[ 2,  1],  # Red constraint left side
...             [-4,  5],  # Blue constraint left side
...             [ 1, -2]]  # Yellow constraint left side

>>> rhs_ineq = [20,  # Red constraint right side
...             10,  # Blue constraint right side
...              2]  # Yellow constraint right side

>>> lhs_eq = [[-1, 5]]  # Green constraint left side
>>> rhs_eq = [15]       # Green constraint right side

You put the values from the system above into the appropriate lists, tuples, or NumPy arrays:

• $ sudo dnf install glpk-utils
  

  9 holds the coefficients from the objective function.

• $ conda install -c conda-forge glpk
  

  0 holds the left-side coefficients from the inequality (red, blue, and yellow) constraints.

• $ conda install -c conda-forge glpk
  

  1 holds the right-side coefficients from the inequality (red, blue, and yellow) constraints.

• $ conda install -c conda-forge glpk
  

  2 holds the left-side coefficients from the equality (green) constraint.

• $ conda install -c conda-forge glpk
  

  3 holds the right-side coefficients from the equality (green) constraint.

Note: Please, be careful with the order of rows and columns!

The order of the rows for the left and right sides of the constraints must be the same. Each row represents one constraint.

The order of the coefficients from the objective function and left sides of the constraints must match. Each column corresponds to a single decision variable.

The next step is to define the bounds for each variable in the same order as the coefficients. In this case, they’re both between zero and positive infinity:

>>>

>>> bnd = [(0, float("inf")),  # Bounds of x
...        (0, float("inf"))]  # Bounds of y

This statement is redundant because

$ sudo dnf install glpk-utils

Note: Instead of , you can use , , or

$ conda install -c conda-forge glpk

Finally, it’s time to optimize and solve your problem of interest. You can do that with

$ sudo dnf install glpk-utils

>>>

$ pulptest

The parameter

$ glpsol --version

$ glpsol --version

$ glpsol --version

$ glpsol --version

$ glpsol --version

$ glpsol --version

You can use the parameter

$ glpsol --version

1. $ glpsol --version
   

   7 selects the interior-point method. This option is set by default.

2. $ glpsol --version
   

   8 selects the revised two-phase simplex method.

3. $ glpsol --version
   

   9 selects the legacy two-phase simplex method.

$ sudo dnf install glpk-utils

• >>> from scipy.optimize import linprog
  

  1 is the equality constraints residuals.

• >>> from scipy.optimize import linprog
  

  2 is the objective function value at the optimum (if found).

• >>> from scipy.optimize import linprog
  

  3 is the status of the solution.

• >>> from scipy.optimize import linprog
  

  4 is the number of iterations needed to finish the calculation.

• >>> from scipy.optimize import linprog
  

  5 is the values of the slack variables, or the differences between the values of the left and right sides of the constraints.

• >>> from scipy.optimize import linprog
  

  6 is an integer between

  >>> from scipy.optimize import linprog
  

  7 and

  >>> from scipy.optimize import linprog
  

  8 that shows the status of the solution, such as

  >>> from scipy.optimize import linprog
  

  7 for when the optimal solution has been found.

• >>> obj = [-1, -2]
  >>> #      ─┬  ─┬
  >>> #       │   └┤ Coefficient for y
  >>> #       └────┤ Coefficient for x
  
  >>> lhs_ineq = [[ 2,  1],  # Red constraint left side
  ...             [-4,  5],  # Blue constraint left side
  ...             [ 1, -2]]  # Yellow constraint left side
  
  >>> rhs_ineq = [20,  # Red constraint right side
  ...             10,  # Blue constraint right side
  ...              2]  # Yellow constraint right side
  
  >>> lhs_eq = [[-1, 5]]  # Green constraint left side
  >>> rhs_eq = [15]       # Green constraint right side
  

  0 is a Boolean that shows whether the optimal solution has been found.

• >>> obj = [-1, -2]
  >>> #      ─┬  ─┬
  >>> #       │   └┤ Coefficient for y
  >>> #       └────┤ Coefficient for x
  
  >>> lhs_ineq = [[ 2,  1],  # Red constraint left side
  ...             [-4,  5],  # Blue constraint left side
  ...             [ 1, -2]]  # Yellow constraint left side
  
  >>> rhs_ineq = [20,  # Red constraint right side
  ...             10,  # Blue constraint right side
  ...              2]  # Yellow constraint right side
  
  >>> lhs_eq = [[-1, 5]]  # Green constraint left side
  >>> rhs_eq = [15]       # Green constraint right side
  

  1 is a NumPy array holding the optimal values of the decision variables.

You can access these values separately:

>>>

$ pulptest

That’s how you get the results of optimization. You can also show them graphically:

As discussed earlier, the optimal solutions to linear programming problems lie at the vertices of the feasible regions. In this case, the feasible region is just the portion of the green line between the blue and red lines. The optimal solution is the green square that represents the point of intersection between the green and red lines.

If you want to exclude the equality (green) constraint, just drop the parameters

$ glpsol --version

$ glpsol --version

$ sudo dnf install glpk-utils

>>>

$ pulptest

The solution is different from the previous case. You can see it on the chart:

In this example, the optimal solution is the purple vertex of the feasible (gray) region where the red and blue constraints intersect. Other vertices, like the yellow one, have higher values for the objective function.

Example 2

You can use SciPy to solve the resource allocation problem stated in the :

As in the previous example, you need to extract the necessary vectors and matrix from the problem above, pass them as the arguments to

>>> obj = [-1, -2]
>>> #      ─┬  ─┬
>>> #       │   └┤ Coefficient for y
>>> #       └────┤ Coefficient for x

>>> lhs_ineq = [[ 2,  1],  # Red constraint left side
...             [-4,  5],  # Blue constraint left side
...             [ 1, -2]]  # Yellow constraint left side

>>> rhs_ineq = [20,  # Red constraint right side
...             10,  # Blue constraint right side
...              2]  # Yellow constraint right side

>>> lhs_eq = [[-1, 5]]  # Green constraint left side
>>> rhs_eq = [15]       # Green constraint right side

>>>

$ pulptest

The result tells you that the maximal profit is

>>> obj = [-1, -2]
>>> #      ─┬  ─┬
>>> #       │   └┤ Coefficient for y
>>> #       └────┤ Coefficient for x

>>> lhs_ineq = [[ 2,  1],  # Red constraint left side
...             [-4,  5],  # Blue constraint left side
...             [ 1, -2]]  # Yellow constraint left side

>>> rhs_ineq = [20,  # Red constraint right side
...             10,  # Blue constraint right side
...              2]  # Yellow constraint right side

>>> lhs_eq = [[-1, 5]]  # Green constraint left side
>>> rhs_eq = [15]       # Green constraint right side

1. The third product brings the largest profit per unit, so the factory will produce it the most.

2. The first slack is

   >>> from scipy.optimize import linprog
   

   7, which means that the values of the left and right sides of the manpower (first) constraint are the same. The factory produces

   >>> obj = [-1, -2]
   >>> #      ─┬  ─┬
   >>> #       │   └┤ Coefficient for y
   >>> #       └────┤ Coefficient for x
   
   >>> lhs_ineq = [[ 2,  1],  # Red constraint left side
   ...             [-4,  5],  # Blue constraint left side
   ...             [ 1, -2]]  # Yellow constraint left side
   
   >>> rhs_ineq = [20,  # Red constraint right side
   ...             10,  # Blue constraint right side
   ...              2]  # Yellow constraint right side
   
   >>> lhs_eq = [[-1, 5]]  # Green constraint left side
   >>> rhs_eq = [15]       # Green constraint right side
   

   8 units per day, and that’s its full capacity.

3. The second slack is

   >>> obj = [-1, -2]
   >>> #      ─┬  ─┬
   >>> #       │   └┤ Coefficient for y
   >>> #       └────┤ Coefficient for x
   
   >>> lhs_ineq = [[ 2,  1],  # Red constraint left side
   ...             [-4,  5],  # Blue constraint left side
   ...             [ 1, -2]]  # Yellow constraint left side
   
   >>> rhs_ineq = [20,  # Red constraint right side
   ...             10,  # Blue constraint right side
   ...              2]  # Yellow constraint right side
   
   >>> lhs_eq = [[-1, 5]]  # Green constraint left side
   >>> rhs_eq = [15]       # Green constraint right side
   

   9 because the factory consumes 60 units of raw material A (15 units for the first product plus 45 for the third) out of a potential

   >>> bnd = [(0, float("inf")),  # Bounds of x
   ...        (0, float("inf"))]  # Bounds of y
   

   0 units.

4. The third slack is

   >>> from scipy.optimize import linprog
   

   7, which means that the factory consumes all

   >>> bnd = [(0, float("inf")),  # Bounds of x
   ...        (0, float("inf"))]  # Bounds of y
   

   2 units of the raw material B. This entire amount is consumed for the third product. That’s why the factory can’t produce the second or fourth product at all and can’t produce more than

   >>> bnd = [(0, float("inf")),  # Bounds of x
   ...        (0, float("inf"))]  # Bounds of y
   

   3 units of the third product. It lacks the raw material B.

>>> bnd = [(0, float("inf")),  # Bounds of x
...        (0, float("inf"))]  # Bounds of y

>>> from scipy.optimize import linprog

>>> bnd = [(0, float("inf")),  # Bounds of x
...        (0, float("inf"))]  # Bounds of y

>>> bnd = [(0, float("inf")),  # Bounds of x
...        (0, float("inf"))]  # Bounds of y

SciPy’s linear programming capabilities are useful mainly for smaller problems. For larger and more complex problems, you might find other libraries more suitable for the following reasons:

• SciPy can’t run various external solvers.

• SciPy can’t work with integer decision variables.

• SciPy doesn’t provide classes or functions that facilitate model building. You have to define arrays and matrices, which might be a tedious and error-prone task for large problems.

• SciPy doesn’t allow you to define maximization problems directly. You must convert them to minimization problems.

• SciPy doesn’t allow you to define constraints using the greater-than-or-equal-to sign directly. You must use the less-than-or-equal-to instead.

Fortunately, the Python ecosystem offers several alternative solutions for linear programming that are very useful for larger problems. One of them is PuLP, which you’ll see in action in the next section.

Example 1

You’ll now solve this system with PuLP:

The first step is to initialize an instance of to represent your model:

$ pulptest

You use the

>>> bnd = [(0, float("inf")),  # Bounds of x
...        (0, float("inf"))]  # Bounds of y

$ pulptest

$ pulptest

Once that you have the model, you can define the decision variables as instances of the class:

$ pulptest

You need to provide a lower bound with

$ pulptest

$ pulptest

The optional parameter

$ pulptest

$ pulptest

You can use the variables

$ pulptest

$ pulptest

>>>

$ pulptest

When you multiply a decision variable with a scalar or build a linear combination of multiple decision variables, you get an instance of that represents a linear expression.

Note: You can add or subtract variables or expressions, and you can multiply them with constants because PuLP classes implement some of the that like , , and . These methods are used to customize the behavior of operators like

$ pulptest

$ pulptest

$ pulptest

Similarly, you can combine linear expressions, variables, and scalars with the operators

$ pulptest

$ pulptest

$ pulptest

Note: It’s also possible to build constraints with the rich comparison methods , , and that define the behavior of the operators

$ pulptest

$ pulptest

$ pulptest

Having this in mind, the next step is to create the constraints and objective function as well as to assign them to your model. You don’t need to create lists or matrices. Just write Python expressions and use the

$ pulptest

$ pulptest

In the above code, you define tuples that hold the constraints and their names.

>>> bnd = [(0, float("inf")),  # Bounds of x
...        (0, float("inf"))]  # Bounds of y

$ pulptest

Setting the objective function is very similar:

$ pulptest

Alternatively, you can use a shorter notation:

$ brew install glpk

Now you have the objective function added and the model defined.

Note: You can append a constraint or objective to the model with the operator

$ pulptest

>>> bnd = [(0, float("inf")),  # Bounds of x
...        (0, float("inf"))]  # Bounds of y

$ pulptest

For larger problems, it’s often more convenient to use with a list or other sequence than to repeat the

$ pulptest

$ brew install glpk

It produces the same result as the previous statement.

You can now see the full definition of this model:

>>>

$ brew install glpk

The string representation of the model contains all relevant data: the variables, constraints, objective, and their names.

Note: String representations are built by defining the special method . For more details about

$ pulptest

$ pulptest

$ pulptest

Finally, you’re ready to solve the problem. You can do that by calling on your model object. If you want to use the default solver (CBC), then you don’t need to pass any arguments:

$ brew install glpk

$ pulptest

$ pulptest

$ pulptest

You can get the optimization results as the attributes of

$ pulptest

$ pulptest

>>>

$ brew install glpk

$ pulptest

$ pulptest

$ pulptest

$ pulptest

$ pulptest

>>>

$ brew install glpk

As you can see, this list contains the exact objects that are created with the constructor of

$ pulptest

The results are approximately the same as the ones you got with SciPy.

Note: Be careful with the method

$ pulptest

$ pulptest

$ pulptest

You can see which solver was used by calling

$ pulptest

>>>

$ brew install glpk

The output informs you that the solver is CBC. You didn’t specify a solver, so PuLP called the default one.

If you want to run a different solver, then you can specify it as an argument of

$ pulptest

$ pulptest

$ brew install glpk

Now that you have GLPK imported, you can use it inside

$ pulptest

$ brew install glpk

The

$ pulptest

$ pulptest

$ pulptest

$ pulptest

Your model is defined and solved, so you can inspect the results the same way you did in the previous case:

>>>

$ brew install glpk

You got practically the same result with GLPK as you did with SciPy and CBC.

Let’s peek and see which solver was used this time:

>>>

$ sudo apt install glpk glpk-utils

As you defined above with the highlighted statement

$ pulptest

You can also use PuLP to solve mixed-integer linear programming problems. To define an integer or binary variable, just pass

$ pulptest

$ pulptest

$ pulptest

$ sudo apt install glpk glpk-utils

In this example, you have one integer variable and get different results from before:

>>>

$ sudo apt install glpk glpk-utils

Now

$ pulptest

As you can see, the optimal solution is the rightmost green point on the gray background. This is the feasible solution with the largest values of both

$ pulptest

$ pulptest

GLPK is capable of solving such problems as well.

Example 2

Now you can use PuLP to solve the resource allocation problem from above:

The approach for defining and solving the problem is the same as in the previous example:

$ sudo apt install glpk glpk-utils

In this case, you use the dictionary

$ pulptest

$ pulptest

$ pulptest

The code above produces the following result:

$ sudo apt install glpk glpk-utils

As you can see, the solution is consistent with the one obtained using SciPy. The most profitable solution is to produce

$ pulptest

$ pulptest

Let’s make this problem more complicated and interesting. Say the factory can’t produce the first and third products in parallel due to a machinery issue. What’s the most profitable solution in this case?

Now you have another logical constraint: if x₁ is positive, then x₃ must be zero and vice versa. This is where binary decision variables are very useful. You’ll use two binary decision variables, y₁ and y₃, that’ll denote if the first or third products are generated at all:

$ sudo apt install glpk glpk-utils

The code is very similar to the previous example except for the highlighted lines. Here are the differences:

• Line 5 defines the binary decision variables

  $ pulptest
  

  77 and

  $ pulptest
  

  78 held in the dictionary

  $ pulptest
  

  10.

• Line 12 defines an arbitrarily large number

  $ pulptest
  

  80. The value

  >>> bnd = [(0, float("inf")),  # Bounds of x
  ...        (0, float("inf"))]  # Bounds of y
  

  0 is large enough in this case because you can’t have more than

  >>> bnd = [(0, float("inf")),  # Bounds of x
  ...        (0, float("inf"))]  # Bounds of y
  

  0 units per day.

• Line 13 says that if

  $ pulptest
  

  77 is zero, then

  $ pulptest
  

  84 must be zero, else it can be any non-negative number.

• Line 14 says that if

  $ pulptest
  

  78 is zero, then

  $ pulptest
  

  86 must be zero, else it can be any non-negative number.

• Line 15 says that either

  $ pulptest
  

  77 or

  $ pulptest
  

  78 is zero (or both are), so either

  $ pulptest
  

  84 or

  $ pulptest
  

  86 must be zero as well.

Here’s the solution:

$ sudo apt install glpk glpk-utils

It turns out that the optimal approach is to exclude the first product and to produce only the third one.