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.

Example 8. As the author sold the programs

(Russian text)

(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).

Picture 3.11.  The problem about paint

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.