Problems of linear programming problem statement: solution methods and formation

For economists, it is often necessary to optimize a production function, maximize or minimize it, such as profit, loss, or other data subject to a linear constraint. Understanding linear programming problems and setting problems - this requires knowledge of the basics of mathematics and statistics. The task of linear programming (LP) is to define a function to obtain optimal data. It is one of the most important business operations research tools. It is also widely used as a decision aid in many industries such as economics, computer science, mathematics and other modern practical research.

Characteristics of linear programming problems

The following characteristics of LP are distinguished:

1. Optimization. The basis of linear programming problems and the formulation of optimization problems is the maximization of eitherminimization of some database, which is the subject of research. This is common in economics, business, advertising, and many other areas that require efficiency in order to conserve resources. This includes profit making, resource acquisition, production time and other important economic indicators.
2. Linearity. As the name implies, all LP problems have the sign of linearity. However, it is sometimes misleading, since linearity applies only to variables of the 1st degree, excluding power functions, square roots, and other non-linear relationships. However, it does not mean that the functions of the LP problem have only one variable. It treats variables as coordinates of points on a line, excluding any curvature.
3. Objective function. The basis of linear programming problems and the formulation of objectivity problems are variables that can be changed at will, for example, time spent on work, units of goods produced. The objective function is written with a capital "Z".
4. Restrictions. All LPs are limited to variables within the function. These limits take the form of inequalities, such as "b<3", where b can represent units of books written by the author per month. These inequalities establish how the objective function can be maximized/minimized, as together they define decision regions.

Conditions defining tasks

Companies strive to get the highest profitability in their activities, so they must make the most of the availabletheir resources: human, materials, equipment, facilities and others. LP is presented as a useful tool to help determine the best solution for a company.

Conditions for executing linear programming tasks and setting tasks are necessary to obtain the maximum net profit. In order to solve the LP problem, it must have:

1. Limits or limited resources, such as a limited number of employees, a maximum number of customers, or a limit on production losses.
2. Goal: maximizing revenue or minimizing costs.
3. Proportional linearity. Equations that generate decision variables must be linear.
4. Homogeneity: The characteristics of the decision variables and resources are the same. For example, a person's hours of work are equally productive, or goods made by a machine are identical.
5. Divisibility: Products and resources can be shown as a fraction.
6. No negativity: solutions must be positive or zero.

Objectivity of a function in the formulation of the main problem of linear programming mathematically expresses the goal that must be achieved in solving the problem. For example, to maximize the company's profit or minimize production costs.

This is represented by a variable solution equation, where: X 1, X 2, X 3, …, X n are solution variables; C 1, C 2, C 3, …, C n are constants.

Each constraint is expressed mathematically with any of these features:

1. Less than or equal (≦). When there is an upper limit,for example, overtime cannot be more than 2 hours per day.
2. Equal (=). Specifies a mandatory relationship, such as ending stock equals opening stock plus production minus sales.
3. Greater than or equal to (≧). For example, when there is a floor, the production of a certain product must be higher than the projected demand.
4. The general formulation of a linear programming problem begins with setting constraints.
5. Any LP task must have one or more constraints.
6. The positivity of the decision variables must be considered within the constraints.

Stages of setting goals

The general formulation of the problem of linear programming and its formulation refers to the translation of a real problem into the form of mathematical equations that can be solved.

Integer linear programming problem statement steps:

1. Define a number that reveals the behavior of the objective function to be optimized.
2. Find a set of constraints and express them as linear equations or inequalities. This will set the area in the n-dimensional space of optimized features.
3. It is necessary to impose a non-negativity condition on the task variables, that is, they must all be positive.
4. Express a function as a linear equation.
5. Optimize a function graphically or mathematically when doing a mathematical formulation of a linear programming problem.

Graphic method

Graphic methodused to perform LP tasks in two variables. This method is not applicable to problems that have three or more decision variables.

Standard problem of maximizing unknown LP problems, in which the function is increased, subject to constraints of the form:

x ≧ 0, y ≧ 0, z ≧ 0 and further shape restrictions:

Ax + By + C z +., ≦ N, where A, B, C and N are non-negative numbers.

Inequality should be "≦", not "=" or "≧".

The LP graphical method with two unknowns is as follows:

1. Set possible chart areas.
2. Calculate the angular coordinates of the points.
3. Substitute them in order to see the optimal value. This moment gives a solution to the LP problem.
4. Minimize the function and, if its coefficients are non-negative, the solution exists.

Identification of existing solutions:

1. Bound the area by adding a vertical line to the right of the rightmost corner point and a horizontal line above the highest corner point.
2. Calculate the coordinates of new corner points.
3. Find the corner point with the optimal value.
4. If it takes place at the starting point of an unbounded region, then the LP problem has a solution at this point. If not, then it does not have an optimal solution.

Drawing a set of solutions

Select a starting point and mark the blocking area.

Drawingthe area represented by the inequality of two variables in the formulation of the linear programming problem. Briefly for example:

1. Draw a line obtained by replacing inequality with equality.
2. Select a control point, (0, 0). A good choice if the line goes through the beginning.
3. If the control point satisfies the inequality, then the solution set is the entire area on the same side of the line as the control point. Otherwise, she is on the other side of the line.
4. The allowable area is defined by a set of linear inequalities and is a set of points that satisfy all inequalities.
5. To draw it defined by a set of two-variable linear inequalities, execute the areas represented by each inequality on one graph, remembering to shade the parts of the plane that are not needed.

Simplex method for maximization

The formulation of a linear programming problem with a mathematical model for maximization can be performed using the simplex method:

1. Transform the data into a system of equations, introducing weak variables to turn the constraints into equations, and rewrite the function in standard form.
2. Write the original table.
3. Select the reversal column, the negative number with the largest value in the bottom row, excluding the rightmost entry. Its column is summary. If there are two candidates, choose one. If all numbers in the bottom row are zero or positive, excluding the rightmost entry, then alldone and the basic solution maximizes the objective function.
4. Select a bar in the column. The axis must always be a positive number. For each positive "b" entry in the summary column, the "a/b" ratio is calculated, where "a" is the answer in that row. The minimum is chosen from the test coefficients, then the corresponding number "b" will be the axis.
5. Use a pivot to clear the column in the usual way, making sure to follow exactly the guidelines for formulating string operations described in the Gauss-Jordan manual, and then swapping the labeled column from the column.
6. The variable that initially represents the summary row is the output, and the variable that represents the column is the input.

To get a base solution that matches any table in the simplex method, set to zero all variables that do not appear as row labels. The value of the displayed row label (active variable) is the number in the rightmost column in the row divided by the number in that row in the column labeled with the same variable.

Custom limits

To solve the LP problem with constraints of the form (Ax + By +.,.≧ N) with positive N, subtract the extra variable from the left side (instead of adding a weak variable). The base solution corresponding to the original table will not be feasible because some of the active variables will be negative. Therefore, the rules for the initial rotation are differentfrom above.

Next, mark all lines that give a negative value for the associated active variable, except for the target. If there are marked lines, you need to start from stage I.

I stage. Find the largest positive number in the first line. Use test factors as in the previous section to find the summary in this column, and then expand this entry. Repeat until no marked lines remain, then go to step II.

II stage uses the simplex method for the standard maximization problem. If there are any negative values in the lower left row after stage I, the method of standard maximization problems is used.

An example of a game that can be solved using the simplex method.

PHP Simplex Online Tool

Today, technological tools make many activities of professional life easier and LP's problem solving methods are no exception. Their advantage is that you can get the best solution from any computer with Internet access.

PHPSimplex is a great online tool for solving LP problems. This application can solve problems without limit on the number of variables and restrictions. For problems with two variables, it demonstrates a graphical solution and presents the entire process of calculating the optimal solution in a simple and understandable way. It has a friendly interface, close to the user, easy to use and intuitive, available on severallanguages.

WanerMath: applications without borders

Warneth provides 2 tools for solving linear programming problems:

1. Linear programming graph (two variables).
2. Simplex method.

Unlike other tools where only coefficients are placed, all functions with variables are included here. This is not a big problem for novice users, as the profile site has instructions for use. In addition, the site has an "Examples" function that automatically creates tasks so that the user can evaluate his work, for example, when setting up a linear programming transport problem.

JSimplex is another online tool. It allows you to solve LP problems without limiting the number of variables. It has a simple control interface, which prompts you to specify the purpose and the number of variables. The user writes down the coefficients of the objective function, constraints and clicks on "solve". Integration, best case calculation and results for each variable will be shown.

As you can see, these tools are extremely useful for easily learning linear programming solution procedures.

Simple LP example

The company produces portable and scientific calculators. Long-term projections indicate an expected daily demand for 150 scientific and 100 handheld calculators. The daily production capacity allows the production of no more than 250 scientific and 200 portable calculators daily.

To fulfill the contractfor delivery, a minimum of 250 calculators must be produced. The implementation of one - leads to a loss of 20 rubles, but each manual calculator brings a profit of 50 rubles. It is necessary to perform the calculation in order to get the maximum net profit.

Algorithm for executing the example of setting linear programming problems:

1. Decision variables. Since the optimal number of calculators was set, they will be the variables in this problem: x - the number of scientific calculators, y - the number of portable ones.
2. Set limits since a company cannot produce a negative number of calculators per day, the natural limit would be: x ≧ 0, y ≧ 0.
3. Lower bound: x ≧ 150, y ≧ 100.
4. Set an upper bound on these variables due to company production constraints: x ≦ 250, y ≦ 200.
5. Joint limitation on 'x' and 'y' values due to minimum shipping order: x + y ≧ 250
6. Optimize the net profit function: P=-20x + 50y.
7. Problem solution: maximizing P=-20x + 50y provided that 150 ≦ x ≦ 250; 100 ≦ y ≦ 200; x + y ≧ 250.

Applications

Among the applications of linear programming, the most common are:

1. Total sales and operations planning. The goal is to minimize production costs in the short term, such as three and six months to meet expected demand.
2. Product planning: find the optimalcombination of products, given that they require different resources and have different costs. As an example, you can find the optimal mixture of chemical elements for gasoline, paints, human diets and animal feed.
3. Production flow: determine the optimal flow for the production of a product, which must pass sequentially through several work processes, each with its own costs and production characteristics.
4. Formulation of the transport problem of linear programming, transportation schedule. The method is used to program multiple routes for a given number of vehicles to serve customers or receive materials to be transported between different locations. Each vehicle may have different load capacity and performance.
5. Inventory management: determining the optimal combination of products that will be in stock in the sales network.
6. Staff Programming: Developing a HR plan to meet expected variable demand for talent with as few staff as possible.
7. Waste control: Using linear programming, you can calculate how to reduce waste to a minimum.

These are some of the most common applications where linear programming is used. In general, any optimization problem that satisfies the above conditions can be solved with it.