Использование пакетов прикладных программ для решения задач линейного программирования

ГОУ ВПО

Уфимский государственный авиационный технический университет

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

КУРСОВАЯ РАБОТА

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

«Математические методы и модели ИО»

на тему

«Использование пакетов прикладных программ для решения задач линейного программирования»

Выполнили:

студент гр. МИЭ-310з

Валеева А.М.

Проверил:

Доцент каф.ВМиК

Тарасова Т.Д.

Уфа 2011 г.

Содержание

Введение ……………………………….………………….……2

1. Постановка задачи ………………………………….………………….4

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

3. Решение задачи

3.1. Пакет Solver…………………….…………………………..………6

3.2. ПЭР ………………………………………………….…………….14

3.3. MathCAD…………………………………………………………..17

4. Результат решения …………….……………………………………….19

Заключение ……………………………………………………………………....20

Список используемой литературы………………………...……………………22

Введение.

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

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

Пакет прикладных программ (ППП) представляет собой набор программ, позволяющих решать определенный класс задач и ориентированный на определенный тип машин.

Решение задач линейного программирования с помощью пакета Solver

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

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

Решение задач линейного программирования с помощью Пакета Экономических Расчетов (ПЭР)

Пакет экономических расчетов является адаптацией пакета «Системы количественного анализа в управлении» версии 5.0.

ППП ПЭР предназначен для решения ряда экономико – математических задач на персональных компьютерах типа PENTIUM. В пакете реализованы наиболее часто используемые экономико – математические задачи и методы, в частности: линейное программирование.

Максимальные размеры решаемых задач: 40 основных переменных и 40 ограничений. Программа линейного программирования использует симплексный – метод решения задач.

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

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

Первая версия пакета MATHCAD появилась в 1986г. Пакет постоянно совершенствуется. В настоящее время существуют версии MATHCAD, работающие под Windows.

1. Постановка задачи.

При производстве 4 видов кабеля выполняется 5 групп технологических операций. Нормы затрат на 1 километр кабеля данного вида на каждой из групп операций, прибыль от реализации 1 километра каждого вида кабеля, а также общий фонд рабочего времени, в течение каждого могут выполняться эти операции, указаны в таблице 1.

Таблица 1

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

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

Составим математическую модель задачи. Искомое норма затрат времени на обработку кабеля 1 вида обозначим через Х1, норма затрат кабеля 2 вида - через Х2, норма затрат 3 вида – через Х3, норма затрат 4 вида – через Х4. Математическая постановка состоит в определении максимального значения функции

F = 1,2∙x₁ + 0,8∙x₂ +1∙ x₃ +1,3∙x₄ → max (1.1)

при выполнении условий:

1,2∙х₁ + 1,8∙х₂ + 1,6∙х₃ + 2,4∙х₄ ≤ 7200 (1.2)

1∙х₁ + 0,4∙х₂ + 0,8∙х₃ + 0,7∙х₄ ≤ 5600

6,4∙х₁ + 5,6∙х₂ + 6∙х₃ + 8∙х₄ ≤11176

3∙х₁ + + 1,8∙х₃ + 2,4∙х₄ ≤ 3600

2,1∙х₁ + 1,5∙х₂ + 0,8∙х₃ + 3∙х₄ ≤ 4200

хj ≥ 0 (j =1,4). (1.3)

3.1. Решение задачи с помощью пакета Solver

1. Создаем форму для ввода условий задачи. Запускаем Excel. Открывается чистый лист Excel. Создаем текстовую форму - таблицу для ввода условий задачи.

2. Указываем адреса ячеек, в которые будет помещен результат решения (изменяемые ячейки). Обозначим через X1, X2, X3, X4 норму затрат на кабель каждого вида. В нашей задаче оптимальные значения компонент вектора X = (X1, X2, X3, X4) будут помещены в ячейках В3:Е3, оптимальное значение целевой функции — в ячейке F4.

3. Вводим исходные данные задачи в созданную форму—таблицу.

4. Вводим зависимость для целевой функции:

- курсор в ячейку F4.

-курсор на кнопку «Мастер функций», расположенную на панели инструментов.

На экране появляется диалоговое окно Мастер функций шаг 1 из 2

- курсор в окно «Категория» на категорию Математические;

- курсор в окно Функции на СУММПРОИЗВ;

На экране появляется диалоговое окно СУММПРОИЗВ;

в строку «Массив 1» вводим В$3:Е$3;

в строку «Массив 2» вводим В4:Е4; кнопка «ОК».

На экране: в ячейку F4 введена функция.

5. Вводим зависимости для ограничений:

курсор в ячейку F4 → Копировать в буфер

курсор в ячейку F7 → Вставить из буфера

курсор в ячейку F8 → Вставить из буфера

курсор в ячейку F9 → Вставить из буфера и т.д. до ячейки F14

6. В строке Меню указатель мыши на имя Сервис → Поиск решения. Появляется диалоговое окно Поиск решения.

Назначаем целевую функцию (установить целевую ячейку):

- курсор в строку Установить целевую ячейку;

- вводим адрес ячейки $F$4;

- вводим направление целевой функции Максимальному значению;

- курсор в строку Изменяя ячейки;

- вводим адреса искомых переменных В$3:Е$3.

7. Вводим ограничения:

- указатель мышки на кнопку Добавить. Появляется диалоговое окно Добавление ограничения

- в строке Ссылка на ячейку вводим адрес $F$7;

- вводим знак ограничения ≤;

- в строке Ограничение введите адрес $Н$7;

- указатель мыши на кнопку Добавить.

На экране вновь диалоговое окно Добавление ограничения.

Вводим остальные ограничения задачи, по вышеописанному алгоритму;

после введения последнего ограничения кнопка ОК.

8. Вводим параметры для решения ЗЛП:

- в диалоговом окне указатель мыши на кнопку Параметры. На экране появляется диалоговое окно Параметры поиска решения;

- устанавливаем флажки в окнах Линейная модель (это обеспечит применение симплекс-метода) и Неотрицательные значения;

- указатель мыши на кнопку ОК. На экране диалоговое окно Поиск решения;

- указатель мыши на кнопку Выполнить.

Через непродолжительное время появится диалоговое окно Результаты поиска решения и исходная таблица с заполненными ячейками В3:Е3 для значений Xi и ячейка F4 с максимальным значением целевой функции

Из сценария решения задачи видно, что максимальная общая прибыль от реализации изготовляемой продукции составляет 1939,428 тыс.руб. при норме затрат на производство кабеля 1 вида – 1200, 2 вида - 624,2857, и не производить 3 и 4 вид кабеля.

При этом на волочение тратиться - 2563,714 часов рабочего времени, на наложение изоляции - 1449,714 ч, на скручивание элементов в кабеле – 11176 ч, на освинцовывание – 3600 ч, на испытание и контроль - 3456,428 ч.

3.2. Решение задачи с помощью Пакета Экономических Расчетов (ПЭР)

Запускаем программу ПЭР.

Выбираем пункт 1 – Линейное программирование → Enter

Ввод новой задачи (2) → Enter

Вводим название для задачи → Enter

Далее вносим исходные параметры задачи:

- Желаете максимизировать → 1

- Количество переменных в задаче → 4

- Количество ограничений в задаче → 5

- Использовать стандартные имена переменных → Y

После этого программа просит ввести коэффициенты функции цели и ограничений:

Далее программа приступает непосредственно к решению задачи

и выводит таблицу, содержащую итоговые результаты вычислений:

Из этой таблицы видно, что максимальна прибыль, согласно которому следует, что норма затрат на 1 вид кабеля составляет 1200, на кабель 2 вида – 624,285, а на 3 и 4 вид кабеля нормы нет. Максимальная общая прибыль от реализации изготовляемых продуктов - 1939,429 тыс.руб. Точно такие же результаты получились при решении данной задачи с помощью пакета Solver.

3.3. Решение задачи с помощью MathCAD.

Введем обозначения:

Норма затрат на производство кабеля 1 типа – х₁.

Норма затрат на производство кабеля 2 типа – х₂.

Норма затрат на производство кабеля 3 типа – х₃.

Норма затрат на производство кабеля 4 типа – х₄.

Прибыль от реализации от 1 км кабеля – F.

Запускаем MathCAD, вводим исходные обозначения и целевую функцию.

Затем с помощью функции Givenвводим ограничения по условию данной задачи:

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

4. Результаты решения.

Из сценария решения задачи видно, что максимальная общая прибыль от реализации изготовляемой продукции составляет 1939,428571 тыс.руб. при норме затрат на производство кабеля 1 вида – 1200, 2 вида - 624,2857, и нет нормы затрат на 3 и 4 вид кабеля.

При этом на волочение тратиться - 2563,714 часов рабочего времени, на наложение изоляции - 1449,714 ч, на скручивание элементов в кабеле – 11176 ч, на освинцовывание – 3600 ч, на испытание и контроль - 3456,428 ч.

Точно такие же результаты получились при решении данной задачи с помощью ПЭР иMathCAD.

Заключение.

Пакет Solver обеспечивает возможность:

٭ использовать одновременно до 200 адресов ячеек, содержащих отыскиваемые значения переменных (параметров);

٭ устанавливать конкретный результат для целевой функции и для этого значения отыскивать значение параметров;

٭ отыскивать оптимальное значение (минимальное или максимальное) целевой функции, то есть находить одно из наилучших возможных решений;

٭ генерировать множество различных решений для сложных задач линейного программирования. При этом возможно сохранение вариантов решении в виде сценариев.

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

размерностью 40 х 40. Она имеет следующие преимущества.

٭ можно определить четырехсимвольные имена переменных.

٭ можно вывести на экран и распечатать конечное решение и результаты анализа на устойчивость.

٭ задачу можно модифицировать и сохранить на диске(те) для последующего считывания.

٭ можно вывести на экран отдельные шаги симплекс - метода.

Перечислим основные достоинства MATHCAD`a.

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

٭ программирование на общепринятом математическом языке

позволяет преодолеть языковой барьер между машиной и пользователем. Потенциальные пользователи пакета - от студентов до академиков.

٭ совместно применение текстового редактора, формульного

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

вычислений получить готовый документ.

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

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

1. Акулич И.Л. «Математическое программирование в примерах и задачах», М. – Высшая школа, 1986

2. Методические указания для выполнения курсовых работ по курсу «Математические методы и модели исследования операций», Уфа, 2005

3. Работа в системе Mathcad: Методические указания по выполнению лабораторных работ под ред. Воронина А.В.; Томск, 2004