Задача об использовании сырья
А.А. Усков
НАДСТРОЙКА «ПОИСК РЕШЕНИЯ» MS EXCEL
УЧЕБНОЕ ПОСОБИЕ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ СТУДЕНТОВ ПО ДИСЦИПЛИНЕ “ЭКОНОМЕТРИКА ”
Надстройка «поиск решения» MS Excel. Усков А.А. Смоленск, 2006. – 20 с.
В учебном пособии рассмотрена методика применения надстройки «Поиск решения» MS Excel для решения задач экономического планирования.
Введение
Построение моделей и оптимизация экономических систем относится к разряду особо трудных «не решаемых» задач. Поэтому, на практике в большинстве случаев при принятии решений в области экономическо-управленческой деятельности руководствуются экспертными оценками, опытом и интуицией. В тоже время, для ряда экономических задач возможно получить формальную математическую модель, однозначно и достоверно описывающую происходящие процессы. В указанном случае применение математических методов достаточно эффективно. В частности, для статических задач применим аппарат математического программирования (поиск минимума или максимума, в общем случае, нелинейной функции при нелинейных ограничениях). Наиболее разработаны методы решения частного случаем задач математического программирование – задач выпуклого программирования. Особенностью выпуклого программирования является одноэкстремальность целевой функции на множестве допустимых решений. Примером таких задач является задача линейного программирования (поиск экстремума линейной целевой функции при линейных ограничениях).
|
|
|
В пакете MS Excel есть удобное средство для решения задач нелинейного программирования – надстройка «Поиск решения» [1, 2].
В надстройке «Поиск решения» реализованы алгоритмы условного метода Ньютона и условного метода сопряженных градиентов [3, 4], отлично справляющиеся с задачами выпуклого программирования, в частности линейного, но при решении задач с целевой функцией имеющей несколько экстремумов или при наличии дискретных ограничений (например, в задачах целочисленного программирования [5, 6]) возникают определенные сложности, проявляющиеся в том, что полученное решение соответствует не глобальному экстремуму, а локальному, т. е. носит лишь приближенный, не самый эффективный из возможных характер.
Указанные сложности преодолимы, по крайне мере, частично, так для решения многоэкстремальных задач можно многократно запускать процедуру локального поиска из различных начальных точек и выбирать наилучшее решение, а при решении дискретных задач использовать более сложные методы, сводящиеся к многократному решению недискретных задач, например, для решения задач линейного целочисленного программирования можно использовать метод ветвей и границ, сводящийся к последовательности решений составленных специальным образом задач «обычного» линейного программирования [5, 6].
|
|
|
Учебное пособие посвящено систематическому изложению методики применения надстройки MS Excel «Поиск решения».
В учебном пособии использован материал книг [1, 2].
Надстройка «Поиск решения» MS Excel
Рассмотрим задачу нахождения точек, в которых достигаются максимальные и минимальные значения функции нескольких переменных, при линейных и нелинейных ограничениях. Другими словами – находится оптимальное решение задачи статического управления с ограничениями.
Для решения задач будем использовать Поиск решения MS Excel. Для запуска этого инструмента необходимо выполнить команду Сервис | Надстройки. Появится окно диалога "Надстройки", в котором нужно установить флажок на строке Поиск решения и нажать кнопку ОК (рисунок 1).
Рисунок 1 – Окно диалога "Надстройки"
После загрузки инструмента Поиск решенияв списке опций ниспадающего меню Сервиспоявится новая команда Поиск решения.В результате выполнения этой команды появляется окно диалога "Поиск решения" (рисунок 2).
|
|
|
Рисунок 2 – Окно диалога "Поиск решения"
В поле ввода Установить целевую ячейкууказывается ссылка на ячейку с целевой функцией, значение которой должно быть максимальным, минимальным или равным заданному значению в зависимости от выбранного положения переключателя.
В поле ввода Изменяя ячейкиуказываются ячейки, которые отведены под переменные целевой функции.
Поле Ограничения должно содержать ограничения, накладываемые на изменение переменных целевой функции.
Кнопка Параметрывызывает окно диалога "Параметры поиска решения" (см. рисунок 3), в котором можно изменять параметры алгоритма поиска решения.
Рисунок 3 – Окно диалога "Параметры поиска решения"
Установки по умолчанию подходят для решения большинства типов оптимизационных задач. В таблице 1 приведены параметры надстройки Поиск решения и их описание.
Таблица 1 – Параметры надстройки Поиск решения
| Параметр | Действие |
| Максимальное время | Максимальное время в секундах (не превышающее 32 767), которое может быть затрачено на поиск решения |
| Предельное число итераций | Максимальное число итераций, которые могут быть сделаны. Каждая итерация заключается в вычислении очередного значения (приближения) и проверке, насколько это значение подходит в качестве ответа |
|
|
|
Таблица 1 – Параметры надстройки Поиск решения(продолжение)
| Относительная погрешность | Задает точность выполнения ограничений. Поле должно содержать число из интервала от нуля до единицы |
| Допустимое отклонение | В случае целочисленных ограничений задает, насколько близко в процентном отношении должен быть ответ к возможному наилучшему решению. При работе со сложными целочисленными задачами увеличение допустимого отклонения может привести к значительному ускорению работы. Используется только для целочисленных задач |
| Сходимость | Когда относительное изменение значения в целевой ячейке за последние пять итераций становится меньше числа, указанного в этом поле, поиск прекращается. Сходимость применяется только к нелинейным задачам (когда снят флажок Линейная модель). Поле должно содержать число из интервала от нуля до единицы |
| Линейная модель | Служит для ускорения поиска решения линейной задачи оптимизации или линейной аппроксимации нелинейной задачи путем использования методов линейного программирования. Если рабочий лист содержит нелинейную модель, при запуске средства Поиск решения будет появляться предупреждение |
| Неотрицательные значения | Устанавливает неотрицательность всех переменных, для которых не заданы явные ограничения в виде неравенств |
| Автоматическое масштабирова-ние | Служит для включения автоматической нормализации входных и выходных значений, качественно различающихся по порядку величины, например максимизация прибыли в процентах по отношению к вложениям, исчисляемым в млн руб. |
| Показывать результаты итераций | Выводит промежуточный результат и делает паузу при каждой итерации. Для продолжения поиска решения необходимо каждый раз нажимать кнопку Продолжить. С помощью кнопки Стоп можно остановить процесс |
| Оценки | Выбор линейного или квадратичного метода оценки. Квадратичный метод имеет смысл использовать, если зависимости в модели сильно отличаются от линейных |
| Разности | Служит для указания метода численного дифференцирования (прямые или центральные производные), который используется для вычисления частных производных целевых и ограничивающих функций. Прямые производные предназначены для гладких непрерывных функций. Центральные производные — для функций, имеющих разрывную производную |
Таблица 1 – Параметры надстройки Поиск решения(продолжение)
| Метод поиска | Служит для выбора алгоритма оптимизации (метод Ньютона или сопряженных градиентов) для указания направления поиска. При методе Ньютона запрашивается больше памяти, но выполняется меньше итераций, чем в методе сопряженных градиентов. Метод сопряженных градиентов следует использовать, если задача достаточно велика и необходимо экономить память, а также если итерации дают слишком малое отличие в последовательных приближениях |
Параметры поиска решения могут быть сохранены и затем загружены, для чего необходимо воспользоваться кнопками Сохранить модель… и Загрузить модель… .
По найденным результатам можно создавать отчеты. Такие отчеты полезны для сравнения влияния на решение различных ограничений или исходных данных. Отчеты бывают трех типов: Результаты, Устойчивость, Пределы. Тип выбирается по окончании поиска решения в диалоговом окне Результаты поиска решения в списке Отчеты (рисунок 4). Можно выбрать сразу два или три типа с помощью мыши при нажатой клавише <Ctrl>. Каждый отчет будет создан на отдельном рабочем листе. Содержание отчетов кратко описано в таблица 2.
Рисунок 4 – Окно «Результаты поиска решения»
Для сохранения значений в ячейках таблицы служит кнопка Сохранить сценарий…(см. рисунок 4). Для того чтобы загрузить сохраненный ранее сценарий необходимо выполнить команду в меню MS Excel Сервис / Сценарии…
Таблица 2–Содержание отчетов
| Тип отчета | Содержание |
| Результаты | Отчет состоит из целевой ячейки и списка влияющих ячеек модели, их исходных и конечных значений, а также формул ограничений и дополнительных сведений о наложенных ограничениях |
| Устойчивость | Отчет содержит сведения о чувствительности решения к малым изменениям в формуле модели или в формулах ограничений. Такой отчет не создается для моделей, значения в которых ограничены множеством целых чисел. В случае нелинейных моделей отчет содержит данные для градиентов и множителей Лагранжа. В отчет по нелинейным моделям включаются ограниченные затраты, фиктивные цены, объективный коэффициент (с некоторым допуском), а также диапазоны ограничений справа |
| Пределы | Отчет состоит из целевой ячейки и списка влияющих ячеек модели, их значений, а также нижних и верхних границ. Такой отчет не создается для моделей, значения в которых ограничены множеством целых чисел. Нижним пределом является наименьшее значение, которое может содержать влияющая ячейка, в то время как значения остальных влияющих ячеек фиксированы и удовлетворяют наложенным ограничениям. Соответственно верхним пределом называется наибольшее значение |
Сохранение параметров модели.Последние использованные параметры модели сохраняются на рабочем листе, для этого применяются именованные формулы. При следующем открытии рабочего листа и запуске средства Поиск решенияпоявится диалоговое окно с теми же параметрами, которые были установлены при предыдущем запуске. Каждый рабочий лист в рабочей книге также имеет установки, определенные в предыдущем сеансе MS Excel.
Задача об использовании сырья
Предположим необходимо определить оптимальный план выпуска продукции в условиях дефицита сырья.
Предприятие выпускает два вида продукции. Цена единицы продукции вида 1 равна 25000 руб., вида 2 – 50000 руб.
Для изготовления продукции используются три вида сырья, запасы которого оцениваются в 37, 57,6 и 7 тонн соответственно. На каждый вид сырья есть коэффициент его расхода на единицу продукции. Соответствующие коэффициенты приведены в таблице 3.
Таблица 3 – Коэффициенты расхода сырья на единицупродукции
| Вид сырья | Продукция | Запасы сырья | |
| Вид 1 | Вид 2 | тонн | |
| 1 | 1,2 | 1,9 | 37 |
| 2 | 2,3 | 1,8 | 57,6 |
| 3 | 0,1 | 0,7 | 7 |
Обозначим количество произведенной продукции вида 1 через с1, вида 2 вида – с2. Целевая функция в данном случае есть выражение следующего вида:
J(cl, c2) = 25000*cl + 50000*с2.
Это есть цена произведенной продукции. Наше решение должно обеспечить максимальное значение этой функции.
Таблица 1 налагает на величины cl и с2 ограничения следующего вида:
1,2*с1 + 1,9*с2 <= 37
2,3*с1 + 1,8*с2 <= 57,6
0,1*с1 + 0,7*с2 <= 7
c1 >= 0
c2 >= 0
Выполним следующие действия:
1. Введем в ячейку А1 формулу для целевой функции:
=25000*с1+50000*с2.
2. Введите в ячейку A3 формулу для ограничения: =1, 2*с1+1, 9*с2.
3. Введите в ячейку А4 формулу для ограничения: =2.3*cl+1,8*c2.
4. Введите в ячейку А5 формулу для ограничения: =0,1*с1+0, 7*с2.
5. Введите в ячейку А6 формулу для ограничения: =cl.
6. Введите в ячейку А7 формулу для ограничения: =с2.
7. Введите в ячейки С1:C2 начальные значения переменных (положим их нулевыми).
8. Выполним команду Сервис | Поиск решения.Появится окно диалога «Поиск решения».
9. В поле ввода Установить целевуювведем ссылку на ячейку А1.
10. В поле ввода Изменяя ячейкиукажем ссылки на ячейки С1:С2.
11. Начинаем вводить информацию в поле ввода Ограничения.Нажмем кнопку Добавить.Появится окно диалога "Добавить ограничения". Вполе ввода Ссылка на ячейкувведем ссылку на ячейкуA3. В поле ввода Ограничениевведем <= и число 37 (рисунок 3).
Рисунок 3 – Окно «Добавление ограничения»
12. Воспользуемся кнопкой Добавитьдля ввода остальных ограничений. После ввода параметров окно диалога "Поиск решения" будет иметь вид показанный на рисунке 4. При необходимости, для изменения ограничения установите на него курсор и нажмите кнопку Изменить.
Рисунок 4 – Окно «Поиск решения» после ввода параметров
13. Нажмем кнопку Выполнить. После окончания расчета Excel откроет окно диалога "Результаты поиска решения" (рисунок 5).
14. Выберем в окне "Тип отчета" Результаты и нажмите кнопку ОК. Перед тем листом, где записана постановка задачи, будет вставлен лист "Отчет по результатам 1". В ячейках Сl и Сl отображаются значения переменных, на которых достигается максимальное значение целевой функции (рисунок 6).
Рисунок 6 – Решение задачи
15. Нажмем мышью ярлык «Отчет по результатам 1». На экране появится отчет о решении задачи (рисунок 7).
Рисунок 7 – Отчет по результатам
Транспортная задача
В этом примере необходимо определить оптимальный план перевозок продукции со складов в пункты реализации.
Предположим, что нужно перевести весь груз из трех складов в 2 пункт, причем весь груз должен быть перевезен во все пункты. В 1 пункт должно быть перевезено 45 единиц груза, в пункт 2 – 79. На складах груз размещен следующим образом: на складе 1 – 18 единиц, на складе 2 – 75 единиц, на складе 3 – 31 единица.
Стоимость перевозки единицы груза со склада в пункт назначения определяется таблицей 4.
Таблица 4 – Стоимость перевозки единицы груза
| Номер склада | Пункт 1 | Пункт 2 |
| 1 | 17 | 6 |
| 2 | 12 | 13 |
| 3 | 9 | 8 |
В таблице 5 приведены переменные, которые обозначают объемы перевозок со складов в пункты назначения.
Таблица 5 – Обозначения для объемов перевозок
| Номер склада | Пункт 1 | Пункт 2 |
| 1 | с1 | с4 |
| 2 | с2 | с5 |
| 3 | с3 | с6 |
В данном примере целевая функция определяется как сумма затрат на перевозки:
J(cl, c2, c3, c4, c5, c6) = 17*c1 + 12*с2 + 9*с3 + 6*с4 + 13*c5 + 8*с6
Запишем уравнения для ограничений Тот факт, что все грузы перевезены записывается в виде трех уравнений:
cl + с4 = 18,
с2 + с5 = 75,
сЗ + с6 = 31.
Сумма грузов в каждом пункте дает еще два уравнения:
cl + с2 + с3 = 45,
с4 + с5 + с6 = 79.
Еще два ограничения: объемы грузов должны быть неотрицательными и целочисленными (предположим, что единицы продукции являются неделимыми).
Для решения задачи выполним следующие действия:
1. Введите в ячейку A1 формулу для целевой функции:
= 17*C1 + 12*С2 + 9*СЗ + 6*С4 + 13*C5 + 8*С6
2. Введите в ячейку A3 формулу для ограничения: =C1+C4.
3. Введите в ячейку А4 формулу для ограничения =С2+С5.
4. Введите в ячейку А5 формулу для ограничения =С3+С6.
5. Введите в ячейку А6 формулу для ограничения =С1+С2+С3.
6. Введите в ячейку А7 формулу для ограничения =С4+С5+С6.
7. Введем в ячейки С1:С6 начальные значения переменных (положим их нулевыми).
8. Выполним командуСервис / Поиск решения. Появится окно «Поиск решения».
9. В поле Установить целевую функцию введем ячейку А1.
10. Установим переключатель в позицию Минимальное значение.
11. В поле ввода Изменяя ячейкиукажем ячейки С1:С6.
Начнем вводить информацию в поле вода Ограничения.Нажмем кнопку Добавить. Появится окно диалога "Добавить ограничения". В ноле Ссылка на ячейки введем ячейку А3. В поле ввода Ограничение введем
= число 18. Аналогичную операцию проделаем с ячейками А4:А7.
12. Для ввода ограничений на неотрицательность переменных в окне диалога «Добавить ограничения» в поле Ссылка на ячейкувведем С1:С6. В поле ввода Ограничение введем >= и число 0. Аналогичную операцию проделаем для ввода ограничений на целочисленность переменных, при этом в поле ввода Ограничение необходимо вводить цел (см. рисунок 8).
13. Нажмем кнопку Выполнить. Результаты решения показаны на рисунке 9.
Рисунок 8 – Ввод ограничений на условие целочисленности переменных
Рисунок 9 – Результат решения транспортной задачи
Задача о рюкзаке
В классических трудах по теории оптимизации достаточно часто выделяется отдельный класс задач, которым присвоено условное обозначение «задачи о рюкзаке»: турист собирается в поход и планирует взять с собой некоторое количество предметов (грузов) с различной степенью «полезности». Под «полезностью» конкретного предмета понимается совокупность его характеристик, определяющих эффективность использования этого предмета в походе, например, стоимость.
Для каждого предмета известен его вес.
Имеются и ограничение: выносливость туриста (какой вес он может нести).
Естественно, что общий вес всех предметов, которые целесообразно взять в поход, не превышает «грузоподъемность» туриста.
Поэтому требуется подобрать такую комбинацию предметов, чтобы их суммарная «полезность» была максимальной при выполнении ограничений по весу и объему.
Очевидно, что обобщенная постановка задачи подразумевает самые различные транспортные средства (в этом качестве мы уже рассмотрели туриста, а могут быть грузовики, корабли, самолеты и прочее).
Могут рассматриваться самые различные характеристики грузов — вес, объем и стоимость наиболее очевидны.
Первый (простой) пример такой задачи представлен на рабочем листе ЗадачаОРюкзаке(рисунок 10).
Рисунок 10–Рабочий лист задачи о рюкзаке
В клетки таблицы заносятся следующие формулы:
I4 =H4*E4
I5 =H5*E5
I6 =H6*E6
I7 =H7*E7
J4 =H4*E8
J5 =H5*E9
J6 =H6*E10
J7 =H7*E11
I8 =СУММ(I4:I7)
J8 =СУММ(J4:J7)
Как видите, здесь речь идет о погрузке грузов четырех видов в самолет. Пример является довольно простым, так как есть только два ограничения — по общему весу груза и по целочисленности количества предметов. В качестве критерия целесообразности загрузки предмета конкретного вида используется показатель под названием «эффективность» (измеряемый в некоторых единицах (баллах)).
Условия и ограничения задачи представлены на рисунке 11.
Рисунок 11–Условия и ограничения задачи
Решение задачи представлено на рисунке 12.
Рисунок 12 – Решение задачи о рюкзаке
Рассмотрим задачу о рюкзаке с заданным и ограниченным множеством предметов. В данном случае предметы в рюкзак набираются из заданного набора предметов. Будет помещен предмет в рюкзак или нет обозначается специальным индексом, который может принимать значения 1 или 0 соответственно.
Лист задачи о рюкзаке с заданным множеством предметов приведен на рисунке 13.
Рисунок 13 – Лист задачи о рюкзаке с заданным множеством предметов
В клетки таблицы заносятся следующие формулы:
Q4
=B4*B6+C4*C6+D4*D6+E4*E6+F4*F6+G4*G6+H4*H6+I4*I6+J4*J6+K4*K6+L4*L6+M4*M6+N4*N6+O4*O6+P4*P6
Q5
=B5*B6+C5*C6+D5*D6+E5*E6+F5*F6+G5*G6+H5*H6+I5*I6+J5*J6+K5*K6+L5*L6+M5*M6+N5*N6+O5*O6+P5*P6
Условия и ограничения задачи представлены на рисунке 14.
Рисунок 14 – Условия задачи о рюкзаке с заданным множеством предметов
Решение задачи при принятых по умолчанию параметрах приведено на рисунке 15.
Рисунок 15 – Решение задачи о рюкзаке с заданным множеством предметов
Целевая функция в данной задаче имеет линейный вид. Для улучшения качества решения установим «Линейную модель» (см. рисунок 16).
Рисунок 16 – Окно параметров поиска решения с установленной линейной
моделью
При установке линейной модели решение несколько улучшилось (см. рисунок 17).
Рисунок 17 – Решение задачи о рюкзаке с заданным множеством предметов при линейной модели
В тоже время, истинное решение (полученное методом ветвей и границ [5, 6]) является еще более эффективным (см. рисунок 18).
Рисунок 18 – Глобальное решение задачи о рюкзаке с заданным множеством предметов
Список литературы
1. Excel для экономистов и менеджеров / А.Г.Дубина, С.С.Орлова, И.Ю.Шубина, А.В.Хромов. Спб.: Питер, 2004.
2. Долголаптев В.Г. Работа в Excel 7.0 для Windows 95 на примерах. М.: Бином, 1995.
3. Кузнецов А.В., Холод Н.И., Костевич Л.С. Руководство к решению задач по математическому программирования. Минск: Вышэйшая школа, 2001.
4. Карманов В.Г. Математическое программирование. М.: Наука, 1975.
5. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование М. Наука. Гл. ред. физ.-мат. лит. 1969.
6. Береснев В.Л., Гимади Э.Х., Дементьев В.Т. Экстремальные задачи стандартизации. Новосибирск. Наука, 1978.
Содержание
Введение 3
1 Надстройка «Поиск решения» MS Excel 4
2 Задача об использовании сырья 8
3 Транспортная задача 12
4 Задача о рюкзаке 14
Список литературы 19
Дата добавления: 2018-02-28; просмотров: 1044; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!