key: cord-0046000-r19ipjw3
authors: Wojas, Włodzimierz; Krupa, Jan
title: Supporting Education in Algorithms of Computational Mathematics by Dynamic Visualizations Using Computer Algebra System
date: 2020-05-25
journal: Computational Science - ICCS 2020
DOI: 10.1007/978-3-030-50436-6_47
sha: dc56017fb4289857886746a48a2fc0b1963615a6
doc_id: 46000
cord_uid: r19ipjw3

Computer algebra systems (CAS) are often used programs in universities to support calculations and visualization in teaching mathematical subjects. In this paper we present some examples of dynamic visualizations which we prepared for students of Warsaw University of Life Sciences using Mathematica. Visualizations for simplex algorithm and Karush-Kuhn-Tucker algorithm are presented. We also describe a didactic experiment for students of the Production Engineering Faculty of Warsaw University of Life Sciences using dynamic visualization of the network flow problem.

The development of computational mathematics techniques, technologies and tools in recent decades has created new educational challenges in teaching mathematics and IT subjects in higher education. On the other hand, the development of computational mathematics technology has created new educational perspectives based on the possibility of using new computational and visualization tools in education. CAS such as wxMaxima, Mathematica, Maple, Sage, and others are often used to support calculations and visualization in teaching mathematical subjects [6, 7, [9] [10] [11] . In teaching mathematical algorithms in the field of mathematical analysis, mathematical programming or graph theory, the possibility of symbolic calculations and visualizing the algorithm steps seems useful from an educational point of view. This allows a better and deeper understanding of the topic. In this paper we present two examples of dynamic visualizations which we prepared for students of the Faculty of Informatics and Econometric of Warsaw University of Life Sciences using Mathematica [8, 12] within the course of Mathematical Programming. We present dynamic visualizations for simplex algorithm for linear programming (LP) problem [2, 5] and for nonlinear programming (NLP) problem which we solve using Karush-Kuhn-Tucker (KKT) algorithm [3, 5] . A didactic experiment for students of the Production Engineering Faculty of Warsaw University of Life Sciences using dynamic visualization of the network flow problem will also be discussed.

In this example the authors present some new complex approach to visualization of simplex method steps. The authors propose to use for visualization expanded Simplex Tableau which contains for each simplex step: current simplex table for this step, graph of feasible region for canonical form of LP problem with current corner point and "simplex path", level sets of goal function (hyperplanes: lines in 2D, planes in 3D), axis with current value of objective function for this step.

Let us solve the following LP problem:

Maximize z = 4x 1 + x 2 + 6x 3

Subject to

Corresponding to it canonical form is:

Let S be feasible region for this LP problem (in standard form). S is presented in each Fig. 1, 2 , 3, 4 and 5. It is convex polyhedral set with vertices at: v 1 = (0, 0, 0), v 2 = (9, 0, 0), v 3 = (9, 5, 0), v 4 = (0, 5, 0), v 5 = (0, 0, 1), v 6 = (3, 0, 3), v 7 = (6, 0, 3), v 8 = (9, 5, 1), v 9 = (6, 5, 4) , v 10 = (0, 5, 4) , v 11 = (0, 5/2, 7/2). In each Figs Finally we get that z max = z(6, 5, 4) = 53. The above example and also another 2D and 3D examples, were presented students of Informatics and Econometrics Faculty of Warsaw University of Life Science in the framework of the course of Mathematical Programming. These were introductory examples illustrating the simplex algorithm steps. Using the expanded Simplex Tableau allows students to trace the steps of simplex algorithm in quite comprehensive manner -taking into account both computational and geometric aspects of the algorithm. From Figs. 2, 3 and 4 we can see that the planes: 4x 1 + x 2 + 6x 6 = 6, 4x 1 + x 2 + 6x 6 = 30, 4x 1 + x 2 + 6x 6 = 42 are not supporting planes of the feasible region for this LP problem S, but from Fig. 5 we can see that the plane 4x 1 + x 2 + 6x 6 = 53 is supporting plane of S (this can be better seen in the dynamic versions of the Figs. 1, 2, 3, 4 and 5 in the Electronic supplementary material). So we may conclude independently that z max = z(6, 5, 4) = 53. We cannot find analogical approach to present simplex algorithm steps in available literature.

We will consider NLP problems in the following form:

where n and m are positive integers, X is a subset of R n and f, g i are realvalued functions on X with at least one function of f, g i (i = 1, 2, . . . , m) being nonlinear. A feasible region of the NLP problem is defined as a set of all possible points that satisfy all the problem's constraints.

We start with the following theorem [3] :

Theorem (Karush-Kuhn-Tucker Necessary Conditions). Let X be a nonempty open set in R n , and let f : R n → R and g i : 

x − 1 ≥ 0 and next we visualise the solution graphically using dynamic plots. Formally, KKT necessary conditions require an independent solution of two tasks -one for minimum and one for maximum. We first solve the NLP problem for minimum and next the NLP problem for maximum. a) Consider the following problem:

Let

. So we must solve the following system:

Case 2. Let g 1 (x, y) = 0, g 2 (x, y) = 0 and g 3 (x, y) > 0. Hence 5 − x − y = 0 and xy − 4 = 0 and λ 3 = 0. So x = 4 and y = 1 hence −1 = −λ 1 + λ 2 and 2 = −λ 1 + 4λ 2 hence λ 2 = 1 and λ 1 = 2. ∇g 1 (4, 1) = [−1, −1], ∇g 2 (4, 1) = [1, 4] are linearly independent. Case 3. Let g 1 (x, y) = 0 and g 2 (x, y) > 0 and g 3 (x, y) = 0. Hence λ 2 = 0, x = 1 and y = 4, but g 2 (1, 4) = 0 contradicts assumption in current Case 3 g 2 (x, y) > 0. Case 4. Let g 1 (x, y) = 0 and g 2 (x, y) > 0 and g 3 (x, y) > 0. Hence

It follows that λ 1 = 1. Hence y = −1/2 and x = 11/2. g 2 (11/2, −1/2) = −11/4− 4 < 0 contradicts assumption in current Case 4 g 2 (x, y) > 0.

Case 5. Let g 1 (x, y) > 0 and g 2 (x, y) = 0 and g 3 (x, y) = 0. Hence λ 1 = 0 and x = 1 and y = 4, hence −1 = 4λ 2 + λ 3 and 8 = λ 2 . So λ 3 = −33 < 0 contradicts nonnegativity of λ 3 . Case 6. Let g 1 (x, y) > 0 and g 2 (x, y) = 0 and g 3 (x, y) > 0. Hence

Case 7 and 8. Let g 1 (x, y) > 0 and g 2 (x, y) > 0 and g 2 (x, y) ≥ 0. Hence

From Cases 1, 2, 3, . . . , 8 it follows that the only point which satisfies KKT conditions is (4, 1), λ 1 = 2, λ 2 = 1 and λ 3 = 0.

We solve this problem also using Mathematica procedures. We present the solution below: Listing 1.1: Mathematica code for point a):

In [3] 

In [4] 

Let g 1 (x, y) = −x 2 − 4y 2 + 1, g 2 (x, y) = −1 + x + 2y and g 3 (x, y) = x − 1. −∇f (x, y) = λ 1 ∇g 1 (x, y) + λ 2 ∇g 2 (x, y) + λ 3 g 3 (x, y) is equivalent to:

. So we must solve the following system:

where λ 1 ≥ 0, λ 2 ≥ 0 and λ 3 ≥ 0. Case 2. Let g 1 (x, y) = 0 and g 2 (x, y) = 0 and g 3 (x, y) > 0. Hence 5−x−y = 0 and xy − 4 = 0 and x > 1 and λ 3 = 0. So x = 4 and y = 1 hence 1 = −λ 1 + λ 2 and −2 = −λ 1 + 4λ 2 hence λ 2 = −1 < 0 contradicts nonnegativity of λ 2 . Case 3. Let g 1 (x, y) = 0 and g 2 (x, y) > 0 and g 3 (x, y) = 0. Hence λ 2 = 0, and x = 1 hence

Hence y = 4 and λ 1 = 8 and hence λ 3 = 9 (Case 1). Case 4. Let g 1 (x, y) > 0 and g 2 (x, y) = 0 and g 3 (x, y) = 0. Hence λ 1 = 0 and x = 1 and y = 4, hence 1 = 4λ 2 + λ 3 and −8 = λ 2 -a contradiction.

Case 5. Let g 1 (x, y) = 0 and g 2 (x, y) > 0 and g 3 (x, y) > 0. Hence λ 2 = λ 3 = 0 hence λ 1 = −1a contradiction. Case 6. Let g 1 (x, y) > 0 and g 2 (x, y) = 0 and g 3 (x, y) > 0. Hence λ 1 = λ 3 = 0 hence 1 = λ 2 y and −2y = λ 2 x. λ 2 must be nonzero, so y = 1 λ2 hence λ 2 2 = − 2 x < 0 because x > 1-a contradiction. Case 7 and 8. Let g 1 (x, y) > 0 and g 2 (x, y) > 0 and g 3 (x, y) ≥ 0. Hence λ 1 = λ 2 = 0, hence 1 = λ 3 and y = 0 hence g 2 (x, 0) = −4 < 0 contradicts assumption in current Case 7 and 8 g 2 (x, y) > 0.

From Cases 1, 2, . . . , 8 it follows that the only point which satisfies KKT conditions is (1, 4), λ 1 = 8, λ 2 = 0 and λ 3 = 9.

f (1, 4) = 15, f (4, 1) = −3.

The set D is compact and f is continuous on it so finally we get: the greatest value 15 and smallest value −3 of f on D are attained at points (1, 4) and (4, 1) respectively.

In Fig. 6 we present the solution of the above NLP problem graphically using dynamic plots. We solve the problem from Example 2 using graphical method. In the Fig. 6 we present Mathematica dynamic plot for the Example 2. The level sets is a family of parabolas y 2 − x = c.

The dynamic versions of the Fig. 6 can be found in the Electronic supplementary material: https://drive.google.com/open?id=1vgBC1ij7Z9mNL8 nmhVgrwi3qFRzzhYN.

Global maximum of the function f (x, y) = y 2 − x at point (1, 4) we can determine graphically from the level set: y 2 −x = 15. Similarly, global minimum of the function f at point (4, 1) we can determine graphically from the level set:

This example and also another 2D and 3D examples, were dedicated students of Informatics and Econometrics Faculty of Warsaw University of Life Science within the course of Mathematical Programming. These were introductory examples illustrating the KKT method. Even relatively simple NLP problems with three or four constraints can lead to the need to consider many subcases, what is rather not suitable for hand calculations in class. The presented example shows that calculations are possible to do in class with support of computer programs such as Mathematica. Visualization presents graphical way of reaching the optimal solution of the NLP problem (for min and for max respectively) 

This experiment was carried out in the form of a mathematics test on a group of 41 first-year students of the Production Engineering Faculty of Warsaw University of Life Sciences within the course of Higher Mathematics II. Students were after a semester course of Higher Mathematics I which included differential and integral calculus of functions of one variable. These students have not encountered the topic of network flows before. The experiment consisted of five parts. In the first part, students were introduced to the basic definitions of networks and flows in networks [1, 4] . The following definitions were presented: graph is a pair (N, A) where N is a finite set and A is a set of ordered pairs (v, w) such that v, w ∈ N . Elements of the set N we call nodes, and elements of the set A we call directed arcs.

Most often directed graph is presented as a set of points representing nodes connected by arcs with arrows. (N, A) from node v 1 to node v 2 is a sequence of nodes and arcs:

v 1 − k 1 − v 2 − k 2 − . . . − v n−1 − k n−1 − v n without any repetition of nodes where k i = (v i , v i+1 ) ∈ A for i = 1, 2, . . . , n − 1 and v i ∈ A for i = 1, 2, . . . , n.

We define sets: (N, A, u) from source s ∈ A to the sink t ∈ A is a function f : A → [0, ∞) which satisfies the following conditions:

A number V = div f (s) we call the value of a flow f . A flow in pure network is also called static flow. The definitions were discussed by the lecturer on the example of a simple network 1 (Fig. 7) drawn on a table with simple examples of flows in this network. The numerical values of flows on the arcs were recorded above the arcs. The first part lasted about 25 min. In the second part, students were given the first task to solve. It was based on giving an example of flow in the network 2 ( Fig. 8) from source s to the sink t with the value of flow V = 5. Students received 10 minutes of time to solve this task. In the third part, two dynamic visualizations of flows in network were presented to the students: Example 3 and Example 4 presented in the Subsect. 4.1. These visualizations were discussed during the presentation by the lecturer. The presentation of the visualization together with the discussion lasted about 10 min. In the fourth part, students were again given a task to solve. It consisted, as before, of giving an example of flow in the network 3 ( Fig. 9 ) from source s to outlet t with the value of flow V = 4. Students were given 10 minutes of time to solve this task. In the fifth part, students answered the question -to what extent dynamic flow visualizations were useful in solving the task in the fourth part. They chose one of four options: a) they were not helpful, b) they were a bit helpful, c) they were helpful, d) they were very helpful. We received the following experiment results: only 24% of students presented the correct solution to the task in the second part of the experiment, 66% of the students presented the correct solution to the task in the fourth part of the experiment (after seeing dynamic visualizations), 5% of the students chose the answer a), 19% answer b), 54% answer c) and 22% answer d).

For directed graph (N, A) presented below we define: s = 1, t = 7, V = 5, u(k) = 3 for all k ∈ A. We present two different static flows: static flows 1, static flows 2 in the pure network (N, A, u) . 

This article presents visualizations for two algorithms: simplex algorithm for LP problem and KKT algorithm for NLP problem which we have prepared for students of Informatics and Econometrics Faculty of Warsaw University of Life Sciences. The visualizations were prepared using Mathematica. In Example 1 we demonstrate some new didactic proposition -expanded simplex tableau. The expanded simplex tableau contains for each algorithm step: current simplex table in traditional form for this step, graph of feasible region for canonical form of LP problem with current corner point and current simplex path, level sets of goal function (hyperplanes : lines in 2D, planes in 3D), axis with current value of objective function for this step. In our opinion, using such visualization allows students to better understand the steps of the simplex algorithm and its geometric interpretation. In Example 2 we solve the NLP problem using KKT method. We demonstrate dynamic visualization of graphic method of obtaining the optimal solution in this example. In general, computer support (e.g. by CAS) in solving tasks by KKT method seems very useful due to the need to consider sometimes a large number of subcases difficult to consider by hand calculations. The visualizations presented in this example, seem very useful to us in a better understanding of solving NLP problems graphically. This article also presents the result of the didactic experiment carried out on a group of 41 first-year students of the Production Engineering Faculty of Warsaw University of Life Sciences. In this experiment dynamic visualizations for two examples of network flows were presented to these students. This had a significant impact on the result of the test consisting in the construction of flow in the given network. The number of correct solutions increased more than 2.5 times compared to the number of correct solutions of the analogous task before presenting this visualizations. Over 75% of students said that these visualizations were helpful or very helpful in solving the second task (after seeing dynamic visualizations).

Network Flows: Theory, Algorithms, and Applications

Linear Programming and Network Flows

Nonlinear Programming. Theory and Algorithms

Network Flows

Linear and Nonlinear Optimization

Computer algebra systems as the mathematics teaching tool

Using computer algebra systems in mathematical classrooms

Mathematica Navigator: Graphics and Methods of Applied Mathematics

Familiarizing students with definition of lebesgue integral: examples of calculation directly from its definition using mathematica

Some remarks on Taylor's polynomials visualization using mathematica in context of function approximation

Teaching students nonlinear programming with computer algebra system

The Mathematica Book