Обзор основных методов математической оптимизации для задач с ограничениями / Хабр

Особенности
математических методов, применяемых к решению экономических задач

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

Не стоит говорить о применении арифметики, алгебры в экономических
исследованиях. Особняком здесь стоят так называемые методы оптимизации, чаще
называемые как экономико-математические методы.

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

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

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

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

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

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

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

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

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

Предприятие может работать по трем технологическим процессам (ТП1, ТП2,
ТП3). При работе по первому технологическому процессу предприятие выпускает 300
изделий в день, по второму – 250, по третьему – 450 изделий в день. Расходы ресурсов,
необходимые предприятию для работы в течение дня по каждому из технологических
процессов, приведены в таблице.

Это означает, например, что в случае, если предприятие в течение одного
дня работает по технологическому процессу ТП1, то для этого требуется 15 тыс.
человеко-ч рабочей силы, 35 тыс. кВт-ч электроэнергии, 20 т сырья.

Предприятие располагает рабочей силой в количестве 1,2 млн. человеко-ч,
электроэнергией – 3 млн. кВт-ч, сырьем – 1500 т.

По требованию заказчика необходимо выпустить не менее 500 изделий по
второму технологическому процессу.

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

2. Построение базовой аналитической модели

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

Для построения математической модели введем следующие переменные:

В данной задаче имеются ограничения на расход ресурсов (рабочей силы,
электроэнергии, сырья). Так расход рабочей силы по первому технологическому
процессу составляет 15 тыс. человеко-ч/день, по второму – 20 тыс.
человеко-ч/день, по третьему – 25 тыс. человеко-ч/день.

Аналогично можно составить ограничение на расход электроэнергии:

и на расход сырья:

Имеется также ограничение на выпуск изделий по второму технологическому
процессу – необходимо выпустить не менее 500:

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

Приведем полную математическую модель данной задачи:

3. Обоснование и описание вычислительной процедуры

.1 Обоснование вычислительной процедуры

В задачах линейного программирования, где все ограничения являются
неравенствами вида “£” (с отрицательной правой частью), дополнительные (остаточные)
переменные позволяют формировать начальное допустимое базисное решение.
Естественно, что возникает вопрос: как найти начальное допустимое базисное
решение в задачах линейного программирования, где есть ограничения в виде
равенств или неравенств типа “³ “?

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

3.2 Описание вычислительной процедуры

Для задач с ограничениями “³” обычно нельзя использовать в качестве начального
допустимого решения (начальной угловой точки области допустимых решений) начало
координат, то есть решение, в котором все исходные переменные математической
модели равны нулю. Такое решение, как правило, оказывается недопустимым по
причине не соответствия ограничениям. Избыточные переменные использовать в
качестве базисных переменных невозможно, так как они входят в уравнения с
коэффициентом -1. В случае, когда переменным

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

Искусственные переменные используются только для получения начального
базиса. Они не имеют какого-либо содержательного смысла, связанного с условием
задачи; их нельзя интерпретировать как объемы производства, решение, содержащее
искусственные переменные, является недопустимым, то есть не соответствует
исходной системе ограничений.

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

ЭТАП 1.

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

ЭТАП 2.

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

Рассмотрим реализацию этого метода оптимизации более подробно. Пусть в
задаче, которая представлена в стандартной форме, имеется n-переменных (включая
остаточные и избыточные). Базис состоит из m-переменных (m-количество
уравнений), из них k-искусственных:

Метод реализуется следующим образом:

. Задача сводится к стандартной форме.

. Выполняется переход к целевой функции, направленной на максимум (если
это необходимо).

. Строится искусственный базис, т.е. вводятся искусственные переменные

. Строится искусственная целевая функция, равная сумме искусственных
переменных:

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

. Для приведения всей задачи к стандартной форме выполняется максимизация
искусственной целевой функции. Для этого она умножается на -1.

. Определяется начальное (недопустимое) решение. Базис состоит из
переменных, из них k-искусственные, остальные m-k-остаточные переменные. Если
остаточных переменных нет (т.е. в задаче не было ограничений “не
больше”), то обычно весь базис составляется из искусственных переменных.

Базисные переменные принимают значения, равные правым частям ограничений
задачи. Все остальные переменные (исходные и избыточные) считаются равными
нулю. В этом случае исходная целевая функция принимает значение 0, а
искусственная целевая функция ─ значение W0.

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

. Реализуется первый этап двухэтапного метода: с помощью обычных процедур
симплекс-метода выполняется минимизация функции W. При этом переменные,
включаемые в базис, выбираются по строке искусственной целевой функции (т.е. на
каждом цикле в базис включается переменная, соответствующая максимальному по
модулю отрицательному коэффициенту в W-строке; столбец, соответствующий этой
переменной, становится ведущим). Все преобразования выполняются по обычным
формулам симплекс-метода или по “правилу прямоугольника”.

. Выполняется анализ результатов минимизации искусственной целевой
функции. Если найденное минимальное значение (W равно 0) и все искусственные
переменные оказались небазисными (т.е. равными 0), это означает, что найдено
допустимое решение исходной задачи, т.е. решение, которое удовлетворяет
исходным ограничениям; выполняется переход к шагу 11.

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

. Над сокращенной симплекс таблицей выполняются обычные процедуры
симплекс-метода (т.е. в Е-строке находится максимальный по модулю отрицательный
элемент, соответствующая переменная включается в базис, выбирается переменная
для исключения из базиса и т.д.). В результате находится оптимальное решение
исходной задачи.

4. Решение задачи оптимизации на основе симплекс-таблиц

Математическая модель решаемой задачи:

4.1 Приведение задачи к стандартной форме

Приведем задачу к стандартной форме. Все ограничения требуется
преобразовать в равенства. Для этого в ограничения “меньше или равно”
необходимо ввести остаточные переменные. В ограничение “больше или
равно” добавляется избыточные переменные. Математическая модель задачи в
стандартной форме имеет следующий вид:

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

4.2 Поиск оптимального решения задачи на основе двухэтапного метода

Первый этап (поиск допустимого решения).

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

Таким образом, начальный базис будет состоять из остаточных переменных

Составляем искусственную целевую функцию – сумму всех искусственных
переменных:

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

Искусственная целевая функция выражается через небазисные переменные. Для
этого сначала требуется выразить искусственную переменную через небазисные
переменные:

Выраженная таким образом искусственная переменная подставляется в
искусственную целевую функцию:

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

Приведем полную математическую модель задачи, приведенную к стандартной
форме:

Определяется начальное решение. Все исходные, а также избыточные
переменные задачи являются небазисными, т.е. принимаются равными нулю.
Искусственные, а также остаточные переменные образуют начальный базис: они
равны правым частям ограничений. Для рассматриваемой задачи начальное решение
следующее:

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

Таблица 4.1

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

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

В таблице в строке искусственной целевой функции максимальное по модулю
(в этой строке) отрицательное значение, равное -250. Это коэффициент при
переменной

Переменную, которой соответствует ведущий столбец, включим в базис вместо
переменной, которой соответствует ведущая строка; в столбце “Базис”
вместо переменной, исключенной из базиса, указывается переменная, включенная в
базис. Все элементы ведущей строки делятся на ведущий элемент.

Все элементы ведущего столбца (кроме ведущего элемента) заменяются
нулями. Все остальные элементы таблицы (включая E-строку и столбец
“Решение”) пересчитываются по “правилу прямоугольника”.
Этот пересчет выполняется следующим образом: мысленно вычерчиваем
прямоугольник, одна вершина которого совпадает с ведущим элементом, а другая –
с элементом, образ которого мы ищем; остальные две вершины определяются
однозначно

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

Таблица 4.2

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

Таблица 4.3

Второй этап (поиск допустимого решения)

Решение, полученное по результатам первого этапа (табл.4.2), не является
оптимальным: в строке целевой функции имеются отрицательные элементы. Поиск
оптимального решения выполняется по обычным правилам симплекс-метода. В базис
включается переменная

Таблица 4.4

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

Таблица 4.5

Получено оптимальное решение (отсутствуют отрицательные элементы в строке
целевой функции):

5. Анализ задачи на чувствительность

Анализ решения на чувствительность-это анализ влияния изменений в постановке задачи на
оптимальное решение. Анализ моделей на чувствительность – это процесс,
реализуемый после получения оптимального решения. В рамках такого анализа
выявляется чувствительность оптимального решения к определенным изменениям исходной
модели.

.1 Анализ на чувствительность к изменению ограничения на использование
сырья

Для анализа влияния данного изменения на оптимальное решение используются
коэффициенты из столбца остаточной переменной, входящей в изменившееся
ограничение (используем последнюю симплекс-таблицу), в данном случае
Здесь коэффициенты взяты из столбца избыточной переменной

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

Решив эту систему неравенств, получим:

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

.2 Анализ на чувствительность к изменению одного из коэффициентов целевой
функции

Для анализа влияния изменений коэффициента целевой функции на оптимальное
решение используются коэффициенты из строки переменной, для которой изменился
коэффициент целевой функции.

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

Пусть коэффициент при
где

Рассчитаем диапазон изменений выпуска изделий при работе по
технологическому процессу ТП1, при котором решение остается оптимальным. Он
находится из условия неотрицательности всех коэффициентов Е-строки:

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

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

6. Построение модифицированной аналитической модели и анализ результатов
модификации

Часть имеющееся электроэнергии остается неизрасходованной (152 тыс. кВт-ч
из 3 млн кВт-ч). Найдем, на какую величину необходимо увеличить запасы
остальных ресурсов, чтобы использовать все ресурсы по возможности более полно.
Это позволит также увеличить выпуск изделий.

Попробуем увеличить количество рабочей силы. Предположим, например, что
рабочей силы стало на 20 млн. человеко-ч больше. Внесем соответствующие
изменения в правую часть ограничения:

Остальные ограничения и целевая функция остаются прежними. Получим
следующее оптимальное решение: ):

Варьируя величину рабочей силы, подберем такие значения, чтобы расход
ресурсов был наиболее полным. Для следующей математической модели

оптимальное решение будет следующим

Рабочий лист MS Excel находится в приложении В. Сравнительная
характеристика двух планов работы предприятия (при базовом и новом варианте
производства изделий) приведена в таблице 6.1.

Таблица 6.1

Из таблицы 6.1 видно, что незначительное увеличение рабочей силы позволит
практически полностью использовать все ресурсы. При этом производство деталей
также увеличится.

7. Примеры постановок и решений перспективных оптимизационных
управленческих задач

.1 Пример 1

Косметическая фирма выпускает три вида продукции:

Бальзам, шампунь и мыло. Для изготовления продукции используется три вида
сырья: крем, настойка из трав, глицерин.

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

Таблица 7.1

Решение.

Составим математическую модель задачи. Введем ограничения.

Ограничение на использование крема:

Ограничение на использование настойки из трав:

Ограничение на использование глицерина:

Все переменные в данной задаче неотрицательны:

Составим целевую функцию:

Таким образом, математическая модель имеет вид:

.2 Пример 2

Мебельная фабрика изготавливает диваны двух видов –
раскладные и угловые. Для производства диванов используют два вида сырья –
дерево и ДСП. Максимально возможные запасы сырья в сутки составляют 900 и 730
единиц соответственно. Расход сырья на один раскладной диван и один угловой диван
приведен в таблице 8.7.

Таблица 7.2

аналитический оптимизация симплекс управленческий

Кроме того, известно, что минимальный спрос на раскладные диваны равен 20
ед. в сутки.

Прибыль от продажи одного дивана равна: 6 д. е. – для угловых диванов и 4
д.е. для раскладных.

Какое количество диванов каждого вида должна производить фабрика, чтобы
прибыль от продажи диванов был максимальным?

Решение:

Составим математическую модель задачи. Введем ограничения.

Ограничение на использование дерева при производстве диванов:

Ограничение на использование ДСП при производстве диванов:

Ограничение на спрос раскладных диванов:

Все переменные в данной задаче неотрицательны и целочисленные:

Составим целевую функцию:

Таким образом, математическая модель имеет вид:

Смысл этих ограничений:

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

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

Задачи 2 и 3 включаются в список решаемых задач.

Получено оптимальное целочисленное решение (отсутствуют отрицательные
элементы в строке целевой функции):

Заключение

В результате проведения всех вычислительных операций мы определили
оптимальное решение, производство по технологическим процессам оказалось
следующим: 56 дней по ТП1, 2 дня по ТП2 и 12,8 дней по ТП3. При этом рабочая
сила и сырье будут использованы полностью. 152 тыс. кВт/ч будут не израсходованы.
Выпуск изделий составит 23060 штук.

В рассматриваемой задаче имеются следующие недостатки: значительная часть
электроэнергии осталась неизрасходованной. Это можно устранить следующим
способом: увеличим запас рабочей силы на 58 млн. человеко-ч/день (исходный
запас составлял 1200 млн. человеко-ч/день).

Список литературы

1.      Дегтярев
Ю.И. Исследование операций. – М.: Высшая школа, 1979. – 320 с.

.        Смородинский
С.С. Методы и алгоритмы для решения оптимизационных задач линейного
программирования: Учебно-методическое пособие по курсу “Системный анализ и
исследование операций” для студентов специальности
“Автоматизированные системы обработки информации и управления”, Ч. 1.
/ С.С. Смородинский, Н.В. Батин – Мн.: БГУИР, 1995. – 91 с.

.        Смородинский
С.С., Батин Н.В. Оптимизация решений на основе методов и моделей
математического программирования: Учебное пособие по курсу “Системный
анализ и исследование операций” – Мн.: БГУИР, 2003. – 136 с.: ил.

.        Таха
Х. Введение в исследование операций. М., С.-П., Киев: “Вильямс”,
2001. – 910 с.

Приложение А

(справочное)

Протокол решения задачи оптимизации с использованием пакета SIMPLEX

Рисунок А.1 – Первая симплекс-таблица

Рисунок А.2 – Первое допустимое решение

Рисунок А.3 – Третья симплекс-таблица

Рисунок А.4 – Оптимальное решение

Рисунок А.4 – Результат

Приложение Б

(справочное)

Рабочий лист MS EXCEL с результатами оптимизации на основе базовой
аналитической модели

Рисунок Б.1 – Рабочий лист Excel

Рисунок Б.2 – Надстройка “Поиск решения”

Приложение В

Рабочий лист MS EXCEL с результатами оптимизации на основе
модифицированной аналитической модели

Рисунок В.1 – Рабочий лист Excel

Рисунок В.2 – Надстройка “Поиск решения”

Приложение Г

Протокол решения перспективной оптимизационной управленческой задачи с
использованием пакета SIMPLEX-M

Задача 1.

Рисунок Г.1 – Оптимальное решение

Рабочий лист MS EXCEL с результатами оптимизации на основе перспективной
оптимизационной управленческой задачи

Рисунок Г.2 – Рабочий лист Excel

Рисунок Г.3 – Надстройка “Поиск решения”

Протокол решения перспективной оптимизационной управленческой задачи с
использованием пакета SIMPLEX-M

Задача 2.

Рисунок Г.4 – Оптимальное решение

Рабочий лист MS EXCEL с результатами оптимизации на основе перспективной
оптимизационной управленческой задачи

Рисунок Г.5 – Рабочий лист Excel

Рисунок Г.6 – Надстройка “Поиск решения”