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

Разделы: Информатика


Подбор параметра

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

 

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

 

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

 

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

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

Ниже приведены данные для постановки проблемы. Оба окна отображают один и тот же лист (первое - результаты, второе - формулы).

2. Выбрать команду Сервис Подбор параметра - откроется диалоговое окно "Подбор параметра".

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

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

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

6. Щелкнуть по кнопке "ОК" - откроется окно, информирующее о том, что решение найдено (если оно существует).

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

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

Задача1

Вы хотите положить деньги в банк под 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.

Задача 2

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

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

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

- в поле Установить в ячейке - ссылка на ячейку D2,

- в поле Значение - значение 200000,

- в поле Изменяя значение ячейки - ссылка на ячейку А2.

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

Поиск решения

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

  • Указывать несколько изменяемых ячеек
  • Указывать ограничения на значения изменяемых ячеек
  • Находить решение, при котором значение в определенной ячейке рабочего листа достигает максимума или минимума
  • Получить несколько решений задачи

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

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

Условие задачи:

Входные данные

 

А

В

С

D

1  

Количество

Доход на 1 ед.

Доход

2 Изделие А

100

13

1300

3 Изделие В

100

18

1800

4 Изделие С

100

22

2200

5 Всего

300

 

5300

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

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

Ограничения

  1. Общий объем производства – всего 300 единиц изделий в день.
  2. Компании нужно произвести 50 единиц изделия А для выполнения существующего заказа.
  3. Компании нужно произвести 40 единиц изделия В для выполнения планового заказа.
  4. Поскольку сбыт изделий С относительно небольшой, то должно быть изготовлено не более 40 единиц этого изделия.

Решение задачи:

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

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

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

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

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

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

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

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

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

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

Входные данные

Цель задачи – удовлетворить потребность в товарах, находящихся на складах, всех 6 различных магазинов и сохранить при этом общие расходы на перевозки на минимальном уровне.

  1. Целевая ячейка G24(минимизировать значение)
  2. Изменяя ячейки D12:F17

Ограничения:

  1. Количество необходимого товара для каждого различного магазина должно равняться количеству перевезенного(C12=G12, C13=G13, C14=G14, C15=G15, C16=G16, C17=G17)
  2. Значения в изменяемых ячейках не должно быть отрицательным(D12>=0, D13>=0, D14>=0, D15>=0, D16>=0, D17>=0, E12>=0, E13>=0, E14>=0, E15>=0, E16>=0, E17>=0, F12>=0, F13>=0, F14>=0, F15>=0, F16>=0, F17>=0)
  3. Количество запасов в каждом магазине не должно быть отрицательным(D21>=0, E21>=0, F21>=0)

Ответ: Минимальные расходы на перевозки при удовлетворении потребностей в товарах составляет 55 515 $

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

Входные данные

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

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

  • Планируемое количество служащих зависит от количества работников начавших работу в этот день недели. К количеству служащих, которые должны начать работу в текущие дни добавляется количество служащих, которые начинают работу в предыдущие 4 дня. Поскольку дни недели изменяются циклически, формулы будут разными, например для строки «Воскресенье» будет следующая формула: (D2+D8+D7+D6+D5)
  • Количество работников начавших работу в этот день недели (изменяемые ячейки). Для изменяемых ячеек нужно выбрать такие исходные значения, которые больше всего соответствуют ожидаемым значениям.
  • В столбце Разность содержаться формулы (планируемое_количество_работников – необходимо_персонала), по которым вычисляется количество необходимого персонала из планируемого количества людей. Это позволяет определить избыток или недостаток персонала.
  • Ячейка D9 является целевой и будет минимизироваться

Ограничения

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

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

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

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

Входные данные

 

A

B

C

D

E

F

G

H

I

2

Необходимые материалы

3 Материал Игрушка

A

Игрушка

B

Игрушка

C

Игрушка

D

Игрушка

E

Есть Использовано Остаток
4 Красная краска 0 1 0 1 3 625 500 125
5 Голубая краска 3 1 0 1 0 640 500 140
6 Белая краска 2 1 2 0 2 1100 700 400
7 Пластик 1 5 2 2 1 875 1100 -225
8 Дерево 3 0 3 5 5 2200 1600 600
9 Клей 1 2 3 2 3 1500 1100 400
10 Доход на единицу $15 $30 $20 $25 $25      
11 План выпуска 100 100 100 100 100      
12 Доход $1500 $3000 $2000 $2500 $2500      
13 Общий доход $11500              

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

Ограничения

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

Ответ: Общий доход составит $ 12365

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

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

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

Входные данные

Ограничения

  • Сумма инвестиций в предприятия, торгующие новыми автомобиля, должна быть по крайне мере, в 3 раза больше суммы инвестиций в предприятия, торгующие подержанными автомобилями, поскольку торговля подержанными автомобилями более рискованное дело. Это ограничение записывается так: C5>=C6*3
  • Ссуды на автомобили должны составлять 15% от полной суммы портфеля. Это ограничение записывается так: D14=0,15
  • Негарантированные ссуды должны составлять не более 25% от суммы портфеля (E8<=0,25)
  • Банковские кредиты должны составлять, по крайне мере, 10% от суммы портфеля (E9>=0,10)
  • Все инвестиции должны быть больше или равны нулю.

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

Выходные данные

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