ОБЩАЯ РАСПРЕДЕЛИТЕЛЬНАЯ ЗАДАЧА ЛИНЕЙНОГО ПРОГРАМИРОВАНИЯ

⇐ ПредыдущаяСтр 8 из 8

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

Пусть:

n – количество исполнителей;

m – количество видов выполняемых работ;

a_i – запас рабочего ресурса исполнителя A_i (i =1, …, n) (ед. ресурса);

b_j – план по выполнению работы B_j ( j =1, …, m) (ед. работ);

c_ij – стоимость выполнения работы B_j исполнителем A_i(руб./ед. работ);

λ _ij – интенсивность выполнения работы B_j исполнителем A_i (ед. работ / ед. ресурса);

x_ij – планируемая загрузка исполнителя A_i при выполнении работ B_j (ед. ресурса);

x_ij^к – количество работ B_j, которые должен будет произвести исполнитель A_i (ед. работ);

F(X) – общие расходы на выполнение всего запланированного объема работ (руб.).

Таблица 6.1. – Общий вид распределительной матрицы

Исполнители, A_i	Работы, B_j	Запасы ресурса, ед.ресурса
B₁	B₂		B_m
A₁	с₁₁		с₁₂		…	с₁_m	a₁
l₁₁	l₁₂	l₁_m
A₂	с₂₁		с₂₂		…	с_2m	a₂
l₂₁	l₂₂	l_2m
. . .	. . .	. . .		. . .	. . .
A_n	с_n1		с_n2		…	с_nm	a_n
l_n1	l_n2	l_nm
План, ед.работ	b₁	b₂		b_m

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

Найти минимум функции с учетом системы ограничений:

(6.1)

где ( ) – это количество работ j-го вида, выполненных i-м исполнителем.

Алгоритм решения распределительной задачи

Шаг 1. Преобразовать распределительную задачу в транспортную:

1)выбрать базовый ресурс и рассчитать нормированные производительности ресурсов :

(6.2)

2)пересчитать запаса рабочего ресурса исполнителей :

(ед.ресурса); (6.3)

3)перерасчитать планового задания :

; (6.4)

4)пересчитать себестоимости работ:

. (6.5)

Шаг 2. Проверить баланспересчитанных параметров .

Построить транспортную матрицу.

Шаг 3. Найти оптимальное решение .

Шаг 4. Преобразовать оптимальное решение транспортной задачи в оптимальное решение распределительной задачи , причем переход выполняется по формуле:

(ед.ресурса), (6.6)

где x_ij и – соответственно элементы решения распределительной и транспортной задач.

Шаг 5. Определить количество работ , соответствующее оптимальному решению распределительной задачи :

. (6.7)

Шаг 6. Определить целевую функцию распределительной задачи согласно (6.1).

Пример решения распределительной задачи

Пример №6.1.

На фабрике эксплуатируются три типа ткацких станков, который могут выпускать четыре вида тканей. Известны следующие данные о производственном процессе:

1) производительности станков по каждому виду ткани, [м/ч]

;

2) себестоимость тканей, [руб./м]

;

3) фонды рабочего времени станков (a_i): 90, 220, 180 [ч];

4) планируемый объем выпуска тканей (b_j): 1200, 900, 1800, 840 [м].

Требуется распределить выпуск ткани по станкам с целью минимизации общей себестоимости производства ткани.

Решение.

Пусть переменные x_ij – это время, в течение которого i-й станок будет выпускать j-ю ткань. Распределительная таблица имеет вид:

Распределительная матрица данного примера

Станки Ткани Фонд времени a_i, ч

B₁ B₂ B₃ B₄

A₁ 2 (c_ij) 1 3 1 90

(l_ij) 24 30 18 42

A₂ 3 2 4 1 220

12 15 9 21

A₃ 6 3 5 2 180

8 10 6 14

Объем выпуска b_j, м 1200 900 1800 840

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

.

Ограничения имеют вид:

Преобразование распределительной задачи в транспортную основано на том, что исходную задачу необходимо представить в виде, когда ткани производит только один станок – базовый и все параметры задачи согласуются с его характеристиками. В качестве базового можно выбирать любой из станков. Пусть это будет станок с максимальной производительностью, т.е. A₁. По формуле (6.2) определияются производительности станков , нормированные относительно производительности базового станка:

;

;

.

Таким образом, базовый станок работает в два раза быстрей второго станков и в три раза быстрей третьего.

Пересчет фонда времени станков производится по формуле (6.3):

(ч); (ч); (ч).

Из этих величин следует, что тот объем работ, который второй станок выполняет за свой фонд времени 220 ч, базовый станок сможет выполнить за 110 ч. Аналогично объем работ, который третий станок выполняет за 180 ч, базовый выполнит за 60 ч.

Пересчет планового задания производится по формуле (6.4):

(ч); (ч); (ч); (ч).

Отсюда следует, что план выпуска первого вида ткани базовый станок выполнит за 50 ч, второго вида за 30 ч и т.д.

Пересчет себестоимости производится по формуле (6.5):

(руб./ч); (руб./ч); (руб./ч).

В полученной транспортной задаче условие баланса (5.1) не выполняется, т.к. суммарный фонд времени станков больше, чем это необходимо для выполнения плана по выпуску всех тканей (260ч > 200ч). Необходимо ввести фиктивный столбец В_ф и записать все перечисленные параметры распределительной задачи в транспортную матрицу. Фиктивные тарифы равны нулю.

Транспортная матрица данного примера

Станки Ткани Фонд времени a_i, ч

B₁ B₂ B₃ B₄ B_ф

A₁

A₂

A₃

Объем выпуска b_j, м

Для упрощения вместо оптимального решения можно рассмотреть опорный план , найденный методом северо-западного угла.

(ч).

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

(ч).

Ответ.

1. Первый станок должен 50 ч производить ткань первого вида, 30 ч – ткань второго вида и 10 ч – ткань третьего вида,

2. Второй станок должен 180 ч производить ткань третьего вида и 40 ч – ткань четвертого вида,

3. Третий станок будет простаивать, не выпуская ткань вообще, т.к. согласно решению, его загрузка находится в фиктивном столбце (x₃₅=180^ф).

Определить сколько метров ткани каждого вида должны произвести станки можно по формуле (6.7):

(м).

Общая себестоимость производства определяется по формуле (6.1), используя вычисленные значения элементов матрицы

(руб.)

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА

1. Акулич И.Л. Математическое программирование в примерах и задачах. Лань, 2011.

2. Афанасьев М.Ю., Суворов Б.П. Исследование операций в экономике: модели, задачи, решения: Учеб. пособие. — М.: ИНФРА-М, 2003.

3. Банди Б. Основы линейного программирования: Пер. сангл. — М.: Радио и связь, 1989.

4. Г.Вагнер. Основы исследования операций. - М., Мир, 1972-1973.

5. Кремер Н.Ш. Исследование операций в экономике: Учеб. пособие для вузов /Н.Ш. Кремер, БА. Путко, И.М. Тришин, М.Н. Фридман; Под ред. проф. Н.Ш. Кремера. - М.: ЮНИТИ, 2005.

6. Лунгу К.Н. Линейное программирование. Руководство к решению задач. – М.: Физматлит, 2005.

7. Таха Х.А. Введение в исследование операций. – М.: ВИЛЬЯМС, 2007.

⇐ Предыдущая 1 2 3 4 5 6 78