Методы и модели в экономике (стр. 1 )

К. А.ДЖАФАРОВ

Методы и модели в экономике

Глава 1. Элементы математического программирования

Под принятием решений понимается сложный процесс, в котором можно выделить 4 основных этапа.

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

Построение модели рассмотренной ситуации состоит из:

1)  выделения наиболее важных факторов,

2)  установления закономерностей, которым эти факторы подчиняются.

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

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

3.  Исследование влияния переменной на значение целевой функции (анализ модели на чувствительность )

4.  Экспертная проверка результатов

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

Возможны 2 случая: 1 - результаты сопоставления неудовлетворительны, отсюда, переходят ко второму циклу процесса, т. е. уточняется входная информация о моделируемом объекте и, в случае необходимости, уточняется постановка задачи, 2 - результаты сопоставления удовлетворительны Þ модель принимается.

Постановка основной задачи математического программирования

Пусть задано множество допустимых решений X и функция , определенная на X и называемая целевой функцией, где

Эта система равенств и неравенств называется в задачах МП ограничением.

Общая задача МП заключается в минимизации (максимизации) скалярной функции от векторного аргумента xÎX, т. е. на допустимом множестве X.

Основные разделы МП:

1.  Линейное программирование

2.  Целочисленное программирование

3.  Динамическое программирование

4.  Нелинейное программирование

Для начала займемся линейным программированием.

§1 Различные формы задач ЛП

1. Общая задача ЛП

(1)

при ограничениях

(3)

(2)

Решения, удовлетворяющее ограничениям (2), называются возможными решениями задачи. Решения, удовлетворяющее ограничениям (2) и условиям (3), называются допустимыми решениями задачи. Решения, удовлетворяющее условиям (1),(2),(3), называются оптимальными решениями задачи.

2. Задача с ограничениями неравенствами

,

при ограничениях

3. Стандартная форма задачи ЛП (каноническая )

,

при ограничениях

Любую модель можно привести к стандартной форме. Рассмотрим ограничения:

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

Пример

Правую часть равенства всегда можно сделать неотрицательной, умножая обе части на (-1)

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

Эти изменения производятся везде, где участвует переменная.

Пример:

Целевая функция.- Перейдя к противоположному знаку можно перейти к противоположной задаче. (от max к min, и наоборот):

,

Пример:

Нужно свести к стандартной форме:

1.  Рассмотрим 2-ое ограничение

3)

2. 

Тогда:

при ограничения:

§2 Некоторые теоремы о решении задач ЛП

Рассмотрим общую задачу ЛП (1-3). Допустим, что - решение.

Определение. Частное решение системы (2), соответствующие нулевым, не базисным переменным, называется базисным решением.

Базисное неотрицательное решение ((2)+(3)) называется опорным (начальным).

Без доказательств перечислим некоторые теоремы.

Теорема. Область допустимых решений системы (2) есть выпуклое множество.

Теорема. (о соответствии опорных решений и угловых точек)

Допустимое решение x является угловой точкой ОДР тогда и только тогда, когда оно опорное.

Система (2) может иметь не более чем n-r опорных решений, где n - число неизвестных, r – ранг системы (2)

Теорема. (о представлении ограниченной области допустимых решений)

Если система (2),(3) имеет ограниченную область ДР, то любое ее допустимое решение представимо в виде выпуклой линейной комбинации всех ее опорных решений. Т. е., если - опорные решения, то любое допустиое решение

Теорема. (о представлении неограниченной ОДР)

Если система (2),(3) имеет неограниченную ОДР, то любое допустимое решение представимо в виде:

где Rj – направляющие векторы неограниченных ребер области решений.

Теорема. (о существовании опорного решения)

Если система (2),(3) имеет хотя бы одно допустимое решение, то среди этих решений имеется хотя бы одно опорное решение.

Теорема. (о существовании опорного решения в ограниченной области)

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

Теорема. (об оптимальном решении в неограниченной области)

Если ОДР стандартной задачи ЛП неограниченна, то оптимальное решение существует и совпадает с хотя бы одним опорным, если целевая функция j(x) ограниченна сверху в задаче максимизации, и снизу – в задаче минимизации.

Теорема. (фундаментальная в ЛП)

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

Теорема. (об альтернативном оптимальном решении)

Если целевая функция j(x) достигает минимума (максимума) в нескольких опорных решениях , то любое оптимальное решение является выпуклой линейной комбинацией альтернативных опорных решений, т. е.

Фундаментальная теорема предлагает следующий алгоритм решения задач ЛП:

1.  Найти все опорные решения

2.  Вычислить значение целевой функции в опорных решениях

3.  Выбрать наименьшее или наибольшее из них

§3. Графическое решение задач ЛП

Дадим графическое применение алгоритма на примере.

Пример. Небольшая фирма выпускает два вида красок для внутренних и наружных работ (I и E). Продукция обоих видов поступает в оптовую продажу. Для производства красок используется два продукта А и В.

Максимально возможные суточные запасы составляют 6 и 8 т. продуктов А и В соответственно. Расходы А и В на производство 1 тонны соответствующих красок приведены в таблице:

Исходный продукт	Расходы продукта в т. на одну тонну красок	Максимальный запас. в т.
I	E
A	2	1	6
B	1	2	8

Изучение рынка сбыта показало, что спрос на краску I никогда не превышает спроса на краску Е более чем на 1 тонну. Кроме того, установлено, что спрос на краску I никогда не превышает 2 т. в сутки. Оптовые цены 1 тонны краски I - $ 2000, E - $ 3000

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

Поставим математическую задачу.

Определим переменные :

x1 – суточный объем производства краски I, в т.

x2 - суточный объем производства краски E, в т.

Целевая функция

j(x) = 2x1 + 3x2 (в тыс $) max

Ограничения:

Получили задачу ЛП о максимизации целевой функции j(x) при указанных ограничениях.

Построим ОДР (область ОАВСDE на рис.).

Построим линию уровня целевой функции

Пусть с=6

Двигаем j(х) в сторону ОДР. Возможны 3 ситуации:

1.  Параллельный сдвиг приведет в положении, когда у прямой окажется только одна общая точка с ОДР. Отсюда, единственное оптимальное решение.

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

3.  В направлении возрастания целевой функции ОДР неограниченна. В этом случае целевая функция может принимать любое значение, отсюда, задача на "max" не имеет решений.

В нашем случае – одна точка D. Следовательно, задача имеет единственное решение. Координаты D найдем как точку пересечения 1 и 2 прямых.

Оптимальный план: производить 4/3 т. краски I, 10/3 т. краски E. И при этом максимальный доход будет:

тыс. долларов

§4. Алгебраический метод решения задач ЛП (Симплекс метод)

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

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

Пример.

при ограничениях

Исходной точкой (см. рисунок) в методе станет точка О. Решение в этой точке называется начальным. От точки О можно переходить к точке А или Е. При x2 коэффициент больше, чем при x1 , Поэтому выгодно увеличивать x2, т. е. двигаться к Е.

Выбор каждой последующей угловой точки определяется следующими правилами:

1.  Каждая последующая угловая точка должна быть смежной с предыдущей

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

Сначала приведем к стандартному виду:

У нас 6 неизвестных, 4 уравнения, 6-4=2, приравниваем двух переменных к нулю и получаем базисное решение. В общем случае, если число неизвестных n , уравнений m, то n-m переменным придаем нулевые значения, и из ограничений получаем базисное решение. Если базисное решение удовлетворяет условию неотрицательности правых частей, то решение будет допустимым. Переменные, имеющие нулевые значения, называются не базисными. Остальные – базисные.

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

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

Исключаемая переменная – та базисная, которая на следующей итерации подлежит исключению из базиса.

Вычислительные процедуры "Симплекс-метода".

Состоит из следующих шагов:

1.  Определение начального допустимого базисного решения. (Путем приравнивания к нулю n-m переменных)

В нашем примере: x1=x2=0.

Это базисное решение соответствует точке О

x1=x2=0. – небазисные, - базисные

2.  Из числа текущих небазисных выбирается включаемая в новый базис переменная. Если такой переменной нет, то вычисления прекращаются. Текущее базисное решение – оптимальное.

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

Условие оптимальности:

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

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

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

3.Из числа переменных текущего базиса выбирается из условия допустимости исключаемая переменная, которая должна принять нулевое значение при введение в состав небазисных. Условие допустимости: в задачах max и min в качестве исключаемой выбирается та базисная переменная, для которой отношение постоянной правой части соответствующего ограничения к положительному коэффициенту при включаемой переменной минимально (в том же ограничении). В случае равенства выбор делается произвольно. Осуществляется поиск нового базисного решения методом Гаусса-Жордана. Этот процесс изменения базиса включает вычислительные процедуры двух типов.

Тип 1. (Формирование нового ведущего уравнения)

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

Тип 2. (Формирование остальных уравнений)

Продемонстрируем на нашем примере.

Составим начальную симплекс-таблицу.

Базисные переменные	x1	x2	s1	s2	s3	s4	Решение
s1	2	1	1	0	0	0	6	(1)
s2	1	2	0	1	0	0	8	(2)
s3	1	-1	0	0	1	0	1	(3)
s4	1	0	0	0	0	1	2	(4)
j	-2	-3	0	0	0	0	0

Найдем включаемую переменную.

Ведущий столбец – x2 (включаемая).

, т. е. s2 исключаемая переменная

Тип

Тип 2.(1)

(3)

(4)– такое же, т. к коэффициент = 0

(j)

Базисные переменные	x1	x2	s1	s2	s3	s4	Решение
s1	3/2	0	1	-1/2	0	0	2	(1)
x2	1/2	1	0	1/2	0	0	4	(2)
s3	3/2	0	0	1/2	1	0	5	(3)
s4	1	0	0	0	0	1	2	(4)
j	-1/2	0	0	3/2	0	0	12	(j)

Включаемая в базис переменная - x1

исключаемая s1

Аналогичным путем получаем следующую таблицу.

Базисные переменные	x1	x2	s1	s2	s3	s4	Решение
x1	1	0	2/3	-1/3	0	0	4/3	(1)
x2	0	1	-1/3	2/3	0	0	10/3	(2)
s3	0	0	-1	1	1	0	3	(3)
s4	0	0	-2/3	1/3	0	1	2/3	(4)
j	0	0	1/3	4/3	0	0	38/3	(j)

Коэффициенты при небазисных – неотрицательные.