The article deals with the problem of introducing cloud calculations into 10th-11th graders' training to solve optimization problems in the context of the STEM-education concept. After analyzing existing programmes of optional courses on optimization problems, the programme of the optional course Optimization Problems has been developed and substantiated implying solution of problems by the cloud environment CoCalc. It is a routine calculating operation and not a mathematical model that is accentuated in the programme. It allows considering more problems which are close to reality without adapting the material while training 10th-11th graders. Besides, the mathematical apparatus of the course which is partially known to students as the knowledge acquired from such mathematics sections as the theory of probability, mathematical statistics, mathematical analysis and linear algebra is enough to master the suggested course. The developed course deals with a whole class of problems of conventional optimization which vary greatly. They can be associated with designing devices and technological processes, distributing limited resources and planning business functioning as well as with everyday problems of people. Devices, processes and situations to which a model of optimization problem is applied are called optimization problems. Optimization methods enable optimal solutions for mathematical models. The developed course is noted for building mathematical models and defining a method to be applied to finding an efficient solution.
1.1
Modern society is evolving fast. The character of current changes is conditioned, first of all, by rapid informatization of people’s life. The scientific-technical and informational advance of the 20th-21st centuries has caused transition from the industrial society to the informational one. These changes are going on. Experts predict the socalled smart society appearing in the nearest decade. Rapid paces of life dictate their terms of success to people.
A person has to be able to make his/her activity and surrounding processes efficient in terms of time expenditures for study, work and transport losses. The problems of optimizing control over a small group of classmates working on a project or managing a business, etc. should also be solved. 1.2
Development of optional and selective courses with the inter-subject integral content is one of the most urgent issues of subject-oriented instruction of senior school students. These courses allow students, on the one hand, to better visualize prospects of a chosen future profession, on the other hand, – to satisfy their educational needs to the fullest.
It is worth noting that in solving optimization problems, the notion of an optimization problem model is as important as that of an optimization problem. Correspondingly, a target function is a mathematical function to be optimized in a problem, while limitation is a set of requirements to problem parameters in the form of equations or inequalities. If the target function is linear and linear limitations are imposed on its arguments, a corresponding optimization problem refers to the problem class of linear programming.
From the practical point of view, optimization problem solution means that a person in his/her activity aimed at achieving a set goal always strives for the best or the most efficient ways of action if there is an opportunity to choose out of an endless variety of methods the one that helps to achieve it. Ways of action or strategies are often characterized by a value. In this case, the problem of choosing the best strategy implies finding an extremum – the minimum or the maximum of this value.
It is also important to admit that the mathematical apparatus of optimization problem solution is used not only as a tool of ordinary calculation. It is also essential for decision making while choosing the most efficient variant to achieve the best result.
It is essential to accentuate the importance of optimization problem solution aimed at demonstrating applicability of inter-subject connections between mathematics and other subjects. It should be noted that complex optimization problems associated with long calculations should be solved professionally, while 10th-11th graders are able to deal with less complicated ones. Such problems include those of the external ballistics theory (determining the maximum missile range, building a safety parabola equation), optimization problems in studying the topic Percentage, etc.
Thus, optional courses dealing with optimization problems allow showing 10th-11th graders how to formalize decision making problems, solve them by applying mathematical tools and how to apply obtained solutions to practice.
At present, there are not so many authors’ optional courses dealing with optimization problems. Yet, the available ones do not accentuate application of information technologies to providing instruction which is a sign of meeting modern requirements to training organization under the STEM concept. Some researchers [2; 4; 5; 6; 7; 9; 10; 11] think that CoCalc can be one of software tools to be applicable to solving optimization problems.
Research methods include theoretical analysis and synthesis of data from research and scientific-pedagogical literature concerning the research problem, analysis of regulatory and legal documents in education that regulate optional courses, investigation into training programmes, teaching aids, programmes of standard and optional courses for 10th-11th graders in similar subjects. 2
The STEM-concept in education is aimed at forming students’ basic ideas of understanding unity of informational principles of building and functioning of various systems and management processes in nature, engineering and society.
Considering these postulates, we have developed the course Optimization Problems. Its relevance is explained by rapid updating of science-intensive technologies calling for highly-qualified specialists of a new type – active, creative, able to enrich their knowledge on elaborating and mastering new generations of machines and industrial processes. According to the competence-oriented approach, there appears a necessity for new interpretation of subject instruction and new conditions of incorporating instruction into formation of students’ competences. Therefore, it is required to find critically new characteristics of subject instruction. New educational standards aimed at self-development, self-identity and self-realization make educators look for new approaches and forms of training organization as well as new content of traditional training forms. In view of this, principles of training organization are changing. Outof-class forms of training are prioritized, while principles of independent work organization are becoming more extensive. Independent work is a cognitive activity associated not only with knowledge acquisition, but also with practical experience in the context of competences.
The developed course considers the whole class of conventional optimization problems that vary in their content. They can be associated with designing devices and technological processes, distributing limited resources and planning business functioning as well as with everyday problems of people. Devices, processes and situations to which a model of optimization problem is applied are called optimization objects. Optimization methods enable optimal solutions to mathematical models. The developed course is noted for building mathematical models and defining the method to be applied to finding an efficient solution.
The specific feature of the suggested course is simple presentation of the training material based on concrete examples and problems. Studying linear programming by applying mathematical materials and solving optimization problems which are understandable for senior school students is of particular interest in this course. In this case, optimization problems are treated as those reduced to finding the maximum or the minimum value. These problems are also called extremal ones as finding the maximum and the minimum value is neither more nor less than finding an extremum – the maximum or the minimum of a function.
While solving such problems, scientific thinking and the ability to see a situation as a whole are formed. Cognitive interests and abilities to find a way out of critical situations with minimum losses are also developed. It is evident that an employee possessing these qualities is much more valuable for society.
Basic principles of optimization problem solution by using computer technologies can be taught at Informatics classes with enhanced mathematics study as they require fundamental mathematical training. As the range of topics is very wide, it is reasonable to treat solving even one of them as a project.
Let us look into some variants of projects to be proposed to students within the optional course Optimization Problems. First, students should be provided with basic algorithms in CoCalc [4; 8]. While doing a project, students get acquainted with methods of optimization problem solution. One should accentuate the recommendations for improving functioning of a process to be simulated while discussing project results.
There are several stages in teaching optimization problem solution.
Optimization problem 1. Any port in a storm [1]: there is significant danger to boats
caught out in the open sea during a storm. Ideally, boats will dock before the storm hits
and wait it out. The map above shows 20 orange boats out at sea. With a storm
approaching, each boat needs to be directed to one of three docks. Docks have a limited
number of spaces available for boats (indicated by the rectangular spaces). Altogether,
there are 20 boat spaces available. The boats are clustered into three areas and each area
varies in distance to the docks (as indicated by the black arrows). All boats must be
assigned to one space in a dock. Question: What is the minimum possible total
distance traveled by all boats? More detailed information is presented in Fig. 1.
Students must build a mathematical model of the problem. To solve the problem we
offer students the following code in CoCalc [
XVar.append('X'+`i+1`) for j in range(m-1):
TVar.append('T'+`j+1`) p=-1 q=-1 isfeasible=1 problemfeasible=0 #Atemp=matrix(QQ, m,n) while (isoptimal==0 and isunbounded==0): isoptimal=1 isunbounded=1 isfeasible=1 problemfeasible=1 p=-1 q=-1 #checks to see if current position is feasible for i in range(m-1): if A[i,n-1]<0 and p<0: p=i isfeasible=0 isoptimal=0 isunbounded=0 #Checks to see if problem is feasible if isfeasible==0: problemfeasible=0 for k in range(n-1): if A[p,k]<0 and q<0: q=k problemfeasible=1 if problemfeasible==0: print('The problem has no feasible solutions') p q else: #checking last row to see if optimal (step 1), #it's optimal when all are negative for i in range(n-1): this') if A[m-1,i]>0:
isoptimal=0 if isoptimal==1 and isfeasible==1:
print('This is optimal, ignore everything after #finding the right [p,q] to pivot on and will only # pivot if point is feasible if isoptimal!=1 and isfeasible==1: q=-1 #finding position q to pivot on for i in range(n-1): if A[m-1,i]>0 and q<0:
q=i; q #checking column q to see if all negative (step 4) for k in range(m-1): #A[k,q] if A[k,q]>0:
isunbounded=0 if isunbounded==1:
print('This is unbounded') p=-1 #finding position p to pivot on (step 5) for j in range(m-1): if A[j,q]!=0: if A[j,n-1]/A[j,q]>=0 and A[j,q]>0: if p<0:
p=j; p if p>=0 and A[j,n-1]/A[j,q]<A[p,n-1]/A[p,q]:
p=j; p print('pivot on position') p q #the temporary matrix pivots on [p,q] Atemp=matrix(QQ, m,n) for i in range(m): for j in range(n): if i==p and j==q:
Atemp[i,j]=1/A[p,q] if i==p and j!=q:
Atemp[i,j]=A[i,j]/A[p,q] if i!=p and j==q:
Atemp[i,j]=-1*A[i,j]/A[p,q] if i!=p and j!=q:
Atemp[i,j]=(A[i,j]*A[p,q]-A[i,q]*A[p,j])/A[p,q] Xp=XVar[q];Xp Tp=TVar[p];Tp XVar[q]=Tp TVar[p]=Xp Atemp A=Atemp XVar
TVar Optimization problem 2. Cell Towers [3]: as the head of analytics for a cell phone company, you have been asked to optimize the location of cell towers in a new area where your company wants to provide service. The new area is made up of several neighborhoods. Each neighborhood is represented by a black house icon in the accompanying image. A cell tower can be placed on any square (including squares with or without a neighborhood). Once placed, a cell tower provides service to 9 squares (the 8 adjacent squares surrounding it and the 1 it sits on). For example, if you placed a cell tower in B2, it would provide service to A1, B1, C1, A2, B2, C2, A3, B3, and C3. The company recognizes that it may not be worthwhile to cover all neighborhoods, so it has instructed you that it needs to cover only 70% of the neighborhoods in the new area. Each cell tower is expensive to construct and maintain so it is in your best interest to only use the minimum number of cell towers. Question: What is the minimum number of cell towers needed to provide service to at least 70% of the neighborhoods? More detailed information is presented in Fig. 2. Students must build a mathematical model of the problem. To solve the problem, we offer students the same code as in optimization problem 1.
No 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 4 5 6 4 5 3 2 5 4 3 6 3 3 7 8
No 16 17 18 19 20 21 22 23 24 25 26 27 28 29 1 3 3 2 4 5 2 6 2 1 1 4 3 5
Optimization problem 3. For the project, students can be offered the task of finding the optimal route with restrictions. More detailed information is presented in Table 1 and Fig. 3. There are a certain number of containers in each quarter, each with a capacity 1,1 m3. Just such containers 110. The following additional conditions are met: the volume of the truck body is limited and equal 43 m3. The point of departure of a filled truck is point B. The truck starts its journey from Base to Point A. The following flights provide a quarterly cycle (from Point B to Point B). The last point of arrival van-tag with an empty body – Point A. Students should independently ask questions and solve the problem.
To solve the problem, we offer students the following code in CoCalc: g = graphs.ChvatalGraph() g = g.minimum_outdegree_orientation() p = MixedIntegerLinearProgram() f = p.new_variable(real=True, nonnegative=True) s, t = 0, 2 for v in g: if v != s and v != t: p.add_constraint( sum(f[(v,u)] for u in g.neighbors_out(v)) - sum(f[(u,v)] for u in g.neighbors_in(v)) == 0) for e in g.edges(labels=False):
p.add_constraint(f[e] <= 1) p.set_objective(sum(f[(s,u)] for u in g.neighbors_out(s))) p.solve() # rel tol 2e-11 Stage 1. Studying theoretical principles. It includes the notion of an optimization problem and the necessity to solve such problems in modern life. There are some problem examples provided.
Various situations require absolutely different solutions depending on the chosen or set criterion.
For example, it is possible to spend 50 minutes driving from one city to another. But if part of the route is covered by railway and then by bus, it will take 30 minutes only. It is evident that the latter solution is better if it is necessary to get to one’s destination in the shortest time possible. In other words, this solution is the best by the criterion of time minimization. According to another criterion (for example, reduction of expenditures or the number of changes), the former solution is better. Thus, to solve problems, it is essential to analyze quantitative parameters – minimum expenditures, minimum deviations from the standard, maximum speeds, revenues, etc.
Stage 2 is studying the general plan of optimization problem solution. Here, the notions of a target function, admissible solutions, and the system of limitations are introduced.
The general plan of optimization problem solution includes: ─ investigation into an object to define parameters required to solve the problem; ─ descriptive simulation, i.e. determining basic connections and dependencies between parameters; ─ mathematical simulation; ─ choice or development of the method for solving the problem; ─ computerized implementation of the solution; ─ analysis of the solution obtained.
One of the problems is considered in the form of a mathematical model as a theoretical basis to receive practical solutions on the computer. Next, a practical method is selected and implemented. After obtaining the result, one should analyze it considering various variants of optimizing the process by the ready-made algorithm with initial data changed.
Stage 3. Theoretical and practical implementation of solving any optimization problem by applying systems of computer mathematics or other tools.
The ability to solve optimization problems is essential for modern people. This should be taught. Introduction of the project course Optimization Problem could be a way out.
If the current variant of training is used without any chance of introducing an optional course like this, the work can be organized as follows. Mathematical models can be created at Mathematics classes, while algorithms of solving these problems by means of CoCalc can be implemented at Informatics classes. Abilities acquired through studying under this mode will help students become successful in new social conditions.
The course programme was based on existing programmes of optional courses of similar character as well as teaching aids and programmes of optional courses.
The developed course is connected with secondary school basic courses of Mathematics (sections Linear Equations and Inequities, Solution of Systems of Linear Equations and Inequities) and Informatics (Mathematical Simulation, Spreadsheets).
The developed course is aimed at theoretical and practical study of basic notions and methods of optimization as well as basic principles of the decision making theory to form students’ ideas of applying the mathematical apparatus to solving problems of finding efficient solutions. While achieving the set aim, a number of tasks are solved: ─ getting students acquainted with basic principles of the decision making theory and optimization methods; ─ demonstrating application of optimization methods to practical activities; ─ introducing methods of solving linear programming problems and their application to students; ─ forming students’ abilities of solving decision making problems by applying studied optimization methods.
The optional course Optimization Problems comprises 35 hours designed for a semester. The recommended number of hours per week in the 10th grade is 2, in the 11th grade – 1.
The course consists of two main content modules: 1. The role of the theory and methods of decision making in the modern world (17 hours); 2. Linear optimization (17 hours).
The content of the first module includes general statement of the decision making problem in various spheres of human activity as well as some decision making methods. Presentation of theoretical materials of this section should be illustrated by concrete examples and problems. This module covers the following topics: ─ The decision making theory (basic notions and definitions); ─ The decision making theory in economics; ─ Mathematical simulation of decision making; ─ Collective decision making. Models of collective choice; ─ Decision making in the organization theory.
The second module includes the most important, yet at the same time, simple section of the decision making theory – linear programming. It enables students to comprehend applicability of systems of linear equations and inequities, methods of studying and building function diagrams, mathematical modules of real-life objects and processes to human activity. Presentation of theoretical materials of this section should also be illustrated by concrete examples and problems. This module covers the following topics: ─ Basic principles of linear programming; ─ Linear optimization problems; ─ The graphical method of solving linear programming problems; ─ The simplex-method of solving linear programming problems; ─ Solving linear programming problems by means of CoCalc.
The suggested programme of the optional course is of a rough character and open to changes to enable a teacher to correct and modify the course depending on the type of an educational institution where the course is taught. It should be noted that the course programme includes some modules and topics that can be used as independent optional courses if their content is expanded.
The course programme provides theoretical and practical classes and independent work (solo work on problem solution). The distance mode of training is recommended.
After mastering the programme material, a student can get an idea of practical application of the decision making theory and optimization methods to everyday life and professional activity. Besides, there are the following requirements to students’ knowledge and abilities to be formed after mastering the course: ─ The student knows basic notions of the decision making theory, methods of decision making and optimization, basic problems of linear programming, the simplexmethod of solving linear programming problems; ─ The student is able to correctly choose a relevant solving method to optimize a problem and implement it; ─ The student possesses methods of solving problems of linear programming, abilities of applying CoCalc and modern mathematical tools to solving practical problems. 3
After analyzing existing programmes of optional courses on optimization problems, the programme of the optional course Optimization Problems has been developed and substantiated implying solution of problems by the cloud environment CoCalc. It is a routine calculating operation and not a mathematical model that is accentuated in the programme. It allows considering more problems which are close to reality without adapting the material while training 10th-11th graders. Besides, the mathematical apparatus of the course which is partially known to students as the knowledge acquired from such mathematics sections as the theory of probability, mathematical statistics, mathematical analysis and linear algebra is enough to master the suggested course. The developed course deals with a whole class of problems of conventional optimization which vary greatly. They can be associated with designing devices and technological processes, distributing limited resources and planning business functioning as well as with everyday problems of people. Devices, processes and situations to which a model of optimization problem is applied are called optimization problems. Optimization methods enable optimal solutions for mathematical models. The developed course is noted for building mathematical models and defining a method to be applied to finding an efficient solution.