Использование АОС «Транспортная задача»

ПЕРВОЕ ВЫСШЕЕ ТЕХНИЧЕСКОЕ УЧЕБНОЕ ЗАВЕДЕНИЕ РОССИИ

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«НАЦИОНАЛЬНЫЙ МИНЕРАЛЬНО-СЫРЬЕВОЙ УНИВЕРСИТЕТ «ГОРНЫЙ»

КАФЕДРА ИНФОРМАЦИОННЫХ СИСТЕМ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

Использование АОС «Транспортная задача»

Санкт-Петербург

Цель работы

Целью данной лабораторной работы является решение математической задачи, которая представлена в виде модели транспортной задачи.

Задание

Решить транспортную задачу методом потенциалов, используя АОС.

Согласно УМК условия задания (таблица № 1) выбираются студентом самостоятельно и согласовывается с преподавателем каждым студентом индивидуально.

Таблица № 1. Условия математической транспортной задачи для ее решения методом потенциалов

Решение

Математическая модель транспортной задачи: F =? ? c_ijx_ij, (1), при условиях:

? x_ij = a_i при i = 1, 2,…, m, (2) и? x_ij = b_j при j = 1, 2, …, n, (3).

С целью составления двойственной задачи переменные x_ij в условии (2) заменим на u₁, u₂, u_i, …, u_m, а переменные x_ij в условия (3) на v₁, v₂, v_j,…, v_n.

Поскольку каждая переменная x_ij входит в условия (2,3) и целевую функцию (1) по одному разу, то двойственную задачу по отношению к прямой транспортной задаче можно сформулировать следующим образом.

Требуется найти не отрицательные числа u_i (при i = 1, 2, …, m) и v_j (при j = 1, 2, …, n), обращающие в максимум целевую функцию: G =? a_iu_i +? b_jv_jпри условии:

u_i + v_j? c_ij, i = 1, 2, …, m; j = 1, 2, …, n (4).

В систему условий (4) будет mxn неравенств. По теории двойственности для оптимальных планов прямой и двойственной задачи для всех i, j должно быть: u_i + v_j? c_ij, если x_ij = 0, u_i + v_j = c_ij, если x_ij? 0,

Эти условия являются необходимыми и достаточными признаками оптимальности плана транспортной задачи.

Числа u_i, v_j называются потенциалами. Причем число u_i называется потенциалом поставщика, а число v_j — потенциалом потребителя.

Для упрощения решения математической транспортной задачи воспользуемся программным комплексом «АОС транспортная задача» разработанным студентом Сорокиным Д.Ю.

1.По первой теореме двойственности в оптимальном решении значения целевых функций прямой и двойственных задач совпадают: F = G.

Стоимость доставки единицы груза из каждого пункта отправления в соответствующие пункты назначения задана матрицей тарифов в таблице № 1 и отображена на рисунке № 1.

транспортный задача потенциал поставка

Рисунок № 1. Ввод исходных данных задачи в программу «АОС транспортная задача»

Проверим необходимое и достаточное условие разрешимости задачи:

?_a = 25+25+25= 75

?_b = 30+25+20= 75

Условие баланса соблюдается. Запасы равны потребностям. Следовательно, модель транспортной задачи является закрытой.

2.Решим задачу диагональным методом или методом северо-западного угла

Благодаря программе «АОС транспортная задача» автоматически получен первый опорный план рисунок № 2, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.

Рисунок № 2. Первый опорный план и проверка целевой функции

3.Подсчитаем число занятых клеток таблицы на рисунке № 2.

Количество занятых клеток равно 5, а должно быть m + n — 1 = 5. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F (x) = 700

4.Проверим оптимальность опорного плана путем поиска предварительных потенциаловu_i, v_i. по занятым клеткам таблицы, в которых u_i + v_i = c_ij, полагая, что u₁ = 0.

Благодаря программе «АОС транспортная задача» найдем предварительные потенциалы.

Результат поиска потенциалов отобразим на рисунке № 3.

Рисунок № 3. Результат поиска предварительных потенциалов в программе «АОС транспортная задача»

5.Проверим результат поиска предварительных потенциалов путем вычисления невязок.

С помощью программы «АОС транспортная задача» вычислим невязки.

Результат вычисления невязок отобразим на рисунке № 4

Рисунок № 4. Результат вычисления невязок в программе «АОС транспортная задача»

6. Согласно полученным результатам на рисунке № 4, выходит, что все потенциалы не равны нулю, следовательно, u_i + v_i>c_ij, тогда предложенный план не оптимален.

Следовательно, нажимается кнопка «Нет».

7. На рисунке № 5, программа «АОС транспортная задача» просит ввести «Координаты перевозки, вводимый в базис».

Рисунок № 5. Ввод координат перевозки, вводимый в базис

8. Произведем ввод «координаты перевозки, вводимый в базис», которые в данном случае будут: A (i) = 3 и B (j)= 1.

Ввод «координат перевозки, вводимый в базис» в программе «АОС транспортная задача» изображен на рисунке № 6.

9. В следующем окне программа «АОС транспортная задача» построит цикл поставок рисунке № 7.

Рисунок № 6. Ввод координат перевозки, вводимый в базис Рисунок № 7. Цикл поставок Рисунок № 8. Цикл поставок с удаленными ребрами

10. В следующем окне (рисунке № 7) программа «АОС транспортная задача» построит цикл поставок.

11. Для дальнейшего решения задачи требуется в окне программы «АОС транспортная задача» выделить все ребра, которые не входят в цикл и удалить их.

В результате этих удалений получится цикл рисунок № 8.

12. Введем знаки для клеток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)

13. Выберем из клеток A (2)B (2)и А (3)В (3) минимальное количество товара, которое равняется 5, т. е. это значение находящиеся в клетке А (2)В (3).

Введем данное значение в поле «Из клеток помеченных знаком „-“ выберите MIN значение».

В результате всех выше описанных действий с программой «АОС транспортная задача» получился новый опорный план, который изображен на рисунке № 10.

Рисунок № 10. Второй опорный план Рисунок № 11. Второй опорный план и проверка целевой функции

14.Подсчитаем число занятых клеток таблицы на рисунке № 11.

Количество занятых клеток равно 6, а должно быть m + n — 1 = 6. Следовательно, опорный план является невырожденным.

Значение целевой функции для этого опорного плана равно:

F (x) = 625

15.Далее итерация повторяется до тех пор, пока все потенциалыне станут равны нулю, следовательно u_i + v_i?c_ij, тогда предложенный план оптимален.

На рисунке № 12 можно увидеть результат деятельности программы «АОС транспортная задача», который подтверждает, что изначально предложенный план по доставке и распределения груза оптимален, и поздравление с его получением.

Рисунок № 12. Окончательный вариант плана поставок товара предоставленный программой «АОС транспортная задача»