Решение задач оптимизации

Команда Сервис ® Поиск решения… предоставляет пользователю следующие возможности:

· поиск безусловных экстремумов функции одного или нескольких аргументов;

· поиск экстремумов функции одного или нескольких аргументов при наличии ограничений на найденное решение;

· поиск аргументов, при которых функция примет нулевое значение;

· выбор метода решения поставленной задачи;

· ввод ограничений на точность и время выполнения задачи.

Эти возможности реализуются с помощью параметров, собранных в основном окне Поиск решения и дополнительном – Параметры поиска решения. Дополнительное окно вызывается кнопкой <Параметры> из основного. Кнопка <Справка> вызывает окно с разъяснением смысла каждого параметра и возможностей, которые предоставляются при его заказе.

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

f₁(x₁, x₂, …, x_n) = 0; f₂(x₁, x₂, …, x_n) = 0; …. f_n(x₁, x₂, …, x_n) = 0

составляют вспомогательную целевую функцию

S = f₁² + f₂² + … f_n².

S – неотрицательная функция. Ее минимальное значение равно нулю и достигается только тогда, когда все слагаемые одновременно равны нулю. А это и есть решение исходной задачи.

Рассмотрим в качестве примера систему двух нелинейных уравнений

x² + y² = 3; 2x + 3y = 1.

Введем исходные данные по плану, представленному в табл. 6.7.1. Для удобства дальнейшей работы можно провести форматирование введенной информации.

Таблица 6.7.1

Ячейки	Информация	Значение
А1	Заголовок расчета	Решение системы нелинейных уравнений
А2	Заголовок	Переменные
А3:В3	Название переменных	А3: Х, В3: Y
А4:В4	Начальные значения переменных	А3: 1, В3: –1
А5	Заголовок	Функции системы
А6:В6	Названия функций системы	А6: f1, B6: f2
А7:В7	Формулы для расчета функций	=A4^2+B4^2–3 =2*A4+3*B4–1
А8	Заголовок	Вспомогательная целевая функция
А9	Формула целевой функции	=A7^2+B7^2

Вызовем команду Сервис ® Поиск решения… В окне Поиск решения установим следующие параметры:

· "Установить целевую ячейку:" А9;

· "Равной:" минимальному значению;

· "Изменяя ячейки:" А4:В4;

· нажмем кнопку <Параметры> и в дополнительном окне Параметры поиска решения проверим, что флажок "Линейная модель" не установлен. Закроем дополнительное окно кнопкой <ОК>;

· запустим команду кнопкой <Выполнить> основного окна.

Когда команда закончит работу, на экране автоматически появляется окно Результаты поиска решения. Пояснения к параметрам, представленным в нем, вызываются кнопкой <Справка>. Закажем, к примеру, параметры "Сохранить найденное решение" и "Тип отчета: результаты". В этом случае начальные значения переменных в ячейках А4:В4 заменятся на найденные и в таблицу будет вставлен новый лист "Отчет по результатам 1". Просмотрите отчет. Проверьте, какое значение приняла вспомогательная целевая функция в А9 при найденных решениях. Если она существенно отличается от нуля, то решение найдено неверно.

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

Задание

Составьте таблицу значений целевой функции

S = (x² + y² –3)² + (2x + 3y – 1)2

в диапазоне аргументов –3 < x < 3, – 3 < y < 3. Выберите 4–5 точек с наименьшими значениями функции, проведите поиск минимума, используя каждую из них в качестве начального приближения. В результате должно быть получено только два разных решения: х₁ = –1,268; у₁ = 1,179 и х₂ = 1, 576; у₂ = –0,717. Графически уравнения системы представляются окружностью и прямой линией. Система такого типа не может иметь больше двух точек пересечения.

Задачи технического и экономического планирования часто решаются методами линейного программирования. Особенность этих задач – большое количество исходных данных. Чтобы упорядочить их, полезно перед вводом данных в ЭВМ составить математическую модель задачи на бумаге. При этом можно руководствоваться следующим планом:

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

2. Определяемся с целью оптимизации, т. е. решаем, минимальное или максимальное значение критерия будет соответствовать наилучшему плану.

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

4. Составляем формулы ограничений, которые показывают, какие планы имеет смысл рассматривать при выборе оптимального.

Только после составления математической модели имеет смысл вводить информацию в ЭВМ.

Пример

Процесс изготовления двух видов изделий состоит в последовательной обработке каждого из них на трех станках. Возможности использования каждого из них ограничены 10-ю часами в сутки. Удельное время обработки и удельная прибыль для каждого изделия приведены в табл.6.7.2. Найти оптимальный план выпуска каждого изделия.

Таблица 6.7.2

Изделие	Время обработки одного изделия, мин	Прибыль на одно изделие, $
Станок 1	Станок 2	Станок 3
A
B

Составляем модель по предложенному выше плану:

1. Критерий оптимизации – общая прибыль (ОП), планируемые параметры – число запланированных к выпуску изделий каждого вида (k_A, k_В).

2. Цель оптимизации – максимальная прибыль.

3. Целевая функция – ОП = k_AП_А + k_BП_В, где П_А и П_В – удельные прибыли от продажи каждого вида изделий.

4. Ограничения – в этой задаче наложены ограничения только по времени использования в трудовом процессе каждого станка:

· Станок 1: t_A1k_A + t_B1k_B <= 600;

· Станок 2: t_A2k_A + t_B2k_B <= 600;

· Станок 3: t_A3k_A + t_B3k_B <= 600.

Здесь индексы показывают, какому станку и изделию соответствует удельная норма времени обработки. Например, t_B2 – норма времени обработки одного изделия В на станке 2.

На рис. 6.7.1 изображен пример расположения модели на рабочем листе Excel.

	A	B	C	D	E	F	G
	Изделие	Время обработки одного изделия, мин	Удельная прибыль	План выпуска изделий	Ожидаемая прибыль
	Станок 1	Станок 2	Станок 3
	A				$2
	B				$3
	Время по плану					Общая прибыль
	Допустимое время

Рис. 6.7.1

В ячейки F3, F4 вводится ориентировочный план. Можно оставить их пустыми. В ячейки G3, G4 вводятся формулы прибыли по каждому виду изделий, в ячейке G5 эти прибыли суммируются. В ячейки B5:D5 вводятся левые части формул ограничений.

После того, как все элементы модели занесены на рабочий лист, можно вызывать команду Сервис ® Поиск решения… В ее диалоговом окне для нашего примера следует установить такие значения параметров:

· "Установить целевую ячейку" – G5 (ячейка, в которой находится окончательное значение целевой функции).

· "Равной" – максимальному значению.

· "Изменяя ячейки" – F3:F4 (ячейки, в которых находятся планируемые параметры. После окончания работы команды в них будут записаны оптимальные значения).

· "Ограничения" – для заполнения этого окна надо нажать кнопку <Добавить>. В появившемся окне Добавление ограничения три поля. В левом указывают адрес ячейки, в которой сосчитана та часть ограничения, которая меняет значение для разных планов. В правом – должна стоять константа, с которой сравнивается значение левого поля при разных планах. Если она уже введена на рабочий лист, здесь можно указать ее адрес. Для нашего примера в левое поле вводим В5, в правое – В6, в центральном поле устанавливаем соотношение <=. Нажимаем кнопку <Добавить>. Повторяем аналогичные действия для ввода ограничений по второму и третьему станкам. После установки последнего ограничения вместо кнопки <Добавить> нажимают <ОК>. Если какие-то ограничения оказались лишними или введены неверно, это можно исправить кнопками<Удалить> и <Изменить>.

· Нажимаем кнопку <Параметры>. Появляется диалоговое окно Параметры поиска решения. Здесь оговариваются метод и точность решения. Для задач линейного программирования достаточно установить только параметры "Линейная модель" и "Неотрицательные значения", закрыть окно кнопкой <ОК> и нажать кнопку <Выполнить>.

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