Моделирование задач линейного программирования в MathCad

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

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «МОРДОВСКИЙ ГОСУДАРСТВЕННЫЙ ПЕДАГОГИЧЕСКИЙ ИНСТИТУТ ИМ.М.Е.ЕВСЕВЬЕВА»

Факультет физико-математический

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

Реферат

Моделирование решения задач линейного программирования в MathCad

Выполнила: студентка группы МДИ-117

Федюшкина В. А.

Проверила: Кормилицына Т. В.

Саранск 2020

Содержание

Введение 3

1 Задачи линейного программирования в MathCad 4

1.1 Общая постановка задачи линейного программирования 4

1.2 Алгоритм решения задач линейного программирования в MathCad 5

2 Примеры решения задач линейного программирования в MathCad 7

2.1 Решение задачи линейного программирования 7

2.2 Решение транспортной задачи 8

2.3 Решение задачи о назначениях 10

Список использованной литературы 12

Введение

Линейное программирование – наука о методах исследования и нахождения наибольшего или наименьшего значений линейной (целевой) функции при наличии линейных ограничений. Термин "программирование" понимается в смысле "планирования". Он был предложен в середине 1940-х годов Джорджем Данцигом, одним из основателей линейного программирования, еще до того, как компьютеры были использованы для решения линейных задач оптимизации.

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

Опыт преподавания показывает необходимость использования в рамках дисциплины исследования операций табличного процессора MS Excel и систем компьютерной математики, в частности системы MathCad, главными достоинствами которой является то, что она проста в изучении и использовании, позволяет одновременно с расчетами создавать документы в общепринятом виде.

1. Задачи линейного программирования в MathCad

1. Общая постановка задачи линейного программирования

Линейное программирование это один из первых и более углубленно изученных разделов математического программирования. Не что иное, как линейное программирование стало тем разделом, с помощью которого и начала развиваться дисциплина «математическое программирование».

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

К задачам линейного программирования можно отнести такие задачи, в которых целевая функция и ограничения в виде равенств и неравенств являются линейными. Для примера задачу линейного программирования можно задать следующим образом: необходимо найти вектор значений переменных, которые доставляют экстремум линейной целевой функции при m ограничениях в виде линейных равенств или неравенств.

Как было сказано ранее линейное программирование является часто используемым методом оптимизации. К задачам линейного программирования относят задачи:

а) рационального расхода материалов и сырья;

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

в) наилучшего размещения и концентрации производства;

г) создание наиболее прибыльного плана перевозок, работы транспорта;

д) управление производственными запасами;

е) и множество других задач, которые принадлежат к этой сфере.

Если судить по оценкам американских экспертов, то около 75% от всего числа используемых методов оптимизации приходится на линейное программирование. Больше половины машинного времени, которое было потрачено за последние годы на проведение некоторых научных испытаний, отвели решению задач линейного программирования.

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

1.2 Алгоритм решения задач линейного программирования в MathCad

Система MathCad позволяет упростить решения задач линейного программирования, используя при этом основные функции Maximize и Minimize.

Рассмотрим порядок выполнения решения задачи линейного программирования в системе MathCad с системой ограничений двух или трех переменных.

1. Установить режим автоматических вычислений.

2. Определить целевую функцию как функцию трех переменных.

3. Задать начальные приближения для всех переменных.

4. Ввести ключевое слово Given.

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

6. Задать вектор-столбец, элементы которого переменные х₁, х₂, х₃. Ввести знак присваивания и функцию Maximize (f, x₁,x₂,x₃) для решения задачи линейного программирования на максимум, или Minimize (f, x₁,x₂,x₃) для решения задачи линейного программирования на минимум.

7. Еще раз ввести вектор-столбец с переменными x₁, x₂, x₃, нажать знак равенства и будет получено оптимальное решение.

8. Вычислить значение целевой функции в точке экстремума.

9. Оформить документ и сохранить его в файле.

2 Примеры решения задач линейного программирования в MathCad

2.1 Решение задачи линейного программирования

Задача 1. Найти максимальное значение функции

при заданных ограничениях:

Решение:

1) Специальной переменной ORIGIN присваиваем значение 1. Значением ORIGIN является номер первого элемента строки или столбца в матрице. По умолчанию ORIGIN=0.

В меню Math выбрать строку Options или

2) Вводим исходные данные задачи в матричной форме.

3) Вводим линейную целевую функцию.

4) Задаем начальные значения переменным задачи.

5) Вводим ограничения задачи в матричной форме.

6) Определяют оптимальное решение задачи с помощью встроенной функции Maximize (в случае поиска максимума функции) или Minimize (в случае поиска минимума функции).

2.2 Решение транспортной задачи

Задача 2. Имеются n пунктов производства и т пунктов распределения продукции. Стоимость перевозки единицы продукции с і-го пункта производства в j-й центр распределения приведена в таблице, где под строкой понимается пункт производства, а под столбцом - пункт распределения. Кроме того, в этой таблице в i-й строке указан объем производства в і-м пункте производства, а в j-м столбце указан спрос в j-м центре распределения. Необходимо составить план перевозок по доставке требуемой продукции в пункты распределения, минимизирующий суммарные транспортные расходы.

Стоимость перевозки единицы продукции				Объем производства
1	3	4	5	20
5	2	10	3	30
3	2	1	4	50
6	4	2	6	20
42	40	80	38

Объем потребления

Решение:

1. Ввели исходные данные в матричной форме.

1. Ввели линейную целевую функцию.

1. Задали начальные значения переменных:

1. Ввели ограничения задачи в матричной форме.

1. Определили оптимальное решение задачи с помощью встроенной функции Minimize:

2.3 Решение задачи о назначениях

Задача 3. Имеются n рабочих и т видов работ. Стоимость выполнения і-и работником j-й работы приведена в таблице, где рабочему соответствует строка, а работе – столбец. Необходимо составить план работ так, чтобы все работы были выполнены, каждый рабочий был занят только на одной работе, а суммарная стоимость выполнения всех работ была минимальной.

Стоимость выполнения работ

	Виды работ
Рабочие	14	21	14	22
	12	12	23	31
	13	17	45	33
	14	15	75	34

Решение задачи средствами MathCad:

1. Ввели исходные данные в матричной форме.

1. Ввели линейную целевую функцию.

1. Задали начальные значения переменных:

1. Ввели ограничения задачи в матричной форме.

1. Определили оптимальное решение задачи с помощью встроенной функции Minimize:

Заключение

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

Математическую систему MathCad достаточно удобно использовать для обучения, вычислений и инженерных расчетов. Она славится универсальностью своего пакета, который может быть использован для решения самых разнообразных инженерных, экономических, статистических и других научных задач. Программирование на общепринятом математическом языке позволяет преодолеть языковой барьер между машиной и пользователем, что делает его востребованным среди студентов и академиков. А совместное применение текстового редактора, формульного транслятора и графического процессора позволяет пользователю в ходе вычислений получить готовый документ.

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

Список использованной литературы

1. Аверьянова С.Ю., Растеряев Н.В. Содержательные задачи линейного программирования и их решение с помощью ЭТ MS EXCEL и пакета MATHCAD: учебное пособие/ Южный федеральный университет. – Ростов-на-Дону: Издательство ЮФУ, 2014. – 132 с.

2. Гольштейн Е. Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. - М.: Наука, 1969. – 382 с.

3. Капустин Е.И. Решение некоторых классов математических задач в программе Excel. URL://exponenta.ru/educat/systemat/kapustin/003.asp/.

4. Карманов В.Г. Математическое программирование: Учеб. Пособие. М.: Физматлит, 2001. 263 с.

5. Кудрявцев Е.М. MathCad-2000. М.: ДМК Пресс, 2001. С. 576.

6. Кузнецова Л.Г. Системы компьютерной математики / Учебное пособие. Омск, 2003. С. 108.

7. Растеряев, Н.В., Герасименко Ю.Я. Решение оптимизационных задач в среде MATHCAD и EXCEL: Учеб. пособие – Новочеркасск: Южно-российский гос. тех. ун-т (НПИ), 2004.- 100 с.