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

Известно, что за смену рабочие выпускают 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) приведены там же.