Introduction

It is well known that Linear Programming (LP) is a technique for the optimization (maximization or minimization) of a linear objective function subject to linear equality and inequality constraints. The feasible region of a LP problem is a convex polytope, which is a generalization of the three-dimensional polyhedron in the n-dimensional space Rⁿ, where R denotes the set of the real numbers and n is an integer, n>.²

In 1975 the Soviet Leonid Kantorovich and the Dutch-American T. C. Koopmans shared the Nobel prize in Economics for their work, at the end of the 1930’s, on formulating and solving LP problems. A LP algorithm determines a point of the LP polytope, where the objective function takes its optimal value, if such a point exists. In 1947 George B. Dantzic invented the SIMPLEX algorithm¹ that for the first time efficiently tackled the LP problem in most cases. Note that earlier, in 1941, Frank Lamen Hitchcock gave a very similar to the SIMPLEX algorithm solution for the Transportation Problem. In 1948

Dantzic, adopting a conjecture of John von Neuman, who worked on an equivalent problem in Game Theory, provided a formal proof of the theory of Duality.² According to the above theory every LP problem can be converted to a dual problem the optimal solution of which, if it exists, provides an optimal solution for the original problem.  A large breakthrough in the field came also in 1984, when Narendra Karmakar introduced a new interior-point method for solving LP problems. For more details about the history of LP the reader my look at,³ while for general facts about the SIMPLEX algorithm we refer to Chapters 3 and 4 of.⁴

LP, apart from mathematics, is widely used nowadays in business and economics, in several engineering problems, etc. Many practical problems of Operations Research can be expressed as LP problems. However, in large and complex systems, like the socio-economic, the biological ones, etc. ., it is often very difficult to solve satisfactorily the LP problems with the standard theory, since the necessary data can not be easily determined precisely and therefore estimates of them are used in practice. The reason for this is that such kind of systems they usually involve many different and constantly changing factors the relationships among which are indeterminate, making their operation mechanisms not clear. In order to obtain good results in such cases one may apply either techniques of fuzzy logic (Fuzzy LP, e.g. see^5-7, etc.) or of the grey systems theory (Grey LP, e.g. see,^8,9 etc.).

In this work we develop a new technique for solving grey LP problems. The rest of the paper is formulated as follows: In the second Section the background information is recalled about the Grey Numbers (GNs) which is necessary for the understanding of the paper. In the third Section our method for solving grey LP problems is developed and examples are presented illustrating it. Finally, the fourth Section is devoted to our conclusions and some hints for future research on the subject.

Grey Numbers

An investigated object with “poor” information is referred to as a grey system. An effective tool for handling the approximate data of a grey system is the use of GNs. In an earlier work we have presented the GNs and their arithmetic and we have applied them for assessing the mean performance of a group of objects (students, players, etc.) participating in a certain activity.¹⁰ Therefore, here we shall recall only the information about GNs which is necessary for the understanding of the present work.   

A GN is an indeterminate number whose probable range is known, but which has unknown position within its boundaries. Therefore, a GN, say A, can be expressed mathematically in the form

Let us denote by w(A) the white number with the highest probability to be the representative value of  the GN A. E[a, b]. The technique of determining the value of w(A) is called whitenization of  A.

One usually defines w(A) = (1- t)a + tb,

with t in.^0,1 This is known as the equal weight whitenization. When the distribution

For general facts on GNs we refer to the book.¹¹ Further, for the needs of the present paper we introduce the following definition:

The GN A [a, b] has Rank of Greyness (RoG) equal to x, with x in R, if, and only if

b - a = x. We write then RoG (A) = x. Therefore, for a white number A we have

RoG (A) =0, whereas the RoG of a black number is defined to be equal to +.

Note that, if the values w(A) = y  and

RoG (A) = x are known, then the GN A[a, b] can be easily determined by

A Method of Solving Grey LP Problems

The general form of a Grey LP problem is the following:

Maximize (or minimize) the linear expression F = A₁x₁ + A₂x₂ +….+ A_nx_n subject to constraints of the form x_j  0,

A_i1x₁+ A_i2x₂ +…..+ A_inx_n <(>) B_i, where

i = 1, 2, …, m ,  j = 1, 2,,,, n and A_j, A_ij, B_i are GNs.

The proposed in this work method for solving a Grey LP problem involves the following steps:

• Whitenization of the GNs A_j, A_ij and B_i.
• Solution of the obtained by the previous step ordinary LP problem with the standard theory.
• Conversion of the values of the decision variables in the optimal solution to GNs with the desired RoG.

The last step is not compulsory, but it is useful in problems of fuzzy structure, where a vague expression of their solution is often preferable than the crisp one.

The following examples illustrate the applicability of our method: in real life applications:

Example 1: A furniture-making factory constructs tables and desks. It has been statistically estimated that the construction of a group of tables needs 2-3 working hours (w.h.) for assembling, 2.5-3.5 w.h. for elaboration (plane, etc.) and 0.75-1.25 w.h. for polishing. On the other hand, the construction of a group of desks needs 0.8-1.2, 2-4 and 1.5-2.5 w.h. for each of the above procedures respectively. According to the factory’s existing number of workers, no more than 20 w.h. per day can be spent for the assembling, no more than 30 w.h. for the elaboration and no more than 18 w.h. for the polishing of the tables and desks. If the profit from the sale of a group of tables is between 2.7 and 3.3 thousand euros and of a group of desks between 3.8 and 4.2 thousand euros,¹ find how many groups of tables and desks should be constructed daily to maximize the factory’s total profit. Express the problem’s optimal solution with GNs of RoG equal to 1.   

Solution: Let x₁ and x₂ be the groups of tables and desks to be constructed daily. Then the problem is mathematically formulated as follows:

Maximize F = [2.7, 3.3]x₁ + [3.8, 4.2]x₂ subject to constraints x₁, x₂ > 0 and

[2, 3]x₁ + [0.8, 1.2]x₂ <[20, 20]

[2.5, 3.5]x₁ + [2, 4]x₂ < [30, 30]

[0.75, 1.25]x₁ + [1.5,2.5]x₂ < [16, 16]

The whitenization of the GNs involved leads to the following LP maximization problem of canonical form:

Maximize f(x₁, x₂) = 3x₁ + 4x₂ subject to the constraints x₁, x₂  >0 and

2.5x₁ + x₂ <20

3x₁ + 3x₂ < 30

x₁ + 2x₂ <16

Adding the slack variables s₁, s₂, s₃ for converting the last three inequalities to equations one forms the problem’s first SIMPLEX matrix, which corresponds to the feasible solution f(0, 0) = 0, as follows:

Denote by L₁, L₂, L₃, L₄ the rows of the above matrix, the fourth one being the net evaluation row.  Since -4 is the smaller (negative) number of the net evaluation

In this matrix the pivot element 3/2 lies in the intersection of the second row and first column, therefore working as above one obtains the third SIMPLEX matrix, which is:

Since there is no negative index in the net evaluation row, this is the last SIMPLEX matrix. Therefore f(4, 6) = 36 is the optimal solution maximizing the objective function. Further, since both the decision variables x₁ and x₂ are basic variables, i.e. they participate in the optimal solution, the above solution is unique.

Converting the values of the decision variables in the above solution to GNs with RoG equal to 1 one finds that

x₁[3.5, 4.5] and x₂[5.5, 6.5].

Therefore a vague expression of the solution states that the factory’s maximal profit corresponds to a daily production between 3.5 and 4.5 groups of tables and between 5.5 and 6.5 groups of desks.

However, considering for example the extreme values of the daily construction of 4.5 groups of tables and 6.5 groups of desks, one finds that it needs 33 in total w.h. for elaboration, whereas the maximum available w.h. are only 30. In other words, a vague expression of the solution does not guarantee that all the values of the decision variables within the boundaries of the corresponding GNs are feasible solutions.

Example 2: Three kinds of food, say T₁, T₂ and T₃, are used in a poultry farm for feeding the chickens, their cost varying between 38 - 42, 17 - 23 and 55 - 65 cents per kilo respectively. The food T₁ contains 1.5 - 2.5 units of iron and 4 - 6 units of vitamins per kilo, T₂ contains 3.2 - 4.8, 0.6 – 1.4 and T₃ contains 1.7 – 2.3, 0.8 – 1.2 units per kilo respectively.  It has been decided that the chickens must receive at least 24 units of iron and 8 units of vitamins per day. How one must mix the three foods so that to minimize the cost of the food? Express the problem’s solution with GNs of RoG equal to 2.

Solution: Let x₁, x₂ and x₃ be the quantities in kilos for each food to be mixed. Then, the problem’s mathematical model is the following:

Minimize

F = [38, 42]x₁ + [17, 23]x₂ + [55, 65]x₃ subject to the constraints x₁, x₂ , x₃< 0 [1.5, 2.5]x₁+ [3.2, 4.8]x₂+ [1.7  2.3]x₃[24, 24],

[4, 6]x₁+ [0.6, 1.4]x₂+[0.8, 1.2]x₃ < [8, 8].

The whitenization of the GNs leads to the following LP minimization problem of canonical form:

Minimize f(x₁, x₂, x₂) = 40x₁ + 20x₂ + 60x₃ subject to the constraints x₁, x₂ , x₃< 0 and

2x₁+ 4x₂+ 2x₃24

5x₁ + x₂ + x₃    8 

The dual of the above problem is: the following:

Maximize g(z₁, z₂) = 24z₁ + 8z₂ subject to the constraints z₁, z₂ < 0 and

2z₁ + 5z₂ <40

4z₁ + z₂  < 20

2z₁ + z₂  < 60

Working similarly with Example 1 it is straightforward to check that the last SIMPLEX matrix of the dual problem is the

exceeds too much the minimal price of 133 cents. This means that the chosen RoG of the GNs is too large to provide a creditable vague expression of the problem’s solution. On the contrary, choosing for example the RoG to be equal

which is much closer to the minimal price of 133 cents.  In general, the smaller is the chosen RoG of the GNs the more creditable is the vague expression of the problem’s solution.

Example 3: A cheese-making company produces three different types of cheeseT₁, T₂ and T₃ by mixing cow-milk (C), sheep-milk (S) and milk powder (P). The required quantities in kilos from each kind of milk for producing a barrel of each of the three types of cheese are depicted, in form of GNs, in the following Table:

Table 1: Required quantities of milk 1