Математические модели в экономическом анализе

Пример 3.1

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

Условия спроса на рынке ограничивают число изделий первого вида 2000 единицами, второго – 3000 и третьего – 5000 единицами.

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

Таблица 3.1

Тип ресурсов	Вид изделий			Всего ресурсов
Тип ресурсов	1	2	3	Всего ресурсов
1 2 3 4	500 1000 150 100	300 200 300 200	1000 100 200 400	25000000 30000000 20000000 40000000
Прибыль	20	40	50

Как организовать производство, чтобы:

1) обеспечить заказчиков;

2) не допустить затоваривания;

3) получить максимальную прибыль?

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

Выполним последовательно этапы построения математической модели, сформулированные в пункте 3.

1) Цель – получение максимальной прибыли.

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

3) Управляющие переменные:

x ₁ – число изделий первого вида;

x ₂ – число изделий второго вида;

x ₃ – число изделий третьего вида;

4) Ограничения: обеспечить заказчиков, не превысить, запас ресурсов, не допустить затоваривания рынка.

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

(3.5)

Первые три неравенства в системе (3.5) соответствуют спросу заказчиков. Неравенства с четвертого по шестое формализуют спрос на рынке. Последние четыре неравенства соответствуют ограничениям по ресурсам.

5) Целевая функция или критерий эффективности задачи имеет вид

Р = 20х₁ + 40 х₂ + 50 х₃ max. (3.6)

В формуле буквой Р обозначена прибыль. Ее надо максимизировать. Каждое слагаемое определяет прибыль от производства изделий каждого вида соответственно в количествах х₁, х₂, х₃.

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

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

5, Общая постановка задачи линейного программирования (ЗЛП). Примеры ЗЛП

Линейное программирование – направление математики, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием оптимальности. Несколько слов о самом термине линейное программирование. Он требует правильного понимания. В данном случае программирование - это, конечно, не составление программ для ЭВМ. Программирование здесь должно интерпретироваться как планирование, формирование планов, разработка программы действий. К математическим задачам линейного программирования относят исследования конкретных производственно-хозяйственных ситуаций, которые в том или ином виде интерпретируются как задачи об оптимальном использовании ограниченных ресурсов. Круг задач, решаемых при помощи методов линейного программирования достаточно широк. Это, например:

· задача об оптимальном использовании ресурсов при производственном планировании;

· задача о смесях (планирование состава продукции);

· задача о нахождении оптимальной комбинации различных видов продукции для хранения на складах (управление товарно-материальными запасами или " задача о рюкзаке" );

· транспортные задачи (анализ размещения предприятия, перемещение грузов). Линейное программирование – наиболее разработанный и широко применяемый раздел математического программирования (кроме того, сюда относят: целочисленное, динамическое, нелинейное, параметрическое программирование). Это объясняется следующим:

· математические модели большого числа экономических задач линейны относительно искомых переменных;

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

· многие задачи линейного программирования, будучи решенными, нашли широкое применение;

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

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

= c₁x₁ + c₂x₂ +... + c_nx_n → max(min);

(2.1)

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

a₁₁x₁ + a₁₂x₂ +... + a_1nx_n {≤ = ≥ } b₁, a₂₁x₁ + a₂₂x₂ +... + a_2nx_n {≤ = ≥ } b₂, ... a_m1x₁ + a_m2x₂ +... + a_mnx_n {≤ = ≥ } b_m;

(2.2)

· требование неотрицательности:

x_j ≥ 0,

(2.3)

· При этом a_ij, b_i, c_j ( ) - заданные постоянные величины. Задача состоит в нахождении оптимального значения функции (2.1) при соблюдении ограничений (2.2) и (2.3). Систему ограничений (2.2) называют функциональными ограничениями задачи, а ограничения (2.3) - прямыми. Вектор , удовлетворяющий ограничениям (2.2) и (2.3), называется допустимым решением (планом) задачи линейного программирования. План , при котором функция (2.1) достигает своего максимального (минимального) значения, называется оптимальным.

5. Формы записи ЗЛП

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

(10.10)

при условиях

(10.11)

(10.12)

. (10.13)

Функция (10.10) называется целевой функцией (или линейной формой ) задачи (10.10) – (10.13), а условия (10.11) – (10.13) – ограничениями данной задачи.

2. Стандартной (или симметричной ) задачей линейного программирования называется задача, которая состоит в определении максимального для «≤ » (минимального для «≥ ») значения функции (10.10) при выполнении условий (10.11) и (10.13), где k = m, s = n.

3. Канонической (или основной ) задачей линейного программирования называется задача, которая состоит в определении максимального (минимального) значения функции (10.10) при выполнении условий (10.12) и (10.13), где k = 0, s = n.

Каноническая (основная) форма	Стандартная (симметричная) форма	Общая форма
1) ограничения
Уравнения .	Неравенства .	Уравнения и неравенств .
2) условия неотрицательности
Все переменные ,	Все переменные ,	Часть переменных , , .
3) цель задачи
max F(x) или minF(x)	max F(x) [min F(x)]	max F(x) или min F(x)

Замечание.

max F(x) = – min[– F(x)], min F(x) = – max[– F(x)].

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

Запишем основную задачу линейного программирования в векторной форме. Найти максимум (минимум) функции

при условиях

, (10.14)

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

План Х называется опорным планом основной задачи линейного программирования, если система векторов , входящих в разложение (10.14) с положительными коэффициентами , линейно независима.

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

План , при котором целевая функция принимает свое максимальное (минимальное) значение, называется оптимальным.

7. На этом шаге мы рассмотрим представление задачи линейного программирования в канонической форме.

Если математическая модель задачи линейного программирования имеет вид:

то говорят, что задача представлена в канонической форме.

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

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

если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;
если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;
если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;
если некоторая переменная x_j не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными:
x₃ = x₃⁺ - x₃^-, где x₃⁺, x₃^- ≥ 0.

Пример 3.1

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

Прибыль от реализации одной единицы товара первого вида составляет 2 усл. ед., второго вида – 3 усл. ед.

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

Таблица 3.2

Ресурсы	Норма затрат ресурсов на товары		Общее количество ресурсов
	1 -го вида	2-го вида
1 2 3 4	2 1 4 0	2 2 0 4	12 8 16 12

Решение

Это задача составления плана реализации товара при n =2, m=4.

Математическая модель имеет вид

(3.16)

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

Графическое решение.

Построим в плоскости X ₁ OX ₂ область допустимых решений. Каждое неравенство системы (3.3.2) определяет в плоскости X ₁ OX ₂ полуплоскость, лежащую выше или ниже прямой, определяемой соответствующим уравнением. Построим прямые (см. рис. 3.1)

Рассмотрим точку с координатами х₁ =0; х₂ =0. Подставив их в первое неравенство, получаем 0 £ 12 – верно, следовательно, искомая полуплоскость лежит ниже прямой 2x₁ +2x₂ = 12; остальные полуплоскости находятся аналогичным образом.

Область OABCD – область допустимых решений задачи.

Для нахождения максимального значения Р проверим граничные. Точки из области решений.

Построим две линии уровня (рис. 3.1):

2x₁ + 3x₂ = 6;

2x₁ +3х₂=13.

Функция Р возрастает в направлении вектора-нормали = (2, 3) следовательно, минимум находится в точке (0.0). Максимум определяем, передвигая нашу линию уровня в направлении вектора параллельно самой себе до тех пор, пока хотя бы одна ее точка будет принадлежать области допустимых решений.

В данном случае это точка: х₁ = 4, х₂ = 2;

при этом P=2*4+3*2=14.

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

Рис. 3.1. Графический метод решения задачи ЛП

Изложенный выше графический метод применим для решения задач линейного программирования следующего вида:

(3.17)

(3.18)

Алгоритм решения ЗЛП графическим методом.

1) Записывают уравнения прямых, соответствующих ограничениям (3.3.4), и строят их на плоскости x ₁ ox _3.

2) Определяют области, в которых выполняются ограничения задачи. Для этого выбирают произвольную точку на плоскости х₁ох₂ и подставляют ее координаты в первую часть одного из неравенств. Если неравенство верно, то искомая полуплоскость находится с той же стороны от прямой, что и точка; в противном случае искомая полуплоскость лежит с противоположной стороны от прямой. Эти действия последовательно выполняются для всех неравенств (3.3.4).

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

4) Определяют направление возрастания (убывания) целевой функции f. Это можно сделать двумя способами. Можно построить вектор-нормаль , его направление показывает направление возрастания функции f, и противоположном направлении функция убывает. Можно просто построить две линии уровня функции f = K₁; f = K₂; (K₁, K₂ – произвольные константы, K₁ K₂), и по их расположению определить направление возрастания (убывания) функции.

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

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

Возможны следующие варианты областей допустимых решений (рис. 3.2):

Рис. 3.2. Варианты областей. а – область допустимых решений
– замкнутое множество (многоугольник); б – область допустимых решений – открытое множество; в – область допустимых решений – пустое множество (система ограничений (3.18) несовместна);
г – область допустимых решений состоит из единственной точки А

На рис. 3.2 показаны варианты пересечения линии уровня целевой функции с областью допустимых решений. Может быть единственное решение – точка В, бесконечно много решений – отрезок CD (рис. 3.2, а), максимальным (минимальным) значением целевой функции может быть бесконечность (рис. 3.2, б). Область ограничений несовместимо (допустимых решений нет, рис. 3.2, в). И может быть только одна допустимая точка (рис. 3.2, г)

Алгоритм симплекс-метода

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

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

Второй столбец - коэффициенты целевой функции, соответствующие векторам, входящим в базис.

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

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

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

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

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

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

Этап 1

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

Если все эти разности

то план является оптимальным

Этап 2

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

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

Этап 3

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

где просматриваются лишь те дроби

для которых

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

помечать ее символом

Этап 4

После того, как определены направляющие столбец и строка, начинает заполняться новая симплекс-таблица, в которой на месте направляющей

строки будет стоять вектор

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

пишется величина

, то есть

Остальные элементы этой строки заполняются величинами

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

Написанные выше формулы для пересчета элементов направляющей строки можно записать следующим правилом:

Этап 5

Далее начинается пересчет всех остальных строк таблицы, включая и дополнительную нижнюю строку по формулам: для компонент плана

;

для координат разложения по базису

;

для дополнительной строки

Обратите внимание на то, что все эти формулы по сути дела строятся по одному правилу

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

1 на месте бывшего элемента

Далее итерации продолжаются.

Пример

Решить задачу линейного программирования

В данном случае вектор равен (0, 1, -3, 0, 2, 0), а в векторной форме ограничения могут быть записаны в виде

Заполним исходную симплекс-таблицу, взяв в качестве исходного базиса

вектора

что удобно из-за их вида.

Исходная симплекс-таблица

Ба-		План	0	1	-3	0	2	0
зис
	0	7	1	3	-1	0	2	0
	0	12	0	-2	4	1	0	0
	0	10	0	-4	3	0	8	1
		0	0	-1	3	0	-2	0

Обратите внимание на то, что из-за специфического вида векторов в столбец " план" просто переписался вектор , а в качестве координат векторов в нашем базисе стоят просто сами векторы.

Ну, а величины приходится считать:

Первая итерация

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

В этом направляющем столбце есть два положительных числа - 4 и 3. Поэтому нужно рассмотреть два частных

и выбрать из них наименьшее. Так как

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

Ба-		План	0	1	-3	0	2	0
зис
	0	10	1		0		2	0
	-3	3	0		1		0	0
	0	1	0		0		8	1
		-9	0		0		-2	0

Заполним теперь новую симплекс-таблицу, следуя сформулированным выше правилам.

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

Вторая итерация

Просматривая дополнительную строку мы вновь видим в ней всего один положительный элемент это 1/2, стоящая в столбце вектора . Следовательно, этот вектор надо ввести в базис и этот столбец будет направляющим.

В столбце, соответствующем вектору , всего один положительный элемент это 5/2, которая стоит в первой строке. Поэтому первая строка будет

направляющей и вектор

должен быть выведен из базиса.

Ба-		План	0	1	-3	0	2	0
зис
	1	4		1	0			0
	-3	5		0	1			0
	0		1	0	0		10	1
		-11		0	0			0

Запишем новую симплекс-таблицу, следуя сформулированным выше правилам.

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

Итак, оптимальный план имеет вид

то есть , а все остальные Ему соответствует значение целевой функции, равное -11.

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

Назначение метода

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

Идея симплекс-метода заключается в следующем. Сначала нужно найти некоторую (начальную) вершину многогранника допустимых решений (начальное допустимое базисное решение). Затем нужно проверить это решение на оптимальность. Если оно оптимально, то решение найдено; если нет, то перейти к другой вершине многогранника и вновь проверить на оптимальность. Ввиду конечности вершин многогранника (следствие конечности ограничений задачи ЛП) за конечное число " шагов" мы найдем искомую точку минимума или максимума. Надо заметить, что при переходе от одной вершины к другой значение целевой функции убывает (в задаче на минимум) или возрастает (в задаче на максимум).

Симплексные таблицы

Приведя ЗЛП к предпочтительному виду, её заносят в симплексную таблицу.

max Z = 18x1 + 20x2 + 32x3

18x1 + 15x2 +12x3 + x4 = 720;

6x1 + 4x2 + 8x3 + x5 =384;

5x1 + 3x2 + 12x3 + x6 = 360;

Базисные переменные	Коэффициенты	A0	X1	X2	X3	X4	X5	X6
Базисные переменные	Коэффициенты	A0	18	20	32	0	0	0
X4	0	720	18	15	12	1	0	0
X5	0	384	6	4	8	0	1	0
X6	0	360	5	3	12	0	0	1
Z_j - C_j		0	-18	-20	-32	0	0	0

∆ ₀ = 0*720 + 0* 384 + 0* 360 = 0; ∆ ₀ = Z(x₀)

∆ _I = ∑ коэфф. * a_ij - c_j;

∆ ₁ = 0*18 + 0*6+ 0*5 – 18= -18

Правило прямоугольника

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

Обозначения.

Всюду ниже R — множество вещественных, N — натуральных, а C — комплексных чисел. С самого начала мы будем использовать векторные обозначения. Всегда через R ^m обозначается m-мерное вещественное линейное пространство. При этом мы всегда считаем, что в R ^m фиксирован базис и отождествляем R ^m с арифметическим m-мерным пространством (пространством упорядоченных наборов m вещественных чисел). Буква Q будет обозначать нуль пространства R ^m. Индекс внизу всегда обозначает координату вектора, например, x_i — это i-ая координата вектора x. Последовательности мы обычно будем обозначать индексом вверху: {xⁿ}.

Через (·, ·) обозначается каноническое скалярное произведение в R^m: (x, y) = å ^m _i₌₁x_iy_i. Если не оговорено противное,, порожденную скалярным произведением: || · || =(å ^m _i₌₁x_i²)^1/2.

Обозначение B(x₀, r) закреплено для шара в пространстве R ^m с центром в x₀ радиуса r: B(x₀, r) = {x Î R ^m: ||x - x₀|| £ r}.

Если A = {a_ij}ⁿ^,^m _i_{=1, j=1} —n× m-матрица, то через A также обозначается и линейный оператор из R ⁿ в R ^m, задаваемый этой матрицей.

Для двух векторов x, y Î R ^m мы будем писать x £ y, если x_i £ y_i при всех i = 1, ..., m; здесь x_i и y_i — i-е координаты векторов x и y, соответственно.

Мы будем различать обозначение f: X ® Y отображения, действующего из множества X во множество Y, и обозначение f: x ® y (или x ® f(x)) отображения, переводящего точку x в точку f(x), а также обозначение f отображения и обозначение f(x) значения отображения f в точке x.

Метод множителей Лангранжа

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

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

Если m < n, то можно из уравнений связи найти зависимость m переменных от n - m остальных переменных, т.е.

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

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

т.е. функцию m + n переменных, в которую ограничения, накладываемые системой функций входят как составная часть.

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

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

(1)

При этом новых независимых определяются из условия

(2)

Объединение систем (6.1.1) и (6.1.2) можно получить

(3)

Таким образом, задача в форме (3) сводится к задаче: найти

(4)

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

· Основной метод решения задачи об оптимизации качества кодирования аудио и видео информации при заданном среднем битрейте (оптимизация искажений — англ. Rate-Distortion optimization).

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

Метод Гомори. Нахождение решения задачи целочисленного программирования методом Гомори начинают с определения симплексным методом оптимального плана задачи (78) – (80) без учета целочисленности переменных. После того как этот план найден, просматривают его компоненты. Если среди компонент нет дробных чисел, то найденный план является оптимальным планом задачи целочисленного программирования (78) – (81). Если же в оптимальном плане задачи (78) – (80) переменная принимает дробное значение, то к системе уравнений (79) добавляют неравенство

(82)

и находят решение задачи (78) – (80), (82).

В неравенстве (82) и – преобразованные исходные величины и значения которых взяты из последней симплекс–таблицы, а и – дробные части чисел (под дробной частью некоторого числа а понимается наименьшее неотрицательное число b такое, что разность между а и b есть целое). Если в оптимальном плане задачи (78) – (80) дробные значения принимают несколько переменных, то дополнительное неравенство (82) определяется наибольшей дробной частью.

Если в найденном плане задачи (78) – (80), (82) переменные принимают дробные значения, то снова добавляют одно дополнительное ограничение и процесс вычислений повторяют. Проводя конечное число итераций, либо получают оптимальный план задачи целочисленного программирования (78) – (81), либо устанавливают ее неразрешимость.

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

(83)

где определяются из следующих соотношений:

1) для , которые могут принимать нецелочисленные значения,

(84)

2) для , которые могут принимать только целочисленные значения,

(85)

Из изложенного выше следует, что процесс определения оптимального плана задачи целочисленного программирования методом Гомори включает следующие основные этапы:

1. Используя симплексный метод, находят решение задачи (78) – (80) без учета требования целочисленности переменных.

2. Составляют дополнительное ограничение для переменной, которая в оптимальном плане задачи (78) – (80) имеет максимальное дробное значение, а в оптимальном плане задачи (78) – (81) должна быть целочисленной.

3. Используя двойственный симплекс–метод, находят решение задачи, получающейся из задачи (78) – (80) в результате присоединения дополнительного ограничения.

4. В случае необходимости составляют еще одно дополнительное ограничение и продолжают итерационный процесс до получения оптимального плана задачи (78) – (81) или установления ее неразрешимости.

Основные понятия теории игр

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

Как утверждал Г.Лейбниц, "...и игры заслуживают изучения; и если какой-нибудь проницательный математик посвятит себя их изучению, то получит много важных результатов, ибо нигде человек не показывает столько изобретательности, как в игре ".

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

Остановимся на классификации игр.

Интересы участников игры (игроков) могут оказаться несовпадающими и даже противоположными. В последнем случае игра называетсяантагонистической.

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

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

Игры, в которых игроки осведомлены о состоянии своем и партнеров, а также о прошлом поведении участников игры, относятся к категории игр сполной информацией (типичные примеры - шахматы, " крестики-нолики" и т.п.). Большинство же игр протекает в условиях неполной информации, где сведения о состоянии партнеров исчерпываются лишь вероятностными характеристиками (домино, карточные игры, игры против " природы" ).

Антагонистическую игру, где выигрыш одного коллектива равен проигрышу другого, называют игрой с нулевой суммой.

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

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

Простейшими являются игры 2 лиц с нулевой суммой.

Пусть в такой игре игрок 1 имеет m выборов и игрок 2 - n выборов. Если игрок 1 делает свой i-й выбор, а игрок 2 - свой j-й выбор, то выигрыш игрока 1 (проигрыш игрока 2) равен Rij. Такая игра называется матричной и матрица R = [ R_ij / i=1..m, j=1..n ] называется матрицей выигрышей (пла-тежной матрицей).

При ведении игры игрок должен ориентироваться на оптимальную политику партнера и наказывать его за отступления от таковой.

Проведем рассуждения за игрока 1. Если Я воспользуюсь i-м выбором, мой противник для минимизации моего выигрыша сделает тот из своих выборов, который даст min R_ij. Соответственно, Я должен использовать тот выбор, который гарантирует мне выигрыш, не меньший

Противник, рассуждая аналогично, приходит к выводу о гарантированном проигрыше, не превышающем

Если в матрице выигрышей существует элемент R_kl = V₁ = V₂, то говорят о наличии оптимальной политики " в пространстве чистых стратегий" и оптимальными выборами для игроков соответственно являются выборы k и l. Пару (k, l) называют седловой точкой.

Пример 1. Пусть игра определяется матрицей

Седловые точки - (4, 1) и (4, 2). Цена игры = 6; оптимальный выбор для игрока 1 - четвертый, для игрока 2 равнозначны первый и второй (под ценой игры понимают гарантированный выигрыш-проигрыш при оптимальной политике обоих игроков).

Пример 2. Пусть игра определяется матрицей

Здесь равенство V₁ = V₂ не выполняется; оптимальной чистой стратегии для игроков нет.

При анализе игр часто прибегают к попыткам обнаружить доминирование между строками и столбцами. Так в примере 1 элементы четвертой строки больше элементов других строк: использование выбора 4 выгоднее других выборов при любой политике противника. Противник видит, что в такой ситуации использовать выборы 3 и 4 неразумно.

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

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

Если игрок 1 прибегает к своему выбору i с вероятностью P_i, а игрок 2 - к своему j-му выбору с вероятностью Q_j, то ожидаемый выигрыш игрока 1 (проигрыш игрока 2) равен

Основная теорема теории игр (теорема Джона фон Неймана) утверждает, что любая матричная игра с нулевой суммой всегда имеет седловую точку, т.е. существуют векторы P и Q такие, что

(V - цена игры).

Платежная матрица

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

В целом платежная матрица полезна, когда:

1. Имеется разумно ограниченное число альтернатив или вариантов стратегии для выбора между ними.

2. То, что может случиться, с полной определенностью не известно.

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

Платежная матрица. Нижняя и верхняя
цена игры.

Оглавление | Назад | Далее| Глоссарий понятий

Рассмотрим парную конечную игру. Пусть игрок А располагает m личными стратегиями, которые обозначим A₁, A₂, ..., A_m. Пусть у игрока В имеется n личных стратегий, обозначим их B₁, B₂, ..., B_m. Говорят, что игра имеет размерность m × n. В результате выбора игроками любой пары стратегий

A_i и B_j (i = 1, 2, ..., m; j = 1, 2, ..., n)

однозначно определяется исход игры, т.е. выигрыш a_ij игрока А (положительный или отрицательный) и проигрыш ( - a_ij ) игрока В. Предположим, что значения о, у известны для любой пары стратегий (A_i, B_j ). Матрица P = (a_ij ), i = 1, 2, ..., m; j = 1, 2, ..., n, элементами которой являются выигрыши, соответствующие стратегиям A_i и B_j, называется платежной матрицей или матрицей игры. Общий вид такой матрицы представлен в таблице 3.1.

Таблица 3.1

Строки этой таблицы соответствуют стратегиям игрока А, а столбцы — стратегиям игрока В. Составим платежную матрицу для следующей игры.

Седлова точка

Седловая точка в математическом анализе — такая точка из области определения функции, которая является стационарной для данной функции, однако не является её локальным экстремумом. В такой точке, если рассматривается функция двух переменных, образованная графиком функцииповерхность обычно напоминает по форме седло или горный перевал — выпуклая в одном направлении и вогнутая в другом. На карте высот седловая точка может быть в общем случае обнаружена в месте пересечения изолиний. Например, два холма, между которыми находится высокий перевал, образуют седловую точку в вершине этого перевала: на карте высот это будет выглядеть как центр «восьмерки», образованной соответствующими изолиниями. Проверить, является ли данная стационарная точка функции F(x, y) двух переменных седловой, можно, вычислив матрицу Гессе функции в этой точке: если гессиан будет неопределенной квадратичной формой, то данная точка — седловая. Например, составив матрицу Гессе функции в стационарной точке получим матрицу:

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

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

График y = x³ с седловой точкой в 0

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

Заключение

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

Математические модели в экономическом анализе

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

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

Самыми существенными моментами при постановке и решении экономических задачах в виде математической модели являются:

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

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

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

Можно выделить в экономическом анализе - анализ влияния производительности труда и численности работающих на объем произведенной продукции; анализ влияния величины прибыли основных производственных фондов и нормируемых оборотных средств на уровень рентабельности; анализ влияния заемных средств на маневренность и независимость предприятия и т. п..

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

В этом случае ставится обратная задача- так называемая задача обратного факторного анализа.

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

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

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

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

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

Задача о диете

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

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

Даме необходимо похудеть, за помощью обратилась к подруге.

Построение модели - рассмотрение этого этапа и является главной целью.

Подруга посоветовала перейти на рациональное питание, состоящее из двух продуктов P и Q.

Суточное питание этими продуктами должно давать не более 14 единиц жира (чтобы похудеть), но не менее 300 калорий. На упаковке продукта Р написано, что в одном килограмме этого продукта содержится 15 единиц жира и 150 калорий, а на упаковке с продуктом Q - 4 единицы жира и 200 калорий соответственно. При этом цена 1 килограмма продукта Р равна 15 руб., а 1 кг продукта Q - 25 руб.

Так как дама была стеснена в средствах, но ее интересовал вопрос: в какой пропорции нужно брать эти продукты для того, чтобы выдержать условия диеты и истратить как можно меньше денег?

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

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

Количество единиц жира, содержащегося в х кг продукта Р и в у кг продукта Q, равно 15х + 4 и по условию диеты не должно превосходить 14:

В свою очередь, количество калорий, содержащихся в х кг продукта Р и в у кг продукта Q, равно 150х + 200у и по условию диеты должно быть не меньше 300:

Теперь о стоимости z продуктов. Она равна

и в соответствии с высказанными пожеланиями должна быть минимальной.

Последнее записывается так:

Тем самым мы получили систему формул:

которую решим графическим способом.

Нас интересует только та ее часть, которая лежит над треугольником BDE. Вычисляя значения z во всех трех вершинах этого треугольника

и сравнивая полученные результаты, замечаем, что наименьшее значение (35) достигается в вершине Е. Таким образом,

и искомая пропорция - 2: 3.

4, 3.1. Постановка задачи линейного программирования (ЛП)

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

Максимизировать (минимизировать) функцию

(3.1)

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

где x_j, –управляющие переменные или решения задачи
(3.1)–(3.4); b_j, a_ij, – параметры, f – целевая функция или критерий эффективности задачи.

Функция (3.1) – линейная, ограничения (3.2)–(3.4) – линейные. Задача содержит п переменных и т ограничений.

Решить задачу линейного программирования – это значит найти значения управляющих переменных x_j, удовлетворяющих ограничениям (3.2)–(3.4), при которых целевая функция (3.1) принимает минимальное или максимальное значение.

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

В этой главе рассматривается общая линейная задача.

Приведем пример экономической задачи, сводящейся к линейной модели.

Пример 3.1

Таблица 3.1

Тип ресурсов	Вид изделий			Всего ресурсов
Тип ресурсов	1	2	3	Всего ресурсов
1 2 3 4	500 1000 150 100	300 200 300 200	1000 100 200 400	25000000 30000000 20000000 40000000
Прибыль	20	40	50

Как организовать производство, чтобы:

1) обеспечить заказчиков;

2) не допустить затоваривания;

3) получить максимальную прибыль?

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

Выполним последовательно этапы построения математической модели, сформулированные в пункте 3.

1) Цель – получение максимальной прибыли.

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

3) Управляющие переменные:

x ₁ – число изделий первого вида;

x ₂ – число изделий второго вида;

x ₃ – число изделий третьего вида;

4) Ограничения: обеспечить заказчиков, не превысить, запас ресурсов, не допустить затоваривания рынка.

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

(3.5)

5) Целевая функция или критерий эффективности задачи имеет вид

Р = 20х₁ + 40 х₂ + 50 х₃ max. (3.6)

5, Общая постановка задачи линейного программирования (ЗЛП). Примеры ЗЛП

· задача об оптимальном использовании ресурсов при производственном планировании;

· задача о смесях (планирование состава продукции);

· математические модели большого числа экономических задач линейны относительно искомых переменных;

· многие задачи линейного программирования, будучи решенными, нашли широкое применение;

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

= c₁x₁ + c₂x₂ +... + c_nx_n → max(min);

(2.1)

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

a₁₁x₁ + a₁₂x₂ +... + a_1nx_n {≤ = ≥ } b₁, a₂₁x₁ + a₂₂x₂ +... + a_2nx_n {≤ = ≥ } b₂, ... a_m1x₁ + a_m2x₂ +... + a_mnx_n {≤ = ≥ } b_m;

(2.2)

· требование неотрицательности:

x_j ≥ 0,

(2.3)

5. Формы записи ЗЛП

(10.10)

при условиях

(10.11)

(10.12)

. (10.13)

Каноническая (основная) форма	Стандартная (симметричная) форма	Общая форма
1) ограничения
Уравнения .	Неравенства .	Уравнения и неравенств .
2) условия неотрицательности
Все переменные ,	Все переменные ,	Часть переменных , , .
3) цель задачи
max F(x) или minF(x)	max F(x) [min F(x)]	max F(x) или min F(x)

Замечание.

max F(x) = – min[– F(x)], min F(x) = – max[– F(x)].

Запишем основную задачу линейного программирования в векторной форме. Найти максимум (минимум) функции

при условиях

, (10.14)

7. На этом шаге мы рассмотрим представление задачи линейного программирования в канонической форме.

Если математическая модель задачи линейного программирования имеет вид:

то говорят, что задача представлена в канонической форме.

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

12 3 4 5 6 7 8 9 10 Следующая ⇒

Последнее изменение этой страницы: 2019-05-06; Просмотров: 230; Нарушение авторского права страницы