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

Задача №1. Определение оптимальной структуры флота судоходной компании.

Постановка задачи. Судоходная компания (СК) занимается перевозками грузов. В ее составе имеется типов судов, число судов в каждом типе .

В соответствии с долгосрочными договорами объемы перевозок на n направлениях возрастут, и их годовые объемы составят тыс. т. Имеющихся судов недостаточно для освоения перевозок.

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

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

Для решения задачи используется такой подход. Из сетки типоразмеров судов отбираются подходящие по назначению типы судов. При отборе судов также учитываются глубины в портах захода, оснащенность их перегрузочным оборудованием, гидрометеорологические условия на трассе и в портах и др. Эти суда будем называть претендентами на пополнение флота СК. Суда - претенденты могут быть отобраны и из других источников (данные о продаже судов, сдаче их в аренду и т.п.).

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

Математическая модель задачи в общем виде такова:

(6)

, (7)

, (8)

, (9)

(10)

где - число судов i-ого типа на j-ом направлении,

- прибыль одного судна i-ого типа на j-ом направлении, тыс. долл.,

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

Экономический смысл математической модели (6)-(10):

(6) – ЦФ отражает годовую прибыль судов всех типов на всех направлениях, которую нужно максимизировать.

(7) – ограничение по обязательному освоению перевозок на всех направлениях.

(8) – ограничение по обязательному использованию действующих типов судов.

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

(10) – условие неотрицательности переменных.

Число судов, подлежащих постройке (покупке) - , определяется соотношением:

.

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

- целое .

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

Математическая модель задачи будет иметь вид:

(11)

, (12)

, (13)

, (14)

(15)

(16)

Задача №2. Выбор вида транспорта для доставки грузов.

Постановка задачи. В m пунктах отправления А₁, А₂, …, А_i, …, A_m имеется однородный груз в количестве а₁, а₂, …, a_i, …, a_m (ед.). Груз нужно доставить в n пунктов назначения В₁, В₂, …, В_j, …, B_n, потребности которых составляют b₁, b₂, …, b_j, …, b_n (ед.). Груз может перевозиться t видами транспорта Т₁, Т₂, …, T_p, …, T_t.

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

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

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

Математическая модель задачи имеет вид:

(17)

(18)

(19)

(20)

(17) – ЦФ отражает расходы на все перевозки, которые нужно минимизировать.

(18) – ограничение по обязательному вывозу груза от всех отправителей.

(19) – ограничение по удовлетворению потребностей всех получателей.

(20) – условие неотрицательности переменных.

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

,

где b_j – пропускная способность j-ого порта.

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

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

. (21)

В задаче могут рассматриваться перевозки разнородных грузов. Обозначим род груза текущим индексом k, .

Математическая модель (17)-(20) примет вид:

(22)

(23)

(24)

(25)

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

Задача №3. Выбор маршрута доставки грузов.

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

В m пунктах имеется однородный груз, который нужно доставить n получателям. Доставка груза осуществляется в смешанном сообщении (морская часть пути и наземная, где есть возможность выбора вида транспорта для доставки: железнодорожный, автомобильный).

Перевалка груза может осуществляться в портах. Известна стоимость доставки 1 т груза из каждого иностранного порта в каждый порт перевалки (морская часть пути) и из каждого порта перевалки получателям каждым видом транспорта.

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

Введем обозначения:

i – порт отправления груза,

- порт перевалки, ;

j – пункт назначения, ;

p – вид транспорта, ;

a_i – количество груза в порту отправления i;

b_j – потребность в пункте назначения j;

- стоимость перевозки 1 т груза от i-ого поставщика к порту перевалки , долл./т;

- стоимость перевозки 1 т груза от порта перевалки к j-ому получателю транспортом вида р, долл./т.

Введем 2 группы переменных:

- количество груза, которое может быть перевезено из i-ого порта отправления в порт перевалки , тыс. т;

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

Математическая модель задачи имеет вид:

(26)

, (27)

, (28)

, (29)

(30)

(26) – ЦФ отражает расходы на перевозку груза по всему пути его доставки, которые нужно минимизировать;

(27) – ограничение по вывозу груза из портов отправления;

(28) – ограничение по удовлетворению потребностей получателей;

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

(30) – условие неотрицательности переменных.