Предисловие
В условиях рыночной экономики существует высокая степень
неопределенности экономического поведения субъектов рынка.
Разработка и осуществление эффективных управленческих решений,
на основе оценки возможных в будущем ситуаций и выбора
из нескольких альтернативных вариантов решений, является важнейшей
предпосылкой обеспечения конкурентоспособности выпускаемой
продукции, осуществления обоснованной кадровой политики
и рационализации других сторон деятельности организации.
В связи с чем, дисциплина «Методы оптимальных решений»
является важной составляющей системы фундаментальной
подготовки современного экономиста, обеспечивающей ему профессиональную
мобильность.
Предлагаемое учебное пособие подготовлено в соответствии
с требованиями Федерального государственного образовательного
стандарта высшего профессионального образования и программой
курса «Методы оптимальных решений» для студентов высших
учебных заведений, обучающихся по направлению подготовки
080100.62 «Экономика».
Цель пособия – повышение уровня математической подготовки
студентов, усвоение знаний и формирование навыков в области
использования оптимизационных моделей для принятия экономически
целесообразных управленческих решений в различных ситуациях.
В
результате изучения данного пособия студент должен: знать
типы экономических задач, решаемых с помощью методов оптимальных
решений, основные математические методы анализа принятия
решений; уметь перейти от прикладной экономической задачи
к математической модели, выбирать рациональные варианты
действий в практических задачах принятия решений; владеть методами
построения математических моделей типовых профессиональных
задач. Материал книги направлен на формирование
у студентов следующих профессиональных компетенций: способности
осуществлять сбор, анализ и обработку данных, необходимых
для решения поставленных экономических задач (ПК-4); способности
выбирать инструментальные средства для обработки
экономических данных в соответствии с поставленной задачей,
3
Стр.1
анализировать результаты расчетов и обосновывать полученные
выводы (ПК-5); способности на основе описания экономических
процессов и явлений строить стандартные теоретические и эконометрические
модели, анализировать и содержательно интерпретировать
полученные результаты (ПК-6).
Пособие состоит из 4 разделов, охватывающих методы линейного,
динамического и выпуклого программирования, элементы
теории графов и матричных игр.
Каждый раздел пособия содержит основные положения теории,
формулы, определения, теоремы, необходимые для решения
задач. Поскольку выпускники вузов по экономическим специальностям
в будущей профессиональной деятельности будут встречаться
с математическими методами оптимизации главным образом
как пользователи, а не разработчики, в данном пособии основное
внимание уделяется приложениям математических методов
в экономике, а не их подробному теоретическому обоснованию.
В книге приводятся подробные решения типовых задач различной
степени трудности, поясняющих теоретический материал; большое
(достаточное) количество содержательных примеров, иллюстрирующих
приемы математического моделирования экономических
ситуаций с последующим анализом полученных результатов;
вопросы для самоконтроля и задачи для самостоятельного решения,
позволяющие закрепить приобретенные на практических занятиях
навыки решения задач и оценить степень подготовленности
по данной теме.
Материалы пособия имеют прикладную направленность и
найдут конкретное применение в общепрофессиональных и специальных
дисциплинах, посвященных микро- и макроэкономике, государственному
управлению и экономике общественного сектора,
фондовому рынку и финансовому менеджменту, институциональной
экономике и ряду других научных областей.
4
Стр.2
1. Линейное программирование
1.1. Математическая модель задачи линейного
программирования
Задача линейного программирования (ЗЛП) в общем виде
формулируется следующим образом: найти условный экстремум
(максимум или минимум) линейной целевой функции n переменных
f
x = 1 1 + 2 2
( )
a x a x + + 1a x ≤ = ≥ b1
21 1 + 22 2
11 1 + 12 2
a x a x + + a2 x ≤ = ≥ b2
................................................
...
...
где коэффициенты c c ,...,c n ; a a ,...,a mn ; b b ,...,b m – заданные
числа, а величины x x ,..., x n – неизвестные. Каждое из ограam
x am x + + a x ≤ = ≥ b ,
1, 2
1 1 +
2 2
1, 2
ничений системы – одно из трех возможных (≤ = ≥,,
(2) называется математической моделью ЗЛП.
Любой набор чисел
1, 2
).
Совокупность целевой функции (1) и системы ограничений
x x ,..., x n , удовлетворяющий системе
ограничений (2), называется допустимым решением ЗЛП.
Допустимое решение, на котором достигается требуемый экстремум
целевой функции (1), называется оптимальным решением
ЗЛП.
Множество всех допустимых решений ЗЛП называется областью
допустимых решений (ОДР).
Общая ЗЛП допускает ограничения всех видов и уравнения, и
неравенства.
В том случае, когда все переменные неотрицательны (
n
xi ≥ 0 ,
j =1, ), а система ограничений (2) состоит только из неравенств,
ЗЛП называется стандартной.
5
...
mn n ( , , ) m
11, 12
1, 2
n n
n n
c x c x + + → max(min)
...
и соответствующие ему переменные x x ,..., x n , удовлетворяющие
системе линейных ограничений:
cn nx
1, 2
( , , ) ,
( , , ) ,
(2)
(1)
Стр.3
Стандартная модель ЗЛП
на максимум
f x = 1 1 + 2 2
11 1 + 12 2
( )
am x am x + + a x b ,
x ≥ 0
a x a x + + a x b ,
.............................................
21 1 + 22 2
1 1 +
j
2 2
...
...
...
2n n ≤ 2
mn n ≤ m
j =1,n
c x c x + + →max
a x a x + + a x b ,
...
c x
1
n n
n n
≤ 1
( )
Стандартная модель ЗЛП
на минимум
f x = 1 1 + 2 2
11 1 + 12 2
am x am x + + a x b ,
x ≥ 0
a x a x + + a2 x b ,
.............................................
21 1 + 22 2
1 1 +
j
2 2
...
...
...
n n
n n
≥ 1
≥ 2
mn n ≥ m
j =1,n
Если все ограничения системы заданы уравнениями, и все переменные
удовлетворяют условию неотрицательности ( xj ≥ 0 ,
j
=1, ) ЗЛП называют канонической.
Каноническая форма ЗЛП в координатной форме имеет вид:
f x = 1 1 + 2 2
n
( )
a x a x + + a x b ,
21 1 + 22 2
...
...
c xn n
1
a x a x + + a2 x b= 2
......................................
...
n n
n n
am x am x + + a x b ,
xj ≥ 0
1 1 +
2 2
...
mn n = m
j =1,n ,
или с использованием знак суммирования
n
f x =∑
j=1
( )
n
∑
j=1
x ≥ 0 ,
j
в матричной записи
A X B
f x C X
( )
⋅ ≤
= ⋅ →
X ≥ 0 ,
m (min),
ax
,
(5)
ij
a x b
c x
j → ax
j
j = i
1, ,
m (min),
i m
=
(4)
= 1
c x c x + + →max(min),
11 1 + 12 2
(3)
c x c x + + →min
a x a x + + a x b ,
...
c xn n
1
6
Стр.4
где C c c ,..., )cn
= ( , 21
, X =
x
x
2
1
:
xn
, B =
b
b
2
1
:
bm
, A =
a11
a21
..
am1
a12
a22
..
am2
...
...
..
...
дополнительная неотрицательная переменная
знаком «+»:
a x a x + + n n
1 1 + 2 2
...
a x a x + + n n
1 1 + 2 2
...
( ) 3
a x a x + + n n ≤
xn+ 1 вводится со
1 1 + 2 2 ...
a x b
...
a x b , со знаa1
a2
n
n
..
amn
Общую и стандартную ЗЛП всегда можно представить в каноническом
виде. Для чего неравенства преобразуют в равенства
путем введения дополнительных (балансовых, выравнивающих)
переменных. В линейное неравенство вида
в неравенство-ограничение вида a x a x2 2 + + n n ≥
ком «–»:
a x + xn+1 = b ,
1 1 +
a x − xn+1 = b .
Дополнительные переменные вводятся в целевую функцию с
нулевыми коэффициентами и поэтому не влияют на ее значение.
Пример 1. Привести ЗЛП к каноническому виду
max,
f x = x1 →+ x5 2
2x1 +3x2 ≤ 9,
3x1 + 2x2 ≤13,
x1 −5x2 ≥ 20,
x1, 2 ≥x
0 .
Решение. В левые части первого и второго ограниченийнеравенств
типа «≤» вводим соответственно дополнительные неотрицательные
переменные 3x и 4x со знаком «+», а в левую часть
третьего ограничения-неравенства типа «≥ » дополнительную неотрицательную
переменную 5x со знаком «–». В целевую функцию
дополнительные переменные 3x ,
x 4 , x 5 входят с коэффициентом
ноль. Получаем
f x =
( ) 3x1 +5x2 + ⋅ + ⋅ + ⋅ → max,
0 x3
0 x4
0 x5
.
7
Стр.5
2x1 +3x2 + = 9,
3x1 + 2x2 + =13,
x1 −5x2 − = 20,
xj ≥ 0 ,
x3
x4
x5
j =1,5.
ременные, любую такую переменную заменяют разностью двух
неотрицательных переменных, т.е.
j
xj
x j
, x′′ ≥ 0.
Пример 2. Привести к каноническому виду следующую ЗЛП:
6 min
f x = − −5x2 − →x3
2x1 +5x2 −7x3 ≤12,
3x1 − 2x2 +10x3 ≤17,
− +3x2 +8x3 ≥15,
( )
4x1
x1, 3 ≥x
0 .
Решение. Так как переменная 2x может принимать любые
значения, как положительные, так и отрицательные представим ее
как разность двух неотрицательных переменных, которые обозначим
3x и 4x ,
x2 = − . Переменную 3x теперь будем обозначать
x x 4
3
через 2x .
Преобразуем первые два ограничения вида «≤ » в равенства,
прибавив к их левым частям дополнительные неотрицательные
переменные 5x и 6x и третье неравенства вида «≤ », вычитая из
левой части дополнительную неотрицательную переменную 7x .
Дополнительные переменные 5x ,
f x = − − 6x2 −5x3 + 5x4 + ⋅ + ⋅ + ⋅ → min,
2x1 −7x2 +5x3 −5x4 + =12,
3x1 +10x2 − 2x3 + 2x4 + =17,
− +8x2 +3x3 −3x4 − =15,
3x1
0 x5
0 x6
0 x7
1
4x1
xj ≥ 0 ,
Если X d d ,...,dn ) – оптимальное решение полученной
8
= ( , 2
j =1,7.
x5
x6
x7
3x1
,
В случае, когда задача имеет произвольно изменяющиеся пеx
= ′ − ′′ , где x′ ≥ 0j
x 6 , x 7 входят в целевую функцию
с нулевыми коэффициентами. В результате указанных преобразований
ЗЛП примет вид:
( )
Стр.6
ЗЛП, то оптимальное решение исходной ЗЛП следующее:
.
x d x d d x d= 2
1 = 1,
2 = − 4 ,
3
3
Примечание. Иногда возникает необходимость перейти от задачи
нахождения минимума к нахождению максимума и наоборот. Для этого
достаточно изменить знаки всех коэффициентов целевой функции на
противоположные, а в остальном задачу оставить без изменений. Оптимальные
решения полученных таким образом задач на максимум и минимум
совпадают, а значения целевых функций при оптимальных решениях
отличаются только знаком.
Рассмотрим примеры построения математических моделей
ЗЛП.
Пример 3. Задача об использовании ресурсов. Для изготовления
двух видов продукции Р1, Р2 используют три вида сырья: S1,
S2, S3. Запасы сырья, количество единиц сырья, затрачиваемых на
изготовление единицы продукции, а также величина прибыли,
получаемая от реализации единицы продукции, приведены в таблице
1.
Таблица 1
Вид сырья
S1
S2
S3
Запас сырья
20
40
30
Прибыль от единицы продукции,
в руб.
на изготовление единицы продукции
Р1
Кол-во единиц сырья, идущих
Р2
2
8
5
50
котором прибыль от ее реализации будет максимальной.
Решение. Обозначим 1x ,
(8 x1 5 x2 ) единиц ресурса S2, (5 x1 6 x2 ) единиц ресурса S3.
⋅ + ⋅
2 x1 5 x2 ) единиц ресурса S1,
⋅ + ⋅
Так как потребление ресурсов S1, S2, S3 не должно превышать их
запасов, соответственно 20, 40 и 30 ед., то связь между потреблением
ресурсами и их запасами выражается системой неравенств:
5
5
6
40
единиц продукции Р1, Р2 запланированных к производству. Для их
изготовления потребуется (
Необходимо составить такой план выпуска продукции, при
x 2 – соответственно количество
⋅ + ⋅
9
Стр.7
2x1 +5x2 ≤ 20,
8x1 +5x2 ≤ 40,
5x1 + 6x2 ≤ 30.
Если продукция Р1 не выпускается, то 1x =0, в противном случае
1x >0. То же самое получаем и для продукции Р2. Таким образом,
на неизвестные 1x и 2x должны быть наложены условия неотрицательности:
1x ≥0, 2x ≥0.
Конечную цель задачи – получение максимальной прибыли
при реализации продукции – выразим как функцию двух переменных
1x и 2x . Реализация 1x единиц продукции вида P1 и 2x единиц
продукции вида Р2 дает соответственно 50 1x и 40 2x руб. прибыли,
суммарная прибыль составит
f x =
f x =
чения при ограничениях
( ) 50x1 40x 2 достигает максимального зна2x1
+5x2 ≤ 20,
+
n
8x1 +5x2 ≤ 40,
5x1 + 6x2 ≤ 30.
Задачу легко обобщить на случай выпуска n видов продукции
с использованием m видов ресурсов.
Обозначим jx (
j =1, ) – число единиц продукции jP , запланированной
к производству; b i ( mi =1, ) – запас ресурса iS , a ij –
число единиц ресурса iS , затрачиваемого на изготовление единицы
продукции jP ;
c j – прибыль от реализации единицы продукции
P j .
зовании ресурсов в общей постановке примет вид: найти такой
план
теме
( , 21
10
Тогда экономико-математическая модель задачи об испольX
= x x ,..., xn ) выпуска продукции, удовлетворяющий сис(
) 50x1 40x 2 (руб.).
+
Итак, экономико-математическая модель задачи: необходимо
найти такие неотрицательные значения 1x и 2x , при которых линейная
функция
Стр.8
a x a x + + a x b ,
21 1 + 22 2
11 1 + 12 2
................................................
,
a x a x + + a2 x b≤ 2
...
...
am x am x + + a x b ,
1 1 +
2 2
и условию неотрицательности
xj ≥ 0 ( j =1, ),
n
при котором функция
( )
f x = 1 1 + 2 2
c x c x + + → max
...
cn nx
(7)
(8)
принимает максимальное значение.
Пример 4. Задача составления рациона. Имеется два вида
корма I и II, содержащие питательные вещества S1, S2, S3. При откорме
каждое животное ежедневно должно получить не менее
9 ед. питательного вещества S1, 8 ед. вещества S2, 12 ед. вещества
S3. Cтоимость 1 кг корма I составляет 4 ед., корма II – 6 ед. Содержание
количества единиц питательных веществ в 1 кг каждого
вида корма приведены в таблице 2.
Таблица 2
Питательные вещества
S1
S2
S3
Кол-во единиц питательных веществ в 1 кг корма
корм I
3
1
1
корм II
1
2
6
Необходимо составить дневной рацион, имеющий минимальную
стоимость, в котором содержание каждого вида питательных
веществ было бы не менее установленного предела.
Решение. Для составления экономико-математической модели
обозначим 1x и 2x соответственно количество кормов I и II, входящих
в дневной рацион животных. Принимая во внимание значения,
приведенные в таблице 2, и условие, что дневной рацион
удовлетворяет требуемой питательности только в случае, если количество
единиц питательных веществ не меньше предусмотренного,
получаем систему ограничений
3x x+ ≥ 9,
1
2
x1 + 2x2 ≥ 8,
x1 + 6x2 ≥12.
11
...
mn n ≤ m
1
n n
n n
≤ 1
(6)
Стр.9
функции f x( ) 4x1 6x 2 (ед.).
По смыслу задачи переменные x1 0≥ , x2 0≥ .
+
3x x+ ≥ 9,
x1 + 2x2 ≥ 8,
x1 + 6x2 ≥12,
2
Общую стоимость рациона можно выразить в виде линейной
=
Итак, экономико-математическая модель задачи: необходимо
найти значения 1x и 2x , удовлетворяющие системе
1
условиям
f x =
x1 0≥ ,
( ) 4x1 6x 2 принимает минимальное значение.
+
Пример 5. Предприятие располагает тремя видами сырья и
может выпускать одну и ту же продукцию двумя способами. Запасы
сырья составляют 100, 100, 90 кг соответственно. За 1 ч работы
первым способом выпускается 20 ед., вторым – 30 ед. продукции.
Количество сырья (кг) того или иного вида, расходуемого за 1 ч
при различных способах производства приведены в таблице 3.
Способ
производства
Первый
Второй
1
10
20
Сырье
2
20
10
Таблица 3
3
15
15
Требуется найти план производства, при котором будет выпущено
наибольшее количество продукции.
Решение. Обозначим 1x и 2x время (час) использования соответственно
первого и второго способов производства. Исходя из
условий задачи, составляем систему ограничений.
Формулируем экономико-математическую модель задачи:
найти такое решение 1x и 2x , удовлетворяющее системе
10x1 + 20x2 ≤100,
20x1 +10x2 ≤100,
15x1 +15x2 ≤ 90,
x2 ≥ 0,
х1 ≥ 0,
при которых функция f ( )x =20 1x +30 2x принимает максимальное
значение.
12
x2 0≥ , при которых линейная функции
Стр.10