«Авторы: И. В. Левандовская, И. С. Дмитренко, О. Н. Кузнецова, Н. С. Грудкина. ЭКОНОМИКОМАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ Учебное пособие В печать экз. Утверждено Первый проректор на заседании А. Н. Фесенко ученого совета ...»

Три последние строки состоят из равных элементов, тогда 1 0, 2 0, а 3 = 0, 4 = 0, отбросим две последние строки, получим:

Это соответствует системе:

За базисные переменные примем x1, x2, тогда свободные - x3, x 4.

Вопросы для самоконтроля 1. Что такое экономико-математическая модель?

2. Какие экономико-математические модели Вам известны?

3. Какие экономические матрицы используются в модели многоотраслевой экономики?

4. Какую задачу решает модель Леонтьева?

5. Сформулируйте теорему Кронекера-Капелли.

6. Найти ранг матрицы:

7. Проверить совместность системы и определить количество решений, 8. Отрасль состоит из четырех предприятий. Вектор выпуска продукции и матрица коэффициентов прямых затрат имеют вид:

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

Литература для самостоятельной работы по данному разделу:

[4, раздел I,гл. 2,пп. 2, 7, с. 56-62], [7, гл. 5, с. 73-89; гл. 7, 8, с. 101-135, [12, часть 2, с. 158-236], [13, часть 1, гл. 2, с. 51-62], [14, гл. 9, с. 345-358], [19, п. 28.1, с. 412-415].

3 ЗАДАЧА ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

И МЕТОДЫ ЕЕ РЕШЕНИЯ

и удовлетворяют системе ограничений:

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

Допустимым решением (планом) задачи ЛП называется любой вектор X = (x1, x 2,..., x n ), удовлетворяющий системе ограничений и условиям не отрицательности (3.2).

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

Пример 3.1. Задача составления рациона.

Имеется два вида корма 1 и 2, содержащие витамины A1, A2, A3.

Стоимость 1кг корма соответственно равна 4 и 6 грн. Данные по содержанию витаминов в 1 кг корма и их необходимый минимум приведены в таблице 3.1.

Необходимо составить дневной рацион, имеющий минимальную стоимость, в котором содержанию витаминов было бы не меньше нормы.

Решение. Обозначим x1, x 2 – количество кормов 1 и 2, входящих в рацион. Тогда витаминов в нем будет содержаться соответственно:

что составит систему.

Данная система и ограничения x1 0, x 2 0 образуют систему ограничения задачи.

Общая стоимость корма составит F = 4 x1 + 6 x 2 - целевую функцию задачи.

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

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

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

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

Для нахождения среди допустимых решений оптимального решения используются линии уровня, опорные прямые, градиент.

Линией уровня называется прямая, на которой целевая функция принимает постоянное значение F = C, где C – const. Все линии уровня параллельны между собой.

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

Градиент – это вектор, который показывает направление наибольшего роста функции:

Алгоритм графического метода.

1. Построить область допустимых решений.

2. Построить градиент функции и одну из линий уровня ( F = 0 ).

3. Если ищем максимум, то перемещать линию уровня по направлению градиента, если минимум – против градиента.

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

5. Решив совместно уравнения границ, имеющих общую точку с последней опорной прямой, найти координаты этой точки ( x 0, y 0 ).

6. Вычислить значение функции F (x0, y0 ).

Замечание.

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

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

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

Пример 3.2. (множество решений).

Решить графическим методом задачу.

На рисунке 3.1 представлена графическая интерпретация решения задачи.

Область ABCD - допустимая, прямая L - линия уровня. Сдвинем L по направлению g. Решением будут точки A и B, т.е. отрезок AB. Уравнение AB : y = 8 x, 3 x 6. Значение F = 24.

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

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

3.3 Приведение стандартной задачи ЛП к канонической задаче Каждому решению (a1, a 2,..., a n ) неравенства:

соответствует определенное решение (a1, a 2,..., a n, a n +1 ) уравнения:

и, наоборот, каждому решению (a1, a 2,..., a n ) уравнения (3.7) и неравенства (3.8) соответствует определенное решение (a1, a 2,..., a n ) неравенства (3.6).

Переведем стандартную задачу (3.1), (3.3), (3.4) в каноническую. Для этого в каждое из m неравенств введём дополнительные неотрицательные переменные x n +1, x n + 2,..., x n + m, и система ограничений примет вид:

Стандартная задача в канонической форме - найти такое решение X = ( x1, x 2,..., x n, x n +1,..., x n + m ), удовлетворяющее системе (3.9) и условию (3.3), при котором функция (3.1) принимает максимальное значение.

3.4 Решение системы линейных уравнений методом Жордана – Гаусса.

Рассмотрим систему m уравнений с n неизвестными.

Независимые переменные bi должны быть неотрицательны.

Перепишем ее в другом виде, перенеся все выражения в правую часть уравнений и приравняв к нулю (0 - система).

........................................................................................

Перепишем ее в Жорданову таблицу 3.2.

Таблица 3. Преобразуем элементы таблицы методом жордановых исключений.

Алгоритм метода.

1. Выберем разрешающий элемент aij, не равный 0 (в своем столбце это элемент, отношение к которому свободного элемента его строки наименьшее min i a ). Его строка и столбец становятся разрешающими.

2. Разрешающий элемент заменяется на обратный: a ij = 1 a.

a ik = 4. Остальные элементы разрешающего столбца делятся на (aij ) :

a pj = pj 5. Остальные элементы таблицы вычисляются по следующему правилу. Строим в таблице прямоугольник с вершинами в разрешающем элементе aij и рассматриваемом элементе art (рис.3.2).

7. Переменная xi и 0 из строки i меняются местами.

После первого шага получим таблицу 3.3:

После m шагов получим таблицу 3.4:

Полученное решение X = ( x1, x 2,..., x n, x n +1,..., x n + m ) называется базисным. В нём x1 = b1m, x 2 = b2,…, x1m = bm, остальные корни равны нулю.

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

Неотрицательные базовые решения называются опорными решениями или планами.

Решить систему линейных уравнений методом Жордана-Гаусса:

Перепишем систему в виде нуль - равенств:

Составим таблицу полученной системы уравнений (таблица 3.5).

Таблица 3. Сделаем шаг Жордановых исключений.

1. Разрешающий элемент a12 = 1.

2. Строка 1 не меняется (делятся на 1).

3. В столбце 2 элементы, кроме a12, делятся на (-1).

4. Остальные элементы найдем по формуле прямоугольника (рис.

3.3) и заполним таблицу 3.6.

Таблица 3. Шаг 1. Разрешающий элемент a21 = 5 (таблица 3.7).

Таблица 3. Шаг 2. Разрешающий элемент a33 = 4 (таблица 3.8).

Таблица 3. Система имеет единственное решение - ( 1,2,1).

Замечание.

Столбцы под 0 можно не писать, т.к. они не влияют на дальнейшее вычисление.

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

2. Как перевести стандартную задачу в каноническую задачу?

3. Понятие градиента и линии уровня для функции.

4. Построить линии уровня функций: а) z = 3 x + 4 y, б) z = xy.

5. Найти градиент и его модуль для функции z = 4 x 2 y 2 в указанной 6. Построить выпуклую область, заданную неравенствами:

7. Определить, являются ли области ограниченными:

8. Графическим методом найти минимум и максимум функции Литература для самостоятельной работы по данному разделу [1] – гл. 1, с. 16-28,[8] – раздел I, гл. 1-4, с. 16-64, [12] – часть 4, гл. 17, с.

343-353, [13] – часть IV, гл. 14, с. 259-266, [14] – гл. 1, с. 9-46, [19] – п. 28.2, 29.1, 29.2, с. 415-431.

4 ТЕОРИЯ ДВОЙСТВЕННОСТИ И АНАЛИЗ ЛИНЕЙНЫХ

МОДЕЛЕЙ ОПТИМИЗАЦИОННЫХ ЗАДАЧ

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

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

1. Запишем общую задачу в каноническом виде:

Преобразуем систему (4.2) в 0 – систему (при этом все bi 0 ).

Составляем начальную таблицу, аналогично методу Жордана – Гаусса, добавив в нее строку коэффициентов F (таблица 4.1).

Таблица 4. 4. Применяя метод Жордановых исключений, заполняем 0столбец, выбирая x j по правилам разрешающего элемента (таблица 4.2).

Полученный план X = (x1, x 2,..., x n, xn +1,..., xn + m ) называется начальx1 = b1m, x2 = b2m, …, x1m = bm, остальные корни ным планом. В нём равны нулю.

А) В полученной таблице удобно убирать столбцы с 0 в верхней строке, т.к. они не влияют на решение.

Б) Ненулевыми могут быть любые x j.

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

6. Следующим действием меняем в плане один из x с помощью Жорданова исключения.

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

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

8. Пункты 6, 7 повторяют до тех пор, пока критерий не выполнися.

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

Порядок выбора разрешающего элемента.

• разрешающий элемент всегда больше или равен 0;

• столбец, в котором в последней строке находится наибольший по модулю отрицательный элемент ci < 0, является разрешающим столбцом;

• для разрешающего столбца проверяем отношение элементов с элеменbi тами столбца 1 - ищем min ; при этом учитываем следующие оценки:

1) если a is и bi имеют разные знаки, то Строка, в которой найден min называется разрешающей строais кой.

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

Критерий оптимальности. Если в последней строке есть c j < 0, то план неоптимальный. Если в последней строке все c j > 0, то план оптимальный, и значение c0 является значением Fmax.

Критерий неразрешимости. Если при построении начального базиса возникла строка, в которой все aij < 0, то система ограничений противоречива, задача не имеет решения. Если на каком-либо шаге один из коэффициентов F отрицателен c k < 0, а в его столбце k нет положительных элементов, значит, расчет прекращается, т.к. функция не ограничена.

Переход от одной таблицы к другой.

Меняем местами переменные строки и столбца разрешающего элемента.

Разрешающий элемент заменяется обратным.

Все элементы разрешающей строки делятся на разрешающий элемент.

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

Все остальные элементы находим методом Жордановых исключений.

Решить симплекс-методом задачу.

Составим симплекс-таблицу (таблица 4.3).

Таблица 4. Методом жордановых исключений найдем начальный опорный план.

Шаг 1. Столбец x 4, строка 3, разрешающий элемент a34 = 5 (таблица 4.4).

Таблица 4. Шаг 2. Столбец x 2, строка 2, разрешающий элемент a 22 = 2 (таблица 4.5).

Таблица 4. Шаг 3. Столбец x1, строка 1, разрешающий элемент a11 = 2,2 (таблица 4.6).

Таблица 4. 4.2 Теория двойственности Каждой задаче линейного программирования можно определенным образом поставить в соответствие другую задачу тоже линейного программирования, которую называют двойственной по отношению к данной (исходной) задаче. Исходная и двойственная задачи тесно связаны между собой и образуют единую пару двойственных задач.

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

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

4.2.1 Симметричные двойственные задачи Рассмотрим неканоническую модель исходной задачи ЛП. Ищется максимум целевой функции при ограничениях:

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

• каждому неравенству системы ограничений исходной задачи приводим в соответствие переменную y j ;

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

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

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

Математическая модель двойственной задачи имеет следующий вид:

найти минимум целевой функции при ограничениях:

4.2.2 Несимметричные двойственные задачи Рассмотрим математическую модель исходной задачи в канонической форме.

Дана исходная задача нахождения максимума целевой функции при ограничениях:

Составим математическую модель двойственной задачи.

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

• ограничениями двойственной задачи будут неравенства. Если в целевой функции двойственной задачи требуется найти минимум, то знак неравенства, если максимум – то ;

• переменные y j произвольные по знаку, т. е. могут принимать как положительные, так и отрицательные значения.

Математическая модель двойственной задачи также состоит из соотношений (4.6), (4.7), с той лишь разницей, что теперь переменные y j – произвольные по знаку, i = 1, m.

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

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

Приведем основные теоремы, необходимые для решения двойственных задач.

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

Замечание. Если одна из двойственных задач неразрешима из-за L (x ) max (или S ( y ) min ), то другая задача также не имеет допустимых решений.

Теорема 4.2. Для оптимальности допустимых решений x и y пары двойственных задач необходимо и достаточно, чтобы они удовлетворяли системе уравнений:

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

Пример 4.2. Рассмотрим решение задач с использованием теорем двойственности.

Решив исходную задачу любым методом, например графическим, получим х опт (4 ; 1) при L( x ) max = 3.

На основании теоремы двойственности 4.1 получаем:

По теореме двойственности 4.2 систему ограничений двойственной задачи можно записать в виде равенств:

Подставим хопт в систему ограничений исходной задачи. Тогда система ограничений двойственной задачи примет вид:

Тогда система ограничений двойственной задачи примет вид:

Вопросы для самоконтроля Сформулируйте алгоритм симплекс-метода.

Как преобразуется стандартная задача в симплекс-методе?

Покажите преобразование Жордана – Гаусса.

Назовите критерий оптимальности симплекс-метода.

Составьте симплекс-таблицу для задачи.

6. Решить симплекс методом, сравнить с геометрическим решением 7. Составить математическую модель двойственной задачи и решить Литература для самостоятельной работы по данному разделу [1] – гл. 1, с. 88-115, [8] – раздел I, гл. 5, 6, с. 64-123, [12] – часть 4, гл. 18, 19, с. 354-383 [13] – часть IV, гл. 14, с. 267-285, [14] – гл. 1,2, с. 47-94, [19] – п. 30, 31, с. 432-475.

5 ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ

В общем виде математическая модель задачи целочисленного программирования имеет вид:

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

Методы целочисленной оптимизации можно разделить на следующие группы:

- методы отсечения;

- комбинаторные методы;

- приближенные методы;

- графический метод.

5.1 Методы отсечения. Метод Гомори.

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

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

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

Пусть получено оптимальное решение X опт = ( f1, f 2,..., f r, 0,..., 0), которое не является целочисленным, тогда последний шаг симплексной таблицы имеет следующий вид (таблица 5.1):

Таблица 5. где r - ранг системы ограничений, hi, r +1 - коэффициент симплексной таблицы i -ой строки, (r + 1) -го столбца, f i - свободный член i -й строки.

Пусть f i и хотя бы одно hij ( j = r + 1,..., n; i = 1,..., r )- дробные числа.

Обозначим через [ f i ], [hij ] - целые части чисел f i, hij.

Определение. Целой частью числа f i называют наибольшее целое число, не превосходящее числа f i. Дробную часть чисел f i и hij обозначим { f i } и { hij }, она определяется следующим образом:

{ f i }= f i -[ f i ], { hij }= hij -[ hij ].

Пример 5.1. Выделить целую и дробную часть числа Если f i и хотя бы одно значение hij дробны, то с учетом введенных обозначений целых и дробных чисел дополнительное ограничение по целочисленности (неравенство Гомори) примет вид:

Примечания.

1) если f i - дробное число, а все hij - целые числа, то задача линейного программирования не имеет целочисленного решения.

2) если среди f i несколько дробных чисел, то для составления неравенства Гомори выбирают строку, соответствующую f i с наибольшей дробной частью.

Пример 5.2. Для улучшения финансового положения фирма приняла решение об увеличении выпуска конкурентоспособной продукции, для чего принято решение об установке в одном из цехов дополнительного оборудования, занимающего 19/3 м2 площади. На приобретение дополнительного оборудования фирма выделила 10 усл.ед., при этом она может купить оборудование двух видов. Приобретение одного комплекта оборудования 1-го вида стоит 1 усл.ед., 2-го вида – 3 усл.ед. Приобретение одного комплекта оборудования 1-го вида позволяет увеличить выпуск продукции в смену на 2 шт., а одного комплекта оборудования 2-го вида – на 4 шт. Зная, что для установки одного комплекта оборудования 1-го вида требуется м2 площади, а для оборудования 2-го вида – 1 м2 площади. Определить такой набор дополнительного оборудования, который дает возможность максимально увеличить выпуск продукции.

Решение: Составим математическую модель задачи. Предположим, что фирма приобретает x1 комплектов дополнительного оборудования 1го вида и x2 комплектов оборудования 2-го вида. Математическая модель задачи будет иметь вид:

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

Вначале решим задачу линейного программирования симплекс - методом (таблица 5.2):

Таблица 5. Найдем дробные части чисел 9/5 и 41/15:

= 0 =, = + 1 =, составляем неравенство Гомори для 1- ой строки: 3 5 x3 + 4 5 x4 4 5 или 3 5 x3 + 4 5 x4 x5 = 4 5, которое вводим в последнюю таблицу 5.3:

Таблица 5. Ответ: X цел = (1, 3), L = 14. Фирме необходимо приобрести 1 комплект дополнительного оборудования 1-го вида и 3 комплекта оборудования 2-го вида. При этом в смену будет дополнительно производиться 14 шт. продукции.

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

Если в условие задачи поставить x3 = 4 3, то дополнительное ограничение имеет вид:

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

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

Через D обозначим допустимое множество решений задачи P0. Если оптимальный план задачи Xопт является цело численным, то исходная задача решена, если нет, - то есть хотя бы одна компонента Xопт не является цело численной, - то производится ветвление. Пусть, например, xi не является целым числом. Тогда производим ветвление исходной задачи P0 на две под задачи P и P2. В задаче P добавляем ограничение xi xi, а в задаче P2 - ограничение xi xi + 1. Таким образом из множества D исключается область [xi ] < xi < [xi ] + 1, а допустимыми множествами под задач P и P2 являются множества D1 и D2.

Предположим нам удастся показать, что L( x ) L0, где L0 - верхняя оценка задачи P0. В качестве L0 может быть взято значение L в любой допустимой точке множества D. Предположим, что после ветвления P0 на L( x ) L1, x D1 ; L( x ) L2, x D2. Назовем L1 и L2 нижними оценками подзадач P и P2 соответственно. Пусть при этом L1 > L0. Тогда множество D1 не содержит оптимального плана, то есть задача P исключается из списка рассматриваемых задач. В случае, если задача P2 при этом не имеет целочисленного решения, то производим ветвление второго уровня и т.д.

5.3 Транспортная задача ЛП закрытого типа Пусть имеется n поставщиков товара одного и того же вида и m потребителей этого товара. Объем продукции i - го поставщика, т. е. его мощность – Pi. Объем потребления j - го потребителя – Q j. Стоимость перевозки одной единицы товара от i - го поставщика до j - го потребителя составляет cij. Данные задачи записываются в виде таблицы 5.4.

Нужно найти объемы перевозок для каждой пары Ai B j, так чтобы • Мощности всех поставщиков были реализованы;

• Спросы всех потребителей были удовлетворены;

Суммарные затраты S = cij xij на перевозку были бы миниij мальны.

Задача открытого типа можно свести к задаче закрытого типа путем введения фиктивного поставщика или фиктивного потребителя.

Алгоритм решения:

• построить любой допустимый план перевозок;

• последовательно оптимизировать план, проводя пошаговую оценку.

Замечание.

Количество заполненных клеток в любом плане перевозок всегда равно ( m + n 1), т.к. ранг матрицы ограничений равен ( m + n 1). Если ранг меньше числа ( m + n 1), то одну из нулевых клеток считаем заполненной.

Построение начального плана (опорного решения) методом северозападного угла.

Преобразуем таблицу данных (таблица 5.5).

Таблица 5. Заполняем таблицу, начиная с клетки (1, 1) и двигаясь вправо и вниз.

Выбираем минимум из Q1 и P1 – x11 Если x11 = P1, то столбец 1 закрыт.

Следующий шаг вправо. Выбираем минимум из чисел (Q1 x11 ) и (P2 x12 ). Если x11 = (Q1 x11 ), то строка 1 закрыта. Следующий шаг вниз и т. д.

Рассмотрим начальную таблицу (таблица 5.6).

Таблица 5.6-начальная Данные преобразования представлены в таблице 5.7.

5 шаг. x 24 = min (350 100 190;150 ) = 60. Закрыта строка 2.

6 шаг. x 34 = min (200;150 60) = 90. Закрыт столбец 4.

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

Количество заполненных клеток равно: (m + n 1) = 5 + 3 1 = 7.

Построение начального плана (опорного решения) методом минимального элемента.

В начальной таблице выберем клетку с наименьшей ценой перевозки с номером (i; j ). Заполним эту клетку по правилу x ij = min(Pi ; Q j ). Предположим, что xij = Pi. Тогда i - й столбец закрыт, а в j - й строке опять выбираем клетку с наименьшей ценой.

Пример 5.4. Рассмотрим начальную таблицу (таблица 5.8).

Таблица 5.8 - начальная 1 шаг. Выбираем клетку (1; 5), x15 = min (300 ; 220 ) = 220. Закрыт столбец 5.

2 шаг. Выбираем клетку (3; 2 ), x 32 = min (250;140 ) = 140. Закрыт столбец 2.

3 шаг. Выбираем клетку (1;1), x11 = min (300 220;150) = 80. Закрыта строка 1.

4 шаг. Выбираем клетку (3; 3), x33 = min (250 140;115) = 110. Закрыта строка 3.

5 шаг. Выбираем клетку (2;3), x15 = min (300; 5) = 5. Закрыт столбец 3.

Данные преобразования представлены в таблице 5.9.

6 шаг. Выбираем клетку (2;1), x 21 = min (295; 70 ) = 70. Закрыт столбец 1.

7 шаг. Выбираем клетку (2; 4 ), x 24 = min (225; 225) = 225. Закрыт столбец 3.

5.3.1 Цикл пустой клетки плана Если полученный начальный план не оптимален, то его изменяют, сдвигая поставки в другие клетки. При этом в одних клетках количество единиц товара увеличивается, а в других — уменьшается.

В полученной ранее таблице переместим одну единицу товара в клетку (3;4 ). При этом в клетках (2;4 ) и (3;3) количество товара уменьшается на ту же единицу, чтобы суммы строки и столбца не изменились, а в клетке (2;3) соответственно возрастет (таблица 5.10).

Единица движется по замкнутой ломанной, которая называется циклом. При таком движении суммы строк и столбцов не нарушаются.

Циклом, составленным для пустой клетки, называется замкнутая ломанная со следующими свойствами:

• вершины, кроме начальной, находиться в заполненных клетках;

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

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

Прибавляется стоимость перевозки (3; 4), (2; 3) и вычитается (3; 3), (2; 4).

Значит, стоимость изменяется на величину, называемую оценкой клетки:

Чтобы посчитать оценку клетки, нужно:

• в цикле вершины пометить знаками «+» и «-», чередуя их, начиная с пустой клетки и знака «+»;

• посчитать сумму цен перевозок клеток-вершин, взятых со знаками, которые мы расставили.

Критерий оптимальности плана. Базисное распределение поставок оптимально тогда и только тогда, когда все оценки пустых клеток больше или равны 0.

5.3.2 Распределительный метод.

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

- построить циклы для всех пустых клеток;

- посчитать оценки для всех пустых клеток;

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

- в цикле рабочей клетки вершины пометить знаками «+» и «-», чередуя их, начиная с пустой клетки и знака «+»;

- в клетках со знаком «-» выбрать минимальное количество перевозимого товара x = x pk ;

- сдвинуть по циклу число x, вычитая его из cij в клетках с «-» и прибавляя в клетках с «+»;

- получив новый план, нужно проверить, чтобы количество заполненных клеток было ( m + n 1) ;

- проверить для нового плана критерий оптимальности.

Пример 5.5.

Используем начальный план, построенный по методу северозападного угла (таблица 5.11).

Таблица 5. Построим циклы пустых клеток. x – оцениваемая клетка, з – заполненная клетка, п – пустая клетка.

Проведём оценку пустых клеток:

Наиболее перспективная для изменений – клетка с наименьшей оценкой (1; 4).

В цикле этой клетки выделяем все занятые клетки с «-», и среди них находим наименьшее количество xij x12 = 30.

Сдвигаем эту величину по циклу, добавляя в клетки с «+» и вычитая в клетки с «-» (таблица 5.12).

Таблица 5. Получаем новый план, для которого опять нужно построить циклы, найти оценки и т.д. (таблица 5.13).

Таблица 5. Процесс оканчивается, когда все оценки станут положительными.

5.3.3 Метод потенциалов Алгоритм метода очень похож на распределительный метод, отличается лишь принцип оценок:

- для каждой строки выбираем число потенциал u j, а для каждого столбца – vi ;

- один из потенциалов выбираем произвольно (лучше u1 = 0 );

- остальные выбираются по правилу: для заполненной клетки cij = u j + vi ;

- оцениваем пустые клетки по формуле S ij = cij (u j + vi ) и составляем матрицу оценок;

Замечание. Оценки всех заполненных клеток равны 0.

- если не выполняется критерий оптимальности (все S ij 0 ), то выбрать среди отрицательных оценок S ij самую большую по модулю, эта клетка будет рабочей;

- для выбранной клетки строим цикл;

- в цикле рабочей клетки вершины пометить знаками «+» и «-», чередуя их, начиная с пустой клетки и знака «+»;

- в клетках со знаком «-» выбрать минимальное количество перевозимого товара x = x pk ;

- сдвинуть по циклу число x, вычитая его из cij в клетках с «-» и прибавляя в клетках с «+»;

- получив новый план, нужно проверить чтобы количество заполненных клеток было (m + n 1) ;

- проверить для нового плана критерий оптимальности.

Пример 5.6.

Используем начальный план, построенный по методу минимального элемента (таблица 5.13).

Выберем u1 = 0, тогда по клетке (1;1) : v1 = 24 0, а по клетке (1; 5) :

Зная v1, вычислим по клетке (2;1) : u 2 = 20 24 = 4, тогда по клетке Зная v3, вычислим по клетке (3; 3) : u 3 = 18 44 = 26, тогда по клетке Вычислим оценки пустых клеток: S12 = 50 (0 + 42 ) = 8 и т.д.

Наименьшая оценка S14 = 12, значит, строим цикл для клетки (1; 4) и смещаем по циклу минимальный груз 80, оказавшийся в клетке со знаком «-» (таблица 5.14).

Получим новый план, который нужно проверить на оптимальность (таблица 5.15).

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

Вопросы для самоконтроля 1. Расскажите, чем задача целочисленного программирования отличается от задачи линейного программирования, 2. Какие типы задач решает целочисленное программирование?

3. Сформулируйте транспортную задачу.

4. Что такое цикл в транспортной задаче?

5. Какие есть методы построения начального базиса?

6. Основные этапы распределительного метода.

7. Основные этапы метода потенциалов.

8. Составить начальный план для задачи.

9. Решить транспортную задачу распределительным методом.

10.Решить транспортную задачу методом потенциалов.

Литература для самостоятельной работы по данному разделу [1] – гл. 2, с. 134-192, [8] – раздел I, гл. 7, 8, с. 123-197, [12] – часть 4, гл.

20, с. 384-396, [13] – часть IV, гл. 14, с. 286-295, [14] – гл. 5, с. 229-266, [19] – п. 32, 33, с. 476-504.

6 НЕЛИНЕЙНЫЕ ОПТИМИЗАЦИОННЫЕ МОДЕЛИ ЭКОНОМИЧЕСКИХ СИСТЕМ

найти вектор X ( x1 ; x2 ;...; xn ), удовлетворяющий системе ограничений:

и доставляющий экстремум (наибольшее или наименьшее значение) целевой функции:

где x j — переменные; Z, F, — заданные функции от переменных;

bi — фиксированные значения.

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

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

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

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

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

Функция F (х ), определенная на выпуклом множестве X, называется выпуклой (вогнутой), если и любых точек x и x из этого множества и любого 0 1 справедливо неравенство:

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

Если функции Fi (х ) ( i = 1, k ) являются выпуклыми на выпуклом множестве X, то выпуклой на X будет и линейная комбинация их функций.

Если F (х ) — выпуклая функция при всех x 0, то будет выпуклым и множество решений системы F (x ) b, x 0. Аналогичное утверждение справедливо и для вогнутых функций.

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

Локальный минимум (максимум) выпуклой (вогнутой) функции F (х ), определенной на выпуклом множестве X, совпадает с глобальным минимумом (максимумом) на этом множестве.

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

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

6.1 Графический метод.

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

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

Если определена область допустимых решений, то нахождение решения задачи (6.1), (6.2) сводится к определению такой точки этой области, через которую проходит гиперповерхность наивысшего (наинизшего) уровня F ( x1, x2,..., xn ) = h.

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

Процесс нахождения решения задачи нелинейного программирования (6.1), (6.2) с использованием ее геометрической интерпретации включает следующие этапы:

Найти область допустимых решений задачи, определенную соотношением (6.2).

Построить гиперповерхность F (x1, x2,..., xn ) = h (линия уровня).

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

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

Пример 6.1. Найти экстремумы функции F = ( x 4) + ( y 3) при условиях:

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

Определим уравнение линии уровня (x 4) + ( y 3) = h. Значит, линиями уровня являются окружности с центром F(4;3) и радиусом R = h (рис. 6.1). Увеличивая радиус окружности, мы одновременно увеличиваем значение функции. Очевидно, что самое маленькое значение, F = 0, функция принимает в центре окружности F(4;3), а самое большое – в той точке многоугольника ABCDE, которая наиболее удалена от точки F. По рисунку 1 видно, что это точка С.

Точка С лежит на пересечении двух граничных прямых. Ее координаты можно найти, решив систему уравнений:

Решив, получим точку С(13;10,5). Следовательно, Fmin=F(4;3)=0, Fmax=F(13;10,5)=137,25.

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

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

Если заранее известно, что функция F (х ) имеет в допустимой области единственный экстремум, то поиск точки, в которой он достигается, осуществляется по следующему алгоритму. В допустимой области необходимо взять произвольную точку x0 и с помощью градиента (антиградиента) определить направление, в котором возрастает (убывает) F (х ) с наибольшей скоростью (рис. 6.2). Сделав небольшой «шаг» в найденном направлении, перейти в новую точку x1. Проверить «улучшилось ли» значение функции, если нет – уменьшить шаг. Потом снова определить наилучшее направление для перехода в очередную точку x2 и т. д. Иначе говоря, надо построить последовательность точек x1, x2,... так, чтобы она сходилась к точке экстремума x, т. е. для точек последовательности выF ( x0 ) < F ( x1 ) < F ( x 2 ) <...

F ( x0 ) > F ( x1 ) > F ( x 2 ) >... для минимума.

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

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

Пример 6.2. Дана функция F (x, y ) = 4 x 2 + 4 y 2 + 2 xy x y + 60. Нужно сделать два шага в направлении минимизации и найти три контрольные точки. Начальная точка М0(8;4), начальный шаг h = 4.

Решение. Для контроля найдем значение функции в точке М0(8;4):

Вычислим градиент функции:

Значит, в точке М0(8;4) найден grad F = G (71; 47 ) и его длина G = 712 + 47 2 = 85,147.

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

Получилась новая точка М1(4,664; 2,072), значение функции в ней равно F1 = F ( 4, 664; 2, 072) = 176, 776.

Так как F1 < F0, значит, получившаяся точка является контрольной, и в следующем шаге ее можно использовать в качестве начальной точки.

Решение задачи удобно записывать с помощью таблицы 6.1.

X G G X Y F

Данная задача является типичной задачей о загрузке.

Постановка задачи: определить X = ( x1, x2,..., xi,..., xn ) удовлетворяющий условиям:

и обеспечивающий максимум целевой функции:

Разобьем процесс оптимизации на n шагов и будем на каждом i -ом шаге оптимизировать инвестирование не всех предприятий, а только предприятий с i -ого по n -ое. При этом естественно считать, что в остальные предприятия с первого по (i 1) -ое тоже вкладываются средства, и поэтому на инвестирование предприятий с i -ого по n -ое остаются не все средства, а некоторая меньшая сумма Ci W. Эта величина и будет являться переменной состояния системы. Переменной управления на i -ом шаге будет являться величина xi средств, вкладываемых в i -е предприятие. В качестве функции Беллмана f i (C i ) на i -ом шаге можно выбрать максимально возможный доход, который можно получить с предприятий с i -ого по n ое при условии, что на их инвестирование осталось C i средств. При вложении в i -е предприятие xi средств будет получена прибыль g i ( xi ), а система к (i + 1) -му шагу перейдет в состояние S i +1 и, следовательно, на инвестирование предприятий с (i + 1) -го до n -ого останется Ci +1 = (Ci xi ) средств.

Таким образом, на первом шаге условной оптимизации при i = n функция Беллмана представляет собой прибыль только с n -ого предприятия. При этом на его инвестирование может остаться количество средств C i, 0 Ci W. Чтобы получить максимум прибыли с этого предприятия, можно вложить в него все эти средства, т. е. f n (C n ) = g n (C n ) и xn = C n.

На каждом последующем шаге для вычисления функции Беллмана необходимо использовать результаты предыдущего шага. Пусть на i -ом шаге для инвестирования предприятий с i -ого по n -ое осталось Ci средств 0 Ci W. Тогда от вложения в i -е предприятие xi средств будет получена прибыль g i (C i ), а на инвестирование остальных предприятий i -го по n е останется Ci +1 = (Ci xi ) средств. Максимально возможный доход, который может быть получен с предприятий i -го по n -е будет равен:

Максимум данного выражения достигается при некотором значении xi, которое является оптимальным управлением на i -ом шаге для состояния системы S i. Действуя таким образом, можно определить функции Беллмана и оптимальные управления до шага i = 1.

Значение функции Беллмана F1 (C1 ) представляет собой максимально возможный доход со всех предприятий, а значение xi, на котором достигается максимум дохода, является оптимальным количеством средств, вложенных в первое предприятие. Далее на этапе безусловной оптимизации для всех последующих шагов величина C i = (Ci 1 xi 1 ) и оптимальном управлении на i -ом шаге является то значение xi, которое обеспечивает максимум дохода при соответствующем состоянии системы S i.

Пример 6.3. Совет директоров фирмы рассматривает предложения относительно прироста производственных мощностей для увеличения выпуска однородной продукции на четырех предприятиях, принадлежащих фирме. Для модернизации предприятий совет директоров инвестирует средства в объеме 250 усл.ден.ед. с дискретностью 50 усл.ден.ед. Прирост выпуска продукции зависит от выделенной суммы, его значения даны предприятиями и содержатся в таблице 6.3. Найти распределение инвестиций между предприятиями, обеспечивающее фирме максимальный прирост продукции, при чем на одно предприятие можно осуществить только одну инвестицию.

Инвестиции, Прирост выпуска продукции, усл.ден.ед.

Решение. Запишем уравнение Беллмана для метода обратной прогонки и разобьем решение задачи на 4 этапа.

Этап 4. F5 (C5 ) = 0 (таблица 6.4).

Из таблицы этапа 1 находим оптимальное значение целевой функции при распределении между предприятиями всей суммы C1 = 250, F1 ( 250) = 55. При этом первому предприятию должно быть выделено x1 = 0 ден.ед. Тогда остальным трем предприятиям остается распределить 2 = 1 x1 = 250 0 = 250 ден.ед. Из таблицы этапа 2 выделению суммы 3 = 2 x 2 = 250 100 = 150 ден.ед. Из таблицы этапа 3 выделению сумx3 = 50, 4 = 3 x3 = 150 50 = 100 ден.ед. На последнем этапе 4 определяем x 4 = 100.

Таким образом, оптимальный план инвестирования предприятий X = (0,100, 50, 100), который обеспечит максимальный доход, равный F (250) = g1 (0) + g 2 (100) + g 3 (50) + g 4 (100) = 0 + 20 + 12 + 23 = 55 усл.ден.ед.

Вопросы для самоконтроля 1 Сформулировать основные признаки нелинейного программирования.

2 Дать определение выпуклой области, выпуклой функции.

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

4 Дать определение градиента функции многих переменных.

5 Рассказать, что такое стационарные точки функции многих переменных и основные признаки существования в них экстремума.

6 Алгоритм градиентного метода.

8 Решить графически:

длиной h = 4 по антиградиенту от точки М0 (8,4).

Литература для самостоятельной работы по данному разделу [1] – гл. 3,4, с. 251-311, [8] – раздел II, гл. 10-12, с. 200-270, [12] – часть 4, гл. 20, 21, с. 384-405, [14] – гл. 7, 8, с. 267-344.

7 АНАЛИЗ И УПРАВЛЕНИЕ РИСКОМ В ЭКОНОМИКЕ

Процесс принятия решения состоит из следующих этапов:

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

2. Оценка вероятностей состояний среды (возможность исхода каждого события).

3. Установление выигрышей или проигрышей (как выигрышей со знаком минус) для каждой возможной комбинации действий (альтернатив) и состояний среды.

4. Построение дерева решений.

5. Проведение расчетов и принятие решения как движение от вершин дерева решений к его корням (справа налево) с анализом вариантов.

Рассмотрим процедуру принятия решений на примерах.

Пример 7.1. Администрация компании (ЛПР) решает вопрос об инвестировании. Можно инвестировать средства в проект А, проект Б, или в действующий торговый комплекс. С вероятностями 0,5 инвестиции в проекты А и Б могут принести выигрыши S1, и S 2 в определенных денежных единицах: 250000 либо – 170000 и 140000 либо – 30000 соответственно.

Инвестирование торгового комплекса (проект В) принесет гарантированную прибыль в размере 25000. Определить решение ЛПР.

Решение. По данным задачи полагаем, что этапы 1 – 3 процесса принятия решения выполнены. Дерево решений приведено на рис. 13.4. Определим теперь ожидаемую прибыль в каждом возможном случае как математическое ожидание случайной величины, которая может принимать два значения с вероятностями p1 и p 2 :

Тогда для вершин 1 – 3 дерева решений средние ожидаемые выигрыши составят, соответственно, 40000, 55000 и 25000. Если в качестве критерия выбора принять величину ожидаемой прибыли Pr f, то следует выбрать проект Б.

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

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

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

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

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

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

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

Пример 7.2. В условиях примера 7.1 определить меру рисков проектов для принятия решения.

Решение. Дисперсия для проектов А и Б составляет соответственно:

Соответственно, 1 = 210 000, 2 = 85 000. Из этого следует, что нужно остановить свой выбор на проекте Б, так как при более высокой ожидаемой прибыли риск этого проекта минимальный.

7.1.3 Портфельный анализ. Формирование инвестиционного портфеля Поскольку ценные бумаги различных видов различаются по доходности и степени надежности, инвесторы вкладывают средства в приобретение ценных бумаг нескольких видов, стремясь достичь наилучшего соотношения «риск – доходность». Принимая решение о приобретении набора ценных бумаг, инвестор должен иметь в виду, что доходность портфеля в предстоящий период владения неизвестна. Однако можно оценить предполагаемую доходность различных ценных бумаг, является случайной величиной, и основными ее характеристиками являются ожидаемое, или среднее, значение и стандартное отклонение. Именно последнюю характеристику предлагается использовать как меру риска. Инвестор максимизирует ожидаемую доходность и минимизирует риск, то есть неопределенность. Подход Г. Марковица к принятию решения дает возможность адекватно учесть обе цели, противоречащие друг другу.

7.1.4 Доходность и риск портфеля Метод, применяемый для выбора наиболее желательного портфеля, использует кривые безразличия. Иными словами, для инвестора существует функция полезности, зависящая от двух аргументов – ожидаемой доходности портфеля rp и стандартного (среднего квадратического) отклонения p как меры риска:

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

Рисунок 7.2 – Достижимое множество портфелей из n видов Инвестор считает любой портфель, лежащий на линии безразличия выше и левее, более привлекательным, чем портфели, лежащие на линии безразличия, которая ниже и правее. Ожидаемая доходность портфеля состоящего из n ценных бумаг, равна где x – доля начальной стоимости портфеля, инвестированная в i -й вид ценных бумаг, ri – ожидаемая доходность i -го вида ценных бумаг, n – количество видов ценных бумаг в портфеле.

Стандартное отклонение портфеля (rp ) вычисляется следующим образом. Дисперсия доходности портфеля – это дисперсия суммы случайных величин; как известно из теории математической статистики, она равна ковариации:

Здесь Cov(ri, r j ) – ковариация ожидаемых доходностей ценных бумаг i и j, вычисляемая по формуле:

где µ ij – коэффициент корреляции между доходностями i -й и j -й ценных бумаг, D и – соответственно, дисперсия и стандартное (среднеквадратическое) отклонение доходностей ценных бумаг. Как известно, 1 µ ij 1.

Формула для стандартного отклонения портфеля имеет вид:

Пример 7.3. Найти ожидаемую доходность и стандартное отклонение доходности портфеля, состоящего из 30 % акций компании А и 70 % акций компании В, если их доходности некоррелированы и равны, сооветственно, 25 и 10 %, а стандартные отклонения – 10 и 5 %.

Решение. По формуле (7.4) получаем:

Поскольку доходности бумаг некоррелированы, то µ ij = 0 при i j, и тогда получаем:

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

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

1 Максимизирует ожидаемую доходность для некоторого уровня риска.

2 Минимизирует риск для некоторого уровня ожидаемой доходности.

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

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

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

Назовем таких субъектов игроками. Каждый игрок „ ” имеет в своем распоряжении некоторое множество S возможных действий, которые мы назовем стратегиями. Процесс игры заключается в том, что каждый игрок выбирает одну из своих стратегий s S i. Каждая игра состоит из системы стратегий совокупности игроков, которую мы назовем ситуацией S :

В каждой ситуации игроки получают некоторый выигрыш H i (S ).

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

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

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

Функцию выигрыша H ( a, b) считаем функцией двух переменных, где a – стратегии первого игрока, а b – стратегии второго игрока.

7.2.1 Понятие о минимаксе и седловой точке Ситуацию равновесия можно записать в виде двойного неравенства:

Это неравенство определяет следующее свойство функции H ( a, b) в точке (a, b ).

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

Если функция f ( x ) задана на множестве D, то ее супремумом на этом множестве называется наименьше из всех чисел S, для которых f ( x ) S для любого x D. Обозначается sup f ( x ). Аналогично инфимуx D мом функции f ( x ) на множестве D называют наибольшее из чисел S для которых f (x ) S. Обозначается inf f ( x ). Если супремум функции достигаx D ется, то есть существует x такое, что f (x ) = sup f (x ), то он называется максимумом и обозначается max f ( x ). Если достигается инфимум, то он называется минимумом и обозначается min f ( x ).

Непосредственно из определения можно доказать следующие утверждения.

Утверждение 7.1. Если некоторая константа c такая, что f ( x ) c при любом x, то и sup f (x ) c. Аналогично, если f (x ) c при любом x, Утверждение 7.2. Если функции f ( x ) и g ( x ) имеют одну область Теорема 7.1. Если x изменяется в области X, а y изменяется в области Y, то для любой функции f ( x, y ), определенной на области X Y, имеет место неравенство:

Доказательство. При любых x и y имеем:

Поэтому, из утверждения 7.2 получаем:

В правой части этой неравенства стоит константа. Поэтому, по утверждению 7.1 получаем: sup inf f (x, y ) inf sup f (x, y ).

Теорема доказана.

Следствие.

Если в (3.1) все екстремумы достигаются, то имеем неравенство минимаксов Теорема 7.2 (без доказательства). Для того чтобы функция f ( x, y ) на множестве X Y имела седловые точки, необходимо и достаточно, чтобы существовали минимаксы max min f ( x, y ), min max f ( x ) и выполнялось равенство:

Антагонистическая игра, в которой каждый игрок имеет конечное количество стратегий, называется матричной игрой. Это название объясняется тем, что в этом случае есть возможность составить прямоугольную таблицу, в которой строки отвечали бы стратегиям первого игрока, а столбцы – стратегиям второго; клетки матрицы, которые стоят на пересечении строк и столбцов отвечали бы ситуациям игры. Если в клетке записать соответственно выигрыш первого игрока, то получим описание игры в виде матрицы. Процесс игры в этом случае удобно интерпретировать таким образом: задана матрица A, игрок 1 выбирает строку этой матрицы, игрок 2 – ее столбец. Выбор обеих игроков – независимый. После этого первый игрок получает выигрыш, который записан в клетке, которая стоит на пересечении соответствующих строки и столбца. Понятно, что если этот выигрыш – отрицательное число, то фактически выиграл второй игрок.

Пусть матрица выигрыша имеет вид:

Стратегии первого игрока обозначают номерами соответствующих строк, а второго – номерами столбцов. Ситуацией в игре является пара (i, j ), где i – номер строки, j – номер столбца.

Ситуацией (i, j ) является седловая точка, если для любого i = 1,..., m и любого j = 1,..., n выполняется неравенство:

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

Практически поиск седловых точек матрицы A можно выполнять по такой схеме Если минимаксы этой матрицы, то есть max min aij и min max aij отj j личны один от другого, то игра, заданная матрицей выигрышей не имеет ситуации равновесия. В этом случае первый игрок может обеспечить себе выигрыш max min aij, а второй игрок может не дать ему больше чем min max aij.

min max aij max min aij остается открытым. Для того чтобы получить в свою пользу как можно большую часть этой разности, игроки должны выбирать свои стратегии случайно. Такие стратегии назовем смешанными, в отличие от так называемых чистых стратегий, о которых сообщалось выше. Смешанная стратегия игрока имеет схему вероятностей выбора им своих чистых стратегий, ее можно представить в виде вектора Легко видеть, что чистым стратегиям отвечает вектор, одна координата которого равняется 1, а все другие 0.

Пусть в игре с матрицей выигрышей (7.2) игроки первый и второй выбирают свои смешанные стратегии Назовем ситуацией в смешанных стратегиях пару векторов ( X, Y ).

Таким образом, каждая обычная ситуация (i, j ) (в чистых стратегиях) оказывается случайным событием и реализуется с вероятностью xi y j. Поскольку в этой ситуации первый игрок получает выигрыш aij, то математическое ожидание его выигрыша равняется Теорема 7.3 (без доказательства). Для любой матрицы A выполняется Таким образом, при использовании смешанных стратегий, результат матричной игры можно предвидеть и он не зависит от искусства или глубины психологического анализа игроков. Общее значение минимаксов (7.11) называют значением матричной игры, заданным матрицей выигрышей A. Равновесные стратегии игроков ( X, Y ) называют оптимальными стратегиями.

Рассмотрим матричную игру, в которой каждый из игроков имеет по две чистых стратегии. Матрица выигрышей этой игры имеет вид:

Пусть X – произвольная смешанная стратегия первого игрока, которая не может быть чистой. Если x – вероятность выбора первым игроком своей первой чистой стратегии, то (1 x ) – вероятность выбора второй чистой стратегии. Тогда X = ( x,1 x ). Аналогично Y = ( y, 1 y ) – стратегия второго игрока. То есть ситуация полностью исчерпывается парой чисел Обозначим x и y оптимальные стратегии игроков. При этом Учитывая то, что максимум и минимум достигаются в интервале [1, 2], они должны быть аналитическими екстремумами. То есть в точках x и y должны обращаться в 0 соответствующие частные производные:

Цена игры по формуле (7.5) после преобразований примет вид:

Таким образом, решение игры 2 2 можно вести по такой схеме:

1. Проверить существование ситуации равновесия в чистых стратегиях по схеме (7.8). Если минимаксы равны между собой, то они равны цене игры.

2. Если минимаксы в схеме (7.8) разные, то имеем дело с ситуацией равновесия в смешанных стратегиях. Оптимальные стратегии ищем по формулам (7.13), (7.14) а цену игры по формуле (7.15).

Например, решить игру, заданную матрицей Максимум 1-го столбца – 6, 2-го – 4. Минимум этих двух чисел – 4.

Минимум 1-ой строки – 2, 2-ой – 3. Максимум этих чисел – 3. Минимаксы разные. Ищем смешанные стратегии:

Вывод: первый игрок выбирает первую стратегию с вероятностью 0,6, вторую стратегию с вероятностью 0,4. Второй игрок выбирает свою первую стратегию с вероятностью 0,2, вторую с вероятностью 0,8. При этом выигрывает первый игрок и его выигрыш 3,6. Это наименьший выигрыш, который ему разрешит получить второй игрок.

7.2.4 Графический метод решения 2 n игр Рассмотрим игру, в которой первый игрок имеет две чистые стратегии, а второй некоторое число n стратегий. Матрица выигрышей этой игры имеет вид:

Как и в предыдущем случае, считаем вероятность выбора первым игроком первой чистой стратегии x, а второй 1 x. Если второй игрок выбирает одну из чистых стратегий, например j, то выигрыш первого игрока будет зависеть от выбранной им смешанной стратегии, то есть вероятности Второй игрок не захочет отдавать больше чем min(xa1 j + (1 x )a 2 j ), а первый будет стараться взять max min(xa1 j + (1 x )a 2 j ). Эти зависимости можно интерпретировать геометрически, если абсциссой взять ось x. Тогда каждая стратегия второго игрока будет отрезком прямой (16), при x (0,1).

точками (0, 2) и (1,1) (рис. 7.3).

Если каждой чистой стратегии j второго игрока отвечает свой отрезок прямой, то выражению min (x a1 j + (1 x ) a2 j ) отвечает нижняя окаймj ляющая семейства всех отрезков. Наивысшая точка этой ломаной отвечает тому значению, на котором достигается max min(x a1 j + (1 x ) a2 j ). Абсj цисса этой точки x является оптимальной смешанной стратегией первого игрока, а ее ордината – ценой игры H (рис. 7.4).

В точке ( x, H ) пересекается не меньше двух отрезков прямых. Это означает, что мы пришли к случаю игры 2 2, который рассмотрели ранее.

Отдельно отметим случаи, когда оптимальными стратегиями второго игрока являются чистые стратегии. Это случай, когда x лежит на одном отрезке (рис. 7.5).

Пример 7.4. Решить игру, заданную матрицей:

Первый игрок имеет 2 стратегии, второй 5 стратегий. Первый игрок может выбрать первую стратегию с вероятностью x, вторую стратегию с вероятностью (1 x ), где х (0,1). Второй игрок может выбрать пять чистых стратегий. Если он выбирает первую, то выигрыш первого игрока аналогично для второй чистой стратегии второго игрока выигрыш первого составляет:

Построим графики всех пяти линий (рис.7.7).

Легко видеть, что x лежит на пересечении второй и пятой линий.

Найдем их пересечение:

Это и есть оптимальная стратегия первого игрока. Для второго игрока игра свелась к игре 2 2 с матрицей, которая содержит только вторую и пятую чистые стратегии:

По формуле (7.14) получаем:

При этом цена игры по формуле (7.8) равна:

Вопросы для самоконтроля 1. Каковы этапы процесса принятия решения?

2. С помощью каких методов оценивают риск экономических ситуаций?

3. Что такое мера риска?

4. Алгоритм оценки риска с помощью дерева решений.

5. Определение безкоалиционной игры.

6. Что такое ситуация равновесия в игре?

7. Чем понятие „седловая точка” терии игр отличается от понятия „седловая точка” геометрии?

8. Доказать неравенство минимаксов.

9. Алгоритм нахождения седловых точек матрицы игры.

10.Решить игру, заданную матрицей 6 3.

11.Решить игру, заданную матрицей Литература для самостоятельной работы по данному разделу [7] – гл. 13, с. 217-245, [12] – часть 6, гл. 26, с. 474-503, [13] – часть IV, гл.

13, с. 234-256, [14] – гл. 3, с. 148-168, [19] – п. 26, с. 388-395.

8 ЛИНЕЙНАЯ РЕГРЕССИЯ. СИСТЕМЫ МАССОВОГО ОБСЛУЖИВАНИЯ

где a и b – параметры, подлежащие определению. Обычно эти величины определяются с помощью метода наименьших квадратов Функцию g (x ) называют среднеквадратической регрессией Y на X.

Линейная среднеквадратическая регрессия Y на X имеет вид:

где rxy – коэффициент корреляции случайных величин X и Y, равный отношению их корреляционного момента к произведению средних квадратичных отклонений этих величин:

Коэффициент b = rxy y / x называют коэффициентом регрессией Y на X, а прямую, реализующую линейную зависимость (8.3) случайной величины Y от случайной величины X – прямой среднеквадратической регрессии Y на X. Поскольку зависимость (8.3) является приближенной, то существует погрешность этого приближения, называемая остаточной дисперсией:

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

Найти линейную регрессию Y на X.

Таблица 8. Решение. Составим расчетную таблицу 8.2:

Таблица 8. Составим систему уравнений для определения a и b по формуле (8.3):

Линейная среднеквадратическая регрессия Y на X имеет вид: