11. Решение оптимизационных задач

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

Простейшим случаем такой задачи является определение корня нелинейного уравнения. Уравнение f (x) = 0 будет нелинейным, если в его правой части присутствует неизвестная в степени, отличной от 1, или имеются трансцендентные функции sin x, ln x и т.д. Для некоторых уравнений существуют методы, позволяющие получить точное решение (например, квадратное уравнение). Однако большинство из них не имеет точного аналитического решения. Чаще всего нелинейное уравнение имеет несколько корней, поэтому его приближённое решение состоит из двух этапов, на первом производится грубый подбор или отделение корня, то есть находятся все или хотя бы один отрезок, на котором есть корень, а на втором отделённый корень определяется с заданной точностью.

Проиллюстрируем решение на примере уравнения x ³+ 2x + 5 = 0.

Это уравнение может иметь 3 действительных корня. Напомним, что корень - это значение х, при котором правая часть уравнения равна 0. На первом этапе решения – отделим корни графическим методом, для чего рассчитаем таблицу значений функции Y=x³+2x+5 для х, изменяющегося от –3 до 3 с шагом 0,5, и построим её график в виде точечной диаграммы (Error: Reference source not found). Отрезок изменения переменной х выбирается произвольно, но так чтобы были видны все корни уравнения. Возможно, придется повторить выбор несколько раз, чтобы добиться этого.

Анализируя график (Error: Reference source not found), можно сделать следующие выводы:

• Уравнение имеет один действительный корень, поскольку график только один раз пересекает ось Х между значениями –2 и -1.

• Вместо первоначально выбранного отрезка от –3 до 3 для уточнения корня можно взять меньший отрезок от –2 до –1.

• Для уточнения решения используем два специальных средства – это «Подбор параметра» и «Поиск решения». Чтобы использовать средство «Подбор параметра», были произведены следующие действия:

• В ячейку С5 было записано граничное значение х – 2 , а в ячейки D5 -формула для расчета функции ( =C5^2+2*C5+5).

• В

  

  Рисунок 31 - Использование средства «Подбор параметра» для решения нелинейного уравнения

  ыполнена команда «Подбор параметра» меню «Сервис». В появившемся окне (Рисунок 31) указаны: адрес функции (поле « Установить в ячейке»); значение, которому должна стать равна функция (поле «Значение»); адрес аргумента (поле «Изменяя значение ячейки»). После щелчка по кнопке «ОК» производится подбор подходящего значения аргумента (-1,328), которое записывается в ячейку С5 , при этом в ячейке D5 появится значение функции 0,000. Это говорит о том, что подбор прошёл успешно и корень равен -1,328.

Чтобы использовать средство «Поиск решения», были выполнены следующие действия:

• В ячейки С10 было записано граничное значение х – 2 , а в ячейке D10 - формула для расчета функции ( =C10^2+2*C10+5).

• Выполнена команда «Поиск решения» меню «Сервис».

В появившемся окне «Поиск решения» (Рисунок 32) указан адрес функции (поле «Установить целевую»), значение которого должна достигнуть функция (опция и поле «Значение»), адрес аргумента (поле «Изменяя ячейки»). Кроме того, в список «Ограничения» добавлены ограничения, задающие отрезок изменения аргумента (ячейка С10) от –2 до -1. После щелчка по кнопке «Выполнить» производится поиск решения путем поиска подходящего значения аргумента (-1,328), которое записывается в ячейку С10 , при этом в ячейке D10 появляется значение функции 0,000. Это говорит о том, что поиск решения прошёл успешно и корень равен -1,328. В окнах «Поиск решения» и «Добавление ограничения» показаны абсолютные адреса, появившиеся в соответствующих полях после щелчка по ячейке. Для корректировки ограничений используются кнопки: «Добавить», «Изменить» и «Удалить». Две первые вызывают окно «Добавление ограничения», здесь указываются адрес ячейки с формулой, значение которой ограничивается (поле «Ссылка на ячейку:»), ограничивающий знак (раск

Рисунок 32 - Использование средства «Поиск решения» для уточнения корня нелинейного уравнения

рывающийся список знаков) и значение (адрес ячейки со значением), с которым происходит сравнение (поле «Ограничение:»). В качестве ограничивающего знака могут использоваться операции сравнения: >=, <=, = или слова: «цел» или «двоич», в этом случае ячейка, указанная в ссылке, может принимать только целые или двоичные значения соответственно и поле «Ограничение» не заполняется. Например, в окне «Добавление ограничения» (Рисунок 32) показан процесс создания первого ограничения(x <= -1). Кнопки: «ОК», «Отмена», «Добавить» этого окна используются, когда последнее ограничение создано, процесс создания ограничения нужно прервать, нужно перейти к созданию следующего ограничения соответственно.

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

Первая задача может быть сформулирована, например, так: предприятие выпускает 3 вида кондитерских изделий. Известны: количество продуктов необходимое выпуска каждого изделия (Таблица 19), прибыль от выпуска каждого изделия: Кекс - 110, Торт – 75, Пирог - 45. Найти количество изделий каждого вида, необходимое для получения максимальной прибыли.

Таблица 19 - Исходные данные для задачи планирования производства

Ресурс (продукт)	Расход ресурса на одно изделие			Наличие ресурса
	кекс	торт	пирог
Мука	3,2	2,1	1,1	600
Масло	0,8	0,5	0,3	150
Сахар	0,7	0,5	0,3	150
Дрожжи	0,2	0,15	0,1	40

Приведём математическую постановку задачи. Введём следующие обозначения:

Х₁ – выпуск кексов; Х₂ – выпуск тортов; Х₃ – выпуск пирогов;. Прибыль от реализации одного кекса составит 110 руб., а от реализации Х₁ кексов Х₁*110 руб. Прибыль от реализации одного торта составит 75 руб., а от реализации Х₂ тортов Х₂*75 руб.. Аналогично от реализации одного пирога 45 руб. а от реализации Х₂ пирогов Х₃*45 руб. Тогда прибыль, полученная от реализации кексов, тортов и пирогов, составит: Х₁*110 + Х₂*75 + Х₃*45. Она должна стремиться к максимуму. Однако стать ей максимально большой не дадут различные ограничения. Чаще всего это ограничения на ресурсы. Мы не можем израсходовать ресурса больше, чем его лимит. Например, нельзя израсходовать больше 600 кг муки. Так на изготовление одного кекса тратиться 3,2 кг(Таблица 11), а на изготовление Х₁ кексов Х₁*2,1 кг.. На изготовление одного торта тратиться 2,1 кг, а на изготовление Х₂ тортов Х₂*2,1 кг. Аналогично на изготовление Х₂ пирогов - Х₂*1,1 кг муки. Норма расхода на изделия и ограничения в предложенных задачах приведены в одних и тех же единицах измерения, поэтому в дальнейшем не будем их указывать. Тогда общий расход муки составит Х₁*3,2 + Х₂*2,1 + Х₃*1,1, и он не должен превысить 600. Рассуждая таким же образом, составим все ограничения по расходу:

Муки: Х₁*3,2 + Х₂*2,1 + Х₃*1,1  600

Масла: Х₁*0,8 + Х₂*0,5 + Х₃*0,3  150

Сахара: Х₁*0,7 + Х₂*0,5 + Х₃*0,3  150

Дрожжей: Х₁*0,2 + Х₂*0,15 + Х₃*0,1  40

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

Для её решения, представленного ниже (Рисунок 33 и Рисунок 34), были созданы две расчётные таблицы: «План производства» и «Расход ресурсов»(Рисунок 33).

В первой таблице заполняются строки:

• «Количество» - произвольными цифрами, например, единицами. Вместо них после вызова и выполнения режима «поиск решения» появляются значения, являющиеся решением задачи.

• «Прибыль» - формулами, вычисляющими её как произведение количества на цену, а в ячейке «Общая прибыль» суммируется прибыль от каждого вида изделий.

Во второй таблице каждая ячейка столбца «Общий расход» рассчитывается как сумма произведений количества каждого изделия на расходсоответствующего ресурса. Например, для ресурса «Мука» формула, записанная в ячейке Е8, выглядит так: =СУММПРОИЗВ($B$3:$D$3;B8:D8). Абсолютная адресация блока ячеек B3:D3 используется для того, чтобы эту формулу можно было копировать в ячейки с Е9 по Е11.

А затем вызвано окно «Поиск решения» (Рисунок 34), в котором в качестве целевой функции выбрана ячейка с итоговой прибылью, указано направление оптимизации (опция «максимальному значению»), заданы изменяемые ячейки и ограничения. Изменяемыми будут ячейки, где указано количество изделий каждого вида, они могут быть только целыми и неотрицательными – первая и вторая строка ограничений. Кроме того, общий расход каждого из ресурсов (графа «Общий расход») не может превышать его наличия (графа «Наличие ресурса») - третья строка ограничений.

Т

Рисунок 34 - Использование средства «Поиск решения» для решения задачи планирования производства

аким образом использование средства «Поиск решения» позволило найти оптимальный план производства предприятия (Рисунок 33) это: 137 кексов, 51 торт и 49 пирогов, его выполнение позволит получить прибыль 21100 руб. Причём расходуются полностью почти все ресурсы (только по ресурсу сахара остался небольшой резерв). Решение проиллюстрировано двумя диаграммами: первая показывает долю в прибыли каждого изделия (диаграмма с областями), а вторая – структуру изделия кекс ( круговая диаграмма).

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

Таблица 20 - Исходные данные для транспортной задачи

Затраты на перевозки		Потребители				Мощность завода
		стройка 1	стройка 2	стройка 3	стройка 4
Поставщики	ЖБИ-1	12	5	13	15	200
	ЖБИ-8	11	12	10	15	300
	Завод 3	14	15	8	20	400
Потребность стройки		100	150	200	450

Для её решения (Рисунок 35 и Рисунок 36) были созданы две расчётные таблицы: «План перевозок» и «Затраты на перевозки» (Рисунок 35).

В первой таблице заполняются:

• Ячейки С3:F5 - произвольными цифрами, например, единицами, вместо которых после вызова и выполнения режима «поиск решения» появляются числа, являющиеся решением задачи.

• Строка «Итого» и столбец «Всего» - формулами, суммирующими объёмы перевозок по каждому заводу и стройке. Например, формулы в ячейках G3 и C6 выглядят так: =СУММ(C3:F3) и =СУММ(C3:C5) соответственно.

В

	A	B	C	D			E	F		G	H
1	План перевозок		Потребители								Мощность завода
2			Стройка 1	Стройка 2		Стройка 3		Стройка 4		Всего
3	Поставщики	ЖБИ-1	0	150		0		50		200	200
4		ЖБИ-8	0	0		0		300		300	300
5		Завод 3	100	0		200		100		400	400
6		Итого	100	150		200		450
7	Потребность стройки		100	150		200		450
8	Затраты на перевозки		Потребители							Общие затраты на перевозки
9			Стройка 1		Стройка 2	Стройка 3			Стройка 4
10	Поставщики	ЖБИ-1	12		13	15			13
11		ЖБИ-8	11		10	15			10
12		Завод 3	14		8	20			8	11000

Рисунок 35 – Оформление решения транспортной задачи

о второй таблице ячейка «Общие затраты на перевозки» рассчитывается как сумма произведений объёма перевозки с каждого завода на каждую стройку на соответствующую стоимость перевозки. Формула, записанная в ячейке G14, выглядит так: =СУММПРОИЗВ(C3:F5;C10:F12).

Рисунок 36 - Использование средства

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

А затем вызвано окно «Поиск решения»(Рисунок 36), в котором в качестве целевой функции выбрана ячейка, где вычисляются общие затраты на перевозки, указано направление оптимизации (опция «минимальному значению»), заданы изменяемые ячейки и ограничения. Изменяемыми будут ячейки, где указан объём перевозки с каждого завода на каждую стройку, они могут быть только не отрицательными – первая строка ограничений. Кроме того, на каждую стройку нужно привести именно столько строительных конструкций, сколько нужно (соответствующие ячейки строк «Итого» и «Потребность стройки» равны), а с каждого завода вывести всю продукцию (соответствующие ячейки столбцов «Всего» и «Мощность завода» равны) – вторая и третья строки ограничений.После завершения решения была построена трёхмерная гистограмма (Рисунок 35), иллюстрирующая оптимальный план перевозок. Каждый её столбик - это объём перевозки с одного из заводов на одну из строек.