МНОГОМЕРНЫЕ ЗАДАЧИ ОПТИМИЗАЦИИ
Выше мы рассмотрели одномерные задачи оптимизации, в которых целевая функция зависит лишь от одного аргумента. Однако в большинстве реальных задач оптимизации, представляющих практический интерес, целевая функция зависит от многих проектных параметров. Например, минимум дифференцируемой функции многих переменных u = f (x1, x2,..., xn) можно найти, исследуяеезначения в критических точках, которые определяются из решения системы дифференциальных уравнений
ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
В случае, когда оптимизируемая целевая функция и ограничения линейны, задача оптимизации решается методами линейного программирования и обычно называется задачей линейного программирования.
Процесс решения задачи линейного программирования обычно состоит из ряда этапов:
· 1-й этап: осмысление задачи, выделение наиболее важных качеств, свойств, величин, параметров. Это можно делать, составляя схемы, таблицы, графики и т.п.;
· 2-й этап: введение обозначений (неизвестных). Желательно ограничиваться как можно меньшим количеством неизвестных, выражая по возможности одни величины через другие;
· 3-й этап: создание целевой функции. Обычно в качестве цели могут выступать максимальная стоимость всего объема продукции, максимальная прибыль, минимальные затраты и т.п. Целевая функция записывается в виде(X.1);
· 4-й этап: составление системы ограничений, которым должны удовлетворять введенные величины (X.2) или (X.3);
· 5-й этап: решение задачи на компьютере.
Инструментом для поиска решений задач оптимизации в Excel служит процедура Поиск решения (Сервис/Поиск решения). При этом открывается диалоговое окно Поиск решения. Оно содержит следующие рабочие поля:
· Установить целевую ячейку – служит для указания целевой ячейки, значение которой необходимо максимизировать, минимизировать или установить равным заданному числу. Эта ячейка должна содержать формулу;
· Равной – служит для выбора варианта оптимизации значения целевой ячейки (максимизация, минимизация или подбор заданного числа). Чтобы установить число, необходимо ввести его в поле;
· Изменяя ячейки – служит для указания ячеек, значения которых изменяются в процессе поиска решения до тех пор, пока не будут выполнены наложенные ограничения и условие оптимизации значения ячейки, указанной в поле Установить целевую ячейку;
· Предположить – используется для автоматического поиска ячеек, влияющих на формулу, ссылка на которую дана в поле Установить целевую ячейку. Результат поиска отображается в поле Изменяя ячейки;
· Ограничения – служит для отображения списка граничных условий поставленной задачи;
· Добавить – используется для отображения диалогового окна Добавить ограничение;
· Изменить – применяется для отображения диалогового окна Изменить ограничение;
· Удалить – служит для снятия указанного ограничения;
· Выполнить – используется для запуска поиска решения поставленной задачи;
· Закрыть – служит для выхода из окна диалога без запуска поиска решения поставленной задачи. При этом сохраняются установки, сделанные в окнах диалога, появлявшихся после нажатий на кнопки Параметры, Добавить, Изменить или Удалить;
· Параметры – применяется для отображения диалогового окна Параметры поиска решения, в котором можно загрузить или сохранить оптимизируемую модель и указать предусмотренные варианты поиска решения;
· Восстановить – служит для очистки полей окна диалога и восстановления значений параметров поиска решения, используемых по умолчанию.
ПРИМЕР X.1
Требуется
На нефтяных месторождениях 1 и 2 поисково-разведочными работами готовятся запасы промышленных категорий X 1 и X 2 (в млн. т.). Необходимо отыскать значения запасов, приводящие к максимуму стоимости сырья (в тыс. долларов), которое возможно получить на двух месторождениях. В математическом виде – найти максимум прикладной линейной функции Z
при ограничениях:
– объемы работ по экологической реабилитации площади работ;
– стоимость геофизических работ;
– стоимость геохимических работ;
.
Указание
Обозначим: X 1 – запасы месторождения 1, X 2 – запасы месторождения 2. Значения запасов, приводящие к максимуму стоимости сырья (в тыс. долларов), которое возможно получить на двух месторождениях значения запасов, приводящие к максимуму стоимость сырья (в тыс. долларов), которое возможно получить на двух месторождениях . Функция, для которой ищется экстремум (максимум или минимум), носит название целевой функции. Беспредельному увеличению запасов препятствуют ограничения:
– объемы работ по экологической реабилитации площади работ;
– стоимость геофизических работ;
– стоимость геохимических работ. Кроме того, запасы – неотрицательное число, поэтому
.
Формально задача оптимизации записывается так:
Решение
Решим эту задачу в Excel.
Введите в ячейки A1, A2, A4:A8 рабочего листа текст. В ячейки B1, B2, A4:A8 введите нули (рис. X.1).
Рис. X.1. Размещение исходных данных задачи в документе Excel
В ячейку B4 введите формулу =50*B1+40*B2. Это целевая функция. В ячейку B6 введите формулу =2*B1+5*B2. В ячейку B7 введите формулу =8*B1+5*B2. В ячейку B8 введите формулу =5*B1+6*B2. Это ограничения.
Выделим ячейку B4, в которой вычисляется целевая функция, и вызовем Решатель (Сервис/Поиск решения). В диалоговом окне в поле ввода Установить целевую ячейку: уже содержится адрес ячейки с целевой функцией $B$4. Установим переключатель: Равной максимальному значению. Перейдем к полю ввода Изменяя ячейки:. В нашем случае достаточно щелкнуть кнопку Предположить и в поле ввода появится адрес блока $B$1:$B$2.
Перейдем к вводу ограничений. Щелкнем кнопку Добавить. Появится диалоговое окно Добавление ограничения. В поле ввода Ссылка на ячейку: укажите $B$6. Правее расположен выпадающий список с условными операторами (раскройте его и посмотрите). Выберем условие <=. В поле ввода Ограничение: введите число 20. У нас есть еще два ограничения, поэтому, не выходя из этого диалогового окна, щелкните кнопку Добавить и введите ограничение $B$7<=40. Аналогично добавить ограничение $B$8<=30. Ввод ограничений закончен, поэтому нажмите OK. Вы вновь окажитесь в диалоговом окне Поиск решения. Вы увидите введенные ограничения $B$6<=20, $B$7<=40 и $B$8<=30. Справа имеются кнопки Изменить и Удалить. С их помощью Вы можете изменить ограничение или стереть его. (Если Вы используете Excel 5.0/7.0, то Вы должны ввести еще одно ограничение $B$1:$B$2>=0).
Щелкните кнопку Параметры. Вы окажитесь в диалоговом окне Параметры поиска решения. Чтобы узнать назначение полей ввода этого окна, щелкните кнопку Справка. Менять ничего не будем, только установим два флажка: Линейная модель (так как наши ограничения и целевая функция являются линейными по переменным X 1 и X 2) и Неотрицательные значения (для переменных X 1 и X 2). В Excel 5.0/7.0 этот последний флажок отсутствует, поэтому и нужно было вводить ограничение $B$1:$B$2>=0. Щелкнем OK и окажемся в исходном окне.
Задача оптимизации полностью подготовлена. Нажимаем кнопку Выполнить. Появляется диалоговое окно Результаты поиска решения. В нем мы читаем сообщение: Решение найдено. Все ограничения и условия оптимальности выполнены. На выбор предлагаются варианты: Сохранить найденное решение или Восстановить исходные значения. Выбираем первое. Можно также вывести отчеты: по результатам, по устойчивости, по пределам.
После нажатия OK вид таблицы меняется: в ячейках X 1 и X 2 появляются оптимальные значения: X 1 – 3,913043 и X 2 – 1,73913. Соответственно пересчитываются все формулы. Целевая функция достигает значения 265,2174.
КОНТРОЛЬНЫЕ ВОПРОСЫ
1. Геологические образования и процессы как объекты изучения. Системы расположения точек наблюдений в геологии.
2. Погрешности измерений и погрешности аналогий. Шкалы измерений в геологии. «Выборочная», «геологическая» и «опробуемая» совокупности.
3. Виды моделирования в геологии. Этапы процесса решения геологических задач математическими методами.
4. Одномерные статистические модели. Числовые диаграммы «стебель с листьями» и «ящик с усами».
5. Статистические характеристики. Решение геологических задач с помощью гистограмм и кумулят.
6. Статистические законы распределения, используемые в геологии.
7. Специфика случайных угловых величин. Круговое среднее направление, круговая мода и круговая медиана.
8. Точечные и интервальные оценки свойств геологических объектов. Свойства точечных оценок.
9. Построение доверительных интервалов оценок средних значений.
10. Статистическая проверка гипотез. Ошибки первого и второго рода при статистической проверке гипотез.
11. Параметрические и непараметрические критерии согласия.
12. Проверка гипотезы о типе статистического распределения.
13. Решение геологических задач путем проверки гипотез о равенстве средних.
14. Решение геологических задач путем проверки гипотез о равенстве дисперсий.
15. Решение геологических задач путем проверки гипотезы об однородности выборки.
16. Решение геологических задач с помощью однофакторного и двухфакторного дисперсионного анализа.
17. Геологические объекты как двумерная статистическая совокупность. Описание двумерной статистической совокупности с помощью корреляционного поля точек.
18. Решение геологических задач путем проверки гипотезы о наличии корреляционной связи.
19. Оценка силы корреляционной связи.
20. Применение в геологии регрессионного анализа.
21. Описание характера корреляционной связи свойств геологических объектов уравнениями.
22. Проверка гипотезы о линейном характере корреляционной связи.
23. Применение многомерных статистических моделей в геологии.
24. Понятия парного, частного и множественного коэффициентов корреляции.
25. Методы выделения ассоциаций. Метод графов.
26. Принципы и области применения кластер-анализа.
27. Множественные регрессионные модели и их применение.
28. Распознавание образов в геологии.
29. Факторный анализ и метод главных компонент при решении геологических задач.
30. Моделирование пространственных переменных.
31. Непрерывные и дискретные геологические пространственные переменные, скалярные и векторные поля.
32. Фон и аномалия. Решение геологических задач с помощью тренд-анализа.
33. Способы «сглаживания» случайных полей.
34. Статистические методы проверки гипотез о наличии тренда.
35. Метод аппроксимации поверхностей тренда полиномами в геологии.
36. Моделирование дискретных случайных полей.
37. Понятие о моделировании с помощью случайных функций.
ЛИТЕРАТУРА
1. Аветисов А.Г., Булатов А.И., Шаманов Методы прикладной математики в инженерном деле при строительстве нефтяных и газовых скважин. – М.: ООО «Недра-Бизнесцентр», 2003. – 239 с.
2. Андронов А.М., Копытов Е.А., Гринглаз Л.Я. Теория вероятностей и математическая статистика: Учебник для вузов. – СПб.: Питер, 2004. – 461 с.
3. Вуколов Э.А. Основы статистического анализа. Практикум по статистическим методам и исследованию операций с использованием пакетов STATISTICA и EXCEL: Учебное пособие. – М.: ФОРУМ: ИНФРА-М, 2004. – 464 с.
4. Гайдышев И. Анализ и обработка данных: специальный справочник. – СПб.: Питер, 2001. – 752 с.
5. Гельман В.Я. Решение математических задач средствами Excel: Практикум – СПб: Питер, 2003. – 240 с.
6. Гмурман В.Е. Теория вероятностей и математическая статистика: Учеб. пособие для вузов. – 10-е изд., стер. – М.: Высш. шк., 2004. – 479 с.
7. Гмурман В.Е. Руководство к решению задач по теории вероятностей и математической статистике: Учеб. пособие для студентов вузов. – 9-е изд. стер. – М.: Высш. шк., 2004. – 404 с.
8. Горелова Г.В., Кацко И.А. Теория вероятностей и математическая статистика в примерах и задачах с применением EXCEL. – Ростов н/Д: Феникс, 2005. – 480 с.
9. Грановская Н.В., Наставкин А.В. Сборник задач для лабораторных и самостоятельных занятий по дисциплине «Математические методы моделирования в геологии». Для студентов геологических специальностей геолого-географического факультета. – Ростов н/Дону: 2002. – 40 с.
10. Гуськов О.И., Кушнарев П. И. Таранов С.М.. Математические методы в геологии. Сборник задач. М.: Недра,1991.
11. Каждан А.Б., Гуськов О.И. Математические методы в геологии. Учебник для вузов. – М.: Недра, 1990.
12. Лавренов С.М. Excel: Сборник примеров и задач. – М.: Финансы и статистика, 2002. – 336 с.
13. Мартьянова А.Е. Сборник примеров и задач. Лабораторный практикум по дисциплине «Статистическое моделирование на ЭВМ». /Учебно-методическое пособие для студентов специальности 250400 «Химическая технология природных энергоносителей и углеродных материалов». – Астрахань, 2007, 136 с.
14. Мартьянова А.Е. Сборник примеров и задач. Лабораторный практикум по дисциплине «Математические методы моделирования в геологии». /Учебное пособие для студентов направления 650100 «Прикладная геология» (электронный вариант). – Астрахань, 2005, 263 с.
15. Мартьянова А.Е. Математические методы моделирования в геологии. Сборник примеров и задач: Учебное пособие для студентов направления 650100 «Прикладная геология». – Астрахань, 2005, 268 с.
16. Минько А.А. Статистический анализ в MS EXCEL. – М.: Издательский дом «Вильямс», 2004. – 448 с.
17. Прозорова Г.Н. Методические указания к выполнению лабораторных работ по курсу «Методы математического моделирования в геологии» (для студентов очной и заочной форм обучения по специальности 08.05.00) – Ростов-на-Дону: Ростовский госуниверситет, 2004. – с. 34.
18. Теория вероятностей и математическая статистика: Учеб. пособие /Под ред. В.И. Ермакова – М.: ИНФРА-М, 2004. – 287 с.
19. Турчак Л. И. Основы численных методов: Учеб. пособие. – М.: Наука, 1987. – 320 с.
20. Microsoft Excel 2000: справочник /Под ред. Ю.В. Колесникова – СПб: Изд-во «Питер», 1999. – 480 с.
21. www.exponenta.ru
22. www.statsoft.com
ПРИЛОЖЕНИЯ
Приложение I. Значения функции нормального распределения с параметрами 0 и 1 (для отрицательных значений Z)
Z | 0,00 | 0,01 | 0,02 | 0,03 | 0,04 | 0,05 | 0,06 | 0,07 | 0,08 | 0,09 |
-0,0 | 0,5000 | 0,4920 | 0,4929 | 0,4880 | 0,4840 | 0,4801 | 0,4761 | 0,4721 | 0,4681 | 0,4641 |
-0,1 | 0,4602 | 0,4562 | 0,4522 | 0,4483 | 0,4443 | 0,4404 | 0,4364 | 0,4325 | 0,4286 | 0,4247 |
-0,2 | 0,4207 | 0,4168 | 0,4129 | 0,4090 | 0,4052 | 0,4013 | 0,3974 | 0,3936 | 0,3897 | 0,3859 |
-0,3 | 0,3821 | 0,3783 | 0,3745 | 0,3707 | 0,3669 | 0,3632 | 0,3594 | 0,3557 | 0,3520 | 0,3483 |
-0,4 | 0,3446 | 0,3409 | 0,3372 | 0,3336 | 0,3300 | 0,3264 | 0,3228 | 0,3192 | 0,3156 | 0,3121 |
-0,5 | 0,3085 | 0,3050 | 0,3015 | 0,2981 | 0,2946 | 0,2912 | 0,2877 | 0,2843 | 0,2810 | 0,2776 |
-0,6 | 0,2743 | 0,2709 | 0,2676 | 0,2643 | 0,2611 | 0,2578 | 0,2546 | 0,2514 | 0,2483 | 0,2451 |
-0,7 | 0,2420 | 0,2398 | 0,2358 | 0,2327 | 0,2297 | 0,2266 | 0,2236 | 0,2206 | 0,2177 | 0,2148 |
-0,8 | 0,2119 | 0,2090 | 0,2061 | 0,2033 | 0,2005 | 0,1977 | 0,1949 | 0,1922 | 0,1894 | 0,1867 |
-0,9 | 0,1841 | 0,1814 | 0,1788 | 0,1762 | 0,1736 | 0,1711 | 0,1685 | 0,1660 | 0,1635 | 0,1611 |
-1,0 | 0,1587 | 0,1562 | 0,1539 | 0,1515 | 0,1492 | 0,1469 | 0,1446 | 0,1423 | 0,1401 | 0,1379 |
-1,1 | 0,1357 | 0,1335 | 0,1314 | 0,1292 | 0,1271 | 0,1251 | 0,1230 | 0,1210 | 0,1190 | 0,1170 |
-1,2 | 0,1151 | 0,1131 | 0,1112 | 0,1093 | 0,1075 | 0,1056 | 0,1038 | 0,1020 | 0,1003 | 0,0985 |
-1,3 | 0,0968 | 0,0951 | 0,0934 | 0,0918 | 0,0901 | 0,0885 | 0,0869 | 0,0853 | 0,0838 | 0,0823 |
-1,4 | 0,0808 | 0,0793 | 0,0778 | 0,0764 | 0,0749 | 0,0735 | 0,0721 | 0,0708 | 0,0694 | 0,0681 |
-1,5 | 0,0668 | 0,0655 | 0,0643 | 0,0630 | 0,0618 | 0,0606 | 0,594 | 0,0582 | 0,0570 | 0,0559 |
-1,6 | 0,0548 | 0,0537 | 0,0526 | 0,0515 | 0,0505 | 0,0495 | 0,0485 | 0,0475 | 0,0465 | 0,0455 |
-1,7 | 0,04046 | 0,0436 | 0,0427 | 0,0418 | 0,0409 | 0,0401 | 0,0392 | 0,0384 | 0,0375 | 0,0367 |
-1,8 | 0,0359 | 0,0351 | 0,0344 | 0,0336 | 0,0329 | 0,0322 | 0,0314 | 0,0307 | 0,0300 | 0,0294 |
-1,9 | 0,0287 | 0,0281 | 0,0274 | 0,0268 | 0,0262 | 0,0256 | 0,0250 | 0,0244 | 0,0238 | 0,0233 |
-2,0 | 0,0227 | 0,0222 | 0,0217 | 0,0212 | 0,0207 | 0,0202 | 0,0197 | 0,0192 | 0,0188 | 0,0183 |
-2,1 | 0,0179 | 0,0174 | 0,0170 | 0,0166 | 0,0162 | 0,0158 | 0,0154 | 0,0150 | 0,0146 | 0,0143 |
-2,2 | 0,0139 | 0,0135 | 0,0132 | 0,0219 | 0,0125 | 0,0122 | 0,0119 | 0,0116 | 0,0113 | 0,0110 |
-2,3 | 0,0107 | 0,104 | 0,0102 | 0,0099 | 0,0096 | 0,0094 | 0,0091 | 0,0089 | 0,0087 | 0,0084 |
-2,4 | 0,0082 | 0,0080 | 0,0078 | 0,0075 | 0,0073 | 0,0071 | 0,0069 | 0,0068 | 0,0066 | 0,0064 |
-2,5 | 0,0062 | 0,0060 | 0,0059 | 0,0057 | 0,0055 | 0,0054 | 0,0052 | 0,0051 | 0,0049 | 0,0047 |
-2,6 | 0,0047 | 0,0045 | 0,0044 | 0,0043 | 0,0041 | 0,0040 | 0,0039 | 0,0038 | 0,0037 | 0,0036 |
-2,7 | 0,0035 | 0,0034 | 0,0033 | 0,0032 | 0,0030 | 0,0030 | 0,0029 | 0,0028 | 0,0027 | 0,0026 |
-2,8 | 0,0026 | 0,0025 | 0,0024 | 0,0023 | 0,0023 | 0,0022 | 0,0021 | 0,0020 | 0,0020 | 0,0019 |
-2,9 | 0,0019 | 0,0018 | 0,0017 | 0,0017 | 0,0016 | 0,0016 | 0,0015 | 0,0015 | 0,0014 | 0,0014 |
-3,0 | 0,0013 | 0,0013 | 0,0011 | 0,0011 | 0,0010 | 0,0010 | ||||
-3,1 | 0,0010 | 0,0009 | 0,0009 | 0,0009 | 0,0008 | 0,0008 | 0,0008 | 0,0008 | 0,0007 | 0,0007 |
-3,3 | 0,0005 | 0,0005 | 0,0004 | 0,0004 | 0,0004 | 0,0004 | 0,0004 | 0,0004 | 0,0004 | 0,0003 |
-3,4 | 0,0003 | 0,0003 | 0,0003 | 0,0003 | 0,0003 | 0,0003 | 0,0003 | 0,0003 | 0,0002 | 0,0002 |
-3,5 | 0,0002 | 0,0002 | 0,0002 | 0,0002 | 0,0002 | 0,0002 | 0,0002 | 0,0002 | 0,0002 | 0,0002 |
-3,6 | 0,0002 | 0,0002 | 0,0001 | 0,0001 | 0,0001 | 0,0001 | 0,0001 | 0,0001 | 0,0001 | 0,0001 |
-3,7 | 0,0001 | 0,0001 | 0,0001 | 0,0001 | 0,0001 | 0,0001 | 0,0001 | 0,0001 | 0,0001 | 0,0001 |
-3,8 | 0,0001 | 0,0001 | 0,0001 | 0,0001 | 0,0001 | 0,0001 | 0,0001 | 0,0001 | 0,0000 | 0,0000 |
Примечание
Значения функции для положительных Z находятся вычитанием из 1 значений функции для (-Z). Пример: для Z = 0,72 P= 1-0,2358 =0,7642.
Приложение II. Допустимые значения критерия Стьюдента при данном объеме выборки N и уровне значимости α
N | Двусторонняя критическая область | N | Двусторонняя критическая область | ||||||||
α = 0,1 | α = 0,05 | α = 0,02 | α = 0,01 | α = 0,001 | α = 0,1 | α = 0,05 | α = 0,02 | α = 0,01 | α = 0,001 | ||
6,31 | 12,71 | 31,82 | 63,66 | 636,62 | 1,73 | 2,10 | 2,55 | 2,88 | 3,92 | ||
2,92 | 4,30 | 6,97 | 9,93 | 31,60 | 1,73 | 2,09 | 2,54 | 2,86 | 3,88 | ||
2,35 | 3,18 | 4,54 | 5,84 | 12,94 | 1,73 | 2,09 | 2,53 | 2,85 | 3,85 | ||
2,13 | 2,78 | 3,75 | 4,60 | 8,61 | 1,72 | 2,08 | 2,52 | 2,83 | 3,82 | ||
2,02 | 2,57 | 3,37 | 4,03 | 6,86 | 1,72 | 2,07 | 2,51 | 2,82 | 3,79 | ||
1,94 | 2,45 | 3,14 | 3,71 | 5,96 | 1,71 | 2,07 | 2,50 | 2,81 | 3,77 | ||
1,90 | 2,37 | 3,00 | 3,50 | 5,41 | 1,71 | 2,06 | 2,49 | 2,80 | 3,75 | ||
1,86 | 2,31 | 2,90 | 3,36 | 5,04 | 1,71 | 2,06 | 2,49 | 2,79 | 3,73 | ||
1,83 | 2,26 | 2,82 | 3,25 | 4,78 | 1,71 | 2,06 | 2,48 | 2,78 | 3,71 | ||
1,81 | 2,23 | 2,76 | 3,17 | 4,59 | 1,70 | 2,05 | 2,47 | 2,77 | 3,69 | ||
1,80 | 2,20 | 2,72 | 3,11 | 4,44 | 1,70 | 2,05 | 2,47 | 2,76 | 3,67 | ||
1,78 | 2,18 | 2,68 | 3,06 | 4,32 | 1,70 | 2,05 | 2,46 | 2,76 | 3,66 | ||
1,77 | 2,16 | 2,65 | 3,01 | 4,22 | 1,70 | 2,04 | 2,46 | 2,75 | 3,65 | ||
1,76 | 2,15 | 2,62 | 2,98 | 4,14 | 1,68 | 2,02 | 2,42 | 2,70 | 3,55 | ||
1,75 | 2,13 | 2,60 | 2,95 | 4,07 | 1,67 | 2,00 | 2,39 | 2,66 | 3,46 | ||
1,75 | 2,12 | 2,58 | 2,92 | 4,02 | 1,66 | 1,98 | 2,36 | 2,62 | 3,37 | ||
1,74 | 2,11 | 2,57 | 2,90 | 3,97 | ∞ | 1,65 | 1,96 | 2,33 | 2,58 | 3,29 | |
N | α = 0,05 | α = 0,025 | α = 0,01 | α = 0,005 | α = 0,0005 | N | α = 0,05 | α = 0,025 | α = 0,01 | α = 0,005 | α = 0,0005 |
Односторонняя критическая область | Односторонняя критическая область |