Задача оперативного планирования производства

Задача оперативного планирования производства

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

Дано:

n - число рабочих

n - число станков

m - число типов деталей

b1, b2, ... , bm - количество деталей, которое необходимо изготовить (задано)

λij - количество деталей j-го типа, выпускаемых за час i-м рабочим (задано)

i = 1, ... , m

j = 1, ... , n

cij - материальные затраты i-го рабочего при выпуске детали j - го типа

i = 1, ... , n

j = 1, ... , m

xij - время работы i - го рабочего над деталью j - типа (не известная)

P =

T, i = 1, ... , n

, j = 1, ... , m

xij 0

T = 8 (час.)

n = 3, m = 5

Время работы рабочего ограничено: его максимальная продолжительность показана в последней графе таблицы.

Известно, что за смену рабочие выпускают 40 деталей 1-го типа, 35 деталей 2-го типа, 38 деталей 3-го типа, 30 деталей 4-го типа, 28 деталей 5-го типа. Возможно, что выпуск указанного количества деталей не исчерпает полностью все ресурсы времени работы оборудования и предприятие сможет выпустить сверхплановую продукцию.

В таблице приведены также затраты времени на производство единицы продукции для каждого рабочего, а также количество деталей выпускаемых за час одним рабочим.

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

Составим математическую модель задачи. Пусть х1 - выпуск изделий 1 по способу 1, х2 - выпуск тех же изделий по способу 2, х3 - их выпуск по способу 3, х4 - по способу 4, х5 - по способу 5, х6 выпуск изделий 2 по способу 1 и т.д., т.е. до х10, х11 - выпуск изделий 3 по способу 1 и т.д., т.е. до х15.

Сформулируем неравенства, относящиеся к ограничением во времени работы рабочих:

x1 + x2 + x3 + x4 + x5 ≤ 8

x6 + x7 + x8 + x9 +x10 ≤ 8

x11 + x12 + x13 + x14 + x15 ≤ 8

Составим ограничение по выпуску. Общий выпуск изделий 1 равен

2x 1 + 3x6 + 5x11. Условие о том, что выпуск этих изделий должен быть равен 20, записывается так:

2x 1 + 3x6 + 5x11 = 20

По изделиям 2, 3, 4 и 5 подобные условия имеют вид:

5x2 + 4x 7 + 3x12 = 15

3x3 +6x8 +7x13 = 18

4x4 + 8x9 + 9x14 = 10

3x5 + 4x10 +5x15 = 8

В целевую функцию входят все неизвестные с коэффициентами, представляющие собой время на выпуск одной детали конкретным рабочим. Для х1 этот коэффициент равен 0,1, для х2 = 0,2, для х7 = 0,15 и т.д.

Таким образом

P = 0,1x1 + 0,2x2 + 0,03x3 + 0,4x4 + 0,35x5 + 0,2x6 + 0,15x7 + 0,1x8

+0,5x9 +0,4x10 + 0,3x11 + 0,25x12 +0,15x13 + 0,6x14 + 0,15x15 max

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

x1 + x2 + x3 + x4 + x5 ≤ 8

x6 + x7 + x8 + x9 + x10 ≤ 8

x11 + x12 + x13 + x14 + x15 ≤ 8

2x 1 + 3x6 + 5x11 = 20

5x2 + 4x 7 + 3x12 = 15

3x3 + 6x8 + 7x13 = 18

4x4 + 8x9 + 9x14 = 10

3x5 + 4x10 + 5x15 = 8

xij ≥ 0

P = 0,1x1 + 0,2x2 + 0,03x3 + 0,4x4 + 0,35x5 + 0,2x6 + 0,15x7 + 0,1x8

+0,5x9 +0,4x10 + 0,3x11 + 0,25x12 +0,15x13 + 0,6x14 + 0,15x15 max

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

P = (1)

T, i = 1, ... , n (2)

, j = 1, ... , m (3)

xij 0

T = 8 (час.)

n = 3, m = 5

где k - число балансовых переменных х1, j = n +1, ... , n + k, добавление которых в левые части ограничений типа неравенств превращает их в равенства. При этом в ограничения типа <= балансовые переменные добавляются со знаком (+), а в ограничения типа >=, со знаком (-).

Ниже, в таблице TAB.XLS приведена каноническая форма задачи. Балансовые переменные х16, х17 и х18 - вводятся в соответствующие неравенства (<=) со знаком (+).

В общем случае задача линейного программирования решается симплексным методом. Для этого необходимо, чтобы каноническая форма представления задачи (см. TAB.XLS), была бы сведена к базисному виду, когда явно указаны базисные и свободные переменные. Так, в таблице TAB.XLS переменные х16, х17, х18, х19, х20, х21, х22 и х23 являются базисными (входят только в одно уравнение с коэффициентом +1). Число базисных переменных должно равняться числу уравнений системы ограничений. Поэтому задачу (1) -(2) - (3) сводят к задаче с искусственными базисными переменными (М - задача):

P = (1’)

T, i = 1, ... , n (2)

, j = 1, ... , m (3’)

где М - сколь угодно большое положительное число (в данном случае выбрано М = 1000).

В таблице (TAB.XLS) приведена М-задача, в которой ищется минимум целевой функции . Искусственные переменные добавляются соответственно в 4, 5, 6, 7, 8 уравнения системы ограничений (см. TAB.XLS) под номерами х19, х20, х21, х22 и х23. Таблица (TAB.XLS) представляет собой задачу (1’) -(2) - (3’). Последняя строка таблицы (TAB.XLS) является строкой оценок, а последний столбец - столбец условий выбора разрешающего элемента для пересчета симплексной таблицы (TAB.XLS). Формулы пересчета таблицы (TAB.XLS) приведены там же.

Ниже приведена программа Макрос позволяющая автоматически производить пересчет симплексной таблицы (макрокоманды). Решение задачи о загрузки оборудования приведено в таблице (Итоговый).

Анализ полученных результатов: Как видно из таблицы (Итоговый), где приведено оптимальное решение задачи о загрузке оборудования, можно сделать следующую интерпретацию решения:

х4 = 10,0 - выпуск изделия 1 по способу 4 за 10,0 минут.

х6 = 16,67 - выпуск изделий 2 по способу 1 за 16,67 минут.

х10 = 9,5 - выпуск изделий 2 по способу 5 за 9,5 минут.

х12 = 15,0 - выпуск изделий 3 по способу 2 за 15,0 минут.

х13 = 6,86 - выпуск изделий 3 по способу 3 за 6,86 минут.

х7 = 1,3367 - выпуск изделий 1 по способу 1 за 0,667 часа.

Остальные переменные, не перечисленные выше, являются свободными переменными и полагаются равными нулю.

Максимально возможный фонд времени полностью не выработан, оставшееся время равно:

15,91 (мин.)