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

ФГБОУ ВПО ДВГУПС Кафедра «Управление эксплуатационной работой».

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

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

Гр.232

Выполнил: Илларионова Е. В Проверил: Широков А.П.

ХАБАРОВСК

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

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

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

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

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

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

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

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

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

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

150=150

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

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

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 (ваг-км)

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

К_зб?m+n-1

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

11? 5+9−1

11?13

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

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

V_i=U_i+c_ij

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

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

U_i=V_j — c_ij

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

V_i — U_i? c_ij, при x_ij=0 (клетка свободна)

V_i — U_i = c_ij, при (клетка базисная).

V_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=13

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

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

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

12?5+9−1

12?13

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

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

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

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

13?5+9−1

13=13

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

F=25*10+30*7+45*6+35*10+55*7+46*0+58*25+35*2+35*13+40*0+35*10+30*6+40*9+40*6+40*15+37*8+30*10+45*6=6036 (ваг-км)

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

13?5+9−1

13=13

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

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

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

13?5+9−1

13=13

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

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

Скорректированный опорный план проверяется на условие «вырождения»:

К_зб?m+n-1

13?5+9−1

13=13

После присвоения потенциалов всем столбцам и строкам матрицы проверяются условия оптимальности.

В полученном плане нет нарушений условий оптимальности. План оптимальный.

Значение целевой функции уменьшилось по сравнению с начальным планом на 313 ваг.-км (6349−6036=313) или на 313/6349*100%=4,9%

Условие.

На 4 станциях А₁, А₂, А₃ и А₄ имеется избыток порожних вагонов в размере соответственно а₁, а₂, а₃ и а₄ (табл.1) вагонов. Необходимо распределить данные вагоны по 7 станциям В₁, В₂, В₃, В₄, В₅, В₆ и В₇ с недостатком порожняка соответственно в количестве b₁, b₂, b₃, b₄, b_5, b₆ и b₇ вагонов (табл. 2). Расстояние между каждой станцией отправления (избытка вагонов) и каждой станцией назначения (недостатка порожняка) представлено в виде матрицы (табл.3).

Необходимо составить план распределения вагонов между указанными станциями с минимальным суммарным пробегом порожних вагонов.

Ресурсы станций отправления

Таблица 1.

Потребности станции назначения

Таблица 2.

Матрица расстояний между станциями, км

Таблица 3.

Исходный план транспортной задачи.

Данная задача является, задачей транспортного вида (так как суммарный объем производства, а а_i равен суммарному объему потребления, а b_i):

а₁+а₂+а₃+а₄=b₁+b₂+b₃+b₄

300=300

Целевая функция (суммарный пробег порожних вагонов) определяется по формуле:

где с_ij— расстояние перевозки от i-ой станции отправления до j-ой станции назначения; x_ij — величина перевозки из пункта отправления i-ой станции отправления до j-ой станции назначения.

Система ограничений

где a_i — ресурсы i-ой станции отправления; b_j — потребность j-ой станции назначения.

Условие формирования закрытой транспортной задачи:

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

Исходный опорный план перевозок может быть построен различными методами.

1.Метод северо-западного угла.

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

F = 25*55+33*45+37*5+29*45+42*35+34*15+37*30+57*25+36*5+42*40= 10725(ваг-км)

2. Метод наименьшего критерия в строке.

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

F=25*55+28*50+18*45+34*10+26*25+34*30+21*15+25*25+29*45=7840 (ваг-км)

3.Метод наименьшего критерия в столбце.

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

F=24*15+22*40+28*50+18*45+42*25+34*10+32*45+25*25+41*10+29*35=8330 (ваг-км)

4.Метод двойного предпочтения

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

F=24*30+38*25+33*15+28*35+18*45+26*35+32*40+21*5+25*25+29*45=8180 (ваг-км)

5. Метод минимального элемента.

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

F=18*45+43*25+32*5+41*25+24*55+25*25+29*20+28*50+34*10+21*40=8175 (ваг-км)

Как видно из приведенных расчетов наименьшее значение целевой функции (суммарный пробег порожних вагонов) получено при построении начального опорного плана методом наименьшего критерия в строке (F=7840 ваг-км).

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