Использование сверхурочных работ

При изготовлении изделий двух видов осуществляется последова­тельная обработка соответствующих заготовок на двух различных станках. Каждый станок может использоваться для производства из­делий по 8 часов в сутки, однако этот фонд времени можно увеличить на 4 часа за счет сверхурочных работ. Каждый час сверхурочного вре­мени требует дополнительных расходов: для станка 1 это долл.5, для станка 2 — долл.7. Производительность станков и продажная цена из­делий приведены в таблице.

Станок	Производительность станков (изделие/ч)
изделие 1	изделие 2
Цена изделия	$6	$4

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

Для этих задач целевая ячейка обычно определяет объем реализа­ции некоторой разнородной продукции в стоимостном выражении. Целью оптимизации является определение оптимального соотноше­ния объемов между видами выпускаемой продукции, при котором объем реализации достигает максимума.

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

Математическая формулировка задачи

Содержимое изменяемых ячеек

Определим X11, Х12 как количества изделий первого типа, выпу­скаемых соответственно на первом и втором станках. Аналогично,

Часть 1. Поиск решений на электронных таблицах

Примеры структуризации задач

Х21, Х22 будут определять количество изделий второго типа, выпус­каемых на этих же станках.

Т1с/у, Т2с/у — время сверхурочных работ соответственно на пер­вом и втором станках.

Ограничения

1. По времени занятости станков:

XI1/5 + Х21/6 <= 8 + Tlc/y; X12/4 + Х22/8 <= 8 + Т2с/у; Т1с/у <= 4; Т2с/у <= 4.

2. «Естественные» ограничения:

Т1с/у >= 0; Т2с/у >= 0; X1UX22 >= 0. Целевая функция:

Z = (XI1+ Х12)*6 + ( Х21 + Х22)*4 - (5* Т1с/у + 7* Т2с/у). Максимизировать Z.

Изменяемые ячейки: D3:E4; С10:С11.

Ограничение по времени использования станков: С10:С11<=ЕШ:Е11.

Целевая ячейка: G13.

Задачи смеси

Как правило, в таких задачах требуется определить такой состав смеси различных продуктов, который удовлетворяет заданным огра­ничениям по ее качеству (например, по калорийности, пластичности, содержанию питательных веществ) и вместе с тем определяет смесь минимальной стоимости. В литературе часто встречается и другое на­звание для этого класса задач — «задачи о диете».

Для этого вида оптимизационных задач характерно наличие про­центных (или долевых) ограничений. Ниже приводится пример струк­туризации задачи этого типа.

Определение топливной смеси

Фирма хочет использовать для своих грузовиков смешанное топ­ливо с целью сокращения транспортных расходов. Планируется сме­шивать два вида топлива (Аи В).

Смешанное топливо должно иметь октановое число не меньше 80. Октановое число смеси является взвешенным средним октановых чи­сел смешиваемых компонент, причем веса пропорциональны соответ­ствующим смешиваемым объемам (при смешивании компонент объ­ем смеси равен сумме объемов компонент):

ОЧсм = Ва*ОЧа + ВЬ*ОЧв; Ва - Va/(Va + Vb); Bb = Vs/(Va + Vb).

Здесь ОЧсм, ОЧа, ОЧв — октановые числа соответственно смеси, топлива А и топлива В, Va, Vb — объемы смешиваемых топлив А и В.

Для обеспечения всех грузовиков фирмы в течение следующего месяца необходимо не менее 3000 галлонов топлива. Фирма рас­полагает хранилищем для топлива емкостью 4000 галлонов. Воз­можно приобретение до 2000 галлонов топлива А и 4000 галлонов топлива В.

Топливо А имеет октановое число 90 и стоимость $1,20 за галлон, топливо В имеет октановое число 75 и стоимость $0,90 за галлон. Определите смесь минимальной стоимости.

46

Часть 1. Поиск решений на электронных таблицах

Примеры структуризации задач

47

J

Математическая формулировка задачи

Содержимое изменяемых ячеек

Пусть переменная Va определяет объем топлива А, а переменная Vb — объем топлива В. Ограничения

1. По запасам топлива: Va + Vb >= 3000; Va + Vb <= 4000.

2. По закупкам топлива: Va <= 2000; Vb <= 4000.

3. По октановому числу смеси: Ва*90 + ВЬ*75 >= 80.
Целевая функция: Z = l,20*Va + 0,90*Vb.
Минимизировать Z.

Изменяемые ячейки: В2:ВЗ. Ограничения:

1. По закупкам топлива: В2:ВЗ <= С2:СЗ.

2. По запасам топлива: F4 <= F5; F4 >= F6.

3. По октановому числу смеси: F7 >= F8.
Целевая ячейка: F8.

Задачи дисбаланса

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

Ниже рассматриваются две характерных задачи этого класса.

Минимизация дисбаланса при сборке изделий из комплектующих

Изделия двух типов (А и В) собираются с использованием комп­лектующих четырех видов (1, 2, 3 и 4). Структура изделий определена в таблице (изделие типа А состоит из трех комплектующих первого типа, десяти комплектующих второго типа и т. д.).

Тип изделия	Вид комплектующих i
А
В

Комплектующие выпускаются на двух различных заводах. В сле­дующей таблице приведены данные, характеризующие производите­льность заводов по выпуску комплектующих и недельный ресурс вре­мени, которым располагает каждый из заводов для их производства. Цена изделий вида А — $40, вида В — $27.

Завод	Недельный фонд времени (ч)	Производительность по видам комплектующих (ед./ч)

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

48

Часть 1. Поиск решений на электронных таблицах

Примеры структуризации задач

49

Математическая формулировка задачи

Определим варьируемые переменные Xij как еженедельные затраты времени (в час) для производства комплектующих i-oro вида на j-ом заводе (i = 1, 2, 3, 4; j = 1, 2). Тогда суммарное количество комплекту­ющих, выпускаемых двумя заводами (по видам комплектующих), определится выражениями:

N1=1O*X11+8*X12; (комплектующие первого вида);

N2=5*X21+6*X22; (комплектующие второго вида);

N3=7*X31+12*X32; (комплектующие третьего вида);

N4=8*X41+3*X42 (комплектующие четвертого вида).

Введем дополнительные варьируемые переменные «второго уровня» Nia — количество комплектующих i-oro вида, используемых для сбор­ки изделия А, аналогично Nib (Nia + Nib = Ni; i = 2, 3, 4).

При решении этой задачи целесообразно использовать понятие полного комплекта — набора комплектующих, из которых может быть собрано одно изделие. Так, для изделия А полным комплектом явля­ется набор (3, 10, 7, 1), а для изделия В — (0, 8, 5, 4). Любой комплект составляется из порций комплектующих разных видов. Для изделия А это 4 порции:

1) из трех комплектующих первого вида;

2) десяти второго вида;

3) семи третьего вида;

4) одной комплектующей четвертого вида.

Дисбаланс заключается в том, что из-за различий в производите­льности заводов число таких порций не позволяет составить целое число полных комплектов, поэтому возникает дисбаланс, связанный с образованием остатков комплектующих одного вида и нехваткой ком­плектующих другого вида. Оба этих фактора влекут к снижению объе­мов производства изделий. При этом фактически количество выпус­каемых изделий определяется минимальным количеством порций, из которых могут быть составлены полные комплекты.

Например, все комплектующие первого вида используются для сбор­ки изделий А. Какое количество изделий типа А можно собрать из комп­лектующих первого вида? Очевидно, это количество определяется тем, сколько порций можно собрать из комплектующих первого вида, т. е. ве­личиной [Nl/З] (квадратные скобки определяют здесь целую часть).

Комплектующие второго вида делятся на две части, одна из них идет на сборку изделий типа А, вторая — на сборку изделий типа В, при этом N2a + N2b = N2. Величина [N2a/10] определит количество порций и соответственно количество изделий типа А, которые можно собрать с учетом объема имеющихся комплектующих второго вида — N2a.

Таким образом, общее количество изделий типа А, которое может быть собрано при наличии комплектующих 1/4-ого видов в количест­ве (N1, N2a, N3a, N4a), определится формулой:

Кол-во_Изделий_А = MIN ([N1/3], [N2a/10], [N3a/7], [N4a]).

Аналогично для изделий типа В: Кол-во_Изделий_В = MIN ([N2b/8], [N3b/5], [N4b/4]).

Содержимое целевой ячейки: Z = 40*Кол-во_Изделий_А + 27*Кол-во_Изделий_В.

Ограничения: по времени производства

для завода 1: XII + Х21 + Х31 + Х41 <= 130;

для завода 2: Х12 + Х22 + Х32 + Х42 <= 90.

по видам комплектующих: Nia + Nib = Ni; i = 2, 3, 4; Nia, Nib = целые.

Максимизировать Z.

Таким образом, в этой задаче общее число варьируемых перемен­ных (изменяемых ячеек) равно 14. Из них 8 переменных Xij имеют размерность времени, а 6 переменных (Nia, Nib) — безразмерны.

Структура ЭТ

50

Часть 1. Поиск решений на электронных таблицах

Примеры структуризации задач

51

Продолжение ЭХ

Изменяемые ячейки первого уровня: F4:15. Изменяемые ячейки второго уровня: G12:113. Целевая ячейка: J19.

Ограничения:

• по времени производства J4 : J5 <= J7:J8;

• по видам комплектующих: G14 : 114 = G9:I9;

• G12:I13 = целые.

Модель производства с запасами

Фирма переводит свой завод на производство новых изделий, которые планируется выпускать в течение четырех месяцев. Оцен­ки спроса на изделия в каждый из этих месяцев приведены в таб­лице:

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

• избытка изделий, произведенных в предшествующие месяцы;

• изделий, произведенных в текущем месяце;

• изделий, произведенных в последующие месяцы для погашения
невыполненных ранее заказов.

Затраты на изготовление одного изделия составляют долл.4. Изде­лие, произведенное, но не поставленное потребителю в текущем ме­сяце, влечет за собой дополнительные издержки на хранение в разме­ре долл.0,5 за каждый месяц хранения. Изделие, выпускаемое в счет невыполненных заказов, облагается штрафом в размере долл.2 за каж­дый месяц недопоставки.

Объем производства меняется от месяца к месяцу по внутризавод­ским причинам. В рассматриваемые 4 месяца планируется следующая программа выпуска изделий.

Месяц производства изделия
Выпуск (штук)

Требуется уточнить (доопределить) эту программу таким образом, чтобы она обеспечивала минимальные издержки, обусловленные не­согласованностью спроса и предложения (дисбалансом).

Задачи такого типа в исследовании операций известны как «транспортные задачи». Это обусловлено тем, что чаще всего та­кие задачи связаны с оптимизацией процессов перевозок. Вместе с тем к этому типу сводится рассматриваемая задача и многие другие, не имеющие непосредственного отношения к транспорту. Специфика этих задач заключается в использовании табли­цы-матрицы, строки и столбцы которой определяют факторы дисбаланса — спрос и предложение, место производства и по­требления продукции и т. п.

Пусть i определяет месяц производства изделия, a j — месяц по­ставки. В качестве содержимого изменяемых ячеек будем использовать Xij — количество изделий, произведенных в i-ый месяц и поставлен­ных в j-ый.

Месяц поставки изделия
Спрос (штук)

Математическая формулировка задачи

Определим матрицу стоимостей производства и хранения из­делий.

52

Часть 1. Поиск решений на электронных таблицах

Примеры структуризации задач

53

\ Месяц пр-ва (i)	Месяц потребления 0)	Программа выпуска изделий (шт)
		4,5		5,5
2 .!			4,5
				4,5
Спрос (шт)

$4; (при i = j);

Cij = $4 + $0,5 * (j - i); (при j > 0; $4 + $2*(i-j); (при i>j).

В таком же виде определим программу производства изделий.

Месяц пр-ва (i)	Месяц потребления (j)	Программа выпуска изделий (шт)
	Х11	XI2	Х13	Х14
	Х21	Х22	Х23	Х24
	Х31	Х32	ХЗЗ	Х34
	Х41	Х42	Х43	Х44
Спрос

Структура ЭТ

Ограничения:

предложение (объемы производства):

Х11+Х12+Х13+Х14= 50;

Х21+Х22+Х23+Х24=180;

ХЗ 1+Х32+ХЗЗ+Х34=280;

Х41+Х42+Х43+Х44=270. спрос:

Х11+Х21+Х31+Х41=100;

X12+Х22+Х32+Х42=200;

Х13+Х23+ХЗЗ+Х43=180;

Х14+Х24+Х34+Х44=300. Целевая функция:

Z= ^ Zj (Xij*Cij) для i=l₅2,3,4; j=l,2,3,4; Минимизировать Z.

Функция СУММ() находится в списке функций системы EXCEL. Она реализует суммирование элементов массива. Функция СУММПРОИЗВ() суммирует произведения элементов двух массивов. Она также находится в списке функций EXCEL.

Например,

СУММПРОИЗВ(В12:Е15; В4:Е7) =

B12*B4+C12*C4+D12*D4+E12*E4+

B13*B5+C13*C5+D13*D5+E13*E5+

B14*B6+C14*C6+D14*D6+E14*E6+

B15*B7+C15*C7+D15*D7+E15*E7.

Изменяемые ячейки: В12:Е15, целевая ячейка F17.

Ограничения:

по производственной программе: F4:F7=F12:F15;

по спросу: В8:Е8=В16:Е16;

естественные: В12:Е15 целые, неотрицательные.

54

Часть 1. Поиск решений на электронных таблицах

Примеры структуризации задач

55

Составление «скользящих» графиков

Такие графики обычно связаны с расписаниями многосменной работы предприятия в условиях нестационарного спроса на товары или услуги, связанные с деятельностью этого предприятия. Эти зада­чи характеризуются наличием многих ограничений, действующих в разные периоды времени. Например, спрос на общественный транс­порт сильно меняется в зависимости от времени суток, спрос на про­даваемые товары в магазине меняется в зависимости от дня недели и времени суток и т. д. Задача состоит в том, чтобы организовать распи­сание обслуживания клиентов (пассажиров, покупателей и т. п.) та­ким образом, чтобы издержки от неравномерности спроса были бы минимальны.

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

Составление скользящего расписания при нестационарном потребительском спросе

В таблице приведено количество продавцов, которое необходимо для удовлетворения покупательского спроса в торговом зале магазина в течение суток. Требуется так организовать расписание работы про­давцов, чтобы их общее количество (и соответственно расходы на оплату их труда) было минимальным.

Время суток	Требуемое количество продавцов
0-4
4-8
8-12
12-16
16-20
20-24

Математическая формулировка задачи

Допустим, что продавцы в магазине работают по 8 часов (в смену).

В соответствии с данными задачи количество требуемых продав­цов меняется через 4 часа. Если предположить, что в первую смену работает XI продавцов, во вторую — Х2 и т. д., то график работы про­давцов можно представить следующим рисунком.

Жирные линии означают смены, которые начинаются через 4 часа и продолжаются 8 часов. Смены перекрываются, т. е., напри­мер, с 4 до 8 часов в торговом зале присутствуют (XI + Х2) продав­цов, с 8 до 12 часов — (Х2 + ХЗ) продавцов, а с 0 часов до 4 работа­ют (XI + Х6) продавцов. Этот «скользящий» график и образует рас­писание смен.

XI - Х6 определяют изменяемые (варьируемые) переменные, кото­рые следует определять из условия минимального общего количества продавцов, т. е. целевая функция в этой задаче определяется выраже­нием

: (Xl+X2+X3+X4+X5+x6)=>min.

В качестве ограничений при этом будут выступать условия: Х1+Х6>=2; Х1+Х2>=2; Х2+Х3>=5; Х3+Х4>=7; Х4+Х5>=7; Х5+Х6>=4.

Кроме того, (XI - Х6) должны быть целыми и положительными. Такая структуризация может быть реализована, например, в сле­дующей электронной таблице.

Часть 1. Поиск решений на электронных таблицах

57

Здесь столбцы А, В, С, F определяют исходные данные, столбец D — изменяемые ячейки, столбец Е — зависимые ячейки, реализую­щие математическую формулировку задачи. Ячейка F8 — целевая. Ограничения: E2:E7>=F2:F7; E2:E7 — целые и неотрицательные.