II. Linear Programming


LINEAR PROGRAMMING FORMULATIONS

Linear Programming (LP) is a deterministic tool for solving optimization problems. It is a technique used to find the optimum solution of a linear objective function into two or more variables, subject to some constraints.

A STANDARD FORM OF THE LINEAR PROGRAMMING MODEL

OBJECTIVE FUNCTION : 
		Optimize Z = f(X1, X2,...Xn)

CONSTRAINTS :

      Explicit Constraints :

		g(X1, X2,...Xn) >= Bi 
		g(X1, X2,...Xn) <= Bi        (i = 1,2,...n)
		g(X1, X2,...Xn) =  Bi

      Implicit Constraint :

		Xi >= 0 (non-negativity constraint)

       Decision Variables :

		X1,X2,....Xn
To formulate a linear programming problems simply means to translate a real problem into a standardized format consisting of mathematical equations and inequalities. Formulating the problem is often the most difficult part in analyzing problems in operations research applications.

	Consider the following formulation:

				Max Z = 60X1+30X2
				subject to :
				     2X1+4X2 <= 320
				     3X1+ X2 <= 180
				         2X  <= 100
	        		       X1,X2 <= 0
The above formulation is an example of a standard linear programming model. Each linear programming problem consists of only two parts.

The first part is a mathematical equation that represents the objective to be maximized or minimized. It is referred to as the objective function. The second part is a set of mathematical expression that represent the limitations placed on the decision maker. These mathematical restrictions can be either equation or inequality. Taken as a group, they are referref to as the Constraint Set, and collectively they defined the decision maker's sphere of discretion. The phrase "subject to" indicates that the decision maker's action are restricted by the limitations that follow.

The objective function of a linear programming problem is simply a mathematical statement expressing the relationship between the item that the decision maker wishes to optimize and the level of operation of the decision variables in the problem. The objective function statement is generally preceded by the word maximize or minimize, depending on whether the item under consideration is to be maximized or minimized. In the objective function, Z is the value of the variable being optimized.

Example : Ready Mix Problem

Ready Mix Co. owns a small paint factory that produces both interior and exterior house paints for wholesale distributions two basic raw materials, A and B, are used to manufacture the paint. The maximum availability is 6 tons a day for A and that of B is 8 tons a day. The daily requirements of raw materials per ton of interior and exterior paint are summarized in the following table :

				Tons Of Raw Material
				  Per Ton Of  Paint
		  	Exterior	Interior	Max. Availability (tons)
Raw Material A	            1	            2	             6  
Raw Material B		    2		    1		     8
A market survey has established that the daily demand for internet paints does not exceed that of external paints by more than 1 ton. The survey also shows that the maximum demand for interior paint is limited to 2 tons daily. The wholesale price per ton is P 120,000.00 per external paint and P 80,000.00 per internal paint. How much interior and exterior paint should the company produce daily to maximize gross income?

Solution :

Ready Mix seeks to determine the amount (in tons) of interior and exterior paint to be produced to maximize the total gross income while satisfying the constraints of demand and raw material usage.

The crux of the mathematical model is first to identify the variables and then to express the objective and constraint as mathematical functions of the variables.

	Variables :
		Let Xe(decision variable) = amount in tons of exterior paint
	    	    Xi(decision variable) = amount in tons of interior paint
Since each ton of exterior paint sells for P120,000, the gross income from selling Xe tons will be 120,000Xe. Similarly, the gross income from Xi tons of interior paints is 80,000Xi. Under the assumption that the sale of interior and exterior paints are independent, the total gross income becomes the sum of the 2 revenues.

If we let Z represent the total gross revenue, the objective function may be written mathematically as -

	Objective Function:  maximize gross income
	       Max Z(gross income) = 120,000Xe + 80,000Xi
Ready Mix imposes restrictions on the usage of raw materials and on demand. The usage restriction maybe expressed as - 
	Subject to: 
		    Xe + 2Xi = 6 (usage of raw material A)
		   2Xe +  Xi = 8 (usage of raw material B)
		    Xi -  Xe = 1 (excess demand of interior over exterior)
			  Xi = 2 (maximum demand for internal paint)
		      Xi, Xe = 0 (implicit)
ASSUMPTIONS OF LINEAR PROGRAMMING

Linearity in linear programming models implies that both the proportionality and additivity properties are satisfied.

Proportionality is an assumption about individual activities considered independently of others.
  1. Proportionality requires that the contribution of each variable in the objective function or its usage of the resources be directly proportional to the level or value of the variable.

    For example, if the Ready Mix Company grants quantity discounts by selling a ton of exterior paint for P100,000 when the sales exceed 2 tons, it will no longer be true that each ton produced will bring a revenue of P120,000. Rather, it will bring P120,000 per ton for Xe <= 2 tons and P100,000 per ton for Xe > 2 tons. This situation does not satisfy the condition of direct proportionality with Xe.

  2. The assumption of Additivity concerns with the effect of conducting activities jointly. Additivity requires that the objective function be the direct sum of the individual contributions of the different variables. Similarly, the left side of each constraint must be the sum of the individual usages of each variable from the corresponding source.

    The additivity assumption is that, for each function the total function value can be obtained by adding the individual contributions from the respective activities.

    For example, in case of two competing products, where an increase in the sales of one product adversely affects that of the other, the two products do not satisfy the additivity property.

  3. The divisibility assumption is that activity units that can be divided into any fractional levels, so that non-integer values for the decision variables are permissible. Frequently, linear programming is still applied when an integer solution is required. If the solution obtained is non-integer variables are merely rounded to integer values.

  4. The Certainty assumption is that all the parameters of the model are known constants. In real problems, this assumption is seldom satisfied precisely. Linear programming models usually are formulated to select some future course of action. Therefore, the parameters used would be based on a prediction of future conditions, which inevitably introduces some degree of uncertainty.

    For this reason, it is usually important to conduct a thorough sensitivity analysis after finding a solution that is optimal under the assumed parameter values.

    Send your comments and/or suggestions to yeng21@hotmail.com