Контрольная работа: Математическое моделирование систем и процессов

Математическое моделирование систем и процессов

ФГБОУ ВПО

ДВГУПС

Кафедра «Управление эксплуатационной работой».

КОНТРОЛЬНАЯ РАБОТА

Математическое моделирование систем и процессов

Гр.232

Выполнил: Илларионова Е.В

Проверил: Широков А.П.

ХАБАРОВСК

2013

Транспортная задача закрытого типа, представленная в матричной форме, с ограничениями пропускной способности.

Условие: Для заданного варианта транспортной задачи в матричной форме с ограничениями пропускной способности необходимо найти оптимальный план, при котором будет выполняться условие наименьшего суммарного пробега порожних вагонов. Для этого необходимо:

1)   Составить математическую модель задачи;

2)      Составить начальный план, проверить по условию вырождения, рассчитать суммарные вагоно-километры порожнего пробега;

)        Решить задачу методом потенциалов, рассчитать суммарные вагоно-километры порожнего пробега оптимального плана;

)        Сравнить начальный и оптимальный варианты.

Исходные данные транспортной задачи с ограничениями

математическое моделирование транспортная задача

Транспортная задача является закрытой, так как суммарные запасы ресурсов равны суммарным потребностям:

+25+25+15+45=18+20+12+15+10+15+20+25+15

=150

Математическая модель задачи:

.        Целевая функция:

2.      Система ограничения

3.      Условие не отрицательности

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

Начальный опорный план, построенный методом наименьшего критерия в столбце.

Значение целевой функции составит:

F=25*10+30*7+35*10+60*4+75*9+58*25+35*8+35*13+35*4+30*6+45*7+55*2+38*6+40*15+37*8+30*10+45*6=6349 (ваг-км)

Скорректированный начальный план, построенный методом наименьшего критерия в столбце

1.F=25*10+30*7+35*10+60*4+75*9+46*0+58*25+35*8+35*13+35*4+30*6+45*7+55*2+40*0+38*6+40*15+37*8+30*10+45*6=6349 (ваг-км)

.Проверка исходного опорного плана на условие «вырождения».

К_зб≤m+n-1

Где К_зб - число занятых базисных клеток; m- число строк матрицы (пунктов отправления); n-число столбцов (пунктов назначения).

≤ 5+9-1

≤13

Условие вырождения выполняется, но план является «вырожденным». Для устранения «вырождения» назначаются фиктивные перевозки х₅₁=0,х₂₃=0.

. Потенциалы столбцов определяются следующим образом:

V_i=U_i+c_ij

Где c_ij- критерий расстояния в заданной клетке.

Потенциалы строк определяются через занятые клетки, связанных со столбцами, получившими потенциал по формуле:

_i=V_j - c_ij

Проверка на оптимальность. План считается оптимальным, если соблюдается следующие условия:

_i - U_i ≤ c_ij, при x_ij=0 (клетка свободна)

V_i - U_i = c_ij, при  (клетка базисная)._i - U_i ≥c_ij, при x_ij=  (насыщенная клетка)

Формальное правило улучшения плана:

а) начиная с клетки с нарушением, двигаясь по горизонталям и вертикалям ходом «шахматной ладьи», строят замкнутый контур с вершинами в базисных клетках;

б) начиная с клетки с нарушением, нумеруют вершины контура (направление обхода контура значения не имеет);

в) в четный вершинах находится минимальная перевозка.

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

Формальное правило улучшения плана при нарушении условия оптимальности для насыщенных клеток:

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

б) начиная с клетки с нарушением, нумеруют вершины контура (направление обхода контура значения не имеет);

в) в нечетных вершинах находится минимальная перевозка;

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

Скорректированный план перевозок (первая итерация)

F=25*10+30*7+35*10+60*6+75*7+46*0+58*25+35*8+35*13+35*4+30*6+45*7+40*2+40*0+38*6+40*15+37*8+30*10+45*6=6289 (ваг-км)

Проверка на условие «вырождения»:

13≤5+9-1

=13

Скорректированный план перевозок (вторая итерация)