Пример: оптимальная раскройка листа

Рассмотрим пример практической задачи оптимизации. В углах квадратного листа железа, сторона которого равна 1 м, вырезают четыре квадрата со стороной x. Затем складывают получившуюся развертку (по штриховым линиям на рисунке), сваривают швы и таким образом получается бак:

Требуется выбрать размер выреза x так, чтобы получился бака наибольшего объема.

Для того, чтобы грамотно поставить задачу оптимизации, нужно

1. определить целевую функцию: в данном случае выразить объем бака через неизвестную величину x;

2. задать ограничения на возможные значения x.

Легко видеть, что основание получившегося бака – это квадрат со стороной z, а его высота равна x. Однако, величина z зависит от x и равна , поэтому объем бака вычисляется по формуле , это и есть целевая функция, для которой нужно найти максимум.

Понятно, что x не может быть меньше нуля. С другой стороны, x не может быть больше, чем половина стороны исходного листа (0,5 м), поэтому ограничения запишутся в виде двойного неравенства: . Заметим, что при и объем бака равен нулю (в первом случае равна нулю высота, во втором – площадь основания).

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

(Ответ: )

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

В стандартной поставке OpenOffice Calc модуль оптимизации работает только для линейных функций. Для того, чтобы решить рассмотренную выше задачу с баком, нужно установить расширение Solver for Nonlinear Programming (extensions.services.openoffice.org/project/NLPSolver) и в параметрах модуля оптимизации выбрать один из методов нелинейной оптимизации. В табличном процессоре Excel оптимизация выполняется с помощью стандартной надстройки «Поиск решения».

Сначала построим график функции, как мы делали это при решении уравнения.

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

Выделим в таблице две ячейки (например, E2 и F2), в первую запишем начальное приближение (0,2), а во вторую – формулу для вычисления объема для этого значения x:

Задача оптимизации формулируется в виде «найти максимум (или минимум) целевой функции в ячейке …, изменяя значения ячеек … при ограничениях …». В нашей задаче целевая ячейка – F2 (нужно найти ее минимум), изменяемая ячейка – E2.

Выбираем в верхнем меню пункт «Сервис – Поиск решения», в появившемся окне вводим адреса целевой и изменяемой ячеек (для этого можно установить курсор в нужное поле ввода и щелкнуть по ячейке) и ограничения:

После щелчка по кнопке «Решить» в ячейке E2 будет записано оптимальное значение x, а в целевой ячейке – соответствующее (максимальное) значение объема.

Надстройка «Поиск решения» позволяет

• находить максимум или минимум целевой функции;

• решать уравнения, задавая желаемое значение целевой функции;

• использовать несколько изменяемых ячеек и диапазонов, например запись

A2:A6;B15

в списке изменяемых ячеек означает «изменять все ячейки диапазона A2:A6 и ячейку B15»;

• использовать ограничения типа «меньше или равно», «больше или равно», «равно», «целое» и «двоичное» (только 0 или 1).

Кнопка «Параметры» позволяет опытным пользователям менять настройки алгоритма оптимизации.

1. Что такое оптимизация?

2. Что такое целевая функция?

3. Какое решение называется оптимальным?

4. Почему выражение «самый оптимальный» безграмотно?

5. Что можно сказать о рекламной фразе «Этот крем обеспечивает оптимальный цвет лица»?

6. Зачем нужны ограничения в задаче оптимизации?

7. В чем разница между понятиями «локальный минимум» и «глобальный минимум»?

8. Что такое начальное приближение?

9. Почему результат решения задачи оптимизации чаще всего зависит от выбора начального приближения?

10. Объясните принцип работы метода дихотомии.

11. Обязательно ли при использовании метода дихотомии брать пробные точки симметрично относительно середины отрезка? Ответ обоснуйте.

12. Когда метод дихотомии не будет работать (может выдать неверный ответ)?

13. Подумайте, можно ли задачу решения уравнения сформулировать как задачу оптимизации.

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

2. *Напишите программу, которая реализует метод «золотого сечения» (на каждом шаге вычисляется только одно значение функции).

3. *Банка имеет форму цилиндра³, полная площадь ее поверхности (боковая поверхность и два круга-основания) равна 100 см². Определите радиус и высоту банки, которая при этих условиях имеет максимальный объем.

4. *Банка имеет форму цилиндра, ее объем равен 500 см³. Определите радиус и высоту банки, которая при этих условиях имеет минимальную площадь полной поверхности.

5. Фирма «Рога и копыта» хочет провести рекламную кампанию в газетах. Данные о цене рекламного объявления и тиражах газет внесены в таблицу:

Газета	Тираж	Цена 1 объявл.	Объявлений	Расходы	Охват
Ведомости	10000	1000р.	1	1000 р.	10000
Туризм	3500	570р.	2	1140 р.	7000
Спорт	6000	700р.	3	2100 р.	18000
Правда	20000	1250р.	4	5000 р.	80000
Всего				9240 р.	115000

В каждую газету нужно дать не менее одного и не более 6 объявлений. С помощью надстройки «Поиск решения» табличного процессора определите, сколько объявлений нужно дать в каждую газету, чтобы обеспечить общий охват не менее 200000 человек и при этом израсходовать как можно меньше денег.

6. В условиях предыдущей задачи определите, сколько объявлений нужно дать в каждую газету, чтобы обеспечить наибольший общий охват и при этом израсходовать не более 15 000 рублей.