A PRODUCTION PROBLEM INTERACTIVE 
PROTOTVPE OF LINEAR PROGRAMME 
INFORMATiCA3/87 
UDK 519.852 
Janez Barle, Janez Grad, Džordž Krstič* 
Ekonomska fakulteta Borisa Kidriča, Ljubljana 
Iskra Zorin, TOZD CAOP, Ljubljana, Vugbsiavia 
In the paper we describe our approaoh in developing a new program package comprising different models of linear pro-
gramming which ali together build up a sophistioated 3ystem for produotion planning and decision making. By means of 
it the necessary Information will be generated uhioh the top management of Iskra enterprise, Ljubljana Cone of the 
manufactures of electronic and computer equipment in Yugoslavia) is asking for. The input data are mainly retrieved 
from a data base and partly generated by means of a matrix generator. By generating different applioation matrioes 
with different objectlve functions various produotion plans can be studied. The speoiflo charaoteristics of the 
disGussed production problem are (i) the need for balanoing exports and imports and (ii) the ability to čope with a 
very high rate of inflation and very high rate of bank interest oharges. 
*Presented at "Deutsche Gesellsohaft fUr Operations Research - Tagung 1986", Ulm, W. Germany, 24. - 26. Sept. 1986. 
1. INTRODUaiOH 
Optimization methods of manufactured assortments are 
generally not used frequently enough withln the basic 
production process activities in most industrial esta-
blishments. Defined in a oommon linear programme form 
these methods could be particularly useful in those 
Industries where they offer the market many different 
products or their variants and where the maln pro-
portlon of the products, aimed for an unknown puroha-
ser, is to be stored in a narehouse for a certain 
period of tirne (KRSTIC, 3)- There are two main reasons 
why the usage of the production problem linear progra­
mme has not been adequate within the establishments 
where it could have proved' both possible and profitab-
le. One reason is the lack of knouledge of optimization. 
methods among the management who therefore are not in 
a State to draw and build up the necessary schemes and 
models, of possible applications. The seoond reason is 
the rather awkward and demanding presentation of the LP 
input data and the complex interpretation of the LP 
output results which makes them hard to understand and 
explain to the end-users. Three years ago in the Iskra 
enterprise, Ljubljana, we drew up adequate models and 
organized the necessary education oourses for end-
-users. We have been runnlng on the computer some opti­
mization methods for single members (faotories) of the 
enterprise sinoe then. Unfortunately ali the computer 
programs are batch orientid and are not linked toge­
ther with other parts of the Information system, despi-
te the use of some Interactive equipment. This leads 
to a substantial redundancy in data within the Iskra 
Information systera. 
A nevj programme package is being developed at present 
comprising different models of LP which ali together 
build up a much more sophistioated system for pro­
duction planning and decision making. By means of it 
the necessary fundamental information will be genera­
ted which the top management of a manufaturlng company , 
is asking for. The input data are [DOStly extracted 
from a data base and partly generated interaotively by 
means of an applioation orientated matrix generator. 
By generating different aplication matrioes with dif­
ferent objective functions, various produotion plans 
could be studied. The optiraal solutions obtained by LP 
are further processed by a computer aided expert 
system. In the man-oomputer interfaoe the most sultable 
production assortment is selected. Useful sugestions 
for the elimination of production bottle-neoks and 
other complementary information could also b^e obtained. 
The management and planning functions that link toge­
ther the finanoial and production parts are two impor-
tant domains of the program system applioation. 
The present LP program package, whlch is written in 
the APL programming language is of a prototype form. 
The final version will be in PASCAL. It solves linear 
prograrames with up to 200 constraints and with up to 
500 variables. The revised simplex method Is applied 
where the basis matrix is presented in product form 
with špike seleotions. Great attention has been paid 
in order to make the package as user friendly as 
possible and less attention has been paid to the pro­
gram' s effioiency in execution. 
In this paper we describe our approaoh and experience 
in developing the necessary softuare for solving LP in 
this particular fleld of applioation. 
2. CHARACTERISTICS OF THE PRODUCTION PROBLEM MODEL 
Let us first describe the general production (assort­
ment) problem of linear programming. 
Suppose that a company produces n products P., P-, ..., 
P by means of m different elements of the availlble 
pPoduction resources, such as machines, human capaci-
ties, finanoial means and other, the amounts of vihich 
are restricted by b,, b,, ..., b nithin the dlscussed 
period of tlme. The oonsunption of eaoh element of 
resources per unit of the produced product P. is knovm 
and we denote it by a.^, for ali j = 1, 2, ..., m and 
k = 1, 2, ..., n. There exist upper and loner pro­
duotion quantity bounds for each product due to the 
limited production resources, marketing restrlctions 
(possibllities) and the signed oontraots that impose 
certain obligations in production planning. The problem 
that arises most often is to define such an assortment 
and the corresponding quantities of the products which 
assure the maximum value of the profit after šale. 
Sometimes we try to optimize the net profit o. of pro­
duct Pj^,i.e. difference betueen its net selling priče 
and iti direct production costs. 
Denoting by L. the lower, by U. the upper possible and 
by Xj^ the optimum production quantity of P^^ we obtain 
\-^\ 
<U„ 
for k = 1, 2, 
or in a matrix notation 

30 
L<x<U 
Similarly we inay introduce 
^11 •••• ^In 
a-jT . >. • a^ 
• A = 
"21 "2n 
C = [c^, Cg, .... oj 
•ml 
and define the general produotion problem LP in the 
folloving way: 
Find Coompute) the solutlon of produotion quantities 
vector X, satisfying relations (1) and 
Ax < b 
for nhich the value of the objeotive function f(x) is 
niaximum, vrtiere 
f(x) = (c,x) , 
We can solve this problem by means of the general 
siinplex method. 
The specifio characteristics of the produotion problem 
LP for the needs od the Iskra enterprise take Into 
account the folloviing two characteristics of the 
present state of the econoiny in Yugoslavla: 
(I) The need for the olosest posslble balance 
between exports and imports vithin each parti-
cular enterpise 
(II) Very high rate of inflation and very high rates 
of bank interest oharges (MO % - 70 %). 
The possibilities of coping with the oonditions that 
aocompan/ the two characteristics differ very muoh 
among dlfferent enterprlses. We explaln here only 
briefly the basic characteristics of the foreign 
currency balanoing assortment problem which incorpora-
tes both the resouroes and users of foreign ourrenoy 
at the same tirne. More detalls on the subject are 
given in (KRSTiC and KLUCAR), I)). 
The basic inequallty which we add to the system of 
oonstraint functions is 
^n 
(E-I) ^ >D 
in 
where <E-I)|^ stands for the export - import trade 
balance of product Pj^ exported to some foreign 
customer. The same pPoduot may differ in the export 
priče E and the amount (priče) of the imported raw 
material I from one country to another one. We there-
fore consider it in the LP as a dlfferent product for 
each dlfferent oountr/. The values of the export -
- import trade balance for ali the products are stated 
in the same foreign currency unit, usually in DM or in 
US dollars. Product P. produced for the Vugoslav 
market would have a negative export - import trade 
balance (-1,), according to the above definition. D 
the above relation means the neoessary surplus in 
foreign trading which the enterprise needs for some 
other purposes such as the import of the nece3sary 
equipment, advertising in foreign countries and 
similar. 
The example of treating each product as a dlfferent 
one for each diferent cour.try shows that we have to 
deal with a large amount of LP input data (usually we 
optimize the produotion programme tvrioe a year, 
accomplishing S-"* consecutive oomputer runs each tirne 
and enabling the users to exchange some of the para-
meters). Here we use eleotronic spreadsheets as an 
additional and helpful resource for presentlng the ori­
ginal data in the LP input form. Nevertheless we are 
nowadays not satisfied with this kind of approach. We 
have decided therefore to develop a new program packa-
ge which is better orientated to the end-user. It is 
based on the results and experlences of the suooess-
fully performed produotion plannirj; model adjusted 
to the real environment and givine reasonable financial 
effeots both in Yu^oslav and foreign currencies. 
3. CHARACTERISTKS OF THE PRODU(n'ION PROBLEM INTERA-
CTIVE-TYPE MODEL (PACKAGE) DESIGN 
The discussed model (program package) consists of three 
modules: 
- LP input data preparation module; 
- LP module and 
- postoptimization module. 
In the folloMing we describe the basic oharacteristios 
of each of these modules. 
3.1. LINEAR PROGRAMME INPUT DATA PREPARATION MODULE 
It consists of three parts that handle the followlng 
aotivities: ' 
- retrieval of data from the Iskra enterprise MIS data 
base; 
- Interactive input and modification of the additional 
data; 
- building up the LP input data matrix. 
In order to retrieve data from the data base the user 
States the name of the product and the corresponding 
attributes that he uants. New products and new attribu-
tes can be added into the data base and raodificatlons 
to the retrleved data (prices to-oorae, expenses, .,.) 
can be performed interactively. The user can further 
state and define his conditions and demands with regard 
to restriotions on the production problem solution. He 
either accepts the already existir.g restriotions vithin 
the LP or imposes some new ones. 
From the user standpoint there exi3t two ways (modes) 
of LP data preparation: 
(i) The general mode which enables the comroon approach 
to the LP prooess definition (min of max value of 
the objectlve function, optional relation opera-
tors of the oonstraint functions, etc). 
(11) A mode oriented solely tovrards the produotion 
problem LP. It is user-friendly approach with 
additional references (options) explaining the 
raanageraent view and demands on standards and the 
pollcy which should be taken into account uithin 
the production process optimizlng procedures. The 
computer/user dialog inoludes question3 and 
ansviers about the chosen objectlve function vrtiich 
should be added to the LP data matrix of the 
oonstraint functions. In a sirailar way the user 
also gets the list of existing and available pro­
duction resources uhich he may use in the LP pro­
gramme. Here too he raay insert dlfferent rela-
tional operators. 
3.2. LINEAR PROCRA.MME MODULE 
The most efficient methods for solving LP problems are 
dlfferent variants of the simplex algorithm. Due to the 
dimensions of onr problem we could not use the standard 
siraplex method. It was necessary to employ the revised 
simplex method wlth basis matrix in a product form 
(MURTAGH, 5). HoMever, the expected dimensions of our 
problem don't require the use of the most sophisticated 
variants of this method. The most advanced feature used 
in our program is probably the algorithm for periodio 
refactorisation of the basis matrix with the "bumps and 
spikes selecting procedure". 
We must mention, however, that this module prograraned 
in APL shows relatlvely high ineffioienoy in execution 
corapared with a similar FORTRAN program vjhich is about 
ten times faster. 

31 
3.3. POSTOPTIMISATION MODULE 
Similarly to the LP input data preparation module, the 
piostoptimisation module enables two modes of operation. 
In the general mode, the oommon postoptinBlity (senai-
tivity) analysis is performed. It includea: 
a) computing the intervala vithln which the values 
of particular coefficients of the objective 
function can range and yet maintalning the same 
optimal solution (providing ali other elementa 
remain the same), 
b) computing the intervals within which the values 
of particular ooefflecients of the right-slde 
vector b can range and yet malntaining the same 
optimal basis (with changed values of the basic 
coefficients of x). 
Other standard type3 of LP output (MURTAGH, 5) are 
also provided. 
For our particular application another ncde of opera­
tion is available uhich is more user-friendly. It 
expresses ali LP output data in terms of production 
and finance. Using this mode production bottle-neoks 
beoause of teohnologioal oonstraints of foreign 
currency availability can be studied muoh more easily 
by the average end-user. Such interpretations also 
raise the level of user interesi and expertise in LP 
models within Iskra. 
t. PROTOTYPING APPROACH 
We extensively used the prototyping approach when 
working on these problems. Prototyping (BOAR, 1) is a 
relatively new method for extracting, presenting and 
refining a user's needs by building a vorking, 
user-friendly model of the ultimate system quickly and 
in context. The prototyping approach, by lnorementaly 
refining the model, leads to a bistter understanding of 
the problem and hence helps in the development of 
effective and efficient solutions. 
There are four basic stages in the prototyping life 
cycle: 
(i) Identify user's needs - define the problems and 
define the functions and data needed to solve 
them. 
(ii) Develop an Interactive model - quickly create a 
preliminary Korking model that incorporates the 
key items.identified in the previous step. 
(iii) Demonstrate the Interactive model - while demon-
strating the small system encourage the active 
role of the user - to add to and Ijnprove the 
systeii). 
(iv) Revise and evaluate the sy3tem - the prototype is 
altemately revised and implemented in the user'g 
environment until the system is aoceptable to 
both users and developers. 
For prototype building we use the APL prograinning 
language. This is a high level language which is parti-
cularly useful for the quick development of interaotive 
programnes (GILMAN, ROSE, 2). Its ability to perform 
vector and matrix operations make it also a povierful 
tool for testing mathematical algorithms. The main 
obstaole for uide use of APL is its inefficiency in 
execution. Nevertheless APL proved to be very. useful 
as a prototyping language for our particular type of 
application. We feel that our APL based prototype is a 
very good basic bor the development of a production 
solution, which will be in the PASCAL language. 
5. CONCLUSION 
Our project to build an LP production problem intera­
otive prototype is not finlshed. Up to nou our main 
attention was devoted to building an adaptively desi-
gned optimization model and appropriate LP module. The 
data preparation module and postoptimlsation module are 
not yet fully integrated into the system. 
The experience obtained in solving production problems 
for both particular factories and the uhole enterprise 
has encouraged us to continue and expand this project. 
REFERENCE 
1. Boar B.H., "Application Prototyping - a Requireinents 
Definition Strategy for the 80s", John Hiley 4 Sons, 
New Yort<, 198t. 
2. Gllman L., Rose A.J.,'APL: an Interactive ApproachT 
John Wiley 4 Sons, New York, 1976. 
3. Krstio D., "The Use of Univac LP and MCS Packages", 
in: UUA/E Conference Technioal Papers, Wien, Nov. 
1987: The Effect of Communications Policy and 
Technology on Computer Planing, UUA/E, London, 1979, 
p. 3>*(>. 
U. Krstič D., Klučar M., "Optimiranje proizvodnih pro­
gramov ob upoštevanju pokritja deviznih potreb z 
izvozom". Organizacija in kadri, 18 (1985), 3-t, 
p. 218 (in Slovenian). 
5. Murtagh B.,'Advanced Linear Programming; Coraputa-
tion and Practice' McGraw-Hill, New York, 1981.