Задача об оптимальном плане выпуска стульев

Суть задачи такова. Мебельная фабрика может выпускать стулья двух типов ценою в 8 и 12 условных единиц (у. е.11). Под этот заказ выделены материальные и людские ресурсы — известно, сколько досок, ткани и времени идет на изготовление каждого стула (табл. 3.1).

Таблица 3.1. Данные для задачи об оптимальном плане выпуска стульев

Спрашивается, как нужно спланировать производство стульев, чтобы наделать их либо количеством, либо ценой поболее. Решение этой задачи представлено на рис. 3.18 и 3.19.

Данная задача относится к широкому классу под названием "задачи линейного программирования": необходимо установить план (программу!) выпуска изделий (у нас это стулья), ориентируясь на целевую функцию (у нас их две — общее количество и общая стоимость стульев) и принимая во внимание ограничения (ресурсы по доскам, ткани и человеко-часам).

Примечание

"Линейного" — значит, что и целевая функция, и ограничения от переменных задачи зависят линейно. "Программирование" не имеет прямого отношения к программированию в современном понимании этого слова. Здесь другой смысл — программа (план) выпуска продукции.

Рис. 3.18. Попытка решения задачи целочисленного линейного программирования

На рис. 3.18 показана попытка решения задачи о стульях с помощью функции Maximize. Она оказалась не вполне удачной: Mathcad, а точнее, функции

Maximize и Minimize не способны решать целочисленные задачи, т. е. такие, где в списке ограничений стоит ограничение на целочисленность искомых переменных.

На рис. 3.19 сделана попытка спасти решение, показанное на рис. 3.18. В список ограничений введено ограничение на целочисленность: Стул: = Floor (Стул1,шт) — переменная Стул1 должна быть равна своей целой части. После этой вставки решение было выдано целочисленное (1 и 122 стула). Но самое ли оно оптимальное (стоимость стульев равна 1472 $)? Ответ на этот вопрос хранится на рис. 3.19.

Рис. 3.19. Попытка спасения решения задачи целочисленного линейного программирования

На рис. 3.20 показано решение задачи о плане (программе) выпуска стульев методом перебора — анализа матрицы цена, хранящей стоимости вариантов выпуска стульев при выполнении ограничений — если одно из ограничений не соблюдается, то соответствующий элемент матрицы цена становится нулевым. Встроенная в Mathcad функция match в задаче о стульях вернула нам два решения задачи, при которой цена стульев (20 и 112 шт.; 17 и 114 шт.) будет максимальной — 1504 $. Так что решение, показанное на рис. 3.18 (1 и 122 стульев), было не оптимальным.

Внизу рис. 3.20 можно увидеть, как расходуются ресурсы (что остается лишним — доски, ткань и/или рабочее время) при найденных двух планах —-производственных программах изготовления стульев.

Задачи, показанные на рис. 3.15—3.20— простенькие, но очень, если так можно выразиться, жизненно важные. На каждом шагу приходится что-то оптимизировать (расходы, например), принимая во внимание всякого рода ограничения (доходы!). Можно привести такой пример. После часа пик (скажем, в зимнее утро) расход электроэнергии падает, и необходимо снижать нагрузку электрогенераторов. Как это делать? Можно отключить отдельные генераторы, а можно оставить их в работе, изменив нагрузку. Диспетчер энергосистемы дает соответствующие команды, ориентируясь на некие целевые функции: средний расход топлива по системе, выброс с дымовыми газами вредных веществ в атмосферу, износ оборудования, степень готовности электростанций и дальше менять нагрузку и т. д.

Рис. 3.20. Решение задачи целочисленного линейного программирования

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

Вот еще примеры. Когда нужно убирать пшеницу? Пораньше — зерно еще не вызрело. Попозже — часть зерна уже осыпалась. Сколько и каких акций стоит купить на ограниченную сумму денег, чтобы будущий дивиденд был максимален? В каких средствах массовой информации стоит размещать рекламу на выделенные по смете деньги, чтобы эффект от нее был максимален, и т. д. и т. п.?