Presentation on linear programming. Presentation: Linear programming, solving problems using the simplex method

By clicking on the "Download archive" button, you will download the file you need completely free of charge.
Before downloading this file, think about those good essays, tests, term papers, dissertations, articles and other documents that are lying unclaimed on your computer. This is your work, it should participate in the development of society and benefit people. Find these works and submit them to the knowledge base.
We and all students, graduate students, young scientists who use the knowledge base in their studies and work will be very grateful to you.

To download an archive with a document, enter a five-digit number in the field below and click the "Download archive" button

Slide captions:

Solving the simplest linear programming problems using the graphical method 04/17/2012.

If the system of constraints of a linear programming problem is represented as a system of linear inequalities with two variables, then such a problem can be solved geometrically.

Task. There are 14 radio relay communication (RRC) channels and 9 tropospheric channels. On them it is necessary to transmit information of 3 types: A, B, C. Moreover, information A is equal to 600 USD, B – 3000 USD, C – 5500 USD. (information can be understood as the number of telephone conversations, data transfers, etc.). The capabilities of the channels and the costs of servicing each channel are given in the table. It is necessary to find the number of channels of both types involved, necessary to transmit the required information, so that the cost of operation is minimal.

Types of information Communication channels Required amount of information, units Tropospheric RRS A 80 40 600 B - 1000 3000 C 300 800 5500 Costs of servicing one channel, rub. 3000 2000

Stages of solving the ZLP: Construct the SDR. Construct the gradient vector of the objective function at some point X 0 belonging to the ODR – (c 1 ;c 2) . Construct a straight line c 1 x 1 + c 2 x 2 = h, where h is any positive number, preferably such that the drawn straight line passes through the solution polygon.

Move the found straight line parallel to itself in the direction of the gradient vector until the straight line leaves the ODR (when searching for the maximum) or in the opposite direction (when searching for the minimum). At the limit point, the objective function reaches a maximum (minimum), or the unboundedness of the function on the set of solutions is established. Determine the coordinates of the maximum (minimum) point of the function and calculate the value of the function at this point.

On the topic: methodological developments, presentations and notes

This development can be used as a general lesson on the topic “Systems of inequalities with two variables” in grade 9 (algebra 9 edited by Telyakovsky) and as a review lesson on this topic in grade 10. ...

The material is intended for advanced level students. The program discusses the algorithm for compiling the basic and reference plans using different methods and finding the optimal solution...

A workbook for a mathematics lesson on the topic “Linear programming problems” was developed by me for the mathematics lesson of the same name (advanced level). can be used in class, seminar...

Slide 2

Linear programming

Linear programming methods are used in forecast calculations, in planning and organizing production processes.

Linear programming is a branch of mathematics that studies methods for investigating and finding extreme values of a linear function whose arguments are subject to linear constraints.

Slide 3

Such a linear function is called a target function, and a set of quantitative relationships between variables expressing certain requirements of an economic problem in the form of equations or inequalities is called a system of constraints. The word programming was introduced due to the fact that unknown variables usually determine the program or work plan of some subject.

Slide 4

A set of relations containing an objective function and restrictions on its arguments is called a mathematical model of an optimization problem. ZLP is written in general form as follows: with restrictions

Slide 5

Here are unknown, given constant quantities. Constraints can be specified by equations.

The most common problems are in the form: there are resources with limitations. It is necessary to determine the volumes of these resources at which the objective function will reach a maximum (minimum), i.e., find the optimal distribution of limited resources. In this case, there are natural restrictions >0.

Slide 6

In this case, the extremum of the objective function is sought on an admissible set of solutions determined by the system of restrictions, and all or some of the inequalities in the system of restrictions can be written in the form of equations.

Slide 7

To compile a mathematical model of the ZLP, it is necessary to: 1) designate the variables;

2) create an objective function;

3) write down a system of restrictions in accordance with the purpose of the problem;

4) write down a system of restrictions taking into account the indicators available in the problem statement.

If all the constraints of a problem are given by equations, then a model of this type is called canonical. If at least one of the constraints is given by an inequality, then the model is non-canonical.

Slide 9

Examples of tasks that can be reduced to PPLs.

the problem of optimal resource allocation when planning production at an enterprise (the assortment problem); the task of maximizing product output for a given assortment; problem about mixtures (ration, diet, etc.); transport problem; the task of rational use of existing capacities; assignment problem.

Slide 10

1.The problem of optimal resource allocation.

Let's assume that an enterprise produces various products. Their production requires various types of resources (raw materials, working and machine time, auxiliary materials). These resources are limited and amount to conventional units during the planning period. Technological coefficients are also known, which indicate how many units of the i-th resource are required to produce a product of the j-th type. Let the profit received by the enterprise when selling a unit of product of the jth type be equal. During the planning period, all indicators are assumed to be constant.

Slide 11

It is required to draw up a production plan in which the enterprise's profit would be greatest.

Economic and mathematical model of the problem
Slide 12

The target function represents the total profit from the sale of manufactured products of all types. In this problem model, optimization is possible by selecting the most profitable types of products. Constraints mean that for any resource, its total consumption for the production of all types of products does not exceed its reserves.
Slide 13

Examples
Now let's create the objective function. The profit from the sale of products of type A will be 10, from the sale of products of type B -14 and from the sale of products of type C-12. The total profit from the sale of all products will be

Slide 17
Thus, we arrive at the following ZLP: It is required to find among all non-negative solutions of the system of inequalities one at which the objective function takes the maximum value.

Slide 18
Example 2

The products of the city dairy plant are milk, kefir and sour cream, packaged in containers. To produce 1 ton of milk, kefir and sour cream, 1010, 1010 and 9450 kg of milk are required, respectively. At the same time, the labor time required for bottling 1 ton of milk and kefir is 0.18 and 0.19 machine hours. Special machines are busy packaging 1 ton of sour cream for 3.25 hours.

Slide 19
In total, the plant can use 136,000 kg of milk to produce whole milk products. The main equipment can be occupied for 21.4 machine hours, and sour cream packaging machines for 16.25 hours. Profit from the sale of 1 ton of milk, kefir and sour cream is respectively 30, 22 and 136 rubles. The plant must produce at least 100 tons of bottled milk daily. There are no restrictions on the production of other products.

Slide 20
It is necessary to determine what products and in what quantities the plant should produce daily in order to maximize the profit from its sale. Create a mathematical model of the problem.

Slide 21
Solution

Let the plant produce tons of milk, tons of kefir and tons of sour cream.

Then he needs kg of milk.
Since the plant can use no more than 136,000 kg of milk daily, the inequality must be satisfied

Slide 22
Time restrictions on the packaging of milk and kefir and on the packaging of sour cream.

Since at least 100 tons of milk should be produced daily, then.
From an economic point of view

Slide 23

The total profit from the sale of all products is equal to RUB. Thus, we come to the following problem: with restrictions Since the objective function is linear and the restrictions are specified by a system of inequalities, this problem is a ZLP.
Slide 24
Problem about mixtures.
Solution

There are two types of products containing nutrients (fats, proteins, etc.)

Slide 25
Mathematical formulation of the problem: create a daily diet that satisfies the system of constraints and minimizes the objective function.

In general, the group of problems about mixtures includes problems of finding the cheapest set of certain starting materials that ensure the production of a mixture with given properties. The resulting mixtures must contain n different components in certain quantities, and the components themselves are components of m starting materials.
Slide 28

Let us introduce the following notation: -the amount of the j-th material included in the mixture; -price of material of the jth type; is the minimum required content of the i-th component in the mixture.
The coefficients show the specific gravity of the i-th component in a unit of the j-th material

Slide 29

Economic and mathematical model of the problem.
The objective function represents the total cost of the mixture, and the functional restrictions are restrictions on the content of components in the mixture: the mixture must contain components in volumes not less than those specified.

Slide 30

Cutting problem
In a garment factory, fabric can be cut in several ways to produce the desired parts of garments. Let the j-th cutting option produce parts of the i-th type, and the amount of waste for this cutting option is equal to Knowing that parts of the i-th type should be made in pieces, it is necessary to cut the fabric so that the required number of parts of each type is obtained with minimal total waste. Create a mathematical model of the problem.
Slide 31
Solution. Let's assume that hundreds of fabrics are cut using the jth option. Since when cutting fabric according to the j-th option, parts of the i-th type are obtained, for all cutting options from the fabrics used, the total amount of waste for all cutting options will be

Slide 35

The main task of the LP
Def.4. The main or canonical ZLP is the task consisting of determining the value of the objective function, provided that the system of constraints is presented in the form of a system of equations:

Slide 36
A support plan is called non-degenerate if it contains m positive components. Otherwise it is called degenerate.

The plan in which the ZLP objective function takes its maximum (minimum) value is called optimal.

View all slides

Decision making under uncertainty If the first subject has m strategies, and the second has n strategies, then we are said to be dealing with an m x n game. Consider the game m x n. Let a set of strategies be given: for the first player (Ai), for the second player (Bj), a payment matrix, where aij is the gain of the first player or the loss of the second player when they choose strategies Ai and Bj, respectively. Each player chooses uniquely with probability I some strategy, i.e. uses a pure strategy when choosing a solution. In this case, the solution to the game will be in pure strategies. Since the interests of the players are opposite, the first player seeks to maximize his winnings, and the second player, on the contrary, minimizes his losses. The solution to the game is to determine the best strategy for each player. The choice of the best strategy by one player is carried out in the complete absence of information about the decision being made by the second player.

Presentation on linear programming. Presentation: Linear programming, solving problems using the simplex method

Similar documents

Slide captions:

On the topic: methodological developments, presentations and notes

Linear programming

3) write down a system of restrictions in accordance with the purpose of the problem;

Slide 9

It is required to draw up a production plan in which the enterprise's profit would be greatest.

Example 2

Solution

From an economic point of view

Slide 24

Solution

The coefficients show the specific gravity of the i-th component in a unit of the j-th material

The objective function represents the total cost of the mixture, and the functional restrictions are restrictions on the content of components in the mixture: the mixture must contain components in volumes not less than those specified.

Solution. Let's assume that hundreds of fabrics are cut using the jth option. Since when cutting fabric according to the j-th option, parts of the i-th type are obtained, for all cutting options from the fabrics used, the total amount of waste for all cutting options will be