Замечание: Задача решается на основе изначально полученной формулировки задачи, до ее преобразования в основную форму

СБОРНИК

ПРАКТИЧЕСКИХ ЗАНЯТИЙ

по дисциплине

«Анализ и моделирование систем математическими методами»

для специальности 080802 (2205)

«Прикладная информатика»

(по отраслям)

Ульяновск

Мардамшина А.А.

Сборник практических занятий по дисциплине «Анализ и моделирование систем математическими методами». Методические указания для студентов. Ульяновск, 2011; УАвиаК, - стр.

Сборник практических занятий разработан для закрепления теоретических знаний по дисциплине «Анализ и моделирование программ математическими методами». Темы занятий соответствуют рабочей программе.

Сборник предназначен для специальности 080802 (2205) «Прикладная информатика» (по отраслям).

Одобрен на заседании комиссии «Программирование и ИТ».

(Протокол № )

Печатается по решению редакционно-издательского совета

Ульяновского авиационного колледжа

Рецензенты:

Камышова Г.А.	Преподаватель высшей категории Ульяновского авиационного колледжа
Кондратьев А.Е.	кандидат физико-математических наук, доцент кафедры Информационных Технологий факультета Математики и Информационных Технологий Ульяновского Государственного Университета

Отзывы и предложения направлять по адресу:

432067, г. Ульяновск, проспект Созидателей, 13

телефон (8-422) 20-15-72,20-15-85

факс: 54-54-63

E-mail: [email protected]

СОДЕРЖАНИЕ

ВВЕДЕНИЕ................................................................................................. 4

ПРАКТИЧЕСКИЕ ЗАНЯТИЯ

№ 1 Симплексный метод.................................................................... 5

№ 2 Двойственный симплекс-метод.................................................. 8

№ 3 Транспортная задача................................................................. 11

№ 4 Метод множителей Лагранжа.................................................... 14

№ 5 Градиентные методы.................................................................. 17

№ 6-7 Теория игр............................................................................... 19

№ 8 Динамическое программирование............................................ 26

ИСПОЛЬЗОВАННАЯ ЛИТЕРАТУРА.................................................... 28

ВВЕДЕНИЕ

Практические занятия проводятся с целью приобретения практических навыков программирования математических задач, используя модели и методы, изученные на лекционных занятиях.

ПРАКТИЧЕСКОЕ ЗАНЯТИЕ №1

СИМПЛЕКСНЫЙ МЕТОД

(2 часа)

1. ЦЕЛЬ РАБОТЫ:

1.1.Формирование навыков построения моделей задач ЛП;

1.2.Формирование навыков решения задач ЛП симплексным методом без применения инструментальных сред;

1.3.Формирование навыков решения задач ЛП симплексным методом в Excel с использованием надстройки Поиск решения;

1.4.Формирование навыков решения задач ЛП симплексным методом в MathCAD с использованием функций Minimize и Maximize.

2. СОДЕРЖАНИЕ РАБОТЫ:

2.1.Ознакомьтесь с теоретическим материалом;

2.2.Выполните задания из пункта 4;

2.3.Ответьте на контрольные вопросы.

3. ПЕРЕЧЕНЬ ОБОРУДОВАНИЯ И ПО:

3.1.ПК;

3.2.MS Office 2007;

3.3.MS Excel 2007с надстройкой Поиск решения;

3.4.MathCAD

4. ВЫПОЛНЕНИЕ:

4.1.Постройте математическую модель задачи линейного программирования. Установите форму полученной записи ЗЛП. Преобразуйте ее к форме основной ЗЛП.

4.2.Решите ЗЛП симплексным методом без использования инструментальных средств.

4.3.Решите ЗЛП симплексным методом в MS Excel, используя надстройку «Поиск решения».

4.4.Решите ЗЛП симплексным методом в MathCAD.

5. МЕТОДИЧЕСКИЕ УКАЗАНИЯ:

Общей задачей линейного программирования называется задача, которая состоит в определение максимального (или минимального) значения функции (1) при условиях

(2)

, (3)

, (4)

где - заданные постоянные величины.

Основной или канонической задачей линейного программированияназывается задача, которая состоит в определении максимального значения функции (1) при ограничениях вида (3) и (4).

Решение задачи ЛП симплексным методом включает следующие этапы:

1. Находят опорный план

2. Составляют симплекс таблицу

3. Выясняют, является ли хотя бы одно число дельта, отрицательным

4. Находят направляющие столбец и строку

5. Определяю по формулам компоненты нового опорного плана

6. Проверяют новый план на оптимальность

Еслив пакете MS Excel недоступна утилита Поиск решения, то установить ее можно выполнив последовательно: Office > Параметры Excel > Надстройки > Поиск решения > Ок.

Задание 1.

По условию задачи вашего варианта:

1. Составьте и запишите математическую модель задачи.

2. Установите форму записи полученного условия.

3. Если требуется, то внесите изменения в формулировку так, чтобы форма записи соответствовала основной ЗЛП.

Задание 2.

1. Запишите условие задачи в векторной форме. Выделите базисные векторы.

2. Составьте и заполните исходную симплекс—таблицу.

3. Вычислите числа дельта и определите по их значениям—является ли найденный опорный план оптимальным.

4. В случае не оптимального опорного плана определите ведущие столбец и стоку, ведущий элемент. Составите новую систему базисных векторов. Вычислите коэффициенты векторов в новом базисе. Занесите все вычисления в таблицу.

5. В случае оптимального опорного плана запишите его и определите значения целевой функции при найденном опорном плане.

Задание 3.

Решите задачу ЛП симплексным методом в MS Excel используя надстройку Поиск решения.

Замечание: Задача решается на основе изначально полученной формулировки задачи, до ее преобразования в основную форму.

1. В ячейки B1, С1 и т.д. внесите поясняющий назначение выбранных вами переменных текст: «Кол-во изготовленных изделий вида А » и т.п.

2. В ячейки В2, С2 и т.д. внесите имена выбранных вами переменных: х1, х2 и т.д.

3. В ячейки B3, С3 и т.д. внесите 0 — это - начальные значения переменных хi.

4. В ячейки A5, A6, A7 и т.д. внесите названия запасов / ресурсов

5. В ячейки В4, С4 и т.д. названия изделий.

6. В ячейки В5, С5, …, В6, С6, …, В7, С7, … внесите заданные в условии задачи коэффициенты - ограничения

7. В ячейку F5 внесите формулу =В5*В3+С5*С3+D5*D3+… , цель создания формулы—записать первое ограничение задачи. На ячейки В3, С3, D3 в этой формуле поставьте абсолютные ссылки (F4). Введите форуму и размножьте ее по столбцу F, до последнего ограничения задачи.

8. В ячейку G4 внесите текст «Запасы» или т.п.

9. В ячейки G5, G6 и т.д. внесите свободные коэффициенты системы ограничений.

10. В ячейку А8 внесите текст «Цена изделия». А в ячейки В8, С8 и т.д. коэффициенты целевой функции задачи.

11. В ячейке F8 составьте формулу соответствующую целевой функции задачи: = В8*В3+С8*С3+ …

12. Закончив вводить формулу в F8 снова выделите эту ячейку.

13. Найдите на вкладке главного меню «Данные» утилиту «Поиск решения» и вызовите ее.

14. Проверьте, что в окно «Установить целевую ячейку» внесена F8.

15. Проверьте, что из флагов раздела «Равной», выбран «максимальному значению». (Если он требуется в вашей задаче.)

16. Уставите курсов в окно «Изменяя ячейки». Нажмите на кнопку перехода в окно Excel и выделите в нем блок В3, С3 и т.д. содержащий начальные значения ваших переменных. Вернитесь к окну «Поиск решения».

17. Установите курсор в окне «Ограничения». Нажмите кнопку Добавить. Находясь в окне «Ссылка на ячейку» выполните щелчок по ячейке F5 в которой находится левая часть созданного вами первого ограничения задачи.

18. Переведите курсор в раздел «Ограничение» и выполните щелчок по ячейке G5, в которой находится правая часть первого ограничения задачи. Нажмите кнопку Добавить.

19. Повторите действия для каждого ограничения.

20. Установите курсов в окно «Ссылка на ячейку» и нажмите на кнопку перехода в окно Excel. Выделите блок начальных значений переменных В3, С3 и т.д. Вернитесь в окно «Добавление ограничений». В списке знаков ограничений выберите >= и в раздел «Ограничение» впишите 0. Нажмите кнопку Ок.

21. Вернувшись в окно «Поиск решения» еще раз проверьте все выполненные вами установки и нажмите кнопку Выполнить.

22. Если решение найдено, то согласитесь с его сохранением и получите отчет по результатам.

23. Сравните полученные результаты с вычисленными вами в ручную.

Задание 4.

Решите задачу ЛП симплексным методом в MathCAD.

1. Откройте в среде MathCAD новый документ и внесите в него математическую модель решаемой вами задачи. Для набора текста на русском языке выберите шрифт Courier New. Для создания текстового блока нажмите «.

2. Для ввода условия задачи используем ее матричное представление. Для создания матриц раскрывается панель «Матрицы», выбирается шаблон и в окне настроек задается число строк и столбцов создаваемой матрицы. Так для целевой функции записываем с:= (для этого знака нажимаем литеру :) и вызываем шаблон матрицы из одного столбца и количества строк равного количеству неизвестных в задаче. Шаблон заполняем данными по условию задачи. Для задания начального значения неизвестных записываем х:= и вызываем шаблон матрицы. Шаблон заполняем нулями. Далее записываем f(x):=c*x.

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

4. Далее (обязательно ниже) записывается служебное слово Given за которым записывается система ограничений, а именно а*x<=b и x>=0

5. Далее вводится новая переменная y. А именно y:=Maximize(f,x) Для поиска минимального значения задается y:=Minimize(f,x)

6. Для получения результата записываем y= и выполняем щелчок ЛКМ в произвольном месте страницы.

7. Для нахождения максимального значения целевой функции записываем f(y)= и и выполняем щелчок ЛКМ в произвольном месте страницы.

6. ОТЧЕТ ДОЛЖЕН СОДЕРЖАТЬ:

6.1.Номер практической работы, ее название, номер выполняемого варианта.

6.2.Номер задания.

6.3.Условие решаемой задачи.

6.4.Математическая модель задачи.

6.5.Решение ЗЛП симплексным методом в ручную.

6.6.Распечатка результата решения ЗЛП в Excel включающая фрагмент эл.листа с условием задачи и отчет по результатам.

6.7.Распечатка результата решения в MathCAD.