Решение задачи коммивояжера. Решение транспортной задачи Антипатия index php elementary math

В задаче коммивояжера для формирования оптимального маршрута объезда n городов необходимо выбрать один лучший из (n-1)! вариантов по критерию времени, стоимости или длине маршрута. Эта задача связана с определением гамильтонова цикла минимальной длины. В таких случаях множество всех возможных решений следует представить в виде дерева - связного графа, не содержащего циклов и петель. Корень дерева объединяет все множество вариантов, а вершины дерева - это подмножества частично упорядоченных вариантов решений.

Назначение сервиса . С помощью сервиса можно проверить свое решение или получить новое решение задачи коммивояжёра двумя методами: методом ветвей и границ и венгерским методом .

Математическая модель задачи коммивояжера

Сформулированная задача - задача целочисленная. Пусть х ij =1 , если путешественник переезжает из i -ого города в j -ый и х ij =0 , если это не так.
Формально введем (n+1) город, расположенный там же, где и первый город, т.е. расстояния от (n+1) города до любого другого, отличного от первого, равны расстояниям от первого города. При этом, если из первого города можно лишь выйти, то в (n+1) город можно лишь придти.
Введем дополнительные целые переменные, равные номеру посещения этого города на пути. u 1 =0 , u n +1 =n . Для того, чтобы избежать замкнутых путей, выйти из первого города и вернуться в (n+1) введем дополнительные ограничения, связывающие переменные x ij и переменные u i (u i целые неотрицательные числа).

U i -u j +nx ij ≤ n-1, j=2..n+1, i=1..n, i≠j, при i=1 j≠n+1
0≤u i ≤n, x in+1 =x i1 , i=2..n

Методы решения задачи коммивояжера

метод ветвей и границ (алгоритм Литтла или исключения подциклов). Пример решения методом ветвей и границ ;
венгерский метод. Пример решения венгерским методом .

Алгоритм Литтла или исключения подциклов

Операция редукции по строкам: в каждой строке матрицы находят минимальный элемент d min и вычитают его из всех элементов соответствующей строки. Нижняя граница: H=∑d min .
Операция редукции по столбцам: в каждом столбце матрицы выбирают минимальный элемент d min , и вычитают его из всех элементов соответствующего столбца. Нижняя граница: H=H+∑d min .
Константа приведения H является нижней границей множества всех допустимых гамильтоновых контуров.
Поиск степеней нулей для приведенной по строкам и столбцам матрицы. Для этого временно нули в матице заменяэт на знак «∞» и находят сумму минимальных элементов строки и столбца, соответствующих этому нулю.
Выбирают дугу (i,j) , для которой степень нулевого элемента достигает максимального значения.
Разбивают множество всех гамильтоновых контуров на два подмножества: подмножество гамильтоновых контуров содержащих дугу (i,j) и не содержащих ее (i*,j*) . Для получения матрицы контуров, включающих дугу (i,j) , вычеркивают в матрице строку i и столбец j . Чтобы не допустить образования негамильтонова контура, заменяют симметричный элемент (j,i) на знак «∞». Исключение дуги достигается заменой элемента в матрице на ∞.
Проводят приведение матрицы гамильтоновых контуров с поиском констант приведения H(i,j) и H(i*,j*) .
Сравнивают нижние границы подмножества гамильтоновых контуров H(i,j) и H(i*,j*) . Если H(i,j)
Если в результате ветвлений получается матрица (2x2) , то определяют полученный ветвлением гамильтонов контур и его длину.
Сравнивают длину гамильтонова контура с нижними границами оборванных ветвей. Если длина контура не превышает их нижних границ, то задача решена. В противном случае развивают ветви подмножеств с нижней границей, меньшей полученного контура, до тех пор, пока не получится маршрут с меньшей длиной.

Пример . Решить по алгоритму Литтла задачу коммивояжера с матрицей

	1	2	3	4
1	-	5	8	7
2	5	-	6	15
3	8	6	-	10
4	7	15	10	-

Решение . Возьмем в качестве произвольного маршрута: X 0 = (1,2);(2,3);(3,4);(4,5);(5,1). Тогда F(X 0) = 20 + 14 + 6 + 12 + 5 = 57
Для определения нижней границы множества воспользуемся операцией редукции или приведения матрицы по строкам, для чего необходимо в каждой строке матрицы D найти минимальный элемент: d i = min(j) d ij

i j	1	2	3	4	5	d i
1	M	20	18	12	8	8
2	5	M	14	7	11	5
3	12	18	M	6	11	6
4	11	17	11	M	12	11
5	5	5	5	5	M	5

Затем вычитаем d i из элементов рассматриваемой строки. В связи с этим во вновь полученной матрице в каждой строке будет как минимум один ноль.

i j	1	2	3	4	5
1	M	12	10	4	0
2	0	M	9	2	6
3	6	12	M	0	5
4	0	6	0	M	1
5	0	0	0	0	M

Такую же операцию редукции проводим по столбцам, для чего в каждом столбце находим минимальный элемент:
d j = min(i) d ij

i j	1	2	3	4	5
1	M	12	10	4	0
2	0	M	9	2	6
3	6	12	M	0	5
4	0	6	0	M	1
5	0	0	0	0	M
d j	0	0	0	0	0

После вычитания минимальных элементов получаем полностью редуцированную матрицу, где величины d i и d j называются константами приведения .

i j	1	2	3	4	5
1	M	12	10	4	0
2	0	M	9	2	6
3	6	12	M	0	5
4	0	6	0	M	1
5	0	0	0	0	M

Сумма констант приведения определяет нижнюю границу H: H = ∑d i + ∑d j = 8+5+6+11+5+0+0+0+0+0 = 35
Элементы матрицы d ij соответствуют расстоянию от пункта i до пункта j.
Поскольку в матрице n городов, то D является матрицей nxn с неотрицательными элементами d ij ≥ 0
Каждый допустимый маршрут представляет собой цикл, по которому коммивояжер посещает город только один раз и возвращается в исходный город.
Длина маршрута определяется выражением: F(M k) = ∑d ij
Причем каждая строка и столбец входят в маршрут только один раз с элементом d ij .
Шаг №1 .
Определяем ребро ветвления

i j	1	2	3	4	5	d i
1	M	12	10	4	0(5)	4
2	0(2)	M	9	2	6	2
3	6	12	M	0(5)	5	5
4	0(0)	6	0(0)	M	1	0
5	0(0)	0(6)	0(0)	0(0)	M	0
d j	0	6	0	0	1	0

d(1,5) = 4 + 1 = 5; d(2,1) = 2 + 0 = 2; d(3,4) = 5 + 0 = 5; d(4,1) = 0 + 0 = 0; d(4,3) = 0 + 0 = 0; d(5,1) = 0 + 0 = 0; d(5,2) = 0 + 6 = 6; d(5,3) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (0 + 6) = 6 для ребра (5,2), следовательно, множество разбивается на два подмножества (5,2) и (5*,2*).
Исключение ребра (5,2) проводим путем замены элемента d 52 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (5*,2*), в результате получим редуцированную матрицу.

i j	1	2	3	4	5	d i
1	M	12	10	4	0	0
2	0	M	9	2	6	0
3	6	12	M	0	5	0
4	0	6	0	M	1	0
5	0	M	0	0	M	0
d j	0	6	0	0	0	6

Нижняя граница гамильтоновых циклов этого подмножества: H(5*,2*) = 35 + 6 = 41
Включение ребра (5,2) проводится путем исключения всех элементов 5-ой строки и 2-го столбца, в которой элемент d 25 заменяем на М, для исключения образования негамильтонова цикла.

i j	1	3	4	5	d i
1	M	10	4	0	0
2	0	9	2	M	0
3	6	M	0	5	0
4	0	0	M	1	0
d j	0	0	0	0	0

Нижняя граница подмножества (5,2) равна: H(5,2) = 35 + 0 = 35 ≤ 41
Поскольку нижняя граница этого подмножества (5,2) меньше, чем подмножества (5*,2*), то ребро (5,2) включаем в маршрут с новой границей H = 35
Шаг №2 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j	1	3	4	5	d i
1	M	10	4	0(5)	4
2	0(2)	9	2	M	2
3	6	M	0(7)	5	5
4	0(0)	0(9)	M	1	0
d j	0	9	2	1	0

d(1,5) = 4 + 1 = 5; d(2,1) = 2 + 0 = 2; d(3,4) = 5 + 2 = 7; d(4,1) = 0 + 0 = 0; d(4,3) = 0 + 9 = 9;
Наибольшая сумма констант приведения равна (0 + 9) = 9 для ребра (4,3), следовательно, множество разбивается на два подмножества (4,3) и (4*,3*).
Исключение ребра (4,3) проводим путем замены элемента d 43 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,3*), в результате получим редуцированную матрицу.

i j	1	3	4	5	d i
1	M	10	4	0	0
2	0	9	2	M	0
3	6	M	0	5	0
4	0	M	M	1	0
d j	0	9	0	0	9

Нижняя граница гамильтоновых циклов этого подмножества: H(4*,3*) = 35 + 9 = 44
Включение ребра (4,3) проводится путем исключения всех элементов 4-ой строки и 3-го столбца, в которой элемент d 34 заменяем на М, для исключения образования негамильтонова цикла.

После операции приведения сокращенная матрица будет иметь вид:

i j	1	4	5	d i
1	M	4	0	0
2	0	2	M	0
3	6	M	5	5
d j	0	2	0	7

Сумма констант приведения сокращенной матрицы: ∑d i + ∑d j = 7
Нижняя граница подмножества (4,3) равна: H(4,3) = 35 + 7 = 42 ≤ 44
Поскольку 42 > 41, исключаем подмножество (5,2) для дальнейшего ветвления.
Возвращаемся к прежнему плану X 1 .
План X 1 .

i j	1	2	3	4	5
1	M	12	10	4	0
2	0	M	9	2	6
3	6	12	M	0	5
4	0	6	0	M	1
5	0	M	0	0	M

Операция редукции .

i j	1	2	3	4	5
1	M	6	10	4	0
2	0	M	9	2	6
3	6	6	M	0	5
4	0	0	0	M	1
5	0	M	0	0	M

Шаг №1 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j	1	2	3	4	5	d i
1	M	6	10	4	0(5)	4
2	0(2)	M	9	2	6	2
3	6	6	M	0(5)	5	5
4	0(0)	0(6)	0(0)	M	1	0
5	0(0)	M	0(0)	0(0)	M	0
d j	0	6	0	0	1	0

d(1,5) = 4 + 1 = 5; d(2,1) = 2 + 0 = 2; d(3,4) = 5 + 0 = 5; d(4,1) = 0 + 0 = 0; d(4,2) = 0 + 6 = 6; d(4,3) = 0 + 0 = 0; d(5,1) = 0 + 0 = 0; d(5,3) = 0 + 0 = 0; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (0 + 6) = 6 для ребра (4,2), следовательно, множество разбивается на два подмножества (4,2) и (4*,2*).
Исключение ребра (4,2) проводим путем замены элемента d 42 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (4*,2*), в результате получим редуцированную матрицу.

i j	1	2	3	4	5	d i
1	M	6	10	4	0	0
2	0	M	9	2	6	0
3	6	6	M	0	5	0
4	0	M	0	M	1	0
5	0	M	0	0	M	0
d j	0	6	0	0	0	6

Нижняя граница гамильтоновых циклов этого подмножества: H(4*,2*) = 41 + 6 = 47
Включение ребра (4,2) проводится путем исключения всех элементов 4-ой строки и 2-го столбца, в которой элемент d 24 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:

i j	1	3	4	5	d i
1	M	10	4	0	0
2	0	9	M	6	0
3	6	M	0	5	0
5	0	0	0	M	0
d j	0	0	0	0	0

Сумма констант приведения сокращенной матрицы: ∑d i + ∑d j = 0
Нижняя граница подмножества (4,2) равна: H(4,2) = 41 + 0 = 41 ≤ 47
Поскольку нижняя граница этого подмножества (4,2) меньше, чем подмножества (4*,2*), то ребро (4,2) включаем в маршрут с новой границей H = 41
Шаг №2 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j	1	3	4	5	d i
1	M	10	4	0(9)	4
2	0(6)	9	M	6	6
3	6	M	0(5)	5	5
5	0(0)	0(9)	0(0)	M	0
d j	0	9	0	5	0

d(1,5) = 4 + 5 = 9; d(2,1) = 6 + 0 = 6; d(3,4) = 5 + 0 = 5; d(5,1) = 0 + 0 = 0; d(5,3) = 0 + 9 = 9; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (4 + 5) = 9 для ребра (1,5), следовательно, множество разбивается на два подмножества (1,5) и (1*,5*).
Исключение ребра (1,5) проводим путем замены элемента d 15 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (1*,5*), в результате получим редуцированную матрицу.

i j	1	3	4	5	d i
1	M	10	4	M	4
2	0	9	M	6	0
3	6	M	0	5	0
5	0	0	0	M	0
d j	0	0	0	5	9

Нижняя граница гамильтоновых циклов этого подмножества: H(1*,5*) = 41 + 9 = 50
Включение ребра (1,5) проводится путем исключения всех элементов 1-ой строки и 5-го столбца, в которой элемент d 51 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:

i j	1	3	4	d i
2	0	9	M	0
3	6	M	0	0
5	M	0	0	0
d j	0	0	0	0

Сумма констант приведения сокращенной матрицы: ∑d i + ∑d j = 0
Нижняя граница подмножества (1,5) равна: H(1,5) = 41 + 0 = 41 ≤ 50
Поскольку нижняя граница этого подмножества (1,5) меньше, чем подмножества (1*,5*), то ребро (1,5) включаем в маршрут с новой границей H = 41
Шаг №3 .
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
С этой целью для всех клеток матрицы с нулевыми элементами заменяем поочередно нули на М(бесконечность) и определяем для них сумму образовавшихся констант приведения, они приведены в скобках.

i j	1	3	4	d i
2	0(15)	9	M	9
3	6	M	0(6)	6
5	M	0(9)	0(0)	0
d j	6	9	0	0

d(2,1) = 9 + 6 = 15; d(3,4) = 6 + 0 = 6; d(5,3) = 0 + 9 = 9; d(5,4) = 0 + 0 = 0;
Наибольшая сумма констант приведения равна (9 + 6) = 15 для ребра (2,1), следовательно, множество разбивается на два подмножества (2,1) и (2*,1*).
Исключение ребра (2,1) проводим путем замены элемента d 21 = 0 на M, после чего осуществляем очередное приведение матрицы расстояний для образовавшегося подмножества (2*,1*), в результате получим редуцированную матрицу.

i j	1	3	4	d i
2	M	9	M	9
3	6	M	0	0
5	M	0	0	0
d j	6	0	0	15

Нижняя граница гамильтоновых циклов этого подмножества: H(2*,1*) = 41 + 15 = 56
Включение ребра (2,1) проводится путем исключения всех элементов 2-ой строки и 1-го столбца, в которой элемент d 12 заменяем на М, для исключения образования негамильтонова цикла.
В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
После операции приведения сокращенная матрица будет иметь вид:

i j	3	4	d i
3	M	0	0
5	0	0	0
d j	0	0	0

Сумма констант приведения сокращенной матрицы:
∑d i + ∑d j = 0
Нижняя граница подмножества (2,1) равна: H(2,1) = 41 + 0 = 41 ≤ 56
Поскольку нижняя граница этого подмножества (2,1) меньше, чем подмножества (2*,1*), то ребро (2,1) включаем в маршрут с новой границей H = 41.
В соответствии с этой матрицей включаем в гамильтонов маршрут ребра (3,4) и (5,3).
В результате по дереву ветвлений гамильтонов цикл образуют ребра:
(4,2), (2,1), (1,5), (5,3), (3,4). Длина маршрута равна F(Mk) = 41

Дерево решений.


							1


	(5,2), H=41											(5,2)


(4,2), H=47			(4,2)								(4,3), H=44		(4,3)


	(1,5), H=50				(1,5)


		(2,1), H=56							(2,1)


						(3,4)				(3,4), H=41


				(5,3)				(5,3), H=41

Lesia М. Ohnivchuk

Abstract

The article considers way to extend the functionality of LMS Moodle when creating e-learning courses for the mathematical sciences, in particular e-learning courses "Elementary Mathematics" by using flash technology and Java-applets. There are examples of the use of flash-applications and Java-applets in the course "Elementary Mathematics".

Keywords

LMS Moodle; e-learning courses; technology flash; Java-applet, GeoGebra

References

Brandão, L. O., "iGeom: a free software for dynamic geometry into the web", International Conference on Sciences and Mathematics Education, Rio de Janeiro, Brazil, 2002.

Brandão, L. O. and Eisnmann, A. L. K. “Work in Progress: iComb Project - a mathematical widget for teaching and learning combinatorics through exercises” Proceedings of the 39th ASEE/IEEE Frontiers in Education Conference, 2009, T4G_1–2

Kamiya, R. H and Brandão, L. O. “iVProg – a system for introductory programming through a Visual Model on the Internet. Proceedings of the XX Simpósio Brasileiro de Informática na Educação, 2009 (in Portuguese).

Moodle.org: open-source community-based tools for learning [Електронний ресурс]. – Режим доступу: http://www.moodle.org.

MoodleDocs [Електронний ресурс]. – Режим доступум: http://docs.moodle.org.

Інтерактивні технології навчання: теорія, практика, досвід: методичний посібник авт.-уклад.: О. Пометун, Л. Пироженко. – К. : АПН; 2004. – 136 с.

Dmitry Pupinin. Question Type: Flash [Электронный ресурс]. – Режим доступа: https://moodle.org/mod/data/view.php?d=13&rid=2493&filter=1 – 26.02.14.

Андреев А. В., Герасименко П. С.. Использование Flash и SCORM для создания заданий итогового контроля [Электронный ресурс]. – Режим доступа: http://cdp.tti.sfedu.ru/index.php?option=com_content&task=view&id=1071&Itemid=363 –26.02.14.

GeoGebra. Материалы [Електронний ресурс]. – Режим доступу: http://tube.geogebra.org.

Хохенватор М. Введение в GeoGebra / М. Хохенватор / пер. Т. С. Рябова. – 2012. – 153 с.

REFERENCES (TRANSLATED AND TRANSLITERATED)

Brandão, L. O. "iGeom: a free software for dynamic geometry into the web", International Conference on Sciences and Mathematics Education, Rio de Janeiro, Brazil, 2002 (in English).

Moodle.org: open-source community-based tools for learning . – Available from: http://www.moodle.org (in English).

MoodleDocs . – Available from: http://docs.moodle.org (in English).

Pometun O. I., Pirozhenko L. V. Modern lesson , Kiev, ASK Publ., 2004, 192 p. (in Ukrainian).

Dmitry Pupinin. Question Type: Flash . – Available from: https://moodle.org/mod/data/view.php?d=13&rid=2493&filter=1 – 26.02.14 (in English).

Andreev А., Gerasimenko Р. Using Flash and SCORM to create of tasks final control . – Available from: http://cdp.tti.sfedu.ru/index.php?option=com_content&task=view&id=1071&Itemid=363 – 26.02.14 (in Russian).

GeoGebra Wiki . – Available from: http://www.geogebra.org (in English).

Hohenwarter M. Introduction in GeoGebra / M. Hohenwarter. – 2012. – 153 s. (in English).

DOI: https://doi.org/10.33407/itlt.v48i4.1249

Инструкция . Для получения решения транспортной задачи в онлайн режиме выберите размерность матрицы тарифов (количество поставщиков и количество магазинов).

Вместе с этим калькулятором также используют следующие:
Графический метод решения ЗЛП
Симплексный метод решения ЗЛП
Решение матричной игры
С помощью сервиса в онлайн режиме можно определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.

Экстремум функции двух переменных
Задачи динамического программирования

Первым этапом решения транспортной задачи является определение ее типа (открытая или закрытая, или иначе сбалансированная или не сбалансированная). Приближенные методы (методы нахождения опорного плана ) позволяют на втором этапе решения за небольшое число шагов получить допустимое, но не всегда оптимальное, решение задачи. К данной группе методов относятся методы:

вычеркивания (метод двойного предпочтения);
северо-западного угла;
минимального элемента;
аппроксимации Фогеля.

Опорное решение транспортной задачи

Опорным решением транспортной задачи называется любое допустимое решение, для которого векторы условий, соответствующие положительным координатам, линейно независимы. Для проверки линейной независимости векторов условий, соответствующих координатам допустимого решения, используют циклы.
Циклом называется такая последовательность клеток таблицы транспортной задачи, в которой две и только соседние клетки расположены в одной строке или столбце, причем первая и последняя также находятся в одной строке или столбце. Система векторов условий транспортной задачи линейно независима тогда и только тогда, когда из соответствующих им клеток таблицы нельзя образовать ни одного цикла. Следовательно, допустимое решение транспортной задачи, i=1,2,...,m; j=1,2,...,n является опорным только в том случае, когда из занятых им клеток таблицы нельзя образовать ни одного цикла.

Приближенные методы решения транспортной задачи.
Метод вычеркивания (метод двойного предпочтения) . Если в строке или столбце таблицы одна занятая клетка, то она не может входить в какой-либо цикл, так как цикл имеет две и только две клетки в каждом столбце. Следовательно, можно вычеркнуть все строки таблицы, содержащие по одной занятой клетке, затем вычеркнуть все столбцы, содержащие по одной занятой клетке, далее вернуться к строкам и продолжить вычеркивание строк и столбцов. Если в результате вычеркивания все строки и столбцы будут вычеркнуты, значит, из занятых клеток таблицы нельзя выделить часть, образующую цикл, и система соответствующих векторов условий является линейно независимой, а решение опорным. Если же после вычеркиваний останется часть клеток, то эти клетки образуют цикл, система соответствующих векторов условий линейно зависима, а решение не является опорным.
Метод «северо-западного угла» состоит в последовательном переборе строк и столбцов транспортной таблицы, начиная с левого столбца и верхней строки, и выписывании максимально возможных отгрузок в соответствующие ячейки таблицы так, чтобы не были превышены заявленные в задаче возможности поставщика или потребности потребителя. На цены доставки в этом методе не обращают внимание, поскольку предполагается дальнейшая оптимизация отгрузок.
Метод «минимального элемента» . Отличаясь простотой данный метод все же эффективнее чем, к примеру, метод Северо-западного угла. Кроме того, метод минимального элемента понятен и логичен. Его суть в том, что в транспортной таблице сначала заполняются ячейки с наименьшими тарифами, а потом уже ячейки с большими тарифами. То есть мы выбираем перевозки с минимальной стоимостью доставки груза. Это очевидный и логичный ход. Правда он не всегда приводит к оптимальному плану.
Метод «аппроксимации Фогеля» . При методе аппроксимации Фогеля на каждой итерации по всем столбцам и по всем строкам находят разность между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи. Среди указанных разностей выбирают минимальную. В строке (или в столбце), которой данная разность соответствует, определяют минимальный тариф. Клетку, в которой он записан, заполняют на данной итерации.

Пример №1 . Матрица тарифов (здесь количество поставщиков равно 4 , количество магазинов равно 6):

	1	2	3	4	5	6	Запасы
1	3	20	8	13	4	100	80
2	4	4	18	14	3	0	60
3	10	4	18	8	6	0	30
4	7	19	17	10	1	100	60
Потребности	10	30	40	50	70	30

Решение . Предварительный этап решения транспортной задачи сводится к определению ее типа, открытой она является или закрытой. Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 80 + 60 + 30 + 60 = 230
∑b = 10 + 30 + 40 + 50 + 70 + 30 = 230
Условие баланса соблюдается. Запасы равны потребностям. Итак, модель транспортной задачи является закрытой. Если бы модель получилась открытой, то потребовалось бы вводить дополнительных поставщиков или потребителей.
На втором этапе осуществляется поиск опорного плана методами, приведенными выше (наиболее распространенным является метод наименьшей стоимости).
Для демонстрации алгоритма приведем лишь несколько итераций.
Итерация №1. Минимальный элемент матрицы равен нулю. Для этого элемента запасы равны 60 , потребности 30 . Выбираем из них минимальное число 30 и вычитаем его (см. в таблице). При этом из таблицы вычеркиваем шестой столбец (потребности у него равны 0).

3	20	8	13	4	x	80
4	4	18	14	3	0	60 - 30 = 30
10	4	18	8	6	x	30
7	19	17	0	1	x	60
10	30	40	50	70	30 - 30 = 0	0

Итерация №2. Снова ищем минимум (0). Из пары (60;50) выбираем минимальное число 50. Вычеркиваем пятый столбец.

3	20	8	x	4	x	80
4	4	18	x	3	0	30
10	4	18	x	6	x	30
7	19	17	0	1	x	60 - 50 = 10
10	30	40	50 - 50 = 0	70	0	0

Итерация №3. Процесс продолжаем до тех пор, пока не выберем все потребности и запасы.
Итерация №N. Искомый элемент равен 8. Для этого элемента запасы равны потребностям (40).

3	x	8	x	4	x	40 - 40 = 0
x	x	x	x	3	0	0
x	4	x	x	x	x	0
x	x	x	0	1	x	0
0	0	40 - 40 = 0	0	0	0	0

	1	2	3	4	5	6	Запасы
1	3	20	8	13	4	100	80
2	4	4	18	14	3	0	60
3	10	4	18	8	6	0	30
4	7	19	17	0	1	100	60
Потребности	10	30	40	50	70	30

Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n - 1 = 9. Следовательно, опорный план является вырожденным. Строим новый план. Иногда приходится строить несколько опорных планов, прежде чем найти не вырожденный.

	1	2	3	4	5	6	Запасы
1	3	20	8	13	4	100	80
2	4	4	18	14	3	0	60
3	10	4	18	8	6	0	30
4	7	19	17	0	1	100	60
Потребности	10	30	40	50	70	30

В результате получен первый опорный план, который является допустимым, так как число занятых клеток таблицы равно 9 и соответствует формуле m + n - 1 = 6 + 4 - 1 = 9, т.е. опорный план является невырожденным .
Третий этап заключается в улучшении найденного опорного плана. Здесь используют метод потенциалов или распределительный метод . На этом этапе правильность решения можно контролировать через функцию стоимости F(x) . Если она уменьшается (при условии минимизации затрат), то ход решения верный.

Пример №2 . Используя метод минимального тарифа, представить первоначальный план для решения транспортной задачи. Проверить на оптимальность, используя метод потенциалов.

	30	50	70	10	30	10
40	2	4	6	1	1	2
80	3	4	5	9	9	6
60	4	3	2	7	8	7
20	5	1	3	5	7	9

Пример №3 . Четыре кондитерские фабрики могут производить три вида кондитерских изделий. Затраты на производство одного центнера (ц) кондитерских изделий каждой фабрикой, производственные мощности фабрик (ц в месяц) и суточные потребности в кондитерских изделиях (ц в месяц) указаны в таблице. Составить план производства кондитерских изделий, минимизирующий суммарные затраты на производство.

Примечание . Здесь предварительно можно транспонировать таблицу затрат, поскольку для классической постановки транспортной задачи сначала следуют мощности (производство), а потом потребители.

Пример №4 . На строительство объектов кирпич поступает с трех (I, II, III) заводов. Заводы имеют на складах соответственно 50, 100 и 50 тыс. шт. кирпича. Объекты требуют соответственно 50, 70, 40 и 40 тыс. шт. кирпича. Тарифы (ден. ед./тыс.шт.) приведены в таблице. Составьте план перевозок, минимизирующий суммарные транспортные расходы.

будет закрытой если:
А) a=40, b=45
Б) a=45, b=40
В) a=11, b=12
Условие закрытой транспортной задачи : ∑a = ∑b
Находим, ∑a = 35+20+b = 55+b; ∑b = 60+a
Получаем: 55+b = 60+a
Равенство будет соблюдаться только при a=40, b=45 You are here: Home → Articles → Calculator usage

Using calculator in elementary math teaching

This article discusses whether or not a calculator should be used in teaching math in elementary grades and how to use it wisely.

The "battle" over calculator use

Some people say a calculator enables children to concentrate on understanding and the mathematical concepts instead of spending time on tedious calculations. They say a calculator helps develop number sense, and makes students more confident about their math abilities.

Others are against using calculator in lower level math teaching, saying that it makes children not to learn their basic facts, prevents students from discovering and understanding underlying mathematical concepts and instead encourages them to randomly try different operations without understanding what they"re doing.

They say calculators keep students from benefiting from one of the most important reasons for learning math: to train and discipline the mind and to promote logical reasoning.

There IS a balance

In my opinion, a calculator can be used in the teaching in a good way or a bad way — it all depends on the teacher"s approach. The calculator in itself is not bad nor good — it is just a tool. It is used a lot in today"s society, so students should learn to use it by the time they finish school.

At the same time, children SHOULD learn their basic facts, be able to do mental calculations, and master long division and other basic paper-pencil algorithms. Mathematics is a field of study that builds on previously established facts. A child that does not know basic multiplication (and division) facts will have a hard time learning factoring, primes, fraction simplification and other fraction operations, the distributive property, etc. etc. Basic algorithms of arithmetic are a needful basis for understanding the corresponding operations with polynomials in algebra. Mastering long division precedes understanding how fractions correspond to the repeating (non-terminating) decimals, which then paves way to understanding irrational numbers and real numbers . It all connects together!

For this reason, it is advisable to restrict the calculator use in the lower grades, until children know their basic facts and can add, subtract, multiply, and divide even large numbers with pencil & paper. THIS, in my opinion, builds number sense , as do mental calculations.

This does not mean that you couldn"t use calculator occasionally in the elementary grades for special projects, when teaching specific concepts, or for some fun. It could be used for example in science or geography projects, for exploring certain new concepts, for some number games, or checking homework. See below for some ideas.

The discussion here does not apply to graphical calculators in high school. I am strongly in favor of using graphical calculators or a graphing software when studying graphing and calculus. Even there though, one certainly needs to learn the basic idea of how the graphing is done on paper.

Things to keep in mind when using a calculator

When calculator is used more freely, one should pay attention to following points:

The calculator is a tool to do calculations. So are the human mind and paper & pencil. Children should be taught when to use a calculator and when mental computing (or even paper & pencil) are more effective or appropriate. Choosing the right "tool" is part of an effective problem-solving process.
It is very important that students learn how to estimate the result before doing the calculation. It is SO easy to make mistakes when punching the numbers into a calculator. A student must not learn to rely on the calculator without checking that the answer is reasonable.
A calculator should not be used to try out randomly all possible operations and to check which one produces the right answer. It is crucial that students learn and understand the different mathematical operations so they know WHEN to use which one — and this is true whether the actual calculation is done mentally, on paper, or with a calculator.

Ideas for calculator use in elementary math

If you use these ideas, make sure the children don"t get the idea that a calculator takes away the need to learn mental math. It can serve as a tool to let children explore and observe, but afterwards the teacher should explain concepts, justify the rules of math, and put it all together.

Kindergartners and first graders can explore numbers by adding 1 repeatedly (which can be done with first pushing 1 + 1 = and then pressing the = button repeatedly) or subtracting 1 repeatedly. Observe their faces when they hit negative numbers! Or, let them investigate what happens to a number when you add zero to it.
Calculator pattern puzzles : This is an extension of the idea above, where first to third grade children add or subtract the same number repeatedly using a calculator. Children will observe patterns that emerge when you add, say, 2, 5, 10, or 100 repeatedly. For example, they can start at 17 and add 10 repeatedly or start at 149 and subtract 10 repeatedly. Another idea is to let children make their own "pattern puzzles", which are number sequences with a pattern where some numbers are omitted, for example 7, 14, __, __, 35, __, 49. The activity can connect with the idea of multiplication very easily.
Place value activity with a calculator : Students build numbers with the calculator, for example:
Make a three-digit number with a 6 in the tens place; OR Make a four-digit number larger than 3,500 with a four in the ones place; OR Make a four-digit number with a 3 in the tens and a 9 in the hundreds place; etc.
Afterwards the teacher lists several numbers on the board and discusses what the numbers that students made have in common, such as: all of the numbers are sixty-something.
Write the number one million on the board. Ask students to pick a number that they will add repeatedly with the calculator to reach one million within reasonable class time. If they pick small numbers, such as 68 or 125, they won"t reach it! This can teach children how vast the number one million is.
When introducing pi, have students measure the circumference and the diameter of several circular objects, and calculate their ratio with a calculator (which saves time and can help keep the focus on the concept).

The Use of Calculators Gets at the Heart of Good Teaching — an article by Susan Ray; no longer online

Comments

I teach in a very small school and I currently teach Algebra 1, 8th grade science, and then Physics to the seniors and I have a small group that has completed high school calculus and we"re doing some Linear Algebra. I, myself, have a Masters in Physics.
Before I read some of these posts, I felt that I was pretty rabid anti-calculator, but now I think I"m more middle of the road.
The comments about doing square roots on paper is a good one. No, we don"t need to know how to do that anymore with good precision. However, I would really like all of my students to be able to tell you what two numbers it"s between. Example: 8
Just last year I discovered how to input data in a TI-83 and have it spit out the mean and the standard deviation. In the context of a Physics class, I don"t want to spend a lot of time on things that they should learn in a Statistics class. But if the calculator does it easily, then I can gently introduce the concept and hope that the initial exposure has prepped them for what they need to learn in Stats.
In Algebra 1, however, I don"t allow students to use calculators at all. And, it my school, I find that most kids come to my course without a calculator or an inclination to use it. I feel that the basic rundown on the math in Algebra 1 should be: 80% of the numbers should utilize the basic information on a 12x12 multiplication table that kids should have memorized. 15% of the numbers should push beyond those limits. (example: what"s 384/8?). And the last 5% should be things that they need a calculator for.
In my opinion, you learn things about numbers when you have to do them in your head. If you want to do the prime factors of 357, you can start with the idea that it is less than 400, so you only have to check up to 20. You also know that it"s odd, so you don"t have to check 2 or any of the evens. Then you can realize that you don"t have to check any of the non-prime numbers between 1 and 20. So, you only have to check 3, 5, 7, 11, 13, 17.
This helps students start to develop some fundamental concepts related to sets. There are groups of numbers that share common properties, like evens and odds and primes. This is a deep concept that you might not get if you don"t have to simplify a process for yourself.
But, also, simplifying a process for yourself is really important. Suppose you are head mechanic on a Sprint Cup NASCAR car. They break all of the time. What do you need to do to fix them? What is extraneous to the problem? What is the smallest number of things that you need to test/fix, and in what order should you try them? That"s a long extension from developing algorithmic thought in high school math class. But I would argue that it"s harder to get there if you have been fed answers by a machine your entire life.
I know this is running long. Two more points... I would never use a graphing calculator to actually graph. I have $100 software on my laptop that blows any hand-held graphing calculator out of the water.
Finally, the comment on store clerks and calculators caught my attention. The world certainly needs people to run the cash registers in department stores. But somehow I feel that the goal of getting a good education is so that you can later choose a career that you are passionate about. Cashiers who are passionate about retail are few and far between. I would hope that my students would have an wider set of choices when they finish school.
David Iverson

I think both should be used. I agree we need to learn the basics in elementary school, addition, subtraction, etc.) However, When you go to Macy"s, Olive Garden or Mc Donald"s, the cashier doesn"t use paper and pencil. Computers (calculators) are used. We live in a computer age. We are no longer in the Industrial Revolution, so let"s come into the 21st century.

Hi I"m Kelly. I"m a freshmen in college at St. Charles community college in Missouri. Your site is wonderful. I was looking it over for my younger sister. Something I would really like to tell everyone and anyone who plans on going to college is to stop using a calculator immediately. Only use it for graphing logs and necessary things like that. I finished high school in a calculus class using a calculator for even the simplest multiplication and division problems, and when I got to college I had to start all over in BEGINNING ALGEBRA because I didn"t know how to multiply and divide without a calculator. So please do everyone a favor and ask them or tell them to stop using a calculator. They will thank me for it later. Kelly

Hello my name is Rafeek and I am a freshman at Hobart and William Smith colleges in Geneva, NY. I am doing a paper on technology and its effects, so I decided to pick the calculator. I came across this site in my research. I want to stress what Kelly said. The same thing happened to me, I was great in high school math, practically aced all math exams, then I came here for orientation and they told me I have to take a math placement test W/OUT a calc. I didn"t realize I couldn"t do a lot of the simple problems because I always plugged it into my calc and got the answer. This is becoming something serious, I already took away my younger brother and sisters calc. and told them until they are in college they will not be using a calc (at least not in front of me). Now I am taking pre-calc. and my goal it to not use a calc. DO NOT DEPEND ON YOUR CALCULATOR!!!

When in University taking math courses for my BMath we weren"t allowed calculators for many of the exams (to prevent people smuggling in pocket computing devices). For anyone doing higher level math I would say that being able to do sums on paper is essential.
Emily Bell

I"ve never been good at math and so when i got a hold of my calculator and how encouraging it is in highschool i fell in love with it. that is until i took my colege placement test. I did horrible. I couldn"t even remember how to do a simple division problem mentally. The problem with schools today is that they worry and encourage too much about calculators. Students should have a good sturdy base of mental math before they learn to use the calculator and if u ask me K-3 grade isn"t enough. it should not be permitted until college.

I am a recent college graduate. My major was Electrical Engineering. As my course of study involved a great deal of mathematics, I feel obligated to speak on this important issue. In my opinion, calculators should never be used for any mathematics class, even at the college level. Using a calculator for any subject will cause the user to become mentally lazy and incapable of basic mathematics skills. You should never use a calculator when learning how to multiply, do long division, or even graph a function.
"Some people say calculator enables children to concentrate on understanding and studying mathematical concepts instead of spending time on tedious calculations. They say calculator helps develop number sense, and makes students more confident about their math abilities."
The above statement is the total hogwash. The only way to develop number sense and understand mathematical concepts is to pour over hours of tedious calculations. The only way to develop confidence in one"s math abilities is to use a pencil and paper whenever you are confronted by a math problem. If a mathematics teacher agrees with the above statement, he or she should be fired immediately. The NCTM should be publicly disgraced for going along with such ruinous ideals.
The only time calculators should be used in school is in the laboratory class when you are doing calculations on numbers with more than 4 significant digits. Otherwise, the student should rely on a paper, a pencil, and his or her brain.

The calculator has no place; NO PLACE; in an elementary school classroom. Period. I am a high school math teacher and the majority of my students have absolutely zero number sense. They"re using calculators to do single-digit multiplication problems they should have rightly memorized in the third grade. They"re helpless without them. I place 100% of the blame on calculator use in the early grades.

My children are 4 and 2. My daughter is going into kindergarten next year, and I"m going to instruct her teachers each year, and periodically throughout the year, she is FORBIDDEN to use a calculator for ANY of her work until she is in high school. There is NOTHING in the elementary or middle school curriculum that requires the use of a calculator.

AS to this statement "National Council of Teachers of Mathematics (1989) has recommended that long division and "practicing tedious pencil-and-paper computations" receive decreased attention in schools, and that calculators be available to all students at all times." My understanding is that this was a reaction to a survey of the time spent on math topics in the classroom and the nearly a third of fourth and fifth grade was spent learning to do division with decimal and double digit divisors (ie 340/.15 or 500/15) Yes teachers were spending more than two months of each of these! This just did not reflect the situation of math in the current world.
Personally, I have seen many great uses for calculators. They allow for error free repetition so that I could discover patterns. Many of the conversions and quick tricks I can do were because I only had a basic calculator all the way through precalculus. BTW, NCMT has also updated its standards to include fluency for math facts in second and fourth grades. As a math tutor I was hearing from parents all the time that children were not spending any time in school memorizing the basic fact.

I would probably would have liked it in the long run if I wasn"t allowed to use a calculator until at least high school (Geometry for me). You know those Nintendo DS Brainage games? Well they made me realize how awful I am with simple math. I can do it, just takes me a lot longer. Also, I can hardly ever do long division. I was taught math on a calculator since grade school.

As a junior high and high school teacher of Math, Pre-Algebra and Algebra I, I find myself fighting this battle yearly. While yes, calculators offer a quick way of finding answers, I don"t know of any problem in any of the three textbooks that I currently use that requires the student to solve long division problems to the upteenth place behind the decimal (which is a common argument).
However I do expect my students to be able to do basic math functions without the use of a calculator. As they get into Algebra, they spend too much time trying to figure out how to do things on the calculator that aren"t possible with the calculators they have. I also expect them to show their work on tests and quizzes (so does the new state tests for partial points) so that I KNOW that they know the process. "I used a calculator" does not demonstrate to me that they know process and rules or the "why" it works. Often it is the "why" that leads to the "look what I found out" and the "ah-ha"s" of mathetmatics.
I frequently remind students that calculators were invented long after mathematic rules began; therefore, all mathematics can be done without the use of a calculator. Great minds, don"t become great by taking the easy way out.
In regards to retail workers, while many customers standing in line would get impatient with the salesperson figuring everything by hand, as a teacher when I go to a food establishment, and that unlucky student of mine is the waiter/waitress/etc. I do expect them to count change back to me. I am mindful of when I do these "checks" and most managers (you know those who can do math without a calculator) are usually appreciative that their employees know how to count change back.

I had to laugh just a bit at the comment regarding "cashiers at Macy"s, Olive Garden, McDonalds...use calculators, computers." True, but that is no argument for their use. Have you ever been at one of these stores when the "computers are down?" Many cashiers cannot figure totals, make change, etc. without a computer to tell them what to do. Strong, basic math skills are very important and IMHO calculator use should be very limited. I sometimes wonder how some of our young people would fare in a true disaster/emergency when there may not be power, cell phones, computers, internet capability, etc. As a homeschooling parent one of my goals is for my child to have good basic skills firmly in place so they can function well in any subject without electronic help.

I have a boy going in third grade, and I bought him an extremely simple calculator (just +,-,*,/). He"s pretty good at problem solving, he knows his multiplication tables, can do additions and subtractions with 12 digits on paper, is learning on how to do multiplications on paper etc... and I was actually looking for some meaningful problems to solve with a calculator when I found this ideological debate.
Now, I fully agree that a calculator should not be a substitute for learning to do mental operations, and for learning how to do it on paper. You should be able to do these things on your self, even if it is clumsy.
But the point is, society advances. Where it was useful to do correctly and quickly sums of 20 numbers on a small note, and people even paid you for that skill 40 years ago, it isn"t the case anymore. Most of us don"t learn how to kill a rabbit with bow and arrow - while this was an essential skill for our ancestors living in caves.
When I look at the comments here, it seems that the only problems people faced when not being able to calculate without a calculator was in an artificial setting where this was an expressly tested competence. Rabbit hunting with arrow and bow would also pose a problem if this was not taught, and explicitly tested for one or other exam. I think in "real life" it is now important to be handy with a calculator - although one should of course be able to do without, but maybe not *drilled* at doing it efficiently, correctly and fast without.
BTW, who knows still how to take square roots on paper? Isn"t this an important skill? And who knows how to use efficiently a slide rule? Or a logarithm table to do multiplications? All these were techniques that were once very useful, and were important to be mastered quickly and efficiently. Now, they belong more to folklore. I don"t say that knowing how to do an addition on paper is folklore, one should know how to do it, but I wonder what"s the reason to be able to do it fast and efficiently (and hence spend hours training for it). Can"t one use that time now to do more useful things?
I would say, what"s still a practical skill is *mental* calculation, precise mental calculation, and approximate calculation to get an idea of order of magnitude. Whether doing multiplications of two numbers with 6 or 7 digits is still a very useful skill to train onto, I have my doubts - although, again, one should be able to know how it is done.
Things that get interesting with calculators, are constructions like Pascal"s triangle, or Fibonacci"s series, or factorials, combinations and things like that, and which are too tedious to do by hand.
Patrick Van Esch

Question: What are the main reasons for not using calculators in forms one to three of secondary schools?
I"m not quite sure what forms one to three are, but I guess you are talking about high school.
I personally would not deny calculator use of high schoolers. Children need to learn to use calculator, and to use it wisely - which means they should learn WHEN it"s good to use it and when not. Maybe one would deny calculator use in high school if a student was constantly misusing it, in other words using it for 6 x 7 etc., in which case such a student might need to review lower grades math.

I am a current sixth grader, I know most kids my age prefer using a calculator not for checking there work, but doing a large portion of they"re math with calculators. Calculator should be used only for checking work,recently my math teach has practically been forcing us to use TI30 xa calculators,as you know,the school provides a calculator that can add,subtract,multiply,and divide, and that seems to be enough. Lately I have been catching myself relying on calculators to do all my work, but today during my math class I decided no more calculator,one problem I had to solve was 3.8892 divided by 3 and I couldn"t remember how to do it. And the other day my mom gave me a simple math problem while getting gas and it took me 5 minutes to do this basic addition problem. My parents didn"t use calculators when they were in school and if they didn"t need them then we don"t either. But once all of our current middle schoolers are full grown adults, our school system will see that the adults will be way behind in math while relying on computers, and calculators to do all there deeds. I am officially Anti calculator!

I was lucky enough to learn basic math facts (multiplication, division, fractions, estimation, etc) before getting a calculator in 8th grade, but I grew really dependent on my TI 83 graphing utility for my high school algebra/precalc classes. I would graph the function to find the zeros instead of using the quadratic formula and stuff like that.
My freshman calculus class didn"t allow calculators, and I failed it. This was after doing quite well in honors high school precalculus. I went into an easier life/social science series (still had to struggle for B"s/C"s when I"d had easy A"s in high school) and eventually repeated the harder calculus class much more prepared. My life/social science series classes allowed 4-function but not graphing utilities. Also, in college I had to show my work to get any credit, even if the answer was right. I think one problem is that I got too hung up on finding the answers rather than learning the process.
My sister on the other hand has had a calculator since 3rd grade, and she literally can"t multiply 6*7 without a calculator or do a word problem, though she does get B"s in high school math.

As a Senior majoring in Early Childhood/Elementary Education, I understand the importance of having the knowledge on how to use a calculator, because yes, we live in an age where technology is widely used. However, like many of you, when I first came to college and had to take exams without use of the calculator, I was in big trouble! I still did very well, but it took me a long time to relearn all of the basic functions of math. From my own personal experiences in the field and through my own courses, I recommend a consistent balance between the two methods!!

I teach mathematics in a college where a calculator is forbidden. Unfortunately many students have been ruined by using a calculator. They have trouble doing even the simplest algebra. This has caused an increase of remedial math in colleges everywhere by up to 95%. There is a book out called "The Deliberate Dumbing Down Of America" written by a former whistle blower from the Department O Education (also known as the DOE which should stand for Dopes Of Education)

Math Lessons menu

Grade 1 Using a 100-bead abacus in elementary math Teaching tens and ones Practicing with two-digit numbers Counting in groups of ten Skip-counting practice (0-100) Comparing 2-digit numbers Cents and dimes Grade 2 Three-digit numbers Comparing 3-digit numbers Grade 3 Place value with thousands Comparing 4-digit numbers Rounding & estimating Rounding to the nearest 100 Grade 4 Place value - big numbers	Grade 1 Missing addend concept (0-10) Addition facts when the sum is 6 Addition & subtraction connection Grade 2 Fact families & basic addition/subtraction facts Sums that go over over the next ten Add/subtract whole tens (0-100) Add a 2-digit number and a single-digit number mentally Add 2-digit numbers mentally Regrouping in addition Regrouping twice in addition Regrouping or borrowing in subtraction Grade 3 Mental subtraction strategies Rounding & estimating	Grade 3 Multiplication concept as repeated addition Multiplication on number line Commutative Multiply by zero Word problems Order of operations Structured drill for multiplication tables Drilling tables of 2, 3, 5, or 10 Drilling tables of 4, 11, 9 Grade 4 Multiplying by whole tens & hundreds Distributive property Partial products - the easy way Partial products - video lesson Multiplication algorithm Multiplication Algorithm — Two-Digit Multiplier Scales problems - video lesson Estimation when multiplying

Catalog Information

Title

Elementary Linear Algebra.

(Credit Hours:Lecture Hours:Lab Hours)

Offered

Prerequisite

Minimal learning outcomes

Upon completion of this course, the successful student will be able to:

Use Gaussian elimination to do all of the following: solve a linear system with reduced row echelon form, solve a linear system with row echelon form and backward substitution, find the inverse of a given matrix, and find the determinant of a given matrix.
Demonstrate proficiency at matrix algebra. For matrix multiplication demonstrate understanding of the associative law, the reverse order law for inverses and transposes, and the failure of the commutative law and the cancellation law.
Use Cramer"s rule to solve a linear system.
Use cofactors to find the inverse of a given matrix and the determinant of a given matrix.
Determine whether a set with a given notion of addition and scalar multiplication is a vector space. Here, and in relevant numbers below, be familiar with both finite and infinite dimensional examples.
Determine whether a given subset of a vector space is a subspace.
Determine whether a given set of vectors is linearly independent, spans, or is a basis.
Determine the dimension of a given vector space or of a given subspace.
Find bases for the null space, row space, and column space of a given matrix, and determine its rank.
Demonstrate understanding of the Rank-Nullity Theorem and its applications.
Given a description of a linear transformation, find its matrix representation relative to given bases.
Demonstrate understanding of the relationship between similarity and change of basis.
Find the norm of a vector and the angle between two vectors in an inner product space.
Use the inner product to express a vector in an inner product space as a linear combination of an orthogonal set of vectors.
Find the orthogonal complement of a given subspace.
Demonstrate understanding of the relationship of the row space, column space, and nullspace of a matrix (and its transpose) via orthogonal complements.
Demonstrate understanding of the Cauchy-Schwartz inequality and its applications.
Determine whether a vector space with a (sesquilinear) form is an inner product space.
Use the Gram-Schmidt process to find an orthonormal basis of an inner product space. Be capable of doing this both in R n and in function spaces that are inner product spaces.
Use least squares to fit a line (y = ax + b ) to a table of data, plot the line and data points, and explain the meaning of least squares in terms of orthogonal projection.
Use the idea of least squares to find orthogonal projections onto subspaces and for polynomial curve fitting.
Find (real and complex) eigenvalues and eigenvectors of 2 × 2 or 3 × 3 matrices.
Determine whether a given matrix is diagonalizable. If so, find a matrix that diagonalizes it via similarity.
Demonstrate understanding of the relationship between eigenvalues of a square matrix and its determinant, its trace, and its invertibility/singularity.
Identify symmetric matrices and orthogonal matrices.
Find a matrix that orthogonally diagonalizes a given symmetric matrix.
Know and be able to apply the spectral theorem for symmetric matrices.
Know and be able to apply the Singular Value Decomposition.
Correctly define terms and give examples relating to the above concepts.
Prove basic theorems about the above concepts.
Prove or disprove statements relating to the above concepts.
Be adept at hand computation for row reduction, matrix inversion and similar problems; also, use MATLAB or a similar program for linear algebra problems.