close

Вход

Забыли?

вход по аккаунту

?

организация практического обучения в профобразовании

код для вставкиСкачать
Государственное бюджетное образовательное учреждение Астраханской области
среднего профессионального образования «Астраханский колледж вычислительной
техники»,
г. Астрахань
Интернет – конференция по учебной работе
Организация практического обучения в профессиональном образовании
Тема работы: Методические рекомендации по выполнению лабораторной работы
«Решение оптимизационных задач с использованием математического пакета MathCad и
ЭП Excel» по дисциплине «Математические методы»
Автор: Демина Юлия Сергеевна, преподаватель специальных дисциплин
Программа учебной дисциплины «Математические методы» предусматривает
изучение математических методов решения задач линейного программирования,
построение сетевых моделей, систем массового обслуживания, методов прогнозирования
и имитации процессов. При выполнении данной лабораторной работы студент должен:
знать:

этапы построения математических моделей;

способы решения оптимизационных задач с использованием математического
пакета MathCad и средств MS Excel.
уметь:

использовать математические знания для построения моделей и решения задач
линейного программирования.
Лабораторная работа
1 Решение оптимизационных задач с использованием математического пакета
MathCad и ЭП Excel
1.1 Цель работы:
-
научиться составлять математическую модель оптимизационных задач;
-
находить оптимальное решение графическим методом;
-
находить оптимальное решение симплекс- методом;
-
использовать математический пакет MathCad и ЭП Excel для решения
оптимизационных задач.
1.2 Приборы и оборудования
-
ПЭВМ IBM PC;
-
Математический пакет MathCad;
-
ЭП Excel.
1.3 Порядок выполнения работы:
1.3.1 Задание 1. Предприятию необходимо изготавливать два вида продукции Р1,
Р2 с использованием трех видов ресурсов: R1,R2,R3, количество которых ограничено.
Исходные данные задачи сведены в следующую таблицу:
Количество ресурсов, идущее на
Вид ресурсов
Запас ресурсов
изготовление единицы продукции
Р1
Р2
R1
36
6
6
R2
30
4
2
R3
20
4
8
8
6
Доход от реализации единицы продукции
Требуется составить такой план выпуска продукции, чтобы при ее реализации
получить максимальный доход.
Для решения задачи необходимо:
1.
Составить математическую модель задачи;
2.
Найти оптимальное решение графическим методом;
3.
Проверить решение, используя математический пакет MathCad;
4.
Найти оптимальное решение симплекс- методом;
5.
Проверить решение, используя ЭП Excel.
1.3.2 Задание 2. В кафетерии продается кофе трех видов: обычный кофе; особый
кофе со сливками; особый кофе с шоколадом. Цены на них равны соответственно 3,75;
6,0; 7,25 рублей. Складские помещения и условия продажи позволяют производить не
более 500 чашек кофе (как обычного, так и особого). Существуют ограничения на
подставку сливок и шоколада, которые позволяют производить в неделю 125 чашек кофе с
шоколадом и 350 со сливками.
Требуется составить такой план реализации продукции, чтобы прибыль была
максимальной.
Составить математическую модель задачи и решить её с использованием
электронного процессора Excel .
1.4 Контрольные вопросы
1.4.1 Назовите основные этапы процесса построения математических моделей.
1.4.2 Назовите три составляющие задач оптимизации. Охарактеризуйте их.
1.4.3 Какую область образуют задачи линейного программирования, и что она
собой представляет?
1.4.4 Что такое угловая точка?
1.4.5 Где целевая функция достигает своего экстремального значения?
1.4.6 Дайте определение: допустимые решения; оптимальные решения.
1.4.7 Опишите графический метод решения задач линейного программирования.
1.4.8 Какая форма задачи линейного программирования считается канонической?
1.4.9 Какая переменная является базисной?
1.4.10 В каких случаях применяется метод искусственного базиса? В чем суть
этого метода?
1.5. Теоретические сведения
Графический метод решения задач линейного программирования
Решим графическим методом задачу линейного программирования с двумя
переменными:
f  x1  3x2  min
Построим область ее допустимых решений, для этого
отобразим
10x1  3x2  30
 x1  x2  3


x1  x2  4
x1  x2  10
x1  0, x2  0
в
прямоугольной
системе
координат
условия
неотрицательности -переменных. Построим прямые х1=0, х2=0,
которые лежат на границах полуплоскостей и совпадают с осями
координат. Множество точек, удовлетворяющих неравенствам
х1>=0 и х2>=0 совпадает с точками первой четверти.
Рассмотрим ограничения задачи. Построим по порядку
прямые:
Определим, с какой стороны от
10x1+3x2=30
этих прямых лежат полуплоскости,
-x1+x2=3
точки
x1-x2=4
соответственно строгим неравенствам.
которых
Убедиться
x1+x2=10
стороны
удовлетворяют
в
том,
с
какой
от
прямой
лежит
полуплоскость,
можно
путем
подстановки координат точек одной
или
другой
полуплоскости
неравенство,
удобнее
в
всего
подставлять точку с координатами (0,
0).
Если
координаты
точки
удовлетворяют неравенству, то эта
точка
лежит
соответствующей
неравенству.
в
полуплоскости,
данному
Область определения задачи будет представлять собой пересечение всех
построенных полуплоскостей - многоугольник АВСDЕ.
Следующим этапом присвоим целевой функции f значение нуль и построим
прямую
х1-3x2=0
Эта прямая, проходящая через начало координат, строится следующим образом В
левой части уравнения стоит скалярное произведение двух векторов С=(с1, с2) = (1, -3) и
Х=(х1,х2). Если скалярное произведение векторов равно нулю, то векторы
перпендикулярны.
Построим вектор С , он проходит через начало координат и точку (1, -3) и
перпендикулярно ему через начало координат проведем прямую.
Вектор С всегда показывает направление возрастания значения целевой функции, а
противоположный ему вектор (-С) направление убывания значения целевой функции.
Передвигая прямую х1-3x2=0 по области определения параллельно самой себе в
направлении вектора С, значения целевой функции будут возрастать. Передвижение в
направлении вектора (-С) дает убывание значения целевой функции.
Целевая функция в задаче достигает своего минимального значения в точке В
многоугольника, а максимального - в точке D.
Оптимальному решению задачи соответствует точка В, которая лежит на
пересечении прямых
-х1+х2=3
х1+х2=10
Для определения координат точки В решим систему. В результате получим: х1=3,5,
х2=6,5; f=-16.
Графическое решение задач линейного программирования с использованием
пакета MathCad.
1. Чтобы найти область допустимых значений ограничений, уравнения прямых
записываются в виде y=kx+b. Чтобы выразить переменную y через x, необходимо в
уравнение прямой выделить y в рамку и последовательно ввести команды SymbolicsVariable- Solve.
2. Графики прямых строятся с использованием команд Insert- Graph-X-Y-Plot.
Чтобы на одном графике построить несколько прямых, необходимо после ввода значения
по оси ординат нажать символ запятая.
3. Для построения осей в контекстном меню Format поля графика устанавливается
флажок Crossed.
4. Строятся для одного или нескольких значений С линии уровня целевой функции
f(x,y)=C.
5. Определяется и вычисляется точка экстремума целевой функции.
Алгоритм симплекс-метода
Как уже известно, прежде чем решать задачу линейного программирования
симплекс-методом, ее необходимо привести к канонической форме . После этого
выделяют переменные, которые присутствуют только в одном уравнении с
коэффициентом единица и принимают их в качестве базисных. Если в ограничении такую
переменную выделить нельзя, то вводят искусственную базисную переменную. Затем
определяется исходное базисное решение и значение целевой функции для этого решения.
Далее выполняется следующая последовательность шагов:
Шаг 1. Строим и заполняем исходную симплексную таблицу по следующей схеме:
В столбце «Базис» записываются базисные переменные, в столбце «С» —
коэффициенты при базисных переменных в целевой функции (сi), в столбце «В» —
свободные члены ограничений (bi), т. е. значения базисных переменных. В столбцах хj
(небазисные переменные) отражаются коэффициенты при небазисных переменных в
ограничениях (аij), над переменными xj — коэффициенты при этих переменных в целевой
функции (сj). Строка «  » в столбце «В» содержит значение целевой функции, которое
рассчитывается по формуле:
f  ci bi
iI б
1.
а столбцы хj этой же строки — значения относительных оценок (  j ),
рассчитываемых по формуле.
 j  ci aij  c j , j I б
iI б
2.
Числа (—1) и 0, записываемые соответственно над столбцами «С» и «В»,
неизменно присутствуют в каждой симплексной таблице и носят вспомогательный
характер, чтобы при расчете оценок  j по таблице не забывать о вычитании сj.
При определении значения f фактически нужно найти сумму произведений
элементов столбца «С» на соответствующие элементы столбца «В», что равносильно
подстановке базисного плана в целевую функцию, а при определении значения
относительной оценки  j — сумму произведений элементов столбца «С», включая (—1),
на соответствующие элементы того столбца xj для которого она рассчитывается.
Шаг 2. Проверим полученный базисный решение на оптимальность по условию
оптимальности.
Если j  I б ,  j  0 и среди базисных переменных нет искусственных, то решение
является оптимальным.
Если j  I б ,  j  0 и среди базисных переменных есть искусственные, то задача
неразрешима, так как ее система ограничений несовместна.
Если  j  0 , то полученный базисный решение не является оптимальным и
необходимо переходить к другому базисному решению.
Если в оптимальном решение  j  0 , то это говорит о том, что задача имеет
бесконечное число решений.
Шаг 3. Для перехода к новому базисному решению в первую очередь из числа
небазисных переменных с отрицательными оценками  j выбирается переменная, которая
вводится в базис. Введем в новый базис переменную хk, которой соответствует
наибольшая по абсолютной величине отрицательная оценка  j :
 k  max  j
j
3.
Столбец, отвечающий переменной xk, назовем главным. Элементы главного
столбца обозначаются через аik. Выбранная переменная будет вводиться в базис.
Если окажется несколько одинаковых наибольших по абсолютной величине
отрицательных оценок, то выбирается любая из соответствующих им переменных.
Шаг 4. Выбираем переменную, которая выводится из базиса. Ее индекс r находится
из соотношения:
b
br
 min i
i a
ark
ik
4.
по всем i, для которых аik>0.
Строку таблицы, в которой получено наименьшее отношение
br
элемента столбца
ark
«В» к соответствующему положительному элементу главного столбца, назовем главной.
Элементы главной строки обозначаются через arj. Выбранная переменная xr будет
выводиться из базиса.
Если окажется несколько одинаковых наименьших значений отношений, то
выбирается любая из соответствующих им переменных. Это может произойти в
вырожденной задаче.
Элемент, стоящий на пересечении главной строки и главного столбца, назовем
главным (обозначается через аrk).
В случае отсутствия значений аik>0 задача неразрешима, так как ее целевая
функция не ограничена на множестве решений задачи.
Шаг 5. Для определения нового базисного решения производим пересчет
элементов таблицы и результаты заносим в новую симплексную таблицу. Выбранные
переменные в новой таблице меняются местами вместе со своими коэффициентами в
целевой функции. Остальные переменные переписываются без изменений со своими
коэффициентами. Элементы новой симплексной таблицы рассчитываются по
приведенным ниже формулам.
Элементы главной строки bk 
главный элемент akr 
arj
br
; akj 
ark
ark
1
ark
элементы главного столбца air  
aik

; r   k
ark
ark
все остальные элементы таблицы:
bi   bi 
br aik
ark
aij   aij 
arj aik
ark
 j   j 
 k arj
ark
f  f 
br  k
ark
Шаг 6. Проверяем правильность расчета значений целевой функции f и оценок по
формулам 1и 2.Переходим к шагу 2.
Решение задач оптимизации с использование ЭП Excel
Рассматриваются задачи нахождения точек, в которых достигаются максимальные
и минимальные значения функций нескольких переменных
Задачи решаются с помощью инструмента Excel Поиск решения. Для запуска
выполняется команда Сервис- Настройка. В результате выполнения команды Поиск
решения появляется окно диалога Поиск решения .
В поле ввода Установить целевую ячейку указывается ссылка на ячейку с целевой
функцией, значение которой будет максимальным, минимальным или нулем в
зависимости от выбранного вами переключателя.
В поле ввода Изменяя ячейки указываются ячейки, которые отведены под
переменные целевой функции.
Кнопка Параметры вызывает окно диалога Параметры поиска решения, в котором
можно изменять параметры алгоритма поиска решения.
Порядок выполнения:
- вводятся формулы для целевой функции и ограничений;
- вводятся начальные значения переменных (нулевыми);
- выполните команду Сервис - Поиск решения. Появится окно диалога "Поиск
решения ;
- в поле ввода Установить целевую ячейку введите ссылку на целевую функцию;
- в поле ввода Изменяя ячейки укажите ссылки на ячейки со значениями
переменных;
- начинаем вводить информацию в поле ввода Ограничения. Нажмите кнопку
Добавить. Появится окно диалога "Добавить ограничения". В поле ввода Ссылка на
ячейку введите ссылку на ячейку с первым ограничением. В поле ввода Ограничение
введите <= и число;
- воспользуйтесь кнопкой Добавить для ввода остальных ограничений. Для
изменения ограничения установите на него курсор и нажмите кнопку Изменить.
- нажмите кнопку Выполнить. После окончания расчета Excel откроет окно
Результаты поиска решения;
- выберите в окне Тип отчета и .нажмите кнопку ОК. Перед тем листом, где
записана постановка задачи, будет вставлен лист "Отчет по результатам 1", а на экране вы
увидите ответ на поставленную задачу.
- Нажмите мышью ярлык "Отчет по результатам 1". На экране появится отчет
Excel о решенной задаче.
Список литературы:
Основная литература:
1. В.П.Агальцов, И.В. Волдайская, Математические методы в программировании,
Москва, ИД «Форум»- ИНФРА-М, 2006
2. Е.М.Кудрявцев, MathCad 8, Символьное и численное решение разнообразных
задач, Москва, ДМК, 2000.
3. Г.С. Малик, Основы экономики и ММ в планирование, Москва, Высшая школа,
1988
4. Ю. Стоцкий, Office 2000,. Санкт-Петербург, Питер, 2002
Дополнительная литература:
1. А.И. Карасев, Н.Ш. Кремер, Г.И. Савельев, Математические методы и модели в
планировании, Москва, экономика, 1987
2. Л.М. Климова, Основы программирования. Решение типовых задач Delphi 7,
Москва, 2005
3. Т.Л. Партыка, И.И. Попов, Математические методы, Москва, ИД «Форум» ИНФРА-М, 2007
4. М. Хэлворсон, М. Янг, Office 2007, Санкт-Петербург, Питер, 2000
Автор
profobrazovanie
Документ
Категория
Математика
Просмотров
90
Размер файла
371 Кб
Теги
обучения, организации, профобразование, практическое
1/--страниц
Пожаловаться на содержимое документа