Этап 2. Определение портов с избытком и недостатком тоннажа
А) Составление таблицы корреспондирующих тоннаже потоков, (так называемой «косой» таблицы тоннаже потоков) (табл. 2.3).
При составлении табл. 2.3 во втором столбце по вертикали перечисляются все порты (отправления и назначения), которые должны быть обслужены судами флота судоходной компании при освоении заданных грузопотоков в соответствии с планом перевозок. Причем порты (погрузки и выгрузки) в таблице должны располагаться в соответствии с их географической ротацией.
В шапке табл. 2.3. все порты перечисляются по горизонтали в том же порядке, в котором они расположены по вертикали во втором столбце таблицы.
Затем в ячейки табл. 2.3 заносится информация о направлении и величине тоннаже потоков.
Далее по строкам и столбцам табл. 2.3 определяется сумма величин отправляемого и прибывающего тоннажа. Соответствующая информация о величине отправляемого тоннажа заносится в ячейки последнего столбца табл. 2.3, а информация о величине прибывающего в порт тоннажа отражается в ячейках последней строки табл. 2.3.
Таблица 2.3
«Косая» таблица тоннажепотоков
| № | … | … | … | … | Всего отправлено ( ), тыс. тонн | |||||
| № | Порты отправления и назначения (названия) | … | … | … | … | |||||
| 1. | ||||||||||
| 2. | ||||||||||
| … | … … | … | ||||||||
| … | … | … | … | |||||||
| … | … | … | ||||||||
| … | … … | … | … | |||||||
| … | ||||||||||
| Всего прибыло ( ), тыс. тонн | … | … | … | … |
Образец составления табл. 2.3 приведен в табл. 2.4.
Таблица 2.4
Образец заполнения «косой» таблицы тоннаже потоков
| № | Порт | Одесса | Ильичёвск | Порт-Саид | Стамбул | Тулон | Акаба | Всего отправлено ( ), тыс. тонн |
| 1. | Одесса | 8,609 | 20,000 | 18,874 | 38,874 | |||
| 2. | Ильичёвск | -49,669 | 49,669 | 49,669 | ||||
| 3. | Порт-Саид | 26,954 | -26,954 | 26,954 | ||||
| 4. | Стамбул | 20,530 | 29,139 | 20,530 | ||||
| 5. | Тулон | 20,000 | 0,000 | |||||
| 6. | Акаба | 18,874 | 0,000 | |||||
| Всего прибыло ( ), тыс. тонн | 47,483 | 0,000 | 0,000 | 49,669 | 20,000 | 18,874 |
Б) Дополнение полученной «косой» таблицы тоннажепотоков (табл. 2.3) данными об обеспечении каждого порта тоннажем
Для этого в диагональные клетки «косой» таблицы тоннажепотоков (табл. 2.3) записывается разность между числами, которые показывают прибытие тоннажа и его отправление по каждому порту.
Знак «-»(табл. 2.3) показывает, что в порту не хватает тоннажа, а знак «+» говорит об его избытке.
Этап 3. Определение оптимального плана перехода тоннажа в балласте
В КП постановка задачи формулируется каждым студентом самостоятельно в зависимости от полученных исходных данных.
Постановка задачи в общем виде. Имеются портов с избытком («запасом» «+») тоннажа, т. е. портов, из которых тоннаж отправляется в балласте. И портов с недостатком («потребностью» «-») тоннажа, т. е. портов назначения тоннажа, следующего в балласте.
Необходимо найти такой план распределения тоннажа, при котором общее количество тоннаже-миль в балласте будет наименьшим.
А) Проверка выполнения условия баланса
В рассматриваемой транспортной задаче должно выполняться условие баланса, т. е. сумма «запасов» должна равняться сумме «потребностей»:
| , | (2.4) |
Таким образом, следует определить общий «запас» тоннажа, идущего в балласте:
, (2.5)
который должен быть равен его суммарной «потребности» в соответствующих портах:
. (2.6)
Б) Обозначение переменных рассматриваемой задачи (табл. 2.5).
Таблица 2.5
Переменные задачи
| Порты с избытком тоннажа | Порты с недостатком тоннажа | |||||
| … | … | |||||
| … | ||||||
| … | ||||||
Исходя из условия данной задачи, представляем экономико-математическую модель линейного программирования в общем виде.
В) Построение экономико-математической модели задачи минимизации тоннаже-миль в балласте.
| ; | (2.7) |
| , | (2.8) |
| ; | |
| , | (2.9) |
| ; | |
| , | (2.10) |
| ; , |
где - параметр управления, который отражает величину тоннажа, идущего в балласте из - го порта с избытком тоннажа в - ый порт с его недостатком;
- расстояние между портами и , мили (табл. 2.6);
- «запасы» тоннажа в - ом порту;
- «потребности» в тоннаже в - ом порту.
Целевая функция (2.7) минимизирует общую протяженность балластных переходов судна.
Группа ограничений (2.8) говорит о том, что все «запасы» тоннажа в портах с его избытком должны быть исчерпаны.
Система уравнений (2.9) отражает то, что «потребности» всех портов с недостатком тоннажа должны быть удовлетворены.
Выражение (2.10) – это условие неотрицательности переменных, которое указывает на то, что параметр управления не должен быть отрицательной величиной, т. е. по любому маршруту либо следует тоннаж, либо нет.
Количество переменных в задаче должно соответствовать следующему выражению: .
Количество базисных переменных - выражению: .
Количество ограничений - выражению: .
Условие задачи минимизации тоннаже-миль в балласте представляем в виде табл. 2.6.
Таблица 2.6
Расстояния между портами с избытком и недостатком тоннажа
| Порты с избытком тоннажа | Порты с недостатком тоннажа | «Запасы» тоннажа ( ), тыс. тонн | |||||
| … | … | ||||||
| … | … | ||||||
| … | … | ||||||
| «Потребность» в тоннаже ( ), тыс. тонн | … | … |
Г) Представление экономико-математической модели задачи минимизации тоннаже-миль в балласте в координатной форме.
На основании исходных данных записывается экономико-математическую модель сформулированной задачи в координатной форме.
Д) Реализация задачи минимизации тоннаже-миль в балласте.
Данную задачу можно решить симплекс-методом. Однако особенности ТЗ дают возможность для её решения применять более простые и рациональные методы, чем симплекс-метод.
Специальные методы решения ТЗ основаны на той же идее, что и симплекс-метод: из предыдущего базиса выводят определенный вектор, а на его место вводят другой вектор. Как и в симплекс-методе, решение ТЗ специальными методами заключается в целенаправленном переборе и проверке на оптимальность опорных планов задачи, для чего нужно, прежде всего, найти исходный опорный план.
Специальный алгоритм решения транспортной задачи первоначально разрабатывался для ручных вычислений как метод, дающий «быстрое» решение. Сегодня мощная компьютерная техника совместно с соответствующим программным обеспечением позволяет решать транспортные задачи любой размерности как задачи линейного программирования. В частности, программа TORA, LINGO, а также средство EXCEL ПОИСК РЕШЕНИЯ использует формат транспортной задачи только для экранного представления данных, выполняя все вычисления на основе обычного симплекс – метода. С другой стороны, рассматриваемые далее алгоритмы решения транспортной задачи, кроме исторического интереса, предлагают взглянуть изнутри на то, как можно использовать теоретические отношения двойственности для получения практических результатов.
В КП данную задачу следует решать с помощью средства «Поиск решения» программы электронных таблиц EXCEL. Инструкция для работы со средством «Поиск решения» программы электронных таблиц EXCEL приведена в []. Результаты оптимизации плана балластных переходов представляются в табл. 2.8.
Таблица 2.8
Оптимальный план балластных переходов судна
| Порт с избытком тоннажа | Порт с недостатком тоннажа | «Запасы» тоннажа ( ), тыс. тонн | |||||
| … | … | ||||||
| … | … | ||||||
| … | … | ||||||
| «Потребность» в тоннаже ( ), тонн | … | … |
После табл. 2.8 следует привести значение целевой функции: тыс. тоннаже-миль.
В приложении А курсового проекта следует представить соответствующий «Отчет о результатах» решения задачи минимизации балластных переходов.
Этап 4. Построение оптимальных схем движения тоннажа
С целью построения оптимальных схем движения тоннажа, для начала, необходимо перенести оптимальный план балластных переходов (табл. 2.8) в «косую» таблицу корреспонденции груженных тоннажепотоков (табл. 2.3, 2.4). В результате получается табл. 2.9.
В табл. 2.9 балластные переходы обводятся рамкой.
При построении схем движения тоннажа следует соблюдать следующие непременные условия:
1. Схемы движения должны быть замкнутыми, т. е. суда должны возвратиться в тот порт, из которого они вышли.
2. Каждый порт может входить в схему только один раз. Исключение составляет начальный порт, который одновременно является и конечным.
3. Схем не должна начинаться с балластного перехода.
4. В схеме не должно быть подряд два или более балластных переходов.
5. Схемы должны быть уравновешены по тоннажу, т. е. все участки схемы должны характеризоваться одинаковой величиной тоннажа.
Таблица 2.9
Совмещение оптимального плана балластных переходов и
косой таблицы корреспонденции тоннаже потоков
| № | Порты | Одесса | Ильичёвск | Порт-Саид | Стамбул | Тулон | Акаба | Всего отправлено ( ), тыс. тонн |
| 1. | Одесса | 8,609 0 | 20,000 11,921 0 | 18,874 0 | 38,874 | |||
| 2. | Ильичёвск | 49,669 20,530 8,609 0 | 49,669 | |||||
| 3. | Порт-Саид | 26,954 8,079 0 | 26,954 | |||||
| 4. | Стамбул | 20,530 8,609 0 | 29,139 0 | 20,530 | ||||
| 5. | Тулон | 12,921 0 | 8,079 0 | 0,000 | ||||
| 6. | Акаба | 18,874 0 | 0,000 | |||||
| Всего прибыло ( ), тыс. тонн | 47,483 | 0,000 | 0,000 | 49,669 | 20,000 | 18,874 |
Построение схем движения осуществляется в следующей последовательности:
построение простых схем движения (т. е. между двумя портами) с грузом на обоих участках, т. е. схем уравновешенных по груженному тоннажу;
построение схем движения, содержащих балластные переходы.
Числовой пример методики постороения оптимальных схем движения приведен в [].
Следует отметить, что схемы движения определяются однозначно только в том случае, если оптимальный план балластных переходов единственный.