 |
Комплекс лабораторных работ
|
|
|
|
Методические указания
по выполнению лабораторных работ
Дисциплина
«Моделирование»
Специальность 230101
«Вычислительные машины, комплексы, системы и сети»
Киров,2009
Печатается по решению редакционно-издательского совета
Вятского государственного университета
УДК 004.92(07)
Б
Рецензент: доктор технических наук, профессор кафедры РЭС А.В. Частиков
Блинова С,Д, Комплекс лабораторных работ. Методические указания по выполнению лабораторных работ/ С.Д. Блинова. – Киров: Изд-во ВятГУ, 2009. – 19 с.
Редактор Е.Г. Козвонина
Подписано в печать Усл.печ.л. 1,13
Бумага офсетная Печать копир Aficio 1022
Заказ №441 Тираж 27 Бесплатно
Текст напечатан с оригинал-макета, представленного автором.
610000, г.Киров, ул. Московская, 36.
Оформление обложки, изготовление – ПРИП ВятГУ
С.Д. Блинова, 2009
Вятский государственный университет, 2009
Содержание
1. Лабораторная работа №1. Формализация и алгоритмизация задач нахождения корней уравнений
2. Лабораторная работа №2. Составление и использование математических моделей для решения линейных оптимизационных задач
3. Лабораторная работа №3. Построение моделей и решение нелинейных задач
Лабораторные работы проводятся в среде Microsoft Excel, которая по сути является информационной моделью «поведения» субъекта моделирования (пользователя) в процессе познания (обучения) или практической деятельности. В ходе выполнения работ используются и другие информационные модели: математические, алгоритмические, программные.
Лабораторная работа №1
Формализация и алгоритмизация задач нахождения корней уравнений
|
|
|
Цель работы:
· научиться формализации задач при моделировании;
· научиться строить и использовать математические и алгоритмические модели для решения математических задач;
· освоить приемы работы с электронными таблицами.
Задание на лабораторную работу:
Найти корни исходных уравнений, используя заданные математические и программные модели для решения и среду Microsoft Excel.
Лабораторная работа состоит из трех частей, в каждой задача нахождения корней решается своим методом.
Задача №1. Нахождение корней уравнения F(x)=0 методом деления отрезка пополам
Постановка задачи: найти аналитически и графически корень уравнения х2 - 2 = 0 с точностью 10-4 , используя метод деления отрезка пополам.
Этапы решения задачи:
· анализ задачи с обязательным указанием объекта, субъекта, цели моделирования и выделением существенных свойств моделируемого объекта;
· формализация задачи и составление алгоритмической модели согласно заданному методу решения задачи;
· реализация модели, получение и анализ результатов решения задачи.
Первый этап решения предполагает системный анализ задачи, ее входных и выходных данных. Исходными данными для решения являются математическая модель в виде заданного уравнения, точность вычислений (E) и метод решения задачи. Метод деления отрезка пополам применяется, когда функция F(x) непрерывна и имеет значения разных знаков на концах диапазона [a,b] изменения аргумента x, т.е. F(a)*F(b)<=0. В таких случаях корень уравнения находится внутри отрезка [a,b], называемого отрезком локализации корня. Именно таким условиям отвечает решаемая задача. Значения отрезка локализации – вещественные числа, подстановка которых в исходное уравнение дает приближенные решения. Результатом являются вещественные числа - решение исходного уравнения с заданной точностью. Объектом моделирования является математическая модель – уравнение, субъектом – тот, кто его решает, цель моделирования – решение уравнения (нахождение всех его корней). Поскольку объект моделирования – модель, то в ней уже учтены все существенные свойства её объекта моделирования. Для правильного использования модели необходимо следовать требованиям по заданию области определения аргумента в уравнении.
|
|
|
На втором этапе составляется алгоритм решения задачи (алгоритмическая модель решения) по заданному методу деления отрезка пополам. Формализация задачи для получения алгоритмической модели выглядит следующим образом. Пусть с-корень уравнения F(x)=0. За исходное значение корня принимается число: c=(a+b)/2, которое далее уточняется, достигая заданной точности вычислений. Если F(a)*F(b)<=0, то новым отрезком локализации становится отрезок [a,b], иначе - отрезок [с,b]. Процесс деления отрезка продолжается до тех пор, пока его длина станет меньше заданной точности. В этом случае любая точка отрезка будет отличаться от корня не более, чем на половину E. Далее следует построить схему алгоритма решения задачи.
Третий этап реализации модели определяется средой, в которой будет решаться задача. Технология решения задачи в среде Microsoft Excel:
· за начальный отрезок локализации выбирается [0,2];
· исходные данные вводятся в следующие ячейки таблицы: D7->Точность;
E7->0,0001; D8->a; D9->0; E8->b; E9->2; G8->F(a)*F(c); F8->C; H8->F(c);
· алгоритм реализации метода вводится в ячейки: D10-> =ЕСЛИ(G9<=0;D9;F9); E10-> =ЕСЛИ(G9<=0;F9;E9); F9-> =(D9+E9)/2; G9-> =(D9^2-2)*(F9^2-2); H9-> =F9^2-2; I10-> =ЕСЛИ(E9-D9<$E$7;”Корень ”& ТЕКСТ (F9;”0,0000”); “Нет”).
· ячейки с формулами протаскиваются вниз по столбцам, пока не будет найден корень 1.414.
· самостоятельно, используя возможности среды Microsoft Excel, необходимо построить графическую модель решения задачи.
Аналогичным образом следует аналитически и графически найти второй корень заданного уравнения.
Задача №2. Пошаговое решение системы линейных уравнений (СЛУ) методом Гаусса
Задание: методом Гаусса найти корни СЛУ 2х1 +3х 2 +7х 3 +6х4 =1 3х1 +5х 2 +3х 3 +1х4 =3
5х1 +3х 2 +1х 3 +3х4 =4
3х1 +3х 2 +1х 3 +6х4 =5
Формализация задачи согласно методу ее решения и последовательность действий (алгоритмическая модель) по достижению результатов решения задачи:
|
|
|
· Введите исходные данные в диапазоны ячеек: А33:D36 – матрицу коэффициентов при неизвестных; E33:E36 – столбец свободных членов.
· Содержимое ячеек А33:Е33 скопируйте в ячейки А38:Е38, А43:Е43 и А48:Е48. В диапазон ячеек А39:Е39 введите формулу: {=A34:E34-$A$33:$E$33*(A34/$A$33)}, обращающую в нуль коэффициент при х1 во втором уравнении системы. Не забывайте нажимать клавиши < Ctrl >+< Shift >+< Enter > для работы с массивом ячеек.
· Выделите А39:Е39 и заполните диапазон А39:Е41, что обратит в нуль коэффициент при х1 в третьем и четвертом уравнениях системы.
· Скопируйте значения из А39:Е39 в А44:Е44 и А49:Е49. Для этого используйте команду Правка->Специальная вставка, где в диалоге в группе Вставить установите переключатель Значения.
· В ячейки А45:Е45 введите формулу: {=A40:E40-$A$39:$E$39*(В40/$В$39)}. Выделите диапазон А45:Е45 и протащите маркер заполнения, заполнив ячейки А45:Е46. Это обратит в нуль коэффициент при х2 в третьем и четвертом уравнениях системы.
· Скопируйте значения из А45:Е45 в А50:Е50. В А51:Е51 введите формулу: {=A46:E46-$A$45:$E$45*(С46/$С$45)}, обращающую в нуль коэффициент при х3 из четвертого уравнения системы. На этом прямая прогонка метода Гаусса завершена.
· Обратная прогонка заключается в вводе в диапазоны ячеек G36:K36, G35:K35, G34:K34 и G33:K33 следующих формул: {=A51:E51/D51}; {=(A50:E50-G36:K36*D50)/C50}; {=(A49:E49-G36:K36*D49-G35:K35*C49)/B49}; {=(A48:E48-G36:K36*D48-G35:K35*C48-G34:K34*B48)/A48}, соответственно. Решение СЛУ будет получено в ячейках К33:К36.
Проверьте найденные значения корней подстановкой их в уравнения системы.
Самостоятельно решите СЛУ по предложенному преподавателем варианту.
Задача №3. Нахождение корней уравнения F(x)=0 с помощью модели Подбор параметров
Постановка задачи: найти аналитически и графически все корни уравнения х3 - 0,01х2 - 0,7044х + 0,139104 = 0.
Этапы решения задачи с помощью программной модели Подбор параметров.
Первый этап – это анализ задачи. Поскольку уравнение задачи имеет третью степень, всех корней в уравнении может быть не более трех вещественных. Для их нахождения методом подбора нужна предварительная локализация. Протабулируйте исходный полином на отрезке [-1;1] с шагом 0,2. Для этого в ячейку А1 введите X, в В1 – Y, в диапазон А2:А12 – значения x, в В2 – формулу: =А2^3-0.01*А2^2-0.7044*F2+0.139104. Заполните диапазон В2:В12 значениями y. Просмотрев полученные значения, можно сделать вывод о смене полиномом знака на интервалах изменения аргумента: [-1;-0.8], [0,2;0,4] и [0,6;0,8]. Это означает наличие на каждом из них корня. Так как интервала три и корней может быть не более трех, то локализованы все корни.
|
|
|
Второй этап – это инициализация модели. Для решения задачи будет использована программа Подбор параметров, реализованная в среде Microsoft Excel как надстройка. Необходимо инициализировать программу, для чего задайте относительную погрешность вычислений (0,00001) и предельное число итераций (1000) на вкладке Вычисления диалогового окна Параметры команды Сервис->Параметры. В качестве начальных значений приближений к корням возьмите, например средние точки из отрезков локализации корней: -0,9; 0,3: 0,7. Введите их в ячейки С2:С4. В ячейку D2 введите формулу: =C2^3-0.01*C2^2-0.7044*C2+0.139104. Выделите эту ячейку и заполните диапазон D2:D4, получив значения полинома при начальных значениях приближений.
Третий этап – это получение результатов решения задачи по программной модели. Выберите команду Сервис->Подбор параметров и заполните диалоговое окно программы Подбор параметров следующим образом: Установить в ячейке – (щелчок на D2) - значение 0, изменяя значение ячейки – (щелчок на С2). После нажатия на OK программа Подбор параметров находит приближенное значение корня (0,919999) и помещает его в С2. Аналогично вычислите и поместите в ячейки С3 и С4 два оставшихся корня. Они должны быть равны 0,20999 и 0,71999, соответственно.
Далее следует самостоятельно построить графическую модель решения задачи и проверить её аналитическое решение. Также самостоятельно решите задачу нахождения корней согласно заданному варианту и постройте график заданной функции.
Отчет по лабораторной работе должен содержать описание всех этапов решения трех задач согласно заданным вариантам по требованиям стандартов на оформление технической документации.
Вопросы для самоконтроля:
v Что такое математическая модель? Как она получается, для чего используется?
v Что такое формализация задачи, для чего она необходима?
v Чем отличаются алгоритмические и программные модели решения задач?
v Перечислите объекты моделирования при решении задач лабораторной работы и используемые для них модели.
Лабораторная работа №2
Составление и использование математических моделей для решения линейных оптимизационных задач
В данной работе моделируется процесс решения линейных оптимизационных задач на примере трех типичных ситуаций: планирование производства, составление сплавов и смесей и планирование штатного расписания. При моделировании используется табличная форма представления исходных данных и полученных результатов.
|
|
|
1 Задача планирования производства красок
Исходные данные для задачи планирования представлены в таблице 1.
Таблица1 – Исходные данные для планирования
| Исходный продукт | Расход исходных продуктов на тонну краски, т | Возможный суточный запас, т | |
| Краска B | Краска H | ||
| Продукт 1 Продукт 2 |
Постановка задачи 1. Изучение рынка сбыта показало, что суточный запрос на краску H никогда не превышает запрос на B более чем на одну тонну, спрос на краску H никогда не превышает двух тонн в сутки. Оптовые цены одной тонны красок равны: 2000 руб. для краски Н и 3000 руб. для краски В.
Требуется узнать, какое количество краски каждого вида должна производить фабрика, чтобы доход от реализации продукции был максимальным.
Для решения задачи нужно построить математическую модель, для чего следует ответить на три вопроса:
а) Для нахождения каких величин (неизвестных) строится модель? Что является объектом моделирования?
б) Какова цель построения модели (цель моделирования)?
в) Каким ограничениям должны удовлетворять неизвестные?
Для данной задачи цель построения модели – максимизация прибыли. Неизвестными являются суточные объемы производства краски В – хb и Н – хh. Суммарная суточная прибыль от производства красок равна: Z = 3000Xb + 2000Xh. Z называется целевой функцией задачи, ее следует максимизировать. Ограничениями для задачи могут быть следующие: объем производства красок не может быть отрицательным, расход исходного продукта для производства обоих видов красок не может превосходить максимально возможный запас данного продукта, следовательно:
Xb + 2Xh £ 6, 2Xb + Xh £ 8.
Кроме того, ограничения на величину спроса на краски:
Xh – Xb £ 1, Xh £2.
Таким образом, математическая модель данной задачи формулируется так: максимизировать
Z = 3000Xb + 2000Xh
при следующих ограничениях:
Xb + 2Xh £ 6,
2Xb + Xh £ 8.
Xh – Xb £ 1,
Xh £ 2, Xh, Xb ³ 0.
Поскольку целевая функция и ограничения линейно зависят от переменных, данная модель является линейной.
Задача будет решаться с помощью программной модели Поиск решения. Данное средство является одной из надстроек Microsoft Excel.
Технология решения задачи.
· Отведите ячейки А3 и В3 под значения переменных хb и хh. В ячейку С4 введите целевую функцию: = 3000 * Xb + 2000 * Xh
· В ячейки А7: А10 введите левые части ограничений
= А3 + 2 * В3
= 2 * А3 + В3
= В3 – А3
= В3,
· а в ячейки В7: В10 – правые части ограничений.
· Выберите команду Сервис -> Поиск решения и заполните открывшееся диалоговое окно Поиск решения. При нажатии на кнопку Параметры открывается диалоговое окно Параметры поиска решения, в котором можно изменять условия и варианты поиска решения исследуемой задачи. Можно также загружать и сохранять оптимизируемые модели. Значения и состояния элементов управления, используемые по умолчанию, подходят для решения большинства задач.
· Нажмите кнопку Выполнить (Solve), откроется окно Результаты поиска (Solver Results), которое сообщит о найденном решении. Результатами расчета задачи (оптимальный план производства и соответствующая ему прибыль) являются: производство 3.3 т краски В и 1.3 т краски Н в сутки, что принесет фабрике 12.6 тыс. руб прибыли. Выведите отчеты по результатам и просмотрите их.
2 Задача определения состава сплавов
Постановка задачи 2. Для получения сплавов А и В используются металлы М1, М2, М3, М4, требования к содержанию которых в сплавах А и В следующие: сплав А должен содержать не более 80 % металла М1 и не более 30 % металла М2; сплав В должен содержать от 40 до 60 % М2, не менее 30 % М3 и не более 70 % М4. Характеристики и запасы руд для производства металлов представлены в таблице 2.
Таблица 2 – Характеристики и запасы руд
| Руда | Max запас, т | Состав, % | Цена, $/т | ||||
| М1 | М2 | М3 | М4 | Прочие | |||
Пусть цена 1 т сплава А равна 200 долларов, а 1 т сплава В – 210.
Необходимо максимизировать прибыль от продажи сплавов А и В.
Формализация задачи и построение математической модели её решения. Если обозначить через x1A, x2A, x3A, x4A и x1B, x2B, x3B, x4B соответствующие количества металлов для получения сплавов, а количество использованной i – ой руды - через yi, где i изменяется от 1 до 3, то математическая модель задачи будет иметь следующий вид.
Максимизировать
Z = 200 (x1A + x2A + x3A + x4A) + 210 (x1B + x2B + x3B + x4B) - 30y1 - 40 y2 - 50y3
при следующих ограничениях на состав сплавов
x1A £ 0.8 (x1A + x2A + x3A + x4A),
x2A £ 0.3 (x1A + x2A + x3A + x4A),
x2B £ 0.6 (x1B + x2B + x3B + x4B),
x2B ³ 0.4 (x1B + x2B + x3B + x4B),
x3B ³ 0.3 (x1B + x2B + x3B + x4B),
x4B £ 0.7 (x1B + x2B + x3B + x4B),
на характеристики и состав руды:
x1A + x1B £ 0.2 y1 + 0.1 y2 + 0.05 y3,
x2A + x2B £ 0.1 y1 + 0.2 y2 + 0.05 y3,
x3A + x3B £ 0.3 y1 + 0.3 y2 + 0.7 y3,
x4A + x4B £ 0.3 y1 + 0.3 y2 + 0.2 y3,
а также на диапазоны использования переменных
xiA ³ 0, xiB ³ 0, i Î [1,4],
0 £ y1 £ 1000,
0 £ y2 £ 2000,
0 £ y3 £ 3000.
Технология решения задачи с применением математической и программной моделей в среде Microsoft Excel.
· Отведите под переменные xiA, xiB, i Î [1,4] диапазон ячеек С3:D6, а под переменные yi, i Î [1,3] – F3:F5.
· В ячейку G9 введите выражение для целевой функции:
= 200*СУММ(C3:C6)+210*СУММ(D3:D6)–30*F3-40*F4-50*F5.
· В диапазон C8:C17 введите левые части ограничений:
= C3 – 0.8 * СУММ (C3: C6)
= C4 – 0.3 * СУММ (C3: C6)
= D4 – 0.6 * СУММ (D3: D6)
= 0.4 * СУММ (D3: D6) – D4
= 0.3 * СУММ (D3: D6) – D5
= D6 – 0.7 * СУММ (D3: D6)
= СУММ (C3: D3) – 0.2 * $F$3 – 0.1 * $F$4 – 0.05 * $F$5
= СУММ (C4: D4) – 0.1 * $F$3 – 0.2 * $F$4 – 0.05 * $F$5
= СУММ (C5: D5) – 0.3 * $F$3 – 0.3 * $F$4 – 0.7 * $F$5
= СУММ (C6: D6) – 0.3 * $F$3 – 0.3 * $F$4 – 0.2 * $F$5.
· В диапазон ячеек H3:H5 введите количество имеющихся запасов руд. Выберите команду Сервис-> Поиск решения и заполните открывшееся диалоговое окно Поиск решения. Значением целевой функции будет число 896250 (для сплава А потребуется 550,0,2025,1500, для сплава В – 0,650,975,0 металлов).
3 Задача планирования штатного расписания
Постановка задачи 3. Авиакомпании требуется определить число стюардесс для работы в течение 6 месяцев при условии, что любая из них должна пройти предварительную подготовку в течение месяца, включающую 100 часов полетного времени. Потребности в количестве человеко-часов летного времени: январь – 8000, февраль – 9000, март – 8000, апрель – 10000, май – 9000, июнь – 12000. Каждая полностью обученная стюардесса в месяце может иметь налет до 150 ч. На начало января у компании уже есть 60 опытных стюардесс, ни одну из них с работы не снимают. Установлено, что около 10 % обучаемых стюардесс по окончании обучения увольняются по разным причинам. Опытная стюардесса обходится авиакомпании в 800 долларов, а обучаемая – в 400 долларов в месяц. Нужно спланировать штат таким образом, чтобы минимизировать издержки авиакомпании за отчетные 6 месяцев.
Математическая модель для данной задачи представлена и проанализирована далее в более развернутой форме.
· Отведите диапазон ячеек B3:B8 под фактическое число новых стюардесс, принимаемых на работу с января по июнь (неизвестные - фактическое число работающих).
· В ячейки C3:C8 введите требуемое число человеко–часов налета по месяцам.
· В ячейки F12 и G12 введите допустимый налет обучаемой и работающей стюардесс.
· В ячейки D12 и E12 введите затраты на обучение и работу стюардессы.
· В ячейку В2 введите число стюардесс, работающих в декабре. В диапазоне ячеек D3:D8 вычислите число стюардесс, постоянно работающих в текущем месяце, введя в ячейки D3 и D4 формулы: = В2; = D3 + 0.9 * B3 последнюю протаскивая на диапазон D5:D8.
· В диапазоне E3:E8 вычислите налет по месяцам, введя в ячейку E3 формулу:
= D3 * $G$12 + B3 * $F$12 и протаскивая ее на диапазон E4:E8. В диапазоне F3:F8 вычислите затраты по месяцам, введя в ячейку F3: = D3 * $Е$12 + B3 * $D$12 и протаскивая ее на диапазон F4:F8.
· Суммарные затраты на планируемый период (целевая функция) вычислите в ячейке F9 по формуле: = СУММ(F3:F8).
· Выберите команду Сервис->Поиск решения и заполните открывшееся окно. Ограничения: неотрицательные и целые значения неизвестных; фактическое число налёта работающих не должно быть меньше требуемого.
Согласно полученным расчетам (0,0,0,10,0,17) фирма в июне должна взять на обучение 17 новых стюардесс. Если по каким-либо причинам авиакомпания решила не брать в июне на обучение новых стюардесс, то в поле Ограничения диалогового окна Поиск решения следует добавить В8 = 0. Оптимальное решение при таком дополнительном ограничении приведет к временному повышению текущих затрат (в июне, например, с 62000 до 64560). Просмотрите результаты, отчеты и проанализируйте полученные решения задачи.
Далее следует самостоятельно построить математическую модель заданного варианта линейной оптимизационной задачи и решить ее аналогичным рассмотренному способом.
Отчет по лабораторной работе должен содержать описание всех этапов решения задачи в соответствии с заданным вариантом по требованиям стандартов на оформление технической документации.
Вопросы для самоконтроля:
v Что такое информационная модель? Чем она отличается от натурной модели?
v Для чего нужны модели? Укажите их главное назначение.
v Каковы основные этапы построения моделей?
v Уточните основные этапы построения математических формул.
v Какие формы представления данных использовались в лабораторной работе? Что их характеризует?
Лабораторная работа №3.
Построение моделей и решение нелинейных задач
В данной работе следует решить в среде Microsoft Excel с помощью надстройки Поиск решения транспортную задачу, систему нелинейных уравнений, задачу о назначениях, уравнение регрессии (линейное и экспоненциальное) и транспортную задачу с фиксированными доплатами
.
Постановка, построение моделей и решение транспортной задачи
Фирма имеет четыре фабрики (в Денвере, Бостоне, Новом Орлеане и Далласе с производственными возможностями, соответственно 200, 150, 225 и 175 единиц продукции ежедневно) и пять центров распределения ее товаров (в Лос-Анджелесе, Далласе, Сент-Луисе, Вашингтоне, Атланте с потребностями, соответственно в 100, 200, 50, 250, 150 единиц продукции ежедневно). Хранение на фабрике единицы продукции, не поставленной в центр распределения, обходится в 0.75 долларов в день, а штраф за просроченную поставку единицы продукции, заказанной потребителем в центре распределения, но там не находящейся, равен 2.5 долларов в день. Стоимость перевозки единицы продукции с фабрик в пункты распределения дана в таблице 3.
Таблица 3
| Лос-Анджелес | Даллас | Сент-Луис | Вашингтон | Атланта | |
| Денвер | 1.5 | 1.75 | 2.25 | 2.25 | |
| Бостон | 2.5 | 1.75 | 1.5 | ||
| Новый-Орлеан | 1.5 | 1.5 | 1.75 | 1.75 | |
| Даллас | 0.5 | 1.75 | 1.75 | 1.75 |
Необходимо так спланировать перевозки, чтобы минимизировать суммарные транспортные расходы.
Проанализировав задачу, пришли к следующим выводам. Поскольку суммарный объем произведенной продукции в данной задаче равен суммарному объему потребностей в ней, модель сбалансирована. В ней не надо учитывать издержки, связанные со складированием и с недопоставками продукции.
Следует построить математическую модель задачи. Неизвестными здесь являются: объемы перевозок xij с i – ой фабрики на j – ый центр распределения, стоимость перевозки единицы продукции cij с i – ой фабрики на j – ый центр распределения. Целевой функцией будут суммарные транспортные расходы, которые следует минимизировать. Ограничения: объемы перевозок не могут быть отрицательны (xij ³ 0, i Î [1,4], j Î[1,5]) и вся продукция должна быть вывезена с фабрик, а потребности всех центров распределения должны быть удовлетворены полностью, т.е.
 |
где ai – объем производства на i – ой фабрике;
bj– спрос в j – ом центре распределения.
Данная задача легко решается с помощью средства поиска решения. Введите данные: стоимость перевозок - в ячейки A1:E4; объемы производства на фабриках - в G6:G9, потребность продукции в пунктах распределения - в A11:E11; целевую функцию =СУММПРОИЗВ(A1:E4;A6:E9) – в F10. Ячейки A6:E9 отведите под значения неизвестных (объемы перевозок). В ячейки A10:E10 введите формулы: =СУММ(A6:A9), =СУММ(B6:B9), =СУММ(C6:C9), =СУММ(D6:D9), =СУММ(E6:E9), определяющие объем продукции, ввозимой в центры распределения. В ячейки F6:F9 введите формулы: =СУММ(A6:E6), =СУММ(A7:E7), =СУММ(A8:E8), =СУММ(A9:E9), вычисляющие объем продукции, вывозимой с фабрик.
Выберите команду Сервис-> Поиск решения и заполните диалоговое окно Поиск решения. Не забудьте в диалоговом окне Параметры поиска решения установить флажок Линейная модель. После нажатия кнопки Выполнить средство поиска решений находит оптимальный план поставок продукции и соответствующие ему транспортные расходы (975 долларов), как показано на рисунке 1.
Рисунок 1- Оптимальный план поставок продукции
Проверьте правильность решения задачи.
Задача решения системы нелинейных уравнений
Кроме оптимизационных задач, средство поиска решений позволяет находить решения систем нелинейных уравнений. Далее процесс решения рассмотрен на примере следующей системы уравнений
X2 + Y2 = 3
2*X + 3*Y = 1.
Решением данной системы является пара (x,y), при которой (x2 + y2 – 3y)2 + (2x + 3y -1)2 = 0. Данное уравнение будет решаться с помощью средства поиска решения. Проанализировав его, следует отметить, что решением являются не более двух точек пересечения окружности с радиусом, равным трем, и прямой. Определяемое решение зависит от начального приближения, удачный подбор которого очень важен. Локализовать корни можно, например, протабулировав левую часть уравнения по переменным x,y на отрезке от минус трёх до трёх с шагом 1.5.
Введите в A2:A6 и B1:F1 значения x и y, соответственно. В ячейку B2 введите формулу: =($A2^2+b$1^2-3)^2+(2*$A2+3*B$1-1)^2. Протащите формулу на диапазон B2:F6. Из полученных данных видно, что за начальное приближение к корню разумно выбрать пары значений: (-1.5;1.5), (1.5;0), (1.5;-1.5).
Для нахождения первого корня отведите под переменные x и y ячейки A10 и B10, соответственно и введите в них начальные приближения –1.5 и. 1.5. В ячейку C10 введите формулу =(A10^2+B10^2-3)^2+(2*A10+3*B10-1)^2, Вызовите команду Сервис-> Поиск решения и заполните диалоговое окно Поиск решения: в поле Установить целевую ячейку введите C10; в поле Изменяя ячейки - A10:B10; в группе Равной - переключатель в положение Значению, а в поле ввода введите 0; в диалоговом окне Параметры поиска решения снимите флажок Линейная модель. Нажмите на кнопку Выполнить. В ячейках A10:B10 появятся значения –1.268 и 1.179, в ячейке C10 - значение 8.89Е-09.
Найдите второе решение, используя начальное приближение (1.5;-1.5). Решением должны быть значения 1.576 и –0.717. Убедитесь, что начальное приближение (1.5;0) приводит к тому же результату.
Задача о назначениях
Постановка задачи рассмотрена на типичном примере решения задачи о назначениях. Четверо рабочих могут выполнять четыре вида работ. Стоимости cij выполнения i–ым рабочим j- ой работы занесите в ячейки диапазона A1:D4, как показано на рисунке 1.
Рисунок 1 – Стоимости выполнения работ
В таблице на рисунке 1 строки соответствуют рабочим, а столбцы – работам. Нужно составить план выполнения работ так, чтобы все работы были выполнены, каждый рабочий был загружен только одной работой, а суммарная стоимость выполнения всех работ была минимальной.
Поскольку число работ в данной задаче равно числу рабочих, модель сбалансирована. В противном случае перед началом решения в нее вводят недостающее число фиктивных строк или столбцов с достаточно большими щтрафными стоимостями работ.
Следует построить математическую модель задачи. Пусть переменная xij = 1, если i – ым рабочим выполнена j – ая работа, в остальных случаях она равна 0. Тогда модель имеет вид
 |
При ограничениях:
 |
Для решения этой задачи отведите под неизвестные диапазон ячеек F2:I5. В ячейку J1 введите целевую функцию: =СУММПРОИЗВ(F2:I5;A1:D4), вычисляющую стоимость работ. В ячейки J2:J5 и F6:I6 введите формулы, задающие левые части ограничений.
Выберите команду Сервис-> Поиск решения и заполните диалоговое окно Поиск решения: В качестве целевой ячейки введите $J$1, диапазон изменяемых ячеек – $F$2:$I$5, ограничения - $F$2:$I$5<=1,. $F$2:$I$5 = целое, $F$2:$I$5 >=0, $J$2:$J$5 =1. После нажатия кнопки Выполнить средство поиска решений находит оптимальное решение (стоимость работ = 18) и оптимальный план работ
Замечание – флажок Формулы ДО Параметры (Сервис-> Параметры) обеспечивает отображение формул в ячейках, где они есть.
Решение уравнения регрессии с использованием линейной модели
Далее рассмотрено решение задачи нелинейной оптимизации с помощью средства поиска решения на примере построения линейного уравнения регрессии.
Постановка задачи, построение моделей и решение. Имеются две наблюдаемые величины x и y, например, объем реализации фирмы, торгующей подержанными автомобилями, за шесть недель ее работы. Значения этих наблюдаемых величин x=(1,2,3,4,5,6); y=(7,9,12,13,14,17), где x – отчетная неделя, а y – объем реализации за эту неделю, поместите в ячейки (A2:A7) и (B2:B7) соответственно. Столбец С выделите под теоретические значения y. Необходимо построить линейную модель y=mx + b, наилучшим образом описывающую наблюдаемые значения. Обычно коэффициенты m и b подбираются так, чтобы минимизировать сумму квадратов разностей между наблюдаемыми и теоретическими значениями зависимой переменной y, т.е. минимизировать
где n - число наблюдений (в данном случае n = 6).
Для решения задачи отведите под переменные m и b ячейки D3 и E3, соответственно, а в ячейку F3 введите минимизируемую функцию =СУММКВРАЗН(B2:B7;E3+D3*A2:A7), которая вычисляет сумму квадратов разностей для элементов указанных массивов.
Выберите команду Сервис-> Поиск решения и заполните открывшееся диалоговое окно Поиск решения следующим образом: в целевую ячейку внесите $F$3; задача - на минимум; изменять ячейки - $D$3:$E$3; ограничений нет. Результатом должны стать m = 1,88571; b = 5,400; целевая функция равна 1,77143.
Коэффициенты m, b можно найти и другим способом. Постройте точечный график по диапазону ячеек A2:B7 Назовите график - «Динамика продажи», ось Х – «Недели», ось Y – «Машины, шт». Выделите точки графика двойным щелчком, а затем щелкните их правой кнопкой мыши. В контекстном меню выберите команду Линии тренда, в диалоговом окне Линии тренда на вкладке Тип в группе Построение линии тренда (аппроксимация и сглаживание) выберите параметр Линейная, а на вкладке Параметры установите флажки Показывать уравнение на диаграмме и Поместить на диаграмму величину достоверности аппроксимации (R^2), т.е. на диаграмму нужно поместить значение квадрата коэффициента корреляции. По коэффициенту корреляции можно судить о правомерности использования линейного уравнения регрессии. Если он лежит в диапазоне от 0,9 до 1, то данную зависимость можно использовать для предсказания результата. Чем ближе к единице коэффициент корреляции, тем более обоснованно это указывает на линейную зависимость между наблюдаемыми величинами. Если коэффициент корреляции близок к -1, то это указывает на обратную зависимость между наблюдаемыми величинами. Флажок Пересечение кривой с осью Y в точке устанавливается только в случае, если эта точка известна. В результате выполнения команды Линии тренда появится график линии тренда, по которому видно, что квадрат коэффициента корреляции равен 0,9723. Следовательно, линейная модель может быть использована для предсказания результатов. На основе найденных коэффициентов уравнения регрессии можно определить теоретические значения наблюдаемой величины y. Введите в ячейку C2 формулу =$D$3*A2+$E$3. Протяните C2 до C7, получите значения, соответственно (7,9,11,13,15,17). Те же значения можно получить и без предварительного определения коэффициентов линейной модели, например, теоретическое значение в ячейке C2 можно определить по формуле =ПРЕДСКАЗ(A2;$B$2:$B$7;$A$2:$A$7).
Решение уравнения регрессии по экспоненциальной модели
Другой часто встречающейся на практике регрессионной моделью является экспоненциальная, которая описывается уравнением y=bmx. Значения экспоненциального тренда можно предсказывать функцией РОСТ, а значения параметров экспоненциальной модели определяются с помощью функции ЛГРФПРИБЛ. Можно построить одномерную экспоненциальную модель графически. Для построения экспоненциального уравнения тренда продажи подержанных автомобилей за 7, 8 и 9-ю недели торговли (данные предыдущей задачи) следует выполнить следующее. Значения наблюдаемых величин x=(1,2,3,4,5,6,7,8,9); y=(7,9,12,13,14,17), где x – отчетная неделя, а y – объем реализации за эту неделю, поместите в ячейки (A2:A10) и (B2:B7) соответственно. Столбец С выделите под теоретические значения y. В диапазон ячеек В8:В10 (Линейный прогноз) введите формулу построения линейного тренда =ТЕНДЕНЦИЯ(B2:B7;A2:A7;A8:A10); в C2:C10 (Нелинейный прогноз) – формулу построения экспоненциального тренда =РОСТ(B2:B7;A2:A7;A2:A10). Оба тренда тесно связаны между собой. В диапазон ячеек D2:D10 (Преобразованный линейный прогноз) введите формулу = EXP(ТЕНДЕНЦИЯ(LN(B2:B7);A2:A7;A2:A10)). Убедитесь, что значения в диапазонах C2:C10 и D2:D10 совпадают. В диапазоны ячеек F2:G2 (m и b линейной функции) введите формулу =ЛИНЕЙН (B2:B7;A2:A7), в диапазон F3:G3 (m и b функции приближенной) - =ЛГРФПРИБЛ (B2:B7;A2:A7) для определения параметров линейной и экспоненциальной моделей соответственно. В F4 (ln m) введите формулу =Ln(F3). Постройте точечный график, как в предыдущей задаче, выбрав параметр Экспоненциальная в команде Линии тренда. Квадрат коэффициента корреляции экспоненциальной модели равен 0,947 и меньше его значения в линейной модели, равное 0,9923. Таким образом, для данного примера линейная модель более достоверно описывает зависимость между наблюдаемыми величинами.
Примечание: не забывайте нажимать комбинацию клавиш Ctrl + Shift + Enter при заполнении массивов ячеек!
Транспортная задача с фиксированными доплатами
Далее рассмотрен пример нелинейной задачи, которая становится линейной после введения вспомогательных переменных. Пусть, как в обычн
|
|
|
