TOPIC: LINEAR PROGRAMMING

TASK 2.A. Solving a linear programming problem by graphical method

Attention!

This is a TRIAL VERSION of work No. 2073, the price of the original is 200 rubles. Designed in Microsoft program Word.

Payment. Contacts.

Option 7. Find the maximum and minimum valueslinear function Ф = 2x 1 - 2 x 2with restrictions: x 1 + x 2 ≥ 4;

- x 1 + 2 x 2 ≤ 2;

x 1 + 2 x 2 ≤ 10;

x i ≥ 0, i = 1.2.

Solution:

By conditionally replacing the inequality signs with equality signs, we obtain a system of equations x1 + x2 = 4;

- x1 + 2 x2 = 2;

x1 + 2 x2 = 10.

Let us construct straight lines using these equations, then, in accordance with the signs of inequalities, we select the half-planes and obtain their common part - the region of admissible solutions of the ODR - the quadrilateral MNPQ.

Minimum function value

tions - at point M(2; 2)

Ф min = 2·2 - 2·2 = 0.

The maximum value is reached at point N (10; 0),

Ф max = 2·10 - 2·0 = 20.

Option 8. Find the maximum and minimum values

linear function Ф = x 1 + x 2

with restrictions: x 1 - 4 x 2 - 4 ≤ 0;

3 x 1 - x 2 ≥ 0;

x 1 + x 2 - 4 ≥ 0;

x i ≥ 0, i = 1.2.

Solution:

Conditionally replacing the inequality signs with equality signs, we obtain a system of equations x1 - 4 x2 = 4 ;

3 x1 - x2 = 0;

Let us construct straight lines using these equations, then, in accordance with the signs of inequalities, we select the half-planes and obtain their common part - the region of admissible solutions of the ODR - the unlimited polygon MNPQ.

Minimum function value

tions – on direct NP, for example

at point P(4; 0)

Ф min = 4 + 0 = 4.

The ODR is not limited from above, therefore, Ф max = + ∞.

Option 10. Find the maximum and minimum values

linear function Ф = 2 x 1 - 3 x 2

with restrictions: x 1 + 3 x 2 ≤ 18;

2 x 1 + x 2 ≤ 16;

x 2 ≤ 5;

x i ≥ 0, i = 1.2.

By conditionally replacing the inequality signs with equality signs, we obtain a system of equations

x 1 + 3 x 2 = 18 (1);

2 x 1 + x 2 = 16 (2);

3 x 1 = 21 (4).

Let's construct straight lines using these equations, then, in accordance with the signs of inequalities, select the half-planes and obtain their common part - the region of admissible solutions of the ODR - the MNPQRS polygon.

Let's construct the vector Г(2; -3) and draw through the origin of coordinates level line– straight.

We move the level line in the direction, the value of Ф increases. At point S(7; 0) the objective function reaches a maximum Ф max =2·7–3·0= = 14. We move the level line in the direction, the value of Ф decreases. The minimum value of the function is at point N(0; 5)

Ф min = 2·0 – 3·5 = –15.

TASK 2.B. Solving a linear programming problem

analytical simplex method

Option 7. Minimize the objective function Ф = x 1 - x 2 + x 3 + x 4 + x 5 - x 6

with restrictions: x 1 + x 4 +6 x 6 = 9,

3 x 1 + x 2 – 4 x 3 + 2 x 6 = 2,

x 1 + 2 x 3 + x 5 + 2 x 6 = 6.

Solution:

Number of unknowns n=6, number of equations m=3. Therefore, r = n-m = 3 unknowns can be taken as free. Let's choose x 1, x 3 and x 6.

We express the basic variables x 2 , x 4 and x 5 in terms of free ones and reduce the system to a unit basis

x 2 = 2 – 3 x 1 + 4 x 3 – 2 x 6

x 4 = 9 – x 1 – 6 x 6 (*)

x 5 = 6 – x 1 – 2 x 3 – 2 x 6

The objective function will look like:

Ф = x 1 - 2 + 3 x 1 - 4 x 3 + 2 x 6 + x 3 + 9 – x 1 – 6 x 6 +6 – x 1 – 2 x 3 – 2 x 6 – x 6 =

13 + 2 x 1 – 5 x 3 – 7 x 6

Let's put x 1 = x 3 = x 6 = 0, and the basic variables will take the values ​​x 2 = 2; x 4 = 9; x 5 = 6, that is, the first feasible solution (0; 2; 0; 9; 6; 0), objective function Ф 1 = 13.

The variables x 3 and x 6 are included in the objective function with negative coefficients, therefore, as their values ​​increase, the value of Ф will decrease. Let's take x 6 for example. From the 1st equation of the system (*) it is clear that an increase in the value of x 6 is possible up to x 6 = 1 (while x 2 ³ 0). In this case, x 1 and x 3 remain equal to zero. Now we take x 4, x 5, x 6 as basic variables, and x 1, x 2, x 3 as free variables. Let us express the new basic variables in terms of the new free ones. We get

x 6 = 1 – 3/2 x 1 – 1/2 x 2 + 2 x 3

x 4 = 3 + 8 x 1 + 3 x 2 – 12 x 3

x 5 = 4 + 2 x 1 + x 2 – 6 x 3

Ф = 6 + 25/2 x 1 + 7/2 x 2 – 19 x 3

Let's assign zero values ​​to the free variables, that is, x 1 = x 2 = x 3 = 0, while x 6 = 1, x 4 = 3, x 5 = 4, that is, the third feasible solution (0; 0; 0; 3; 4; 1). In this case Ф 3 = 6.

The variable x 3 is included in the objective function with a negative coefficient, therefore an increase in x 3 relative to the zero value will lead to a decrease in F. From the 2nd equation it is clear that x 3 can increase to 1/4, from the 3rd equation - to 2/3 . The second equation is more critical. Let us convert the variable x 3 into the number of basic ones, and x 4 into the number of free ones.

Now we take x 1, x 2 and x 4 as new free variables. Let us express through them the new basic variables x 3, x 5, x 6. Let's get the system

x 3 = 1/4 + 2/3 x 1 + 1/4 x 2 – 1/12 x 4

x 5 = 5/2 – 2 x 1 – 1/2 x 2 + 1/2 x 4

x 6 = 3/2 – 1/6 x 1 – 1/6 x 4

The objective function will take the form

Ф = 5/4 - 1/6 x 1 - 5/4 x 2 + 19/12 x 4

Variables x 1 and x 2 are included in the objective function with negative coefficients, therefore, as their values ​​increase, the value of Ф will decrease. Let's take x 2 for example. From the 2nd equation of the system it is clear that an increase in the value of x 2 is possible up to x 2 = 5 (while x 5 ³ 0). In this case, x 1 and x 4 remain zero, the values ​​of other variables are equal to x 3 = 3/2; x 5 = 0, x 6 = 3/2, that is, the fourth feasible solution (0; 5; 3/2; 0; 0; 3/2). In this case Ф 4 = 5/4.

Now we take x 1, x 4 and x 5 as new free variables. Let us express through them the new basic variables x 2, x 3, x 6. Let's get the system

x 2 = 5 – 4 x 1 + x 4 – 2 x 5

x 3 = 3/2 – 1/3 x 1 + 1/6 x 4 – 1/2 x 5

x 6 = 3/2 – 1/6 x 1 – 1/6 x 4

The objective function will take the form

Ф = - 5 + 29/6 x 1 + 1/3 x 4 + 5/2 x 5

The coefficients for both variables in the expression for Ф are positive, therefore, a further decrease in the value of Ф is impossible.

That is, the minimum value of Ф min = - 5, the last feasible solution (0; 5; 3/2; 0; 0; 3/2) is optimal.

Option 8. Maximize the objective function Ф = 4 x 5 + 2 x 6

with restrictions: x 1 + x 5 + x 6 = 12;

x 2 + 5 x 5 - x 6 = 30;

x 3 + x 5 - 2 x 6 = 6;

2 x 4 + 3 x 5 - 2 x 6 = 18;

Solution:

The number of equations is 4, the number of unknowns is 6. Therefore, r = n – m = 6 – 4 = 2 variables can be chosen as free variables, 4 variables as basic ones. We choose x 5 and x 6 as free ones, and x 1 , x 2 , x 3 , x 4 as basic ones. Let us express the basic variables in terms of free ones and reduce the system of equations to a unit basis

x 1 = 12 - x 5 - x 6 ;

x 2 = 30 - 5 x 5 + x 6 ;

x 3 = 6 - x 5 + 2 x 6 ;

x 4 = 9 - 3/2 x 5 + x 6;

We write the objective function in the form Ф = 4 x 5 + 2 x 6. Let's assign zero values ​​to the free variables x 5 = x 6 = 0. In this case, the basic variables will take the values ​​x 1 = 12, x 2 = 30, x 3 = 6, x 4 = 9, that is, we get the first feasible solution (12, 30 , 6, 9, 0,) and Ф 1 = 0.

Both free variables enter the objective function with positive coefficients, that is, a further increase in F is possible. Let us convert, for example, x 6 into the number of basic ones. From equation (1) it is clear that x 1 = 0 at x 5 = 12, in (2) ÷ (4) x 6 is included with positive coefficients. Let's move on to a new basis: basic variables - x 6, x 2, x 3, x 4, free - x 1, x 5. Let's express the new basic variables in terms of new free

x 6 = 12 - x 1 - x 5;

x 2 = 42 - x 1 - 6 x 5;

x 3 = 30 - 2 x 1 - 3 x 5 ;

x 4 = 21 - x 1 - 5/2 x 5 ;

The objective function will take the form Ф = 24 - 2 x 1 + 2 x 5 ;

Let's assign zero values ​​to the free variables x 1 = x 5 = 0. In this case, the basic variables will take the values ​​x 6 = 12, x 2 = 42, x 3 = 30, x 4 = 21, that is, we get the second feasible solution (0, 42 , 30, 21, 0, 12) and Ф 2 = 24.

The target function x 5 is included with a positive coefficient, that is, a further increase in F is possible. Let's move on to a new basis: basic variables - x 6, x 5, x 3, x 4, free - x 1, x 2. Let's express the new basic variables through new free

x 6 = 5 - 5/6 x 1 + 1/6 x 2;

x 5 = 7 - 1/6 x 1 - 1/6 x 2 ;

x 3 = 9 - 3/2 x 1 + 1/2 x 2 ;

x 4 = 7/2 - 7/12 x 1 + 5/12 x 5 ;

The objective function will take the form Ф = 38 – 7/2 x 1 – 1/3 x 2 ;

Let's assign zero values ​​to the free variables x 1 = x 2 = 0. In this case, the basic variables will take the values ​​x 6 = 5, x 5 = 7, x 3 = 9, x 4 = 7/2, that is, we obtain the third feasible solution X 3 = (0, 0, 9, 7/2, 7, 5) and Ф 3 = 38.

Both variables enter the objective function with negative coefficients, that is, a further increase in Ф is impossible.

Therefore, the last feasible solution is optimal, that is, X opt = (0, 0, 9, 7/2, 7, 5) and Ф max = 38.

Option 10. Maximize the objective function Ф = x 2 + x 3

with restrictions: x 1 - x 2 + x 3 = 1,

x 2 - 2 x 3 + x 4 = 2.

Solution:

The system of equations-constraints is consistent, since the ranks of the matrix of the system of equations and the extended matrix are the same and equal to 2. Consequently, two variables can be taken as free, the other two variables - basic - can be expressed linearly through two free ones.

Let's take x 2 and x 3 as free variables. Then the basic variables will be x 1 and x 2, which we will express in terms of free

x 1 = 1 + x 2 - x 3 ; (*)

x 4 = 2 - x 2 + 2 x 3 ;

The objective function is already expressed in terms of x 2 and x 3, that is, Ф = x 2 + x 3.

For x 2 =0 and x 3 =0, the basic variables will be equal to x 1 = 1, x 4 = 2.

We have the first feasible solution X 1 = (1, 0, 0, 2), with Ф 1 = 0.

An increase in Ф is possible by increasing, for example, the value of x 3, which is included in the expression for Ф with a positive coefficient (x 2 remains equal to zero). The first equation of the system (*) shows that x 3 can be increased to 1 (from the condition x 1 ³0), that is, this equation imposes a limitation on the increase in the value of x 3. The first equation of the system (*) is resolving. Based on this equation, we move to a new basis, swapping x 1 and x 3. Now the basic variables will be x 3 and x 4, and the free variables will be x 1 and x 2. Let us now express x 3 and x 4 in terms of x 1 and x 2.

We get: x 3 = 1 - x 1 + x 2 ; (**)

x 4 = 4 - 2 x 1 + x 2 ;

Ф = x 2 + 1 - x 1 + x 2 = 1 - x 1 + 2 x 2

Equating the free variables to zero, we obtain the second admissible basic solution X 2 = (0; 0; 1; 4), for which Ф 2 = 1.

An increase in Ф is possible with an increase in x2. The increase in x 2, judging by the last system of equations (**), is not limited. Consequently, Ф will take on increasingly larger positive values, that is, Ф max = + ¥.

So, the objective function Ф is not limited from above, therefore there is no optimal solution.

TASK 2.D. Compose a problem dual to the given one

the original task.

Option 7. Maximize the objective function Ф = 2× x 1 - x 4

with restrictions: x 1 + x 2 = 20,

x 2 + 2× x 4 ≥ 5,

x 1 + x 2 + x 3 ≤ 8,

x i ≥ 0 (i = 1, 2, 3, 4)

Solution:

Let us bring the system of restrictions to a single, for example, canonical form, by introducing additional variables into the 2nd and 3rd equations

x 1 + x 2 = 20,

x 2 + 2 × x 4 – x 5 = 5,

- x 1 + x 2 + x 3 + x 6 = 8.

We have obtained an asymmetric problem of type 2. The dual problem will look like:

Minimize the objective function F = 20 × y 1 + 5 × y2+8 × y 3

at y 1 - y 3 ≥ 2,

y 1 + y 2 + y 3 ≥ 0,

y 3 ≥ 0,

2× y 2 ≥ 1,

Y2 ≥ 0,

y 3 ≥ 0.

Option 8. Maximize the objective function Ф = x 2 - x 4 - 3× x 5

with restrictions: x 1 + 2× x 2 - x 4 + x 5 = 1,

— 4 × x 2 + x 3 + 2× x 4 - x 5 = 2,

3 × x 2 + x 5 + x 6 = 5,

x i ≥ 0, (i = 1, 6)

Solution:

We have an initial maximization problem with a system of constraints in the form of equations, that is, a pair of dual problems has an asymmetric type 2 type, the mathematical model of which in matrix form has the form:

Original problem: Dual problem:

F = C × X max F = B T × Ymin

at A × X = B at A T × Y ≥ C T

In the original problem, the matrix-row of coefficients for the variables in objective function has the form C = (0; 1; 0; -1; -3; 0),

the matrix-column of free terms and the matrix of coefficients for variables in the system of restrictions have the form

B = 2, A = 0 - 4 1 2 -1 0

Let's find the transposed matrix of coefficients, a row matrix of coefficients for variables in the objective function and a column matrix of free terms

0 1 0 0 V T = (1; 2; 5)

A T = -1 2 0 C T = -1

The dual problem will be written in the following form:

find the minimum value of the objective function F = y 1 + 2 × y2+5 × y 3

under restrictions y 1 ≥ 0,

2× y 1 - 4 × y2+3 × y 3 ≥ 1,

- y 1 + 2 × y 2 ≥ -1,

y 1 - y 2 + y 3 ≥ -3,

Option 10. Minimize the function Ф = x 1 + x 2 + x 3

with restrictions: 3× x 1 + 9× x 2 + 7× x 3 ≥ 2,

6 × x 1 + 4 x 2 + 5× x 3 ≥ 3,

8 × x 1 + 2 x 2 + 4× x 3 ≥ 4,

Solution:

We have an initial minimization problem with a system of constraints in the form of inequalities, that is, a pair of dual problems has a symmetrical form of the 3rd type, the mathematical model of which in matrix form has the form:

Original problem Dual problem

F = C × X min F = B T × Ymax

at A × X ≥ B at A T × Y ≤ S T

X ≥ 0 Y ≥ 0

In the original problem, the matrix-row of coefficients for variables in the objective function, the matrix-column of free terms and the matrix of coefficients for variables in the system of constraints have the form

C = (1; 1; 1), B = 3, A = 6 4 5

Let's find the matrices of the dual problem

B T = (2; 3; 4) C T = 3 A T = 9 4 2

The dual problem is formulated as:

Maximize the objective function F = 2y 1 + 3y 2 + 4y 3

under restrictions 3 × y 1 + 6 × y2+8 × y 3 ≤ 1,

9× y 1 + 4 × y2+2 × y 3 ≤ 1,

7× y 1 + 5 × y2+4 × y 3 ≤ 1,

y i ≥ 0 (i = 1, 2, 3)

TASK 2.C. Solving a linear programming problem using simplex tables.

Option 7. Maximize the objective function Ф = 2 x 1 - x 2 + 3 x 3 + 2 x 4

with restrictions: 2 x 1 + 3 x 2 - x 3 + 2 x 4 ≤ 4,

x 1 - 2 x 2 + 5 x 3 - 3 x 4 ≥ 1,

4 x 1 + 10 x 2 +3 x 3 + x 4 ≤ 8.

Solution:

Let us bring the system of restrictions to the canonical form

2 x 1 + 3 x 2 – x 3 + 2 x 4 + z 1 = 4, (1)

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1, (2)

4 x 1 + 10 x 2 +3 x 3 + x 4 + z 3 = 8. (3)

We have a system of 3 equations with 7 unknowns. Let us choose 3 variables x 1 , z 1 , z 3 as basic ones, x 2 , x 3 , x 4 , z 2 as free ones, and express the basic variables through them.

From (2) we have x 1 = 1 + 2 x 2 - 5 x 3 + 3 x 4 + x 6

Substitute into (1) and (3), we get

x 1 - 2 x 2 + 5 x 3 - 3 x 4 - z 2 = 1,

z 1 + 7 x 2 - 11 x 3 + 8 x 4 + 2 z 2 = 2,

z 3 + 18 x 2 - 17 x 3 + 13 x 4 + 4 z 2 = 4,

Ф - 3 x 2 + 7 x 3 - 8 x 4 - 2 z 2 = 2.

Let's create a simplex table

I iteration Table 1

Basic AC	Freedom. AC
x 1	1	1	— 2	5	— 3	0	— 1	0		3/8
z 1	2	0	7	-11		1	2	0	1/ 4	1/8
z 3	4	0	18	-17	13	0	4	1	4/13	13/8
F	2	0	— 3	7	— 8	0	— 2	0		1

X 1 = (1; 0; 0; 0; 2; 0; 4) Ф 1 = 2.

II iteration Table 2

x 1	14/8	1	5/8	7/8	0	3/8	-2/8	0	2	— 1
x 4	1/ 4	0	7/8	-11/8	1	1/8	2/8	0		11/7
z 3	6/8	0	53/8		0	-13/8	6/8	1	6/7	8/7
F	4	0	4	— 4	0	1	0	0		32/7

X 2 = (14/8; 0; 0; 1/4; 0; 0; 4) Ф 2 = 4.

III iteration Table 3

x 1	1	1	— 6	0	0		-1	— 1		1/2
x 4	10/ 7	0	79/7	0	1	-17/7	10/7	11/7		11/7
x 3	6/7	0	53/7	1	0	-13/7	6/7	8/7		13/14
F	52/7	0	240/7	0	0	-45/7	24/7	32/7		45/14

X 3 = (1; 0; 6/7; 10/7; 0; 0; 0) F 3 = 52/7.

IV iteration Table 4

z 1	1/ 2	1/2	— 3	0	0	1	-1/2	-1/2
x 4	37/ 14	17/14	56/14	0	1	0	3/14	5/14
x 3	25/14	13/14	28/14	1	0	0	-1/14	3/14
F	149/14	45/14	15	0	0	0	3/14	19/14

X 4 = (0; 0; 25/14; 37/14; 1/2; 0; 0) F 4 = 149/14.

There is no last table in the index row negative numbers, that is, in the expression for the objective function all Г i< 0. Имеем случай I, следовательно, последнее базисное решение является оптимальным.

Answer: Ф m ax = 149/14,

optimal solution (0; 0; 25/14; 37/14; 1/2; 0; 0)

Option 8. Minimize the objective function Ф = 5 x 1 - x 3

under restrictions: x 1 + x 2 + 2 x 3 - x 4 = 3,

x 2 + 2 x 4 =1,

Solution:

The number of variables is 4, the rank of the matrix is ​​2, therefore the number of free variables is r = 4 - 2 = 2, the number of basic variables is also 2. Let us take x 3, x 4 as free variables, express the basic variables x 1, x 2 in terms of free and Let us reduce the system to a unit basis:

x 2 = 1 - 2 x 4,

x 1 = 3 - x 2 - 2 x 3 + x 4 = 3 - 1 + 2 x 4 - 2 x 3 + x 4 = 2 - 2 x 3 + 3 x 4

Ф = 5 x 1 - x 3 = 5 (2 - 2 x 3 + 3 x 4) - x 3 = 10 - 10 x 3 + 15 x 4 - x 3 = 10 - 11 x 3 + 15 x 4

Let us write the system of equations and the objective function in a form convenient for the simplex table, that is, x 2 + 2 x 4 = 1,

x 1 +2 x 3 - 3 x 4 = 2

F + 11 x 3 - 15 x 4 = 10

Let's make a table

I iteration Table 1

Basic AC	Freedom. AC
X 1	2	1	0		— 3		1/2
X 2	1	0	1	0	2
F	10	0	0	11	— 15		— 11/2

X 1 = (2; 1; 0; 0) Ф 1 = 10.

II iteration Table 2

X 3	1	1/2	0	1	-3/2		3/4
X 2	1	0	1	0			1/2
F	— 1	— 11/2	0	0	3/2		— 3/4

X 2 = (0; 1; 1; 0) Ф 2 = -1.

III iteration Table 3

X 3	7/4	1/2	3/4	1	0
X 4	1/2	0	1/2	0	1
F	— 7/4	— 11/2	— 3/4	0	0

X 3 = (0; 0; 7/4; 1/2) F 3 = -7/4.

There are no positive numbers in the index line of the last table, that is, in the expression for the objective function all Г i > 0. We have case I, therefore, the last basic solution is optimal.

Answer: Ф min = -7/4, optimal solution (0; 0; 7/4; 1/2)

********************

Option 10. Minimize the objective function Ф = x 1 + x 2,

under restrictions: x 1 –2 x 3 + x 4 = 2,

x 2 – x 3 + 2 x 4 = 1,

Solution:

The number of variables is 5, the rank of the matrix is ​​3, therefore the number of free variables is r = 6-3 = 2. Let’s take x 3 and x 4 as free variables, and x 1 , x 2 , x 5 as basic ones. All equations of the system have already been reduced to a unit basis (basic variables are expressed in terms of free ones), but are written in a form that is not convenient for using simplex tables. Let us write the system of equations in the form

x 1 - 2 x 3 + x 4 = 2

x 2 - x 3 +2 x 4 = 1

x 5 + x 3 – x 4 . = 5

We express the objective function in terms of free variables and write it in the form Ф - 3 x 3 +3 x 4 = 3

Let's make a table

I iteration Table 1

Basic AC	Freedom. AC
x 1	2	1	0	-2	1	0	2	-1/2
x 2	1	0	1	-1		0	1/2	1/2
x 5	5	0	0	1	-1	1		1/2
F	3	0	0	-3	3	0		-3/2

X 1 = (2; 3; 0; 0; 5) F 1 = 3.

table 2

x 1	3/2	1	-1/2	-3/2	0	0
x 4	1/2	0	1/2	-1/2	1	0
x 5	11/2	0	1/2	1/2	0	1
F	3/2	0	-3/2	-3/2	0	0

X 2 = (3/2; 0; 0; 1/2; 11/2) F 2 = 3/2.

There are no positive numbers in the index row of the last table, that is, in the expression for the objective function all Gi > 0. We have case 1, therefore, the last basic solution is optimal.

Answer: Ф min = 3/2, optimal solution (3/2; 0; 0; 1/2; 11/2).

Federal Agency for Education

State budget educational institution

higher vocational education

"Omsk State Technical University"

CALCULATION AND GRAPHIC WORK

by discipline "OPTIMAL CONTROL THEORY »

on the topic "OPTIMIZATION METHODS AND OPERATIONS RESEARCH »

option 7

Completed:

correspondence student

4th year group ZA-419

Full name: Kuzhelev S. A.

Checked:

Devyaterikova M. V.

Omsk – 2012
^

Task 1. Graphical method for solving linear programming problems.

7) 7x 1 + 6x 2 → max 20x 1 + 6x 2 ≤ 15 16x 1 − 2x 2 ≤ 18 8x 1 + 4x 2 ≤ 20 13x 1 + 3x 2 ≤ 4 x 1 , x 2 ≥ 0.

Step 1: Constructing the Feasible Region

The conditions for non-negativity of variables and squares limit the range of their permissible values ​​to the first quadrant. Each of the remaining four inequality constraints of the model corresponds to a certain half-plane. The intersection of these half-planes with the first quadrant forms the set of feasible solutions to the problem.

The first constraint of the model has the form . Replacing the ≤ sign in it with the = sign, we obtain the equation . In Fig. 1.1 it defines a straight line (1), which divides the plane into two half-planes, in in this case above and below the line. To choose which one satisfies the inequality , substitute into it the coordinates of any point not lying on a given line (for example, the origin X 1 = 0, X 2 = 0). Since we obtain the correct expression (20 0 + 6 0 = 0 ≤15), then the half-plane containing the origin of coordinates (marked with an arrow) satisfies the inequality. Otherwise, another half-plane.

We proceed similarly with the remaining constraints of the problem. The intersection of all constructed half-planes with the first quadrant forms ABCD(see Fig. 1). This is the feasible area of ​​the problem.

Step 2. Drawing a level line Level line The objective function is the set of points in the plane at which the objective function takes a constant value. Such a set is given by the equation f ( x) = const. Let's put, for example, const = 0 and draw a line at the level f ( x) = 0, i.e. in our case straight line 7 x 1 + 6x 2 = 0.

This line passes through the origin and is perpendicular to the vector. This vector is the gradient of the objective function at the point (0,0). The gradient of a function is a vector of values ​​of the partial derivatives of a given function at the point in question. In the case of the LP problem, the partial derivatives of the objective function are equal to the coefficients Ci, j = 1 , ..., n.

The gradient shows the direction of the fastest growth of the function. Moving the objective function level line f ( x) = const. perpendicular to the direction of the gradient, we find the last point at which it intersects with the region. In our case, this is point D, which will be the maximum point of the objective function (see Fig. 2)

It lies at the intersection of lines (2) and (3) (see Fig. 1) and specifies the optimal solution.

^ Note that if you want to find the minimum value of the objective function, the level line is moved in the direction opposite to the direction of the gradient.

^ Step 3. Determining the coordinates of the maximum (minimum) point and the optimal value of the objective function

To find the coordinates of point C, it is necessary to solve a system consisting of equations corresponding to straight lines (in this case, equations 2 and 3):

16x 1 − 2x 2 ≤ 18

8x 1 + 4x 2 ≤ 20

We get the optimal solution = 1.33.

^ Optimal value objective function f * = f (X*) = 7 * 0 + 6 * 1,33 = 7,8

CONTROL WORK ON DISCIPLINE:

“METHODS OF OPTIMAL SOLUTIONS”

Option No. 8

1. Solve a linear programming problem graphically. Find the maximum and minimum of the function with the given restrictions:

,

.

Solution

It is necessary to find the minimum value of the objective function and the maximum, under the system of restrictions:

9x 1 +3x 2 ≥30, (1)

X 1 +x 2 ≤4, (2)

x 1 +x 2 ≤8, (3)

Let us construct a region of feasible solutions, i.e. Let's solve the system of inequalities graphically. To do this, we construct each straight line and define the half-planes defined by the inequalities (the half-planes are indicated by a prime).

The intersection of half-planes will be a region whose point coordinates satisfy the inequalities of the system of constraints of the problem. Let us denote the boundaries of the area of ​​the solution polygon.

Let's construct a straight line corresponding to the value of the function F = 0: F = 2x 1 +3x 2 = 0. The gradient vector, composed of the coefficients of the objective function, indicates the direction of minimization of F(X). The beginning of the vector is point (0; 0), the end is point (2; 3). We will move this straight line in a parallel manner. Since we are interested in the minimal solution, we therefore move the straight line until it first touches the designated area. On the graph, this straight line is indicated by a dotted line.

Straight
intersects the region at point C. Since point C is obtained as a result of the intersection of lines (4) and (1), its coordinates satisfy the equations of these lines:
.

Having solved the system of equations, we get: x 1 = 3.3333, x 2 = 0.

How can we find the minimum value of the objective function: .

Let's consider the objective function of the problem.

Let's construct a straight line corresponding to the value of the function F = 0: F = 2x 1 +3x 2 = 0. The gradient vector, composed of the coefficients of the objective function, indicates the direction of maximization of F(X). The beginning of the vector is point (0; 0), the end is point (2; 3). We will move this straight line in a parallel manner. Since we are interested in the maximum solution, we therefore move the straight line until the last touch of the designated area. On the graph, this straight line is indicated by a dotted line.

Straight
intersects the region at point B. Since point B is obtained as a result of the intersection of lines (2) and (3), its coordinates satisfy the equations of these lines:

.

How can we find the maximum value of the objective function: .

Answer:
And
.

2 . Solve a linear programming problem using the simplex method:

.

Solution

Let's solve a direct linear programming problem using the simplex method, using a simplex table.

Let's determine the minimum value of the objective function
under the following conditions-restrictions:
.

To construct the first reference plan, we reduce the system of inequalities to a system of equations by introducing additional variables.

In the 1st inequality of meaning (≥) we introduce the basic variable x 3 with a minus sign. In the 2nd inequality of meaning (≤) we introduce the basic variable x 4 . In the 3rd inequality of meaning (≤) we introduce the basic variable x 5 .

Let's introduce artificial variables : in the 1st equality we introduce a variable x 6 ;

To set the problem to a minimum, we write the objective function as follows: .

For the use of artificial variables introduced into the objective function, a so-called penalty of M is imposed, a very large positive number that is usually not specified.

The resulting basis is called artificial, and the solution method is called the artificial basis method.

Moreover, artificial variables are not related to the content of the problem, but they make it possible to construct a starting point, and the optimization process forces these variables to take zero values ​​and ensure the admissibility of the optimal solution.

From the equations we express artificial variables: x 6 = 4-x 1 -x 2 +x 3, which we substitute into the objective function: or.

Coefficient matrix
this system of equations has the form:
.

Let's solve the system of equations for the basic variables: x 6 , x 4 , x 5.

Assuming that the free variables are equal to 0, we obtain the first reference plan:

X1 = (0,0,0,2,10,4)

The basic solution is called admissible if it is non-negative.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

The current reference plan is not optimal because there are positive coefficients in the index line. As the leading column, we will choose the column corresponding to the variable x 2, since this is the largest coefficient. Let's calculate the values D i and from them we choose the smallest: min(4: 1, 2: 2, 10: 2) = 1.

Therefore, the 2nd line is the leading one.

The resolving element is equal to (2) and is located at the intersection of the leading column and the leading row.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 4
x 5

We form the next part of the simplex table. Instead of the variable x 4, plan 1 will include the variable x 2.

The row corresponding to the variable x 2 in plan 1 is obtained by dividing all elements of the row x 4 of plan 0 by the resolving element RE = 2. In place of the resolving element we get 1. In the remaining cells of the x 2 column we write zeros.

Thus, in the new plan 1, row x 2 and column x 2 are filled. All other elements of the new plan 1, including the elements of the index row, are determined by the rectangle rule.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6
x 2
x 5
		1 1/2 +1 1/2 M

The current reference plan is not optimal because there are positive coefficients in the index row. As the leading column, we will choose the column corresponding to the variable x 1, since this is the largest coefficient. Let's calculate the values D i by row as a quotient of division: and from them we choose the smallest: min (3: 1 1 / 2, -, 8: 2) = 2.

Therefore, the 1st line is the leading one.

The resolving element is equal to (1 1/2) and is located at the intersection of the leading column and the leading row.

		x 1	x 2	x 3	x 4	x 5	x 6
x 6		1 1 / 2
x 2
x 5
		-1 1 / 2 +1 1 / 2 M

We form the next part of the simplex table. Instead of the variable x 6, plan 2 will include the variable x 1.

We get a new simplex table:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

There are no positive values ​​among the index string values. Therefore, this table determines the optimal plan for the problem.

The final version of the simplex table:

		x 1	x 2	x 3	x 4	x 5	x 6
x 1
x 2
x 5

Since there are no artificial variables in the optimal solution (they are equal to zero), this solution is admissible.

The optimal plan can be written as follows: x 1 = 2, x 2 = 2:.

Answer:
,
.

3. The Three Fat Men company delivers canned meat from three warehouses located in different parts of the city to three stores. Stocks of canned food available in warehouses, as well as volumes of store orders and delivery rates (in conventional monetary units) are presented in the transport table.

Find a transportation plan that provides the lowest monetary costs (perform the initial transportation plan using the “northwest corner” method).

Solution

Let us check the necessary and sufficient condition for the solvability of the problem:

= 300 + 300 + 200 = 800 .

= 250 + 400 + 150 = 800.

The balance condition is met. Supplies equal needs. Therefore, the model of the transport problem is closed.

Let's enter the initial data into the distribution table.

Needs

Using the northwest corner method, we will construct the first reference plan of the transport problem.

The plan begins to fill in from the upper left corner.

The required element is 4. For this element, inventories are 300, requirements are 250. Since the minimum is 250, we subtract it: .

			300 - 250 = 50
250 - 250 = 0

The required element is equal to 2. For this element, inventories are 50, requirements are 400. Since the minimum is 50, we subtract it: .

			50 - 50 = 0
	400 - 50 = 350

The required element is 5. For this element, inventories are 300, requirements are 350. Since the minimum is 300, we subtract it:

			300 - 300 = 0
	350 - 300 = 50

The required element is 3. For this element, inventories are 200, requirements are 50. Since the minimum is 50, we subtract it:

			200 - 50 = 150
	50 - 50 = 0

The required element is 6. For this element, inventories are 150, requirements are 150. Since the minimum is 150, we subtract it:

			150 - 150 = 0
		150 - 150 = 0

Needs

Introduction

The current stage of human development is distinguished by the fact that the age of energy is being replaced by the age of computer science. There is an intensive introduction of new technologies into all spheres of human activity. There is a real problem of transition to an information society, for which the development of education should become a priority. The structure of knowledge in society is also changing. Increasingly important for practical life acquire fundamental knowledge that contributes to the creative development of the individual. The constructiveness of the acquired knowledge and the ability to structure it in accordance with the goal are also important. Based on knowledge, new ones are formed informational resources society. The formation and acquisition of new knowledge should be based on a strict methodology of a systems approach, within which the model approach occupies a special place. The possibilities of the model approach are extremely diverse, both in terms of the formal models used and in the methods of implementing modeling methods. Physical modeling allows one to obtain reliable results for fairly simple systems.

Currently, it is impossible to name an area of ​​human activity in which modeling methods would not be used to one degree or another. This is especially true in the area of ​​management various systems, where the main processes are decision-making based on the information received.

1. Statement of the problem

minimum objective function

Solve the problem of finding the minimum of the objective function for the system of constraints specified by the solution polygon in accordance with option No. 16 of the task. The solution polygon is shown in Figure 1:

Figure 1 - Polygon of solutions to the problem

The system of constraints and the objective function of the problem are presented below:

It is necessary to solve the problem using the following methods:

Graphical method for solving LP problems;

Algebraic method for solving LP problems;

Simplex method for solving LP problems;

Method for finding an admissible solution to LP problems;

Solution of the dual LP problem;

Branch and bound method for solving integer LP problems;

Gomori method for solving integer LP problems;

Balazs method for solving Boolean LP problems.

Compare solution results different methods draw appropriate conclusions from the work.

2. Graphic solution linear programming problems

The graphical method for solving linear programming problems is used in cases where the number of unknowns does not exceed three. Convenient for qualitative research of the properties of solutions and is used in conjunction with other methods (algebraic, branch and bound, etc.). The idea of ​​the method is based on the graphical solution of a system of linear inequalities.

Rice. 2 Graphical solution of the LP problem

Minimum point

Equation of a line passing through two points A1 and A2:

AB: (0;1); (3;3)

VS: (3;3); (4;1)

CD: (4;1); (3;0)

EA: (1;0); (0;1)

CF: (0;1); (5;2)

with restrictions:

Solving a linear programming problem using the algebraic simplex method

The application of an algebraic method for solving a problem requires a generalization of the representation of the LP problem. The original system of restrictions, specified in the form of inequalities, is converted to a standard notation when the restrictions are specified in the form of equalities. Transformation of the constraint system to standard view includes the following steps:

Transform the inequalities so that there are variables and free terms on the left, and 0 on the right, i.e. to left side was greater than or equal to zero;

Introduce additional variables, the number of which is equal to the number of inequalities in the system of constraints;

By introducing additional restrictions on the non-negativity of the added variables, replace the inequality signs with strict equality signs.

When solving an LP problem using the algebraic method, a condition is added: the objective function must tend to a minimum. If this condition is not satisfied, it is necessary to transform the objective function accordingly (multiply by -1) and solve the minimization problem. After the solution is found, substitute the values ​​of the variables into the original function and calculate its value.

The solution to a problem using the algebraic method is considered optimal when the values ​​of all basic variables are non-negative, and the coefficients of the free variables in the objective function equation are also non-negative. If these conditions are not met, it is necessary to transform the system of inequalities, expressing some variables in terms of others (changing free and basic variables) to achieve the fulfillment of the above restrictions. The value of all free variables is considered equal to zero.

The algebraic method for solving linear programming problems is one of the most effective methods when solving small-scale problems manually because does not require a large number of arithmetic calculations. The machine implementation of this method is more complicated than, for example, for the simplex method, because The solution algorithm using the algebraic method is to some extent heuristic and the effectiveness of the solution largely depends on personal experience.

Free variables

St. lane - additional kit

The non-negativity conditions are met, therefore, the optimal solution has been found.

3. Solving a linear programming problem using a simplex table

Solution: Let's bring the problem to a standard form for solution using a simplex table.

Let us reduce all equations of the system to the form:

We build a simplex table:

In the upper corner of each cell of the table we enter the coefficients from the system of equations;

We select the maximum positive element in row F, except that this will be the general column;

In order to find the general element, we build a relationship for all positive ones. 3/3; 9/1;- minimum ratio in line x3. Therefore - the general string and =3 - the general element.

We find =1/=1/3. We bring it into the lower corner of the cell where the general element is located;

In all empty lower corners of the general line we enter the product of the value in the upper corner of the cell by;

Select the upper corners of the general line;

In all the lower corners of the general column we enter the product of the value in the upper corner by - and select the resulting values;

The remaining cells of the table are filled in as products of the corresponding selected elements;

Then we build a new table in which the designations of the cells of the elements of the general column and row are swapped (x2 and x3);

The values ​​that were previously in the lower corner are written into the upper corner of the former general row and column;

The sum of the values ​​of the upper and lower corners of these cells in the previous table is written in the upper corner of the remaining cells

4. Solving a linear programming problem by finding an admissible solution

Let a system of linear algebraic equations be given:

We can assume that everything is, otherwise we multiply the corresponding equation by -1.

We introduce auxiliary variables:

We also introduce an auxiliary function

We will minimize the system under restrictions (2) and conditions.

RULE FOR FINDING AN ALLOWABLE SOLUTION: To find an admissible solution to system (1), we minimize form (3) under restrictions (2), taking xj as free unknowns, and taking xj as the basis ones.

When solving a problem using the simplex method, two cases may arise:

min f=0, then all i must be equal to zero. And the resulting values ​​of xj will constitute an admissible solution to system (1).

min f>0, i.e. the original system does not have a feasible solution.

Source system:

The condition of the problem from the previous topic is used.

Let's introduce additional variables:

An admissible solution to the original problem has been found: x1 = 3, x2 = 3, F = -12. Based on the obtained feasible solution, we will find the optimal solution to the original problem using the simplex method. To do this, we will build a new simplex table from the table obtained above, removing the row and the row with the target function of the auxiliary problem:

Analyzing the constructed simplex table, we see that the optimal solution for the original problem has already been found (the elements in the row corresponding to the objective function are negative). Thus, the feasible solution found when solving the auxiliary problem coincides with the optimal solution to the original problem:

6. Dual linear programming problem

The original system of constraints and the objective function of the problem are shown in the figure below.

with restrictions:

Solution: Let’s bring the system of restrictions to a standard form:

The problem dual to this one will have the form:

The solution to the dual problem will be performed using a simple simplex method.

Let us transform the objective function so that the minimization problem is solved, and write the system of constraints in standard form for solving using the simplex method.

y6 = 1 - (-2 y1 + 2y2 +y3 + y4+ y5)

y7 = 5 - (-3y1 - y2 + y3 + y4)

Ф = 0 - (3y1 + 9y2 + 3y3 + y4) ??min

Let us construct an initial simplex table for solving the dual LP problem.

Second step of the simplex method

So, at the third step of the simplex method, an optimal solution to the minimization problem was found with the following results: y2 = -7 /8, y1 = -11/8, Ф = 12. In order to find the value of the objective function of the dual problem, we substitute the found values ​​of the basic and free variables into the maximization function:

Фmax = - Фmin = 3*(-11/8) + 9(-7/8) + 3*0 + 0 = -12

Since the value of the objective function of the direct and dual problems coincides, the solution to the direct problem is found and is equal to 12.

Fmin = Фmax = -12

7. Solving an integer linear programming problem using the branch-and-bound method

Let us transform the original problem in such a way that the integer condition is not satisfied when solved using conventional methods.

Initial polygon of solutions to an integer programming problem.

For the transformed polygon of solutions we construct new system restrictions.

Let us write down the system of restrictions in the form of equalities to be solved using the algebraic method.

As a result of the solution, the optimal plan for the problem was found: x1 = 9/4, x2 = 5/2, F = -41/4. This solution does not meet the integer condition set in the problem. Let's divide the original solution polygon into two areas, excluding area 3 from it

Modified problem solution polygon

Let's create new systems of restrictions for the resulting areas of the solution polygon. The left area is a quadrilateral (trapezoid). The system of restrictions for the left region of the solution polygon is presented below.

Restriction system for the left area

The right area represents point C.

The system of restrictions for the right decision region is presented below.

The new constraint systems represent two auxiliary problems that need to be solved independently of each other. Let's solve an integer programming problem for the left region of the solution polygon.

As a result of the solution, the optimal plan for the problem was found: x1 = 3, x2 = 3, F = -12. This plan satisfies the condition that the variables in the problem are integer and can be accepted as the optimal reference plan for the original integer linear programming problem. There is no point in solving for the right solution region. The figure below shows the progress of solving an integer linear programming problem in the form of a tree.

Progress of solving an integer linear programming problem using the Gomori method.

In many practical applications, an integer programming problem in which a system of linear inequalities and a linear form is given is of great interest

It is required to find an integer solution to system (1), which minimizes the objective function F, and all coefficients are integers.

One of the methods for solving the integer programming problem was proposed by Gomori. The idea of ​​the method is to use continuous linear programming methods, in particular, the simplex method.

1) Using the simplex method, the solution to problem (1), (2) is determined, for which the requirement for an integer solution is removed; if the solution turns out to be integer, then the desired solution to the integer problem will also be found;

2) Otherwise, if some coordinate is not an integer, the resulting solution to the problem is checked for the possibility of the existence of an integer solution (the presence of integer points in an admissible polyhedron):

if in any row with a fractional free term, all other coefficients turn out to be integers, then there are no integers or points in the admissible polyhedron and the integer programming problem has no solution;

Otherwise, an additional linear constraint is introduced, which cuts off a part of the admissible polyhedron that is unpromising for finding a solution to the integer programming problem;

3) To construct an additional linear constraint, select the lth row with a fractional free term and write the additional constraint

where and are respectively fractional parts of the coefficients and free

member. Let us introduce an auxiliary variable into constraint (3):

Let us determine the coefficients and included in constraint (4):

where and are the nearest integers from below for and respectively.

Gomori proved that a finite number of similar steps leads to a linear programming problem whose solution is integer and, therefore, the desired one.

Solution: Let’s bring the system of linear constraints and the goal function to the canonical form:

Let us determine the optimal solution to the system of linear constraints, temporarily discarding the integer condition. We use the simplex method for this. Below, sequentially in the tables, the original solution of the problem is presented, and the transformations of the original table are given in order to obtain the optimal solution to the problem:

Solving Boolean LP problems using the Balazs method.

Create your own version for an integer linear programming problem with Boolean variables, taking into account the following rules: the problem uses at least 5 variables, at least 4 constraints, the coefficients of the constraints and the objective function are chosen arbitrarily, but in such a way that the system of constraints is compatible. The task is to solve the LCLP with Boolean variables using the Balazs algorithm and determine the reduction in the complexity of calculations in relation to solving the problem using the exhaustive search method.

Execution of restrictions

F value

Filtering limitation:

Determination of computational effort reduction

The solution to the problem using the exhaustive search method is 6*25=192 calculated expressions. The solution to the problem using the Balazs method is 3*6+(25-3)=47 calculated expressions. The total reduction in the complexity of calculations in relation to solving the problem using the exhaustive search method is:

Conclusion

The process of designing information systems that implement new information technology is constantly being improved. The focus of systems engineers is increasingly on complex systems, making it difficult to use physical models and increasing the importance of mathematical models and machine simulation of systems. Machine simulation has become an effective tool for studying and designing complex systems. The relevance of mathematical models is continuously increasing due to their flexibility, adequacy to real processes, and low cost of implementation on the basis of modern PCs. More and more opportunities are provided to the user, i.e., a specialist in modeling systems using computer technology. The use of modeling is especially effective in the early stages of designing automated systems, when the cost of erroneous decisions is most significant.

Modern computing tools have made it possible to significantly increase the complexity of the models used in the study of systems; it has become possible to build combined, analytical and simulation models that take into account the whole variety of factors that occur in real systems, i.e., the use of models that are more adequate to the phenomena under study.

Literature:

1. Lyashchenko I.N. Linear and nonlinear programming / I.N. Lyashchenko, E.A. Karagodova, N.V. Chernikova, N.Z. Shor. - K.: “Higher School”, 1975, 372 p.

2. Guidelines for completing a course project in the discipline “Applied Mathematics” for students of the specialty “Computer Systems and Networks” of full-time and part-time forms of study / Compiled by: I.A. Balakireva, A.V. Skatkov - Sevastopol: SevNTU Publishing House , 2003. - 15 p.

3. Guidelines for studying the discipline “Applied Mathematics”, section “Methods of global search and one-dimensional minimization” / Comp. A.V. Skatkov, I.A. Balakireva, L.A. Litvinova - Sevastopol: SevGTU Publishing House, 2000. - 31 p.

4. Guidelines for studying the discipline “Applied Mathematics” for students of the specialty “Computer Systems and Networks” Section “Solving integer linear programming problems” for full-time and part-time education / Compiled by: I.A. Balakireva, A.V. Skatkov - Sevastopol : Publishing House of SevNTU, 2000. - 13 p.

5. Akulich I.L. Mathematical programming in examples and problems:

6. Textbook allowance for economics students. specialist. universities.-M.: Higher. school, 1986.- 319 p., ill.

7. Andronov S.A. Optimal design methods: Text of lectures / SPbSUAP. St. Petersburg, 2001. 169 p.: ill.

Similar documents

Algorithm for solving linear programming problems using the simplex method. Construction of a mathematical model of a linear programming problem. Solving a linear programming problem in Excel. Finding profit and optimal production plan.

course work, added 03/21/2012


Graphic problem solving. Drawing up a mathematical model. Determining the maximum value of the objective function. Solution by the simplex method with an artificial basis of the canonical linear programming problem. Checking the optimality of the solution.

test, added 04/05/2016


Theoretical basis of linear programming. Linear programming problems, solution methods. Analysis of the optimal solution. Solution of a single-index linear programming problem. Statement of the problem and data entry. Model construction and solution stages.

course work, added 12/09/2008


Construction of a mathematical model. Selection, justification and description of the method for solving a direct linear programming problem using the simplex method, using a simplex table. Formulation and solution of a dual problem. Sensitivity analysis of the model.

course work, added 10/31/2014


Construction of a mathematical model in order to obtain maximum profit for the enterprise, graphical solution of the problem. Solving the problem using the SOLVER add-on. Analysis of changes in resource reserves. Determining the limits for changing the coefficients of the objective function.

course work, added 12/17/2014


Mathematical programming. Linear programming. Linear programming problems. Graphical method for solving linear programming problems. Economic formulation of the linear programming problem. Construction of a mathematical model.

course work, added 10/13/2008


Solving a linear programming problem by graphical method, checking it in MS Excel. Analysis of the internal structure of solving a problem in a program. Optimization of production plan. Solving the problem using the simplex method. Multichannel queuing system.

test, added 05/02/2012


Solving a linear programming problem using the simplex method: statement of the problem, construction of an economic and mathematical model. Solving the transport problem using the potential method: constructing the initial reference plan, determining its optimal value.

test, added 04/11/2012


Statement of the nonlinear programming problem. Determination of stationary points and their type. Construction of level lines, three-dimensional graph of the objective function and constraints. Graphic and analytical solution of the problem. User's manual and algorithm diagram.

course work, added 12/17/2012


Analysis of the solution to a linear programming problem. Simplex method using simplex tables. Modeling and solving LP problems on a computer. Economic interpretation of the optimal solution to the problem. Mathematical formulation of the transport problem.