X xn

For the sake of brevity, we use £ notation and write:

j=i subject to:

£ aijxj < bi for i = i, 2,..., m j=i and xj > 0 for j = i, 2,..., n

This is adopted as the standard form for the linear programming problem. Any situation whose mathematical formulation fits this model is a linear programming model.

The function Z being maximised, cixi + c2x2 + ■ ■ ■ + cnxn, is called the objective function. The decision variables - the xj - are sometimes referred to as the uncontrolled or endogenous variables. The input variables - the aij, bi, and cj (a-matrix, b-vector and c-vector) - may be referred to as parameters of the model or as the controlled or exogenous variables. The restrictions are referred to as constraints. The first m constraints, bi, b2,..., bm (those with a function aiixi + ai2x2 + ■ ■ ■ + ainxn representing the total usage of resource i, on the left) are called functional constraints. The xj > 0 restrictions are called non-negativity constraints.

The above model describes the typical manufacturing allocation problem of several products competing for limited production facilities.


Figure 3.3 Manufacturing allocation problem


Find the optimum allocation (giving the highest profit Z) to production facilities of two products x1 and X2 which:

contribute to profit:

per unit of x1: c1 per unit of X2: c2

consume from three production facilities, which are limited by capacities b1, b2, b3:

«11X1 + «12 X2 < b1 «21X1 + «22 X2 < b>2 «31X1 + «32 X2 < b3

See Figure 3.3.

Some commonly used terminology in linear programming originates from this manufacturing allocation problem:

• right-hand side constraints bi (i = 1,2,..., m): amount available of resource bi;

• coefficients aij (i = 1,2,..., m, j = 1,2,..., n): usage of resource limited by bi, per unit xj;

• coefficients Cj (j = 1,2,..., n): contribution to profit per unit Xj;

• shadow price of constraint bi (i = 1,2,..., m):

increase of profit Z per unit increase of production capacity bi;

reduction in cost of a third product x3 necessary to make it part of the optimal solution, i.e. to let it contribute to profits.

This model does not fit all linear programming problems. The other legitimate forms are the following:

• Minimising rather than maximising the objective function:

• Some functional constraints with a greater-than-or-equal-to inequality:

• Some functional constraints in equation form:

• Deleting the non-negativity constraints for some decision variables:

xjunrestricted in sign, for some values of j

Any problem that mixes some or all of these forms with the remaining parts of the above model is still a linear programming problem as long as they are the only new forms introduced. The interpretation of allocating limited resources among competing activities may no longer apply, but all that is required is that the mathematical statement of the problem fits the allowable forms. In Open Design, all legitimate forms mentioned above may occur. Note that in the professor's time allocation problem the first two of the above legitimate forms are used.

Best Investment Tips and Ideas

Best Investment Tips and Ideas

The dynamics of investing can be very emotional and stressful if not properly managed. When you are aware of what is all involved you give yourself the power to avoid those situations or at least manage them effectively. That will make your investments more exciting, rewarding, and enjoyable. Those positive factors will only lead to greater success in all that achieve with investments and life.

Get My Free Ebook

Post a comment