Построение моделей и решение нелинейных задач

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

«Вятский государственный университет»

(ФГБОУ ВПО «ВятГУ»)

Факультет автоматики и вычислительной техники

Кафедра электронных вычислительных машин

Построение моделей и решение нелинейных задач

Отчет

Лабораторная работа №3 по дисциплине

«Моделирование»

Вариант 8

Выполнил студент группы ВМ-32 ____________/Умрилов М.В./

Проверил старший преподаватель ____________/Блинова С.Д/.

Киров 2012

1. Цель работы и общие требования к её выполнению

В данной работе следует решить в среде Microsoft Excel с помощью программной модели Поиск решения транспортную задачу, систему нелинейных уравнений, задачу о назначениях, по заданным значениям составить уравнение регрессии. Решение каждой из задач должно быть найдено путём применения математических и алгоритмических моделей. Субъектом моделирования выступает проводящий работу студент.

2. Задача 1. Решение транспортной задачи

2.1 Постановка задачи

Требуется решить транспортную задачу, которая формулируется следующим образом: имеется пять пунктов производства и четыре пункта распределения продукции, стоимость перевозки единицы продукции с i-го пункта производства в j-ый центр распределения cij приведена в таблице 1.

еxcel модель решение уравнение

Необходимо составить план перевозок по доставке требуемой продукции, минимизирующий суммарные транспортные расходы.

Объект моделирования - процесс получения оптимального плана перевозок, а цель - минимизация затрат на перевозку по этому плану.

2.2 Разработка математической модели задачи

Входными данными являются значения, представленные в таблице 1. Необходимо так спланировать перевозки, чтобы минимизировать суммарные транспортные расходы. Поскольку суммарный объём привезенной продукции в данной задаче не равен суммарному объёму потребностей в ней, модель не сбалансирована, следовательно, это необходимо учесть при вводе ограничений в программную модель, т.е. суммарное потребление не должно превышать суммарного производства продукции.

Данная задача относится к классу транспортных задач, для которых математическая модель состоит из целевой функции и ограничений. В данной задаче целевой функцией будут суммарные транспортные расходы, которые следует минимизировать. Таким образом, математическая модель выражается системой

, (1)

где Z - полная стоимость перевозок;

- объём перевозок с -ого пункта производства в -ый пункт распределения;

-стоимость перевозки единицы продукции с -ого пункта производства в -ый пункт распределения;

i = 1-5;

j = 1-4.

Исходя из условий задачи, на данную модель накладываются ограничения, которые можно выразить следующей системой

, (2)

где - объём производства на -ом пункте производства;

- спрос в -ом центре распределения;

 - объём перевозок с -ого пункта производства в -ый пункт распределения;

i = 1-5;

j = 1-4.

2.3 Построение алгоритмической модели метода решения задачи

Для решения задачи, поставленной в 2.1, необходимо построить алгоритмическую модель по математической модели, описанной в 2.2. Алгоритмическая модель процесса решения задачи в виде схемы работы системы представлена на рисунке 1.

Рисунок 1 - Алгоритмическая модель нахождения оптимального плана перевозок транспортной задачи с использованием программной модели

Поиск решения

2.4 Результаты решения задачи

Данная задача решается с помощью программной модели Поиск решения.

Результаты решения задачи 1 представлены на рисунке 2.

Рисунок 2 - Экранная форма результата решения задачи 1

Транспортные расходы, соответствующие оптимальному плану перевозок, составляют 626 условных единиц. Оптимальный план перевозок, представленный на рисунке 2, отображает, как грузы перемещаются из пунктов производства в пункты распределения. Подставив для проверки полученные значения объёмов перевозок в формулу (1),

получаем: Z = 20*8+10*5+30*1+17*8+30*7+10*4 = 626.

3. Задача 2. Задача о назначениях

3.1 Постановка задачи о назнчаениях

Требуется решить задачу о назначениях, которая формулируется следующим образом: имеются пять рабочих и четыре вида работ. Стоимость cij выполнения i-ым рабочим j-ой работы приведена в таблице 2.

Таблица 2 - Стоимость работ

Необходимо составить план работ так, чтобы все работы были выполнены с минимальными затратами при условии, что каждый рабочий был занят только на одной из них.

Объект моделирования - процесс получения оптимального плана работ, а цель - минимизация затрат на работу.

3.2 Разработка математической модели

Входными данными являются значения представленные в таблице 2. Данная задача относится к классу линейных оптимизационных задач, для которых модель состоит из целевой функции и ограничений. Каждый рабочий выполняет только одну работу, а суммарная стоимость выполнения работ должна быть минимальной. Данная задача не сбалансирована, так как число рабочих меньше числа работ. Поэтому необходимо ввести фиктивную строку с большими штрафными стоимостями работ. Таблица 3 - новая таблица для данной задачи.

Таблица 3 - Модифицированная стоимость работ

Целевая функция Z для задачи 2 имеет вид

(3)

где Z - полная стоимость работ;

-затраты на выполнение работы -м рабочим -ой работы;

- переменная,

i = 1-5,

j = 1-4.

Переменная равна единице, если i-ым рабочим выполняется j-ая работа и равна нулю в противном случае.

Исходя из условий задачи, накладываются ограничения, которые можно выразить следующей системой

, (4)

где ,

i = 1-4,

j = 1-5.

3.3 Разработка алгоритмической модели метода решения задачи

Для решения задачи, поставленной в 3.1, необходимо построить алгоритмическую модель задачи, описанного в 3.2. Алгоритмическая модель процесса решения задачи в виде схемы работы системы представлена на рисунке 1.

3.4 Результаты решения задачи

Данная задача решается с помощью программного продукта, описанного в 1. Для применения этого средства в диалоговое окно Поиск решения вводятся исходные данные.

Результаты решения задачи 2 представлены на рисунке 3.

Рисунок 3 - Экранная форма результата решения задачи 2

Стоимость, соответствующая оптимальному плану составляет 14 условных единиц. Учитывая, что четвертая работа все-таки должна быть выполнена, следует выбрать для нее первого работника, так как стоимость выполнения им данной работы будет минимальна. Тогда реальная стоимость составляет 12 условных единиц.

Для проверки стоимости работ необходимо в целевую функцию из формулы (3) подставить значения из таблицы 3 и значения из оптимального плана работ. Таким образом, значение целевой функции равно Z = 2+3+1+100+8-100 = 14.

4. Задача 3. Система нелинейных уравнений

4.1 Постановка задачи 3

Найти все решения системы нелинейных уравнений

, (5)

где х, у - неизвестные переменные.

Объект моделирования - процесс получения решения совокупности уравнений системы (5), а цель- нахождение ее корней.

4.2 Разработка математической модели решения задачи

Исходными данными к задаче, поставленной в 4.1, являются уравнения системы (5). Выходными данными должны стать значения переменных х и у - вещественные числа, при которых система уравнений (5) будет действительна. Для того, чтобы применить программную модель Поиск решения необходимо привести систему (5) к уравнению вида

(5x2 + 6y2 -3)2 + (3x + 3y - 2)2 = 0 (6)

Проанализировав уравнение (6), можно сделать вывод, что существует не более двух точек пересечения эллипса и прямой. Определяемое решение зависит от начального приближения. Локализовать корни можно, протабулировав левую часть уравнения (6) по переменным (x,y) на отрезке от минус двух до двух с шагом 0,5.

4.3 Разработка алгоритмической модели решения СЛУ

Схема работы алгоритма при нахождении корней системы нелинейных уравнений (5) с использованием программной модели Поиск решения представлена на рисунке 1.

4.4 Результаты решения задачи

Данная задача решается с помощью программной модели Поиск решения. Для нахождения приближенных корней необходимо протабулировать левую часть уравнения (6).

Результаты решения задачи 3 представлены на рисунке 4.

Рисунок 4 - Экранная форма результата решения задачи 3

После выполнения поиска решения получилось два корня системы уравнений: (0,214; 0,759), (0,68; -0,14).

Проверить полученные корни можно с помощью подстановки уравнение (6). В результате получим значения погрешности вычисления равные 1,15*10-7 и 1,97*10-8 для первого и второго корня СУ соответственно. Мы получили верное количество корней, т.к. парабола и прямая (первое и второе уравнения системы) не могут иметь более двух точек пересечения.

5. Задача 4. Уравнение регрессии

5.1 Постановка задачи 4

Требуется построить линейную модель для двух наблюдаемых величин объема реализованных фирмой автомобилей за указанный срок. Параметры задачи приведены в таблице 4.

Таблица 4 - Объем реализованных автомобилей

Объект моделирования - график объема продаж автомобилей, а цель - как можно более точно составить функцию, описывающую этот график.

5.2 Анализ задачи

Входными данными являются значения представленные в таблице 4.

В качестве выходных данных должен быть представлен график объёма продаж автомобилей. Сумма разностей квадратов представляет собой функцию Z(x,y) вида

F(x)= mx+b, (7)

где х - номер недели;

m, b - коэффициенты линейной функции.

Коэффициенты m и b подбираются так, чтобы минимизировать сумму квадратов разностей, Z между наблюдаемыми и теоретическими значениями зависимой переменной y

 (8)

где n- число наблюдений.

Функция (8) является моделью для получения коэффициентов линейной функции (7), а так же функция (8) является ключевой, для получения промежуточных данных, необходимых для построения графика по уравнению (7).

5.3 Построение алгоритмической модели получения промежуточных результатов, необходимых для решения основной задачи

Коэффициенты, необходимые для построения линейной модели (7), находятся использованием программной модели Поиск решений ,

Схема работы алгоритма для нахождения коэффициентов линейной модели (7) с использованием средства Поиск решения представлена на рисунке 1.

5.4 Получение результата решения основной задачи

Результаты решения задачи 4 представлены на рисунке 5.

Рисунок 5 - Экранная форма результата решения задачи 4

Значение квадрата коэффициента корреляции R2, как видно из рисунка 8, равно 0,999. По коэффициенту корреляции можно судить о правомерности использования линейной модели, в данном случае его значение близко к единице, следовательно, данная линейная модель может использоваться для предсказания результатов.

6. Анализ результатов и выводы по достижению цели работы

еxcel модель решение уравнение

В ходе лабораторной работы для каждой из задач были составлены математические и алгоритмические модели, которые в ходе моделирования в среде Microsoft Excel доказали свою эффективность. Результаты, полученные в ходе решения каждой задачи на данных моделях, имеют высокую точность и удовлетворяют всем ограничениям, наложенным на них условиями задачи.

Размещено на Allbest.ru