Экономико-математические методы

Введение

Математические модели являются одним из основных инструментов познания человеком мира явлений. Под математическими моделями понимаются основные законы и связи, присущие изучаемым явлениям. Это могут быть формулы или уравнения, наборы правил или соглашений, выраженные в математической форме. Однако для их решения недостаточно простых формул, необходимо использовать вычислительную технику.
Использование компьютеров для математического моделирования изменило само понятие "решить проблему". До возникновения таких возможностей исследователю было достаточно описать математическую модель. Если же модель была обоснована и выводы доказаны, то это означало, что модель в принципе существует, то есть априори можно было считать, что модель адекватно описывает реальность. Поскольку, как правило, не существует простых формул, описывающих поведение модели и, следовательно, и поведение реального объекта, единственный способ – получить точное решение - использование численных методов для решения задачи. В этом случае требуются особые алгоритмы, вычисления и последовательность логических операций, которые должны быть выполнены для получения численных решений.
Целью работы является анализ и решение задачи о загрузке оборудования. Для достижения поставленной цели в работе решаются следующие задачи:
1. Рассмотреть теоретические аспекты постановки задачи;
2. Проанализировать возможные методы решения;
3. Реализовать графический метод решения задачи;
4. Решить задачу симплекс-методом;
5. Дать решение двойственной задачи;
6. Решить задачу с использованием ППП Excel.

1 ТЕОРИЯ И МЕТОДЫ ЭКОНОМИКО-МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ ЗАДАЧИ ОПТИМАЛЬНОГО ПЛАНИРОВАНИЯ

1.1 Общая математическая формулировка решаемой экономико-математической задачи

Рассматривается задача выпуска некоторого объема продукции исходя из ограничений по затратам времени и ресурсов. То есть за указанный промежуток времени t необходимо выпустить некоторое количество n1, n2,…,nk продукции. Производство осуществляется на наборе станков s1, s2,…,sm. При этом известна мощность каждого станка по видам продукции в единицу времени, а также уровень затрат производства. Цель задачи – минимизация затрат на общий объем производства продукции, либо максимизация выручки или прибыли [3].
Обозначим через xij – время, в течении которого станок si будет занят изготовлением продукции pj (i = 1, 2,…,m; j = 1, 2,…,k) Тогда затраты на производство всей продукции выразятся функцией
F=b11x11+b12x12+…+bmkxmk→(min), при ограничениях:
по времени работы каждого станка, которое не превышает величины t :
x11+x12+…+x1k≤t1…xm1+xm2+…+xmk≤tm
по номенклатуре и не отрицательности переменных
a11x11+a12x12+…+a1mx1k=n1…am1xm1+am2xm2+…+amkxmk=nk
xij≥0
В данном случае имеет место одна из формулировок задачи, так как речь может идти о различных технологиях производства, а также различных видах ресурсов. При этом в подобной задаче возможна ситуация, связанная с дополнительными ограничениями по количеству производимой продукции. Например, предприятие имеет заключенные контракты на минимальное заранее определенное количество какой-либо продукции. Тогда вместо ограничения неотрицательности появляется дополнительное ограничение на объем производства.

1.2 Методы решения задачи

Данная задача может быть решена несколькими методами. [1]
При решении задачи с двумя типами продукции, наиболее простой способ решения задачи – графический метод.
При решении задачи графически необходимо выполнение следующих этапов [4]:
Построение прямых, соответствующих неравенствам или равенствам ограничениям.
Определение полуплоскостей.
Определение многоугольника решений, ограничивающего область допустимых решений;
Построение направляющего вектора целевой функции;
Параллельный перенос прямой целевой функции c1x2 + c2x2 = 0 в направлении вектора N до крайней точки многоугольника решений.
Определение координаты точки и значениея целевой функции в этой точке.

Рисунок 1.1 – Общий вид графического решения задачи
При этом могут возникать следующие ситуации [5]:
Целевая функция принимает экстремальное (минимальное или максимальное) значение в единственной точке А.

Рисунок 1.2 – Целевая функция принимает оптимальное значение в единственной точке
Целевая функция принимает экстремальное значение в любой точке отрезка АВ.

Рисунок 1.3 – Целевая функция принимает оптимальное значение в любой точке отрезка


Целевая функция не ограничена сверху (при поиске на максимум) или снизу (на минимум)

Рисунок 1.4 – Целевая функция не ограничена сверху (при решении задачи на максимум)
Система ограничений задачи несовместна

Рисунок 1.5 – Область решений не существует

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

. Для этого необходимо рассмотреть все его этапы.
Первый этап представляет собой формирование опорного плана. Для этого задача приводится к каноническому виду, введением дополнительных балансовых переменных, для которых вводится условие неотрицательности.
Второй этап состоит в проверке полученного плана на оптимальность. Для этого проверяются значения индексной строки, соответствующие целевой функции. Если среди этих значений есть хотя бы одно отрицательное, то построенный план не является оптимальным и требует улучшения.
Третий этап – определение ведущего столбца и строки. Для этого необходимо выполнить следующие действия. Найти наибольшее по модулю отрицательное значение индексной строки. Соответствующий столбец будет базисным, далее. Последовательно, разделить все элементы столбца свободных членов на элементы базисного столбца, отбрасывая отрицательные и нулевые значения. Строка с наибольшим отношением и будет ведущей.
Четвертый этап – построение нового плана производства. Метод линейного программирования состоит в переходе к новому плану путем линейных матричных преобразований, то есть пересчета симплексной таблицы с использованием метода Жордано-Гаусса.
Основная теорема линейного программирования.
Если целевая функция ЗЛП достигает экстремального значения в некоторой точке области допустимых решений, то она принимает это значение в угловой точке. Если целевая функция ЗЛП достигает экстремального значения более чем в одной угловой точке, то она принимает это же значение в любой из выпуклой линейной комбинации этих точек.
То есть симплекс метод основан на сходимости метода к оптимальной точке, если такая существует. Эта схема перебора точек была предложена Р. Данцигом [7].
Основным понятием являются угловые точки, характеризующиеся набором m базисных переменных. Соответственно для перехода к новой угловой точке необходимо заменить одну базисную переменную на небазисную.
Преобразование симплекс-таблиц необходимо продолжать до того момента, пока не будет получено оптимальное решение [5].
В ходе решений возникает несколько ситуаций.
1) Одна из базисных переменных оказывается равна нулю. В этом случае полученный план называется врожденным. При такой ситуации необходимо вернуться к предыдущему полученному решению и выбрать в качестве базисного (ведущего) другой столбец.
2) В индексной строке все полученные значения неотрицательны, но как минимум одна переменная нулевая, в этом случае преобразования закончены, смена переменной не даст изменения целевой функции, задача имеет как минимум два решения.
3) Решение двойственной задачи существует, если существует решение прямой задачи. Для его нахождения используют последнюю симплекс-таблицы, соответствующую оптимальному плану. Значения индексной строки для балансовых (небазисных) переменных соответствуют решению двойственной задачи.
4) Если при решении задачи возникает необходимость нахождения минимума целевой функции, то используется вектор с положительной симплекс-разностью. Алгоритм решения задачи полностью идентичен.
Основная идея теории двойственности: для каждой задачи линейного программирования (ЛП) существует некоторая задача ЛП, решение которой тесно связано с прямой. При этом:
матрица ограничений двойственной задачи (ДЗ) есть транспонированная матрица прямой задачи;
вектор "цен" для прямой задачи есть вектор правых частей ограничений задачи ДЗ и наоборот.
Двойственные оценки характеризуют дефицитность ресурсов. На основании этих оценок можно определить, насколько увеличивает максимальное значение целевой функции прямой задачи при росте количества ресурса на единицу [5].


2 ПРАКТИЧЕСКОЕ РЕШЕНИЕ ЗАДАЧИ ОПТИМАЛЬНОГО ПЛАНИРОВАНИЯ
2.1 Решение задачи графическим методом

Имеются три станка. Два вида изделий проходят последовательную обработку на имеющихся станках. Имеются исходные данные по фонду полезного времени для каждого станка, также, в таблице представлены данные по затратам времени на обработку каждого изделия.
Таблица 1 – Исходные данные
Станки Вид изделия Фонд времени (час)

В1 В2
А1 4 2 48
А2 0 3 36
А3 2 2 40
Цена единицы изделия (тыс