Доклад на тему Оптимизация в планировании перевозок
Работа добавлена на сайт bukvasha.net: 2015-01-23Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
Федеральное агентство по образованию
Сибирская автомобильно-дорожная академия
(СибАДИ)
Кафедра «Организация перевозок и управления на транспорте»
Доклад
Тема: «Оптимизация в планировании на автомобильном транспорте»
Выполнил: Колосова Е.А.
21 ОПУТ
Научный руководитель Витвицкий Е.Е.
Омск-2006
Оптимизация расстояния перевозок грузов
Одним из важнейших факторов, оказывающих влияние на эффективность использования транспортных средств, является расстояние перевозки, от величины которого зависит количество транспортной работы.
Многочисленными исследовании доказано, что чем меньше будет выполняться транспортной продукции, измеряемой в тонно-километрах, тем лучше для народного хозяйства нашей страны. Это связано с тем, что сокращение транспортной работы сопровождается снижением транспортных затрат и уменьшение потребности в транспортных средствах. Поэтому перевозки грузов должны осуществляться по возможности на короткие (оптимальные) расстояния для всех отраслей народного хозяйства.
Большая часть перевозок грузов осуществляется по сложившейся сети дорог и улиц с конкретными условиями эксплуатации подвижного состава и организацией движения. Практически между двумя пунктами, расположенными на транспортной сети города, может быть «n» вариантов проезда, которым соответствуют определенные расстояния li ; скорости Vi и время ti (i=1,2,3...n).
Из теории известно, что максимальную производительность однотипного подвижного состава можно получить на том маршруте, где будут минимальные затраты времени. Однако критерий, по которому находят оптимальное решение, определяется не только затратами времени, а той целью, которую необходимо достигнуть при решении задачи оптимального варианта проезда. Наиболее часто в качестве критерия принимается минимум суммарного пробега, так как при одинаковых условиях движения на всех участках маршрута план, оптимальный по пробегу, будет оптимальным по затратам времени и стоимости.
Не применяя никаких вычислений, кратчайший путь между двумя пунктами можно выбрать в том случае, если они находятся в пределах видимости. Если же они достаточно удалены друг от друга, то возникают различные варианты передвижения, которые необходимо сравнить, чтобы выбрать наилучший.
Если перевозки выполняются на территории города, то, как правило, там насчитывается очень большое количество пунктов отправки и приема грузов. С целью уменьшения трудоемкости определения кротчайших расстояний, грузопотоков и построения транспортной сети используют способ, заключающийся в том, что вместо большого разнообразия конкретных пунктов устанавливают условные. Для этого разделяют весь город на определенное количество микрорайонов и все грузообразующие и грузопоглощающие пункты, расположенные в пределах данного микрорайона, условно считают расположенными в центре микрорайона. Этим приемом большое число пунктов заменяется небольшим количеством центров, и вместо огромного числа транспортных связей между пунктами рассматриваются связи между микрорайонами.
Границу микрорайона не должны пересекать естественные рубежи – реки, железные дороги и т.п. Дорожная сеть внутри микрорайона должна допускать подъезд к любому объекту без необходимости выезда за пределы микрорайона и иметь выход на основные магистрали.
Количество микрорайонов определяют исходя из того, что большое их число усложняет решение задачи, малое может привести к большому количеству объектов, транспортные связи которых не будут учтены. Ориентировочно количество микрорайонов можно устанавливать по численности населения – один микрорайон на 15 – 20 тысяч человек.
Но фактические расстояния в качестве показателя критерия оптимальности можно принимать в том случае, если дороги, связывающие пункты между собой, одной категории. Если дороги разные, то и затраты на дорогах также будут разными. Поэтому фактические расстояния необходимо скорректировать. Для каждой категории дороги в зависимости от величины затрат на километр пробега устанавливается коэффициент приведения. Для дороги первой категории коэффициент приведения К1=1, а для дороги второй категории
К11=З11/З1,
Где З11, З1 – затраты на километр пробега соответственно на дорогах второй и первой категории в рублях.
Величина общего пробега с грузом зависит от того, какой грузоподъемности транспортные средства будут применяться для выполнения перевозок, причем с уменьшением ее общий пробег будет возрастать. Это одна из причин, вызывающая несоответствие между величинами расчетной и фактической экономической эффективности от применения ЭММ в планировании перевозок грузов. Вполне понятно, что использование транспортных средств возможно большей грузоподъемности будет способствовать сокращению затрат на перевозки.
Определение рациональной грузоподъемности транспортных средств
Для обеспечения максимальной производительности транспортных средств необходимо, чтобы автомобили прибывали в погрузочно-разгрузочные пункты по расписанию согласно оптимальной интенсивности входящего потока. Каждый пункт погрузки или разгрузки, как известно, представляет собой систему массового обслуживания, для которых оптимальная интенсивность входящего потока автомобилей может быть найдена с помощью аналитических моделей или путем моделирования процесса обслуживания автомобилей в системе грузового пункта на основе метода статистических испытаний.
Имея достаточное количество подвижного состава, можно обеспечить прибытие автомобилей в соответствии с оптимальной интенсивностью, тем самым загрузить оборудование пункта, обслуживающее транспортные средства (весы, подъемники и т.п.), но это еще не означает, что будет обеспечен максимальный суточный завоз (вывоз) груза. Например, при доставке зерна на заготовительный пункт (элеватор) безразлично, какой грузоподъемности взвешивать автомобили, лишь бы они вмещались на площадку весов и не превышали их возможностей. Но чем меньшей грузоподъемности автомобиль будет занимать весы, тем меньше будет доставлено груза, хотя по времени оборудование может использоваться на 100%. Следовательно, для каждого грузового пункта необходимо применять транспортные средства, минимальная грузоподъемность которых
qgmin=Qmax/M3
где Qmax – максимальная суточная возможность переработки груза по возможностям погрузочного или разгрузочного пунктов, т;
M3 – количество автомобилезаездов, которое может обслужить пункт в течение суток:
M3=Тр*lопт,
где Тр – режим работы грузового пункта, ч;
lопт – оптимальная интенсивность входящего потока автомобилей, авт/ч.
qgmin= Qmax/ Тр*lопт
Таким образом, для вывоза (завоза) грузов на грузовые пункты необходимо выбирать подвижной состав грузоподъемностью qgi ≥ qgmin. Однако следует помнить, что транспортные средства движутся по разным дорогам, в том числе и по грунтовым, на которых могут использоваться автомобили, входящие в группу «Б». Следовательно, данное положение ограничивает максимальную грузоподъемность qgmах подвижного состава. Кроме того, максимальная грузоподъемность ограничивается возможностями разгрузочных и весовых устройств как по весу, так и по габаритам. А тогда грузоподъемность автомобиля выбирается в пределах
qgmin< qgi ≤ qgmах.
Применение транспортных средств грузоподъемностью, меньшей, чем qgmin, вызывает снижение количества доставляемого груза за плановое время. Обратный результат будет при использовании подвижного состава с грузоподъемностью, большей qgmin.
Применение подвижного состава грузоподъемностью qgi> qgmin способствует сокращению потребности в транспортных средствах и операций по их обслуживанию: взвешиванию, разгрузке, оформлению документов и др. Следовательно, возможно сокращение затрат на выполнение транспортного процесса. При практическом выборе автомобиля или автопоезда из имеющегося ряда (если грузоподъемность отличается от рациональной определенной по изложенному расчету) рекомендуется принимать автомобиль ближайшей большей грузоподъемности.
Оптимизация распределения подвижного состава по маршрутам перевозок грузов
В АТП далеко не всегда имеются в наличии транспортные средства, которые согласно изложенной методике выбора подвижного состава следует применять для перевозок грузов. Поэтому приходится решать задачу оптимального распределения по маршрутам имеющегося подвижного состава. Необходимость в решении задачи может возникать ежесуточно в связи с изменением условий эксплуатации или в зависимости от той цели, которую необходимо достичь.
Задача формулируется следующим образом. Имеется m типов подвижного состава в количествах a1, a2,...,am и n объектов, на которые требуется перевести Q1, Q2,..., Qn тонн грузов, причем любой тип имеющегося подвижного состава можно использовать для перевозки указанных грузов. Обозначим выработку i-го типа подвижного состава на j-м объекте через Wij, число подвижного состава этого типа, работающего на данном объекте (маршруте), через xij, стоимость перевозок 1 т груза через Сij и получаемую прибыль через Пij. Требуется составить план перевозок грузов xij при условии, что общая потребность в транспортных средствах для всех объектов равна их наличию или меньше его:
n
å xij ≤ ai, i=1...m
j=1
и на каждый объект должно быть заведено потребное количество груза
m
å xij Wij=Qij, j=1...n.
i=1
Переменные xij должны удовлетворять одному из критериев оптимизации:
суммарным затратам на перевозки
m n
З=å å Wij xij Сij ® min
i=1 j=1
суммарной прибыли
Сибирская автомобильно-дорожная академия
(СибАДИ)
Кафедра «Организация перевозок и управления на транспорте»
Доклад
Тема: «Оптимизация в планировании на автомобильном транспорте»
Выполнил: Колосова Е.А.
21 ОПУТ
Научный руководитель Витвицкий Е.Е.
Омск-2006
Оптимизация расстояния перевозок грузов
Одним из важнейших факторов, оказывающих влияние на эффективность использования транспортных средств, является расстояние перевозки, от величины которого зависит количество транспортной работы.
Многочисленными исследовании доказано, что чем меньше будет выполняться транспортной продукции, измеряемой в тонно-километрах, тем лучше для народного хозяйства нашей страны. Это связано с тем, что сокращение транспортной работы сопровождается снижением транспортных затрат и уменьшение потребности в транспортных средствах. Поэтому перевозки грузов должны осуществляться по возможности на короткие (оптимальные) расстояния для всех отраслей народного хозяйства.
Большая часть перевозок грузов осуществляется по сложившейся сети дорог и улиц с конкретными условиями эксплуатации подвижного состава и организацией движения. Практически между двумя пунктами, расположенными на транспортной сети города, может быть «n» вариантов проезда, которым соответствуют определенные расстояния li ; скорости Vi и время ti (i=1,2,3...n).
Из теории известно, что максимальную производительность однотипного подвижного состава можно получить на том маршруте, где будут минимальные затраты времени. Однако критерий, по которому находят оптимальное решение, определяется не только затратами времени, а той целью, которую необходимо достигнуть при решении задачи оптимального варианта проезда. Наиболее часто в качестве критерия принимается минимум суммарного пробега, так как при одинаковых условиях движения на всех участках маршрута план, оптимальный по пробегу, будет оптимальным по затратам времени и стоимости.
Не применяя никаких вычислений, кратчайший путь между двумя пунктами можно выбрать в том случае, если они находятся в пределах видимости. Если же они достаточно удалены друг от друга, то возникают различные варианты передвижения, которые необходимо сравнить, чтобы выбрать наилучший.
Если перевозки выполняются на территории города, то, как правило, там насчитывается очень большое количество пунктов отправки и приема грузов. С целью уменьшения трудоемкости определения кротчайших расстояний, грузопотоков и построения транспортной сети используют способ, заключающийся в том, что вместо большого разнообразия конкретных пунктов устанавливают условные. Для этого разделяют весь город на определенное количество микрорайонов и все грузообразующие и грузопоглощающие пункты, расположенные в пределах данного микрорайона, условно считают расположенными в центре микрорайона. Этим приемом большое число пунктов заменяется небольшим количеством центров, и вместо огромного числа транспортных связей между пунктами рассматриваются связи между микрорайонами.
Границу микрорайона не должны пересекать естественные рубежи – реки, железные дороги и т.п. Дорожная сеть внутри микрорайона должна допускать подъезд к любому объекту без необходимости выезда за пределы микрорайона и иметь выход на основные магистрали.
Количество микрорайонов определяют исходя из того, что большое их число усложняет решение задачи, малое может привести к большому количеству объектов, транспортные связи которых не будут учтены. Ориентировочно количество микрорайонов можно устанавливать по численности населения – один микрорайон на 15 – 20 тысяч человек.
Но фактические расстояния в качестве показателя критерия оптимальности можно принимать в том случае, если дороги, связывающие пункты между собой, одной категории. Если дороги разные, то и затраты на дорогах также будут разными. Поэтому фактические расстояния необходимо скорректировать. Для каждой категории дороги в зависимости от величины затрат на километр пробега устанавливается коэффициент приведения. Для дороги первой категории коэффициент приведения К1=1, а для дороги второй категории
К11=З11/З1,
Где З11, З1 – затраты на километр пробега соответственно на дорогах второй и первой категории в рублях.
Величина общего пробега с грузом зависит от того, какой грузоподъемности транспортные средства будут применяться для выполнения перевозок, причем с уменьшением ее общий пробег будет возрастать. Это одна из причин, вызывающая несоответствие между величинами расчетной и фактической экономической эффективности от применения ЭММ в планировании перевозок грузов. Вполне понятно, что использование транспортных средств возможно большей грузоподъемности будет способствовать сокращению затрат на перевозки.
Определение рациональной грузоподъемности транспортных средств
Для обеспечения максимальной производительности транспортных средств необходимо, чтобы автомобили прибывали в погрузочно-разгрузочные пункты по расписанию согласно оптимальной интенсивности входящего потока. Каждый пункт погрузки или разгрузки, как известно, представляет собой систему массового обслуживания, для которых оптимальная интенсивность входящего потока автомобилей может быть найдена с помощью аналитических моделей или путем моделирования процесса обслуживания автомобилей в системе грузового пункта на основе метода статистических испытаний.
Имея достаточное количество подвижного состава, можно обеспечить прибытие автомобилей в соответствии с оптимальной интенсивностью, тем самым загрузить оборудование пункта, обслуживающее транспортные средства (весы, подъемники и т.п.), но это еще не означает, что будет обеспечен максимальный суточный завоз (вывоз) груза. Например, при доставке зерна на заготовительный пункт (элеватор) безразлично, какой грузоподъемности взвешивать автомобили, лишь бы они вмещались на площадку весов и не превышали их возможностей. Но чем меньшей грузоподъемности автомобиль будет занимать весы, тем меньше будет доставлено груза, хотя по времени оборудование может использоваться на 100%. Следовательно, для каждого грузового пункта необходимо применять транспортные средства, минимальная грузоподъемность которых
qgmin=Qmax/M3
где Qmax – максимальная суточная возможность переработки груза по возможностям погрузочного или разгрузочного пунктов, т;
M3 – количество автомобилезаездов, которое может обслужить пункт в течение суток:
M3=Тр*lопт,
где Тр – режим работы грузового пункта, ч;
lопт – оптимальная интенсивность входящего потока автомобилей, авт/ч.
qgmin= Qmax/ Тр*lопт
Таким образом, для вывоза (завоза) грузов на грузовые пункты необходимо выбирать подвижной состав грузоподъемностью qgi ≥ qgmin. Однако следует помнить, что транспортные средства движутся по разным дорогам, в том числе и по грунтовым, на которых могут использоваться автомобили, входящие в группу «Б». Следовательно, данное положение ограничивает максимальную грузоподъемность qgmах подвижного состава. Кроме того, максимальная грузоподъемность ограничивается возможностями разгрузочных и весовых устройств как по весу, так и по габаритам. А тогда грузоподъемность автомобиля выбирается в пределах
qgmin< qgi ≤ qgmах.
Применение транспортных средств грузоподъемностью, меньшей, чем qgmin, вызывает снижение количества доставляемого груза за плановое время. Обратный результат будет при использовании подвижного состава с грузоподъемностью, большей qgmin.
Применение подвижного состава грузоподъемностью qgi> qgmin способствует сокращению потребности в транспортных средствах и операций по их обслуживанию: взвешиванию, разгрузке, оформлению документов и др. Следовательно, возможно сокращение затрат на выполнение транспортного процесса. При практическом выборе автомобиля или автопоезда из имеющегося ряда (если грузоподъемность отличается от рациональной определенной по изложенному расчету) рекомендуется принимать автомобиль ближайшей большей грузоподъемности.
Оптимизация распределения подвижного состава по маршрутам перевозок грузов
В АТП далеко не всегда имеются в наличии транспортные средства, которые согласно изложенной методике выбора подвижного состава следует применять для перевозок грузов. Поэтому приходится решать задачу оптимального распределения по маршрутам имеющегося подвижного состава. Необходимость в решении задачи может возникать ежесуточно в связи с изменением условий эксплуатации или в зависимости от той цели, которую необходимо достичь.
Задача формулируется следующим образом. Имеется m типов подвижного состава в количествах a1, a2,...,am и n объектов, на которые требуется перевести Q1, Q2,..., Qn тонн грузов, причем любой тип имеющегося подвижного состава можно использовать для перевозки указанных грузов. Обозначим выработку i-го типа подвижного состава на j-м объекте через Wij, число подвижного состава этого типа, работающего на данном объекте (маршруте), через xij, стоимость перевозок 1 т груза через Сij и получаемую прибыль через Пij. Требуется составить план перевозок грузов xij при условии, что общая потребность в транспортных средствах для всех объектов равна их наличию или меньше его:
n
å xij ≤ ai, i=1...m
j=1
и на каждый объект должно быть заведено потребное количество груза
m
å xij Wij=Qij, j=1...n.
i=1
Переменные xij должны удовлетворять одному из критериев оптимизации:
суммарным затратам на перевозки
m n
З=å å Wij xij Сij ® min
i=1 j=1
суммарной прибыли
m n
П=å å Wij xij Пij ® max
i=1 j=1
суммарному объему перевозок
m n
Q = å å Wij xij ® max.
i=1 j=1
Решение задачи по одному из указанных критериев зависит от конкретных условий эксплуатации. Если общая провозная способность автомобилей недостаточна, то решение ведется по критерию, обеспечивающему выполнение перевозок подвижным составом с минимальными провозными возможностями. В остальных случаях целесообразно минимизировать затраты на перевозки, используя для этого критерий по суммарным затратам на перевозки.
Рассмотрим пример решения одной из частных задач оптимизации распределения подвижного состава по маршрутам перевозки грузов, причем ограничимся случаем, где имеются всегда по два маршрута, вида груза и типа автомобилей.
Таблица 1 Исходная информация
Исходя из данных, составим систему неравенств, которая в математическом виде воспроизводит решаемую задачу:
х11+х21+х31+х41 ≤ 10
х12+х22+х23+х42 ≤ 15
14х11+15х12 ≤ 150
7х21+5х22 ≤ 100(1)
15х31+17х32 ≤ 200
9х41+9х42 ≤ 250
Так как целью решения является обеспечение максимального объема перевозок имеющимся парком подвижного состава, то условия оптимизации решения задачи записываются в виде:
Qmax=14х11+15х12+7х21+5х22+15х31+17х32+9х41+9х42. (2)
В уравнениях (1) и (2) xij – количество автомобилей i-го типа, работающих на j-м маршруте при перевозках соответствующего вида груза, но так как на каждом маршруте перевозятся по два вида груза, то это равносильно рассмотрению четырех маршрутов. Поэтому принята сквозная нумерация по j.
Представленная математическая формулировка задачи соответствует общей задаче линейного программирования, поэтому для ее решения следует применять универсальный метод, например симплексный.
При решении задач симплекс-методом все неравенства (1) необходимо обратить в равенства. Для этого введем свободные переменные х1, х2, …,х6 ≥ 0.
Тогда
х11+х21+х31+х41+х1=10
х12+х22+х23+х42 +х2=15
14х11+15х12+х3=150
7х21+5х22+х4= 100(3)
15х31+17х32 +х5=200
9х41+9х42+х6=250
Qmax=14х11+15х12+7х21+5х22+15х31+17х32+9х41+0х1+0х2+0х3+0х4+0х5+0х6 ® max. (4)
Свободные переменные х1 и х2 выражают количество неиспользованных автомобилей из числа имеющихся, а х3, …, х6 – объем неперевезённого груза. В целевую функцию они входят с коэффициентами, равными нулю.
Все данные полученных уравнений заносятся в специальную симплекс-таблицу (таблица 2).
Каждая строка в симплекс-таблице отражает по порядку все ранее написанные уравнения, а по столбцам таблицы располагаются коэффициенты, с которыми переменные (х11, х12, …, х6) входят в соответствующее уравнение. Если какая-либо переменная не входит в рассматриваемое уравнение, то в таблице для нее проставляется нуль. В индексной строке записываются коэффициенты при соответствующей переменной в выражении целевой функции с обратным знаком.
Алгоритм вычислений симплекс-методом состоит в следующем.
Шаг 1. Выбираем в индексной строке наибольшее отрицательное число. Ему соответствует ключевой столбец. В таблице 2 это столбец х32 с числом 17.
Шаг 2. Определяем ключевую строку. Для этого разделим числа столбца свободных членов на соответствующие им положительные числа ключевого столбца: 10/0 = ∞; 15/1 = 15; 150/0= ∞; 200/17 = 11,76; 250/0 = ∞. Из всех полученных частных выбираем наименьшее (200/17 = 11,76). Оно определяет ключевую строку.
На пересечении ключевой строки и ключевого столбца находится ключевое число (17).
Шаг 3. Переходим к построению следующей симплекс-таблицы, в которой в первую очередь заполняется главная строка. Главная строка располагается там, где в предыдущей симплекс-таблице находилась ключевая строка, а числа главной строки определяются путем деления чисел ключевой строки на ключевое число. Вместо прежнего переменного в столбце переменных записывается переменное соответствующего ключевого столбца. Поэтому для главной строки таблицы 3 в столбце переменных указано 11,76.
В том столбце, который в предыдущей таблице был ключевым, все клетки заполняются нулями, за исключением клетки, где находилось ключевое число. Там всегда будем иметь 1 по расчету чисел главной строки. Те столбцы, у которых в клетках ключевой строки (см. табл. 2) записаны нули, переписываются без изменений. Аналогично правило и для строк. Если в ключевом столбце строке соответствует нуль, то она переписывается в следующую таблицу без изменений.
Для остальных клеток (в столбце свободных членов клетка строки х2, х3, х2, х5, х2 и в индексной строке клетка столбца х32) определяются производные числа (Пр) по правилу:
Пр = Вч – КсКст/Кч,
где Вч – выбранное число;
Кс – соответствующее число в ключевой строке;
Кст – соответствующее число в ключевом столбце;
Кч – ключевое число.
Теперь известны все числа, и построение симплекс-таблицы (см. табл. 2) закончено. Так как в индексной строке еще сохранились отрицательные числа, то решение продолжается, повторяются все операции, описанные выше. Вычисления проводятся до той поры, пока в индексной строке одной из таблиц не окажутся числа больше или равные нулю. Опуская промежуточные решения, покажем сразу матрицу оптимального распределения (таблица 4).
В заключение можно отметить, что изложенным методом можно решать и другие задачи. Например, можно определить минимальное число автомобилей, необходимое для перевозки запланированного количества грузов. Для этого нужно отбросить ограничения по количеству автомобилей и ввести расчет по изложенной схеме до тех пор, пока не будет вывезен весь запланированный груз.
Исходная симплекс-таблица Таблица 2
П=å å Wij xij Пij ® max
i=1 j=1
суммарному объему перевозок
m n
Q = å å Wij xij ® max.
i=1 j=1
Решение задачи по одному из указанных критериев зависит от конкретных условий эксплуатации. Если общая провозная способность автомобилей недостаточна, то решение ведется по критерию, обеспечивающему выполнение перевозок подвижным составом с минимальными провозными возможностями. В остальных случаях целесообразно минимизировать затраты на перевозки, используя для этого критерий по суммарным затратам на перевозки.
Рассмотрим пример решения одной из частных задач оптимизации распределения подвижного состава по маршрутам перевозки грузов, причем ограничимся случаем, где имеются всегда по два маршрута, вида груза и типа автомобилей.
Таблица 1 Исходная информация
| Вид ресурса (автомобили) | Объем груза, перевезенного за смену одним автомобилем, т | Запас ресурсов (кол. автомобилей) | |||
| Груз 1-го вида | Груз 2-го вида | ||||
| Маршрут 1 | Маршрут 2 | Маршрут 3 | Маршрут 4 | ||
| q=3 | 14 | 7 | 15 | 9 | 10 |
| q=5 | 15 | 5 | 17 | 9 | 15 |
| Плановый объем перевозок, т | 150 | 100 | 200 | 250 | __ |
Исходя из данных, составим систему неравенств, которая в математическом виде воспроизводит решаемую задачу:
х11+х21+х31+х41 ≤ 10х12+х22+х23+х42 ≤ 15
14х11+15х12 ≤ 150
7х21+5х22 ≤ 100(1)
15х31+17х32 ≤ 200
9х41+9х42 ≤ 250
Так как целью решения является обеспечение максимального объема перевозок имеющимся парком подвижного состава, то условия оптимизации решения задачи записываются в виде:
Qmax=14х11+15х12+7х21+5х22+15х31+17х32+9х41+9х42. (2)
В уравнениях (1) и (2) xij – количество автомобилей i-го типа, работающих на j-м маршруте при перевозках соответствующего вида груза, но так как на каждом маршруте перевозятся по два вида груза, то это равносильно рассмотрению четырех маршрутов. Поэтому принята сквозная нумерация по j.
Представленная математическая формулировка задачи соответствует общей задаче линейного программирования, поэтому для ее решения следует применять универсальный метод, например симплексный.
При решении задач симплекс-методом все неравенства (1) необходимо обратить в равенства. Для этого введем свободные переменные х1, х2, …,х6 ≥ 0.
Тогда
х11+х21+х31+х41+х1=10
х12+х22+х23+х42 +х2=1514х11+15х12+х3=150
7х21+5х22+х4= 100(3)
15х31+17х32 +х5=200
9х41+9х42+х6=250
Qmax=14х11+15х12+7х21+5х22+15х31+17х32+9х41+0х1+0х2+0х3+0х4+0х5+0х6 ® max. (4)
Свободные переменные х1 и х2 выражают количество неиспользованных автомобилей из числа имеющихся, а х3, …, х6 – объем неперевезённого груза. В целевую функцию они входят с коэффициентами, равными нулю.
Все данные полученных уравнений заносятся в специальную симплекс-таблицу (таблица 2).
Каждая строка в симплекс-таблице отражает по порядку все ранее написанные уравнения, а по столбцам таблицы располагаются коэффициенты, с которыми переменные (х11, х12, …, х6) входят в соответствующее уравнение. Если какая-либо переменная не входит в рассматриваемое уравнение, то в таблице для нее проставляется нуль. В индексной строке записываются коэффициенты при соответствующей переменной в выражении целевой функции с обратным знаком.
Алгоритм вычислений симплекс-методом состоит в следующем.
Шаг 1. Выбираем в индексной строке наибольшее отрицательное число. Ему соответствует ключевой столбец. В таблице 2 это столбец х32 с числом 17.
Шаг 2. Определяем ключевую строку. Для этого разделим числа столбца свободных членов на соответствующие им положительные числа ключевого столбца: 10/0 = ∞; 15/1 = 15; 150/0= ∞; 200/17 = 11,76; 250/0 = ∞. Из всех полученных частных выбираем наименьшее (200/17 = 11,76). Оно определяет ключевую строку.
На пересечении ключевой строки и ключевого столбца находится ключевое число (17).
Шаг 3. Переходим к построению следующей симплекс-таблицы, в которой в первую очередь заполняется главная строка. Главная строка располагается там, где в предыдущей симплекс-таблице находилась ключевая строка, а числа главной строки определяются путем деления чисел ключевой строки на ключевое число. Вместо прежнего переменного в столбце переменных записывается переменное соответствующего ключевого столбца. Поэтому для главной строки таблицы 3 в столбце переменных указано 11,76.
В том столбце, который в предыдущей таблице был ключевым, все клетки заполняются нулями, за исключением клетки, где находилось ключевое число. Там всегда будем иметь 1 по расчету чисел главной строки. Те столбцы, у которых в клетках ключевой строки (см. табл. 2) записаны нули, переписываются без изменений. Аналогично правило и для строк. Если в ключевом столбце строке соответствует нуль, то она переписывается в следующую таблицу без изменений.
Для остальных клеток (в столбце свободных членов клетка строки х2, х3, х2, х5, х2 и в индексной строке клетка столбца х32) определяются производные числа (Пр) по правилу:
Пр = Вч – КсКст/Кч,
где Вч – выбранное число;
Кс – соответствующее число в ключевой строке;
Кст – соответствующее число в ключевом столбце;
Кч – ключевое число.
Теперь известны все числа, и построение симплекс-таблицы (см. табл. 2) закончено. Так как в индексной строке еще сохранились отрицательные числа, то решение продолжается, повторяются все операции, описанные выше. Вычисления проводятся до той поры, пока в индексной строке одной из таблиц не окажутся числа больше или равные нулю. Опуская промежуточные решения, покажем сразу матрицу оптимального распределения (таблица 4).
В заключение можно отметить, что изложенным методом можно решать и другие задачи. Например, можно определить минимальное число автомобилей, необходимое для перевозки запланированного количества грузов. Для этого нужно отбросить ограничения по количеству автомобилей и ввести расчет по изложенной схеме до тех пор, пока не будет вывезен весь запланированный груз.
Исходная симплекс-таблица Таблица 2
| Столбец переменных | Столбец свободных членов | Строка переменных | |||||||||||||
| Х11 | Х12 | Х21 | Х22 | Х31 | Х32 | Х41 | Х42 | Х1 | Х2 | Х3 | Х4 | Х5 | Х6 | ||
| Х1 | 10 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| Х2 | 15 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| Х3 | 150 | 14 | 15 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| Х4 | 100 | 0 | 0 | 7 | 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| Х5 | 200 | 0 | 0 | 0 | 0 | 15 | 17 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
| Х6 | 250 | 0 | 0 | 0 | 0 | 0 | 0 | 9 | 9 | 0 | 0 | 0 | 0 | 0 | 1 |
| Индексная строка | ___ | -14 | -15 | -7 | -5 | -15 | -17 | -9 | -9 | 0 | 0 | 0 | 0 | 0 | 0 |
Промежуточная симплекс-таблица Таблица 3
| Столбец переменных | Столбец свободных членов | Строка переменных | |||||||||||||
| Х11 | Х12 | Х21 | Х22 | Х31 | Х32 | Х41 | Х42 | Х1 | Х2 | Х3 | Х4 | Х5 | Х6 | ||
| Х1 | 10 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
| Х2 | 3,24 | 0 | 1 | 0 | 1 | -0,88 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | -0,06 | 0 |
| Х3 | 150 | 14 | 15 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
| Х4 | 100 | 0 | 0 | 7 | 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| Х32 | 11,76 | 0 | 0 | 0 | 0 | 0,88 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0,06 | 0 |
| Х6 | 250 | 0 | 0 | 0 | 0 | 0 | 0 | 9 | 9 | 0 | 0 | 0 | 0 | 0 | 1 |
| Индексная строка | __ | -14 | -15 | -7 | -5 | 0 | 0 | -9 | -9 | 0 | 0 | 0 | 0 | 0 | 0 |
| Столбец переменных | Столбец свободных членов | Строка переменных | |||||||||||||
| Х11 | Х12 | Х21 | Х22 | Х31 | Х32 | Х41 | Х42 | Х1 | Х2 | Х3 | Х4 | Х5 | Х6 | ||
| Х41 | 2,76 | 0 | 0 | 1 | 1,07 | 0,06 | 0 | 1 | 1,07 | 1 | 1,07 | -0,07 | 0 | -0,064 | 0 |
| Х12 | 3,24 | 0 | 1 | 0 | 1 | -0,82 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | -0,06 | 0 |
| Х11 | 7,25 | 1 | 0 | 0 | -1,07 | 0,94 | 0 | 0 | -1,07 | 0 | -1,07 | 0,07 | 0 | 0,064 | 0 |
| Х4 | 100 | 0 | 0 | 7 | 5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| Х32 | 11,76 | 0 | 0 | 0 | 0 | 0,88 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0,06 | 0 |
| Х6 | 225,16 | 0 | 0 | -9 | -9,63 | -0,54 | 0 | 9 | -0,63 | -9 | -9,63 | -0,63 | 0 | 0,576 | 1 |
| Индексная строка | __ | 0 | 0 | 2 | 34,63 | 0,54 | 0 | 0 | 0,63 | 9 | 9,63 | 0,37 | 0 | 0,424 | 0 |
Литература
1. В.И. Николин, Е.Е. Витвицкий, С.М. Мочалин, Н.И. Ланьков «Основы теории автотранспортных систем ( грузовые автомобильные перевозки )»
2. В.И. Николин «Автотранспортный процесс и оптимизация его элементов»
1. В.И. Николин, Е.Е. Витвицкий, С.М. Мочалин, Н.И. Ланьков «Основы теории автотранспортных систем ( грузовые автомобильные перевозки )»
2. В.И. Николин «Автотранспортный процесс и оптимизация его элементов»
