Методическое пособие 577
.pdfчений: величины использованных ресурсов; теневые цены, то есть двойственные оценки yi, которые показывают, как изменится целевая функция при изменении ресурсов на
единицу; значения приращения ресурсов bi, при которых сохраняется оптимальный набор переменных, входящих в оптимальное решение.
Отчет по пределам показывает, в каких пределах может изменяться выпуск продукции, вошедшей в оптимальное решение, при сохранении структуры оптимального решения: рассматриваются значения xj в оптимальном решении; рассматриваются нижние пределы изменения значений xj.
Кроме этого, в отчете указаны значения целевой функции при выпуске данного типа продукции на нижнем пределе. Далее приводятся верхние пределы изменения xj и значения целевой функции при выпуске продукции, вошедшей в оптимальное решение на верхних пределах.
Важным фактором, помогающим принять оптимальное решение, является наглядное представление полученного результата. Результат решения задачи, рассмотренной выше, примем в качестве исходных данных при рассмотрении вопросов построения диаграмм.
Для построения диаграмм необходимо выделить те ячейки, значения которых должны быть представлены на диаграмме (B3:С3). Затем вызывается «Мастер диаграмм». В появившемся диалоговом окне выбирается нужный тип диаграммы. Выберем, например, объемный вариант гистограммы. После выбора типа диаграммы осуществляется переход к следующему этапу построения диаграммы. В диалоговом окне «Исходные данные» (рис. 7) сначала необходимо ввести диапазон данных, которые отображаются на диаграмме (в нашем примере — ячейки B3:E3), а затем, выбрав команду «Ряд», ввести названия рядов (например, «Количество»), а также подписи под осью X (НДА, АИК). Для ввода подписей можно выделить соответствующие ячейки таблицы (B2:С3) или ввести подписи непосредственно в диалоговом окне через двоеточие.
20
Рис. 7. Наглядное представление итоговых данных
Под параметрическим анализом будем понимать решение задачи оптимизации при различных значениях того параметра, который ограничивает улучшение целевой функции.
Параметрический анализ будем выполнять для рассматриваемой задачи производственного планирования, решая ее при различных значениях имеющегося сырья. Составим таблицу вариантов (табл. 8).
|
|
|
|
|
|
|
|
Таблица 8 |
|
|
|
|
|
|
|
|
|
|
|
Вариант |
1 |
|
2 |
3 |
|
4 |
|
5 |
|
Композиты |
54 |
|
48 |
42 |
|
36 |
|
30 |
|
Для выполнения |
параметрических |
расчетов |
в таблице |
||||||
с результатами решения задачи (см. рис. 5) необходимо удалить результат решения, находящийся в ячейках B3:С3. Далее решить задачу для первого варианта по описанной выше схеме, предварительно введя в ячейку Е8 значение 54. После решения задачи в диалоговом окне «Результаты поиска решения» выбирается команда «Сохранить сценарий». При этом на экране появится диалоговое окно «Сохранение сценария» (рис. 8). В появившемся диалоговом окне необходимо ввести имя сценария «Композиты 54» и подтвердить ввод выбором кнопки OK.
21
Рис. 8. Сохранение сценария
Далее необходимо аналогично решить задачу для всех оставшихся вариантов, последовательно вводя в ячейку Е8 значения 48, 42, 36, 30. При этом нужно сохранять каждый сценарий и вводить его имя, соответствующее текущему значению композитов.
Для представления результатов решения в диалоговом окне «Диспетчер сценариев» (рис. 9) выбирается пункт «Отчет».
Рис. 9. Диспетчер сценариев
При выборе в диалоговом окне «Отчет по сценарию» (рис. 10) типа отчета «Структура» создается итоговый сценарий (рис. 11), который размещается на отдельном листе с названием «Структура сценария».
22
Рис. 10. Диалоговое окно «Отчет по сценарию»
Рис. 11. Итоговый сценарий
Для наглядного представления результатов параметрического анализа построим гистограммы (рис. 12).
23
Рис. 12. Итоговые гистограммы
КОНТРОЛЬНЫЕ ВОПРОСЫ К ГЛАВЕ 2
1.С чего начинается решение задачи производственного плана в среде EXCEL?
2.Какие функциональные зависимости вводятся для целевой функции и ограничений?
3.Для чего используются абсолютные ссылки на ячейки?
4.Как осуществляется вызов процедуры «Поиск реше-
ния»?
5.Какие отчеты можно создать при выполнении процедуры «Поиск решения»?
6.Что понимается под «параметрическим анализом»?
24
ГЛАВА 3. ЦЕЛОЧИСЛЕННОЕ ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ. РЕШЕНИЕ ЗАДАЧИ О НАЗНАЧЕНИЯХ В СРЕДЕ EXCEL
Задача о назначениях относится к классу задач целочисленного линейного программирования. Задачи целочисленного линейного программирования в среде EXCEL решаются аналогично обычным задачам линейного программирования. Решение таких задач проводится с использованием процедуры «Поиск решения». Основное отличие заключается во вводе требования целочисленности для переменных.
Рассмотрим решение следующего примера. Цех по производству корпусов для медицинской техники выполняет на различном оборудовании следующие виды работ: изготовление деталей корпусов, сверление крепежных отверстий, покраска деталей, шлифовка покрашенных деталей, полировка деталей, сборка готовых корпусов. В рабочий штат цеха входят шесть сотрудников: Андрей Андреев, Дмитрий Дмитриев, Иван Иванов, Михаил Михайлов, Петр Петров, Сергей Сергеев. Производительность каждого сотрудника при выполнении различных видов работ задана матрицей:
14 |
17 |
10 |
14 |
18 |
17 |
|
|
|
|
19 |
9 |
13 |
19 |
15 |
|
12 |
|
||||||
|
11 |
20 |
11 |
11 |
20 |
15 |
|
С |
|
15 |
12 |
12 |
17 |
18 |
. |
16 |
|
||||||
|
|
14 |
10 |
15 |
16 |
19 |
|
15 |
|
||||||
|
|
13 |
13 |
13 |
15 |
|
|
13 |
21 |
||||||
При этом столбцы матрицы соответствуют различным видам работы, а строки — работающим сотрудникам. На пересечении строк и столбцов указано количество корпусов, над которыми могут быть проведены соответствующие виды работ конкретным сотрудником за неделю. Необходимо так распределить обязанности между сотрудниками, чтобы общая
25
производительность цеха была максимальной. При этом каждый из сотрудников в течение недели может выполнять только один вид работ, а один и тот же вид работ может выполняться только одним сотрудником. Введем альтернативныепеременные
1,если _i_сотрудник_выполняет_ работу x 0,если _иначе
Таким образом, в итоге нам необходимо определить, какую работу будет выполнять каждый из исполнителей, чтобы суммарная производительность по сборке корпусов была максимальной. Количество ограничений равно сумме количества исполнителей и количества работ. Задача о назначениях относится к классу булевой оптимизации, так как переменные могут принимать только одно из двух значений.
В рабочем листе MS Excel создадим две таблицы (матрицы) с шестью столбцами и строками. Нижнюю (С13:Н18) заполним исходными данными производительности сотрудников (рис. 13).
Рис. 13. Исходные данные задачи о назначениях
26
Верхнюю матрицу (С3:Н8) не будем заполнять, для нее лишь посчитаем суммы по строкам и столбцам, которые вначале примут значения нулей (ячейки С9:Н9 и I3:I9), а при нахождении опорного плана они обязательно должны быть равны единице, так как каждая работа должна выполняться только один раз и каждый из сотрудников должен выполнять только один из видов работ.
В ячейке J8 будем считать значение целевой функции — общая производительность цеха за неделю. Ее значение представляет собой сумму произведений двух матриц: матрицы распределения сотрудников по видам работ (С3:Н8) и матрицы производительности (С13:Н18). Дальнейшая работа выполняется в диалоговом окне «Поиск решения» (рис. 14).
Рис. 14. Диалоговое окно «Поиск решения»
В этом окне устанавливаются целевая ячейка (J8), изменяемые ячейки (C3:H8), указывается направление поиска (максимизация). В случае решения задачи о назначениях, для которой даны исходные данные о времени выполнения работ, направлением целевой функции будет минимизация. Далее вводятся ограничения: C3 = двоичное, ..H8 = двоичное (таких ограничений будет 36 по числу ячеек изменяемой матрицы), C9=1, D9=1, E9=1, F9=1, G9=1, H9=1, I3=1, I4=1, I5=1, I6=1, I7=1, I8=1 (таких ограничений будет 12 — сумма строк
27
и столбцов). Ограничение двоичных переменных позволяет ограничить переменную либо нулем (данная работа не выполняется конкретным сотрудником), либо единицей (работа выполняется). Ограничения на значения сумм столбцов и строк позволяет соблюсти условия того, что каждый из сотрудников может выполнять только один вид работ и каждая работа будет выполнена только одним сотрудником. В нашем случае мы используем линейную модель. Результаты оптимизации представлены на рис. 15.
Рис. 15. Результаты оптимизации
Выделенные ячейки соответствуют распределению работ между сотрудниками. Значение целевой функции, равное 101, — максимальное значение производительности.
Приведем еще один пример решения задачи о назначениях средствами EXCEL.
На пяти биохимических анализаторах различных типов можно выполнять пять операций по измерению показателей крови (табл. 9). При этом за каждым из аппаратов может быть закреплена лишь одна операция, а одна и та же операция может выполняться только одним анализатором.
28
|
Виды анализов и анализаторы |
Таблица 9 |
||||
|
|
|
||||
|
|
|
|
|
|
|
|
Глюкоза |
Билирубин |
Холестерин |
Общий |
Креатинин |
|
|
(в крови) |
общий |
белок |
|
||
Konelab |
|
|
|
|
|
|
Vitalit |
|
|
|
|
|
|
Dimension |
|
|
|
|
|
|
ADVIA |
|
|
|
|
|
|
OLYMPUS |
|
|
|
|
|
|
Время выполнения операций на каждом из анализаторов задается матрицей
2 |
5 |
6 |
8 |
3 |
|
|
|
1 |
2 |
1 |
6 |
5 |
|
|
|
|||||
С |
7 |
12 |
4 |
5 |
8 |
. |
|
9 |
3 |
2 |
2 |
1 |
|
|
|
|||||
|
3 |
7 |
1 |
4 |
5 |
|
|
|
|||||
Необходимо составить такое распределение выполняемых операций между пятью анализаторами, при котором суммарные затраты времени на проведение анализа крови являются минимальными. Данная задача отличается от предыдущей тем, что целевая функция будет стремиться к минимуму.
При этом столбцы матрицы соответствуют различным видам анализа, а строки — анализаторам. На пересечении строк и столбцов указано время, за которое определенным анализатором может быть произведен определенный вид анализа крови.
Необходимо так распределить различные виды анализа между анализаторами, чтобы общее время проведения всех пяти операций было минимальным. При этом каждый из анализаторов может выполнять только один вид анализа, а один и тот же вид анализа может выполняться только одним анализатором. Введем альтернативные переменные
29