Экономико-математические методы и прикладные модели

5.1. Системы массового обслуживания

Система массового обслуживания (СМО) это объект, характеризующийся наличием следующих элементов: 1) источник заявок или требований на обслуживание; 2) очередь; 3) обслуживающий аппарат (ОА).

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

Для описания сокращенных обозначений для однофазных СМО используется трехбуквенное обозначение вида A/B/m, где A и B описывают соответственно интервалы времени между поступлениями последовательных заявок и распределение времени их обслуживания; m - число каналов обслуживания. A и B принимают следующие значения:

M - экспоненциальное (показательное) распределение;

Б_г - распределение Эрланга порядка г;

D - детерминированное;

G - распределение общего вида.

Иногда указывают емкость очереди K и емкость источника заявок M. В этом случае используется пятибуквенное обозначение A/B/m/K/M. При отсутствии одного из двух последних индексов его значение предполагается сколь угодно большим.

СМО удобно описывать на основе диаграммы состояний, которая носит название «процесс гибели и размножения» (рис. 5.1).

' JLI1 Ц2 JLX3—

Рис. 5.1. Процесс гибели и размножения.

Состояние E_k обозначается овалом, в котором записывается число k. Переходы между состояниями обозначаются стрелками, на которых представлены интенсивности переходов.

Здесь - интенсивность потока заявок, поступающих в систему, находящуюся в состоянии с номером k (количество заявок, поступающих за единицу времени); ц_к - интенсивность обслуживания в системе, находящейся в состоянии с номером k (количество заявок, которые обслуживаются в среднем за единицу времени).

Решение этой системы в общем виде невозможно. Модель даже простой системы является чрезвычайно сложной и трудно анализируемой. Если рассматривать СМО более сложного вида, то вычислительные трудности будут еще более высокими. Поэтому обычно рассматривают решения системы уравнений Колмогорова в установившемся режиме при t—ro: dp(k;t)/dt—^0, p(k;t)—p(k)=const.

Выпишем некоторые формулы для систем массового обслуживания.

Вероятности состояний связаны между собой формулами

і—1

, к = 1...аэ.

р^(к ) = р(0)П

і=1 »і

Неизвестную константу p(0) найдем из условий нормировки: 1

р⁽⁰⁾ =

і-1

1+ІП

Для системы M/M/1 (диаграмма состояний представлена на рис. 5. 2) справедливы следующие формулы:

Xj = X = const и р₇ = р = const V/.

— = р < 1, получаем:

р

Тогда, обозначая отношение p(0) = 1- р, p⁽k) = (1- р)р^к,

к-1...00

Рис.5.2. Диаграмма интенсивностей переходов системы M/M/1.

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

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

Среднее число заявок в системе равно N =-, среднее время

пребывания заявки в системе: T

1 _ 1

X р(1 - р) р - А,

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

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

Для системы M/M/m диаграмма состояний представлена на рис. 5.3.

*(т-1)ц ГП|11.......

Рис. 5.4. Диаграмма интенсивностей переходов системы M/M/m. Имеем следующие формулы:

Р^(к ) =

, k<m

’к!

к

p(0)—m^m, к> m

m!

X

Здесь p = — < 1. m\x

Среднее число заявок в системе всегда можно найти как

N=Y,i-P⁽ⁱ⁾.

і=1

5.2. Линейное, целочисленное и нелинейное программирование

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

п

экстремум функции Ц = X ^аі^хі ^ехІГ при наличии следующих ог-

/=1

раничений:

п

Y^bjjXj < Cj, / = \ ...к; Xj > О V/. i-1

Рассмотрим пример такой задачи.

Имеется 150 л жидкости А и 150 л жидкости Б. Для получения одной бутыли смеси 1 нужно взять 2 л жидкости А и 1 л жидкости Б, а для получения одной бутыли смеси 2 нужно взять соответственно 1 л жидкости А и 4 - жидкости Б.Смесь 1 продаётся по цене 2 ден. единицы, а смесь 2 - 3 ден. единицы за одну бутыль. Сколько нужно приготовить бутылей каждой смеси, чтобы общая их стоимость была наибольшей, при условии, что число бутылей со смесью 2 не менее числа бутылей со смесью 1?

Введём следующие обозначения: х - количество бутылей первой смеси; х₂ - количество бутылей второй смеси. Стоимость бутылей первой смеси составляет 2х ден. единиц, а второй смеси - 3х ден. единиц, т. е. необходимо максимизировать целевую функцию (общую стоимость):

f( X) =2х₁ + 3х₂^ max.

Помимо указанной функции мы имеем ряд ограничений.

1- е ограничение: можно потратить не более 150 л жидкости А:

2х\ +Х2 <150

2- е ограничение: можно потратить не более 150 л жидкости В:

х\ + 4^2 < 150

3- е ограничение: число бутылей со смесью 2 не менее числа бутылей со смесью 1:

Хі - Х2 < 0

4- е ограничение: количество бутылей не может быть отрицательным:

х\ > 0, Х2 > 0

Таким образом, получаем следующую задачу: f( X) =2х₁ + 3х₂^ max при условиях

2 xi+ X2< 150 xi+ 4X2 < 150

Xi - X2< 0 xi > 0, X2> 0

К аналогичным задачам приводятся транспортные задачи. Они имеют, как правило, следующую формулировку.

Имеется n поставщиков и m потребителей. Каждый поставщик имеет запасы некоторого товара в объеме a_i, i=1...n, а каждому потребителю необходимо получить этого товара в объеме bj, j=1...m. Затраты на доставку одной единицы товара от поставщика № i к потребителю № j равны Су. Разработать план доставки товаров, минимизирующий издержки.

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

п т

Ц = Л Ъ^хч^сч ->min;

^l=¹j=¹

'и -

= Qi

j=i ^^XIJ ~^bj

1=1

Xj> 0 Vi, j

Если общие запасы у поставщиков меньше, чем суммарные потребности, то второе равенство заменяется на неравенство (<Zy). Если запасы превосходят потребности, то первое равенство заменяется на неравенство (<a_t).

Задачи такого типа решаются при помощи дисциплины, называемой «линейное программирование».

Иногда возникает задача с целочисленными переменными, например, когда необходимо распределить людей по объектам (невозможно поставить за прилавок 0,5 продавца или направить 1,3 курьера).

Такая задача является предметом рассмотрения разделом линейного программирования «целочисленное программирование».

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

5.3. Задачи экономического моделирования

Задача 5.1. Система массового обслуживания.

В цехе имеется два станка для обработки корпусных деталей. Интенсивность поступления деталей на обработку равна Х=6 дет/час, а интенсивность обработки деталей каждым станком равна р=4 дет/час. Нарисовать графы состояний и вычислить: коэффициент использования оборудования, среднее число занятых станков, среднее число деталей в очереди, среднее время пребывания детали в цехе, вероятности состояний, если:

а) имеется накопитель на две детали;

б) емкость накопителя не ограничена.

Решение.

На рис. 5.4 и рис. 5.5 представлены диаграммы состояний для первого и второго случаев соответственно.

Рис. 5.4. СМО с очередью (накопителем) на две заявки (детали) и двумя обслуживающими аппаратами (станками)

Рис. 5.5. СМО с неограниченной очередью (накопителем) и двумя обслуживающими аппаратами (станками)

1). Накопитель с ограниченной емкостью. ?і

В соответствии с общей теорией имеем: р_г = /? ,

Так как у нас два станка и две позиции в накопителе, то интенсивность поступления: Xq - Ay - ^2 = ⁼ ^4 ⁼ ^5 = О V/ > 4.

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

Интенсивность обслуживания:

Рі=р; \і2=2\і; рз=2р; р4=2р; Р5 = ... = О.

Это объясняется тем, что интенсивность обслуживания кратно количеству занятых одновременно станков. Если деталь одна, то р і

= р, если деталей больше, то р₇ = 2р, т.к. станков всего два и на обслуживании одновременно может быть не более двух деталей. Далее имеем:

.2

р = -; рі=рор, Р2=-РоР » Рз

¹ _з

Р 2^iU' 2² 2^:

Сумма всех вероятностей (в том числе и р₀) равна 1, т.е.

1 2 , 1 3 , 1 4

3

1. Ро¦ 1 + Р + -Р +туР +ТТР

Отсюда: ро

1 I 2 I 3 I 4

1 + P+ D +-р +—р

^к 2 ~>² ~>³

2²

2³

Вычислим это в Maxima.

(%І13) Lambda:6; (%о!3) 6

{ % i 14 ) Mu : 4 ;

(?ol4) 4

(%il5) Ro:Lambda/Mu; s

(%ol5J -

(%i24) float(%);

<%o24) 0.19601837672282

Итак, p₀=0.196.

Подставляя это значение, вычислим остальные вероятности:

Число занятых станков: N = р\ +2/?₂ + 2/>₃ + 2/?₄.

(%ІЗЗ) float (%);

(%оЗЗ) 1.313935681470138

Итак, среднее число занятых станков равно #=1,314.

Число деталей в системе: т = +2/?₂ + 3/>₃ + 4/>₄

С % 3.3 4) ш: sum (і*рС'*Ко^Лі/2^Л (і — 1) _r 1, 1, 4) _r float; <%o34) 1.727411944869832

Число деталей в очереди: К = /?₃ + 2/?₄

(%І35) К: рЗ+2*р4,float;

(%о35) 0.41347626339969

Время пребывания в цехе равно: Т = —

т

X

(%І36) - : m/Lambda;

(%о36) 0.28790199081164

2). В случае неограниченности емкости очереди

Xf = Х Vi, pi = 2р Vi> 2, pi =р.

Вероятности любого состояния не будут равны нулю. Условие

нормировки здесь: 'YjPi ⁼ 1 •

7 = 0

Тогда pi)'} l + p + 2^

Вычислим необходимые величины

rif) , simpsura;

{%І40) А:surn ( (Ro/2) ^Л i _fі,2

(%o40) —

4

(%І41) X:l+Ro+2 *A; f %o411 7

Исходя из общей теории, далее получаем: Среднее число деталей в системе:

m=Y;i- Рі= Ро i=1

Последовательно вычисляем:

Вычисление не происходит. Определим тогда функцию:

Вычислим несколько значений:

995069210034491643033576301547[5960 digits;967392663303723030415351577344 (%І51)

(%о5 I) 11.25 (%І52 > Х(100),float;

(%o52) II .24999999589994

Как видно, скорость сходимости ряда большая, возьмем его

значение Y=11,25:

(%І55) Y:%oSl (%o55) 11.25

Далее:

(%І56> m:pO*{Ro+2*Y);

(%o56) 3.428571428571428

Среднее число занятых станков: N = 2- 2р₀ - рі:

(%І57) N:2-2*pO-pO*Ro;

3

(%о57) -2

Среднее число деталей в очереди: К = т-N:

(%І58} К:ш-М;

(%о58) I.928571428571428

Время пребывания в цехе равно: T

Ответ: а) po, pi, p2, Рз, Р4 равны: 0.196, 0.294, 0.221, 0.165, 0.124;

число занятых станков N = 1.314; число деталей в системе m = 1.727; число деталей в очереди K = 0.413; коэффициент использования (N/2)= 0.657; время пребывания в цехе= 0.288. б) р₀ равно: 0.143; число занятых станков = 1.5; число деталей в системе = 3.428;

число деталей в очереди = 1.929; коэффициент использования = 0.75; время пребывания в цехе = 0.571.

Задача 5.2. Задача линейного программирования.

Для сохранения нормальной жизнедеятельности человек должен в сутки потреблять белков не менее 120 условных единиц (усл. ед.), жиров - не менее 70 и витаминов - не менее 10 усл. ед. Содержание их в каждой единице продуктов П и П 2 равно соответственно (0,2; 0,075; 0) и (0,1; 0,1; 0,1) усл. ед. Стоимость 1 ед. продукта П - 2 руб., П2 -3 руб.

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

Решение. Составим экономико-математическую модель.

Пусть х₁ - количество единиц продукта П_ь х₂ - количество единиц продукта П2.

Целевая функция - стоимость питания: Ц=2 х\+3 х₂-^тт.

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

1) необходимо потреблять не менее 120 единиц белка

0.2 х₁+0.1 х₂ > 120

2) необходимо потреблять не менее 70 единиц жиров

0.075 х₁+0.1 х₂ > 70

3) необходимо потреблять не менее 10 единиц витаминов

0.1 х₂ > 10

4) обе переменные неотрицательные

х₁ > 0, х₂ > 0

Для решения используем электронные таблицы OpenOffice.org

Calc.

На рис. 5.6 представлена исходная информация, необходимая для решения задачи.

В ячейках А3 и В3 установлены нули как начальное приближение. В ячейках А7 и А8 помещены коэффициенты целевой функции (2 и 3 соответственно). В ячейках А11:В13 помещены коэффициенты всех трех ограничений.

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

В ячейках F11:F13 помещены правые части ограничений.

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

Если посмотреть на нашу таблицу (рис. 5.6) и формулу целевой функции, то можно записать: Ц=А7*А3+В7*В3.

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

^ Без имени 1 -OpenOffice.org Calc Файл Правка Вид Вставка Фодмат Сервис Данные Окно Справка L ^т Ш У ^ щ - - : |?р АгіаІ [у~| т [?] ж К ч іі Jb D13 А В 1 D 1 F 1 Переменные 2 Х1 Х2 3 0 0 4 5 Коэффициент ы Значение 6 целевой фунь щи и целевой функ щи и 7 2 3 в 9 Коэффициент ы Значение Знак Правая 10 ограничений левой части неравенства часть 11 0,2 0 1 >= 120 12 0 08 0 1 >= 70 ¹³ 0 0 1 >= 10 Рис. 5.6. Исходная информация для решения задачи линей ного программирования

Поместим формулу вычисления целевой функции в ячейку D7. Устанавливаем курсор в эту ячейку, печатаем символ «=», появляется на строке ввода кнопка ввода функции «f». Нажимаем ее и в «Категории» «Массив» выбираем функцию SUMPRODUCT (рис. 5.7).

После нажатия кнопки «Далее>>» появляется окно ввода параметров (рис. 5.8).

Рис. 5.8. Выбор функции SUMPRODUCT

Рис. 5.9. Окно ввода аргументов После нажатия правой кнопки в окне ввода «Массив 1» на рабочем листе активизируется окно ввода первого набора (рис. 5.9).

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

Мастер функций - SUMPRODUCT( Массив 1

Рис. 5.9. Выбор аргументов

То же выполняем и для второго массива. Это - коэффициенты целевой функции, т.е. ячейки А7:В7.

Завершается операция нажатием кнопки «ОК» (рис. 5.10).

Рис. 5.10. Завершение операции

Точно также в ячейки D11:D13 вводятся формулы для вычисления левых частей неравенств.

Введенные формулы показаны на рис. 5.11.

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

И л

= I =SUMPRODUCT($A$3:$B$3;A7:B7) В с Е F •А 1 2 Х2 3 0 4 = 5 Ы Значение' 6 :ции целевой функции 3 =SUMPRODUCT($AS3 SBS3 A7 В7) в 9 Ы Значение Знак Правая 10 левой части неравенства часть 11 0.1 =SUMPRODUCT(SA$3:$B$3:A11 :В11) >= 120 12 0.1 =SUMPRODUCT($A$3:$B$3:A12:B12) >= 70 13 0.1 =SUMPRODUCT($A$3 $В$3:А13:В13) >= 10 14 15 I . М [ЙІГЛИМ .Листі, ЛИСТ2 ЛистЗ J<

Лист 1/3 Базовый

100%

1ІСТАНДІ Г*~1

Сунна=0 Рис. 5.11. Отображение введенных формул

= =SUMPRODUCT($A$3:$B$3;A7:B7) А В С Е F 1 Переменные

Х1

0 2 Х2 3 0 4 5 Коэффициент ы Значение 6

В целевой функции целевой Ф?нк ции 2 3 0 — *— 9 Коэффициент ы Значение Знак Правая 10 ограничений

0,2

0.08

0 левой части неравенства часть 11 0.1 0 >= 120 12 0.1 0 >= 70 13 0.1 0 >= 10 14 15

0Е Гм[н]\Лист1 Лисг2 ЛисгЗ / < Лист 1! 3 БсЗОЕЫЙ 100% СТАНД * Сумма= Рис. 5.12. Вид рабочей области после ввода формул

Для решения задачи необходимо вызвать соответствующий мастер последовательностью выбора команд меню: «Сервис» ^«Поиск решения».

Появляется соответствующая панель (рис. 5.13).

В окне «Целевая ячейка» указываем ее адрес: D7.

В пункте «Оптимизация результата» помечаем окошко «Минимум».

В окне «Путем изменения ячеек» указываем адреса наших переменных А3:В3.

Рис. 5.13. Ввод целевой функции и ограничений в мастер поиска решений. В окнах ввода ограничений под общим именем «Ограничительные условия» указываем:

в окнах «Ссылка на ячейку» вводим адреса ячеек, в которых содержатся формулы вычисления левых частей неравенств (D11:D13);

в окнах «Операция» выбираем либо знаки неравенств, либо типы переменных;

в окнах «Значение» указываем адреса ячеек, в которых находятся числовые ограничения неравенств (F11:F13);

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

После нажатия кнопки «Решить» появляется сообщение о результате работы программы (рис. 5.14).

Рис. 5.14. Информационное сообщение о выполнении программы

После нажатия кнопки «Сохранить результат» происходит возврат в рабочий лист, на котором сохранены результаты расчета (рис. 5.15).

Итак, было получено, что нужно 800 единиц первого продукта и 100 единиц второго продукта. При этом, минимальные расходы составят 1900 денежных единиц. А В С Е F 1 Переменные 2 Х1 Х2 3 800 100 4 5 Коэффициент ы Значение & целевой фуы сци и целевой функ ции 2 3 1Э00 Э 9 Коэффициент ы Значение Знак Правая 10 ограничений левой части неравенства часть 11 0,2 0 1 170 :>= 120 12 0 08 0 1 70 >= 70 13 0 0 1 10 :>= 10 Рис. 5.15. Результаты расчета Все ограничения выполнены, причем два последних дали равенство, а первое - строгое неравенство.

Задача 5.3. Транспортная задача

Три электрогенерирующие станции мощностью 25, 40 и 30 миллионов кВт-ч поставляют электроэнергию в три города. Максимальная потребность в электроэнергии этих городов оценивается в 30, 35 и 24 миллионов кВт-ч. Цены за миллион кВт-ч в данных городах приведены в табл. 5.1.

Стоимость за электроэнергию, руб./млн.кВт-ч

Таблица 5.1. Города 1 2 3 Станция 1 600 700 400 2 320 300 350 3 500 480 450 В августе на 20% возрастает потребность в электроэнергии в каждом из трех городов. Недостаток электроэнергии могут восполнить из другой электросети по цене 1000 за 1 миллион кВт-ч. Но третий город не может подключиться к альтернативной электросети. Электрогенерирующие станции планируют разработать наиболее экономичный план распределения электроэнергии и восполнения ее недостатка в августе. Сформулируйте эту задачу в виде транспортной модели.

Решение. Добавим четвертую станцию из альтернативной сети, учтем возросшие потребности городов и составим новую таблицу:

Таблица 5.2.

Таблица транспортной задачи

Станция Мощность Города 1 2 3 1 25 600 700 400 2 40 320 300 350 3 30 500 480 450 4 11,8 1000 1000 - Потребности города 36 42 28,8 Процедуру оптимизации проведем при помощи электронных таблиц OpenOffice.org Calc.

Сначала сформулируем экономико-математическую модель задачи.

1. Введем четвертую станцию, мощность которой достаточна для удовлетворения потребностей: (36+42+28,8)-(25+40+30)=11,8.

Из суммы потребностей вычли сумму имеющихся мощностей.

2. Обозначим Xj - количество электроэнергии (в млн. квт-час), поставляемое от станции № i в город № j.

3. Обозначим aj - стоимость одного млн. квт-час электроэнергии, при поставках от станции № i в город № j.

4 3

4. Составим целевую функцию: Ц = ^ ^^aij^xij —>min

'=1.7=1

5. Составим ограничения:

4

а) ⁼ ^7 ’ ^1 ⁼ 36, &2 ⁼ 42, 63 = 28,8 - каждому городу нуж-7=1

но поставить столько, сколько требуется;

40, <2₃

3

б) Х^х7/ ^=аі ’ ^а1 ⁼25, <т₂7=1 30, <2₄ = 11,8 - каждая стан- ция поставила то, что могла.

в) X43 =0 - третий город не может получать энергию от четвер

той станции;

г) Ху >0 V/, / - объемы поставок не могут быть отрицатель

ными.

На рис. 5.16 представлена подготовительная часть работы.

Целевая функция находится как сумма произведений объемов поставок на их стоимость или SUMPRODUCT(B4:D7;B13:D16). Эта формула помещена в ячейку D18 (рис. 5.17).

Аналогично вводятся формулы для расчета левых частей ограничений. Например, в ячейке В9 находится сумма ячеек В4:В7 (это сумма поставок в первый город от каждой станции). Аналогичные суммы находятся в ячейках C9 и D9.

В ячейке F4 находится сумма ячеек B4:D4 (количество отгруженного со станции № 1). В ячейках F5:F7 находятся объемы поставок со станций 2, 3, 4 соответственно.

После ввода рабочих формул вызываем мастер поиска решений (Решатель) через пункты меню «Сервис» —>«Поиск решения».

А В С Е 1 Объемы тран спортировки электроэнерп ІИ 2 Города Мощность 3 Станции 1 2 3 станции 4 1 0 0 0 25 5 2 0 0 0 40 6 3 0 0 0 30 7 4 0 0 0 11,8 8 Потребности 36 42 28,8 9 10 Цена транспс іртировки 11 Города 12 Станции 1 2 3 13 1 600 700 400 14 2 320 300 350 15 3 500 480 450 16 4 1000 1000 0 17 18 Целевая фун кция ц= Рис. 5.16. Подготовка таблицы транспортной задачи D18

\y] fx Ж = =SUMPR0DUCT(B4-: D7;B13: D16; А В 1 D 1 F 1 Объемы тран с портировки электроэнерп и 2 Города Мощность 3 Станции 1 2 3 станции Отгрузили 4 1 0 0 0 25 0 5 2 0 0 0 40 0 6 3 0 0 0 30 0 7 4 0 0 0 11.8 0 В Потребности 36 42 28,8 9 Доставка: 0 0 0 10 Цена транспс ртировки 11 Города 12 Станции 1 2 3 13 1 600 700 400 14 2 320 300 350 15 3 500 480 450 16 4 1000 1000 0 17 18 Целевая фун кция ц= 0 Рис. 5.17. Ввод рабочих формул

На панели «Решатель» (рис. 5.18) вводим адрес целевой функции (D18), указываем, что необходимо найти минимум, отмечаем ад

реса переменных (B4:D7) и вводим ограничения.

Первое окно содержит сразу три ограничения (п. 5а), второе -четыре (п. 5б), третье - х₄₃=0 (п. 5в), четвертое - все переменные не-

отрицательные

Рис. 5.18. Ввод параметров и ограничений.

После нажатия кнопки «Решить» появится информационное сообщение о найденном решении (рис. 5.19).

Рис. 5.19. Информационное сообщение

Результаты расчетов появятся после нажатия кнопки «Сохранить результат» (рис. 5.20). D1& [vj fy ^ = =SUMPR0DUCT(B4:D7;B13: D16) А В с Е F 1 Объемы тран сперт ровки электр оэнерп и 2 Г орода Мощность 3 Станции 1 2 3 станции Отгрузили 4 1 0 0 25 25 25 5 2 24,2 15.8 0 40 40 6 3 0 26,2 3,8 30 30 7 4 11-8 0 0 11,8 11.8 В Потребности 36 42 28,8 9 Доставка: 36 42 28,8 10 Цена транспс ртировки 11 Г орода 12 Станции 1 2 3 13 1 600 700 400 14 2 320 300 350 15 3 500 480 450 16 4 1000 1000 0 17 18 Целевая фун кция Ц= 48570 1C 1- Рис. 5.20. Результаты расчетов

Как видно из рис. 5.20, все ограничения выполнены, минимальные затраты составляют 48570 единиц.

Задача 5.4. Задача о назначениях

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

Таблица 5.2

Бальные оценки эффективности работы рабочих на станках

Станок 1 2 3 4 5 Рабочий 1 5 5 — 2 2 2 7 4 2 3 1 3 9 3 5 — 2 4 7 2 6 7 8 Решение.

Решим эту задачу в табличном процессоре Gnumeric.

Первый шаг: подготовка исходных данных и ввод функций (рис. 5.21).

Сначала оформим две таблицы.

«Таблица эффективности» (ячейки A1:F7) содержит исходную табл. 5.2. Отличие - прочерки были заменены нулями (ячейки D4, E6).

«Таблица назначений» (ячейки A9:F15) в ячейках A12:F15 содержит переменные назначения. Числа в этих ячейках могут принимать только два значения: 1 - если рабочий распределен на работу с данным станком; 0 - если не распределен. Изначально везде ставим нули.

Р? *Primer_5_4.gnumeric : Gnumeric

Файл Правка Вид Вставка Формат Сервис Данные Справка

ІП

100%

ІЕЙ П

bans А В С D Е F G Н 1 Таблица эфе эективности 2 Ni станка 3 N° рабочего 1 2 3 4 5 4 1 5 5 0 2 2 5 2 7 4 2 3 1 6 3 9 3 5 0 2 7 4 7 2 6 7 S 0 9 Таблица назначений 10 Nl станка Сумма Границы 11 Ns рабочего 1 2 3 4 5 12 1 0 0 0 0 0 0 1 13 2 0 0 0 0 0 0 1 14 3 0 0 0 0 0 0 1 15 4 0 0 0 0 0 0 1 16 Сумма 0 0 0 0 0 17 Границы 1 1 1 1 1 IS 19 Целевая функиия= 0 Рис. 5.21. Подготовка исходных данных.

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

«=sumproduct( Лист 1!B4:F7; Лист 1!B12:F15)»

В строке «Сумма» в ячейках B16:F16 содержатся суммы переменных назначения по столбцам. Так, в ячейке В16 содержится сумма ячеек В12:В15 (количество назначений на первый станок). Эта величина вычисляется при помощи функции SUM: «=sum(B12:B15)».

В столбце «Сумма» в ячейках F12:F15 содержатся суммы горизонтальных ячеек (общее количество назначений для каждого рабочего). Это задается той же функцией. Например: «=sum(B12:F12)» -сумма ячеек B12:F12, которая находится в ячейке G12.

Строка и столбец «Границы» указывают граничные значения для количества назначений: в строке - количество людей на один станок; в столбце - количество станков на одного человека.

Второй шаг: решение оптимизационной задачи.

Для решения оптимизационных задач в таблицах Gnumeric имеется программа Solver. Она вызывается через пункты меню «Сер-вис»==> «Решение». Появляется панель «Solver» (рис. 5.22).

Первая вкладка - «Параметры».

Рис. 5.22. Установка основных параметров.

В строке «Установить целевую ячейку» устанавливаем адрес нашей целевой функции С19.

В строке «Равняется» делаем выбор пункта «Макс».

В строке «Изменяя ячейки» указываем диапазон адресов ячеек переменных назначения B12:F15.

Затем переходим на вкладку «Модель» (рис. 5.23).

Рис. 5.23. Установка параметров модели.

Выбираем пункты: «Линейная модель», «Предполагать НЕ отрицательность», «Предполагать целочисленность», «Алгоритм: Simplex».

Пункт «Квадратичная модель» НЕ РАБОТАЕТ.

И, наконец, переходим на вкладку «Ограничения» (рис. 5.24) и вводим ограничения модели.

Рис. 5.24. Ограничения модели. 1- е ограничение: переменная назначения D12 (назначение первого рабочего на третий станок) равна нулю (D4 у нас равна нулю).

2- ограничение: переменная назначения Е14 (назначение третьего рабочего на четвертый станок) равна нулю.

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

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

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

После ввода ограничения следует нажать кнопку «Добавить».

Затем очистить нижнюю строчку и ввести следующее ограничение и т.д.

ЗАМЕЧАНИЕ: при вводе ограничений в Solver нельзя использовать числа, только ссылки на ячейки!

Окончив ввод ограничений нажмем кнопку «Решить» и появится информационное сообщение о том, что решение найдено (рис. 5.25).

Рис. 5.25. Информационное сообщение. После нажатия кнопки «ОК» решение будет выведено на рабочий лист (рис. 5.26).

Рис. 5.26. Решение задачи.

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

Задача 5.5. Модель Леонтьева межотраслевого баланса

В табл. 5.3 приведены первый (x ) и второй (у ) квадранты

U s J

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

Необходимо:

1. Рассчитать объёмы валовой продукции отраслей.

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

3. Найти матрицу коэффициентов полных затрат.

4. Рассчитать объёмы условно чистой продукции отраслей.

5. Представить в таблице полную схему межотраслевого баланса.

Таблица 5.3.

Производящие Потребляющие отрасли Конечная

продукция отрасли 1 2 3 1 200 50 300 200 2 150 250 0 100 3 230 50 150 300 Решение. Решение будем проводить в таблицах Gnumeric. Составим необходимые исходные таблицы (рис. 5.27).

А В С D Е 1 Производящие Потребляющие отрасли Конечная 2 отрасли 1 2 3 продукция 3 1 200 50 300 200 4 2 150 250 0 100 5 3 230 50 150 300 Рис. 5.27. Таблица исходных данных.

Пусть Ху - межотраслевое потребление (ячейки B3:D5). Эти коэффициенты занесем в матрицу

x = *11

*21 *12

*22 *13

*23 ₌ 200

150 50

250 300

0 *31 *32 ^*33 230 50 150 Конечную продукцию обозначим вектором Y = У\ У2 — 200

100 Y3 300 Задание 1. Рассчитать объёмы валовой продукции отраслей.

Х\

х₂

X 3

Обозначим вектор валовой продукции X

Элементы этого вектора определяются по формуле:

п

Xj = 'ZjXjj + Yj, / = 1 ...п.

7=1

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

Добавим столбец валовой продукции и поместим в элементы столбца вышеуказанную формулу (рис. 5.28).

Рис. 5.28. Расчет валовой продукции.

Формулу «=sum(B3:E3)» и другие (в ячейках F4, F5) можно ввести либо вручную, либо через вставку формулы. 750

Итак, вектор валовой продукции равен X =

500 730

Задание 2. Рассчитать матрицу коэффициентов прямых затрат. Матрица коэффициентов прямых затрат вычисляется по фор-

муле

а_п ^a12 ^a13 А = ^а2\ ^a22 ^a23 ^a31 ^a32 ^a33 ^aij - ^ХУ

Л7*

/,7 = 1...3

Результаты расчетов представлены на рис. 5.29. В& U # = =B3/$F$3 А В С D Е F 1 Производящие Потребляющие отрасли Конечная Валовая 2 отрасли 1 2 3 продукция продукция 3 1 200 50 300 200 750 4 2 150 250 0 100 500 5 3 230 50 150 300 730 6 7 8 Матрица коэффи- 0,266667 0,100000 0,410959 9 циентов прямых 0,200000 0,500000 0,000000 10 затрат А 0,306667 0,100000 0,205479 11 Рис. 5.29. Расчет матрицы коэффициентов прямых затрат.

Как видим, она равна А =

0,266667 0,100000 0,410959 0,200000 0,500000 0,000000 0,306667 0,100000 0,205479

Задание 3. Найти матрицу коэффициентов полных затрат Матрица коэффициентов полных затрат равна B=(E-A)"¹, где Е

- единичная матрица.

На рис. 5.30 представлены матрицы E и (E-A).

Матрица А находится в ячейках B8:D10, а единичная матрица

- в ячейках B12:D14. Нам необходимо попарно вычесть элементы матрицы А из элементов матрицы Е.

Помещаем в ячейку В16 формулу «=В12-В8». Затем копируем ее и вставляем ее во все ячейки, где должна быть разность матриц (B16:D18).

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

t 3 Матрица коэффи- 0,266667 0,100000 0,410959 9 циентов прямых 0,200000 0,500000 0,000000 10 затрат А 0,306667 0,100000 0,205479 11 12 Единичная 1,000000 0,000000 0,000000 13 матрица Е 0,000000 1,000000 0,000000 14 0,000000 0,000000 1,000000 15 16 Разность Е-А 0,7333 -0,1000 -0,4110 17 -0,2000 ' 0,5000 0,0000 13 -0,3067 -0,1000 0,7945 Ч Г-1 Рис. 5.30. Матрицы А, Е и Е-А.

Теперь нам необходимо найти обратную матрицу. Эти действия описаны в задаче 2.3. Результаты расчета представлены на рис. 5.31. 15 16 Разность Е-А 0,7333 -0,1000 -0,4110 17 -0,2000 0,5000 0,0000 13 -0,3067 -0,1000 0,7945 19 20 Обратная матри- 1,945433 0,590340 1,006261 21 ца В=(Е-А)^Л-1 0,773175 2,236136 0,402504 22 0,343337 0,509302 1,697674 74 Рис. 5.31. Матрица коэффициентов полных затрат.

Итак, матрица коэффициентов полных затрат равна Задание 4. Рассчитать объёмы условно чистой продукции отраслей

Объемы условно чистой продукции отраслей рассчитываются

3

по формулам 2j = Xj-Y.x₀ . Результаты расчета представлены на

7=1

рис. 5.32.

Рис. 5.32. Расчет условно чистой продукции.

Как видно из строки формул, в ячейку В24 помещена формула 1,945438

0,778175

0,848837

0,590340

2,236136

0,509302

1,006261

0,402504

1,697674

«=F3-sum(B3:B5)». По ней из валовой продукции первой отрасли вычитается сумма потребления первой отрасли. И т.д. для второй и третьей.

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

170 150 .

280

Задание 5. Представить в таблице полную схему межотраслевого баланса (в соответствии с принципиальной схемой МОБ).

Итог всех наших расчетов может быть представлен в табл. 5.4.

Схема межотраслевого баланса

Таблица 5.4. Производящие Потребляющие

отрасли Конечная

продукция Валовая

продукция отрасли 1 2 3 1 200 50 300 200 750 2 150 250 0 100 500 3 230 50 150 300 730 Условно чистая продукция 170 150 280 600 Валовая продукция 750 500 730 1 980 Задача 5.6. Формирование портфеля ценных бумаг

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

Постановка задачи. Инвестор может вложить определенную сумму денег в приобретение пакетов акций нескольких (n) компаний. На основании анализа рынка и характеристик ценных бумаг было установлено, что средние значения ставок дохода равны соответственно ш_і, i=\...n, а их стандартные отклонения (которые, собственно, и являются риском ценной бумаги) - а_г, / 1.. п. Также необходимо знать зависимости характеристик ценных бумаг друг от друга, которые выражаются через ковариационную матрицу (COV) или матрицу коэффициентов парной корреляции (R=||ry||, і, j=1... n).

Тогда доходность (или эффективность) портфеля ценных бумаг определяется как

m,

хцп_г і=1

Риск портфеля (или стандартное отклонение ставок дохода по портфелю) рассчитывается следующим образом:

<т

= 4х^Т cov х = п—\ П

i=1

i=l j=i+l

Здесь и выше вектор X^T=(x_b x₂, ..., x_n) - вектор долей инвестиций, помещенных в каждый из видов актива (портфельные веса).

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

= 1, х_г >0 V/.

і=1

Теперь можно сформулировать задачу.

Сформировать портфель минимального риска с доходностью не менее 8% из ценных бумаг трех типов. Исходные данные приведены ниже (см. табл. 5.5, табл. 5.6).

Таблица 5.5.

Параметры ценных бумаг

Наименование ABC CDE EFG Доходность, m,

(%) 12 7 11 Риск, аі 25 10 20 Таблица 5.6.

Матрица коэффициентов корреляции

ABC CDE EFG ABC 1 0,52 0,27 CDE 0,52 1 0,75 EFG 0,27 0,75 1 Целевая функция имеет вид:

ег,

СТІ =?х^т со? х =

n—\ n

min

^xf • <т² + 2 • ^ 2>, • jc, • r, • <T, • <T,

i=1

i=1 7=i+1

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

12 • x^\- 7 • x₂ +11 x₃ >8 x^\- x₂+ x₃ =1 Xj, x₂, x₃ > 0

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

Шаги решения следующие.

1) Формируем таблицы 5.5 и 5.6.

2) Резервируем место для изменяемых переменных x_h x₂, x₃.

3) Транспонируем строку изменяемых переменных.

4) Рассчитываем матрицу ковариаций по формуле

СО?„ = <7 =r₉-<j,-a_J

5) Вычисляем дисперсию портфеля как функцию трех переменных (xi, x₂, x₃):

п—1

D = ^=IX-^²+2-Z X

x_i-x_]-r_i]-(j_rcj_j

X^х COV X

i=1 i=1 j=i+1

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

На рис. 5.33 представлен общий вид рабочего листа.

На рис. 5.34 представлены все введенные формулы.

После подготовки данных вызываем мастер поиска решения через пункты меню «Данные» ==> «Поиск решения». Появляется панель «Поиск решения» (рис. 5.35).

В строке «Установить целевую ячейку» указываем адрес В27 -в ней находится формула расчета дисперсии портфеля.

Помечаем «Равной минимальному значению».

В окне «Изменяя ячейки» указываем адреса переменных (B14:D14).

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

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

После нажатия кнопки «ОК» на рабочем листе появляются числовые данные решения (рис. 5.38).

А Б С D I 1

jl Таблица 1. 2 Параметры ценных бумаг з Наименование АВС CDE EFG 4 Доходность, ті (%) 12 7 11 Б Риск, оі 25 10 20 6 Таблица 2 7 Матрица коэффициентов корреляции Б АВС CDE EFG 3 АВС 1 0,52 0,27 1C CDE 0,52 1 0.75 11 EFG 0,27 0,75 1 d * * Пример 5_6_Портфель ценных бума V L_ йЛ /

Главная Вставка Разметка страницы Формулы Данные Р У ш

Сводная Таблица таблица ^т ІЙІ Клип

¦Лкй

-У Фигуры ”

Рисунок

SmartArt д рл" График ^т С обла

іш „ 1

45 Круговая * |7? Точен

Гистограмма — -

—f> Линейчатая * IJ Други Таблицы Иллюстрации Диаграммы J30 12 Изменяемые переменные 13 Х1 Х2 ХЗ 14 0 0 0 1Б Транспонированный вектор изменяемых переменных 16 Х1 0 17 Х2 0 13 ХЗ 0 13 Таблица 3 2С Матрица ковариаций 21 625 130 135 22 СО?= 130 100 150 23 135 150 400 2^L Доходность портфеля 23 771= 0 26 Дисперсия портфеля 27 D= 0 23 Ограничения 23 1. Х1+Х2+Х3=1 0= 1 36 2. 12*Х1+7*Х2+11*ХЗ<20 0> 8 31 З.Х1,Х2,ХЗ >0 Рис. 5.33. Подготовка исходных данных и формул.

А В С D 1 Таблица 1. 2 Параметры ценных оумаі 2 Наименование АВС CDE EFG 4 Доходность, ті (%) 12 7 11 С Риск, si 25 19 20 6 Г аблнца 2 7 Матрица коэффициентов S АВС CDE EFG 5 ЛВС 1 0.52 0427 1C CDE 0,52 1 0,75 11 EFG 0427 0,75 1 12 Изменяемыепеременньп 1? XI X2 X3 14 0 0 0 1Е Транспонированный век: 1? XI =B14 17 Х2 =CU 13 ХЗ =D14 19 Г асипща б 2С Матрица ковариации 21 =В9*В5*В5 =C9*B5*C5 =D9*B5*D5 22 СО?= =В10*В5*С5 =C10*C5*C5 =D10*C5*D5 2? =B11*B5*D5 =C11*C5*D5 =Dll*D5*D5 24 Доходность портфели 23 т= =С?ММПГОИЗВ(В14Т1 14;B4:D4.) 23 Днсперснл портфеля 27 D= =МУМНОЖ(В 14 :D 14 ;МУМНОЖ(В21 :D23 :С IOC 1 5» 23 Ограничения 29 1 Х1+Х2+Х3=1 =СУММ(В 14-D14) = 1 :с 2.12*Х 1-7 *Х2+11 *X3?S =С\Ъ1МПГОИЗВ(В14Т114;B4:D4) > 3 31 3 Xl,X2,X3^s0 II Рис. 5.34. Расчетные формулы.

Рис. 5.35. Установка параметров мастера поиска решения.

Рис. 5.36. Панель ввода ограничений.

Рис. 5.37. Информационное сообщение. 12 Изменяемые переменные 12 XI Х2 ХЗ 14 0', 111938 0.77985 0,10077 15 Транспонированный вектор изменяемых переменных 16 XI 0', 11938 17 Х2 0,77985 13 ХЗ 0', 10077 19 Таблица 3 20 Матрица ковариаций 21 625 130 135 22 со?= 130 100 150 22 135 150 400 24 Доходность портфеля 22 т= 8 2с Дисперсия портфеля 27 D= 124,816 23 Ограничения 25 1. Х1+Х2+Х3=1 1 - 1 30 2. 12*Х1+7*Х2+1ГХЗ<20 8 > 8 21 3. XI, Х2, ХЗ >0 Рис. 5.38. Результаты решения. Итак, на акции ABC следует потратить 12% капитала, на акции CDE - 78%, на акции EFG - 10%. Доходность составит 8%, а минимальная дисперсия - 124,8.