Тема 10. Транспортные задачи. Блокирование перевозок.

 

 

Если план транспортной задачи Х= является оптимальным, то ему соответствует система чисел, называемых потенциалами, для которых выполняются следующие условия

— для , для

— для , для

+ для , для

—

для , для

2Модель транспортной задачи закрытая, если

—

+

—

—

 

 

Цикл в транспортной задаче – это

—замкнутая прямоугольная ломаная линия, все вершины которой находятся в занятых клетках

— замкнутая прямоугольная ломаная линия, все вершины которых находятся свободных клетках

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

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

 

 

Если число занятых клеток меньше, чем (m+n-1), то одну свободную клетку делают занятой с нулевой перевозкой. Эта клетка

— должна образовывать цикл с вершинами только в занятых клетках

+ не должна образовывать цикл с вершинами только в занятых клетках

— должна образовывать цикл с вершинами только в свободных клетках

— может быть любой свободной клеткой

 

 

Модель транспортной задачи является открытой, если

+

—

— не зависит от и

—

 

 

Потенциалами транспортной задачи размерности (m×n) называются m+n чисел u_i и v_j, для которых выполняются условия

+ u_i+v_j=c_ij для занятых клеток

— u_i+v_j=c_ij для свободных клеток

— u_i+v_j=c_ij для первых двух столбцов распределительной таблицы

— u_i+v_j=c_ij для первых двух строк распределительной таблицы

 

 

Оценками транспортной задачи размерности (m+n) называются числа γ_ij=c_ij-u_i-v_j, которые вычисляются

— для занятых клеток

+для свободных клеток

— для первых двух строк распределительной таблицы

— для первых двух столбцов распределительной таблицы

 

 

Целевая функция транспортной задачи имеет вид

—

—

—

+

 

 

При составлении первоначального плана транспортной задачи по методу минимальной стоимости в первую очередь заполняются клетки

— расположенные по главной диваглнали распределительной таблицы

— с максимальными тарифами

+ с минимальными тарифами

— расположенные в первых строках и столбцах распределительной таблицы

 

 

При решении транспортной задачи значение целевой функции должно от итерации к итерации

— увеличиваться

— увеличиваться или не меняться

— увеличиваться на γ_ij

+уменьшаться или не меняться

 

 

В клетках распределительной таблицы располагаются

— только тарифы перевозок c_ij

— только планы перевозок x_ij

+планы перевозок x_ij и соответствующие тарифы c_ij

— значения поизведений c_ijx_ij

 

 

Если план транспортной задачи X=(x_ij)_mxn является оптимальным, то оценки γ_ij=c_ij-u_i-v_j удовлетворяют условиям

— γ_ij 0 для всех клеток

— γ_ij 0 для всех клеток

— γ_ij <0 для свободных клеток

+ γ_ij 0 для свободных клеток

 

Открытая модель транспортной задачи

A\B

 

после приведения к закрытой должна иметь вид

—

A\B

A\B

 

+

 

 

A\B

A\B

 

 

Открытая модель транспортной задачи

 

 

после приведения к закрытой должна иметь вид

—

 

A\B

A\B

 

 

+

A\B

 

 

A\B

A\B

 

 

—

 

 

Чтобы произвести блокировку некоторой клетки транспортной задачи, в этой клетке тариф

— заменяют на нуль

— удваивают

+ заменяют на достаточно большое число М

— уменьшают в два раза

 

 

Число занятых клеток невырожденного плана транспортной задачи должно быть равно

— m+n

— m+n+2

+m+n-1

— m+n+1

 

 

Экономический смысл целевой функции транспортной задачи

—суммарный объем перевозок

+ суммарная стоимость перевозок

—суммарные поставки

— суммарные потребности

 

 

В целевой функции транспортной задачи коэффициенты c_ij – это

— коэффициенты прямых затрат

— коэффициенты полных затрат

+ стоимость перевозки одной тонны груза от i–ого поставщика к j–ому потребителю

— общая стоимость перевозки от i–ого поставщика к j–ому потребителю

 

 

В целевой функции транспортной задачи переменные x_ij – это

— тарифы перевозок

— коэффициенты полных затрат

— коэффициенты прямых затрат

+ объем перевозимого груза от i–ого поставщика к j–ому потребителю

 

В транспортной задаче сумма потенциалов u_i+v_j равна тарифу c_ij, , для

+ занятых клеток

— незанятых клеток

— для любых клеток

— для первого ряда клеток

 

 

В транспортной задаче оценки γ_ij вы числяются для

—занятых клеток

— для всех клеток

+ для незанятых клеток

—для клеток первого столбца

 

 

В транспортной задаче

— максимизируется объем перевозок

+ минимизируется общая стоимость перевозок

— минимизируется общий объем перевозок

— минимизируется объем холостого пробега транспорта

 

 

Экономически отрицательная оценка показывает что, если в клетку перебросить 1т груза, то суммарная стоимость перевозки

—увеличится на

—не изменится

+уменьшится на

—уменьшится на 2

 

 

Оценки транспортной задачи, вычисляемые для свободных клеток, находятся по формуле

—

+

—

—

 

 

Блокирование перевозок применяется для клетки , в которой

—наибольший тариф

—перевозки разрешены

+перевозки запрещены

—наименьший тариф

 

 

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

— m+n-2

+ m+n-1

— m+n

— m+n+1

 

 

Если все оценки для свободных клеток , то план транспортной задачи будет

+оптимальным

—невырожденным

—неоптимальным

—вырожденным

 

 

Если число загруженных клеток в плане транспортной задачи меньше m+n-1, то план называется

—оптимальным

—неоптимальным

—невырожденным

+вырожденным

 

 

Блокирование перевозок применяется в транспортной задаче с открытой моделью. Если , то накладывается дополнительное условие, что груз i – го поставщика должен

+быть вывезен полностью

—частично остаться на складе

—не вывозиться совсем

—быть отправлен только j –му потребителю

 

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

—не удовлетворяться

+удовлетворяться полностью

— удовлетворяться частично

—должны удовлетворятся полностью только i – м поставщиком

 

 

Если плану транспортной задачи соответствует система m+n чисел (потенциалов), для которых выполняются условия для и для , то план называется

—неоптимальным

—вырожденным

— невырожденным

+оптимальным

 

 

В транспортной задаче для плана, приведенного в таблице

А\В
				-2
				-4

неоптимальной клеткой будет

—(1,1)

+(1,2)

—(2,3)

—(1,3)

 

 

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

— больше, чем m+n-1

—равно m+n-1

+меньше, чем m+n-1

—равно m+n

 

 

В транспортной задаче для плана, приведенного в таблице

А\В
				-3

неоптимальной клеткой будет

—(1,1)

—(1,2)

—(1,3)

+(3,1)

 

 

Если модель транспортной задачи открытая и , то вводится

—дополнительный потребитель с тарифами, равными 1

+фиктивный потребитель с тарифами, равными 0

—фиктивный поставщик с тарифами, равными 0

— фиктивный поставщик с тарифами, равными 1

 

 

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

— равно m+n

—равно m+n-1

—больше m+n-1

+меньше m+n-1

—

 

 

Дан план транспортной задачи и вычислены потенциалы:

А\В
				-1
				-3

Данный план является

+оптимальным

—вырожденным

—неоптимальным

— произвольным

 

 

Дана транспортная задача:

А\В

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

—

 

А\В

А\В

 

 

А\В

+

А\В

 

 

Дана транспортная задача:

А\В

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

—

А\В

А\В

+

 

 

А\В

 

А\В

 

 

Если в транспортной задачи , то для приведения к закрытой модели следует вводить

+фиктивного потребителя

—фиктивного поставщика

— фиктивных поставщика и потребителя

—нулевую поставку

 

 

Если в транспортной задачи , то для приведения к закрытой модели следует вводить

—фиктивного потребителя

+фиктивного поставщика

— фиктивных поставщика и потребителя

—нулевую поставку