In this case the Kuhn-Tucker necessary conditions are: denotes the gradient at , and is a vector which has the same length as . If we formulate the () conditions for , we get an equality-inequality system which can be solved by computer methods. It is easy to see that () can also be rewritten to an nonlinear optimization task: If the optimal objective function is positive, the () system doesn't have a solution, and if the optimal objective function value is zero, any optimal solution is also a solution of the () system, so the equilibrium are among the optimal solutions. We know about the sufficiency of the Kuhn-Tucker conditions that if is concave in with all , the Kuhn-Tucker conditions are also sufficient, thus every solution of () gives an equilibrium. The formal algorithm is as follows: Kuhn–Tucker-Equilibrium 1 FOR TO 2 DO 3 4 the solution of the () optimum task 5 IF THEN RETURN ELSE RETURN 6 "there is no equilibrium" 7 () Example 27.8 Assume that production plant produce some water purification device sold into households. Let denote the quantity produced by the th production plant, let be the cost function of it, and let be the sale price, which depends on the total quantity to be put on the market. Furthermore, be is the capacity of the th production plant. Thus, the possible decision set is the closed interval, which can be defined by the conditions, so The objective function of the th production is the profit of that: Since is two-dimensional, is a two-element vector as well, and the () optimum task has the following form: Let's introduce the new variables, and for the sake of notational convenience be , then taking account of the last condition, we get the following problem: Let's notice that in case of optimum , so the last term of the objective function can be neglected. Consider the special case of , , , . The () problem is now simplified as follows: Using a simple computer program we can get the optimal solution: which is the equilibrium as well. Exercises
In this case the Kuhn-Tucker necessary conditions are: denotes the gradient at , and is a vector which has the same length as . If we formulate the () conditions for , we get an equality-inequality system which can be solved by computer methods. It is easy to see that () can also be rewritten to an nonlinear optimization task: If the optimal objective function is positive, the () system doesn't have a solution, and if the optimal objective function value is zero, any optimal solution is also a solution of the () system, so the equilibrium are among the optimal solutions. We know about the sufficiency of the Kuhn-Tucker conditions that if is concave in with all , the Kuhn-Tucker conditions are also sufficient, thus every solution of () gives an equilibrium. The formal algorithm is as follows: Kuhn–Tucker-Equilibrium 1 FOR TO 2 DO 3 4 the solution of the () optimum task 5 IF 6 THEN RETURN "there is no equilibrium" 7 ELSE RETURN () Example 27.8 Assume that production plant produce some water purification device sold into households. Let denote the quantity produced by the th production plant, let be the cost function of it, and let be the sale price, which depends on the total quantity to be put on the market. Furthermore, be is the capacity of the th production plant. Thus, the possible decision set is the closed interval, which can be defined by the conditions, so The objective function of the th production is the profit of that: Since is two-dimensional, is a two-element vector as well, and the () optimum task has the following form: Let's introduce the new variables, and for the sake of notational convenience be , then taking account of the last condition, we get the following problem: Let's notice that in case of optimum , so the last term of the objective function can be neglected. Consider the special case of , , , . The () problem is now simplified as follows: Using a simple computer program we can get the optimal solution: which is the equilibrium as well. Exercises
0046_algorithms_of_informatics_volume3.docx