Пархоменко В.И. Транспортная логистика и транспортные средства - файл n1.doc

Пархоменко В.И. Транспортная логистика и транспортные средства
скачать (9166 kb.)
Доступные файлы (1):
n1.doc9166kb.07.11.2012 02:35скачать

n1.doc

1   2   3   4   5   6   7   8   9   ...   13

По окончательной таблице строим оптимальные маршруты, наводя их двойными линиями на графе (рисунок 10).
1.5.2 Задача расчета потребного числа автомобилей

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

Суть задачи.

а) Дано:

- количество грузоотправителей – n. Обозначим их О1, О2, О3,...,ОX,…, Оn;

- количество грузополучателей – m. Обозначим их П1, П2, П3,…, Пi,… Пm;

- количество груза, которое необходимо доставить каждому получателю – GПi, т. Например, GП1, GП2, GП3,…,GПi,…, GПm ;

- время, отпущенное для вывоза груза - Т, мес.;

- продолжительность рабочей смены – tСМ, час.;

- время оборота автомобилей на маршрутах «грузоотоправитель-грузополучатель-грузоотправитель» - tПi, час. Например, tП1, tП2, tП3,…tПi,…, tПm;

- грузоподъемность выделенных автомобилей – Q, т.;

- количество рабочих дней в месяце – ДР.Д.

б) Требуется определить максимально допустимое количество автомобилей, необходимых для выполнения этой работы - Cmax.
Решение задачи.

Для примера примем систему из одного поставщика груза и j получателей.

а) Определяем суммарное количество ездок к получателям грузов
; (2)
б) Определяем среднее количество ездок в день для каждого получателя
(3)
На этом подготовительный этап решения закончен
1-й этап

а) Составим j возможных вариантов маршрутов с условием, что суммарное время их выполнения () не превышает времени смены ().

В принципе элементами каждого маршрута являются ездки от любого грузообразующего пункта (ОX) до любого из грузополучателей (Пi) и обратно. В общем случае обозначим этот элемент «ОX – Пi», который соответствует времени оборота автомобиля tПi . Тогда любой j–тый маршрут обозначится последовательными сочетаниями «ОX – Пi». Например, 1-й маршрут от грузообразующего пункта О1 как вариант может быть обозначен

О1 – П1 – О1 – П1 – О1 – П3 – О1 – …– О1 – Пi
При этих сочетаниях «ОX – Пi» суммарное время каждого маршрута (tMj) не должно превышать продолжительности рабочей смены (tСМ)
, (4)
где - количество одинаковых элементов «OX – Пi» в маршруте.

Перечень маршрутов оформляется в виде таблицы (таблица 6).
Таблица 6 – Перечень маршрутов (пример)



маршрута

п/п

Маршрут

Время выполнения, час

1.

О1 – П1 – О1 – П1




2.

О1 – П2 – О1 –… – О1 – П2



………….

………………………………………

………………….

Z

О1 – Пi – О1 –…– О1 – Пm



…….….

……………………………………….

………………….

…………

………………………………………..

………………….

j

О1 – Пi – О1 – …– О1 – Пm




б) Предположим, что на каждом j-том маршруте должно работать Xj автомобилей. Допустим, что каждый из i-тых грузополучателей (например, грузополучатели П1, П2,…,Пi и так далее) обслуживаются всеми маршрутами. Тогда общее среднее количество ездок в день к каждому получателю () может быть выражено суммой произведений количества автомобилей на каждом маршруте (Xj) на количество ездок в сутки () к i-тому получателю по j-тому маршруту
= (5)

1-й маршр. 2-й маршр. j-й маршр.
Этих уравнений будет столько, сколько потребителей грузов.

В этих уравнениях количество автомобилей на соответствующих маршрутах (Xj) неизвестно. Количество ездок в сутки к i-тому получателю по j-тому маршруту (aij) определяется по таблице 6 как сумма одинаковых сочетаний «ОX – Пi», соответствующих данному потребителю. Например, для потребителя 1: по маршруту 1 соответствующее сочетание будет «О1 – П1». Этих сочетаний в маршруте 1 содержится два (таблица 6). Следовательно, . Аналогично по маршруту 2 соответствующие сочетание также будут «О1 – П1». Они в маршруте 2 отсутствуют. Следовательно, a12 =0, и так далее.

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

Однако, уравнения (5) и (6) не отвечает начальному условию. В начальный момент времени при отсутствии автомобилей на линии () правая часть уравнений обращается в нуль. Но левая часть уравнения (5) уже задана уравнением (3) и не равна нулю. Для устранения этого противоречия введем в уравнение (5) дополнительные переменные с коэффициентами «1» перед , соответствующими номеру получателя. Остальные коэффициенты принимаем равными нулю. Так же поступим с уравнением (6), введя в него дополнительные переменные с коэффициентами «0».

Тогда математическая модель задачи может быть выражена системой линейных уравнений
(7)

и уравнением цели
(8)








в) Нахождение точного решения поставленной задачи заключается в решении системы уравнений (7) совместно с уравнением (8). По существу это решение уравнений с неизвестными и является трудоемкой задачей даже с применением ЭВМ.

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

Симплексная таблица показана на рисунке 11.

Заполним эту таблицу для исходного состояния системы, когда еще не начато движение по маршрутам.

Для этого:

- в столбце свободных членов проставляем значения свободных членов из системы уравнений (7);

- в основных строках дополнительных переменных для каждого Xj проставляем значения коэффициентов aij из системы уравнений (7);

где cj - коэффициент загрузки автомобилей на маршрутах (формула (6))
, (9)


Строка переменных
х








X1


X2


X3





Xj


?1


?2


?3








?m





?1













.





1


0


0


0


0


0


?2













..





0


1


0


0


0


0

?3









..



0

0

1

0

0

0











.















?m









..



0

0

0

0

0

1

zj-cj

0

-1

-1

-1




-1

0

0

0

0

0

0



Основные столбцы переменныхи.Количество столбцов

равно количеству маршрутов плюс количество получателей (j+m)

Основные строки дополнительных

переменных. Количество строк рав-

Индексная строка но количеству получателей – m

Столбец свободных членов



Столбец дополнительных переменных

Рисунок 11 – Симплексная таблица
В соответствии с начальными условиями коэффициенты при дополнительных переменных в уравнении (6) равны нулю. Стало быть, в соответствии с уравнением (9) для всех маршрутов.

Если принять коэффициенты загрузки автомобилей по всем маршрутам cj = 1, то
zj – cj = 0 – 1 = –1 (10)
для всех маршрутов. Проставляем их в индексной строке для основных переменных.


В то же время в соответствии с уравнением (8) коэффициенты при дополнительных переменных равны нулю. Проставляем их в таблице;

- заполняем основные строки дополнительных переменных в столбцах переменных в соответствии с системой уравнений (7).

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

Этап 2

а) Определяется ключевой столбец. Это столбец, у которого в индексной строке стоит отрицательное число с максимальным модулем. В начальный момент во всех столбцах проставлено одинаковое число: –1. Поэтому мы в праве взять любой столбец Xj в качестве ключевого. Но для упорядочения действий выбираем их по порядку и определяем ключевым столбец X1. Обводим его тонкой линией;

б) Определяем ключевую строку. Для этого свободные члены разделим на соответствующие коэффициенты ключевого столбца. Наименьшее частное от деления и определит ключевую строку.

Например, - ключевая строка – ?2. Обведем ключевую строку тонкой линией.

в) На пересечении ключевого столбца и ключевой строки находится ключевое число. Для приведенного примера оно равно .

г) Пересчитываем значения ключевой строки, деля их на ключевое число:
;;;;;;

д) Выводим из ключевой строки дополнительную переменную ?i(в приведенном примере – ?2). Вывод ее из таблицы указываем стрелкой. В дальнейшем заменяем ее основной переменной Xj ключевого столбца. В нашем случае – X1.

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


(11)
Значения в индексной строке, имеющие «0» в ключевой строке, не пересчитываются, так как их значения остаются без изменения. Действительно, например, для столбца , где выбранное для пересчета число равно нулю



Стало быть, в нашем случае пересчитываются только значения в столбцах свободных членов, X1, X2, X3, Xj и :

столбец свободных членов ,

cтолбец X1 ,
столбец X2 ,
столбец X3 ,
столбец Xj ,
столбец
ж) Строим новую симплексную таблицу 7 с измененными значениями коэффициентов в основных строках и индексной строке с заменой дополнительной переменной ?2 на основную переменную X2.


Таблица 7





X1


X2


X3




Xj


?1


?2


?3








?m




















.





1


0


0


0


0


0


X1





1







..





0





0


0


0


0

?3









..



0

0

1

0

0

0











.















?m









..



0

0

0

0

0

1

zj-cj



0










0



0

0

0

0
1   2   3   4   5   6   7   8   9   ...   13


Учебный материал
© bib.convdocs.org
При копировании укажите ссылку.
обратиться к администрации