Разработка программных средств анализа графика функции и решение оптимизационных задач (стр. 2 из 3)
Разделим отрезок [a, b] пополам точкой
Если 
(что практически наиболее вероятно), то возможны два случая: либо f(x) меняет знак на отрезке [a, c] (Рис. 1), либо на отрезке [c, b] (Рис. 2)  Рис. 1 |  Рис. 2 |
Выбирая в каждом случае тот отрезок, на котором функция меняет знак, и продолжая процесс половинного деления дальше, можно дойти до сколь угодно малого отрезка, содержащего корень уравнения.
6 РЕШЕНИЕ ЗАДАЧИ
Дана следующая функция:
F(х)=60*sin(5.5*x*pi/180)-69*cos(2.7*x*pi/180)-exp(x/192)-181/x
где Х изменяется от 0 до 400. Найти точки пересечения функции с точкой А (А=0).
Для нахождения точек пересечения используем метод половинного деления. Для этого от данной функции отнимем А (F(x)-А).
Построим алгоритм (приложение А).
Для того, что бы найти точки пересечения функции с точкой А, построим график (приложение В) по данным приведенным в таблице (приложение Г).
В графе Е2 введем формулу для нахождения значений где происходит смена знака =ЕСЛИ(В2*В3<=0; “смена знака”;” “).
По полученным данным найдем точки пересечения данной функции с точкой А в точках где происходит смена знака.
Например, смена знака происходит при значении Х=15, тогда в ячейку G2 введем значение Х1=15,а в ячейку G3 введем формулу =ЕСЛИ(J2*L2<=0;G2;I2). В ячейку Н2-значение Х2=20, а в ячейку Н3 введем формулу =ЕСЛИ(J2*L2<=0;I2;H2), это значит, что на этом интервале про исходит пересечение функции с координатной осью, то есть с точкой А. Для нахождения среднего значения в ячейку I2 введем формулу =(G2+H2)/2. В ячейки J2, K2, L2 введем формулы заданной в условии функции, где Х, для каждой из заданных ячеек, будет принимать значение Х1, Х2, Хср. соответственно.
Для того, чтобы определить на какой половине происходит смена знака в ячейку М2 введем формулу
=ЕСЛИ(J2*L2<=0;”смена знака на 1-ой половине”;”cмена знака на 2-ой половине”).
В столбце N приведено количество шагов, за которое будит достигнута точность определения значения (х) не ниже 0,001.
Для определения погрешности, в ячейку О2 введем формулу =0-L2. Таким образом из приведенной таблицы видно, что значение Х с точностью до 0,001 определено за 14 шагов.
| X1 | X2 | Xср | F(x1) | F(x2) | F(xcр) | Кол-во шагов | Погреш-ность | |
| 15,000 | 20,000 | 17,500 | -6,129 | 5,665 | 1,368 | смена знака на 1-ой половине | 1 | -1,3678 |
| 15,000 | 17,500 | 16,250 | -6,129 | 1,368 | -1,969 | смена знака на 2-ой половине | 2 | 1,9692 |
| 16,250 | 17,500 | 16,875 | -1,969 | 1,368 | -0,199 | смена знака на 2-ой половине | 3 | 0,1991 |
| 16,875 | 17,500 | 17,188 | -0,199 | 1,368 | 0,610 | смена знака на 1-ой половине | 4 | -0,6096 |
| 16,875 | 17,188 | 17,031 | -0,199 | 0,610 | 0,212 | смена знака на 1-ой половине | 5 | -0,2116 |
| 16,875 | 17,031 | 16,953 | -0,199 | 0,212 | 0,008 | смена знака на 1-ой половине | 6 | -0,0078 |
| 16,875 | 16,953 | 16,914 | -0,199 | 0,008 | -0,095 | смена знака на 2-ой половине | 7 | 0,0952 |
| 16,914 | 16,953 | 16,934 | -0,095 | 0,008 | -0,044 | смена знака на 2-ой половине | 8 | 0,0436 |
| 16,934 | 16,953 | 16,943 | -0,044 | 0,008 | -0,018 | смена знака на 2-ой половине | 9 | 0,0179 |
| 16,943 | 16,953 | 16,948 | -0,018 | 0,008 | -0,005 | смена знака на 2-ой половине | 10 | 0,0050 |
| 16,948 | 16,953 | 16,951 | -0,005 | 0,008 | 0,001 | смена знака на 1-ой половине | 11 | -0,0014 |
| 16,948 | 16,951 | 16,949 | -0,005 | 0,001 | -0,002 | смена знака на 2-ой половине | 12 | 0,0018 |
| 16,949 | 16,951 | 16,950 | -0,002 | 0,001 | 0,000 | смена знака на 2-ой половине | 13 | 0,0002 |
| 16,950 | 16,951 | 16,950 | 0,000 | 0,001 | 0,001 | смена знака на 1-ой половине | 14 | -0,0006 |
GHIJKLMNO
По полученным данным с помощью мастера диаграммпостроим график погрешности.
Для определения правильности решения произведем проверку с помощью подбора параметров.
Для этого в ячейку А107 введем формулу заданной функции, а в ячейку В107 введем значение Х при котором происходит смена знака. Далее необходимо поставить курсор в ячейку А107 и из меню сервис выбрать подбор параметра. В появившемся окне ввести необходимые данные, нажать кнопку ОК.
| А | В | |
| 105 | Подбор параметров | |
| 106 | F(X) | X |
| 107 | 0,0000 | 16,950 |
| 108 | 0,0005 | 28,806 |
| 109 | 0,0003 | 54,235 |
| 110 | 0,0000 | 98,448 |
| 111 | -0,0002 | 146,365 |
| 112 | 0,0000 | 158,039 |
| 113 | 0,0000 | 185,884 |
| 114 | 0,0001 | 230,163 |
| 115 | 0,0000 | 318,118 |
| 116 | 0,0009 | 361,607 |
В появившемся окне Результат подбора параметра нужно нажать
кнопку ОК, после чего в ячейках А107 и В107 появится результат поиска.
7 Понятие оптимизационных задач и оптимизационных моделей
Экономико-математические задачи, цель которых состоит в нахождении наилучшего, то есть оптимального с точки зрения одного или нескольких критериев варианта использования имеющихся ресурсов, называются оптимизационными.
Оптимизационные задачи решаются с помощью оптимизационных моделей методами математического программирования.
Математическое программирование – это раздел прикладной математики, который изучает задачи оптимизации и методы их решения с ориентацией на современные средства компьютерной техники.
Структура оптимизационной модели включает целевую функцию, области допустимых решений и системы ограничений, определяющих эту область. Целевая функция в самом общем виде также состоит из трех элементов:
· управляемых переменных;
· неуправляемых переменных;
· формы функции (вида зависимости между ними).
Область допустимых решений – это область, в пределах которой осуществляется выбор решений. В экономических задачах она ограничена наличными ресурсами и условиями, которые записываются в виде системы ограничений, состоящей из уравнений и неравенств.
Главная задача математического программирования – это нахождение экстремума функций при выполнении указанных ограничений. Если система ограничений несовместима, то область допустимых решений является пустой.
Сущность задач оптимизации: определить значение переменных х1, х2,..., хn, которые обеспечивают экстремум целевой функции Е, с учетом ограничений, наложенных на аргументы этой функции. При этом сложность решения задач зависит:
· от вида функциональных зависимостей, то есть от связи функции Е с элементами решения;
· от размерности задачи, то есть от количества элементов решения;
· от вида и количества ограничений, накладываемых на элементы решения.
8 РЕШЕНИЕ ЗАДАЧИ
Кондитерская фабрика для производства трех видов карамели А, В и С использует три вида сырья: сахарный песок, патоку и фруктовое пюре. Нормы расхода сырья на производство 1 кг. Карамели заданы в таблице.
| Наименование сырья | Нормы расхода (кг./кг.) | |||
| A | B | C | ||
| Сахарный песок | 0,6 | 0,5 | 0,6 | |
| Патока | 0,4 | 0,4 | 0,3 | |
| Фруктовое пюре | 0,1 | 0,2 | 0,2 | |
Запасы сырья на складе соответственно равны V1, V2 и V3 кг. Прибыль от реализации 1 кг. Продукции каждого вида определяется значениями РА, РВ и РС. Найти план производства карамели, обеспечивающий максимальную прибыль.
| Запасы сырья (кг.) | Прибыль от реализации (руб./кг.) | ||||
| V1 | V2 | V3 | Pa | Pb | Pc |
| 800 | 600 | 120 | 1,08 | 1,12 | 1,28 |
Подготовим задачу к решению.
Пусть х1 – карамель вида А (кг.)
х2 – карамель вида В (кг.)
х3 – карамель вида С (кг.).
Тогда система ограничений и целевая функция запишутся следующим образом:
Ра*Х1+Рв*Х2+Рс*Х3 =>mах (целевая функция);х1*0,6+х2*0,5+х3*0,6<=800
х1*0,4+х2*0,4+х3*0,3<=600 ограничения на запасы сырья (сахарный
х1*0.1+х2*0,2+х3*0,2<=120 песок, патока, фруктовое пюре)
х1>=0; x2>=0; x3>=0;
x1, x2, x3- целые числа.
Для решения задачи в Excel запишем ее в виде, представленном на таблице 1.
Таблица 1 – Таблица для решения задачи
| Кг. | ограничение | |||||
| х1 | 0 | 800 | >= | 0 | ||
| х2 | 0 | 600 | >= | 0 | ||
| х3 | 0 | 120 | >= | 0 | ||
| Mах прибыль: | 0 | |||||
В соответствии с условием прибыль должна быть максимальной, поэтому в таблице 1 добавлена строка «Mах прибыль». В ней буду суммировать прибыль от реализации продукции.