Общая распределительная задача линейного программирования

Теоретическое введение

Общая распределительная задача ЛП – этоРЗ, в которой работы и ресурсы (исполнители) выражаются в различных единицах измерения. Типичным примером такой задачи является организация выпуска разнородной продукции на оборудовании различных типов.

Исходные параметры модели РЗ

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