4.6.1 Общая постановка рзлп
Формальная запись распределительной задачи:
при условиях:
(5)
Наиболее общая постановка (5):
Необходимо выполнить , , видов работ в объемах . Для выполнения этих работ имеется , , типов оборудования. Для каждого типа известна мощность всего парка машин (машино-часы, тонно-километры и т.п.) за определенный промежуток времени (час, сутки, смена, сезон) – , . Известны удельные затраты мощности или времени каждым типом оборудования при выполнении каждого вида работ – . Известны также затраты средств на выполнение единицы работы на каждом из типов оборудования – .
Необходимо так распределить работы по типам оборудования (или закрепить оборудование по работам), чтобы выполнить требуемый объем работ существующим парком машин с наименьшими затратами.
Обозначим – объемы работ -го типа, выполненный на -ом типе оборудования.
26.Задачи, сводящиеся к распределительной задаче ЛП.
4.6.2.1 Станочная задача; более общая постановка
Вернемся к задаче (5.3). Здесь:
– время, затрачиваемое станком -го типа на изготовление детали -го вида [час];
– мощность станочного парка -го типа за некоторый промежуток времени [станко-часы];
– объем -ой работы – число -ых деталей, которые надо произвести, чтобы получить из них готовые изделия в количестве ( – число деталей , идущих на одно готовое изделие);
– число деталей , производимых за промежуток времени на станках -го типа, тогда – распределение деталей по станкам.
Модель будет иметь вид (5), где в качестве функции цели используется:
4.6.2.2 Задача об оптимальном использовании оборудования (задача оптимизации машинно-транспортного парка)
Она возникает, когда к задаче в постановке (5) добавляются требования:
выполняемые работы различаются по срокам их выполнения – требования соблюдения технологических сроков;
работу может выполнять только комплекс машин – агрегат.
Задача теряет специальную структуру и решается симплекс-методом.
27.Сведение распределительной задачи ЛП к транспортной задаче.
Формальная запись распределительной задачи:
при условиях:
(5)
Для задачи (5) разработан специальный алгоритм численной реализации – метод условно-оптимальных планов. Однако, он довольно трудоемкий при больших размерностях задачи. Поэтому, когда возможно, распределительную задачу сводят к транспортной, и решают методом потенциалов.
РЗЛП (5) сводится к транспортной только в том случае, когда ее коэффициенты удовлетворяют условиям:
(9)
Здесь – индекс работы, – затраты мощности или времени для выполнения -й работы на -ом оборудовании.
Соотношение (9) означает, что все работы ранжированы относительно трудоемкости первой «эталонной» работы ( ) не зависимо от оборудования, на котором они выполняются.
В этом случае производительность можно выразить так:
(10)
С учетом (6) запишем модель:
(11)
Сделаем замену переменных: .
Целью является сведение РЗЛП к транспортной задаче. В транспортной задаче правая часть особенная. Коэффициенты в правой части отсутствуют, и стоит сумма неизвестных.
Преобразуем правую часть модели так, чтобы было как у транспортной задачи:
(12)
Задача (12) представляет собой незамкнутую транспортную задачу; она решается стандартными методами для транспортной задачи, а затем осуществляется обратный переход от к .