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

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

+— для , для

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

+—

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

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

 

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

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

 

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

+—

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

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

 

Оценками транспортной задачи размерности называются числа г_ij, которые вычисляются

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

 

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

+—

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

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

 

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

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

 

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

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

 

Если план транспортной задачи X=(x_ij)_mЧn является оптимальным, то оценки удовлетворяют условиям

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

 

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

A\B

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

A\B

 

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

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

 

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

+—m+n-1

 

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

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

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

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

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

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

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

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

 

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

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

 

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

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

Элементы матрицы производительностей в - задаче имеют размерность

+—шт/час

Элементы матрицы затрат в - задаче имеют размерности

+—руб/шт

 

В таблице задачи о загрузке оборудования каждая клетка содержит

+—производительность станка, затраты на один час работы станка, время работы над j-ым изделием

 

В задаче о загрузке оборудования – это

+—фонды рабочего времени станков

 

В задаче о загрузке оборудования b₁, b₂,…,b_n – это

+—заказ по выпуску изделий в штуках

 

В задаче о загрузке оборудования

+—

В задаче о загрузке оборудования называется

+—индексом i–ого станка

 

В задаче о загрузке оборудования

()называются

+—приведенными к стандартным часам потребностями

 

В задаче о загрузке оборудования

() называются

+—приведенными к стандартным часам затратами

В задаче о загрузке оборудования называются

+—приведенным к стандартным часам фондом рабочего времени станков

В - задаче - это

+—приведенное время работы i – го станка по производству - го вида изделий

 

Дан план транспортной задачи

ai\bj				ui
				-1
				-4
vj

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

+—(1,1)

 

Дан план транспортной задачи

ai\bj

Этот план

+—вырожденный

 

Дан план транспортной задачи

ai\bj				ui
vj	-2

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

+—(3,3)

 

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

ai\bj

Первоначальный план, найденный методом минимальной стоимости, имеет вид

ai\bj

 

 

Дан план транспортной задачи

ai\bj

Значение целевой функции равно +—750

 

Дан план транспортной задачи

ai\bj

этот план

+—невырожденный

 

Дан план транспортной задачи

ai\bj				ui
				-1
				-4
vj

Цикл нужно строить для клетки +—(1,1)

 

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

ai\bj

План, найденный методом минимальной стоимости, имеет вид

 

ai\bj

 

Дана транспортная задача и дополнительное условие: третий поставщик должен полностью отправить свой груз.

ai\bj

Необходимо заблокировать клетку +—(3,3)

 

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

ai\bj

Необходимо заблокировать клетку +—(2,3)

 

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

ai\bj

Необходимо заблокировать клетку +—(4,1)

В задаче по загрузке оборудования индекс - го станка определяется по формуле

+—

В задаче по загрузке оборудования элементы матрицы - это

+—производительность - го станка при производстве - го изделия

 

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

+—

—

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

ai\bj

Первоначальный план, найденный методом минимальной стоимости, имеет вид

ai\bj

 

Дан план транспортной задачи

ai\bj				ui
vj

Потенциалы поставщиков и потребителей соответственно равны

		-1

План транспортной задачи

ai\bj				ui
				-2
				-1
vj

+—оптимальный и неединственный

 

План транспортной задачи

ai\bj				ui
vj

+—оптимальный и единственный

 

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

A\B

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

	A\B

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

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

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

+—

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

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

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

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

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

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

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

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

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

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

 

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

А\В
				-2
				-4

неоптимальной клеткой будет +—(1,2)

 

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

А\В
				-3

неоптимальной клеткой будет +—(3,1)

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

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

 

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

А\В
				-1
				-3

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

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

 

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

А\В

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

А\В

 

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

А\В

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

А\В

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

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

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

+—он неединственный

 

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

А\В
			-4

Данный план

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

 

Чтобы данный вырожденный план транспортной задачи

А\В
				-3
				-5
				-6

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

+—(1;3)

 

Данный план транспортной задачи

А\В

является

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

 

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

+—одну клетку занимают нулевой перевозкой

 

Тема 9. Сетевое планирование и управление

Реальная работа - это

+—работа, требующая затрат ресурсов и времени

Полный резерв времени вычисляется по формуле

+—

Конечное событие сетевого графика – это

+—событие, не имеющее выходящих работ

 

Начальное событие сетевого графика – это событие

+—не имеющее входящих работ

Временной параметр - это

+—самый ранний срок начала работы

Параметр - это

+—полный резерв времени на работу

 

Работа – ожидание

+—требует только время

—требует только ресурсы

 

Событие n-го ранга (n¹1) – это событие

+—в которое входит работа, отмеченная наибольшим номером, равным (n-1) и ниже

 

Критическим путем называется

+—путь наибольшей длины из начального события в конечное событие

 

Наиболее ранний срок наступления события с номером k вычисляется по формуле

+—

Параметр t_ij – это

+—время, необходимое для выполнения работы A_ij

—время, необходимое для наступления события с номером i

 

Фиктивная работа

+—не требует ни времени, ни ресурсов

 

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

+—R_ij^п=0

Временной параметр - это

+—самый ранний срок окончания работы

Временной параметр - это

+—поздний срок окончания работы

 

Направление стрелок работ в сетевом графике изображается

+—слева направо

 

Длиной пути из события i в событие j называется

+—сумма продолжительностей работ, составляющих этот путь

 

Математическим аппаратом сетевого планирования и управления является теория

+—графов

 

Если несколько работ выходят из одного события и заканчиваются в другом, то для их различия нужно ввести

+—фиктивные работы

—фиктивные события

 

В сетевом графике не должно быть: —фиктивных работ—работ – ожиданий—фиктивных событий

+—циклов

 

Работа, требующая только время, называется

+—работой – ожидание

 

Работа, не требующая ни времени, ни ресурсов, называется

+—фиктивной

 

Работа, потребляющая ресурсы и время, называется

+—реальной работой

 

Сетевой график состоит из

+—работ и событий

—работ и их длительностей

 

Событие сетевого графика изображается

+—кружком

 

Работа изображается на сетевом графике

+—стрелкой

 

Событие свершилось, если

+—выполнены все работы, в него входящие

При обозначении работы на сетевом графике

+—

Работы, выходящие из событий n –го ранга, имеют номер

—n-1

+—n

—n+1

—n+2

 

Величина равна

+—длине наибольшего пути от события j до конечного события

 

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

+—длине критического пути

 

При нумерации событий сетевого графика необходимо определить

+—ранг событий

 

Сетевой график может иметь

+—одно начальное и одно конечное событие

 

Раннее время свершения k – го события вычисляется по формуле

+—

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

+—

Событие, в которое входит работа с номером III, будет событием

+—четвертого ранга

 

Событие, в которое входят работы с номерами V и I, будет событием

+—шестого ранга

 

Событие, в которое входят работы с номерами V и VII, будет событием

+—восьмого ранга

 

Работе, выходящей из события шестого ранга присваивают номер

+—VI

 

В сетевом графике число событий и работ должно быть

+—счетным (натуральные)

 

Целью системы сетевого планирования управления является

+—выявление и мобилизация резервов времени

 

Сетевой моделью называется ЭММ, отображающая

+—комплекс работ и событий, связанных с реализацией некоторого проекта

 

Графом называется

+—совокупность точек, называемых вершинами, и ориентированных дуг, соединяющих вершины

 

Сетью называется

—совокупность событий и работ

+—граф, в котором только одна точка, не имеющая входящих дуг, и лишь одна точка, не имеющая выходящих дуг, и каждой дуге которого приписано число

В сетевом графике путем из начального события в конечное называется

+—последовательность работ, в которой конец каждой предыдущей работы совпадает с началом последующей