Использование АОС 'Транспортная задача'
ПЕРВОЕ
ВЫСШЕЕ ТЕХНИЧЕСКОЕ УЧЕБНОЕ ЗАВЕДЕНИЕ РОССИИ
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
федеральное
государственное бюджетное образовательное учреждение высшего профессионального
образования
«НАЦИОНАЛЬНЫЙ
МИНЕРАЛЬНО-СЫРЬЕВОЙ УНИВЕРСИТЕТ «ГОРНЫЙ»
КАФЕДРА
ИНФОРМАЦИОННЫХ СИСТЕМ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ
Использование
АОС «Транспортная задача»
Санкт-Петербург
Цель работы
Целью данной лабораторной работы является решение математической задачи,
которая представлена в виде модели транспортной задачи.
Задание
Решить транспортную задачу методом потенциалов, используя АОС.
Согласно УМК условия задания (таблица №1) выбираются студентом
самостоятельно и согласовывается с преподавателем каждым студентом
индивидуально.
Таблица №1. Условия математической транспортной задачи для ее решения
методом потенциалов
Поставщик
|
Потребители
|
Запасы
|
|
1
|
2
|
3
|
|
|
1
|
15
|
5
|
5
|
|
25
|
2
|
10
|
5
|
10
|
|
25
|
3
|
5
|
15
|
5
|
|
25
|
Потребность
|
30
|
25
|
20
|
|
|
Решение
Математическая модель транспортной задачи: F = ∑ ∑ cijxij,
(1), при условиях:
∑ xij = ai при i = 1, 2,…, m, (2) и ∑xij
= bj при j = 1, 2, …, n, (3).
С целью составления двойственной задачи переменные xij в
условии (2) заменим на u1, u2, ui, ..., um,
а переменные xij в условия (3) на v1, v2, vj,...,
vn.
Поскольку каждая переменная xij входит в условия (2,3) и
целевую функцию (1) по одному разу, то двойственную задачу по отношению к
прямой транспортной задаче можно сформулировать следующим образом.
Требуется найти не отрицательные числа ui (при i = 1, 2, …, m)
и vj (при j = 1, 2, …, n), обращающие в максимум целевую функцию: G
= ∑ aiui + ∑ bjvjпри
условии:
ui + vj ≤ cij, i = 1,
2, ..., m; j = 1, 2, ..., n (4).
В систему условий (4) будет mxn неравенств. По теории двойственности для
оптимальных планов прямой и двойственной задачи для всех i, j должно быть: ui
+ vj ≤ cij, если xij = 0, ui
+ vj = cij, если xij ≥ 0,
Эти условия являются необходимыми и достаточными признаками оптимальности
плана транспортной задачи.
Числа ui , vj называются потенциалами. Причем число
ui называется потенциалом поставщика, а число vj -
потенциалом потребителя.
Для упрощения решения математической транспортной задачи воспользуемся
программным комплексом «АОС транспортная задача» разработанным студентом
Сорокиным Д.Ю.
.По первой теореме двойственности в оптимальном решении значения целевых
функций прямой и двойственных задач совпадают: F = G.
Стоимость доставки единицы груза из каждого пункта отправления в
соответствующие пункты назначения задана матрицей тарифов в таблице №1 и
отображена на рисунке №1.
транспортный задача потенциал поставка
Рисунок №1. Ввод исходных данных задачи в программу «АОС транспортная
задача»
Проверим необходимое и достаточное условие разрешимости задачи:
∑a = 25+25+25= 75
∑b = 30+25+20= 75
Условие баланса соблюдается. Запасы равны потребностям. Следовательно,
модель транспортной задачи является закрытой.
.Решим задачу диагональным методом или методом северо-западного угла
Благодаря программе «АОС транспортная задача» автоматически получен
первый опорный план рисунок №2, который является допустимым, так как все грузы
из баз вывезены, потребность магазинов удовлетворена, а план соответствует
системе ограничений транспортной задачи.
Рисунок №2. Первый опорный план и проверка целевой функции
3.Подсчитаем число занятых клеток таблицы на рисунке №2.
Количество занятых клеток равно 5, а должно быть m + n - 1 = 5.
Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
(x) = 700
4.Проверим оптимальность опорного плана путем поиска предварительных
потенциаловui, vi. по занятым клеткам таблицы, в которых
ui + vi = cij, полагая, что u1 = 0.
Благодаря программе «АОС транспортная задача» найдем предварительные
потенциалы.
Результат поиска потенциалов отобразим на рисунке №3.
Рисунок №3. Результат поиска предварительных потенциалов в программе «АОС
транспортная задача»
5.Проверим результат поиска предварительных потенциалов путем вычисления
невязок.
С помощью программы «АОС транспортная задача» вычислим невязки.
Рисунок №4. Результат вычисления невязок в программе «АОС транспортная
задача»
. Согласно полученным результатам на рисунке №4, выходит, что все
потенциалы не равны нулю, следовательно,ui + vi>cij,тогда
предложенный план не оптимален.
Следовательно, нажимается кнопка «Нет».
. На рисунке №5, программа «АОС транспортная задача» просит ввести
«Координаты перевозки, вводимый в базис».
Рисунок №5. Ввод координат перевозки, вводимый в базис
. Произведем ввод «координаты перевозки, вводимый в базис», которые в
данном случае будут: A(i) = 3 и B(j)= 1.
Ввод «координат перевозки, вводимый в базис» в программе «АОС
транспортная задача» изображен на рисунке №6.
. В следующем окне программа «АОС транспортная задача» построит цикл
поставок рисунке №7.
Рисунок №6. Ввод координат перевозки, вводимый в базис
Рисунок №7. Цикл поставок
Рисунок №8. Цикл поставок с удаленными ребрами
. В следующем окне (рисунке №7) программа «АОС транспортная задача»
построит цикл поставок.
. Для дальнейшего решения задачи требуется в окне программы «АОС
транспортная задача» выделить все ребра, которые не входят в цикл и удалить их.
В результате этих удалений получится цикл рисунок №8.
. Введем знаки для клетокA(2)B(2), А(2)В(3) и А(3)В(3).
В результате ввода знаков для клетокполучается, что значение клеток A(2)B(2) иА(3)В(3) отрицательное, а значение клеток A(2)B(3) и A(3)B(2) положительное, что изображено на
рисунке №9.
Рисунок №9. Результате ввода знаков клетокA(2)B(2),
А(2)В(3) и А(3)В(3)
. Выберем из клеток A(2)B(2)и А(3)В(3) минимальное количество
товара, которое равняется 5, т.е. это значение находящиеся в клетке А(2)В(3).
Введем данное значение в поле «Из клеток помеченных знаком «-» выберите MIN значение».
В результате всех выше описанных действий с программой «АОС транспортная
задача» получился новый опорный план, который изображен на рисунке №10.
Рисунок №10. Второй опорный план
Рисунок №11. Второй опорный план и проверка целевой функции
.Подсчитаем число занятых клеток таблицы на рисунке №11.
Количество занятых клеток равно 6, а должно быть m + n - 1 = 6.
Следовательно, опорный план является невырожденным.
Значение целевой функции для этого опорного плана равно:
(x) = 625
.Далее итерация повторяется до тех пор, пока все потенциалыне станут
равны нулю, следовательно ui + vi≤cij,
тогда предложенный план оптимален.
На рисунке №12 можно увидеть результат деятельности программы «АОС
транспортная задача», который подтверждает, что изначально предложенный план по
доставке и распределения груза оптимален, и поздравление с его получением.
Рисунок №12. Окончательный вариант плана поставок товара предоставленный
программой «АОС транспортная задача»