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

Задача состоит в том, чтобы наилучшим образом перераспределить образовавшийся в портах избыток тоннажа на порты с его недостатком. Для решения используются данные из табл. определение портов с избытком и недостатком тоннажа. Формулировка задачи сводится к следующему. Имеются m портов с избытком тоннажа и n с недостатком. Расстояния между портами – lij, количество тоннажа в портах с избытком ai, (i=1,m); количество потребного тоннажа в портах с недостатком bj, (j=1,n). Необходимо найти такой оптимизационный план распределения тоннажа (xij=Dчij), при котором пробег балластных судов был бы минимальным. Сформулированная задача относится к числу специальных задач линейного программирования – транспортных. Математическая модель транспортной задачи (далее ТЗ) выглядит следующим образом.

Целевая функция: Z = SLijXij-min. Где Xij – тоннаж перемещающийся по заданным портам. При этом очевидно, что из каждого порта должно уйти в балласте все кол-во тоннажа, не обеспеченного грузом Ai во все порты, где есть груз, не обеспеченный тоннажем. Поэтому первое ограничение SXij=Аi, так же кол-во тоннажа, прибывшего в балласте в каждый j-й порт, должно быть равно потребностям этого порта в тоннаже SXij=Вj. В модель должно быть включено условие неотрицательности, так как отрицательные значения балластных переходов не имеют эксплутационного смысла Xij≥0. Далее строится матрица транспортной задачи на минимум балластных пробегов. По вертикали порты с избытком тоннажа, по горизонтали – с недостатком. В итоговой строке и столбце указывается количество тоннажа (+-).

В Матрице располагается не только информация из модели задачи, но и искомый план перемещения тоннажа: каждая клетка основного блока таблицы характеризует передвижение балласта из порта i в порт j и соответствует одной из m x n переменных плана X= (xij). Расстояния между портами в морских милях являются элементами xij матрицы и располагаются в правом верхнем углу каждой клетки. Транспортная задача разрешима, т.е. для нее существует хотя бы один план и целевая функция ограничена, если для нее выполняется условие баланса: SAi = SBi. Это условие обеспечивается предыдущими расчетами, ТЗ считается сбалансированной, а ее модель – закрытого типа. Методов решения таких задач может быть несколько. Один из них – метод потен-

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

значения xij при построении плана перевозок. Полученный опорный план должен удовлетворять условию такому, что число заполненных клеток на единицу меньше суммы числа портов с избытком и недостатком тоннажа, т.е. m+n-1. Такие опорные планы ТЗ,

которые содержат в точности m+n-1 ненулевых клеток, называют невырожденными. Опорный план будет вырожденным, если число ненулевыхклеток в нем меньше m+n-1. В этом случае вводится дополнительная клетка, где xij = 0, так чтобы выполнялось условие m+n-1 для опорного плана.Чтобы воспользоваться методом потенциалов для решения ТЗ, необходимо присвоить дополнительные переменные: строкам – ui и столбцам – vj. Ui – берется произвольно, это максимальное расстояние в табл. Необходимое и достаточное условие оптимальности плана ТЗ:

– для свободных клеток плана:Vj – Ui ≤ lij

– для всех занятых клеток плана:Vj – Ui = lij

Условия (5.1) и (5.2) принято называть условиями потенциальности плана, а признак оптимальности более кратко можно формулировать так:опорный план ТЗ оптимален, если он потенциален. Если план не оптимален, то ту клетку которую мы улучшаем ставим (+) это будет одна величина контура, остальные величины контура содержат заполненные клетки и стороны должны пересекаться под прямыми углами. Далее знаки чередуются. Из заполненных клеток со знаком (-) выбираем миним. значение, которое в последствие передвигаем по контуру. И далее процедура выполняется пока не будет найден оптим. план. Далее считается целевая ф-ия для первого и последнего плана (значение в каждой заполненной клетке*расстояние).

Алгоритм решения задачи методом потенциалов.

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

1. Составляется исходный опорный план одним из известных методов (например: минимального элемента).

2. Строится схема m+n-1 и вводятся доп. переменные ui и vj кот. определяются на основе системы равенств (5.2).

3. План исследуется на оптимальность с помощью системы неравенств (5.1).

Если построенный план на предыдущем шаге не оптимален, то применяется повторяющийся шаг, который состоит из трех операций.

1. План улучшается с помощью пересчета процедуры по циклу. Цикл строится для той свободной клетки, в которой расхождение максимальное.

2. Плану ставится в соответствие новая система потенциалов vj, ui на основе соотношений (5.2).

3. План исследуется на оптимальность с использованием соотношений (5.1).

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

14. Постановка и математическая модель задачи оптимальной расстановки флота. Характеристика методов решения задачи по расстановке флота. (у нас только алгоритм построения схемы движения) + кратко 15 вопрос

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

Постановка задачи расстановки флота.

Имеется m-типов судов, кот.должны обеспечить перевозки на заданных направлениях с грузооборотом Q1, Q2…..Qn

Pij – провозоспособность с i-го типа судна на j-ом направлениях. Расходы по использованию судна на j-ом направлении Cij, руб.

Если обозначить долю экспл-го периода, затрачиваемого i-м типом судна для работы на j-ом направлении через tij, то задача расстановки флота сводится к определению плана распределения бюджета времени судов для освоения задачи грузопотока на каждом направлении.

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

∑^m_i=1∑ⁿ_j=1 tij * Cij→min

Ограничения: ∑ⁿ_j=1 tij ≤1, общее суммарное время работы каждого судна на заданных направлениях ограничено эксплуатационным периодом и Тэ = 1

∑^m_i=1 Pij* tij = Qj, запланированный объем перевозок на каждой линии должен быть выполнен

tij ≥0, если в качестве критерия оптимальности взять прибыль или доход судна от перевозки, то целевая функция должна стремиться к максимуму

Задача распределения флота по видам плавания и формам судоходства на практике решается опытным путем или расчетным методом. Для решения задачи опытным путем идет предположением, что распределение флота на группы трампового судоходства, линейного, по конкретным линиям и направлениям произошло. Распределение судов опытном методом производится с учетом совокупных результатов анализа (по грузоподъемности, финансовым показателям и отбора судов по технико-эксплуатационным ограничительным признакам). Но это метод приближенный и предварительный, и носит косвенный характер, обоснованный на ориентировочные результаты, достигнутые на отдельных линиях и направлениях. Решение экономико-математических методов ведется по следующей схеме: предварительно распределяется имеющийся флот по технико- эксплуатационным ограничительным признакам. Принимается решения о закреплении отдельных типов судов на определенных линиях и направлениях.

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

программирования (метод потенциалов), приближенные методы (метод почти

оптимальных планов)

15. Алгоритм решения задачи расстановки флота методом «почти оптимальных планов»

В основе этого метода лежит сравнение двух производительностей судов и схем движения (Mij и qi). Метод предполагает что в первую очередь для работы на заданной схеме выбираются суда с максимальной приведенной производительностью Mijпривед, а расчет бюджета времени судна производится по фактической производительности Mijфакт.

1) подготовка исх данных для расстановки флота

qi = Σ Qi / Tэ, т/сут (суточная производительность по схеме движения)

Mij = Σ Qijp /tijp, т/сут (производительность тоннажа по схемам движения, где Σ Qijp – колво груза которое вывозит jтип судна по iтой схеме движения.

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

Лямбдаi(Лi) = ΣMimax / ΣMi где ΣMi – общая производительность судов всех типов на схеме движения; ΣMimax– база соизмерения, соответствующая наибольшей величине

производительности судов всех типов на схеме движения.

В левом нижнем углу клеток записывается приведенная производительность, которая определяется по формуле: Mijпривед = Mij* Лi

Где Лi – коэффициент соизмерения трудоемкости.

В основе метода «почти оптимальных планов» лежит следующий принцип: суда для работы по схемам движения отбираются по максимальной величине приведенной производительности. Бюджет времени работы судов j -го типа на i -той схеме движения (в долях от единицы Tэ=1) определяется путем сравнения фактической производительности судов j -го типа на i -той схеме движения с суточным объемом перевозок на данной схеме – qi.

Если qi > mij, то это означает, что весь заданный период (Тэ=1) судно данного типа будет работать на этой схеме движения, а остаток объема перевозок (дельта qi) должен осваиваться судами другого типа: дельта qi = qi - mij

Если qi < mij, тогда доля бюджета времени работы судов данного типа на этой схеме движения определяется из отношения: tij = qi / Mij

а неиспользованная доля бюджетного времени судна (или судов данного типа)

дельта t = 1 - tиспользуется для выполнения работы на других схемах движения.

При дальнейшем использовании ранее задействованных судов их производительность корректируется (т.е. уменьшается от первоначальной величины): Mij = Mij* дельта tij и так же сравнивается с объемом работ по схеме движения.

Процесс сравнения qi и m ij продолжается до тех пор, пока не будет освоен весь объем работы по схемам движения qi. Результатом расстановки является закрепление судов за линиями и расчет времени занятости судов на них в сутках. Для того чтобы перейти от долей к суткам, необходимо дельта t × Tэ (Tэ = 92 дня). Для удобства результаты расчетов можно свести в табл. 2. Время работы последнего судна может быть меньше 92 дней из-за

отсутствия работы в заданном периоде.

16. Рейсовое планирование. Нормативная и справочная база рейсового планирования. Расчет продолжительности рейса судна и экономических показателей рейса в каботаже и загранплавании.

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

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

- по исполнителям транспортного процесса (суда и порты);

- по грузам (номенклатура и количество);

- по времени (время рейса, ходовое, стояночное);

- по валютно-финансовым показателям.

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

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

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

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

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

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

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

Оперативная информация (распоряжения самого диспетчера, данные от агентов, судов и пр.) – самая динамичная часть информационного потока.

Инструкция «Положение о рейсовом планировании и оценке работы морских транспортных судов» содержит порядок составления и выдачи рейсовых заданий, содержание рейсовых заданий, расчет и оценку выполнения планов перевозок.

Рейсовый план график (РПГ) представляет собой календарный плановый график работы судна в рейсе, содержит плановые задания по ресурсам плановой работы и использования судна в рейсе.

Элементы РПГ:

- значение чистой грузоподъемности на данный рейс;

- наименование, количество груза, порт погрузки/выгрузки, дата начала рейса;

- продолжительность рейса и его составляющих;

- доходы в инвалюте;

- расходы в инвалюте и национальной валюте;

- финансовый результат в нац-ой валюте;

- ЧВВ/тнж.сут. μ_В=ЧВВ/Д_Ч*t_Р ($/тн.сут.) =ΔF/Д_Ч*t_р (грв/тн.сут.)

Корректировка плановых значений РПГ допускается в исключительных случаях:

1. При изменении месячных или квартальных планов.

2. В случае форс-мажорных обстоятельств.

Оценка выполнения РПГ производится сопоставлением отчетных показателей с плановыми по законченным рейсам. Для оценки могут приниматься экспл-ые показатели (прямые и обратные), количественные показатели (т, т-м, время рейса), а также экономические показатели (ЧВВ, прибыль, доходы) и качественные (μ_В, μ_ПР, уровень доходности и др.).

Tp = tx+tст, tx = L/V, tст = ∑Qi / Mвi, ходовое основное и дополнительное (прохождение каналов, швартовка..)

D = ∑Qi*fi, R = Rp+Rсб, Rp = tx*kx + tcт*кст, где Rp – эксплуатационные расходы, кх и кст – это суточное содержание судов на ходу и на стоянке, руб/сут

Сборы за вход и выход и начисляются по валовой регистровой вместимости.

В каботаже: 1)показатель удельной доходности у = F/tp, руб/cут., у = F/Дч*tp, руб/тоннаже-cутВ загран: 1) интенсивность валютных поступлений Минв = ЧВВ/ tp, инв/cут,Минв = ЧВВ/ Дч*tp, инв/тоннаже-cут

2)показатель валютной эффективности В = Чвв/ Rруб