Answer to Question #237060 in Operations Research for opr

Question

List the basic properties of linear programming models indicating also the assumptions of linear programming problems

Answer 1

Basic properties of linear programming models:

(i) There are a number of constraints or restrictions- expressible in quantitative terms.

(ii) The prices of input and output both are constant.

(iii) The relationship between objective function and constraints is linear.

(iv) The objective function is to be optimized i.e., profit maximization or cost minimization.

The use of linear functions implies the following assumptions about the LP model:

1) Proportionality

The contribution of any decision variable to the objective function is proportional to its value.

For example in the diet problem, the contribution to the cost of the diet from one pound of apples is $0.75, from two pounds of apples it's $1.50 and from four-pound, the contribution is $3.00. For four hundred pounds, the contribution would be $300.00.

In many situations, you might get a volume discount such that the price per pound goes down if you purchase more apples. These discounts are often nonlinear, which that a linear programming model is either inappropriate or is really an approximation of the real-world problem.

 

 

2) Additivity

The contribution to the objective function for any variable is independent of the other decision variables. For example in the NSC production problem, the production of P2 tons of steel in Month 2 will always contribute $4000 P2 regardless of how much steel is produced in Month 1.

Proportionality and Additivity are also implied by the linear constraints. In the diet problem, you can obtain 40 milligrams of protein for each gallon of milk you drink. It is unlikely, however, that you would actually obtain 400 milligrams of protein by drinking 100 gallons of milk. Also, it may be the case due to a chemical reaction, you might obtain less than 70 milligrams of Vitamin a by combining a pound of cheese with a pound of apples. Thus, the LP model is really just an approximation of what really happens.

3) Divisibility

Since we are using continuous variables, the LP model assumes that the decision variables can take on fractional variables. Thus, we could a solution to the GT Railroad problem that sends 0.7 locomotives from Centerville to Fine Place. In many situations, the LP is being used on a large enough scale that one can round the optimal decision variables up or down to the nearest integer and get an answer that is reasonably close to the optimal integer solution. For example, if an LP for a production plan is said to produce 12,208.4 widgets, we can probably produce 12,209 and be close to an optimal solution. As we will discuss later in the semester, problems in which some or all the variables must be integers are generally speaking much hard to solve than LPs.

Divisibility also implies that the decision variables can take on the full range of real values. For example, in the tennis problem, the LP may tell you to bet $19.123567 on player A to win the match. Again, most of the problems we will encounter in this course are on a large enough scale that some rounding or truncating of the optimal LP decision variables will not greatly affect the solution.

4) Certainty

The LP model assumes that all the constant terms, objective function, and constraint coefficients as well as the right-hand sides, are known with absolute certainty and will not change. If the values of these quantities are known with certainty, for example, the demand data given in the NSC may be forecasts that might not be 100% accurate, then this assumption is violated.