Распределение заданий между исполнителями

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

В целевой функции определялся суммарный грузооборот. Более сложная задача: распределение заданий между отдельными видами оборудования – расстановка флота по линиям для перегрузки тех или иных видов грузов.

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

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

Введем переменные:

– количество типов судов, , шт

 – количество линий, , шт

 – общее количество судов -ого типа, шт

 – навигационный грузооборот -ой линии, в тыс. тонн

– провозная способность судна   -ого типа судна на -ой линии, в тыс. тонн

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

,                                      (4.10)

где – количество судов   -ого типа, закрепленных на -ой линии, шт

При этом должны быть выполнены следующие допустимости:

1) ,

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

2) ,

Количество судов -ого типа, расставленных по всем линиям не должно превышать их наличие.

3)

Количество судов не должно быть отрицательным.

Построим первый опорный план по максимальной производительности методом Фогеля.

В правом верхнем углу, на пересечении линии и типа судна, заполняем провозную способность судов (табл.4.6). Необходимо в столбцах по каждому типу судна (сначала «Беломорск», «1810», «576») выбрать две максимальные провозные способности и записать их разность в первый столбец разности. Аналогично вычислить строки разности. Из полученных чисел выбираем максимальное значение, которое равно 5,17. Тогда в столбце «линия ЕН» количество груза, перевозимое на этой линии, делим на максимальную провозную способность в данном столбце, полученный результат записываем в соответствующую клетку. В строке разности ставим символ F, обозначающий, что на данной линии перевезен весь груз. Остальные строки и столбцы разности рассчитываем аналогично, но, уже не учитывая провозные способности судов всех типов на линии ЕН.

Таблица 4.7 – Первый опорный план

Полученные данные можно оформить в следующую таблицу 4.8, в которую также заносим данные об эксплуатационных расходах по судну за навигацию.

Таблица 4.8 – Данные для разработки оптимального плана расстановки флота по линиям

Таблица 4.9 – Проверка оптимальности полученного плана

	АП 79	АР 532	БЛ 244	БМ 197	БП 11	ЕЛ 105	ЕН 661	£i
Бел-ск 6	171,94  171,94 1,45 25,04	174,36   174,36 4,55 23,14	185,11   183,92   71,45	178,63       178,83   45,02	174,99 175,10   36,93	165,82      165,67   63,57	175,93   176,08   71,81	0
1810 4	241,85   240,25   46,14	244,27   243,27   42,67	255,02   255,02 1,81 134,97	248,54      248,54 2,19 84,64	244,90 244,07   68,49	235,73       232,84   115,60	245,84   245,21   133,43	69,91
576 7	217,23   217,23 0,91 47,16	219,65   219,73   43,04	230,40   228,70   132,27	223,92     223,92 0,14 83,52	220,28 220,28 0,16 69,24	211,11      211,11 0,87 120,77	221,22   221,22 4,92 134,36	45,29
781 10	282,13   281,10   51,73	284,55   284,55 8,99 47,49	295,30   297,32   149,03	288,82       290,29   93,78	285,18 285,33   76,48	276,01       272,72   130,63	286,12   286,64   148,86	110,19
	171,94	174,36	185,11	178,63	174,99	165,82	175,93

Себестоимость данного плана равна 6 142,98 тыс. руб.. План не оптимален, т.к. существуют клетки, где псевдостоимость больше стоимости. Необходимо найти клетку с максимальной переплатой и построить контур пересчета с базисными клетками, поворачивая каждый раз на 90º. Расставлять знаки «+» и «-» надо в клетках, по которым проходят углы контура, по очереди, начиная со знака «+» в клетке с максимальной переплатой. В клетках со знаком «-» находим наименьшее количество задействованных судов и переносим их по контуру соответственно знакам. Обязательно необходимо проверять выполнение системы ограничений, описанных ранее.

Таблица 4.10 – Перенос судов по контуру пересчета               

	АП 79	АР 532	БЛ 244	БМ 197	БП 11	ЕЛ 105	ЕН 661	£i
Бел-ск 6	171,94 0,58 25,04	174,36 5,42 23,14	183,92   71,45	178,83   45,02	175,10   36,93	165,67   63,57	176,08   71,81
1810 4	240,25   46,14	243,27   42,67	255,02 1,81 134,97	248,54 2,19 84,64	244,07   68,49	232,84   115,60	245,21   133,43
576 7	217,23 1,37 47,16	219,73   43,04	228,70   132,27	223,92 0,14 83,52	220,28 0,16 69,24	211,11 120,77	221,22 4,92 134,36
781 10	281,10   51,73	284,55 8,57 47,49	297,32   149,03	290,29   93,78	285,33   76,48	272,72 0,81 130,63	286,64   148,86

 Себестоимость данного плана равна 6 165,40 тыс. руб. Перенос судов по контуру пересчета не дал положительных результатов, т.к. себестоимость только увеличилась на 22,42 тыс. руб., поэтому рассчитывать потенциалы в виде платежей и псевдостоимости нет смысла. Следовательно, можно условно принять, что полученный план по данным таблицы 4.8 является оптимальным.

Таким образом, на всех 7-ми линиях перевозки осуществлены в заданном объеме (ΣQ=1 829 тыс. тонн груза), на линиях работают суда в количестве согласно заданным ограничениям. Тип судна «Беломорск» задействован на линиях: АП и АР в общем количестве 6 единиц. Суда типа «1810» в количестве 4 единиц работают на направлении БЛ и БМ. В свою очередь суда типа «576» перевозят груз на линиях АП, БМ, БП, ЕЛ и ЕН общей численностью 7 единиц техники. Тип судна «781» осуществляет перевозку груза на линии АР в количестве 9 судов. Минимальная себестоимость всего комплекса работ 6 142,98 тыс. руб..

ЗАКЛЮЧЕНИЕ

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

Алгоритм и методы решения транспортной задачи могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с транспортировкой груза. В этом случае величины тарифов c_ij имеют различный смысл в зависимости от конкретной экономической задачи.

Таким образом, важность решения данной задачи для экономики несомненна.

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

Расстановка флота по линиям осуществлялась с помощью метода Фогеля. Решение задачи при помощи данного метода сопровождается большими объемами вычислений, в результате чего было установлено, что на всех линиях были задействованы все данные суда типа «Беломорск», «1810», «576» и в дополнение еще арендовано 9 судов типа «781». Перевозка груза осуществлена в полном объеме, согласно заданным условиям и ограничениям.