It is necessary to solve the LPP using a graphical method, or rather to write a program by analogy.

The task:

enter image description here

There were several problems with programming:

After substituting x1 and x2 of some values, we get the coordinates of 3 straight lines + their directions. Find the intersection point of the line. They and directions will form DHS.

After you need to draw a gradient, in my case it will be (2; 1) and look for a maximum from it. But how to do it in the program?

  • 3
    "How to find the intersection of two lines?" - solve a system of two linear equations with two unknowns. - Igor
  • one
    decipher anyone ZLP and DHS - Grundy
  • @Grundy: The LDC is apparently a range of acceptable values, but what the LPP means is that I have no versions. - VladD
  • @VladD, I only have the Linear Programming Task version, but it seems to me that it does not quite fit - Grundy

1 answer 1

The graphical method for solving the LPP is based on the construction of a convex polygon (simplex) that lies completely in the first quadrant. The initial approximation is the entire first quadrant, i.e. a triangle with vertices (0,0), (Inf, 0), (0, Inf), where Inf is infinity to be cut off.

The ideal variant for “cutting off” is an inequality of the form ax 1 + bx 2 <= c, (a> 0, b> 0, c> 0), which eliminates both singular vertices. In this case, there is no such inequality, but there is a first inequality (a 1 > 0, c 1 > 0), and the second inequality, which after multiplying by "-1" gives (b 2 > 0, c 2 > 0), and the point the intersections M (x, y) of the corresponding lines lie in the first quadrant. This means that a simplex with vertices (0,0), (c 1 / a 1 , 0), (x, y), (0, c 2 / a 2 ) is obtained . Vertices follow in a counterclockwise order, in the same order they should be stored.

Each new inequality will cut off on the simplex a group of adjacent points that do not satisfy it, and replace them with a couple of new ones. The algorithm is simple if the equations of the lines connecting it with the previous and subsequent ones are attached to each vertex and the cyclic order of the vertices is preserved.

If all vertices of the simplex are known, then the maximum of the objective function is reached in one of them. The starting point can be chosen from considerations of convenience of implementation, the direction of the bypass - in the direction of increasing the objective function. For any direction of the bypass, you can take the first local maximum.