Процедуры международный таможенный транзит. Таможенная конвенция о международной перевозке грузов с применением книжки МДП.

БИЛЕТ 19

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

Схемы механизации перегрузочных процессов в аэропортах.

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

Пусть имеется m пунктов отправления, в каждом из которых находится однотипная продукция в количествах: a_1, a₂, …, a_m единиц. Эту продукцию нужно доставить в n пунктов назначения в количествах: b_1, b₂, …, b_n единиц соответственно. Известна стоимость перевозки C_ij единицы продукции из i-ого пункта отправления в j-ый пункт назначения.

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

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

Задача сводится к задаче линейного программирования (ЛП) с ограничениями типа равенств. Введём переменные x_ij - количество продукции перевозимой из i-ого пункта отправления в j-ый пункт назначения. Вся совокупность переменных x_ij образует прямоугольную матрицу:

X = (x_ij), i =1,2, …,m; j=1,2,…,n,

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

Z =

означающую суммарную стоимость перевозки при ограничениях вида:

1. х_ij ³ 0;

2. , i = 1, 2,…, m;

3. , j = 1, 2,…,n.

Условие 1 означает неотрицательность переменных. Условие 2 означает, что вся продукция в каждом из m пунктов отправления вывезена полностью. Условие 3 означает, что все заявки получателей удовлетворены в полном объеме.

План X = (x_ij) называется допустимым, если входящие в него переменные удовлетворяют всем ограничениям задачи – условия 1-3. План называется оптимальным, если он удовлетворяет двум условиям:

1. Он является допустимым;

2. Он обеспечивает минимум заданной целевой функции.

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

K = nm – (n+m-1)

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

1. Отыскание опорного плана;

2. Улучшение опорного плана до тех пор, пока он не станет оптимальным.

Пример отыскания опорного плана.

Задана транспортная таблица:

 

ПН ПО	В1	В2	В3	В4	Предложение
А1
А2
А3
Спрос

Требуется найти опорный план методом Северо-западного угла.

Задача является сбалансированной – суммарный спрос равен суммарному предложению. Расширения транспортной таблицы путем введения фиктивных (пунктов отправления или назначения) не требуется. Опорный план имеет следующий вид:

 

ПН ПО	В1	В2	В3	В4	Предложение
А1
А2
А3
Спрос