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

Задача №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) – условие неотрицательности переменных.

Вопросы по теме 5:

1. Для решения каких экономических задач может быть использован аппарат ЛП?

2. Запишите экономико-математическую модель общей задачи ЛП.

3. В чем отличие стандартной задачи ЛП от канонической?

4. Что называют допустимым, оптимальным решениями задачи ЛП?

5. Сформулируйте постановку задачи определения оптимальной структуры флота судоходной компании. Какой критерий оптимальности используется? Что является параметрами управления? Запишите математическую модель задачи.

6. Что понимается под структурой флота?

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

8. Сформулируйте постановку задачи выбора вида транспорта для доставки груза. Какой критерий оптимальности используется? Что является параметрами управления? Запишите математическую модель задачи.

9. Как учитываются провозные способности видов транспорта в математической модели? Запишите ограничения.

10. Как учитываются перевозки разнородных грузов? Запишите модель.

11. Сформулируйте постановку задачи выбора маршрута доставки грузов.

12. Запишите математическую модель задачи выбора маршрута доставки грузов. Какой критерий оптимальности используется? Что является параметрами управления?

Тема 6. Математические методы планирования: нелинейное программирование.