Стандартные пакеты прикладных программ для решения задач математического программирования
Методы нахождения решения различных задач линейного программирования определяют алгоритмы решения конкретных задач. Под алгоритмом понимается определенное правило, согласно которому установлен соответствующий порядок выполнения действий над исходными данными в целях получения искомых результатов.
Зная алгоритм решения данной конкретной задачи, можно составить программу ее решения на ЭВМ. Однако во многих случаях составление такой программы оказывается излишним, поскольку можно воспользоваться существующими информационными технологиями.
Пакет прикладных программ (ППП) представляет собой набор программ, позволяющих решать определенный класс задач и ориентированный на определенный тип машин.
Решение задач линейного программирования с помощью пакета Solver
Одним из наиболее часто используемых для нахождения решения задач линейного программирования пакетов прикладных программ является Solver.
В основе работы пакета Solver лежат итерационные методы поиска решений. Пакет позволяет находить решения задач, имеющих целевую функцию, вычисление которой можно записать в виде формулы в одну из ячеек рабочего листа электронной таблицы.
Решение задач линейного программирования с помощью Пакета Экономических Расчетов (ПЭР)
Пакет экономических расчетов является адаптацией пакета «Системы количественного анализа в управлении» версии 5.0.
ППП ПЭР предназначен для решения ряда экономико – математических задач на персональных компьютерах типа PENTIUM. В пакете реализованы наиболее часто используемые экономико – математические задачи и методы, в частности: линейное программирование.
Максимальные размеры решаемых задач: 40 основных переменных и 40 ограничений. Программа линейного программирования использует симплексный – метод решения задач.
Решение задач линейного программирования с помощью пакета прикладных программ MathCAD.
Mathcad - программное средство, среда для выполнения на компьютере разнообразных математических и технических расчетов, снабженная простым в освоении и в работе графическим интерфейсом, которая предоставляет пользователю инструменты для работы с формулами, числами, графиками и текстами. В среде Mathcad доступны более сотни операторов и логических функций, предназначенных для численного и символьного решения математических задач различной сложности.
Первая версия пакета MATHCAD появилась в 1986г. Пакет постоянно совершенствуется. В настоящее время существуют версии MATHCAD, работающие под Windows.
1. Постановка задачи.
При производстве 4 видов кабеля выполняется 5 групп технологических операций. Нормы затрат на 1 километр кабеля данного вида на каждой из групп операций, прибыль от реализации 1 километра каждого вида кабеля, а также общий фонд рабочего времени, в течение каждого могут выполняться эти операции, указаны в таблице 1.
Один из стандартных пакетов прикладных программ для решения задач линейного программирования — пакет LP88. Этот пакет широко используется специалистами в конкретных предметных областях. Программа LP88 позволяет организовывать и решать линейные задачи, содержащие до 255 ограничений и до 2 255 переменных.
Программа LP88 функционирует на IBM PC под управлением операцйонной системы PC DOS версий 2.00 и выше.
Подробное описание программы LP88 дано в [7]. Там же приведены методические указания по работе с этой программой. Здесь мы отметим только некоторые ее особенности.
1. Программа работает в диалоговом режиме; вопросы пользователю высвечиваются на экране. Ввод данных осуществляется с помощью редактора LP88 (Display Editor), который легко осваивается пользователем.
2. По завершении работы программы на экране появляются все ненулевые значения компонент оптимального решения, а также значения двойственных переменных.
3. Программа позволяет вносить изменения во входные данные (коэффициенты системы ограничений и целевой функции) с помощью редактора LP88. При этом не требуется вновь вводить неизмененные входные данные.
В качестве примера рассмотрим задачу об использовании ресурсов.
Фабрика выпускает три вида тканей, причем плановое задание составляет: не менее 90 м ткани 1-го вида, 70 м — 2-го и 60 м — 3-го вида.
Поиск оптимального плана на компьютере занимает несколько секунд. После завершения работы программы экран будет выглядеть так:
| tkani | SOLUTION is OPTIMAL | DATE. | ||||
| MAXIMUM | ENTERS | BASIS X: | 3 | |||
| PIVOTS: | 5 | LEAVES | BASIS S.- | 3 | ||
| LAST INV: | 0 | DELTA: | 0 | стоим | 19075 | |
| BASIS | S.6 | S.2 | S.4 | ТКІ | tk2 | ткЗ |
| PRIMAL | 26.25 | 26.25 | 22.25 | 112.5 | 70 | 8.25 |
| DUAL | 2.5 | 0 | 25 | 0 | -37.5 | 0 |
В строке BASIS указаны основные переменные оптимального решения (тк1, тк2, ткЗ — оптимальный план выпуска ткани 1-го, 2-го, 3-го видов, S.l, S.2, S.3 — остаток 1-го, 2-го, 3-го ресурса, S.4, S.5, S.6 — перевыполнение задания по тканям соответственно 1-го, 2-го и 3-го видов).
В строке PRIMAL указаны значения основных переменных оптимального решения, в строке DUAL — значения двойственных переменных. Указатель “стоим” задает оптимальное значение целевой функции.Подробное описание решения этой задачи приведено в [7].
С помощью функциональных клавиш — можно получать дополнительную информацию о решении, а также проводить анализ зависимости его структуры от входных данных.
Эта таблица указывает границы значений коэффициентов целевой функции (столбцы MINIMUM и MAXIMUM), которые обеспечивают сохранение типа переменных в оптимальном решении. Так, если цена 1 м ткани 1-го типа станет меньше 50 или больше 90 денежных единиц, набор основных переменных в оптимальном решении изменится (т.е. целевая функция будет достигать своего максимума в другой угловой точке системы ограничений).
Для задачи об использовании ресурсов при отсутствии ограничений снизу такие данные интерпретируются как пределы рентабельности производства продукции.
Если переменная xh которая задает выпуск /-го вида продукции, перестает быть основной в оптимальном решении, это значит, что продукцию /-го вида становится Невыгодно производить и ее не следует включать в оптимальный план производства.В этом случае в столбцах MINIMUM и MAXIMUM указаны граница коэффициентов правой части системы ограничений, при которых не изменяется набор основных переменных в оптимальном решении двойственной задачи.
Таким образом программа LP88 позволяет не только найти решение задачи линейного программирования, но и провести его
экономико-математический анализ (оценку дефицитности ресурсов, рентабельности продукции, эффективности отдельных планов, сопоставление оптимальных условных затрат и результатов производства, определение норм заменяемости ресурсов и т.п.).
Возможность проведения экономико-математического анализа результатов существенно увеличивает преимущество решения задач на ЭВМ даже для относительно простых задач линейного программирования (см. для сравнения, например, разд. 6.5, где элементы такого анализа проведены вручную).Количественный анализ задачи производится с помощью пробного изменения ее исходных данных. Сначала следует выявить факторы, ограничивающие производство, т.е. имеющие ненулевые объективно обусловленные оценки. Это можно сделать с помощью клавиши . Ее использование приведет к следующей записи на экране:
| tkani | SOLUTION IS MAXIMUM | стоим 19 075 | |||
| DUAL PROBLEM SOLUTION | |||||
| ROW ID | STATUS | DUAL | RHS | USAGE | SLACK |
| VALUE | VALUE | ||||
| оборуд | BINDING | 2.5 | 780 | 780 | 0 |
| сырье | NONBINDING | 0 | 850 | 823.75 | 26.25 |
| эл-эн | BINDING | 25 | 790 | 790 | 0 |
| ТК1-ПЛ | NONBINDING | 0 | 90 | 112.5 | -22.5 |
| тк2-пл | BINDING | -37.5 | 70 | 70 | 0 |
| ткЗ-пл | NONBINDING | 0 | 60 | 86.25 | -26.5 " |
Здесь RHS VALUE — правые части системы ограничений.
USAGE — фактическое использование ресурсов в ограничениях или фактическое выполнение плановых заданий, SLACK — разность между значениями этих столбцов. Отсюда видно (см. также разд. 6.5), что оборудование и электроэнергия являются дефицитными ресурсами и их увеличение приводит к повышению максимального дохода. Продукция тк2 — нерентабельная — уменьшение плана по этой продукции также увеличит максимальное значение целевой функции.
Рассмотрим, например, два вида изменений исходных данных: а) уменьшение задания по ткани 2-го вида на 10 единиц и б) увеличение запаса ресурса электроэнергии на 12 единиц.
В результате первого изменения на экране появится решение следующего вида:
| MAXIMUM | ENTERS: | BASIS | X: | 3 | ||
| PIVOTS: | 5 | LEAVES: | BASIS | S: | 3 | |
| LAST INV: | 0 | DELTA 0 | стоим | 19 450 | ||
| BASIS | S.6 | S.2 | S.4 | тк1 | tk2 | ткЗ |
| PRIMAL | 27.5 | 47.5 | 35 | 125 | 60 | 87.5 |
| DUAL | 2.5 | 0 | 25 | 0 | -37.5 | 0 |
Уменьшение плана по нерентабельному виду продукции позволило перераспределить ресурсы в пользу более рентабельных — 1-го и 3-го видов. В результате целевая функция увеличилась на 375 ден. единиц.
Второе изменение приведет к следующему решению:
| MAXIMUM | ENTERS: | BASIS | X: | 3 | |
| PIVOTS: | 5 LEAVES: | BASIS | S: | 3 | |
| LAST INV: | 0 DELTA 0 | стоим 19 750 | |||
| BASIS | S.6 S.2 | S.4 | тк1 | tk2 | ткЗ |
| PRIMAL | 24.5 56.5 | 41 | 131 | 60 | 84.5 |
| DUAL | 2.5 0 | 25 | • 0 | -37.5 | 0 |
Целевая функция возросла еще на 300 ден. единиц.
Программа ЬР88 позволяет также получать таблицу значений базисных решений и значений целевой функции задачи, что дает возможность следить за пошаговым его изменением. Программа ЬР88 может быть использована и в учебных целях.
Составление и отладка программ, подобной ЬР88, требуют немалых затрат и имеют смысл только в том случае, если спрос на готовые пакеты достаточно высок. Так, например, существуют стандартные программы решения оптимизационных задач с квадратичной целевой функцией. Если требуется решить частную задачу, то, как правило, приходится составлять программу самостоятельно, используя разработанный алгоритм. Стандартных текстовых программ, задающих решение частных математических задач, обычно не существует. Программистам бывает проще самим написать текст программы, чем приспособить чужой текст под свой компьютер.
Эффективность решения реальных многоразмерных оптимизационных задач определяется, как правило, тесным взаимодействием специалиста в предметной области (экономиста, менеджера и т.п.), математика и программиста.
Scilab - мощный математический пакет для построения 2D и 3D графиков, решения задач линейной алгебры, работы с разряженными матрицами; предоставляет возможность использования интерполяции и аппроксимации, дифференциальной и недифференциальной оптимизации. Также пакет имеет встроенный язык. подробнее.
Maxima
Maxima - это система компьютерной алгебры, созданная на языке программирования Common Lisp, первый запуск которой состоялся в далеком 1982 году. Данная утилита предназначена для проведения аналитических и численных вычислений, а также формирования графиков функций. Эта разработка располагает несколькими графическими интерфейсами юзера (wxMaxima, XMaxima и прочими). Программа осуществляет численные расчеты максимально верно, поскольку применяет дроби, целые числа (как с плавающей точкой произвольной точности, так и без нее). Стоит отметить, что при использовании псевдографики, приложение способно функционировать в режиме командной строки. Система имеет довольно понятный интерфейс, несмотря на то, что современным его назвать сложно. подробнее.
Graph Online
Graph Online - бесплатный сервис, предназначенный для визуализации графа и поиска кратчайшего пути на графе. Создание графа выполняется по матрице смежности или матрице инцидентности. Кроме поиска кратчайшего пути можно осуществить поиск компонента связанности. Сервис поддерживает работу с орграфами и неориентированными графами. Построенный граф можно сохранить и продолжить работу с ним позже. подробнее.
SMath Studio
SMath Studio - хороший пакет для вычисления, упрощения математических графиков, построения графиков функций. Интерфейс программы очень понятный и не уступает MathCad. подробнее.
SMath Studio Cloud
SMath Studio Cloud - онлайн версия бесплатного математического пакета SMath Studio. Сервис поддерживает множество функций для математических вычислений и анализа: построение графиков (2D и 3D), множество математических функций, работа с матрицами, решение и упрощение выражений. Большим достоинством онлайн версии является возможность загрузки файлов *.sm, *.smz и *.xmcd. Сервис позволяет сохранить вычисления для дальнейшей работы, а также предоставить ссылку на них другим пользователям, распечатать. подробнее.
GNU Octave
GNU Octave - программный пакет решений для работы с математическими моделями и графиками. Программное обеспечение написано на языке программирования C++ и его можно внедрять в другие проекты. Программа имеет поддержку множества функций при решении математических задач, а в случае если пользователю не будет хватать её функционала, в сети всегда можно найти и расширить их с помощью дополнений. По заверениям разработчиков, совместим с таким ПО как MATLAB и поддерживает многие его функции. Так же программа является кроссплатформенной, что делает её доступной для всех пользователей разных операционных систем. подробнее.
Существует большое количество свободных и коммерческих программ для математических вычислений. Их можно разделить на две большие группы:
1. Системы компьютерной алгебры — программы символьных аналитических вычислений;
2. Программы для численных (числовых) вычислений.
Системы компьютерной алгебры
Системы компьютерной алгебры служат для выполнения аналитических вычислений. С их помощью можно выполнять следующие операции:
• осуществлять решение неопределенных интегралов (т.е. находить первообразную функции);
• вычислять определенные интегралы (в том числе несобственные);
• находить производные, в том числе производные сложных функций (т.е. выполнять дифференцирование);
• упрощать выражения (например, раскрывать скобки и приводить подобные слагаемые);
• решать алгебраические и дифференциальные уравнения;
• находить пределы функций и последовательностей;
• вычислять суммы рядов и бесконечные произведения;
• выполнять разложение функций в ряды;
• строить графики функций.
• Программа Maxima имеет широчайший набор средств для проведения аналитических вычислений, численных вычислений и построения графиков. По набору возможностей система близка к таким коммерческим системам как Maple и Mathematica.
• Axiom — свободная (бесплатная) программа. Состоит из среды интерпретатора, компилятора и библиотеки, описывающей строго типизированную, математически правильную иерархию типов;
• Maple — проприетарная (коммерческая) программа. Предназначена для символьных вычислений, хотя имеет ряд средств и для численного решения дифференциальных уравнений и нахождения интегралов. Обладает развитыми графическими средствами. Имеет собственный язык
программирования, напоминающий Паскаль;
• Mathematica — проприетарная (коммерческая) программа. Содержит множество функций как для аналитических преобразований, так и для численных расчётов. Кроме того, программа поддерживает работу с графикой и звуком, включая построение двух- и трёхмерных графиков функций, рисование произвольных геометрических фигур, импорт и экспорт изображений и звука.
Программы для численных вычислений
Программы для численных вычислений служат для проведения численных инженерных и научных расчетов. С их помощью можно выполнять следующие операции:
• численно осуществлять операции матричной алгебры (сложение/вычитание, умножение, решение систем линейных уравнений, нахождение собственных значений и векторов);
• работать с разреженными матрицами (сборка, факторизация);
• разрабатывать алгоритмы и программы для реализации численных методов;
• осуществлять визуализацию данных: простую двумерную и сложную трехмерную (включая объемную визуализацию.
Свободные (бесплатные) пакеты :
• Scilab - пакет прикладных математических программ, предоставляющий мощное открытое окружение для инженерных (технических) и научных
• GNU Octave — свободная среда для численных вычислений, использующая совместимый с MATLAB язык высокого уровня. Octave представляет интерактивный командный интерфейс для решения линейных и нелинейных математических задач, а также проведения других численных экспериментов.
Проприетарные (коммерческие) пакеты :
• MATLAB - пакет прикладных программ для решения задач технических вычислений. MATLAB используют более 1000000 инженерных и научных работников, он работает на большинстве современных операционных систем, включая GNU/Linux, Mac OS, Solaris и Microsoft Windows;
• Mathcad - программа для выполнения и документирования инженерных
и научных расчётов;
• Origin - пакет программ фирмы для численного анализа данных и научной графики, работающий на компьютере под управлением операционной системы Microsoft Windows.
Читайте также: