Тема урока: «Решение оптимизационных задач линейного и нелинейного программирования»

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

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

Для решения этой задачи надо использовать команду Сервис Подбор параметра.

Чтобы подобрать нужное значение, нужно:

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

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

4. В поле Значение указать значение, которое должно быть результатом формулы.

5. В поле Изменяя значение ячейки ввести координаты ячейки, значение которой Excel должен изменять.

7. В появившемся диалоговом окне щелкнуть по кнопке «ОК», если результат соответствует предъявленным требованиям; в противном случае щелкнуть по кнопке «Отмена» для возврата к исходным значениям ячеек.

Задачи для самостоятельного решения

Вы хотите положить деньги в банк под 4,5% и получить ровно 1000 руб. по истечении года. Необходимо определить сумму вклада.

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

Если в банк положить Х руб. под 4,5% годовых, то в конце года банк выплатит (1+0,045) * х = 1,045 * х. Поскольку в конце года по условию задачи нужно получить сумму 1000 руб., то для решения задачи требуется решить уравнение 1,054 * х = 1000.

Данные расположены на рабочем листе, как показаны ниже

Чтобы решить задачу, нужно выполнить следующие действия.

1. Сделать активной ячейку В3.
2. Вызвать средство Подбор параметра.
3. Проверить, что в поле Установить в ячейке диалогового окна Подбор параметра указана ссылка на ячейку В3.
4. В поле Значение ввести значение 1000.
5. В поле Изменяя значение ячейки указать ссылку на ячейку В2. 6. Нажать кнопку ок.

Средство Подбор параметра найдет решение, равное 956,94, и поместит это значение в ячейку В2.

Для покупки автомобиля Вам необходима сумма 200000 руб. У вас есть возможность взять 30-летнюю ипотечную ссуду со ставкой 8% годовых. При этом нужно сделать 20% взнос. Определить, какую сумму нужно взять в банке, чтобы на руки вы получили требуемую сумму.

Пусть в банке выдали х руб. (S₀). Первоначальный взнос (V) составляет 20% * х. Остается сумма S = S₀-V. Представим исходные данные, как показано на рисунке

Чтобы решить эту задачу, нужно установить курсор на ячейку D2 и воспользоваться командой Сервис / Подбор параметра. В диалоговом окне нужно указать следующую информацию:

С помощью средства Подбор параметра будет найден ответ: 250000 руб.

Хотя подбор параметра – относительно простая операция, использование процедуры поиска решения может оказаться более сложным.

Задача «Вычисление дохода»

Доход2Изделие А

13003Изделие В

18004Изделие С

53006СУММ(B2:B4)СУММ(D2:D4)

Вопрос: При каком количестве изделий мы получим максимальный доход?

Процедура поиска решения выполняется следующим образом

1. Введите в рабочий лист исходные данные и формулы.

2.Вызовите диалоговое окно Поиск решения (Сервис – Поиск решения)

3. Укажите целевую ячейку D5. Здесь вычисляется общая прибыль по трем видам изделий. Поскольку наша цель – максимизировать значение в этой ячейке, установите переключатель Равной максимальному значению.

4. Укажите изменяемые ячейки, которые в данном случае находятся в диапазоне B2:B4.

5. Дальше введите ограничения задачи. Ограничения добавляются по одному за один раз и отображаются в окне Ограничения. Для добавления ограничения щелкните по кнопке Добавить.

6. Теперь для выполнения процедуры поиска решения введены все исходные данные. Чтобы начать процесс поиска решения задачи, щелкните по кнопке Выполнить.

7. После решения вы сможете выбрать одну из следующих возможностей

— Заменить исходные значения в изменяемых ячейках на те, которые были найдены в результате решения задачи.
— Восстановить исходные значения в изменяемых ячейках.
— Создать несколько отчетов о процедуре поиска решения (для выбора нескольких отчетов из списка нажмите клавишу или щелкните на нужном типе отчета).
— Щелкнуть на кнопке Сохранить сценарий для сохранения решения в виде сценария, который может быть использован в среде Диспетчер сценариев.

Задача «Минимизация расходов на перевозку»

Задача «Планирование штатного расписания»

Вопрос: Какое минимальное количество служащих требуется для удовлетворения ежедневной потребности в работниках?

Ответ: Всего необходимо 192 рабочих

Задача «Распределение ресурсов»

Рассматриваемая нами компания производит пять видов игрушек, для которых используются 6 видов материала в различных количествах.

Необходимые материалы3МатериалИгрушка

EЕстьИспользованоОстаток4Красная краска010136255001255Голубая краска310106405001406Белая краска2120211007004007Пластик152218751100-2258Дерево30355220016006009Клей123231500110040010Доход на единицу$15$30$20$25$2511План выпуска10010010010010012Доход$1500$3000$2000$2500$250013Общий доход$11500

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

Задача «Оптимизация портфеля ценных бумаг»

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

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

Изменяемые ячейки – С5:С9, а цель задачи – максимизировать общий доход, указанный в ячейке D12.

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

Источник

Методы оптимальных решений

Пример про стирку

В нашей жизни часто возникают задачи, в которых нужно не просто найти «любое решение» (которое, как раз, достаточно легко найти), а «наилучшее» из возможных решений. Приведем пример. Допустим, у нас есть стиральная машина, в которую можно загрузить 6 килограмм белья. И есть наборы белья, весом 1,2,4,5,6 килограмм. Каждый набор необходимо стирать только целиком. Требуется составить программу стирки наилучшим образом.

Тут мы явно видим, что «какое-то» решение найти очень просто. Например, будем брать наборы белья по-порядку:

Номер стирки	Какие наборы берем в стирку	Сколько кг белья стираем в этот раз
1	1+2	3
2	4	4
3	5	5
4	6	6

Но нам-то нужно именно «лучшее» решение. Будет ли наше решение, в котором мы стираем 4 раза лучшим? А вдруг можно так перетасовать белье, чтобы стирать 3 раза? Или даже 2 раза? На самом деле, в 3 раза вполне можно уложиться:

Номер стирки	Какие наборы берем в стирку	Сколько кг белья стираем в этот раз
1	6	6
2	2+4	6
2	1+5	6

Задачи оптимизации

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

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

Как правило, такие задачи приходят к нам именно из жизни, как задача, приведенная выше. Среди самых распространенных задач оптимизации, пришедших из жизни можно выделить следующие.

Основные типы оптимизационных задач

Если задача математического программирования пришла из жизни, то ее решением занимается дисциплина «Исследование операций». Именно она решает задачи из вышеприведенного списка.

Линейное и нелинейное программирование

Кроме этого, задачи математического программирования делятся на два больших класса:

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

Источник

Решение оптимизационных задач методом поиска решения

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

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

Задача линейного программирования в общем случае формулируется следующим образом:

Определить максимум (минимум) целевой функции F_max(min) при заданной системе ограничений (2) и граничных условий (3):

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

Целевая ячейка – это ячейка, для которой нужно найти максимальное, минимальное или заданное значения.

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

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

Чтобы запустить процедуру поиска решения, надо:

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

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

Каждый отчет создается на отдельном листе текущей рабочей книги.

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

Рассмотрим применение процессора Excel для решения ЗЛП на примерах.

Задача 1. Планирование производства

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

МП выпускает товары х₁,х₂,х₃,х₄, получая от реализации каждого прибыль в 60,70,120,130 руб. соответственно. Затраты на производство приведены в таблице.

Затраты	х1	х2	x3	х4	Всего
Трудовые	1	1	1	1	16
Сырьевые	6	5	4	1	110
Финансы	4	6	10	13	100

Решение задачи средствами Excel состоит из 4 этапов:

Создание математической модели задачи

Составим математическую модель процесса по описанию задачи:

— целевая функция прибыли.

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

Для решения данной задачи c помощью программы MS Excel создадим новую книгу с именем Линейное программирование и изменим имя ее первого рабочего листа на Задача о производстве.

Создание формы

A	B	C	D	E	F	G	H
1	Переменная	х7	х2	x3	х4	Формула	Знак	Св.член
2	Значение
3	Коэф. ЦФ	60	70	120	130	=СУММПРОИЗВ(В$2:Е$2;В3:Е3)	Max
4	Трудовые	1	1	1	1	=СУММПРОИЗВ(В$2:Е$2;В4:Е4)		16
5	Сырьевые	6	5	4	1	=СУММПРОИЗВ(В$2:Е$2;В5:Е5)		110
6	Финансы	4	6	10	13	=СУММПРОИЗВ(В$2:Е$2;В6:Е6)		100

Примечание. Можно вводить В2:Е2 не с клавиатуры, а поставить курсор в окно Массив 1, а затем протащить курсор при нажатой левой клавише мыши по ячейкам В2:Е2, имена ячеек сами запишутся в окно. Аналогично поступить с полем Массив 2.

Нажать клавишу ОК, в ячейку F3 запишется формула 60х₁+70х₂+120х₃+ 130х₄ в виде СУММПРОИЗВ(В2:Е2;В3:Е3).

В результате копирования мы увидим следующие формулы:

Заполнение окна Поиск решения

Аналогично через «Добавить» ввести , для системы ограничений (2), а также , , и .

Также необходимо добавить ограничения для получения целочисленных величин по количеству товаров: B2=цел, C2=цел, D2=цел и Е2=цел.

После ввода последнего граничного условия вместо «Добавить» нажать клавишу ОК, появится окно «Поиск решения».

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

Параметры поиска

В окне «Поиск решения» нажать клавишу «Параметры», выбрать по умолчанию Максимальное время – 100 с, число итераций – 100 (для большинства задач это количество просчётов подходит с большим запасом), установить флажок в строке «Линейная модель», нажать ОК, в появившемся окне Поиск Решения нажать Выполнить (рис. 12. рис. 12.3).

Результаты поиска решения с таблицей результатов:

A	B	C	D	E	F	G	H
1	Переменная	X1	X2	X3	X4	Формула	Знак	Св.член
2	Значение	10	0	6	0
3	Коэф. ЦФ	60	70	120	130	1320	Max
4	Трудовые	1	1	1	1	16		16
5	Сырьевые	6	5	4	1	84		110
6	Финансы	4	6	10	13	100		100

Таким образом оптимальный план Х(Х₁,Х₂,Х₃,Х₄)=(10,0,6,0) при минимальном использовании ресурсов

даёт максимум прибыли F в 1320 руб.

_Вывод: Максимальная прибыль F в 1320 руб. получается при выпуске только товаров Х₁ и Х₃ в количестве 10 и 6 штук соответственно, товары Х₃ и Х₄ выпускать не нужно (это приведёт к снижению прибыли). Трудовые (У₁) и финансовые (У₃) ресурсы используются полностью, по сырьевым ресурсам (У₂) есть запас в 110-84=26 ед.

Задача 2. Задача об оптимальной диете

Требуется определить оптимальный состав рациона продуктов, такой, чтобы каждое питательное вещество содержалось в нем в необходимом количестве, обеспечивающем суточную потребность человека, и при этом суммарная калорийность рациона была минимальной.

Ведем в рассмотрение следующие переменные: х – весовое количество продукта питания i-го типа в суточном рационе.

Тогда в общем случае математическая постановка задачи об оптимальной диете может быть сформулирована следующим образом:

где множество допустимых альтернатив формируется следующей системой ограничений типа неравенств:

Для решения задачи об оптимальной диете с помощью программы MS Excel необходимо задать конкретные значения параметрам исходной задачи.

Для определенности предположим, что в качестве исходных типов продуктов рассматриваются: хлеб, мясо, сыр, бананы, огурцы, помидоры, виноград ( n = 7), а в качестве питательных веществ рассматриваются белки, жиры, углеводы ( m = 3).

Калорийность одной весовой единицы каждого из продуктов следующая:с₁ = 2060,с₂= 2430,с₃= 3600,с₄= 890,с₅= 140,с₆= 230, с₇ = 650. Содержание питательных веществ в каждом из продуктов может быть задано в форме нижеприведенной таблицы.

Минимальная суточная потребность в питательных веществах следующая: в белках b ₁ = 100, в жирах b ₂= 70, в углеводах b3 = 400.

Для решения данной задачи c помощью программы MS Excel создадим новую книгу с именем Линейное программирование и изменим имя ее второго рабочего листа на Задача о диете.

Таблица 1. Содержание питательных веществ в продуктах питания

Продукты/питательные вещества	Хлеб ржаной	Мясо баранина	Сыр «Российский»	Банан	Огурцы	Помидоры	Виноград
Белки	61	220	230	15	8	11	6
Жиры	12	172	290	1	1	2	2
Углеводы	420	0	0	212	26	38	155

Создание математической модели задачи

Составим математическую модель процесса по описанию задачи:

– целевая функция (суммарная калорийность продуктов).

– граничные условия

Создание формы

Для решения поставленной задачи выполним следующие подготовительные действия:

Для отображения формул в ячейках рабочего листа необходимо выполнить команду меню: Формулы и на панели инструментов в группе Зависимости формул выбрать Показать формулы.

Заполнение окна Поиск решения

Для дальнейшего решения задачи следует вызвать мастер поиска решения, для чего необходимо выполнить операцию: Данные > Поиск решения.

После появления диалогового окна Поиск решения следует выполнить следующие действия:

Параметры

В окне «Поиск решения» нажать клавишу «Параметры», выбрать «Поиск решения Линейных задач симплекс-методом», нажать ОК, затем нажать Найти Решение (рис. 12.6 рис. 12.6, б).

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

Результатом решения задачи об оптимальной диете являются найденные оптимальные значения переменных: х₁ = 0, х₂ = 0,211, 3 = 0,109, х₄= 1,887, х₅ = 0, х₆ = 0, х₇ = 0, которым соответствует значение целевой функции: f_опт= 2587,140. При выполнении расчетов для ячеек В2:I2 был выбран числовой формат с 3 знаками после запятой.

Анализ найденного решения показывает, что для удовлетворения суточной потребности в питательных веществах (белки, жиры, углеводы) следует использовать 211 г мяса баранины, 109 г сыра и 1887 г бананов, совсем отказавшись от хлеба, огурцов, помидоров и винограда. При этом общая калорийность найденной оптимальной диеты будет приближенно равна 2590 ккал, что вполне соответствует малоактивному образу жизни без серьезных физических нагрузок. Напомним, что согласно медицинским данным, энергетические затраты работников интеллектуального труда (юристы, бухгалтера, врачи, педагоги) лежат в пределах 3000 ккал.

ЗАДАНИЕ

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

Изделия четырех типов проходят последовательную обработку на двух станках. Время обработки одного изделия каждого типа на каждом из станков:

Завод выпускает изделия трех моделей ( I, II III ) Для их изготовления используется два вида ресурсов (А и В), запасы которых составляют – 5000 и 6000 единиц. Расходы ресурсов на одно изделие каждой модели:

Бройлерное хозяйство птицеводческой фермы насчитывает 80000 цыплят, которые выращиваются до 8-недельного возраста и после соответствующей обработки поступают в продажу. Хотя недельный рацион цыплят зависит от их возраста, в дальнейшем будем считать, что в среднем (за 8 недель) он составляет 1 фунт.

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

Смесь должна содержать:

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

Для решения задачи об оптимальной диете с помощью программы MS Excel необходимо задать конкретные значения параметрам исходной задачи. Для определенности предположим, что в качестве исходных типов продуктов рассматриваются: хлеб, мясо, сыр, бананы, огурцы, помидоры, виноград ( n = 7), а в качестве питательных веществ рассматриваются белки, жиры, углеводы ( m = 3). Калорийность одной весовой единицы каждого из продуктов следующая:с₁ = 2060,с₂= 2430,с₃= 3600,с₄= 890,с₅= 140,с₆= 230, с₇ = 650. Содержание питательных веществ в каждом из продуктов может быть задано в форме следующей таблицы (см. табл.).

Таблица 1. Содержание питательных веществ в продуктах питания

Продукты/питательные вещества	Хлеб ржаной	Мясо баранина	Сыр «Российский»	Банан	Огурцы	Помидоры	Виноград
Белки	66	225	235	20	13	16	11
Жиры	17	177	295	1	1	7	7
Углеводы	425	0	0	217	31	43	200

Минимальная суточная потребность в питательных веществах следующая: в белках b ₁ = 105, в жирах b ₂ = 75, в углеводах b ₃ = 405.

Определить суточную потребности в питательных веществах (белки, жиры, углеводы) и общую калорийность оптимальной диеты.

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

Изделия четырех типов проходят последовательную обработку на двух станках. Время обработки одного изделия каждого типа на каждом из станков:

Завод выпускает изделия трех моделей ( I, II III ). Для их изготовления используется два вида ресурсов (А и В), запасы которых составляют – 4000 и 6000 единиц. Расходы ресурсов на одно изделие каждой модели:

Некоторое производственное предприятие выпускает три вида клея. Для производства клея используется 4 типа химических веществ: крахмал, желатин, квасцы и мел. Расход этих веществ в кг для получения 1 кг каждого вида клея и их запас на складе предприятия представлены в таблице.

Таблица 1. Расход химических веществ на изготовления клея, их запас на складе

Вид клея /Химические вещества	Клей № 1	Клей № 2	Клей № 3	Запас на складе
Крахмал	0,4	0,3	0,2	20
Желатин	0,2	0,3	0,4	35
Квасцы	0,05	0,07	0,1	7
Мел	0,01	0,05	0,15	10

Стоимость каждого вида клея для оптовых покупателей следующая:с₁ = 380 руб/кг,с₂ =430 руб/кг,с₃ = 460 руб/кг. Требуется определить оптимальный объем выпуска клея каждого вида, обеспечивающий максимум общей стоимости готовой продукции.

Бройлерное хозяйство птицеводческой фермы насчитывает 20000 цыплят, которые выращиваются до 8-недельного возраста и после соответствующей обработки поступают в продажу. Хотя недельный рацион цыплят зависит от их возраста, в дальнейшем будем считать, что в среднем (за 8 недель) он составляет 1 фунт.

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

Смесь должна содержать:

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

Имеется конечное число видов продуктов питания: ананас, арбуз, грейпфрут, язык говяжий, сардельки говяжьи, хлеб «Бородинский», картофель ( n = 7), а в качестве питательных веществ рассматриваются белки, жиры, углеводы ( m = 3). Калорийность 1 кг каждого из продуктов следующая:с₁ = 470,с₂= 380,с₃ = 350,с₄ = 1460,с₅ = 2150,с₆ = 2070, с₇ = 800. Минимальная суточная потребность в питательных веществах следующая: в белках b ₁ = 100, в жирах b ₂ = 70, в углеводах b3 = 400. Содержание питательных веществ в каждом из продуктов может быть задано в форме нижеприведенной таблицы (табл.).

Требуется определить такой рацион питания, чтобы каждое питательное вещество содержалось в нем в необходимом количестве, обеспечивающем суточную потребность человека, и при этом суммарная калорийность рациона была минимальной.

Источник