Использование пакетов прикладных программ для решения задач линейного программирования (стр. 1 из 2)
ГОУ ВПО
Уфимский государственный авиационный технический университет
Кафедра вычислительной математики и кибернетики
КУРСОВАЯ РАБОТА
по дисциплине
«Математические методы и модели ИО»
на тему
«Использование пакетов прикладных программ для решения задач линейного программирования»
Выполнили:
студент гр. МИЭ-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
| Технологическая операция | Нормы затрат времени на обработку 1 км кабеля (ч) вида | Общий фонд рабочего времени | |||
| 1 | 2 | 3 | 4 | ||
| Волочение | 1,2 | 1,8 | 1,6 | 2,4 | 7200 |
| Наложение изоляции | 1,0 | 0,4 | 0,8 | 0,7 | 5600 |
| Скручивание элементов в кабель | 6,4 | 5,6 | 6,0 | 8,0 | 11176 |
| Освинцовывание | 3,0 | - | 1,8 | 2,4 | 3600 |
| Испытание и контроль | 2,1 | 1,5 | 0,8 | 3,0 | 4200 |
| Прибыль от реализации от 1 км кабеля (тыс.руб.) | 1,2 | 0,8 | 1,0 | 1,3 | |
Определить такой план выпуска кабеля, при котором общая прибыль от реализации изготовляемой продукции являлись бы максимальной.
2. Математическая модель задачи.
Составим математическую модель задачи. Искомое норма затрат времени на обработку кабеля 1 вида обозначим через Х1, норма затрат кабеля 2 вида - через Х2, норма затрат 3 вида – через Х3, норма затрат 4 вида – через Х4. Математическая постановка состоит в определении максимального значения функции
F = 1,2∙x1 + 0,8∙x2 +1∙ x3 +1,3∙x4 → max (1.1)
при выполнении условий:
1,2∙х1 + 1,8∙х2 + 1,6∙х3 + 2,4∙х4 ≤ 7200 (1.2)
1∙х1 + 0,4∙х2 + 0,8∙х3 + 0,7∙х4 ≤ 5600
6,4∙х1 + 5,6∙х2 + 6∙х3 + 8∙х4 ≤11176
3∙х1 + + 1,8∙х3 + 2,4∙х4 ≤ 3600
2,1∙х1 + 1,5∙х2 + 0,8∙х3 + 3∙х4 ≤ 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 ч.