Разработка оптимального плана расстановки флота по линиям

3








СОДЕРЖАНИЕ



ВВЕДЕНИЕ.	3

1 АНАЛИЗ ИСХОДНЫХ ДАННЫХ И ОПРЕДЕЛЕНИЕ МКТЕМАТИЧЕСКИХ МЕТОДОВ РЕШЕНИЯ ПОСТАВЛЕННОЙ ЗАДАЧИ……………………………………………………………………………5

	2 ОПРЕДЕЛЕНИЕ ЛИНИЙ ДВИЖЕНИЯ СУДОВ.	7

	2.1 Постановка математической модели задачи	7

	2.2 Формирование линий движения судов	8

3 ОПРЕДЕЛЕНИЕ ПРОДОЛЖИТЕЛЬНОСТИ ОЖИДАНИЯ ГРУЗОВОЙ ОБРАБОТКИ СУДОВ	13

		3.1	Одноканальная СМО с бесконечной очередью	13

		3.2	Многоканальная СМО с неограниченной очередью	15

		3.3	Расчет времени ожидания грузовой обработки судов	16

4 РАЗРАБОТКА ОПТИМАЛЬНОГО ПЛАНА РАССТАНОВКИ ФЛОТА ПО ЛИНИЯМ	22

		4.1	Формулирование математической модели задачи	22

		4.2	Формирование состава исходных данных для решения математической модели задачи	26

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

ЗАКЛЮЧЕНИЕ	35

БИБЛИОГРАФИЧЕСКИЙ СПИСОК	37


ВВЕДЕНИЕ



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

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

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

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

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

			сформировать линии движения судов;

			определить продолжительность ожидания грузовой обработки судов;

			разработать оптимальный план расстановки флота по линиям;

			проанализировать полученные результаты решения задачи.

Объектом исследования курсовой работы стала оптимизация работы флота по направлениям. Предметом исследования является разработка оптимального плана расстановки флота по линиям.

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










1 АНАЛИЗ ИСХОДНЫХ ДАННЫХ И ОПРЕДЕЛЕНИЕ МАТЕМАТИЧЕСКИХ МЕТОДОВ РЕШЕНИЯ ПОСТАВЛЕННОЙ ЗАДАЧИ

 

1.1 Определение способа решения задачи 

В основе задания лежит следующая схема водных путей (рис.1.1):



А

Б

В

Г

Д

К

М

Л

Е

Н

П

С

.

.

.

.

.

.

.

.

.

.

.

.

.

Р













Рисунок 1.1. Схема водных путей

Из портов А, Б, Е за навигацию необходимо отправить соответственно 611 тыс. тонн, 452 тыс. тонн, 766 тыс. тонн груза. В пункты назначения Л, М, Н, П, Р необходимо доставить соответственно 349 тыс. тонн, 197 тыс. тонн, 661 тыс. тонн, 90 тыс.тонн, 583 тыс. тонн груза.

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

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

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

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

	

	






2 ОПРЕДЕЛЕНИЕ ЛИНИЙ ДВИЖЕНИЯ СУДОВ



2.1 Постановка математической модели задачи

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

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

Целевая функция имеет вид:

,                                          (2.1)

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

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

Существует система ограничений:

Сумма всех перевозок, стоящих в первой строке матрицы Х, должна равняться запасам первого поставщика, сумма перевозок во второй строке матрицы Х – запасам второго поставщика и т.д.:



Это означает, что запасы поставщиков вывозятся полностью.

Суммы перевозок, стоящих в каждом столбце матрицы Х, должны быть равны запросам потребителей:



Это означает, что запросы потребителей удовлетворяются полностью.

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

		  .

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



2.2 Формирование линий движения судов

Из портов А, Б, Е за навигацию необходимо отправить соответственно 611 тыс. тонн, 452 тыс. тонн, 766 тыс. тонн груза. В пункты назначения Л, М, Н, П, Р необходимо доставить соответственно 349 тыс. тонн, 197 тыс. тонн, 661 тыс. тонн, 90 тыс.тонн, 583 тыс. тонн груза.

Введем переменные в матрицу перевозок:



Построим матрицу расстояний:



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

АЛ = АБ + БВ + ВК + КЛ = 381+491+83+76 = 1031 км,

АМ = АБ + БВ + ВК + КМ = 381+491+83+327 = 1282 км,

АН = АБ + БВ + ВК +КЛ + ЛН = 381+491+83+76+75 = 1106 км,

АП = АБ + БВ + ВК +КЛ + ЛП = 381+491+83+76+392 = 1423 км,

АР = АБ + БВ + ВК +КЛ + ЛП + ПР = 381+491+83+76+392+220 = 1643 км,

БЛ = БВ + ВК + КЛ = 491+83+76 = 650 км,

БМ = БВ + ВК + КМ = 491+83+327 = 901 км,

БН = БВ + ВК +КЛ + ЛН = 491+83+76+75 = 725 км,

БП = БВ + ВК +КЛ + ЛП = 491+83+76+392 = 1042 км,

БР = БВ + ВК +КЛ + ЛП + ПР = 491+83+76+392+220 = 1262 км,

ЕЛ = ЕН + НЛ = 473+75 = 548 км,

ЕМ = ЕН +НЛ + ЛК + КМ = 473+75+76+327 = 951 км,

ЕН = ЕН = 473 км,

ЕП = ЕН + НЛ + ЛП = 473+75+392 = 940 км,

ЕР = ЕН + НЛ + ЛП + ПР = 473+75+392+220 = 1160 км,



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









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



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

Исходные данные можно оформить в виде следующей таблице:

Таблица 2.1 – Исходные данные о запасах и запросах груза

             ПН

ПО       

Л

349

М

197

Н

661

П

90

Р

583



А

611

1031



1282

1106

1423

1643

611

Б

452

650



901

725

1042

1262

452

Е

766

548



951

473

940

1160

766

Ф

51

0



0

0

0

0

51



349

197

661

90

583





Строим первый опорный план методом Минимальных расстояний.

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

ПО        ПН

Л

349

М

197

Н

661

П

90

Р

583



А

611

1031



1282



1106



1423

79

1643

532

611

Б

452

650

244

901

197

725



1042

11

1262

452

Е

766 

548

105

951

473

661

940



1160



766

Ф

51

0



0

0

0

0

51

51



349

197

661

90

583





Считаем себестоимость данного плана по формуле 2.1:



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

Проверяя оптимальность данного плана, используют метод потенциалов.

Вводим потенциалы, т.е. платежи:

£i – платеж поставщика,

– платеж за перевозку единицы груза потребителя,

 – псевдостоимость, которая определяется по формуле:

=£i+                                               (2.2)

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



Для расчета псевдостоимости  проверим количество базисных клеток по формуле:

R = m+n-1                                             (2.3)

где R – количество базисных клеток,

m – количество строк с перевозками,

n – количество столбцов с перевозками.

R = 4+5-1 = 8 – базисных клеток, значит можно дальше заполнять новую таблицу по следующим принципам:

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

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

£А всегда равно нулю.

Рассчитываем остальные платежи и псевдостоимости (по формуле 2.2).

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

ПО        ПН

Л

349

М

197

Н

661

П

90

Р

583

£i 

А

611

1031       1031



1282       1282



956         1106



1423       1423

79

1643       1643

532

0

Б

452

650           650

244

901           901

197

575           725



1042       1042

11

1262       1262

-381

Е

766

548           548

105

799           951

473          473

661

940           940



1160       1160



-483

Ф

51

-612             0



-361             0

-687             0

-220             0

0                   0

51

-1643



1031

1282

956

1423

1643



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

Таблица 2.4 – План перевозок (тыс. тонн)

Линии перевозок

Количество груза

АП

79

АР

532

БЛ

244

БМ

197

БП

11

ЕЛ

105

ЕН

661

Себестоимость данного плана равна 1704,24 тыс. руб. Не хватает 51 тыс. тонн груза, поэтому необходимо искать дополнительного поставщика.


3 ОПРЕДЕЛЕНИЕ ПРОДОЛЖИТЕЛЬНОСТИ ОЖИДАНИЯ ГРУЗОВОЙ ОБРАБОТКИ СУДОВ



	Существуют некоторые факторы, которые могут вызвать скопление судов в акватории порта и привести к ожиданию начала их обработки:

	- поступление судов в порты происходит через определенные промежутки времени, 

	- обработка судов в портах сопряжена с определенной продолжительностью их обслуживания.

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

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

	- многоканальные системы массового обслуживания с неограниченной очередью (для портов имеющих два причала и более).

	

	3.1 Одноканальная СМО с бесконечной очередью

	СМО содержит один обслуживающий канал. Если он свободный, то подошедшее судно сразу начинают обслуживать, если занят, то судно встает в очередь.

	Возможные состояния:

	S0 – система свободна (причал свободен);

	S1 – канал занят, очереди нет;

	S2 – канал занят, в очереди одно судно;

	S3 – канал занят, в очереди два судна и т.д.

	СМО характеризуется некоторыми показателями:

	1)– интенсивность поступления судов, определяющаяся по формуле:

	,                                                    (3.1)

	где tобсл – средняя длительность интервала поступления судов, час;

	2)  – интенсивность обслуживания, определяющаяся по формуле:

	,                                                     (3.2)

	где tобсл – средняя продолжительность времени грузовой обработки судов в портах, час;

	Р0, Р1, Р2, Р3 … – предельные вероятности (у каждого состояния есть свои вероятности), которые вычисляются по следующим формулам:

	,                                                 (3.3)

	где - приведенная интенсивность, которая определяется по формуле:

	;                                                 (3.4)

	          ;                                               (3.5)

	;                                              (3.6)

	 и т.д.                                         (3.7)

				Lоч – среднее число заявок в очереди вычисляют по формуле:

				;                                                (3.8)

				Точ – среднее время пребывания заявки в очереди определяют по формуле:

				;                                                 (3.9)

				Lсист – среднее число заявок в системе вычисляют по формуле:

;                                             (3.10)

				

				Тсист – среднее время пребывания заявки в системе (судна в порту) определяем по формуле:

				;                                           (3.11)

	

	

	3.2 Многоканальная СМО с неограниченной очередью

	СМО содержит m-обслуживающих каналов (порт имеет один или более причалов).

	Если в момент поступления заявки имеется свободный канал, то он немедленно приступает к обслуживанию поступившего требования. Если заявка застала состояние: «все каналы заняты», то она встает в очередь и ожидает начало обслуживания.

	Возможные состояния:

	S0 – система свободна;

	S1 – в системе одна заявка, очереди нет;

	S2 – в системе две заявки, очереди нет;

	S3 – в системе три заявки, очереди нет;

	…

	Sn – в системе n заявок, очереди нет;

	Sn+1 – в системе n+1 заявок, в очереди одна заявка и т.д.

	Многоканальная СМО характеризуется такими же показателями как и одноканальная СМО:

	1)– интенсивность поступления судов (по формуле 3.1);

	2)  – интенсивность обслуживания (по формуле 3.2);

	3) Р0, Р1, Р2, Р3 … - предельные вероятности (у каждого состояния есть свои вероятности), которые вычисляются по следующим формулам:

	,                       (3.12)

	где - приведенная интенсивность (по формуле 3.4).

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

	;                                                 (3.5)

	;                                              (3.13)

	;                                              (3.14)

	…

	;                                               (3.15)

	А дальше начинается очередь:

	;                                           (3.16)

	 и т.д.                                     (3.17)

				Lоч – среднее число заявок в очереди вычисляют по формуле:

				;                                          (3.18)

				Точ – среднее время пребывания заявки в очереди определяют по формуле:

				;                                               (3.19)

				Nзан – среднее число занятых каналов(причалов) находят по формуле:

				;                                              (3.20)

				Lсист – среднее число заявок в системе вычисляют по формуле:

				;                                       (3.21)

				Тсист – среднее время пребывания заявки в системе (судна в порту) определяем по формуле:

	;                                      (3.22)

	

	3.3 Расчет времени ожидания грузовой обработки судов

	Рассмотрим первый порт отправления – порт А. Он имеет 5 причалов (см. Характеристики портов), следовательно относится к многоканальной СМО.

	Найдем интенсивность поступления и обслуживания судов по формулам 3.1, 3.2 соответственно для порта А. tпост = 40 часов, а tобсл = 30 часов.

	Следовательно – интенсивность заявок в единицу времени;

	 – интенсивность обслуживания. 

	Аналогично просчитываем все интенсивности поступления и обслуживания для портов Е, М, Н, П, Р (работающие по многоканальной СМО, т.к. имеют 2 и более причала) и заносим результаты в таблицу 3.1.

	Таблица 3.1 – Результатыи  

Порты

Интенсивность поступления судов в единицу времени, 

Порты

Интенсивность обслуживания судов, 

А

0,025

А

0,033

Е

0,111

Е

0,125

М

0,040

М

0,047

Н

0,022

Н

0,040

П

0,020

П

0,027

Р

0,026

Р

0,028

	

	Рассчитаем нагрузку системы (по формуле 3.4) и вероятности состояний для порта А (по формулам 3.12, 3.5, 3.13-3.17):

	;

	;

	;

	;

	;

	;

	.

	Дальше началась очередь:

	;

	.

	Аналогично просчитываем все вероятности для портов Е, М, Н, П, Р (в очереди до 5 судов) и занесем полученные результаты в следующую таблицу 3.2.

Таблица 3.2 – Нагрузка системы 

Порты



Р0

Р1

Р2

Р3

Р4

Р5

Р6

Р7

А

0,757

0,469

0,355

0,134

0,033

0,006

0,0009

0,0001

0,00002

Е

0,888

0,390

0,346

0,153

0,045

0,013

0,003

0,001

0,0003

М

0,851

0,351

0,298

0,145

0,018

0,023

0,011

0,004

0,001

Н

0,550

0,523

0,287

0,079

0,021

0,005

0,001

0,0004

0,0001

П

0,740

0,461

0,341

0,126

0,031

0,007

0,001

0,0004

0,0001

Р

0,928

0,394

0,365

0,169

0,052

0,012

0,002

0,0004

0,00007



Далее рассчитаем среднее число заявок в очереди, среднее время пребывание заявки в очереди, среднее число занятых каналов, среднее число заявок в системе и среднее время пребывания заявки в системе по формулам 3.18-3.22 соответственно.

				;

				;

				;

				;

	.

	Аналогично просчитываем эти же показатели для портов Е, М, Н, П, Р и занесем результаты в таблицу 3.3.

Таблица 3.3 – Показатели работы порта

Порты

Lоч

Точ

Nзан 

Lсист

Тсист

А-5

0,004

0,121

0,757

0,761

30,121

Е-3

0,054

0,432

0,888

0,942

8,432

М-2

0,163

3,468

0,851

1,014

24,468

Н-2

0,041

1,025

0,55

0,591

26,025

П-3

0,027

1,000

0,740

0,767

38,000

Р-5

0,015

0,535

0,928

0,943

35,535

	

	Рассмотрим второй порт отправления – порт Б. Он имеет 1 причал (см. Характеристики портов), следовательно, относится к одноканальной СМО.

	Найдем интенсивность поступления и обслуживания судов по формулам 3.1, 3.2 соответственно для порта Б. tпост = 14 часов, а tобсл = 4 часа.

	Следовательно – интенсивность заявок в единицу времени;

	 – интенсивность обслуживания. 

	Аналогично просчитываем интенсивности поступления и обслуживания для порта Л (работающего по одноканальной СМО, т.к. имеет тоже 1 причал) и заносим результаты в таблицу 3.4.

	Таблица 3.4 – Результатыи  

Порты

Интенсивность поступления судов, 

Порты

Интенсивность обслуживания судов, 

Б

0,071

Б

0,250

Л

0,025

Л

0,062

	

	Рассчитаем нагрузку системы и вероятности состояний для порта Б (по формулам 3.3-3.7):

	;

	;

	;

	;

	;

	;

	;

	.

	Аналогично просчитываем все вероятности для порта Л (в очереди 5 судов) и занесем результаты в таблицу 3.5.

Таблица 3.5 – Нагрузка системы

Порты



Р0

Р1

Р2

Р3

Р4

Р5

Р6

Б

0,284

0,716

0,203

0,057

0,016

0,004

0,001

0,0003

Л

0,403

0,597

0,240

0,096

0,039

0,015

0,006

0,002



Далее рассчитаем среднее число заявок в очереди, среднее время пребывание заявки в очереди, среднее число заявок в системе и среднее время пребывания заявки в системе по формулам 3.18-3.22 соответственно.

				;

				;

;

				;

	Аналогично просчитываем среднее число заявок в очереди, среднее время пребывание заявки в очереди, среднее число заявок в системе и среднее время пребывания заявки в системе для порт Л и заносим результаты в таблицу 3.6.

Таблица 3.6 – Показатели работы порта

Порты

Lоч

Точ

Lсист

Тсист

Б-1

0,112

0,448

0,396

1.584

Л-1

0,272

4,387

0,675

10,887



Таким образом, рассчитав все показатели системы массового обслуживания и занеся их в соответствующие таблицы, можно увидеть характеристики портов отправления А, Б, Е и назначения Л, М, Н, П, Р.






4 РАЗРАБОТКА ОПТИМАЛЬНОГО ПЛАНА РАССТАНОВКИ ФЛОТА ПО ЛИНИЯМ



4.1 Формулирование математической модели задачи

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

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

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

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

Задача разработки оптимального плана использования флота формируется как обобщенная транспортная задача и решается методом Фогеля.

В качестве критерия оптимальности принимается минимум эксплуатационных расходов.

Целевая функция имеет следующий вид:

,                                              (4.1)

где  – эксплуатационные расходы по судну -ого типа при работе на -ой линии, тыс. руб. за навигацию;

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

Существует система ограничений:

, ,

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

- объем перевозок на -ой линии, тыс. тонн;

, 

где - количество судов -ого типа;

, 

Эксплуатационные расходы по судну -ого типа при работе на -ой линии за навигацию определяются по формуле (в тыс. руб.):

                                                    ;                                              (4.2)

где  – эксплуатационные расходы за круговой рейс по судну -ого типа на -ой линии, тыс. руб.;

 – эксплуатационный период (навигационный), сутки; ; 

– продолжительность кругового рейса судна -ого типа при работе на -ой линии, сутки. 

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

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

	                                     ;                                  (4.3)

	где   – себестоимость содержания судна -ого типа на ходу, руб./сут;

	– себестоимость содержания судна -ого типа на стоянке, руб./сут;

 – время хода судна -ого типа на -ой линии за круговой рейс, сутки;

 – время стоянки судна -ого типа на -ой линии за круговой рейс, сутки.

Продолжительность кругового рейса судна -ого типа при работе на -ой линии определяется по формуле:

                               ,                                          (4.4)

где – время хода судна -ого типа на -ой линии на участке , сутки;

 – время стоянки судна -ого типа на -ой линии в портах погрузки и разгрузки, сутки.

Тогда время хода судна определяется по формуле:                                        

                 ;                                      (4.5)

где –  дальность пробега с грузом на участке  -ого направления, км;

 – дальность пробега порожнем на участке  -ого направления, км;

– техническая скорость движения судна -ого типа с грузом на участке , км/час;

 – техническая скорость движения судна -ого типа порожнем на участке , км/час.

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

                                             ;                                                  (4.6)

	где  – расчетная скорость движения судна -ого типа, км/час;

  – скорость течения, км/час;

	                                               .                                                 (4.7)

Время стоянки судна -ого типа на -ой линии в портах погрузки и разгрузки определяется по формуле:

.                                       (4.8)

Провозная способность судна -ого типа на -ой линии за эксплуатационный период (в тыс. тонн за навигацию) определяется по формуле:

    ,                                               (4.9)

	где – грузоподъемность судна -ого типа.

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







4.2 Формирование состава исходных данных для решения математической модели задачи

Рассмотрим судно типа «Беломорск» на линии АП. Рассчитаем время хода судна типа «Беломорск» на линии АП (по формуле 4.5). Разобьем для удобства вычислений линию АП на участки: АБ+БВ+ВК+КЛ+ЛП – по течению и ПЛ+ЛК+КВ+ВБ+БА – против течения.



Таким же образом находим время хода судна типа «Беломорск» на линиях АР, БЛ, БМ, БП, ЕН, ЕЛ. Для судов типа «1810», «576», «781» на линиях АП, АР, БЛ, БМ, БП, ЕН, ЕЛ вычисляем время хода аналогично и заносим результаты в таблицу 4.1:

Таблица 4.1 – Время хода -ого типа судна на -ой линии за круговой рейс, сутки 



АП

АР

БЛ

БМ

БП

ЕН

ЕЛ

Беломорск

5,147

5,908

2,346

3,357

3,766

1,711

1,981

1810

4,530

5,232

2,066

2,932

3,315

1,506

1,744

576

5,643

6,558

2,571

3,704

4,128

1,877

2,173

781

4,894

5,687

2,231

3,180

3,581

1,627

1,883



Дальше необходимо рассчитать время стоянки судна типа «Беломорск» на лини АП за круговой рейс. Оно складывается из среднего времен пребывания судна в портах А и П (по формуле 4.8):



Таким же образом находим время стоянки судна типа «Беломорск» на линиях АР, БЛ, БМ, БП, ЕН, ЕЛ. Для судов типа «1810», «576», «781» на линиях АП, АР, БЛ, БМ, БП, ЕН, ЕЛ вычисляем время стоянки аналогично и заносим результаты в таблицу 4.2:

Таблица 4.2 – Время стоянки -ого типа судна на -ой линии за круговой рейс, сутки



АП

АР

БЛ

БМ

БП

ЕН

ЕЛ

Беломорск

2,838

2,735

0,453

1,085

1,649

1,435

0,804

1810

2,838

2,735

0,453

1,085

1,649

1,435

0,804

576

2,838

2,735

0,453

1,085

1,649

1,435

0,804

781

2,838

2,735

0,453

1,085

1,649

1,435

0,804



Определив время хода и стоянки -ого типа судна на -ой линии можно вычислить продолжительность кругового рейса -ого типа судна на -ой линии.

Найдем продолжительность кругового рейса судна типа «Беломорск» на линии АП (по формуле 4.4):





Таким же образом находим продолжительность кругового рейса судна типа «Беломорск» на линиях АР, БЛ, БМ, БП, ЕН, ЕЛ. Для судов типа «1810», «576», «781» на линиях АП, АР, БЛ, БМ, БП, ЕН, ЕЛ вычисляем продолжительность кругового рейса аналогично и заносим результаты в таблицу 4.3:









Таблица 4.3 – Продолжительность кругового рейса -ого типа судна на -ой линии, сутки



АП

АР

БЛ

БМ

БП

ЕН

ЕЛ

Беломорск

7,985

8,643

2,799

4,442

5,415

3,146

2,785

1810

7,368

7,967

2,519

4,017

4,964

2,941

2,548

576

8,481

9,293

3,024

4,789

5,777

3,312

2,977

781

7,732

8,422

2,684

4,265

5,23

3,062

2,687



Далее можно определить эксплуатационные расходы за круговой рейс по судну -ого типа судна на -ой линии, зная себестоимости содержания судна на ходу и на стоянке (из условия). Рассчитаем эксплуатационные расходы за круговой рейс по судну типа «Беломорск» на линии АП (по формуле 4.3):



Таким же образом находим эксплуатационные расходы за круговой рейс судна типа «Беломорск» на линиях АР, БЛ, БМ, БП, ЕН, ЕЛ. Для судов типа «1810», «576», «781» на линиях АП, АР, БЛ, БМ, БП, ЕН, ЕЛ вычисляем эксплуатационные расходы за круговой рейс аналогично и заносим результаты в таблицу 4.4:

Таблица 4.4 – Эксплуатационные расходы за круговой рейс по судну -ого типа судна на -ой линии, тыс. руб.



АП

АР

БЛ

БМ

БП

ЕН

ЕЛ

Беломорск

6,865

7,535

2,574

3,972

4,741

2,606

2,452

1810

8,851

9,691

3,212

4,992

6,058

3,424

3,124

576

9,212

10,210

3,458

5,362

6,363

3,496

3,293

781

10,821

11,932

3,974

6,165

7,430

4,157

3,835



Найдя эксплуатационные расходы за рейс можно определить эксплуатационные расходы по судну -ого типа судна на -ой линии за навигацию. Вычислим эксплуатационные расходы за навигацию для судна типа «Беломорск» на линии АП (по формуле 4.2):



Таким же образом находим эксплуатационные расходы за навигацию судна типа «Беломорск» на линиях АР, БЛ, БМ, БП, ЕН, ЕЛ. Для судов типа «1810», «576», «781» на линиях АП, АР, БЛ, БМ, БП, ЕН, ЕЛ вычисляем эксплуатационные расходы за навигацию аналогично и заносим результаты в таблицу 4.5:

Таблица 4.5 – Эксплуатационные расходы за навигацию по судну -ого типа судна на -ой линии, тыс. руб.



АП

АР

БЛ

БМ

БП

ЕН

ЕЛ

Беломорск

171,94

174,36

183,92

178,83

175,10

165,67

176,08

1810

240,25

243,27

255,02

248,54

244,07

232,84

245,21

576

217,23

219,73

228,70

223,92

220,28

211,11

221,22

781

281,10

284,55

297,32

290,29

285,33

272,72

286,64



Далее необходимо определить провозную способность по судну -ого типа судна на -ой линии за эксплуатационный период за навигацию. Найдем провозную способность для судна типа «Беломорск» на линии АП, зная эксплуатационный период и грузоподъемность судов в тоннах (из условия) по формуле 4.9:



Таким же образом находим провозную способность судна типа «Беломорск» на линиях АР, БЛ, БМ, БП, ЕН, ЕЛ. Для судов типа «1810», «576», «781» на линиях АП, АР, БЛ, БМ, БП, ЕН, ЕЛ вычисляем провозную способность аналогично и заносим результаты в таблицу 4.6:

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



АП

АР

БЛ

БМ

БП

ЕН

ЕЛ

Беломорск

25,04

23,14

71,45

45,02

36,93

63,57

71,81

1810

46,14

42,67

134,97

84,64

68,49

115,60

133,43

576

47,16

43,04

132,27

83,52

69,24

120,77

134,36

781

51,73

47,49

149,03

93,78

76,48

130,63

148,86



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

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

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

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

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

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

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

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

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

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

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

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

,                                           (4.10)

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

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

, 

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

, 

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



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

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

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

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

Линии

Типы

Судов

Кол-во судов

АП

79

АР

532

БЛ

244

БМ

197



БП

11



ЕН

105

ЕЛ

661

Столбцы разности

Бел-ск

6

25,04

1,45

23,14

4,55

71,45

45,02

36,93

63,57

71,81

0,36

0,36

26,79

8,09

11,89

1,9

23,14

1810

4

46,14



42,67



134,97

1,81

84,64

2,19

68,49



115,60



133,43

1,54

1,54

48,79

16,15

22,35

3,47

42,67

576

7

47,16

0,91

43,04



132,27



83,52

0,14

69,24

0,16

120,77

0,87

134,36

4,92

2,09

2,09

50,84

14,28

22,08

4,12

43,04

781

10

51,73



47,49

8,99

149,03



93,78



76,48



130,63



148,86

















Строки разности

1,02

0,37

2,7

1,12

0,75

5,17

0,93





1,02

0,37

2,7

1,12

0,75

F

0,93





1,02

0,37

F

1,12

0,75



0,93





1,02

0,37



1,12

0,75



F





1,02

0,37



F

0,75









1,02

0,37





F









F

0,37

















F















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









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



АП

79

АР

532

БЛ

244

БМ

197

БП

11

ЕЛ

105

ЕН

661

Бел-ск

6

                      171,94

1,45

25,04

                      174,36

4,55

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

0,91

47,16

                      219,73



43,04

                      228,70



132,27

                          223,92

0,14

83,52

                    220,28

0,16

69,24

                          211,11

0,87

120,77

                      221,22

4,92

134,36

781

10

                      281,10



51,73

                      284,55

8,99

47,49

                      297,32



149,03

                          290,29



93,78

                    285,33



76,48

                          272,72



130,63

                      286,64



148,86



Таблица 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 тыс. руб..












ЗАКЛЮЧЕНИЕ



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

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

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

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

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




БИБЛИОГРАФИЧЕСКИЙ СПИСОК



1 Бакаев В.Г. Эксплуатация морского флота. – М.: Транспорт, 1965. – 560с.

2 Бутов А.С., Легостаев В.А. Планирование работы флота и портов. – М.: Транспорт, 1988. – 174с.

3 Вентцель Е.С., Овчаров Л.А. Теория случайных процессов и ее инженерные приложения, 3- е изд., перераб. и доп. – М.: Академия, 2003. – 432с.

3 Замков О.О., Толстопятенко А.В., Черемных Ю.Н. Математические методы в экономике: Учебник /Под ред. А.В. Сидоровича. – М.: Дело и сервис, 2004. – 368с.

4 Нестеров Е.П. Транспортные задачи линейного программирования. – М.: Транспорт, 1971. – 216с.

5 Павлова Т.Н., Ракова О.А. Линейное программирование. – М.: Наука, 2002. – 289с.

6 Просветов Г.И. Математические методы в логистике: задачи и решения: учебно-практическое пособие. – 2-е изд., доп. – М.: Альфа-Пресс, 2008. – 304с.

7 Шапкин А.С. Математические методы и модели исследования операций. – М.: Дашков и К, 2004. – 395с.

8 Шелобаев С.И. Математические методы и модели в экономике, финансах, бизнесе: Учебное пособие для вузов. – М.: ЮНИТИ-ДАНА, 2001. – 367с.

		9 Хачатрян С.Р. Прикладные методы математического моделирования экономических систем: Науч.-метод. пособие. – М.: Экзамен, 2002. – 268с.