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

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

! для , для

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

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

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

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

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

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

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

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

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

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

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

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

Распределительная таблица транспортной задачи это !таблица, в которую записаны план перевозок и тарифы перевозок

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

!

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

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

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

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

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

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

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

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

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

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

В транспортной задаче !минимизируется общая стоимость перевозок

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

Элементы матрицы затрат в - задаче имеют размерности !руб/шт

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

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

В задаче о загрузке оборудования a₁, a_2…a_m – это !время работы станков

В задаче о загрузке оборудования b₁, b₂, …b_n – это !плановые задания по выпуску изделий в штуках

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

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

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

( )называются !приведенными к стандартным часам плановыми заданиями

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

( ) называются !приведенными к стандартным часам затратами

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

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

В - задаче - это!приведенное время работы i – го станка по производству изделий вида j

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

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

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

ai\bj				ui
				-1
				-4
vj

Неоптимальной будет клетка !(1,1)

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

ai\bj

Этот план !невырожденный

Дан план транспортной задачи Неоптимальной будет клетка !(3,3)

ai\bj				ui
vj	-2

Дан план транспортной задачи Значение целевой функции равно !750

ai\bj

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

Реальная работа – это !работа, требующая затрат ресурсов и времениПолный резерв времени вычисляется по формуле !

Конечное событие сетевого графика – это !событие, не имеющее выходящих работ

Начальное событие сетевого графика – это событие !не имеющее входящих работ

Временной параметр - это !самый ранний срок начала работы

Параметр - это !полный резерв времени на работу

Работа – ожидание!требует только время

Критическим путем называется !путь наибольшей длины из начального события в конечное событие

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

Параметр t_ij – это !время, необходимое для выполнения работы A_ij

Фиктивная работа !не требует ни времени, ни ресурсов

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

Временной параметр - это !самый ранний срок окончания работы

Временной параметр - это !поздний срок окончания работы

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

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

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

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

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

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

Работа, требующая только время, называется !работой – ожидание

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

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

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

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

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

Событие свершилось, если !выполнены всей работы, в него входящие

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

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

Величина равна !длине наибольшего пути от события j до конечного события

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

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

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

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

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

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

Поиск по сайту: