If the reader will
correct translation and will send the improved text to the author
(ochkov@twt.mpei.ac.ru), the author will tell a thank.
(Another articles of V.Ochkov)
Michael
Zhvanetsky is often asked where he took themes for his miniature. «I look
through the window and listen to the conversations in the street» – it is the
reply of great satirist». «And how do you keep in mind all these?» – new
question is followed. «Oh, I can not forget them!».
Worldly
plots are worth to collect for writing computer etudes. It is the hobby of this
book’s author.
The
author’s profession is the teacher of the institute (Moscow Power Engineering
Institute), where he gives courses by
informatics and adjacent disciplines. He directs the group of technologist and
programmers too. They work out the teaching programs and computer trainer for
thermoelectric power station and nuclear power station[1].
Our programs are necessary for Power Stations and power mergers. But the
notorious crisis of non-payments prevents to buy them. Such computer etude took
place in March 1997.
The
join-stock company Tambov-power had not got free money but wanted to buy our
programs. The electric power is necessary for Kotovsky paint and varnish plant
(PVP-Tambovskay region.) for production. Paint requires Moscow Power
Engineering Institute for repair the lecture-halls. Our scientific group is
necessary new computer «iron», tools and of course wages. For solving such
programs people invented money[2]
at dawn of civilization. The natural exchange-barter[3]
revived transfer of our country from something unreal to market. As we have
written previously there is not only one link for the chain was locked.
Fortunately MPEI got some computers. Two of them we exchanged to the paint. In
this combination only the part of described computer etude is concluded. If we
remember chess interpretation of the word «etude» – it is solution of the
puzzle by composition of the steps.
The
second part of the computer etude took already place in Tambov and Katovsk
(PVP). (The story will be told from the first person) In Tambov-power I was
given the letter for getting paint and varnish productions for 14 millions
roubles (of course it was old money) after I turned over our programs. It paid
off their debts for electric power. Then I was sent to Kotovsk. At first in the
sales department PVP I was refused to give paint bluntly for some strange debts
but not real money. But after threat of switching off light and heat they were
agreed with difficulty. Paint which suited[4]
the supply department MPEI cost 14 600 roubles for litre and was bottled to the
tares (to the drums it is the gist’s slang which I have picked up in Kotovsk).
The drum’s volume was 15 and 55 litres. Empty drums cost. 24 and 30 thousand roubles correspondingly.
The sales department’s worker of PVP (her name was Olga) making out the waybill
on the computer asked what capacities (pardon drums) I would take paint. The
flair of old collector of the computer etudes suggested to me that there is
typical and main thing real problem of linear programming where we have to
maximize the criterion function. This function is the summary volume of paint,
the variables are the quantity of full drums of 15 and 55 litres that we had to
take and three limitations – (1)
paint’s price can not exceed stipulated with Tambour-power 14 million roubles,
(2) it is not allowed to take not full jar (it is the limitation to integer
numbers) and (3) quantity of the jars different capacity is not allowed to be
negative numbers[5]. Olga
offered to help me with solving this optimization problem. With help of
calculator[6]
she tossed in that I had to take 16 big and 2 small drums containing 910 litres
of paint the sum of 13 million 814 thousand roubles. Remembered how I awfully
argued in Tambov-power and nevertheless increased the programs’ price from 12
to 14 million roubles I asked Olga if I could not lose 186 thousand i.e. not
leave them Tambov-power. She answered negatively and added that she solved such
problems seemingly every day optimizing as the paint’s price and its charging
to the containers different capacity[7]
and that she knew this problem very well.
Observing «the dance» of Olga’s fingers on the calculator’s buttons and
the numbers on it display I understood that Olga uses so-called «Workers’ and
Peasants’» and main thing unreliable algorithm of optimization: at first the
paint is selected in big tare and then the demand balance (or container’s
volume) is filled the paint in little tare. This way we pack a suitcase. At
first we put massive things to it and then we put to the empty space all small
things. Remembered once more Viona (look the footnote) I asked Olga why she did
not use the computer and tabular processor Excel for solving these problems. At
this moment there was worker page on the display of her computer. On the spot I
offered to show how she could it. In Excel there is Solver which dialogue window is called by the command Find the solution…from menu Service. In this window user shows the
cell keeping criterion function which value we have to maximize, the cells with
variables of search (at the beginning of optimization they are empty or keeps
the values of first approximation to the maximum) and limitations.
The algorithm of optimization with help of Solver Excel may call «lazy»:
user forms the table of calculation and says: «I want that you do so that»...
the criterion function took maximum (minimum, fixed) values but at that all
limitations were realized. For it this is enough to press the button Observe. Solver Excel gave us old
result– 16 big and 2 little drums. But I did not want to give it in.
There is good rule: one has to check the solution of the problem up as
others methods as the software. Besides we can forget about KISS-principle of
programming. It has no connection with kisses although good attitude to the
solving problem and to the computer in it we can find. KISS – is the abbreviation of English
phrase: «Keep It Simple, Stupid!» It
calls to solve the problem put by simplest method and to use the highly
algorithms and methods only when the simple way does not suit because of
duration of the calculation or because of irrational use others their resource
man and/or computer[8].
The simplest way of solving the problem put by is to sort out all
versions and to stop in optimum one. Fortunately there are only 1088 versions:
we could not take more than 63 little drums with paint or more than 16 big ones
[9]
for our 14 million roubles. The excess can be called «Computers’ and Workers’ and Peasants’» method of the solution.
In addition it can give the total-lot confidence in that the solution is right
and that the obtained solution is uniqueness. Even it can show that there are a
few such solutions. Such situation does not meet seldom in the integer linear
programming problems.
So the excess. Following the rule described above new method of the
problem’s solution is necessary to combine with the new software of its
realization. Of course it can be done
in Excel by forming the table of all solutions and/or writing the program of
the excess in programming language Visual Basic for Applications (VBA), build
in Excel. But Olga’s computer had Mathcad too. It quite successfully solves
different problems (including economic ones) with out real programming look-up
(BASIC, C, Pascal and others.). I had been working at the book for that moment.
Reader holds it now in his hands. The example with paint only decorates this book
(it is casual pun).
In Mathcad the report of “
control weighing” you can look at the picture 3.11. Commentaries make clear
what takes place in formulas. First of all the function Maximize gave fractional result as we had awaited (look the point 2) –we can take fraction quantity of big drums so
little drums are needless. Remembered epigraph and the title of the etude I had
to go to excess of the versions. In Mathcad-document are formed two matrixes
with name Îb (point 3.2) and St (point 3.3). Their elements (there are 1088 elements, i.e. there
are 17 columns and 64 lines) keep values of the volume (Îb) and of the worth (St) of paint depending on the combination of the packing.
Then (point 3.4) some elements of the matrix Îb are
named zero values if the given combinations of the parking do not suit by the
worth. The rest is the sleight hand and no mathematics: in point 3.5 number of
the line (variable N_15) and of the column (N_55)
are determined of the matrix Îb. There is the element with
maximum value on their crossing. The reply (6 little and 15 big drums)
surprised Olga unpleasantly. She disappointed me unwittingly for 5 litres of
paint and for 139 thousand roubles.
The method of searches the coordinates of maximum point that we can see
at the picture 3.11 (the double sum) has the considerable limitation: one
maximum element has to be in analyzable matrix (in our case it is matrix Ob).
If there are a few elements than the reply will be wrong: the sums of the points’ coordinates with the maximum elements will
be written to the variables N_15 and N_55. We have observed it in point 2 at the picture 3.9.
So Mathcad has spared me almost 150 thousand roubles. This money is not
so great but if you added to them new computer etude, new theme of the lecture
and new laboratory work and also the author’s emoluments for this book then the
play was worth the candles.
Come
back from Tambov to Moscow I analyzed this problem once more on my home
computer in a comfortable atmosphere. And there is what I have got.
First
of all if we change the initial installation of Solver the problem about paint
can be right explained by the Solver of Excel. For it we could not be lazy and
had to press the button Parameters…
in the dialogue window Search of the
solution. In new dialogue window Parameters of the search of the solution
it was enough to decrease the admissible deviation from 5 to 1%. After it the
right solution was found (15 big and 6 small drums). Frankly speaking in Excel
Solver is not bad, but its initial installations are. There are few users Excel
who apply Solver and press the button Parameters…
But who understand the heart of the problem of the optimization’s installations
does not work with Excel. One gets some misunderstandings because of it.
In
the second place both Olga and Excel, and Mathcad in different degree were
disappointed me a little[10]:
910 litres of the paint could be packed another way-13 small and the same
quality big drums[11].
In this case the balance was only 12 thousand roubles. And what is more the
solution of the problem about paint with new criterion function (worth of paint
in the drums) gives one more result: 37 small and 6 big drums. This way we get
one thousand roubles else from Tambov-power.
|
Version of packing (quantity
of small drums/quantity of big drums) |
2/16 |
6/15 |
13/13 |
37/6 |
|
Volume of paint (litres) |
910 |
915 |
910 |
885 |
|
The rest of money (roubles) |
186
000 |
47
000 |
12
000 |
11
000 |
In the
third place when I showed this table in the supply department MPEI then I was
told that the most optimum alternative both for me (money are important for me)
and for MPEI (it needs paint) the fourth one: we get almost all money from
Tambov-power. It seems strange but 885 litres of paint is more than 910 and
915. Point is that a lot of paint are lost because of tint from massive drums
to small tare. The drum with 15 litres can be taken to the maintainable lecture
hall and can be used completely.
The
wrong solution is got not only because of bad methods or bad software, but
because of user does not know exactly what he really wants. All programs of
linear programming’s solutions require the clear formulation of only one
criterion function[12].
The purpose is clear when we solve training problems. What purpose do we have
for in our life? But it is the mathematics but it is the philosophy…
The
excess method illustrated in the picture 3.11 has three own limitations:
1) the variables’ number can not be more than two as soon as in Mathcad
there are vectors and matrixes but there are not tensors (three- and so
dimensions matrixes)
2) when matrix is excessive dimension the computer refuses to deal with
it and it makes a protest as «there is
not enough memory»;
3) the calculation (if the excess can be called the
calculation) can last to long i.e. for a long time.
Two
limitations can be taken off when we go from the method of forming the matrix
(the picture 3.11) to the method of excess of the versions. We remember only
optimum plan that can be realized by the software. We have done it in our etude
number 6 (look at the pictures 6.31 and 6.32).
The
excess method turns out indispensable (that is it can not be so unnatural) when
the problem is integer but it looses its linearity[13]. In this case traditional methods (for
instance the simplex-method) often turn out feeble.
Nevertheless
the excess method in Mathcad will be always the misinterpretation of the first
water. Mathcad is the program of interpretive type with low speed of
realization of initial text. For excess we need not only the compilers but also
the compilers optimizing the time of realization the program.
