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

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

Размещено на

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

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

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

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

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

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

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

Отчет

Лабораторная работа №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 - Стоимость работ

Номер рабочего	Номер работы
	1	2	3	4
1	10	3	2	4
2	5	9	10	8
3	7	8	1	9
4	11	10	9	12
5	2	7	8	10

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

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

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

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

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

Номер рабочего	Номер работы
	1	2	3	4	5
1	10	3	2	4	100
2	5	9	10	8	100
3	7	8	1	9	100
4	11	10	9	12	100
5	2	7	8	10	100

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

(3)

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

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

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

i = 1-5,

j = 1-4.

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

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

, (4)

где ,

i = 1-4,

j = 1-5.