6.1. Теоретическое введение
Общая распределительная задача
ЛП – это РЗ, в которой работы и ресурсы (исполнители) выражаются в различных
единицах измерения. Типичным примером такой задачи является организация выпуска
разнородной продукции на оборудовании различных типов.
Исходные параметры модели РЗ
1)
n –
количество исполнителей;
2)
m –
количество видов выполняемых работ;
3)
– запас рабочего ресурса исполнителя 
(
) [ед.ресурса];
4)
– план по выполнению работы 
(
) [ед. работ];
5)
– стоимость выполнения работы исполнителем [руб./ед. работ];
6) 
– интенсивность выполнения работы исполнителем [ед. работ/ед.ресурса].
Искомые параметры модели РЗ
1)
– планируемая загрузка исполнителя при выполнении работ [ед. ресурса];
2)
– количество работ , которые должен будет произвести исполнитель [ед. работ];
3)
– общие расходы на выполнение всего запланированного
объема работ [руб.].
Этапы
построения модели
I.
Определение переменных.
II.
Построение распределительной матрицы (см. табл.6.1).
III.
Задание ЦФ.
IV.
Задание ограничений.
Таблица 6.1
Общий вид распределительной матрицы
|
Исполнители,
|
Работы,
|
Запас ресурса,
ед.ресурса
|
|
|
|
…
|
|
|
|
|
|
…
|
|
|
|
|
|
|
…
|
|
|
|
…
|
…
|
…
|
…
|
…
|
…
|
|
|
|
|
…
|
|
|
|
План, ед.работы
|
|
|
…
|
|
|
Модель
РЗ
|
 ;
|
(6.1)
|
где 
– это количество работ j-го вида, выполненных i-м исполнителем.
Этапы решения РЗ
I. Преобразование РЗ в ТЗ:
1) выбор базового ресурса и
расчет нормированных производительностей ресурсов 
:
|
|
(6.2)
|
2) пересчет
запаса рабочего ресурса исполнителей 
:
|
[ед. ресурса];
|
(6.3)
|
3)
пересчет планового задания 
:
|
  ;
|
(6.4)
|
4) пересчет
себестоимостей работ:
|
  .
|
(6.5)
|
II. Проверка баланса
пересчитанных параметров 
и построение транспортной
матрицы.
III. Поиск оптимального решения
ТЗ
.
IV. Преобразование
оптимального решения ТЗ 
в оптимальное решение
РЗ 
, причем переход 
выполняется по формуле
(6.6)
|
[ед. ресурса],
|
(6.6)
|
где и 
–
соответственно элементы решения РЗ и ТЗ.
V. Определение
количества работ 
, соответствующее оптимальному решению РЗ :
|
  .
|
(6.7)
|
VI. Определение
ЦФ распределительной задачи 
согласно (6.1).
6.2. Методические рекомендации
Задача №6.01
На фабрике эксплуатируются три типа ткацких станков, которые могут
выпускать четыре вида тканей. Известны следующие данные о производственном
процессе:
·
производительности станков по каждому виду
ткани, м/ч
;
·
себестоимость тканей, руб./м
;
·
фонды рабочего времени станков (
): 90, 220, 180 ч;
·
планируемый объем выпуска тканей (): 1200, 900, 1800, 840 м.
Требуется распределить выпуск ткани по станкам с целью минимизации общей
себестоимости производства ткани.
Решение
Пусть переменные – это время, в течение которого i-й станок будет выпускать j-ю ткань. Сведем исходные
данные задачи в распределительную таблицу (табл.6.2).
Таблица 6.2
Распределительная матрица задачи
№6.01
|
Станки
|
Ткани
|
Фонд времени , ч
|
|
В1
|
В2
|
В3
|
В4
|
|
А1
|
2 ( )
() 24
|
1
30
|
3
18
|
1
42
|
90
|
|
А2
|
3
12
|
2
15
|
4
9
|
1
21
|
220
|
|
А3
|
6
8
|
3
10
|
5
6
|
2
14
|
180
|
|
Объем выпуска
, м
|
1200
|
900
|
1800
|
840
|
|
ЦФ имеет смысл себестоимости выпуска запланированного
количества ткани всех видов
Ограничения имеют вид
Преобразуем РЗ в ТЗ, т.е. представим исходную задачу в
виде, когда ткани производит только один станок – базовый и все параметры
задачи согласуем с его характеристиками. В качестве базового можно выбирать
любой из станков. Мы выберем станок с максимальной производительностью, т.е. . По формуле (6.2) определим производительности станков , нормированные относительно производительности базового станка:
;
;
.
Таким образом, базовый станок работает в два раза быстрей второго станка
и в три раза быстрей третьего.
Пересчитаем фонды времени
станков по формуле (6.3):
[ч]; 
[ч]; 
[ч].
Из этих величин следует, что тот объем работ, который второй станок
выполняет за свой фонд времени 220 ч базовый станок сможет выполнить за
110 ч. Аналогично объем работ, который третий станок выполняет за
180 ч базовый выполнит за 60 ч.
Пересчитаем плановое
задание по формуле (6.4):
[ч]; 
[ч]; 
[ч]; 
[ч].
Отсюда следует, что план выпуска первого вида ткани базовый станок выполнит
за 50 ч, второго вида – за 30 ч и т.д.
Пересчет себестоимостей производим по формуле (6.5), например:
[руб./ч]; 
[руб./ч]; 
[руб./ч].
В полученной ТЗ условие баланса (4.2) не выполняется, т.к. суммарный фонд
времени станков больше, чем это необходимо для выполнения плана по выпуску всех
тканей (260 ч >
200 ч). Введем
фиктивный столбец 
и запишем все
пересчитанные параметры РЗ в транспортную матрицу (см. табл.6.3). Фиктивные
тарифы для упрощения приравняем к нулю.
Таблица 6.3
Транспортная матрица задачи №6.01
|
Станки
|
Ткани
|
Фонд времени
 , ч
|
|
В1
|
В2
|
В3
|
В4
|
ВФ
|
|
А1
|
48
|
30
|
54
|
42
|
0
|
90
|
|
А2
|
72
|
60
|
72
|
42
|
0
|
110
|
|
А3
|
144
|
90
|
90
|
84
|
0
|
60
|
|
Объем выпуска , ч
|
50
|
30
|
100
|
20
|
60
|
|
Для упрощения вместо оптимального решения рассмотрим опорный план 
, найденный методом северо-западного угла.
[ч].
Преобразуем
опорный план ТЗ в опорный план РЗ 
согласно (6.6)
ч].
Таким образом, первый станок должен 50 ч производить ткань первого
вида, 30 ч – ткань второго вида и 10 ч – ткань третьего
вида. Второй станок должен 180 ч производить ткань третьего вида и
40 ч – ткань четвертого вида. А третий станок будет простаивать, не
выпуская ткань вообще, т.к. согласно решению, его загрузка находится в
фиктивном столбце (
).
Определим, сколько метров ткани каждого вида должны произвести станки по
формуле (6.7)
[м].
Определим общую себестоимость производства по формуле (6.1), используя
вычисленные значения элементов матрицы 
(руб.).
