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

 

Введение

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

 

 

 

Методы математического  программирования для решения оптимизационных задач.

 

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

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

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

• управляемых переменных;
• неуправляемых переменных;
• формы функции (вида зависимости между ними).

Область допустимых решений – это область, в пределах которой осуществляется выбор решений. В экономических задачах она  ограничена наличными ресурсами, условиями, которые записываются в виде системы  ограничений, состоящей из уравнений  и неравенств. [2]

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

а) линейные (I и II) и нелинейные (III и IV) (рис.3.1.);

Рис.1 Линейные и нелинейные ограничения

 

б) детерминированные (А,В) и стохастические (группы кривых ) (рис.3.2.).

Рис.2 Детерминированные и стохастические ограничения

 

Стохастические  ограничения являются возможными, вероятностные, случайными.

Оптимизационные задачи решаются методами математического  программирования, которые подразделяются на:

• линейное программирование;
• нелинейное программирование;
• динамическое программирование;
• целочисленное программирование;
• выпуклое программирование;
• исследование операций;
• геометрическое программирование и др.

Главная задача математического программирования – это нахождение экстремума функций  при ограничениях в форме уравнений  и неравенств.

В качестве примера  рассмотрим подробно оптимизационные задачи, решаемые методами линейного программирования. [1]

Оптимизационные задачи с линейной зависимостью между  переменными

Пусть:

- количество ресурса вида i (i=1,2,...,m);

- норма расхода i – го ресурса на единицу j – го вида продукции;

- количество продукции вида  j (j=1,2,...,n);

- прибыль (доход) от единицы  этой продукции (в задачах на  минимум – себестоимость продукции).

Тогда оптимизационные  задачи линейного программирования (ЛП) в общем виде может быть сформулирована и записана следующим образом:

Найти переменные , при которых целевая функция

,

была бы максимальной (минимальной), не нарушая следующих  ограничений:

,

,

.

Вcе три случая можно привести к так называемой канонической форме, введя дополнительные переменные:

,

k – количество дополнительных переменных, и условие неотрицательности искомых переменных:

.

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

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

Пусть необходимо найти оптимальный  план производства двух видов продукции (x₁ и x₂), т.е. такой план, при котором целевая функция (общая прибыль) была бы максимальной, а имеющиеся ресурсы использовались бы наилучшим образом. Условия задачи приведены в таблице:

 

Вид продукции	Норма расхода ресурса на единицу  продукции			Прибыль на единицу изделия
	А	В	С
1	2	0,1	3,5	4
2	1	0,5	1	5
Объем   ресурса	12	4	18

 

Оптимизационная модель задачи запишется следующим  образом:

а) целевая  функция:

б) ограничения:

2х₁ + х₂ 12          (ограничение по ресурсу А);

0,1х₁ + 0,5х₂ 4   (ограничение по ресурсу B);

3,5х₁ + х₂ 18      (ограничение по ресурсу C).

в) условие  неотрицательности переменных:

Данную и  подобные оптимизационные модели можно  продемонстрировать графически (Рис.3.3.).

Преобразуем нашу систему ограничений, найдя  в каждом из уравнений x₂ , и отложим их на графике. Любая точка на данном графике с координатами x₁ и x₂ представляет вариант искомого плана. Однако ограничение по ресурсу А сужает область допустимых решений. Ими могут быть все точки, ограниченные осями координат и прямой АА, т.к. не может быть израсходовано ресурса А больше, чем его на предприятии имеется. Если точки находятся на самой прямой, то ресурс используется полностью.

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

Рис. 3 Геометрическая интерпретация оптимизационной  задачи линейного программирования

Однако нам  необходимо найти такую точку, в  которой достигался бы максимум целевой  функции. Для этого построим произвольную прямую 4Х₁+5Х₂=20, как Х₂=4-4/5Х₁ (число 20 произвольное). Обозначим эту линию РР. В каждой точке этой линии прибыль одинакова. Перемещая эту линию параллельно ее исходному положению, найдем точку, которая удалена от начала координат в наибольшей мере, однако, не выходит за пределы области допустимых решений. Это точка М₀, которая лежит на вершине многоугольника. Координаты этой точки ( ) и будут искомым оптимальным планом. [4]

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

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

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

Симплекс – это выпуклый многоугольник в n-мерном пространстве с n+1 вершинами, не лежащими в одной гиперплоскости (гиперплоскость делит пространство на два полупространства).

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

Доказано, что  если оптимальное решение существует, то оно обязательно будет найдено  через конечное число итераций (шагов), кроме случаев «зацикливания».

Алгоритм  симплексного метода состоит из ряда этапов.

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

а) правые части  условий (свободные члены b_i) являются величинами неотрицательными;

б) сами условия  являются равенствами;

в) матрица  условий содержит полную единичную  подматрицу.

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

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

В оптимальном  решении задачи все искусственные  переменные (ИП) должны быть равными  нулю. Для этого вводят искусственные  переменные в целевую функцию  задачи с большими отрицательными коэффициентами (-М) при решении задачи на max, и  с большими положительными коэффициентами (+М), когда задача решается на min. В этом случае даже незначительное ненулевое значение искусственной переменной будет резко уменьшать (увеличивать) значение целевой функции. Обычно М в 1000 раз должно быть больше, чем значения коэффициентов при основных переменных.

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

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

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

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

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

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

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

Заключение

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