Технология решения оптимизационных задач средствами программы MathCAD
Понятие линейного программирования и оптимизации. Основы работы в системе MathCAD. Интерфейс пользователя, входной язык и тип данных. Этапы компьютерного математического моделирования. Пример решения оптимизационной задачи средствами программы MathCAD.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 16.10.2011 |
| Размер файла | 352,8 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
1. Определить число и состав базисных и свободных переменных.
2. Выразить базисные переменные через свободные переменные.
3. Выразить целевую функцию через свободные переменные.
4. Построить начальную симплекс-таблицу.
5. Проверить решение на оптимальность: если в F-строке (кроме С0) все Сj0, то получено оптимальное решение: X= (B1,.,Bm,0,.,0), F=C0. Если же существует Cj<0, то решение можно улучшить, но предварительно надо проверить факт существования решения.
6. Проверить существование решения: рассмотрим все столбцы, у которых Сj<0, если существует хотя бы один столбец, у которого все коэффициенты Ai,j<0, то задача решения не имеет, т.к. множество допустимых решений D не ограничено и целевая функция неограниченно возрастает. Если таких столбцов нет, то переходим к следующему этапу.
7. Выбрать свободную переменную, которую надо ввести в базис (выбор разрешающего столбца): это столбец, с минимальным значением Сj (пусть это k-й столбец).
8. Выбрать базисную переменную, которую надо вывести из базиса (выбор разрешающей строки): рассмотрим k-й столбец и все его элементы, которые больше нуля, т.е. Ai,k>0; для всех этих элементов находим отношение Bi/Ai,k и выбираем строку, которая соответствует минимальному значению этого отношения (пусть это i-я строка); соответствующая i-я переменная Xi выводится из базиса; при нескольких одинаковых отношениях берем любую строку; элемент Ai,k называется разрешающим элементом.
9. Пересчитать симплекс-таблицу: составляем новую симплекс-таблицу заменив в составе базисных переменных Xi на Xk; заполняем сначала новую k-ю строку, записывая в нее элементы старой i-ой строки, поделенные на разрешающий элемент; после заполнения k-ой строки заполняем оставшиеся строки; для этого k-ю строку умножаем последовательно на такие числа, чтобы после сложения ее с каждой строкой старой таблицы в k-ом столбце получить везде ноль (кроме единицы в k-ой строке).
10. После заполнения новой симплекс-таблицы алгоритм возвращается к 5-му пункту.
Конец работы алгоритма:
µ либо когда в F-строке все коэффициенты (кроме С0) будут больше нуля, тогда получаем оптимальное решение;
µ либо когда существует столбец, у которого Cj<<0 и все коэффициенты Ai,j<<0, в этом случае решения не существует.
Рассмотрим задачу: Задача линейного программирования имеет вид:
Решение:
Число базисных переменных: 2
Состав базисных переменных: Х3, Х4
Выражение базисных переменных через свободные переменные:
Выражение целевой функции через свободные переменные:
Начальная симплекс-таблица
Таблица 2
Начальная симплекс-таблица
|
Базисная переменная |
Свободная переменная |
X1 |
X2 |
X3 |
X4 |
|
|
X3 |
1 |
1 |
-2 |
1 |
0 |
|
|
X4 |
3 |
1 |
3 |
0 |
1 |
|
|
F (X) |
-1 |
-2* |
2 |
0 |
0 |
В F-строке есть отрицательный коэффициент (*), поэтому решение неоптимальное. В соответствующем столбце все коэффициенты положительные, поэтому решение можно улучшить.
Х1 - свободная переменная, которую надо ввести в базис.
Х3 - базисная переменная, которую надо вывести из базиса.
(т.к. отношение 1/1 меньше, чем 3/1).
Новая симплекс-таблица
Таблица 3
Новая симплекс-таблица
|
Базисная переменная |
Свободная переменная |
X1 |
X2 |
X3 |
X4 |
|
|
X1 |
1 |
1 |
-2 |
1 |
0 |
|
|
X4 |
2 |
0 |
5 |
-1 |
1 |
|
|
F (X) |
-1 |
-0 |
-2 |
2 |
0 |
В F-строке есть отрицательный коэффициент, поэтому решение пока не оптимальное. В соответствующем столбце не все коэффициенты отрицательны, поэтому решение можно улучшить.
Х2 - свободная переменная, которую надо ввести в базис.
Х4 - базисная переменная, которую надо вывести из базиса.
Новая симплекс-таблица
Таблица 4
Новая симплекс-таблица
|
Базисная переменная |
Свободная переменная |
X1 |
X2 |
X3 |
X4 |
|
|
X1 |
9/5 |
1 |
-0 |
3/5 |
2/5 |
|
|
X2 |
2/5 |
0 |
1 |
-1/5 |
1/5 |
|
|
F (X) |
9/5 |
-0 |
0 |
8/5 |
2/5 |
В F-строке все коэффициенты неотрицательны, поэтому полученное решение является оптимальным.
Оптимальное решение: Х= (9/5; 2/5; 0; 0)
Максимум целевой функции: F (Х) = 9/5
Вернемся к этапам математического моделирования. Разработка алгоритма и составление программы для ЭВМ - это творческий трудно формализуемый процесс. решать задачу можно с помощью языка программирования, а можно использовать специальный математический пакет, например, MathCAD.
После составления программы решаем с ее помощью простейшую тестовую задачу (желательно с заранее известным ответом) с целью устранения грубых ошибок. Это - лишь начало процедуры тестирования. Тестирование может продолжаться очень долго.
Затем следует собственно численный эксперимент, и выясняется, соответствует ли модель реальному объекты (процессу). Модель адекватна реальному процессу, если некоторые характеристики процесса, полученные на ЭВМ, совпадают с экспериментальными с заданной степенью точности. В случае несоответствия модели реальному процессу возвращаемся к одному из предыдущих этапов.
2.2 Пример решения оптимизационной задачи
Цех малого предприятия должен изготовить 100 изделий трех типов и не менее 20 штук изделий каждого типа. На изделия уходит 4, 3.4 и 2 кг металла соответственно, при его общем запасе 340 кг, а также расходуются по 4.75, 11 и 2 кг пластмассы, при ее общем запасе 700 кг. Прибыль, полученная от каждого изделия равна 4, 3 и 2 р. Определить, сколько изделий каждого типа необходимо выпустить для получения максимальной прибыли в рамках установленных запасов металла и пластмассы.
Математически задача запишется так: .
Также должны выполняться следующие ограничения:
В системе MathCAD такие задачи решаются с помощью блоков Given-Maximize и Given-Minimize.
Так же, как и при решении систем уравнений, решающий блок состоит из нескольких компонент, следующих на листе в строго определенном порядке:
1. Присваивание начальных значений переменным, относительно которых решается задача оптимизации:
х, y, z - изделия трех типов;
F - целевая функция.
2. Определение целевой функции.
F=
3. Директива Given.
Здесь мы прописываем все ограничения и необходимые условия для решения данной задачи.
4. Ограничения, записываемые в обычной математической форме. Могут использоваться все указанные выше знаки отношений, но вместо простого знака равенства "=" используется оператор логического равенства (вводится путем нажатия Ctrl-=).
5. Обращение к одной из функций Minimize или Maximize для соответственно минимизации или максимизации. Первым аргументом всегда является имя целевой функции. Далее следуют имена переменных, относительно которых решается задача. Функция возвращает вектор значений, где первый элемент соответствует первой переменной в списке аргументов, второй элемент - второй переменной и так далее.
Решение:
Система определила, что решением задачи являются значения: x = 56, y = 20, z = 24.
Следовательно, для получения максимальной прибыли при минимальных затратах расходного материала (метал и пластмасса) необходимо изготовить 56 изделий типа x,20 изделий типа y, 24 изделия типа z.
Заключение
Пакет MathCAD - инструмент для современных инженерных вычислений.
Пакет MathCAD предназначен для увеличения производительности индивидуальной работы математиков-программистов и повышения эффективности совместной работы инженерных групп. Для обращения ко всему богатству своих возможностей по автоматизации математических и научных расчётов пакет предоставляет пользователю лёгкий и дружественный интерфейс. Пакет MathCAD сочетает в себе мощнейший расчётный блок, функции которого доступны через общепризнанный интерфейс записи математических формул в обычной математической нотации и не требует предварительного изучения специального языка. Пакет также содержит полноценный текстовый редактор, графический модуль, экспертную документацию, контекстно-зависимый Help.
В практике математических прикладных вычислений важная роль принадлежит оптимизационным задачам, например таким, как поиск минимальных и максимальных значений функций одной или нескольких переменных. MathCAD дает разнообразные возможности решения задач оптимизации - от поиска элементов списка с минимальным или максимальным значением до поиска локальных и даже глобальных минимумов функций, заданных аналитически.
Цель исследования состояла в том, чтобы теоретически обосновать, составить и экспериментально проверить эффективность решения оптимизационных задач средствами MathCAD. В главе посвященной оптимизации средствами MathCAD мы раскрыли основные понятия, такие как "линейное программирование", "оптимизация", "оптимизационные задачи", рассмотрели основные возможности данной системы.
Вторая глава была направлена на рассмотрение этапов компьютерного математического моделирования, важной частью которой было изучение методов оптимизации, а также непосредственное решение оптимизационной задачи с помощью программы MathCAD.
В процессе решения оптимизационных задач стало очевидно, что неправильная постановка цели приводит к ошибочным результатам. Также необходимо соблюдать правильную последовательность выполнения этапов компьютерного моделирования при решении такого типа задач.
Тезаурус
1. Алгоритм - строгая система правил или инструкций для исполнителя, определяющая некоторую последовательность действий, которая после конечного числа шагов приводит к достижению искомого результата.
2. Библиотека стандартных подпрограмм - совокупность подпрограмм, составленных на одном из языков программирования и удовлетворяющих единым требованиям в структуре, организации их входов и выходов, описаниям подпрограмм.
3. Задача - 1) проблема, подлежащая решению;
4. 2) приложение, работающее в текущем сеансе и потребляющее ресурсы компьютера: оперативная память, процессорное время, доступ к внешним ресурсам.
5. Информационная технология - совокупность методов, производственных программно-технических средств, объединенных в технологическую цепочку, обеспечивающую сбор, хранение, обработку, вывод и распространение информационных ресурсов, повышения надежности и оперативности.
6. Линейное программирование - в имитационном моделировании понимается как поиск экстремумов линейной функции, на которую наложены ограничения
7. Моделирование - метод познания, состоящий в создании и исследовании моделей.
8. Оптимизация - процесс приведения системы в наилучшее (оптимальное) состояние.
9. Пакет прикладных программ - специальным образом организованные программные комплексы, рассчитанные на общее применение в определенной проблемной области и дополненные соответствующей технической документации.
10. Предметная (прикладная) область - совокупность связанных между собой функций, задач управления, с помощью которых достигается выполнение поставленных целей.
11. Прикладная программа - любая конкретная программа, способствующая решению какой-либо задачи в пределах данной проблемной области.
12. Приложение - 1) программная реализация на компьютере решения задачи;
13. 2) комплекс взаимосвязанных программ для создания и модификации объектов (документов), а также для управления объектами определенного типа.
14. Программа - упорядоченная последовательность команд (инструкций) компьютера для решения задачи.
15. Программирование - теоретическая и практическая деятельность, связанная с созданием программы.
16. Программный продукт - комплекс взаимосвязанных программ для решения определенной проблемы (задачи) массового спроса, подготовленный к реализации как любой вид промышленной продукции.
17. САПР (система автоматического проектирования) - комплексные программно-технические системы, предназначенные для выполнения проектных работ с применением математических методов. В качестве входной информации в САПР используются технические знания специалистов, которые вводят проектные требования, уточняют результаты, проверяют полученную конструкцию, изменяют ее и др.
18. Технология - при переводе с греческого означает искусство, мастерство, умение, а это не что иное, как процессы. Под процессом следует понимать определенную совокупность действий, направленных на достижение поставленной цели.
Список используемой литературы
1. Дорофеева, Г.В. Математика [Текст]: Сборник заданий для проведения письменного экзамена за курс средней школы/ Г.В. Дорофеева. - М.: Дрофа, 2002. - 160с.: ил.;
2. Сканави, М.И. Сборник задач по математике для поступающих в ВТУЗы [Текст] / М.И. Сканави. - М.: Высш. шк., 1993. - 528 с.: ил.;
3. Деминович, Б.П. Сборник задач и упражнений по математическому анализу [Текст] / Б.П. Демидович - М.: Изд-во Моск. ун-та, 1997. - 624 с.: ил.;
4. Дьяконов, В.П. Компьютерная математика [Текст]: Теория и практика / В.П. Дьяконов. - М.: Изд-во Нолидж, 2001. - 296 с.;
5. Дьяконов, В.П. MathCAD2000 [Текст]: Учебный курс / В.П. Дьяконов. - СПб: Питер, 2000. - 596 с.;
6. Семакин, И.Г. Информационные системы и модели. Элективный курс [Текст]: Учеб. пособие / И.Г. Семакин, Е.К. Хеннер. - М.: БИНОМ. Лаборатория знаний, 2005. - 303 с.: ил.
7. Калмыкова, Е.А. Информатика [Текст]: учеб. пособие для студ. проф. образования / Е.А. Калмыкова, И.А. Куликова. - М.: Академия, 2005 - 416с.
8. Информатика [Текст]: учебник / Н.В. Макарова [и др.]; под ред. Н.В. Макаровой. - 3-е изд., перераб. - М.: Финансы и статистика, 2004. - 768 с.: ил.
9. Угринович, Н.Д. Информатика и информационные технологии [Текст]: учебник для 10-11 классов / Н.Д. Угринович. - М.: БИНОМ. Лаборатория знаний, 2003. - 512 с.: ил.
10. Электронный курс по MathCAD [Электронный ресурс]: база данных содержит все необходимые сведения о системе MathCad 7.0. - Режим доступа: http://detc. usu.ru/Assets/aMATH0021/frame. htm;
11. Словари поисковой системы Яндекс [Электронный ресурс]. - Режим доступа: http://slovari. yandex.ru;
12. Компьютерное моделирование [Электронный ресурс]: база данных содержит основное понятие компьютерного моделирования, этапы и цели моделирования, классификацию моделей и др. - Режим доступа: http://pcmodel. narod.ru
13. Компьютерные технологии [Электронный ресурс]: база данных содержит информацию о системе MathCAD, раскрывает ее основные особенности значимость. - Режим доступа: http://www.irisoft.ru/info/mathcad
14. MathCAD 12. Полное руководство [Электронный ресурс]: база данных содержит учебник по MathCAD, уроки по MathCAD, справочные данные и справочники. - Режим доступа: http://www.radiomaster.ru/cad/mc12/index1. php
15. Самоучитель по MathCad [Электронный ресурс]: база данных содержит необходимую информацию по использованию системы MathCAD. - Режим доступа: http://www.Math-cad.ru/map. php
16. Основы системного использования ЭВМ. Работа с системой MathCAD [Электронный ресурс]: база данных содержит электронный конспект лекций по данному курсу. - Режим доступа: http://elib. ispu.ru/library/lessons/pekunov/index.html
Размещено на Allbest.ru
Подобные документы
Решение задачи средствами Паскаль и блок-схемы выполненных процедур, составление программы. Результаты решения задачи по перевозке грузов. выполнение задачи средствами MS Excel, создание таблиц. Порядок и особенности решения задачи в среде MathCAD.
курсовая работа [2,5 M], добавлен 27.02.2011Использование информационных технологий для решения транспортных задач. Составление программ и решение задачи средствами Pascal10; алгоритм решения. Работа со средствами пакета Microsoft Excel18 и MathCad. Таблица исходных данных, построение диаграммы.
курсовая работа [749,1 K], добавлен 13.08.2012Краткая характеристика пакета Mathcad, описание простейших примеров работы с ним, примеры решения основных задач элементарной математики. Компьютерные технологии решения математических задач и символьных вычислений. Образование векторов и матриц.
дипломная работа [621,1 K], добавлен 11.03.2011Структура программы Pascal и алгоритмы решения задач. Работа с циклическими операторами, массивами, процедурами. Составление блок-схем задач. Операции над матрицами в программе MathCad. Работа формулами, графиками и диаграммами в оболочке MS Excel.
курсовая работа [459,0 K], добавлен 13.08.2012Изучение структуры рабочего документа MathCad - программы, предназначенной для автоматизации математических расчетов. Работа с переменными, функциями и матрицами. Применение MathCad для построения графиков, решения уравнений и символьных вычислений.
презентация [639,2 K], добавлен 07.03.2013Основные элементы системы MathCAD, обзор ее возможностей. Интерфейс системы, концепция построения документа. Типы данных, входной язык системы. Классификация стандартных функций. Графические возможности системы MathCAD. Решение уравнений системы.
курс лекций [2,1 M], добавлен 01.03.2015Краткая историческая справка и описание современной версии системы. Основные возможности современной версии MathCad, ее интерфейс. Ввод и редактирование выражений, функции, решение уравнений. Использование Mathcad для решения инженерно-технических задач.
курсовая работа [2,8 M], добавлен 04.04.2014Возможности Mathcad для выполнения математических и технических расчетов. Графический интерфейс, инструменты для работы с формулами, числами, графиками и текстами. Операторы и логические функции для численного и символьного решения математических задач.
статья [208,6 K], добавлен 01.05.2010Понятие математической модели и моделирования. Общие сведения о системе MathCad. Структурный анализ задачи в MathCAD. Режим непрерывных символьных преобразований. Оптимизация численных вкладок через символьные преобразования. Расчет опорной реакции.
курсовая работа [649,5 K], добавлен 06.03.2014Расчеты по таблице перевозок грузов между отдельными регионами. Решение задачи управления процессами перевозок в среде Pascal. Решение задачи средствами MS Excel. Исходные данные и итоги по строкам и столбцам. Решение задачи средствами MATHCAD.
курсовая работа [1,8 M], добавлен 25.03.2015
