Creating Integer Range from multiple string math expressions in python-CodePudding

I have a problem in a project and I've searched the internet high and low with no clear answer. How can i convert math expressions As 3x 5y >= 100 And x,y < 500 Into a range of x and range of y to be used as ristriction in a math problem, Ex: f = x^2 4y The end result is to find the largest answer using genetic algorithms where x and y are ristricted in value.

Tried sympy and eval with no luck Searched every and found only a few helpful but not enough resources I need just to translate the user input to the code for the genetic algorithm to use.

CodePudding user response：

Your set of linear inequations define a polygon in the plane.

The edges of this polygon are the lines defined by each equality that you get by replacing the inequal sign by an equal sign in an inequality.

The vertices of this polygon are the intersections of two adjacent edges; equivalently, they are the intersections of two edges that satisfy the system of (large) inequalities.

So, one way to find all the vertices of the polygon is to find every intersection point by solving every subsystem of two equalities, then filtering out the points that are outside of the polygon.

import numpy as np
from numpy.linalg import solve, LinAlgError
from itertools import combinations
import matplotlib.pyplot as plt

A = np.array([[-3, -5],[1,0],[0,1]])
b = np.array([-100,500,500])

# find polygon for system of linear inequations
# expects input in "less than" form:
# A X <= b
def get_polygon(A, b, tol = 1e-5):
    polygon = []
    for subsystem in map(list, combinations(range(len(A)), 2)):
        try:
            polygon.append(solve(A[subsystem], b[subsystem])) # solve subsystem of 2 equalities
        except LinAlgError:
            pass
    polygon = np.array(polygon)
    polygon = polygon[(polygon @ A.T <= b   tol).all(axis=1)] # filter out points outside of polygon
    return polygon

polygon = get_polygon(A, b)
polygon = np.vstack((polygon, polygon[0])) # duplicate first point of polygon to "close the loop" before plotting
plt.plot(polygon[:,0], polygon[:,1])
plt.show()

Note that get_polygon will find all vertices of the polygon, but if there are more than 3, they might not be ordered in clockwise order.

If you want to sort the vertices in clockwise order before plotting the polygon, I refer you to this question:

How to sort a list of points in clockwise/anticlockwise in python?

CodePudding user response：

Using @Stef's approach in SymPy would give the triangular region of interest like this:

>>> from sympy.abc import x, y
>>> from sympy import intersection, Triangle, Line
>>> eqs = Eq(3*x 5*y,100), Eq(x,500), Eq(y,500)
>>> Triangle(*intersection(*[Line(eq) for eq in eqs], pairwise=True))
Triangle(Point2D(-800, 500), Point2D(500, -280), Point2D(500, 500))

So x is in range [-800, 500] and y is in range [m, 500] where m is the y value calculated from the equation of the diagonal:

m = solve(eqs[0], y)[0]  # m(x)
def yval(xi):
    if xi <-800 or xi > 500:
        return
    return m.subs(x,xi)
yval(300) # -> -160