Данная задача формулируется следующим образом. Имеется квадратная заготовка из некоторого гибкого материала, например, картона или жести, причем размеры этой заготовки фиксированы для конкретной ситуации (Рис. 1. а). Из этой заготовки следует вырезать четыре равных квадрата по её углам, а полученную фигуру (Рис. 1. б) согнуть так, чтобы получилась коробка без верхней крышки (Рис. 1. в). При этом необходимо так выбрать размер вырезаемых квадратов, чтобы получилась коробка максимального объема.

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

В то же время на выбор размера вырезаемых квадратов оказывает влияние ограничение размера исходной заготовки. Действительно, если вырезать квадраты со стороной, равной половине стороны исходной заготовки, то задача теряет смысл. Сторона вырезаемых квадратов также не может превышать половину стороны исходной заготовки, поскольку это невозможно из практических соображений. Из этого следует, что в постановке данной задачи должны присутствовать некоторые ограничения.

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

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

Для математической постановки данной задачи необходимо ввести в рассмотрение некоторые параметры, характеризующие геометрические размеры коробки. С этой целью дополним содержательную постановку задачи соответствующими параметрами. С этой целью будем рассматривать квадратную заготовку из некоторого гибкого материала, которая имеет длину стороны L (Рис. 2). Из этой заготовки следует вырезать четыре равных квадрата со стороной r по ее углам, а полученную фигуру согнуть, так чтобы получилась коробка без верхней крышки. Задача состоит в таком выборе размера вырезаемых квадратов, чтобы в результате получилась коробка максимального объема.

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

Целевой функцией является объем полученной коробки. Поскольку длина стороны основания коробки равна: L — 2r, а высота коробки равна r, то ее объем находится по формуле: V(r) = (L — 2r)² * r. Исходя из физических соображений, значения переменной r не могут быть отрицательными и превышать величину половины размера исходной заготовки Z, т. е. 0,5 * L.

При значениях r = 0 и r = 0,5L соответствующие решения задачи о коробке являются вырожденными. Действительно, в первом случае заготовка остается без изменения, а во втором случае она разрезается на 4 одинаковых части. Поскольку эти решения имеют физическую интерпретацию, задачу о коробке для удобства ее постановки и анализа можно считать задачей оптимизации с ограничениями типа нестрогих неравенств.

С целью унификации, обозначим переменную через х = r, что не оказывает влияния на характер решаемой задачи оптимизации. Тогда математическая постановка задачи о коробке максимального объема может быть записана в следующем виде: f(x) = x * (L - 2x)² → max, где Δβ = {X ∈ R¹ | 0 ≤ x ≤ 0,5 * L}.

Целевая функция данной задачи является нелинейной, поэтому задача о коробке максимального размера относится к классу задач нелинейного программирования или нелинейной оптимизации.

Решение задачи о коробке максимального объема с помощью программы MS Excel

Не уменьшая общности математической постановки задачи, предположим: L = 1. Для решения данной задачи с помощью программы MS Excel создадим новую книгу с именем Нелинейная Оптимизация и изменим имя ее первого листа на Задача о коробке. Сделаем необходимые надписи в ячейках А1:В2. После этого введем в ячейку С2 формулу: =C1*(1-2*C1)^2, которая представляет целевую функцию. Внешний вид рабочего листа MS Office Excel с исходными данными для решения задачи о коробке максимального объема имеет следующий вид (Рис. 3).

При изображении исходных данных для решения задачи о коробке максимального объема (Рис. 3.) выбран режим отображения формул в ячейках рабочего листа, что оказывается весьма удобным для визуального контроля правильности задания выражений для соответствующих формул. Этот режим может быть установлен с помощью выполнения операции главного меню: Формулы → Показать формулы. С помощью удаления этой отметки можно вернуться к обычному режиму изображения ячеек рабочего листа.

Для дальнейшего решения задачи следует воспользоваться инструментом поиска решения программы MS Office Excel. С этой целью необходимо выполнить операцию меню: Данные → Поиск решения.

Следует заметить, что при первоначальном обращении к инструменту поиска решения можно не обнаружить в меню Данные операции Поиск решения. Это означает, что компонент поиска решения в программе MS Office Excel не установлен. Поэтому для продолжения работы необходимо предварительно установить данный компонент, для чего следует выполнить операцию главного меню: Файл → Параметры → Надстройки и установить отметку в строке с именем Поиск решения.

После вызова инструмента поиска решения появится диалоговое окно мастера задания параметров для нахождения решения (Рис. 4). Ввиду важности этого инструмента следует более подробно остановиться па элементах его диалоговых окон.

Первое диалоговое окно Поиск решения (Рис. 4) имеет следующие элементы:

• поле Оптимизировать целевую функцию — используется для задания ссылки на ячейку, в которой задана формула с выражением целевой функции решаемой задачи оптимизации;
• переключатели в группе До: — определяют характер решаемой задачи оптимизации. Для нахождения решения с максимальным значением целевой функции этот переключатель ставится в положение максимальному значению, для нахождения решения с минимальным значением — в положение минимальному значению. Наконец, для нахождения решения, при котором целевая функция принимает некоторое фиксированное значение, переключатель ставится в положение Значению, справа от которого можно ввести требуемое фиксированное значение;
• поле Изменяя ячейки переменных — служит для указания ячеек, которые должны изменяться в процессе поиска решения задачи. Именно в этих ячейках должны находиться переменные решаемой задачи оптимизации;
• в многострочном поле В соответствии с ограничениями отображаются ограничения решаемой задачи оптимизации;
• кнопка Добавить — служит для вызова дополнительного окна Добавление ограничения (Рис. 5);
• кнопка Изменить — служит для вызова дополнительного окна Добавление ограничения, в котором будет отображено ограничение, выбранное в многострочном поле Ограничения;
• кнопка Удалить — служит для удаления ограничения, выбранного в многострочном поле Ограничения;
• кнопка Выполнить — служит для запуска процесса нахождения оптимального решения после спецификации всех параметров поиска решения;
• кнопка Сбросить — служит для сброса всех параметров поиска решения;
• кнопка Загрузить / сохранить — служит для загрузки сохраненных условий ограничений или сохранения условий ограничения;
• кнопка Выполнить — служит для запуска процесса нахождения оптимального решения после спецификации всех параметров поиска решения;
• кнопка Параметры — служит для вызова дополнительного окна Параметры поиска решения (Рис. 3.5) для спецификации дополнительных параметров поиска решения, часть которых уже задана по умолчанию.

Диалоговое окно Добавление ограничения (Рис. 5) предназначено для задания одного ограничения и имеет следующие элементы:

• поле Ссылки на ячейки — служит для указания ячейки или диапазона ячеек, в которых содержится левая часть задаваемого ограничения;
• выпадающий список в центре окна — содержит перечень знаков неравенств ограничений, а также возможность спецификации требования целочисленности или двоичных значений переменных. Мастер поиска решений допускает спецификацию ограничений в виде равенств и неравенств;
• поле Ограничение — служит для указания ячейки, диапазона ячеек или конкретного числа, которое специфицирует правую часть задаваемого ограничения;
• кнопка ОК — служит для добавления ограничения к параметрам поиска решения и закрытия окна Добавление ограничения;
• кнопка Отмена — для закрытия окна Добавление ограничения без добавления ограничения к параметрам поиска решения;
• кнопка Добавить — для добавления ограничения к параметрам поиска решения без закрытия окна Добавление ограничения;
• кнопка Справка — служит для получения справочной информации об элементах диалогового окна Добавление ограничения.

Диалоговое окно Параметры поиска решения (Рис. 3.5) предназначено для спецификации дополнительных параметров нахождения решения или изменения уже заданных параметров. Следует заметить, что значения большинства этих параметров, используемых по умолчанию, подходят для решения типовых задач оптимизации. Диалоговое окно Параметры поиска решения имеет следующие элементы.

• Поле Максимальное время служит для ограничения времени, отпускаемого на поиск решения задачи. В это поле можно ввести время (в секундах), не превышающее 32 767. Установленное по умолчанию значение 100 подходит для решения рассматриваемых типовых задач.
• Поле Число итераций служит для ограничения времени решения задачи посредством задания некоторого предельного числа промежуточных вычислений. Установленное по умолчанию значение 100 подходит для решения рассматриваемых типовых задач.
• Флажок Показывать результаты итераций служит для приостановки поиска решения для просмотра результатов отдельных итераций.
• Флажок Автоматическое масштабирование служит для включения автоматической нормализации входных и выходных значений, качественно различающихся по величине, — например, максимизация прибыли в процентах по отношению к вложениям, исчисляемым в миллионах рублей.

Продолжим решение задачи о коробке максимального объема. В первом окне мастера поиска решения следует в поле с именем Установить целевую ячейку указать ячейку $С$2, в которой содержится формула для расчета целевой функции задачи, а в поле е именем Изменяя ячейки ввести абсолютный адрес ячейки $C$1, в которую будет записано искомое решение задачи.

После этого следует добавить два ограничения на допустимые значения переменной. Для этого следует нажать кнопку Добавить, в результате чего появится дополнительное окно задания ограничений (Рис. 7). Для ввода адресов ячеек в левую часть ограничения предназначено поле е именем Ссылка на ячейку. Форма неравенства ограничения выбирается из вложенного списка в средней части окна.

Наконец, для задания правой части ограничений в поле ввода с именем Ограничение следует ввести с клавиатуры следующие числа: 0,5 — для первого ограничения и 0 — для второго. После спецификации каждого из ограничений их необходимо включить в модель расчета, для чего следует нажать кнопку Добавить или ОК. Для того чтобы закрыть дополнительное окно задания ограничений и вернуться в исходное окно мастера поиска решения, следует нажать кнопку Отмена или ОК.

Остальные параметры мастера поиска решения, для редактирования которых предназначено дополнительное второе окно этого мастера, можно оставить без изменения. Окончательный внешний вид диалогового окна мастера поиска решения после задания необходимой информации изображен на Рис. 7.

Для редактирования некоторого ограничения его следует выделить в многострочном поле с именем Ограничения и нажать кнопку с именем Изменить. В этом случае появится дополнительное окно, аналогичное изображенным на Рис. 7, в котором можно выполнить необходимые действия по редактированию выбранного ограничения.

После задания необходимых параметров поиска решения можно приступить к выполнению численных расчетов, для чего следует нажать кнопку Выполнить. После выполнения численных расчетов программой MS Excel практически мгновенно будет получено количественное решение, которое имеет следующий вид (Рис. 8).

Интерпретируя полученные количественные значения, можно прийти к следующему заключению. Результатом решения является оптимальное значение стороны вырезаемого квадрата: ropt = 0,166666693977061, при котором изготовленная коробка будет иметь максимальный объем: Vmax = 0,0740740740740726. Напомним, что это решение соответствует длине стороны исходной заготовки, равной 1.

При выполнении расчетов для ячеек С1:С2 был выбран числовой формате 15 знаками после запятой. Это можно рассматривать в качестве предельного случая, поскольку реально подобная точность может потребоваться весьма редко. Тем не менее, анализ вычислительной точности методов нахождения решений данной задачи оптимизации программой MS Excel основывается на сравнении найденного решения и аналитического приближенного решения (см. Рис. 4) с максимальным количеством значащих цифр.

Полученное решение имеет общий характер, поскольку в любом конкретном случае для получения решения рассматриваемой задачи оптимизации значение L следует умножить на найденное значение r_opt. Например, если L = 2, то для получения коробки максимального объема следует вырезать по углам исходной заготовки квадраты со стороной 0,166666693977061 * 2 = = 0,333333387954122 м.

Таким образом, задача о коробке максимального объема в каждом конкретном случае может быть решена простой подстановкой в расчетную формулу r_opt = 0,166666693977061 * L конкретного значения величины L. Допустимая точность решения задается в каждом конкретном случае, исходя из специфики задачи и соответствующей проблемной области.

Получение решения задачи оптимизации в виде расчетной формулы вообще говоря, делает излишним использование программы MS Excel для решения конкретных задач данною типа. Тем не менее, из методических соображений процесс получения данного решения с помощью программы MS Excel рассмотрен достаточно подробно, поскольку он может быть использован для решения аналогичных задач нелинейной оптимизации.

Для анализа найденного решения можно построить график целевой функции и визуально оценить его корректность. С этой целью на отдельном рабочем листе е помощью операции автозаполнения ячеек зададим последовательный ряд чисел исходной переменной r в диапазоне от 0 до 1 с интервалом 0.01, которые запишем в ячейки с адресами А2:А52. Рядом в ячейки В2:В52 запишем соответствующие значения целевой функции. Для этого можно записать формулу: =A2*(1-2*A2)^2 в ячейку В2 и с помощью операции автозаполнения «протащить» содержание этой ячейки на диапазон В3:В52.

После этого для построения графика целевой функции для задачи о коробке следует воспользоваться мастером диаграмм. Построенный график целевой функции будет иметь следующий вид как на Рис. 9. Визуальный анализ этого графика показывает, что максимум целевой функции находится между значениями х = 0,16 и х = 0,17. Этот факт можно также проверить, сравнив значения в ячейках В18 и В19. Тем самым, можно сделать вывод о корректности полученного результата решения данной задачи оптимизации.

Аналитическое решение задачи о коробке максимального объема

Поскольку задача о коробке максимального объема имеет достаточно простое аналитическое решение, оно приводится для дополнительной проверки правильности численных расчетов программы MS Excel.

Прежде всего, следует заметить, что целевая функция является непрерывной и дифференцируемой на всем интервале ее задания, включая множество допустимых альтернатив Δ_β, которое, в свою очередь, является замкнутым. Как следует из курса математического анализа, непрерывная функция на замкнутом множестве достигает своих экстремальных значений, из которых нас интересуют точки максимума данной функции. Для нахождения экстремума аналитическим способом следует определить первую производную целевой функции и отыскать ее корни.

Первая производная функции: f(x) = x*(1-2x)² равна df(x)/dx = 12x²-8x+1. Соответствующее уравнение: 12x²-8x+1=0 является квадратным, которое имеет два корня: Х = 1/6 и х2 = 1/2. Анализ графика целевой функции (см. Рис. 3.5) показывает, что максимальному значению этой функции соответствует первый корень. Данное значение является допустимым и служит точным аналитическим решением задачи оптимизации о коробке максимального размера.

Таким образом, ropt = 1/6. Поскольку число 1/6 является иррациональным и представляет собой периодическую дробь 0.16(6), при желании можно получить его любое приближение произвольной точности. Сравнивая найденное ранее значение 0,166666693977061 с соответствующим округлением точного значения, можно получить относительную погрешность программы MS Excel. Это значение равно: 0.000016382137877% и свидетельствует о том, что решение задач оптимизации программой MS Excel с гладкой целевой функцией выполняется весьма эффективно.