Коврижных А.Ю., Конончук Е.А. и др. Прикладное программное обеспечение для решения экономических задач
Подождите немного. Документ загружается.
41
Рис.3.22
4. Задачи оптимизации.
Очень широкий класс задач составляют задачи оптимизации или, как их еще
называют, экстремальные задачи. Обычно их решение сопряжено с большим
количеством вычислений, что затруднительно выполнять вручную.
Задачи линейного программирования.
Будем рассматривать задачу линейного программирования, которая
заключается в нахождении n переменных,
x
1
, x
2
, . . . ,x
n
,
минимизирующих данную линейную функцию (целевую функцию):
Z = f(x
1
, x
2
, . . . ,x
n
)= c
1
·
x
1
+ c
2
·x
2
+ . . .+c
n
·x
n
(4.1)
При m линейных ограничениях – равенствах:
a
i1
x
1
+ a
i2
x
2
+. . .+a
in
x
n
= b
i
, где i = 1,2,3,…,m (4.2)
и n линейных ограничениях – неравенствах;
x
k
≥ 0, где k = 1,2,3, . . .,n (4.3)
Допустимым решением (планом) задачи линейною программирования
является упорядоченное множество чисел ( x
1
, x
2
, . . . ,x
n
.). удовлетворяющих
ограничениям (4.2) и (4.3).
Чаще всего оптимальное решение, если оно существует, является
единственным. Однако возможны случаи, когда оптимальных решений
бесчисленное множество. Процесс решения задачи линейного
программирования обычно состоит из следующих этапов:
42
1) Осмысление задачи, выделение наиболее важных качеств, свойств,
величин, параметров.
2) Введение обозначений неизвестных.
3) Создание целевой функции.
4) Составление системы ограничений, которым должны удовлетворять
введенные величины.
5) Решение задачи на компьютере.
Инструментом для поиска решений задач оптимизации в Excel служит
процедура Поиск решения.
Алгоритм использования процедуры поиска решения.
1) Сформулируйте задачу.
2) В меню Сервис выберите команду Поиск решения.
3) Если команда Поиск решения отсутствует в меню Сервис, установите
надстройку Поиск решения.
4) В поле Установить целевую ячейку введите ссылку на ячейку или имя
конечной ячейки. Конечная ячейка должна содержать формулу.
5) Выполните одно из следующих действий:
9 чтобы максимизировать значение конечной ячейки путем
изменения значений влияющих ячеек, установите переключатель в
положение максимальному значению;
9 чтобы минимизировать значение конечной ячейки путем
изменения значений влияющих ячеек, установите переключатель в
положение минимальному значению;
9 чтобы установить значение в конечной ячейке равным некоторому
числу, установите переключатель в положение значению и введите
в соответствующее поле требуемое число.
6) В поле Изменяя ячейки введите имена или ссылки на изменяемые
ячейки, разделяя их запятыми. Изменяемые ячейки должны быть прямо
или косвенно связаны с конечной ячейкой. Допускается задание до 200
изменяемых ячеек.
43
7) Чтобы автоматически найти все ячейки, влияющие на формулу модели,
нажмите кнопку Предположить.
8) В поле Ограничения введите все ограничения, накладываемые на поиск
решения.
Добавление ограничения
1) В разделе Ограничения диалогового окна Поиск решения нажмите
кнопку Параметры.
2) В поле Ссылка на ячейку введите адрес или имя ячейки, на значение
которой накладываются ограничения.
3) Выберите из раскрывающегося списка условный оператор ( <=, =, >=,
цел или двоич ), который должен располагаться между ссылкой и
ограничением. Если выбрано цел, в поле Ограничение появится
«целое». Если выбрано двоич, в поле Ограничение появится
«двоичное».
4) В поле Ограничение введите число, ссылку на ячейку или ее имя либо
формулу.
5) Выполните одно из следующих действий:
a. Чтобы принять ограничение и приступить к вводу нового, нажмите
кнопку Добавить.
b. Чтобы принять ограничение и вернуться в диалоговое окно Поиск
решения, нажмите кнопку OK.
Примечания
Условные операторы типа цел и двоич можно применять только при
наложении ограничений на изменяемые ячейки.
Флажок Линейная модель в диалоговом окне Параметры поиска решения
позволяет задать любое количество ограничений. При решении нелинейных
задач на значения изменяемых ячеек можно наложить более 100 ограничений,
в дополнение к целочисленным ограничениям на переменные.
Изменение и удаление ограничений
44
1) В списке Ограничения диалогового окна Поиск решения укажите
ограничение, которое требуется изменить или удалить.
2) Выберите команду Изменить и внесите изменения либо нажмите кнопку
Удалить.
3) Нажмите кнопку Выполнить и выполните одно из следующих действий:
a. чтобы сохранить найденное решение на листе, выберите в
диалоговом окне Результаты поиска решения вариант
Сохранить найденное решение;
b. чтобы восстановить исходные данные, выберите вариант
Восстановить исходные значения.
4) Чтобы прервать поиск решения, нажмите клавишу ESC. Лист Excel
будет пересчитан с учетом найденных значений влияющих ячеек.
Если решение будет найдено, выберите тип отчета в списке Отчеты и
нажмите кнопку ОК. Отчет будет помещен на новый лист книги
Рассмотрим примеры решения некоторых задач оптимизации
Пример 4.1. В ресторане готовятся фирменные блюда трех видов (блюдо А.
блюдо В и блюдо С), с использованием при приготовлении ингредиентов трех
видов (ингредиент 1, ингредиент 2 и ингредиент 3). Расход ингредиентов в
граммах на блюдо задается следующей таблицей.
Вид ингредиента блюдо А блюдо В Блюдо С
ингредиент 1 20 50 10
ингредиент 2 20 0 40
ингредиент 3 20 10 10
Стоимость приготовления блюд одинакова (например, 100 руб.).
Ежедневно в ресторан поступает 5 кг ингредиента 1 и по 4 кг ингредиентов
видов 1 и 3. Каково оптимальное соотношение дневного производства блюд
различного вида, если производственные мощности ресторана позволят
использовать весь запас поступивших продуктов
Решение.
45
Для решения задачи введем обозначения: х
1
- дневной выпуск блюда А: х
2
, -
дневной выпуск блюда В; х
3
- дневной выпуск блюда С. Составим целевую
функцию — она заключается в стоимости выпушенных рестораном блюд:
Z = 100· x
1
+ 100· x
2
+ 100· x
3
Определим имеющиеся ограничения (руководствуясь таблицей):
1) 20·x1 + 50·x2 + 10·x3 ≤ 5000;
2) 20·x1 + 0·x2 + 40·x3 ≤ 4000;
3) 20·x1 + 10·x2 + 10·x3 ≤ 4000.
Кроме того, поскольку нельзя реализовать часть блюда и количество блюд не
может быть отрицательным, добавим еще ряд ограничений:
1. x
1
≥ 0;
2. x
2
≥ 0;
3. x
3
≥ 0;
4. x
1
– целое;
5. x
2
– целое ;
6. x
3
– целое;
Теперь можно приступить к решению задачи с помощью Excel.
1. Откроем новый рабочий лист.
2. В ячейки А2, А3 и А4 занесем дневной запас продуктов (5000, 4000 и 4000
соответственно).
3. В ячейки С1, D1 и E1 занесем начальные значения неизвестных x1, x2, x3
(нули) – в дальнейшем значения этих ячеек будут подобраны автоматически.
4. В ячейках диапазона С2:E4 разместим таблицу расхода ингредиентов.
5. В ячейках В2:В4 укажем формулы для расчета расхода ингредиентов по
видам.
В ячейке В2 формула будет иметь вид = $С$1*С2 + $D$1*D2+$E$l*E2, а
остальные формулы можно получить методом автозаполнения.
6. В ячейку F1 занесем формулу целевой функции =100*(С1 + Dl + El)
Результат ввода данных в рабочую таблицу представлен на рисунке ниже.
46
Рис.4.1
Выполним команду Сервис → Поиск решения – откроется диалоговое окно
Поиск решения. В поле Установить целевую ячейку укажем ячейку,
содержащую оптимизируемое значение (F1). Установим переключатель
Равной в положение максимальному значению (требуется максимальный
объем производства).
7. В поле Изменяя ячейки зададим диапазон подбираемых параметров:
С1:Е1.
8. Чтобы определить набор ограничений, щелкнем на кнопке Добавить. В
диалоговом окне Добавление ограничения в поле Ссылка на ячейку укажем
диапазон В2:В4. В качестве условия зададим <=. В поле Ограничение зададим
диапазон А2:А4. Это условие указывает, что дневной расход ингредиентов не
должен превосходить запасов. Щелкнем на кнопке ОК.
9. Снова щелкнем на кнопке Добавить. В поле Ссылка на ячейку укажем
диапазон С1:Е1. В качестве условия зададим >=. В поле Ограничение зададим
число 0. Это условие указывает, что число приготавливаемых блюд
неотрицательно. Щелкнем на кнопке ОК.
10. Снова щелкнем на кнопке Добавить. В поле Ссылка на ячейку укажем
диапазон С1:Е1. В качестве условия выберем цел. Это условие не позволяет
производить доли блюд. Вид окна на рис.4.2. Щелкнем на кнопке ОК.
Рис.4.2
47
11. Щелкнем на кнопке Выполнить. По завершении оптимизации откроется
диалоговое окно Результаты поиска решения.
Рис.4.3
12. Установим переключатель в положение Сохранить найденное решение,
после чего щелкнем на кнопке ОК.
В результате получится набор оптимальных значений переменных
(оптимальное количество приготавливаемых фирменных блюд) при данных
ограничениях (при данном количестве ингредиентов): блюда А — 184 порции
(x
1
), блюда В — 24 порции (х
2
) и блюда С — 8 порций (x
3
). При этом общая
стоимость блюд (Z) будет максимальной и равной 21600 руб. Кроме того
останутся неизрасходованными 40г первого ингредиента (рис.4.4).
Рис. 4.4
Проанализируем полученное решение. Проверить его оптимальность можно,
экспериментируя со значениями ячеек С1:Е1. Например, допустим, что
решили приготовить количества блюд, соответственно 184, 23, 9. Тогда при
той же общей стоимости блюд будет перерасход второго ингредиента на 40г,
что, естественно, недопустимо. Можно рассмотреть и другие варианты. Чтобы
восстановить оптимальные значения, можно в любой момент повторить
операцию поиска решения.
48
Пример 4.2. Туристская фирма заключила контракты с турбазами в г. Сухуми
и другом городе. Они могут принять, соответственно, 200 и 150 человек.
Туристам для осмотра предлагается обезьяний питомник в городе,
ботанический сад и поход в горы. Составьте маршрут движения туристов так,
чтобы это обошлось турфирме возможно дешевле, если:
обезьяний питомник принимает в день 70 человек;
ботанический сад — 180 человек,;
в горы в один день могут пойти 110 человек.
О стоимость одного посещения выражается таблицей:
Турбаза ОП БС Поход
1 5 6 20
2 10 12 5
Решение. Для решения задачи введем обозначения: пусть х
1
— число туристов
из турбазы в Сухуми, посещающих обезьяний питомник; х
2
— число туристов
из турбазы в Сухуми, посещающих ботанический сад; х
3
— число туристов из
турбазы в Сухуми, отправляющихся в поход; х
4
— число туристов из другой
турбазы, посещающих обезьяний питомник; х
5
— число туристов из другой
турбазы, посещающих ботанический сад; х
6
— число туристов из другой
турбазы, отправляющихся в поход. Составим целевую функцию — она
заключается в минимизации стоимости дневных мероприятий турфирмы:
Z= 5 ·х
1
+ 6 · х
2
+ 20 · х
3
+ 10· х
4
+ 12 · х
5
+ 5 · х
6
.
Определим имеющиеся ограничения (руководствуясь условиями задачи):
1. х
1
+ х
4
≤ 70;
2. х
2
+ х
5
≤ 180;
3. х
3
+ х
6
≤ 110;
4. х
1
+ х
2
+ x
3
= 200;
5. х
4
+ х
5
+ х
6
= 150.
49
Кроме того, поскольку турист неделим и количество туристов, участвующих в
каждом мероприятии, не может быть отрицательным, добавим еще ряд
ограничений:
1) x
1
≥ 0
2) x
2
≥ 0
3) x
3
≥ 0
4) x
4
≥ 0
5) x
5
≥ 0
6) x
6
≥ 0
7) x
1
– целое;
8) x
2
– целое;
9) x
3
– целое;
10) x
4
– целое;
11) x
5
– целое;
12) x
6
– целое;
Теперь можно приступить к решению задачи.
1. Откроем новый рабочий лист
2. В ячейки А2, A3 и А4 занесем дневное количество посетителей различных
мероприятий — числа 70,180 и 110, соответственно.
3. В ячейки А5 и А6 занесем количество туристов в обеих турбазах — числа
200, и 150, соответственно.
4. В ячейки С1:Н1 занесем начальные значения неизвестных х
1
, х
2
, ...,x:
6
(нули)
— в дальнейшем значения этих ячеек будут подобраны автоматически.
5. В ячейках диапазона С2:Н6 разместим таблицу коэффициентов основных
ограничений:
• 1,0,0,1,0,0;
• 0,1,0,0,1,0;
• 0,0,1,0,0,1;
• 1,1,1,0,0,0;
• 0,0,0,1,1,1.
50
6. В ячейках В2;Вб укажем формулы для расчета ограничений. В ячейке В2
формула будет иметь вид=$С$1*С2 + $D$1*D2 + $Е$1*Е2 + $F$1*F2 +
$G$1*G2 + + $Н$1*Н2, а остальные формулы можно получить методом
автозаполнения.
7. В ячейку I1 занесем формулу целевой функции =5*С1 + 6*D1 + 20*Е1 +
10*F1 + 12*G1+5*H1.
Рис.4.5
8. Выполним Сервис → Поиск решения — откроется диалоговое окно
Поиск решения.
9. В поле Установить целевую ячейку укажем ячейку, содержащую
оптимизируемое значение (I1). Установим переключатель Равной в положение
минимальному значению (требуется минимальный объем затрат).
10. В поле Изменяя ячейки зададим диапазон подбираемых параметров —
С1:Н1.
11. Чтобы начать определять набор ограничений, щелкнем на кнопке
Добавить. В диалоговом окне Добавление ограничения в поле Ссылка на
ячейку укажем диапазон В2:В4. В качестве условия задайте <=. В поле
Ограничение зададим диапазон А2:А4. Это условие указывает, что дневное
количество посетителей мероприятий не должно превосходить их
возможностей. Щелкнем на кнопке ОК.
12. Для продолжения определения набора ограничений щелкнем на кнопке
Добавить. В диалоговом окне Добавление ограничения в поле Ссылка на
ячейку укажем диапазон В5:В6. В качестве условия зададим =. В поле
Ограничение зададим диапазон А5:А6. Это условие указывает, что дневное
количество посетителей мероприятий должно быть равно количеству
туристов. Щелкните на кнопке ОК