В задаче коммивояжера для формирования оптимального маршрута объезда 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 |
| 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 |
| 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 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 |
Наибольшая сумма констант приведения равна (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 |
Включение ребра (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 |
Наибольшая сумма констант приведения равна (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 |
Включение ребра (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 |
Нижняя граница подмножества (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 |
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (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 |
Наибольшая сумма констант приведения равна (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 |
Включение ребра (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 |
Нижняя граница подмножества (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 |
Наибольшая сумма констант приведения равна (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 |
Включение ребра (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 |
Нижняя граница подмножества (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 |
Наибольшая сумма констант приведения равна (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 |
Включение ребра (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).
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 (in English).
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 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
Copyright (c) 2015 Lesia М. Ohnivchuk
SAT Math Test охватывает ряд математических методов, с акцентом на решении задач, математические модели и стратегическое использование математических знаний.
SAT Math Test: все, как в реальном мире
Вместо того, чтобы тестировать Вас по каждой теме математики, новый SAT проверяет Ваше умение использовать математику, на которую Вы будете полагаться в большинстве случаев и во множестве самых различных ситуаций. Вопросы по математическому тесту предназначены для отражения решения задач и моделей, с которыми Вы будете иметь дело в
Университетском обучении, изучая непосредственно математику, а также естественнонаучные и социальные науки;
- Вашей ежедневной профессиональной деятельности;
- Вашей повседневной жизни.
Например, чтобы ответить на некоторые вопросы, Вам нужно будет использовать несколько шагов - потому что в реальном мире ситуации, когда один простой шагявляется достаточным, чтобы найти решение, встречается крайне редко.
SAT Math Format
SAT Math Test: основные факты
Математическая часть SAT делает основной акцент на трех областях математики, которые играют ведущую роль в большинстве академических дисциплин высших учебных заведений и профессиональной карьеры:
- Heart of Algebra
: Основы алгебры, которая фокусируется на решении линейными уравнений и систем;
- Problem Solving and Data Analysis
: Решение задач и анализ данных, которые необходимы для общей математической грамотности;
- Passport to Advanced Math
: Основы высшей математики, где задаются вопросы, требующие манипулирования со сложными уравнениями.
Математический тест также опирается на дополнительные темы в математике, включая геометрию и тригонометрию, наиболее важные для обучения в университете и профессиональной карьеры.
SAT Math Test: видео
Основы алгебры
Heart of Algebra
Этот раздел SAT Math фокусируется на алгебре и ключевых концепциях, которые наиболее важны для успеха в колледже и карьере. Здесь оценивается способность студентов анализировать, свободно решать и сстроить линейные уравнения и неравенства. Студенты также должны будут анализировать и свободно решать уравнения и системы уравнений с использованием нескольких методов.Чтобы полностью оценить знание этого материала, задачи будут существенно различаться по виду и содержанию. Они могут быть как достаточно простыми, так и требовать стратегического мышления и понимания, например, интерпретация взаимодействия между графическим и алгебраическим выражениями или представлять собой решение как процесс рассуждения. Экзаменуемые должны продемонстрировать не только знание методики решения, но и более глубокое понимание концепций, которые лежат в основе линейных уравнений и функций. Основы алгебры SAT Math оценивается по шкале от 1 до 15.
В этом разделе будут задания, ответ на которые представлен множественным выбором или самостоятельно вычеслен студентом. Использование калькулятора иногда разрешается, но не всегда необходимо или рекомендуется.
1. Построить, решить или интерпретировать линейное выражение или уравнение с одной переменной, в контексте каких-то определенных условий. Выражение или уравнение моеут иметь рациональные коэффициенты, и для упрощения выражения или решения уравнения могут потребоваться несколько шагов.
2. Построить, решать или интерпретировать линейные неравенства с одной переменной, в контексте каких-то определенных условий. Неравенство может иметь рациональные коэффициенты и для его упрощения или решения может потребоваться несколько шагов.
3. Построить линейную функцию, которая моделирует линейную зависимость между двумя величинами. Экзаменуемый должен описать линейную зависимость, которая выражает определенные условия, используя либо уравнение с двумя переменными, либо функцию. Уравнение или функция будут иметь рациональные коэффициенты, и для построения и упрощения уравнения или функции может потребоваться несколько шагов.
4. Построить, решить и интерпретировать системы линейных неравенств с двумя переменными. Экзаменуемый проанализирует одно или несколько условий, существующих между двумя переменными, путем построения, решения или интерпретации неравенства с двумя переменными или системы неравенств с двумя переменными, в рамках определенных заданных условий. Для построения неравенства или системы неравенств может потребоваться несколько шагов или определить.
5. Построить, решить и интерпретировать системы двух линейных уравнений с двумя переменными. Экзаменуемый проанализирует одно или несколько условий, существующих между двумя переменными, путем построения, решения или анализа системы линейных уравнений, в рамках определенных заданных условий. Уравнения будут иметь рациональные коэффициенты, и для упрощения или решения системы может потребоваться несколько шагов.
6. Решить линейные уравнения (или неравенства) с одной переменной. Уравнение (или неравенство) будет иметь рациональные коэффициенты и могут потребовать нескольких шагов для решения. Уравнения могут не иметь решения, иметь одно решение или бесконечное число решений. Экзаменуемому также может быть предложено определить значение или коэффициента уравнения, не имеющего решения или с бесконечным числом решений.
7. Решить системы двух линейных уравнений с двумя переменными. Уравнения будут иметь рациональные коэффициенты, и система может не иметь никакого решения, одно решение или бесконечного число решений. Экзаменуемому также может быть предложено определить значение или коэффициента уравнения, в котором система может не иметь решения, иметь одно решение или бесконечного число решений.
8. Объяснить связь между алгебраическими и графическими выражениями. Определить график, описываемый заданным линейным уравнением, или линейное уравнение, которое описывает данный график, определить уравнение линии, заданное устным описанием его графика, определит ключевые особенности графика линейной функции из его уравнения, определить, как на график может повлиять изменение его уравнения.
Решение задач и анализ данных
Problem Solving and Data Analysis
Данный раздел SAT Math отражают результаты исследований, которые выявили, что является важным для успешной учебы в коллежде или университете. Тесты требуют решения задач и анализ данных: умение математически описывать определенную ситуацию, учитывая задействованные элементы, знать и использовать разные свойства математических операций и чисел. Задачи в этой категории потребуют значительного опыта в логических рассуждениях.
От экзаменуемых потребуется знание вычислений средних значений показателей, общие закономерности и отклонения от общей картины и распространения во множествах.
Все вопросы по решению задач и анализу данных проверяют способность экзаменуемых использовать их математическое понимание и навыки для решения проблем, с которыми они могут столкнуться в реальном мире. Многие из этих проблем задаются в академических и профессиональных контекстах и, скорее всего, будут связаны с наукой и социологией.
Решение задач и анализ данных - одна из трех подразделов SAT Math, за решение которых начисляются баллы от 1 до 15.
В этом разделе будут задания с ответами с множественным выбором или рассчитанные самим экзаменуемым. Использование калькулятора здесь всегда разрешено, но не всегда необходимо или рекомендуется.
В этой части SAT Math Вам могут попасться следующие вопросы:
1. Используйте коэффициенты, ставки, пропорции и масштабные чертежи для решения одно- и многошаговых задач. Экзаменуемые будут использовать пропорциональную взаимосвязь между двумя переменными для решения многоэтапной задачи для определения отношения или скорости; Вычисление коэффициент или ставку, а затем решить многоступенчатую задачу, используя заданное соотношение или коэффициент, решить многоступенчатую проблему.
2. Решить одно- и многоступенчатые задачи с процентами. Экзаменуемый будет решать многоуровневую задачу для определения процента. Вычислить процент от числа, а затем решить многоуровневую задачу. Используя заданный процент, решить многоуровневую проблему.
3. Решить одно- и многоступенчатые задачи на вычисления. Экзаменуемый будет решать многоуровневую задачу, чтобы определить единицу ставки; Рассчитать единицу измерения, а затем решить многошаговую проблему; Решить многоуровневую задачу для завершения преобразования единицы; Решить многостадийную задачу расчета плотности; Или использовать понятие плотности для решения многоэтапной проблемы.
4. Используя диаграммы рассения, решить линейные, квадратичные или экспоненциальные модели для описания того, как связаны переменные. Учитывая диаграмму рассеяния, выбрать уравнение линии или кривой соответствия; Интерпретировать линию в контексте ситуации; Или используйте линию или кривую, наилучшим образом подходящие для предсказания.
5. Используя связь между двумя переменными, исследовать ключевые функции графика. Экзаменуемый установит связи между графическим выражением данных и свойствами графика, выбрав график, который представляет описанные свойства, или используя график, определенить значения или множества значений.
6. Сравните линейный рост с экспоненциальным ростом. Экзаменуемый должен будет найти соответствие между двумя переменными, чтобы определить, какой тип модели является оптимальным.
7, Используя таблицы, вычислять данные для различных категорий величин, относительных частот и условной вероятности. Экзаменуемый использует данные по различным категориям для расчета условных частот, условных вероятностей, ассоциации переменных или независимости событий.
8. Сделать выводы о параметрах популяции на основе выборочных данных. Экзаменуемый оценивает параметр популяции, учитывая результаты случайной выборки населения. В статистике выборки могут указываться доверительные интервалы и погрешность измерения, которые учащийся должен понимать и использовать, без необходимости их рассчета.
9. Использовать методы статистики для рассчета средних величин и распространения. Экзаменуемые будет вычислять среднюю величину и / или распределение для заданного набора данных или использовать данные статистики для сравнения двух отдельных наборов данных.
10. Оценивать отчеты, делать выводы, обосновывать выводы и определять целесообразность методов сбора данных. Отчеты могут состоять из таблиц, графиков или текстовых сводок.
Основы высшей математики
Passport to Advanced Math
Этот раздел SAT Math включают в себя темы, овладень которыми представляется особенно важно для учащихся, перед тем, как приступить к изучению высшей математики. Главым здесь является понимание структуры выражений и способность анализировать, манипулировать и упрощать эти выражения. Сюда также входит умение анализировать более сложные уравнения и функции.
Как и два предыдущих раздела SAT Math, задания здесь оцениваются от 1 до 15.
В этом разделе будут задания с ответами с множественным выбором или рассчитанные самим экзаменуемым.. Использование калькулятора иногда разрешается, но не всегда необходимо или рекомендуется.
В этой части SAT Math Вам могут попасться следующие вопросы:
1. Составьте квадратичную или экспоненциальную функцию или уравнение, которое моделирует данные условия. Уравнение будет иметь рациональные коэффициенты и может потребовать несколько шагов для упрощения или решения.
2. Определите наиболее подходящую форму выражения или уравнения, чтобы выявить конкретный признак, учитывая заданные условия.
3. Построить эквивалентные выражения с участием рациональных экспонентов и радикалов, включая упрощение или преобразование в другую форму.
4. Построить эквивалентную форму алгебраического выражения.
5. Решите квадратное уравнение, имеющее рациональные коэффициенты. Уравнение может быть представлено в широком диапазоне форм.
6. Сложить, вычесть и перемножить многочлены и упростить результат. Выражения будут иметь рациональные коэффициенты.
7. Решите уравнение в одной переменной, которая содержит радикалы или содержит переменную в знаменателе дроби. Уравнение будет иметь рациональные коэффициенты.
8. Решите систему линейных или квадратных уравнений. Уравнения будут иметь рациональные коэффициенты.
9. Упростить простые рациональные выражения. Экзаменуемые будут складывать, вычитать, умножать или делить два рациональных выражения или делить два многочлена и упрощать их. Выражения будут иметь рациональные коэффициенты.
10. Интерпретировать части нелинейных выражений в терминах их условий. Экзаменуемые должны связать заданные условия с нелинейным уравнением, которое моделирует эти условия.
11. Понимать взаимосвязь между нулями и множителями в многочленах и использовать эти знания для построения графиков. Экзаменуемые будут использовать свойства многочленов для решения задач, связанных с нулями, таких как определение, является ли выражение множителем многочлена, с учетом предоставленной информации.
12. Понимать связь между двумя переменными путем установления связей между их алгебраическими и графическими выражениями. Экзаменуемый дллжен уметь выбрать график, соответствующий данному нелинейному уравнению; интерпретировать графики в контексте решения систем уравнений; выбрать нелинейное уравнение, соответствующее данному графику; определить уравнение кривой с учетом вербального описания графика; определить ключевые особенности графика линейной функции из его уравнения; определить влияние на график изменения определяющего уравнения.
Что проверяет математический раздел SAT math
Общее владение дисциплиной
Математический тест - это шанс показать, что Вы:
Выполняете математические задания гибко, точно, эффективно и с использованием стратегии решения;
- Решаете задачи быстро, идентифицируя и используя наиболее эффективные подходы к решению. Это может включать решение задач путем
подстановки, поиска наикратчайшего пути или реорганизации предоставленной вами информации;
Концептуальное понимание
Вы продемонстрируете свое понимание математических понятий, операций и соотношений. Например, Вас могут попросить установить связи между свойствами линейных уравнений, их графиками и условиями, которые они выражают.
Применение знания предмета
Многия задания SAT Math взяты из реальных жизненных проблем и просят Вас проанализировать эту проблему, определить основные элементы, необходимые для ее решения, математически выразить эту проблему и найти решение.
Использование калькулятора
Калькуляторы - важные инструменты для проведения математических вычислений. Для успешного обучения в ВУЗе Вам нужно знать, как и когда их использовать. В части теста Math Test-Calculator вы сможете сосредоточиться на самом поиске решения и анализе, потому что Ваш калькулятор поможет сэкономить ваше время.
Тем не менее, калькулятор, как и любой инструмент, умный ровно настолько, как тот, кто его использует. В Math Test есть некоторые вопросы, в которых лучше не использовать калькулятор, даже если это Вам разрешено. В этих ситуациях экзаменуемые, которые умеют думать и рассуждать, зскорее всего, придут к ответу раньше тех, кто будет вслепую использовать калькулятор.
Часть Math Test-No Calculator облегчает возможность оценить Ваше общее знание предмета и понимание некоторых математических концепций. Он также проверяет знакомство с техникой вычислений и понимание концепции чисел.
Вопросы с занесением ответов в таблицу
Хотя большинство вопросов по математическому тесту являются множественным выбором, 22 процента - это вопросы, где ответы являются результатом вычислений самого экзаменуемого - они называемые grid-ins. Вместо того, чтобы выбирать правильный ответ из списка, Вам необходимо решить задания и ввести свои ответы в сетки, указанные в бланке ответов.
Ответы с занесением в таблицу
Отметьте не более одного кружка в любом столбце;
- Только ответы, указанные заполнением кружка, будут засчитаны (Вы не получите баллы за все, что написано в полях, расположенных над
кругами).
- Неважно, в какой колонке вы начинаете вводить свои ответы; важно, чтобы ответы были записаны внутри сетки, тогда Вы получите баллы;
- Сетка может содержать только четыре знака после запятой и может принимать только положительные числа и ноль.
- Если в задании не указано иначе, ответы могут быть введены в сетку как десятичные так и дробные;
- Дроби, такие как 3/24, не нуждаются в сокращении до минимальных значений;
- Все смешанные числа должны быть преобразованы в неправильные дроби, прежде чем записываться в сетку;
- Если ответ является повторяющимся десятичным числом, учащиеся должны установить наиболее точные значения, которые будут
учитывать.
Ниже приведен образец инструкций, которые экзаменуемые будут видеть на экзамене SAT Math:
Lectures on Elementary Mathematics (1898) is the earliest English translation of Joseph Louis Lagrange "s 1795 publication, Leçons élémentaires sur les mathematiques , containing a series of lectures delivered the same year at the Ecole Normale . The work was translated and edited by Thomas J. McCormack, and a second edition, from which the following quotes are taken, appeared in 1901.
Contents
Quotes [ edit ]
Lecture III. On Algebra, Particularly the Resolution of Equations of the Third and Fourth Degree [ edit ]
- Algebra is a science almost entirely due to the moderns... for we have one treatise from the Greeks, that of Diophantus ... the only one which we owe to the ancients in this branch of mathematics. ...I speak of the Greeks only, for the Romans have left nothing in the sciences, and to all appearances did nothing.
- His work contains the first elements of this science . He employed to express the unknown quantity a Greek letter which corresponds to our st and which has been replaced in the translations by N . To express the known quantities he employed numbers solely, for algebra was long destined to be restricted entirely to the solution of numerical problems.
- [H]e uses the known and the unknown quantities alike. And herein consists virtually the essence of algebra, which is to employ unknown quantities, to calculate with them as we do with known quantities, and to form from them one or several equations from which the value of the unknown quantities can be determined.
- Although the work of Diophantus contains indeterminate problems almost exclusively, the solution of which he seeks in rational numbers,- problems which have been designated after him Diophantine problems , -we nevertheless find in his work the solution of a number of determinate problems of the first degree, and even of such as involve several unknown quantities. In the latter case, however, the author invariably has recourse to... reducing the problem to a single unknown quantity, -which is not difficult.
- He gives, also, the solution of equations of the second degree , but is careful so to arrange them that they never assume the affected form containing the square and the first power of the unknown quantity. ...he always arrives at an equation in which he has only to extract a square root to reach the solution...
- Diophantus ... does not proceed beyond equations of the second degree, and we do not know if he or any of his successors... ever pushed... beyond this point.
- Diophantus was not known in Europe until the end of the sixteenth century, the first translation having been a wretched one by Xylander made in 1575. Bachet de Méziriac ... a tolerably good mathematician for his time, subsequently published (1621) a new translation... accompanied by lengthy commentaries, now superfluous. Bachet"s translation was afterwards reprinted with observations and notes by Fermat .
- Prior to the discovery and publication of Diophantus ... algebra had already found its way into Europe. Towards the end of the fifteenth century there appeared in Venice a work by... Lucas Paciolus on arithmetic and geometry in which the elementary rules of algebra were stated.
- [T]he Europeans, having received algebra from the Arabs, were in possession of it one hundred years before the work of Diophantus was known to them. They made, however, no progress beyond equations of the first and second degree.
- In the work of Paciolus ... the general resolution of equations of the second degree... was not given. We find in this work simply rules, expressed in bad Latin verses, for resolving each particular case according to the different combinations of the signs of the terms of equation, and even these rules applied only to the case where the roots were real and positive. Negative roots were still regarded as meaningless and superfluous.
- It was geometry really that suggested to us the use of negative quantities, and herein consists one of the greatest advantages that have resulted from the application of algebra to geometry, -a step which we owe to Descartes .
- In the subsequent period the resolution of equations of the third degree was investigated and the discovery for a particular case ultimately made by... Scipio Ferreus (1515). ...Tartaglia and Cardan subsequently perfected the solution of Ferreus and rendered it general for all equations of the third degree.
- At this period, Italy, which was the cradle of algebra in Europe, was still almost the sole cultivator of the science, and it was not until about the middle of the sixteenth century that treatises on algebra began to appear in France, Germany, and other countries.
- The works of Peletier and Buteo were the first which France produced in this science...
- Tartaglia expounded his solution in bad Italian verses in a work treating of divers questions and inventions printed in 1546, a work which enjoys the distinction of being one of the first to treat of modern fortifications by bastions .
- Cardan published his treatise Ars Magna , or Algebra ... Cardan was the first to perceive that equations had several roots and to distinguish them into positive and negative. But he is particularly known for having first remarked the so-called irreducible case in which the expression of the real roots appears in an imaginary form. Cardan convinced himself from several special cases in which the equation had rational divisors that the imaginary form did not prevent the roots from having a real value. But it remained to be proved that not only were the roots real in the irreducible case, but that it was impossible for all three together to be real except in that case. This proof was afterwards supplied by Vieta , and particularly by Albert Girard , from considerations touching the trisection of an angle .
- [T]he irreducible case of equations of the third degree ... presents a new form of algebraical expressions which have found extensive application in analysis... it is constantly giving rise to unprofitable inquiries with a view to reducing the imaginary form to a real form and... it thus presents in algebra a problem which may be placed upon the same footing with the famous problems of the duplication of the cube and the squaring of the circle in geometry.
- The mathematicians of the period under discussion were wont to propound to one another problems for solution. These... were... public challenges and served to excite and to maintain that fermentation which is necessary for the pursuit of science. The challenges... were continued down to the beginning of the eighteenth century Europe, and really did not cease until the rise of the Academies which fulfilled the same end... partly by the union of the knowledge of their various members, partly by the intercourse which they maintained... and... by the publication of their memoirs, which served to disseminate the new discoveries and observations...
- The Algebra of Bombelli contains not only the discovery of Ferrari but also divers other important remarks on equations of the second and third degree and particularly on the theory of radicals by means of which the author succeeded in several cases in extracting the imaginary cube roots of the two binomials of the formula of the third degree in the irreducible case, so finding a perfectly real result... the most direct proof possible of the reality of this species of expressions.
- The solution of equations of the third and fourth degree was quickly accomplished. But the successive efforts of mathematicians for over two centuries have not succeeded in surmounting the difficulties of the equation of the fifth degree.
- Yet these efforts are far from having been in vain. They have given rise to the many beautiful theorems... on the formation of equations, on the character and signs of the roots, on the transformation of a given equation into others of which the roots may be formed at pleasure from the roots of the given equation, and finally, to the beautiful considerations concerning the metaphysics of the resolution of equations from which the most direct method of arriving at their solution, when possible, has resulted.
- Vieta and Descartes ... Harriot ... and Hudde ... were the first after the Italians... to perfect the theory of equations, and since their time there is scarcely a mathematician of note that has not applied himself...
Lecture V. On the Employment of Curves in the Solution of Problems [ edit ]
- As long as algebra and geometry travelled separate paths their advance was slow and their applications limited. But when these two sciences joined company, they drew from each other fresh vitality and thenceforward marched on at a rapid pace towards perfection. It is to Descartes that we owe the application of algebra to geometry,-an application which has furnished the key to the greatest discoveries in all branches of mathematics.
- The method... for finding and demonstrating divers general properties of equations by considering the curves which represent them, is a species of application of geometry to algebra... [T]his method has extended applications, and is capable of readily solving problems whose direct solution would be extremely difficult or even impossible... [T]his subject... is not ordinarily found in elementary works on algebra.
- [A]n equation of any degree can be resolved by means of a curve, of which the abscissæ represent the unknown quantity of the equation, and the ordinates the values which the left-hand member assumes for every value of the unknown quantity. ...[T]his method can be applied generally to all equations, whatever their form, and... only requires them to be developed and arranged according to the different powers of the unknown quantity. [ edit ]
- Lectures on Elementary Mathematics 2nd ed. (1901) @GoogleBooks
Вместе с этим калькулятором также используют следующие:
Графический метод решения ЗЛП
Симплексный метод решения ЗЛП
Решение матричной игры
С помощью сервиса в онлайн режиме можно определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.
Экстремум функции двух переменных
Задачи динамического программирования
Первым этапом решения транспортной задачи является определение ее типа (открытая или закрытая, или иначе сбалансированная или не сбалансированная). Приближенные методы (методы нахождения опорного плана ) позволяют на втором этапе решения за небольшое число шагов получить допустимое, но не всегда оптимальное, решение задачи. К данной группе методов относятся методы:
- вычеркивания (метод двойного предпочтения);
- северо-западного угла;
- минимального элемента;
- аппроксимации Фогеля.
Опорное решение транспортной задачи
Опорным решением транспортной задачи называется любое допустимое решение, для которого векторы условий, соответствующие положительным координатам, линейно независимы. Для проверки линейной независимости векторов условий, соответствующих координатам допустимого решения, используют циклы.Циклом называется такая последовательность клеток таблицы транспортной задачи, в которой две и только соседние клетки расположены в одной строке или столбце, причем первая и последняя также находятся в одной строке или столбце. Система векторов условий транспортной задачи линейно независима тогда и только тогда, когда из соответствующих им клеток таблицы нельзя образовать ни одного цикла. Следовательно, допустимое решение транспортной задачи, 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
