Für neue Autoren:
kostenlos, einfach und schnell
Für bereits registrierte Autoren
Projektarbeit, 2017
44 Seiten, Note: 84.7
1. Introduction
2. Optimization and optimization model
3. Optimization problem
3.1 The main components of an optimization problem are:
3.1.1 Objective Function
4. Classification of optimization problems
4.1 Classification based on existence of constraints
4.2 Classification based on the physical structure of the problem
4.2.1 Optimal control problems
4.3 Classification based on the nature of the equations involved
4.3.1 Linear programming problem
4.3.2 Nonlinear programming problem
4.3.3 Geometric programming problem
4.3.4 Quadratic programming problem
4.4 Classification based on the permissible values of the decision variables
4.4.1 Integer programming problem
4.4.2 Real-valued programming problem
4.5 Classification based on deterministic nature of the variables
4.5.1 Stochastic programming problem
4.5.2 Deterministic programming problem
4.6 Classification based on separability of the functions
4.6.1 Separable programming problems
4.7 Classification based on the number of objective functions
5. Sıngle varıable optımızatıon
5.1 Necessary condition
5.2 Sufficient condition
6. Multıvarıable optımızatıon wıth no constraınts
7. Multıvarıable optımızatıon wıth equalıty constraınts
7.1 Solution by direct substitution
7.2 Solution by Lagrange multipliers
8. Linear programming methods
8.1 Advantages of linear programming
8.2 Mathematical model of LPP
8.3 Graphical Solution of LP Models
8.4 Simplex method
8.4.1 Solutıon for LPP usıng excel solver
9. SENSITIVITY ANALYS
10. Case studies
11. Conclusion
References
Traditionally, judgment based on experience has been the basis for planning in agriculture, but increased specialization and the adoption of capital intensive production systems have stimulated the development of more formal planning methods based on the construction and analysis of a mathematical model. Once a solution to the model has been derived and tested, the solution can be implemented and its performance is monitored and controlled. Mathematical modeling is quicker and less expensive than using the trial-and-error approach or constructing and manipulating real systems.
KEYWORD- Decision making, Optimization, Constraints, Linear Programming, Variables
Decision Making - Anyone who holds a technical, managerial, or administrative job these days is faced with making decisions daily at work. It may involve: determining which ingredients and in what quantities to add to a mixture being made so that it will meet specifications on its composition, selecting one among a small number of suppliers to order raw materials from, determining the quantities of various products to manufacture in the next period, allocating available funds among various competing agencies, determining how to invest savings among available investment options, deciding which route to take to go to a new location in the city, allocating available farm land to various crops that can be grown, determining how many checkout lanes to staff during a period of stable demand in a grocery store, etc…
A situation such as one of these requiring some decisions to be made is known as a decision making problem or just decision problem. These problems arise in the operation of some system known as the relevant system for the problem. The person(s) responsible for making these decisions are called the decision maker(s) for the problem. At one extreme, these decision making problems may be quite simple requiring the determination of the values of a small number of controllable variables with only simple conditions to be met; and at the other extreme they may be large scale and quite complex with thousands of variables and many conditions to be met. Decision making always involves making a choice between various possible alternatives.
Farm planning has increased in complexity and importance as agriculture in the developed world has become concentrated in larger, more specialized farm units. These changes have stimulated the development of formal planning techniques based on mathematical models. Although this approach has the characteristic of operations research, the profession's direct involvement in agricultural planning has been limited: much of the published work is associated with agricultural economics.
Modern agricultural systems have evolved largely as a result of advances in technology and the associated development of, for example, agricultural equipment, fertilizers, pesticides, new plant varieties and livestock with improved genetic potential. Since many of the new technologies are capital intensive for example, agricultural machinery and environmentally controlled livestock housing-the adoption of many of the new production systems has been accompanied by an increase in the scale and degree of specialization of farm operations. In the developed world agricultural production has therefore become concentrated in larger, more specialized units, and as a result, farm planning has increased in complexity and importance.
Optimization is concerned with decision making. Optimization techniques provide tools for making optimal or best decisions. The concept of optimization is now well rooted as a principle underlying the analysis of many complex decision or allocation problems. It offers a certain degree of philosophical elegance that is hard to dispute, and it often offers an indispensable degree of operational simplicity.
Optimization is the mathematical discipline which is concerned with finding the maxima and minima of functions, possibly subject to constraints. Mathematical optimization also known as mathematical programming is the selection of a best element (with regard to some criterion) from some set of available alternatives. Optimization is the act of achieving the best possible result under given circumstances. The goal of all such decisions is either to minimize effort or to maximize benefit. The effort or the benefit can be usually expressed as a function of certain design variables. Hence, optimization is the process of finding the conditions that give the maximum or the minimum value of a function.
Since prehistoric times, humans have had an abiding interest in optimizing the performance of systems that they use. Now-a-days all the decisions that we make at work, and those affecting our personal lives, usually have the goal of optimizing some desirable characteristic. If there are some objective functions to optimize in addition to satisfying the requirements on the decision variables, the resulting model is known as an optimization model.
An objective function expresses one or more quantities which are to be minimized or maximized. The optimization problems may have a single objective function or more objective functions. Usually the different objectives are not compatible. The variables that optimize one objective may be far from optimal for the others. The problem with multi-objectives can be reformulated as single objective problems by either forming a weighted combination of the different objectives or by treating some of the objectives as constraints.
A set of unknowns, which are essential are called variables. The variables are used to define the objective function and constraints. One cannot choose design variable arbitrarily, they have to satisfy certain specified functional and other requirements. The design variables can be continuous, discrete or Boolean .
A set of constraints are those which allow the unknowns to take on certain values but exclude others. They are conditions that must be satisfied to render the design to be feasible.
Once the design variables, constraints, objectives and the relationship between them have been chosen, the optimization problem can be defined.
An optimization problem can be stated as follows: To find
Abbildung in dieser Leseprobe nicht enthalten
, which minimizes or Maximizes
Abbildung in dieser Leseprobe nicht enthalten
Subject to the constraints
Abbildung in dieser Leseprobe nicht enthalten
Abbildung in dieser Leseprobe nicht enthalten
Where x is an n-dimensional vector called design variable, Abbildung in dieser Leseprobe nicht enthaltenis called the objective function, andAbbildung in dieser Leseprobe nicht enthalten and Abbildung in dieser Leseprobe nicht enthalten are known as inequality and equality constraints respectively. This type of problem is called constrained optimization problem.
Optimization problems can be classified based on the type of constraints, physical structure of the problem, nature of the equations involved, deterministic nature of the variables, permissible value of the design variables, separability of the functions and number of objective functions. These classifications are briefly discussed below.
Under these category optimizations problems can be classified into two groups as follows:
Constrained optimization problems: which are subject to one or more constraints.
Unconstrained optimization problems: in which no constraints exist.
Based on the physical structure, optimization problems are classified as optimal control and non-optimal control problems.
An optimal control (OC) problem is a mathematical programming problem involving a number of stages, where each stage evolves from the preceding stage in a prescribed manner. It is defined by two types of variables: the control or design and state variables. The control variables define the system and controls how one stage evolves into the next. The state variables describe the behavior or status of the system at any stage. The problem is to find a set of control variables such that the total objective function (also known as the performance index, PI) over all stages is minimized, subject to a set of constraints on the control and state variables. An OC problem can be stated as follows:
Find X which minimizes f (X) =
Abbildung in dieser Leseprobe nicht enthalten
Subject to the constraints
Abbildung in dieser Leseprobe nicht enthalten i = 1, 2, …., l
Abbildung in dieser Leseprobe nicht enthalten, j = 1, 2, …., l
Abbildung in dieser Leseprobe nicht enthalten, k = 1, 2, …., l
Where xi is the i th control variable, yi is the i th state variable, and fi is the contribution of the i th stage to the total objective function. gj, hk, and qi are the functions of xj, yj ; xk, yk and xi and yi, respectively, and l is the total number of states. The control and state variables xi and yi can be vectors in some cases.
Problems which are not optimal control problems are called non-optimal control problems.
Based on the nature of equations for the objective function and the constraints, optimization problems can be classified as linear, nonlinear, geometric and quadratic programming problems. The classification is very useful from a computational point of view since many predefined special methods are available for effective solution of a particular type of problem.
If the objective function and all the constraints are ‘linear’ functions of the design variables, the optimization problem is called a linear programming problem (LPP). A linear programming problem is often stated in the standard form :
Find X = Abbildung in dieser Leseprobe nicht enthalten
Which maximizes f (X) = Abbildung in dieser Leseprobe nicht enthalten
Subject to the constraints
Abbildung in dieser Leseprobe nicht enthalten, j = 1, 2, . . . , m
xi Abbildung in dieser Leseprobe nicht enthalten, j = 1, 2, . . . , m
where ci, aij, and bj are constants.
If any of the functions among the objectives and constraint functions is nonlinear, the problem is called a nonlinear programming (NLP) problem. This is the most general form of a programming problem and all other problems can be considered as special cases of the NLP problem.
A geometric programming (GMP) problem is one in which the objective function and constraints are expressed as polynomials in X. A function h(X) is called a polynomial (with Abbildung in dieser Leseprobe nicht enthalten terms) if h can be expressed as
Abbildung in dieser Leseprobe nicht enthalten
where cj (Abbildung in dieser Leseprobe nicht enthalten) and aij (Abbildung in dieser Leseprobe nicht enthalten and Abbildung in dieser Leseprobe nicht enthalten) are constants with Abbildung in dieser Leseprobe nicht enthalten and Abbildung in dieser Leseprobe nicht enthalten. Thus GMP problems can be posed as follows:
Find X which minimizes
Abbildung in dieser Leseprobe nicht enthalten
subject to
Abbildung in dieser Leseprobe nicht enthalten
where N0 and Nk denote the number of terms in the objective function and in the k th constraint function, respectively.
A quadratic programming problem is the best behaved nonlinear programming problem with a quadratic objective function and linear constraints and is concave (for maximization problems). It can be solved by suitably modifying the linear programming techniques. It is usually formulated as follows:
F(X) = Abbildung in dieser Leseprobe nicht enthalten
Subject to,
Abbildung in dieser Leseprobe nicht enthalten
Under this classification, objective functions can be classified as integer and real-valued programming problems.
If some or all of the design variables of an optimization problem are restricted to take only integer (or discrete) values, the problem is called an integer programming problem. For example, the optimization is to find number of articles needed for an operation with least effort. Thus, minimization of the effort required for the operation being the objective, the decision variables, i.e. the number of articles used can take only integer values. Other restrictions on minimum and maximum number of usable resources may be imposed.
A real-valued problem is that in which it is sought to minimize or maximize a real function by systematically choosing the values of real variables from within an allowed set. When the allowed set contains only real values, it is called a real-valued programming problem.
Under this classification, optimization problems can be classified as deterministic or stochastic programming problems.
In this type of an optimization problem, some or all the design variables are expressed probabilistically (non-deterministic or stochastic). For example estimates of life span of structures which have probabilistic inputs of the concrete strength and load capacity is stochastic programming problem as one can only estimate stochastically the life span of the structure.
In this type of problems all the design variables are deterministic.
Based on this classification, optimization problems can be classified as separable and non-separable programming problems based on the separability of the objective and constraint functions.
In this type of a problem the objective function and the constraints are separable. A function is said to be separable if it can be expressed as the sum of n single-variable functions, Abbildung in dieser Leseprobe nicht enthalten, i.e.
Abbildung in dieser Leseprobe nicht enthalten
and separable programming problem can be expressed in standard form as :
Find X which minimizes
Abbildung in dieser Leseprobe nicht enthalten
subject to
Abbildung in dieser Leseprobe nicht enthalten
where bj is a constant.
Under this classification, objective functions can be classified as single-objective and multi-objective programming problems.
(i) Single-objective programming problem in which there is only a single objective function.
(ii) Multi-objective programming problem - A multi-objective programming problem can be stated as follows:
Find X which minimizes
Abbildung in dieser Leseprobe nicht enthalten
Subject to ,
Abbildung in dieser Leseprobe nicht enthalten
where f1, f2, . . . fk denote the objective functions to be minimized simultaneously.
For example in some design problems one might have to minimize the cost and weight of the structural member for economy and, at the same time, maximize the load carrying capacity under the given constraints.
Useful in finding the optimum solutions of continuous and differentiable functions. These methods are analytical and make use of the techniques of differential calculus in locating the optimum points.Since some of the practical problems involve objective functions that are not continuous and/or differentiable, the classical optimization techniques have limited scope in practical applications.
- A function of one variable f (x) has a relative or local minimum at x = x* if f (x*) ≤ f (x*+h) for all sufficiently small positive and negative values of h
- A point x* is called a relative or local maximum if f (x*) ≥ f (x*+h) for all values of h sufficiently close to zero.
Abbildung in dieser Leseprobe nicht enthalten
Graph 1: Local and global minima of a function.
- A function f (x) is said to have a global or absolute minimum at x* if f (x*) ≤ f (x)for all x, and not just for all x close to x*, in the domain over which f (x)is defined.
- Similarly, a point x* will be a global maximum of f (x) if f (x*) ≥ f (x)for all x in the domain.
Abbildung in dieser Leseprobe nicht enthalten
Graph 2: Relative and global minima
If a function f (x) is defined in the interval a ≤ x ≤ b and has a relative minimum at x = x*, where a < x* < b, and if the derivative df (x) / dx = f’(x)exists as a finite number at x = x*, then f’ (x*)=0
The theorem does not say that the function necessarily will have a minimum or maximum at every point where the derivative is zero . e.g. f’ (x) =0 at x= 0for the function shown in figure. However, this point is neither a minimum nor a maximum. In general, a point x* at which f’ (x*) = 0is called astationary point.
Abbildung in dieser Leseprobe nicht enthalten
Graph 3: Stationary point of a continuous function.
Abbildung in dieser Leseprobe nicht enthalten
– A minimum value of f (x) if f (n) (x*) > 0 and n is even
– A maximum value of f (x)if f (n) (x*) < 0 and n is even
– Neither a minimum nor a maximum if n is odd . (Boyd and Vandenberghe, 2004).
Example 1.
A Citrus grower estimates that if 60 orange trees are planted; the average yield per tree will be 400 oranges. The average yield will decrease by 4 oranges per tree for each additional tree planted on the same acreage. How many trees should the grower plant to maximize the total yield?
Let n= the number of additional trees.
Y= the total yield = number of trees × the yield per tree.
Then:
Y (n) = (60trees + n · trees) (400oranges − n · 4oranges) = (60 + n) (400 − 4n)
= 24, 000 + 160n − 4n2
To maximize! Let’s find the critical numbers:
Y’ (n) = 160 − 8n = 0 n = 160 / 8 = 20 is the only critical number.
Moreover, Y” (n) = −8 Y” (20) = −8 < 0.
By the second derivative test, Y has a local maximum at n = 20, which is an absolute maximum since it is the only critical number.
The grower should plant 60+20 = 80 trees to maximize the total yield.
Example 2.
A landscape architect plans to enclose a 3000 square foot rectangular region in a botanical garden; she will use shrubs costing Rupees 15 per foot along three sides and fencing costing Rupees 10 per foot along the fourth side, find the minimum total cost.
If the rectangular region has dimensions x and y, then its area is A = x*y = 3000ft2.
So y = 3000/x.
If y is the side with fencing costing Rupees 10 per foot, then the cost for this side is Rupees 10 y.
The cost for the three other sides, where shrubs costing Rupees 15 is used, is then Rupees 15 (2x+y).
Therefore the total cost is: C(x) = 10y + 15(2x + y) = 30x + 25y.
Since y = 3000/x,
Then C(x) = 30x + 25 * (3000/x) that we wish to minimize.
Since C’(x) = 30 – 25(3000/x2), then C’(x) = 0 for x2 = (25 * 3000)/30 = 2500.
Therefore, since x is positive, we have only one critical number in the domain which is x = 50ft.
Since C”(x) = 25*(6000/x3), we have C” (50) > 0. Thus, by the 2nd derivative test, C has a local minimum
At x = 50, and therefore an absolute minimum because we have only one critical number in the domain.
Hence,
The minimum cost is C (50) = 3000, with the dimensions x = 50 ft and y = 3000/50 = 60 ft
Necessary condition
If f (X) has an extreme point (maximum or minimum) at X = X * and if the first partial derivatives of f (X) exist at X *, then
Abbildung in dieser Leseprobe nicht enthalten
Sufficient condition
A sufficient condition for a stationary point X* to be an extreme point is that the matrix of second partial derivatives (Hessian matrix) of f (X*) evaluated at X* is
– Positive definite when X* is a relative minimum point
– Negative definite when X* is a relative maximum point . (Boyd and Vandenberghe, 2004).
Abbildung in dieser Leseprobe nicht enthalten
figure 4: Hessian matrix
Example 3.
- A monopolist producing a single output has two types of customers. If it produces q1 units for type 1, then these customers are willing to pay a price of 50-5q1 per unit. If it produces q2 units for type 2, then these customers are willing to pay a price of 100-10q2 per unit.
- The monopolist’s cost of manufacturing q units of output is 90+20q.
- In order to maximize profits, how much should the monopolist produce for each market?
Profit is:
Abbildung in dieser Leseprobe nicht enthalten
Problem statement:
Abbildung in dieser Leseprobe nicht enthalten
Solution:
– Solution by direct substitution
– Solution by the method of Lagrange multipliers
Here m is less than or equal to n, otherwise the problem becomes overdefined and, in general, there will be no solution.
For a problem with n variables and m equality constraints:
Solve the m equality constraints and express any set of m variables in terms of the remaining n-m variables.Substitute these expressions into the original objective function, the result is a new objective function involving only n-m variables.The new objective function is not subjected to any constraint, and hence its optimum can be found by using the unconstrained optimization techniques.
Simple in theory But not convenient from a practical point of view as the constraint equations will be nonlinear for most of the problemssuitable only for simple problems.
Problem with two variables and one constraint:
Minimize f (x1,x2)
Subject to g (x1,x2) =0
For this problem, the necessary condition was found to be:
Abbildung in dieser Leseprobe nicht enthalten
By defining a quantity l, called the Lagrange multiplier as:
Abbildung in dieser Leseprobe nicht enthalten
Necessary conditions for the point (x1*,x2*) to be an extreme point
The problem can be rewritten as:
Abbildung in dieser Leseprobe nicht enthalten
In addition, the constraint equation has to be satisfied at the extreme point:
Abbildung in dieser Leseprobe nicht enthalten
The derivation of the necessary conditions by the method of Lagrange multipliers requires that at least one of the partial derivatives of g (x1,x2) be nonzero at an extreme point.The necessary conditions are more commonly generated by constructing a function L,known as the Lagrange function, as
Abbildung in dieser Leseprobe nicht enthalten
By treating L as a function of the three variables x1, x2 and l, the necessary conditions for its extremum are given by:
Abbildung in dieser Leseprobe nicht enthalten
The Lagrange function, L, is defined by introducing oneLagrange multiplier l j for each constraint gj (X) as
Abbildung in dieser Leseprobe nicht enthalten
Example 4.
Utility maximization from consumption of two goods x and y with the constraint of total income available (I) - 90 rupees and prices of these goods (p1)- 3 rupees for good x and (p2)- 2 rupees for good y with parallel solution.
Max x,y f(x,y) subject to g(x,y) = I
Utility (objective function) = U = u(x,y) = 2xy
2xy means that both goods are complement for us, it can be seen as assume we do not buy x ( x= 0 ) then to total utility function also becomes zero. And the coefficient 2 represent that for each pair of x and y ( means x = 1 and y = 1 to x = 2 and y = 2 ) we get twice the utility from each higher pair. This specification of utility function is imaginary as utility cannot be measured in reality but it is in consensus that for each individual this function can be different.
Budget (constraint) = I = g(x,y) , I = p1x + p2y , 90 = 3x + 4y
Also we have budget constraint, here nothing is imaginary where income can be measured and prices of good x and good y are also measured from the market. Following table will show parallel solving of bordered hessian with left side is mathematical derivation and right side is solving the example with values.
Abbildung in dieser Leseprobe nicht enthalten
from these three equations we have
Abbildung in dieser Leseprobe nicht enthalten
these are the values or x and y at which the Lagrange function is optimized.
Abbildung in dieser Leseprobe nicht enthalten
This |B2| > 0 being second order condition confirms that the units of x and y which we determined from the Lagrange above considering our income and market prices as our limitation has yielded us maximum possible objective function (utility for this case).
Linear Programming is that branch of mathematical programming which is designed to solve optimization problems where all the constraints as well as the objectives are expressed as Linear function. Its earlier application was solely related to the activities of the second’ World War. However soon its importance was recognized and it came to occupy a prominent place in the industry and trade.
Linear Programming is a technique for making decisions under certainty i.e.; when all the courses of options available to an organization are known & the objective of the firm along with its constraints are quantified. That course of action is chosen out of all possible alternatives which yields the optimal results. Linear Programming can also be used as a verification and checking mechanism to ascertain the accuracy and the reliability of the decisions which are taken solely on the basis of manager's experience-without the aid of a mathematical model.
"Linear Programming is a method of planning and operation involved in the construction of a model of a real-life situation having the following elements:
Variables which denote the available choices and the related mathematical expressions which relate the variables to the controlling conditions, reflect clearly the criteria to be employed for measuring the benefits flowing out of each course of action and providing an accurate measurement of the organization’s objective. The method maybe so devised' as to ensure the selection of the best alternative out of a large number of alternative available to the organization.
- Evaluation of all possible alternatives. Most of the problems faced by the present organizations are highly complicated - which cannot be solved by the traditional approach to decision making. The technique of Linear Programming ensures that’ll possible solutions are generated - out of which the optimal solution can be selected.
- Helps in re-evaluation. Linear Programming can also be used in .re-evaluation of a basic plan for changing conditions. Should the conditions change while the plan is carried out only partially, these conditions can be accurately determined with the help of Linear Programming so as to adjust the remainder of the plan for best results.
- Quality of decision. Linear Programming provides practical and better quality of decisions’ that reflect very precisely the limitations of the system i.e.; the various restrictions under which the system must operate for the solution to be optimal. If it becomes necessary to deviate from the optimal path, Linear Programming can quite easily evaluate the associated costs or penalty.
- Focus on grey-areas. Highlighting of grey areas or bottlenecks in the production process is the most significant merit of Linear Programming. During the periods of bottlenecks, imbalances occur in the production department. Some of the machines remain idle for long periods of time, while the other machines are unable toffee the demand even at the peak performance level.
- Flexibility. Linear Programming is an adaptive & flexible mathematical technique and hence can be utilized in analyzing a variety of multi-dimensional problems quite successfully.
- Creation of information base. By evaluating the various possible alternatives in the light of the prevailing constraints, Linear Programming models provide an important database from which the allocation of precious resources can be don rationally and judiciously.
- Scientific approach to problem solving. Linear Programming is the application of scientific approach to problem solving. Hence it results in a better and true picture of the problems-which can then be minutely analyzed and solutions ascertained.
Linear Programming is a mathematical technique for generating & selecting the optimal or the best solution for a given objective function. Technically, Linear Programming may be formally defined as a method of optimizing (i.e.; maximizing or minimizing) a linear function for a number of constraints stated in the form of linear in equations.
Mathematically the problem of Linear Programming may be stated as that of the optimization of linear objective function of the following form:
Abbildung in dieser Leseprobe nicht enthalten
Subject to the Linear constrains of the form:
Abbildung in dieser Leseprobe nicht enthalten
From the above, it is linear that a LP problem has:
Linear objective function which is to be maximized or minimized. Various linear constraints which are simply the algebraic statement of the limits of the resources or inputs at the disposal, Non-negatively constraints. Linear Programming is one of the few mathematical tools that can be used to provide solution to a wide variety of large, complex managerial problems.
LP- method includes Model formulation, solving LP model and sensitivity analysis or post optimality analysis.
Model Formulation Steps
Step 1: Clearly define the decision variables
Step 2: Construct the objective function
Step 3: Formulate the constraints
Graphical solution is limited to linear programming models containing only two decision variables (can be used with three variables but only with great difficulty).Graphical methods provide visualization of how a solution for a linear programming problem is obtained.
- Graphical method of solving a LPP
Step 1. Formulate the linear programming problem.
Step 2. Graph the feasible region and find the corner points.The coordinates of the corner points can be obtained by either inspection or by solving the two equations ofthe lines intersecting at that point.
Step 3. Make a table listing the value of the objective function at each corner point.
Step 4. Determine the optimal solution from the table in step 3.If the problem is of maximization (minimization) type, the solutioncorresponding to the largest (smallest) value of the objectivefunction is the optimal solution of the LPP.
Example 5.
A workshop has three (3) types of machines A, B and C; it can manufacture two (2) products 1 and 2, and all products have to go to each machine and each one goes in the same order; First to the machine A, then to B and then to C. The following table shows:
Table 1 : Time requiredby the machines to process products ,weekly working hours of machines and profit per unit products.
Abbildung in dieser Leseprobe nicht enthalten
Formulate and solve using the graphical method a Linear Programming model for the situation that allows the workshop to obtain maximum gains.
Abbildung in dieser Leseprobe nicht enthalten
Figure 5: Pictorial representation of example problem 5.
Decision Variables:
- x 1: Product 1 Units to be produced weekly
- x 2: Product 2 Units to be produced weekly
- Objective Function:
Maximize
- Subjected to :
Abbildung in dieser Leseprobe nicht enthalten
Graph 6: Non-negative area ie, Abbildung in dieser Leseprobe nicht enthalten.
Abbildung in dieser Leseprobe nicht enthalten
Graph 7: Shows feasible region of 1st constraint ie, Abbildung in dieser Leseprobe nicht enthalten.
Abbildung in dieser Leseprobe nicht enthalten
Graph 8: modified feasible region, 2nd constraint introduced ie, Abbildung in dieser Leseprobe nicht enthalten.
Abbildung in dieser Leseprobe nicht enthalten
Graph 9: Final graph showing feasible region, all constraints are built-in.
Simplex method – developed to help solve large, real world linear programming problems. Simplex method is the most efficient and popular method for solving general linear programming problems.
Excel includes a tool called solver that uses techniques from the operations research to find optimal solutions for all kind of decision problems.
Example 6.
International Wool Company operates a large farm on which sheep are raised. The farm manager determined that for the sheep to grow in the desired fashion, they need at least minimum amounts of four nutrients (the nutrients are nontoxic so the sheep can consume more than the minimum without harm). The manager is considering three different grains to feed the sheep. Table lists the number of units of each nutrient in each kg of grain, the minimum daily requirements of each nutrient for each sheep, and the cost of each grain. The manager believes that as long as a sheep receives the minimum daily amount of each nutrient, it will be healthy and produce a standard amount of wool. The manager wants to raise the sheep at minimum cost.
Table 2 : Lists the number of units of each nutrient in each kg of grain, the minimum daily requirements of each nutrient for each sheep, and the cost of each grain
Abbildung in dieser Leseprobe nicht enthalten
Figure 10: Question loaded in MS-Excel.
Abbildung in dieser Leseprobe nicht enthalten
Figure 11: solver in MS-Excel.
Abbildung in dieser Leseprobe nicht enthalten
Figure 12 : solver parameters dialogue box .
Abbildung in dieser Leseprobe nicht enthalten
Graph 13: Solver results dialogue box.
Abbildung in dieser Leseprobe nicht enthalten
Figure 14: Answer report sheet MS-Excel solver .
Optimal solutions to LP problems have been examined under deterministic assumptions. conditions in most real world situations are dynamic and changing,after an optimal solution to a problem is found, input data values are varied to assess optimal solution sensitivity this process is also referred to as sensitivity analysis or post-optimality analysis.
Sensitivity analysis determines the effect on optimal solutions of changes in parameter values of the objective function and constraint equationsChanges may be reactions to anticipated uncertainties in the parameters or the new or changed information concerning the model.
Examples of LP problems in agriculture
- A Product Mix Problem
Normally we can make a variety of products using the raw materials, machinery, labor force, and other resources available to them. The problem is to decide how much of each product to manufacture in a period, to maximize the total profit subject to the availability of needed resources. E.g. Optimum crop-mix.
- A Blending Problem
Blending is concerned with mixing different materials called the constituents of the mixture so that the mixture conforms to specifications on several properties or characteristics. E.g. Fertilizer mix, feed mix or diet problem.
- A Production Scheduling Problem
An LP formulation of this problem has the aim of finding the best production-storage-marketing plan over the planning horizon by determine the production schedule that minimizes the sum of production and storage costs which maximize the overall profit.
For the assignment problem, transportation problem, and flow capacity problem LP formulation has the aim of minimizing cost.
John and Nair (1998) worked out an optimal Integrated Farming System (IFS) model through linear programming for small farmers (0.2 ha and less) comprising of 43 enterprises with a cropping intensity of 161 per cent and a cost benefit ratio of 1:2.5.
Sonmez and Altin (2004) developed a linear programming model for irrigation scheduling and cropping pattern with adequate and deficit water supply in Harrran plain, Turkey. It was found that even with very low water supply, it is possible to keep the farm income at high levels.
Subhadra (2007) conducted a study to identify the optimum activity mix of dairy enterprise and crop production to enhance farm income with the given resource use efficiency and technology in Thrissur and Palakkad districts of Kerala. It was found that net income of different farm size groups could be enhanced in between Rs. 4,275 to Rs. 15,252 by adding two animals to large and small farmers each and three animals to marginal farmers.
Dey (2011) applied linear programming to study on optimum allocation of vegetable crops in Kakdwip block of South Parganas district in West Bengal. In the optimal crop plan, resources were allocated in favour of brinjal and pointed gourd. Net return earned from optimal crop plan increased by 49.79 percent over the net return earned in existing crop.
Traditionally, judgment based on experience has been the basis for planning in agriculture, but increased specialization and the adoption of capital intensive production systems have stimulated the development of more formal planning methods based on the construction and analysis of a mathematical model. Once a solution to the model has been derived and tested, the solution can be implemented and its performance monitored and controlled. Mathematical modeling is quicker and less expensive than using the trial-and-error approach or constructing and manipulating real systems.
Boyd, S. and Vandenberghe, L. 2004. Convex Optimization [e-book]. Cambridge University Press. Available :http://www.stanford.edu/-boyd/cvbook.html.
Dey, G. 2011. Optimum allocation of resources in vegetable cultivation. J. Crop Weed. 7(1): 77-80.
Eppen, G.D., Gould, F.J., and Schmidt, C.P. 1993. Introductory Management Science ( 4th Ed.). Upper Saddle River, N.J.:Prentice-Hall.
Gill, P.E., Murray, W., and Wright, M.H. 2004. Practical Optimization, Elsevier, 401p.
Glen, J.J. 1987. Mathematical Models in Farm Planning: A Survey. Operations Res. 35(5): 641-666.
Hassan, I., Ahamad, P., and Akhtar, M. 2015. Use of linear programming model to determine the optimum cropping pattern: a case study of Punjab. Electr. J. Environ. Agric. Food Chem. (EJEAFChe). 4(1): 841-850.
Igwe, K.C., Onyenweaku, C.E., and Tanko, L. 2013. A linear programming approach to combination of crop, monogastric farm animal and fish enterprises in Ohafia agricultural zone, Abia State, Nigeria. Glob. J. Sci. Frontier Res. Agric. Vet. Sci. 13(3): 23-32.
Jayachandran, N. 1985. Optimization of enterprise combinations with special reference to garden land agriculture. M.Sc. (Ag) thesis, Kerala Agricultural University, Thrissur. 82p.
John, J. and Nair, M.A. 1998. An integrated-coconut based mixed farming homestead model for southern Kerala. Indian coconut J. 29 (8): 4-7.
Majeke1, F., Mubvuma, M.T., Makaza, K., and Mutambara, J. 2013. Optimum combination of crop farm activities: Application of a linear programming model to a rural farmer in Zimbabwe. Greener J. Econ. Accountancy. 2(2): 58-61.
Mehta, P. 1992. Optimizing Techniques in Agriculture. CBS publishers and Distributor, Delhi, 163p.
Mohamad, N.H. and Said, F. 2011. A Mathematical Programming approach to crop mix problem. Afr. J. Agric. Res. 6(1): 191-197.
Murty, K.G. 2010 . Optimizatio n Models for Decision making. Springer Publishers, Delhi, 482p.
Pandey, R.N. and Bhogal, T.S. 1980. Prospects of increasing income and employment on mixed farms. Indian J. Agric. Econ. 35(4): 145-151.
Randhir, O.T. and Krishnamoorthy, S. 1993. Optimal crop planning under production risk in Tank fed South Indian farms. Indian J Agric. Econ. 48(4):678-686.
Salam, M.A., Sreekumar, D., and Mammen, M.K. 1992. Homestead model for the coastal uplands of South Kerala under irrigated agriculture. Indian Coconut J. 23(4): 2-6.
Sastry, T.V.N. 1993. Optimum enterprise system for farmers in Chittoor district of Andhra Pradesh, Ph.D Thesis, University of Agricultural Science, Bangalore, 225p.
Sonmez, F. K. and Altil, M. 2004. Irrigation schedule and optimum cropping pattern with adequate and deficit water supply for mid-sized farms of Harren Plain. Pakistan J. Biol. Sci. 7(8): 1414-1418.
Spall, J.C. 2003. Introductionto Stochastic Search and Optimization, Estimation, Simulation and Control, Wiley Publications, 595 p.
Subhadra, M.R. 2007. The economics of mixed farming in Kerala. Ph.D.Thesis, Mahatma Gandhi University, Kottayam, 183p.
Varalakshmi, K., Jayasree, H., and Yeledhalli, R.A. 2012. Optimum crop enterprise mix for the farmers in Kurnool district of Andhra Pradesh. Karnataka J. Agric. Sci. 24(5): 661-667.
Yang, W.Y. 1995. Methods of Farm Management in Investigation for Improving Farm Productivity. FAO, Rome, 228p.
KERALA AGRICULTURAL UNIVERSITY
COLLEGE OF AGRICULTURE, VELLAYANI
DEPARTMENT OF AGRICULTURAL STATISTICS
MASTER’S CREDIT SEMINAR (591)
MUHAMMED JASLAM P K Date: 31-12-2016
2015-19-005 ABSTRACT Time: 2.00-2.40 pm
ROLE OF OPTIMIZATION TECHNIQUES IN AGRICULTURE
INTRODUCTION
The concept of optimization is now well rooted as a principle under lying the analysis of many complex decision making or allocation problems such as feed mix or diet problem, blending problem, multi period planning problem...etc (Mehta, 1992). Optimization is the method of achieving the best possible result under given conditions. The goal of all such decisions is either to minimize effort or to maximize benefit. The effort or the benefit can be usually expressed as a function of certain design variables. Hence, optimization is the process of finding the conditions that give the maximum or the minimum value of a function (Sastry, 1993).
OPTIMIZATION MODEL
Optimization is a mathematical discipline which is concerned with finding the maxima and minima of functions, possibly subject to constraints (Spall, 2003). Mathematical optimization is also known as mathematical programming which involve the selection of a best element (with regard to some criterion) from some set of available alternatives (Gill et al., 2004). If there are some objective functions to optimize in addition to satisfying the requirements on the decision variables, the resulting model is known as an optimization model (Glen, 1987).
CLASSIFICATION OF OPTIMIZATION PROBLEMS
Optimization problems can be classified to constrained and unconstrained based on the type of constraints, Linear Programming problem and Nonlinear programming problem based on the equations for the objective function and the constraints.
AN OPTIMIZATION PROBLEM
The main components of an optimization problem are Objective Function, Variables, and Constraints.
- Objective function
An objective function expresses one or more quantities which are to be minimized or maximized. The optimization problems may have a single objective function or more objective functions. Usually the different objectives are not compatible. The variables that optimize one objective may be far from optimal for the others. The problem with multi-objectives can be reformulated as single objective problems by either forming a weighted combination of the different objectives or by treating some of the objectives as constraints (Randhir and Krishnamoorthy, 1993).
- Variables
A set of unknowns, which are essential are called variables. The variables are used to define the objective function and constraints. One cannot choose design variable arbitrarily, they have to satisfy certain specified functional and other requirements (Mohamad and Said, 2011). The design variables can be continuous, discrete or Boolean (Murty, 2010).
- Constraints
A set of constraints are those which allow the unknowns to take on certain values but exclude others (Mohamad and Said, 2011). They are conditions that must be satisfied to render the design to be feasible.
Once the design variables, constraints, objectives and the relationship between them have been chosen, the optimization problem can be defined. An optimization problem can be stated as follows: To findAbbildung in dieser Leseprobe nicht enthalten, which minimizes or maximizes Abbildung in dieser Leseprobe nicht enthalten Subject to the constraints Abbildung in dieser Leseprobe nicht enthaltenAbbildung in dieser Leseprobe nicht enthalten , Abbildung in dieser Leseprobe nicht enthaltenAbbildung in dieser Leseprobe nicht enthalten. Where x is an n-dimensional vector called design variable, Abbildung in dieser Leseprobe nicht enthalten is called the objective function, andAbbildung in dieser Leseprobe nicht enthalten andAbbildung in dieser Leseprobe nicht enthalten are known as inequality and equality constraints respectively .This type of problem is called constrained optimization problem (Varalakshmi et al., 2012).
SINGLE VARIABLE OPTIMIZATI ON
- Necessary condition:- If a function f (x) is defined in the interval a ≤ x ≤ b and has a relative minimum at x = x*, where a < x* < b, and if the derivative df (x) / dx = f’ (x) exists as a finite number at x = x*, then f’ (x*) =0.
- Sufficient condition :- Let f’ (x*) = f’’ (x*) =…= f (n-1) (x*) = 0, but f(n) (x*) ≠ 0. Then f (x*) is a minimum value of f (x) if f (n) (x*) > 0 and n is even, a maximum value of f (x) if f (n) (x*) < 0 and n is even, neither a minimum nor a maximum if n is odd (Boyd and Vandenberghe, 2004).
MULTIVARIABLE OPTIMIZATION WITH NO CONSTRAINTS
- Necessary condition :- If f (X) has an extreme point (maximum or minimum) at X=X* and if the first partial derivatives of f (X) exist at X*,then Abbildung in dieser Leseprobe nicht enthalten
- Sufficient condition:- A sufficient condition for a stationary point X* to be an extreme point is that the matrix of second partial derivatives (Hessian matrix) of f (X*) evaluated at X* is Positive definite whenX* is a relative minimum point and Negative definite when X* is a relative maximum point (Boyd and Vandenberghe, 2004).
MULTIVARIABLE OPTIMIZATION WITH EQUALITY CONSTRAINTS
Problem statement: Minimize or Maximize f = f (X) subject to gj (X)=0, j=1,2,…..,m
where,
Abbildung in dieser Leseprobe nicht enthalten
- Solution by direct substitution
- Solution by the method of Lagrange multipliers
Here m is less than or equal to n, otherwise the problem becomes overdefined and, in general, there will be no solution (Eppen et al., 1993).
LINEAR PROGRAMMING
Linear Programming is that branch of mathematical programming which is designed to solve optimization problems where all the constraints as well as the objectives are expressed as Linear function (Majekel et al., 2013). Linear Programming (LP) is perhaps the most important and best-studied optimization problem (Yang, 1995). A lot of real world problems can be formulated as linear programming problems.
Mathematically the problem of Linear Programming may be stated as that of the optimization of linear objective function of the following form
Abbildung in dieser Leseprobe nicht enthalten
Subject to the Linear constrains of the form:
Abbildung in dieser Leseprobe nicht enthalten
…
Abbildung in dieser Leseprobe nicht enthalten
LP- method includes Model formulation, solving LP model and sensitivity analysis or post optimality analysis. Model Formulation includes steps like clearly defining the decision variables , constructing the objective function and formulation of the constraints. The two methods of solving LP model are graphical and simplex method and sensitivity analysis helps to test the sensitivity of the optimum solution with respect to changes of the coefficients in the objective function, coefficients in the constraints inequalities, or the constant terms in the constraints (Jayachandran, 1985).
CASE STUDIES
John and Nair (1998) worked out an optimal Integrated Farming System (IFS) model through linear programming for small farmers (0.2 ha and less) comprising of 43 enterprises with a cropping intensity of 161 per cent and a cost benefit ratio of 1:2.5.
Sonmez and Altin(2004) developed a linear programming model for irrigation scheduling and cropping pattern with adequate and deficit water supply in Harrran plain, Turkey. It was found that even with very low water supply, it is possible to keep the farm income at high levels.
Subhadra (2007) conducted a study to identify the optimum activity mix of dairy enterprise and crop production to enhance farm income with the given resource use efficiency and technology in Thrissur and Palakkad districts of Kerala. It was found that net income of different farm size groups could be enhanced in between Rs.4,275 to Rs.15,252 by adding two animals to large and small farmers each and three animals to marginal farmers.
Dey (2011) applied linear programming to study on optimum allocation of vegetable crops in Kakdwip block of South Parganas district in West Bengal. In the optimal crop plan, resources were allocated in favour of brinjal and pointed gourd. Net return earned from optimal crop plan was increased by 49.79 percent over the net return earned in existing crop.
Boyd, S. and Vandenberghe, L. 2004. Convex Optimization [e-book]. Cambridge University Press. Available :http://www.stanford.edu/-boyd/cvbook.html.
Dey, G. 2011. Optimum allocation of resources in vegetable cultivation. J. Crop Weed. 7(1): 77-80.
Eppen, G.D., Gould, F.J., and Schmidt, C.P. 1993. Introductory Management Science ( 4th Ed.). Upper Saddle River, N.J.:Prentice-Hall.
Gill, P.E., Murray, W., and Wright, M.H. 2004. Practical Optimization, Elsevier, 401p.
Glen, J.J. 1987. Mathematical Models in Farm Planning: A Survey. Operations Res. 35(5): 641-666.
Hassan, I., Ahamad, P., and Akhtar, M. 2015. Use of linear programming model to determine the optimum cropping pattern: a case study of Punjab. Electr. J. Environ. Agric. Food Chem. (EJEAFChe). 4(1): 841-850.
Igwe, K.C., Onyenweaku, C.E., and Tanko, L. 2013. A linear programming approach to combination of crop, monogastric farm animal and fish enterprises in Ohafia agricultural zone, Abia State, Nigeria. Glob. J. Sci. Frontier Res. Agric. Vet. Sci. 13(3): 23-32.
Jayachandran, N. 1985. Optimization of enterprise combinations with special reference to garden land agriculture. M.Sc. (Ag) thesis, Kerala Agricultural University, Thrissur. 82p.
John, J. and Nair, M.A. 1998. An integrated-coconut based mixed farming homestead model for southern Kerala. Indian coconut J. 29 (8): 4-7.
Majeke1, F., Mubvuma, M.T., Makaza, K., and Mutambara, J. 2013. Optimum combination of crop farm activities: Application of a linear programming model to a rural farmer in Zimbabwe. Greener J. Econ. Accountancy. 2(2): 58-61.
Mehta, P. 1992. Optimizing Techniques in Agriculture. CBS publishers and Distributor, Delhi, 163p.
Mohamad, N.H. and Said, F. 2011. A Mathematical Programming approach to crop mix problem. Afr. J. Agric. Res. 6(1): 191-197.
Murty, K.G. 2010 . Optimizatio n Models for Decision making. Springer Publishers, Delhi, 482p.
Pandey, R.N. and Bhogal, T.S. 1980. Prospects of increasing income and employment on mixed farms. Indian J. Agric. Econ. 35(4): 145-151.
Randhir, O.T. and Krishnamoorthy, S. 1993. Optimal crop planning under production risk in Tank fed South Indian farms. Indian J Agric. Econ. 48(4):678-686.
Salam, M.A., Sreekumar, D., and Mammen, M.K. 1992. Homestead model for the coastal uplands of South Kerala under irrigated agriculture. Indian Coconut J. 23(4): 2-6.
Sastry, T.V.N. 1993. Optimum enterprise system for farmers in Chittoor district of Andhra Pradesh, Ph.D Thesis, University of Agricultural Science, Bangalore, 225p.
Sonmez, F. K. and Altil, M. 2004. Irrigation schedule and optimum cropping pattern with adequate and deficit water supply for mid-sized farms of Harren Plain. Pakistan J. Biol. Sci. 7(8): 1414-1418.
Spall, J.C. 2003. Introductionto Stochastic Search and Optimization, Estimation, Simulation and Control, Wiley Publications, 595 p.
Subhadra, M.R. 2007. The economics of mixed farming in Kerala. Ph.D.Thesis, Mahatma Gandhi University, Kottayam, 183p.
Varalakshmi, K., Jayasree, H., and Yeledhalli, R.A. 2012. Optimum crop enterprise mix for the farmers in Kurnool district of Andhra Pradesh. Karnataka J. Agric. Sci. 24(5): 661-667.
Yang, W.Y. 1995. Methods of Farm Management in Investigation for Improving Farm Productivity. FAO, Rome, 228p.
Masterarbeit, 86 Seiten
Hausarbeit (Hauptseminar), 23 Seiten
Masterarbeit, 13 Seiten
Masterarbeit, 90 Seiten
Forschungsarbeit, 32 Seiten
Wissenschaftlicher Aufsatz, 28 Seiten
Studienarbeit, 26 Seiten
Geowissenschaften / Geographie - Wirtschaftsgeographie
Wissenschaftlicher Aufsatz, 14 Seiten
Hausarbeit, 21 Seiten
Doktorarbeit / Dissertation, 169 Seiten
Masterarbeit, 86 Seiten
Hausarbeit (Hauptseminar), 23 Seiten
Masterarbeit, 13 Seiten
Masterarbeit, 90 Seiten
Forschungsarbeit, 32 Seiten
Wissenschaftlicher Aufsatz, 28 Seiten
Studienarbeit, 26 Seiten
Geowissenschaften / Geographie - Wirtschaftsgeographie
Wissenschaftlicher Aufsatz, 14 Seiten
Hausarbeit, 21 Seiten
Doktorarbeit / Dissertation, 169 Seiten
Der GRIN Verlag hat sich seit 1998 auf die Veröffentlichung akademischer eBooks und Bücher spezialisiert. Der GRIN Verlag steht damit als erstes Unternehmen für User Generated Quality Content. Die Verlagsseiten GRIN.com, Hausarbeiten.de und Diplomarbeiten24 bieten für Hochschullehrer, Absolventen und Studenten die ideale Plattform, wissenschaftliche Texte wie Hausarbeiten, Referate, Bachelorarbeiten, Masterarbeiten, Diplomarbeiten, Dissertationen und wissenschaftliche Aufsätze einem breiten Publikum zu präsentieren.
Kostenfreie Veröffentlichung: Hausarbeit, Bachelorarbeit, Diplomarbeit, Dissertation, Masterarbeit, Interpretation oder Referat jetzt veröffentlichen!