close

Вход

Забыли?

вход по аккаунту

?

1169.Методы оптимальных решений в задачах и упражнениях

код для вставкиСкачать
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
МЕТОДЫ ОПТИМАЛЬНЫХ РЕШЕНИЙ
В ЗАДАЧАХ И УПРАЖНЕНИЯХ
Учебно-методическое пособие
для студентов экономических специальностей
аграрного университета
Саратов 2013
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Методы оптимальных решений в задачах и упражнениях. Учебнометодическое пособие для студентов экономических специальностей аграрного
университета/Сост. Н.Б. Уейская, Саратов: ФБГУ ВПО СГАУ им.
Н.И.Вавилова, 2013. с.83.
Настоящее пособие разработано в соответствии с новым образовательным стандартом
по дисциплине «Методы оптимальных решений» для студентов экономических специальностей сельскохозяйственных вузов и содержит необходимые теоретические сведения по изучению данного курса, вопросы для самоконтроля, примеры решения типовых задач, достаточное количество заданий для самостоятельного решения, а также список рекомендуемой
литературы.
2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ВВЕДЕНИЕ
Данный курс является важной составляющей системы фундаментальной
подготовки современного экономиста. Он основан на фундаментальных знаниях, полученных в курсе математики. Особенностью данного курса является его
прикладная направленность: изучаемые методы позволяют решить многие экономические задачи.
В курсе рассматриваются методы, дающие возможность решать задачи
принятия в каком-то смысле наилучших, т.е. оптимальных решений. При этом
используется метод математического моделирования. Значительное внимание
уделяется ситуациям, в которых при формировании оптимального решения необходимо учитывать интересы различных сторон.
Математическая модель – это набор функций, уравнений, неравенств,
матриц и т.д., с помощью которых даётся приближённое описание изучаемого
явления.
Изучая математическую модель можно сделать определённые выводы об
изучаемом явлении.
Математическое моделирование – это метод изучения явлений природы
и общества с помощью математических моделей.
Этапы математического моделирования:
1. Постановка математической задачи, т.е. перевод на математический
язык связей между объектами моделей.
2. Решение и исследование математических задач, к которым приводят
математические модели.
Этот этап, как правило, связан с разработкой новых математических методов для решения полученных задач, зачастую с привлечением вычислительной техники.
3. Анализ полученных решений.
Т.е. сопоставление результатов наблюдений с теоретическими следствиями модели в пределах заданной точности.
4. Последующее усовершенствование модели в случае необходимости.
Математическое моделирование используют, например, при решении задач на составление уравнений, математическом программировании, в теории
игр.
2. Экономико-математические модели и их классификация
Экономико-математические модели (ЭММ) - это модели, с помощью которых изучаются экономические явления.
Приведем следующую классификацию ЭММ.
3
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
По целевому назначению ЭММ делятся на теоретико-аналитические и
прикладные. Теоретико-аналитические ЭММ предназначены для исследования
общих свойств и закономерностей экономических процессов. Прикладные
ЭММ используются при решении конкретных экономических задач.
По характеру отражения причинно-следственных связей выделяют
детерминированные, т.е. функциональные и стохастические ЭММ, учитывающие случайность и неопределенность.
По способам отражения фактора времени ЭММ делятся на статические и динамические. В статических ЭММ все зависимости относятся к одному
моменту или периоду времени. Динамические ЭММ характеризуют изменения
экономических процессов во времени.
По исследуемым экономическим процессам различают макроэкономические и микроэкономические ЭММ. Макроэкономические модели строятся на
уровне национального хозяйства, а микроэкономические – на уровне организаций, их объединений и отдельных регионов.
Существуют и другие признаки классификации ЭММ. Причем с развитием экономико-математических исследований классификация исследуемых
ЭММ расширяется.
При решении экономических задач необходима выработка критерия оптимальности, зачастую представляющего собой характерный показатель решения задачи, по значению которого и оценивается оптимальность найденного решения, то есть максимальное удовлетворение поставленным требованиям.
Критерий оптимальности, как правило, носит количественный характер.
Например, в его роли могут выступить максимум прибыли или минимум затрат.
На практике нередко успех оценивается не по одному, а сразу по нескольким критериям. В этом случае для выбора оптимального решения используют два подхода.
Первый подход заключается в том, что в целевой функции устанавливают
приоритет критериев введением специальных коэффициентов (весов).
Второй подход состоит в отбрасывании из множества допустимых решений заведомо неудачных решений, уступающих другим по всем критериям. В
результате такой процедуры остаются эффективные или так называемые «паретовские» решения, множество которых существенно меньше исходного.
Компромиссное решение – решение, оптимальное по всем критериям, как
правило, не существует. И потому окончательный выбор приемлемого по этим
критериям решения остается за лицом, принимающим решение.
4
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1. МОДЕЛЬ ЛЕОНТЬЕВА МНОГООТРАСЛЕВОЙ ЭКОНОМИКИ
Пусть имеется n различных отраслей, каждая из которых производит
свой продукт и нуждается также в продукции других отраслей (производственное потребление). Введем следующие обозначения:
xi - общий объем продукции отрасли i за плановый год - так называемый валовой выпуск отрасли i;
xij - объем продукции отрасли i, расходуемый отраслью j в процессе
производства;
yi - объем продукции отрасли i, предназначенный к потреблению в непроизводственной сфере - объем конечного потребления.
Модель межотраслевого баланса Леонтьева имеет вид:
x1 = a11 x1 + a12 x 2 +  + a1n x n + y1
x 2 = a 21 x1 + a 22 x 2 +  + a 2 n x n + y 2
. . . . . . . . . . . . . . . . . . . .
x n = a n1 x1 + a n 2 x 2 +  + a nn x n + y n
или, в матричной записи,
x = Ax + y ,
где
 a11 a12  a1n 
 x1 
 y1 




 
a
a

a
 21
22
2 n1 
x2 

y 
A = . . . . . . . . . . . .  , x =   , y =  2 .




 
 
 a n1 a n 2  a nn 


 xn 
 yn 


xij
При этом aij =
(i, j = 1,, n ) - коэффициенты прямых затрат, или коxj
эффициенты материалоемкости. Они показывают, сколько необходимо единиц продукции отрасли i для производства единицы продукции отрасли j, если
учитывать только прямые затраты. x - вектор валового выпуска, y - вектор
конечного потребления, А - матрица прямых затрат.
Задавая для каждой отрасли i валовой выпуск продукции xi можно определить объемы конечного потребления каждой отрасли yi : y = (E − A)x ,
где Е – единичная матрица;
По величинам конечного потребления каждой отрасли yi можно опреде-
лить величины валового выпуска продукции xi : x = (E − A)−1 y , где (E − A)−1 –
матрица, обратная к матрице (E − A) , ее элементы называют коэффициентами
полных материальных затрат.
Матрица A ≥ 0 называется продуктивной, если выполняется следующее
условие продуктивности: для любого вектора y ≥ 0 существует решение x ≥ 0
5
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
уравнения x = Ax + y . В этом случае и модель Леонтьева тоже называется продуктивной.
Критерий продуктивности 1. Матрица A ≥ 0 продуктивна тогда и только тогда, когда матрица (E − A)−1 существует и неотрицательна.
 0,2 0,6 
 .
 0,9 0,3 
Пример 1.1. Исследуем на продуктивность матрицу 
Решение.
 1 0   0,2 0,6  1 − 0,2 − 0,6   0,8 − 0,6 
 - 
 = 
 = 
 .
0
1
,
3
−
−
−
0
,
9
1
0
,
3
0
,
9
0
,
7
0
,
9
0

 
 
 

E − A = 0,8 ⋅ 0,7 − (−0,6)(−0,9) =0,56-0,54=0,02.
1  0,7 0,6   35 30 

=
.
( E − A) −1 =
0,02  0,9 0,8   45 40 
Е-А= 
Следовательно, матрица продуктивна.
Критерий продуктивности 2. Матрица A ≥ 0 продуктивна тогда и только тогда, когда имеет место разложение матрицы (E − A)−1 в матричный ряд
(E − A)−1 = E + A + A2 + A3 +  + An +  .
Матрицы A 2 , A3 , , A n ,  называются матрицами коэффициентов косвенных затрат 2-го, 3-го и т.д. порядков. Их сумма образует матрицу коэффициентов косвенных затрат B = A 2 + A3 +  + A n +  , то есть т.е. матрица коэффициентов полных материальных затрат включает в себя прямые и косвенные затраты.
Если сумма элементов любого столбца неотрицательной матрицы А
меньше 1, то А продуктивна.
Выполнение этого условия с содержательной точки зрения означает, что
любая отрасль рентабельна, так как суммарный вклад всех отраслей в выпуск 1
руб. продукции меньше 1.
Данное условие является достаточным, но не является необходимым для
продуктивности матрицы.
Пример 1.2. Установим продуктивность матрицы
 0,1 0 0,6 


A =  0,2 0,7 0  .
 0,4 0,2 0,3 


Решение. Так как сумма элементов каждого столбца меньше 1, то матрица продуктивна.
Пример 1.3. Для матрицы коэффициентов прямых затрат
6
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
 0,2 0,6 

,
3
0
,
9
0


А= 
 25 

72
 
и вектора конечного потребления y = 
найти: а) вектор валового выпуска; б) матрицу косвенных затрат; в) изменение
вектора валового выпуска при увеличении вектора конечного потребления на
величину
 12 
∆y =  
 35 
Решение. а) вектор валового выпуска x вычислим по формуле:
x = ( E − A) y .
−1
 35 30   25   35 ⋅ 25 + 30 ⋅ 72   3035 
   = 
 = 
 .
x = 
45
40
72
45
⋅
25
+
40
⋅
72
4005

  
 

б) матрицу косвенных затрат найдём по формуле:
 35 30   1 0   0,2 0,6 
 - 
 - 
 =
B = (E − A)−1 − E − A = 
45
40
0
,
9
0
,
3
0
1

 

 
 33,8 29,4 
 .
44
,
1
38
,
7


= 
 35 30   12  1470 
   =
.
40   35  1940 
в) ∆x = (E − A) ∆y = 
 45
−1
Таким образом, при увеличении вектора конечного потребления на
 12 
1470 
 .
∆y =   вектор валового выпуска должен увеличиться на ∆x = 
1940
35

 

Вопросы для самоконтроля
1. Что понимают под математической моделью?
2. Что такое математическое и каковы его этапы?
3. Приведите классификацию экономико-математических методов.
4. Что понимают под критерием оптимальности?
5. Что называют моделью Леонтьева?
6. Какая модель Леонтьева называется продуктивной?
7
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
7. Сформулируйте критерии продуктивности.
8. Что называют прямыми и косвенными затратами в модели Леонтьева?
Задачи и упражнения для самостоятельной работы
Исследуйте на продуктивность матрицы:
 0,2 0,3 
 .
1.1. 
0
,
5
0
,
8


 0,2 0,3 
 0,3 0,2 
 0,7 0,2 




1.2. 
 . 1.3.  0,7 0,8  . 1.4.  0,3 0,5  .
0
,
7
0
,
9






 0,1 0,3 0,2 
 0,1 0,3 0,3 
 0,05 0,45 0,4 






1.5.  0,1 0,2 0,5  . 1.6.  0,1 0,2 0,3  . 1.7.  0,5 0,1 0,2  .
 0, ,3 0,4 0,4 
 0,2 0,5 0,4 
 0,2 0,3 0,1 






 0,3 0,1 0,0 


1.8. Для матрицы А=  0,2 0,4 0,1  коэффициентов прямых затрат и век 0,1 0,0 0,2 


 100 


y
=
200

 найдите вектор валового выпуска.
тора конечного потребления
 300 


 0,05 0,45 0,4 


0
,
1
0
,
2
0
,
5
 коэффициентов прямых затрат и
1.9. Для матрицы А= 
 0,2 0,3 0,1 


152 


вектора конечного потребления y = 114  найти: а) вектор валового выпуска; б)
190 


матрицу косвенных затрат; в) изменение вектора валового выпуска при увели 76 
 
чении вектора конечного потребления на величину ∆y =  38 
 38 
 
1.10. Найдите изменение вектора валового продукта, если известна матрица полных материальных затрат и задан вектор изменения конечного продукта:
 1,23 0,17 0,26 


 0,43 1,25 0,26  коэффициентов прямых затрат и вектора изменения
 0,42 0,48 ,1,16 


8
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
 10 


∆
y
=
0


конечного потребления:
 − 10 


2. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
2.1. Математическая модель задачи линейного программирования
Общая задача линейного программирования формулируется следующим
образом: требуется найти максимум или минимум линейной функции, называемой целевой функцией на множестве неотрицательных решений системы
линейных ограничений (уравнений или неравенств).
Математическая модель задачи линейного программирования имеет вид:
n
L = ∑ c j x j (mах,min).
j =1
 n
 ∑ aij x j ≤ bi ,
 j =1
 x ≥ 0, i = 1.2..., m.
 j
Допустимым решением (планом) задачи линейного программирования
называется любой n – мерный вектор Х=(х1, х2, … , хn), удовлетворяющий системе ограничений.
Оптимальным решением (планом) задачи линейного программирования
называется такое допустимое решение задачи, при котором целевая функция
достигает экстремума.
Пример 2.1.1. Требуется составить математическую модель сочетания
посева трех культур, обеспечивающую максимальную стоимость валовой продукции, если хозяйство располагает следующими ресурсами: площадь посева –
2000 га, трудовые ресурсы – 12000 человеко-дней и техника – 2000 машиносмен. Показатели, характеризующие нормативы затрат в расчете на 1 га, приведены в таблице 2.1.1.
Таблица 2.1.1.
Культура
Показатели
Озимая
Сахарная
Однолетние
Пшеница
свекла
травы
Трудовые ресурсы, человеко-дней
2
25
0,3
Технические ресурсы, машино-смен
0,5
5
0,1
Стоимость продукции, тыс.
руб./ га
35
50
15
9
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Решение. Обозначим количество гектаров, отведенных для посева озимой пшеницы - через х1, для посева сахарной свеклы - через х2 и для посева однолетних трав - через х3.
Составим систему ограничения по ресурсам.
По площади посева:
х1 + х2 + х3 ≤ 2000
На обработку х1 га озимой пшеницы затрачивается 2х1 человеко-дней; на
х2 га сахарной свеклы – 2,5х2 человеко-дней; на х3 га однолетних трав – 0,3х3
человеко-дней; всего затраты труда составляют (2х1 + 25х2 + 0,3х3 ) человекодней, что не может превышать имеющиеся трудовые ресурсы – 12000 человекодней. Получаем ограничение по трудовым ресурсам: х1 + 25х2 + 0,3х3 ≤ 12000.
На обработку х1 га озимой пшеницы затраты техники составляют 0,5х1
машино-смен; на х2 га сахарной свеклы - 5х2 машино-смен; на х3 га – 0,1х3 машино-смен. Все затраты техники составят (0,5х1 + 5х2 + 0,1х3) машино-смен,
что не может превышать имеющиеся ресурсы техники – 2000 машино-смен.
Получаем ограничение по техническим ресурсам:
0,5х1 + 5х2 + 0,1х3 ≤ 2000
При этом все переменные х1, х2, х3 должны быть неотрицательными.
Стоимость озимой пшеницы, полученной с х1 га, составляет 35 тысяч
рублей; сахарной свеклы, выращенной на х2 га – 50х2 тысяч рублей; однолетние
травы, собранные с х3 га, оцениваются в 15х3 тысяч рублей. Общая стоимость
урожая трех культур составляет ( 35х1 + 50х2 + 15х3 ) тысяч рублей, это и есть
целевая функция L .
Получаем математическую модель:
L = 35х1 + 50х2 + 15х3 → max .
+ х2
 х1
 2х
+ 25 х 2
 1

 0,5 х1 + 5 х 2
 х1 ≥ 0 х 2 ≥ 0
+ х3
+ 0,3х3
+ 0,1х3
х3 ≥ 0
≤ 2000
≤ 12000
≤ 2000
Задача 2.1.2. При составлении суточного рациона кормления скота можно использовать сено (не более 50 кг) и силос (не более 85кг). Рацион должен
обладать определенной питательностью, т.е. число кормовых единиц в нем
должно быть не менее 30, и содержать следующие питательные вещества: белок - не менее 1кг, кальций – не менее 100г, фосфор – не менее 80г. В таблице
приведены данные о содержании указанных компонентов в 1 кг каждого продукта питания и себестоимость этих продуктов.
Таблица 2.1.2.
Сено
Силос
Количество,
к.ед.
0,5
0,5
Белок,
г/кг
Кальций,
г/кг
40
10
1,25
2,5
Фосфор,
г/кг
2
1
Себестоимость,
1кг в руб.
1,2
0,8
Требуется составить математическую модель, обеспечивающую рацион
минимальной себестоимости.
10
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Решение. Обозначим через х1 кг – количество сена и через х2 кг – количество силоса в суточном рационе.
Составим систему ограничений по количеству
- сена (кг)
х1 ≤ 50 ;
х2 ≤ 85 ;
- силоса (кг)
- кормовых единиц (к.ед.)
0,5х1 + 0,5х2 ≥ 30
- белка (г/кг)
40х1 + 10х2 ≥ 1000
- кальция (г/кг)
- фосфора (г/кг)
1,25х1 + 2,5х2 ≥ 100
2х1 + х2 ≥ 80.
Себестоимость такого рациона равна L =1,2х1 + 0,8х2 рублей..
Математическая модель этой задачи имеет вид:
L = 1,2x1 + 0,8x2 → min
 х1

х2

 0,5 х1 + 0,5 х 2

 40 х1 + 10 х 2
1,25 х + 2,5 х
1
2

+ х2
 2 х1

 х1 ≥ 0 х 2 ≥ 0
≤
50
≤ 85
≥ 30
≥ 1000
≥ 100
≥ 80
Вопросы для самоконтроля
1. Сформулируйте задачу линейного программирования и напишите ее
математическую модель.
2. Что называется допустимым решением задачи линейного программирования?
3. Что называется оптимальным решением задачи линейного программирования?
Упражнения для самостоятельного решения
2.1.1. За счет мелиоративных работ площадь пашни в хозяйстве возросла
на 170 га. Эту площадь решено было отвести под посев двух наиболее эффективных для хозяйства культур: проса и гречихи, причем гречихи нужно получить не менее 1000 ц. В хозяйстве имеется 630 ц минеральных удобрений.
Известны прибыльность и нормативы затрат в расчете на 1 ц проса и гречихи:
11
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Показатели
Просо
Гречиха
Прибыль, тыс. руб.
5
6
Расход пашни, га
0,06
0,05
Затраты удобрений, ц
0,1
0,3
Требуется составить математическую модель задачи на определение
максимальной прибыли от производства этих культур.
2.1.2. Хозяйство располагает следующими ресурсами: 600 га пашни и
4000 человеко-дней трудовых ресурсов. В таблице содержится информация о
данном хозяйстве.
Показатели
Затраты труда, чел.-дн./га
Урожайность, ц/га
Культура
Зерновая
Кормовая
5
23
10
36
Составить модель наиболее эффективного сочетания посевов зерновых и
кормовых культур при условии, что под кормовые культуры должно быть занято не более 100 га пашни.
2.1.3. Составить модель, оптимального сочетания посевов трех культур:
капусты, картофеля и многолетних трав на сено, дающую максимальную прибыль, при условии, что в хозяйстве имеется 850 га пашни, 15000 тонн органических удобрений, трудовые ресурсы составляют 50000 человеко-дней. Затраты
ресурсов и выход валовой продукции в денежном выражении в расчете на 1 га
указанных культур приведены в таблице:
Показатели
Затраты труда, чел.-дн.
Затраты удобрений, т
Выход продукции, тыс.руб.
Культура
Капуста
Картофель
50
20
125
30
15
80
Травы
10
10
25
2.1.4. При изготовлении двух видов изделий А и В предприятие расходует
в качестве сырья сталь и цветные металлы. Указанные изделия производятся с
помощью токарных и фрезерных станков. Составьте математическую модель
производства этих изделий для достижения максимальной прибыли. Объем ресурсов предприятия, нормы их расходов на каждое изделие и прибыль от реализации приведены в следующей таблице:
12
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Вид ресурса
Сталь, кг
Цветные металлы, кг
Токарные станки, станко-час
Фрезерные станки, станко-час
Прибыль, денежных единиц
Объем ре- Нормы расхода на 1 изделие
сурса
А
В
840
516
4500
2865
15
32
200
240
5
60
64
320
120
12
2.1.5. Швейный цех изготовляет рабочую одежду двух видов: комбинезоны и халаты. На комбинезон расходуется 1,8 м2 ткани одного вида и 0,6 м2
другого вида; на халат соответственно 1,5 м2 и 0,4 м2. Доход от реализации одного комбинезона составляет 300 рублей , от реализации одного халата 100
рублей. Составьте математическую модель производства комбинезонов и халатов, чтобы прибыль от их реализации была максимальной, если наличие ткани,
соответственно, составляет: первого вида – 145 м2 и второго вида – 50 м2.
2.1.6. Из двух сортов бензина для различных целей составляют два вида
смесей А и В. Смесь А содержит 20% бензина А-95 и 80% бензина А-92;
смесь В содержит 30% бензина А-95 и 70% бензина А-92. Продажная цена 1
кг смеси вида А - 16 рублей, Смеси вида В – 18 рублей. Составьте математическую модель плана составления смесей, при котором будет получен наибольший доход, если в наличии имеется 20 тонн бензина А-95 и 45 тонн бензина А92.
2.1.7. Составьте модель суточного рациона кормления животных с наименьшей стоимостью. Исходные данные для решения задачи приведены в следующей таблице:
Питательные веще- Содержание питательных ве- Минимальная суточная
ства, усл.ед.
ществ в единице корма
норма
потребления,
усл.ед.
А
В
Кормовые единицы
1
0,5
5
Переваримый протеин
80
200
560
Кальций
1
8
20
Цена ед. корма, ден.ед.
3
5
2.1.8. Составьте модель суточного рациона кормления свиней с наименьшей стоимостью. В рацион должно быть включено не более 2,5 кг ячменя. Минимальная суточная потребность – 2,4 кг к.ед. и 200 г протеина. Исходные данные для решения задачи приведены в следующей таблице:
Вид корма
Комбикорм
Ячмень
Содержание питательных веществ в 1 кг корма
Кормовые единицы, кг
Протеин, г
1
1,2
100
80
13
Цена 1
корма,
ден . ед.
9
3
кг
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2.1.9.Для сохранения здоровья и работоспособности человек должен потреблять в сутки некоторое количество питательных веществ: белков, жиров,
углеводов, воды и витаминов. Составим рацион питания, состоящий из двух
видов пищи, стоимость единицы массы первого вида пищи П1 – 8 рублей , второго П2 – 12 рублей. Составьте план организации питания так, чтобы стоимость его была наименьшей. Количество питательных веществ в единице массы
каждого вида пищи представлены в следующей таблице:
Питательные
вещества
Жиры
Белки
Углеводы
Вода
Витамины
Минимальная норма
10
12
16
10
1
Вида пищи
П1
П2
1
3
2
2
1
5
2
4
2
0
1.1.10. Составьте математическую модель плана посева зерновых культур
(с учетом плодородия участков), дающего наибольшую прибыль. Площадь первого участка равна 500 га, второго – 400 га, третьего – 600 га, четвертого – 500
га. Все необходимые данные приведены в таблице:
Зерновая
культура
Урожайность по
участкам, ц/га
1
2
3
Посевные
площади,
га
Закупочные
цены,
Затраты на 1 га,
тыс. руб.
тыс. руб. за ц
4
1
2
3
4
Рожь
22 25 20 18
250
24
10 11 12
9
Пшеница
30 32 25 28
1400
35
11 12
8
10
Ячмень
31 28 25 23
350
26
12 14 10
9
2.2. Графический метод решения задач линейного программирования
Чаще всего графический метод применяется для решения задач линейного программирования с двумя переменными. Он основан на том, что оптимальные решения задачи линейного программирования лежат на границе множества
допустимых решений.
Пример 2.2.1. Требуется решить задачу линейного программирования
графическим методом:
14
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
L = 3x1 + 2 x2 → max
 x1 − x2 + 2 ≥ 0
3x − 2 x − 6 ≤ 0
2
 1
 2 x1 + x 2 − 2 ≥ 0

x2 ≤ 3

 x1 ≥ 0, x2 ≥ 0
Решение. Построим сначала область допустимых решений, которая представляет собой множество решений системы линейных ограничений.
Графически решение каждого неравенства есть одна из полуплоскостей,
на которые прямая линия ax +by =c делит координатную плоскость. Решением
системы неравенств будет выпуклый многоугольник, представляющий собой
пересечение полуплоскостей – решений каждого неравенства.
Пронумеруем каждое неравенство и решим его (см. рис.2.2.1)
1. x1 − x 2 + 2 ≥ 0
Построим прямую x1 − x 2 + 2 = 0 , для чего найдём координаты двух её точек, например, (0; 2) и (2; 4). Чтобы выбрать полуплоскость-решение для данного неравенства, подставим в это неравенство координаты любой точки, не
лежащей на построенной прямой, например точки с координатами (0; 0). Получаем 0 – 0 +2 ≥ 0. Это верное неравенство. Следовательно, полуплоскость, содержащая эту точку, будет являться решением неравенства 1. Стрелками отметим решение.
1
2
В
4
4
С
А
n
D
E
3
2
Рис. 2.2.1. Решение задачи линейного программирования.
15
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2. 3x1 − 2 x 2 − 6 ≤ 0
Строим прямую 3x1 − 2 x 2 − 6 = 0 , проходящую через точки с координатами
(0;-3) и (2;0). Решением неравенства является полуплоскость, содержащая начало координат (0,0), так как: 3·0 –2· 0 – 6 ≤ 0 - верное неравенство.
3. 2 x1 + x 2 − 2 ≥ 0
Строим прямую 2 x1 + x 2 − 2 = 0 , проходящую через точки с координатами
(0;2) и (1;0). Затем в неравенство подставляем координаты точки (0;0): 2·0 + 0
– 2 ≥ 0. Так как это неравенство неверное, то решением является полуплоскость, не содержащая точку с координатами (0;0).
4. x 2 ≤ 3
Прямая, определяемая уравнением x 2 = 3 проходит через точку (0;3), параллельно оси абсцисс. Полуплоскость, лежащая ниже этой прямой, и есть решение данного неравенства.
Два последних неравенства х1 ≥ 0; х 2 ≥ 0 определяют первый квадрант координатной плоскости.
На рис. 2.2.1 многоугольник ABCDE представляет собой область допустимых решений задачи линейного программирования.
Для нахождения оптимального решения построим вектор n (3;2), координаты которого равны коэффициентам при переменных в целевой функции L.
Этот вектор является нормальным вектором для линий уровня L=const. Построим одну из линий уровня, например, 3х1 + 2 x 2 = 0 . Чем дальше продвинуть
эту линию уровня параллельно самой себе в направлении вектора n , тем большее значение принимает целевая функция. Так, как задача на отыскание максимального значения целевой функции, то линию уровня перемещаем в направлении нормали до опорной прямой, то есть такой линии уровня, которая
имеет хотя бы одну общую точку с областью допустимых решений и по отношению к которой эта область находится в одной из полуплоскостей. Эта прямая
проходит через точку С пересечения прямых 3x1 − 2 x 2 − 6 = 0 и x 2 = 3 , для опре3х1 − 2 х 2 − 6 = 0
, полух2 = 3

деления координат точки С решим систему уравнений 
чаем
С(4;3)
в
этой
точке
целевая
функция
достигает
максимума
Lmax = 3 ⋅ 4 + 2 ⋅ 3 = 18 .
Ответ: Lmax = 18 при Х*= (4;3).
Вопросы для самоконтроля
1. Что собой представляет график линейного уравнения с двумя переменными графически?
2. Каков график линейного неравенства ?
3. Как изменяется целевая функция при перемещении линии уровня?
4. Сформулируйте алгоритм решения задачи линейного программирования графическим методом.
5. В каком случае задача имеет
единственное
решение,
16
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
бесконечное множество решений и не имеет решения?
Задачи для самостоятельного решения
Решите задачи линейного программирования графическим методом:
L = х1 – х2 → min
 õ1 + 3 õ2
3 õ
− õ2
 1
2.2.1. 3 õ1 − 4 õ2
õ
 1

õ2
L =-2 х1 –2 х2 → min
≤ 12
≤
6
≤
0
≥
≥
0
0
 õ1 + 8 õ2
2 õ + 5 õ
2
 1
2.2.2. 5 õ1 + 2 õ2
õ
 1

õ2
L = 4 x1 + 2 x2 → max
≤5
 x1
2 x + x ≤ 14
 1 2
2.2.3.  x1 + x2 ≤ 10

x2 ≤ 8

 x1 ≥ 0, x2 ≥ 0
2.2.5.
2.2.7.
8
≥ 10
≥ 10
≥
≥
0
0
L = x1 − 4 x2 → min
 x1 + 2 x2 ≤ 4
x
≤3
 1
2.2.4.  x1 − 2 x2 ≥ −1
x
≥0
 1

x2 ≥ 0
L = 2 x1 + 3 x 2 → max
 − 2 x1 + x 2 ≤ 2
 x − 3 x ≥ −9
2
 1
4 x1 + 3 x 2 ≤ 24


 x1 ≥ 0, x 2 ≥ 0
≥
L = 5 x1 − 3 x 2 → min
 4 x1 − x 2 ≥ 0
− x + x ≤ 3
2
 1
2. 2.6 2 x1 − 3 x 2 ≤ 6
 x ≤4
1

 x1 ≥ 0, x 2 ≥ 0
L = 2 x1 + 3x 2 → max
L = 2 x1 + 3 x2 → max
 − 6 x1 + x 2 ≤ 3
− 5 x + 9 x ≤ 45
1
2

 x1 − 3x 2 ≤ 3

х1 ≤ 5

 x1 ≥ 0, x 2 ≥ 0
− 3 x1 + 2 x2 ≤ 4
 − x + 2x ≤ 8
2
 1
 x1 + x2 ≤ 10
 4 x − x ≤ 20
 1 2
 x1 ≥ 0, x2 ≥ 0
2.2.8.
17
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2.2.9.
2.2.11.
2.2.13.
L = 5 x1 + 5 x 2 → max
L = x1 + 2 x2 → max
− 2 x1 + x 2 ≤ 2
 − x + 3x ≤ 9
2
 1
 x1 + x 2 ≥ 3

x1 ≤ 4

 x1 ≥ 0, x 2 ≥ 0
− 3x1 + 2 x2 ≤ 4
 − x + 2x ≤ 8
2
 1
 x1 + x 2 ≤ 10
 x −x ≤2
2
 1
 x1 ≥ 0, x2 ≥ 0
2.2.10.
L = − x1 − x2 → min
L = 2 x1 + 4 x2 → min
 2 x1 − 3 x2 ≤ 0
− 5 x + 9 x ≤ 45
1
2

 5 x1 + 4 x2 ≥ 20

x1 ≤ 6

 x1 ≥ 0, x2 ≥ 0
− 3x1 + 2 x2 ≤ 6
 x + 2 x ≤ 10
2
 1
 x1 − 5 x2 ≤ 5
 x +x ≥4
2
 1
 x1 ≥ 0, x2 ≥ 0
2.2.12.
L = x1 + 2 x 2 → max
L = 2 x1 + 2 x2 → max
− 3x1 + 2 x 2 ≤ 6
 x −x ≤0
2
 1
 x1 + x 2 ≤ 8

x2 ≥ 3

 x1 ≥ 0, x 2 ≥ 0
− 2 x1 + x2 ≤ 2
− x + 2 x ≤ 7
2
 1
 x1 + 3 x2 ≤ 18

x1 ≤ 6

 x1 ≥ 0, x2 ≥ 0
2.2.14.
2.3. Симплекс-метод решения задач линейного программирования.
Если система ограничений задачи линейного программирования является
системой уравнений, то такая задача называется канонической формой задачи
линейного программирования и имеет вид:
n
∑a
j =1
ij
x j =bi
xj ≥ 0
( i = 1, 2, … , m)
(j = 1, 2, … , n)
(1.1.13)
n
L = ∑ c j x j → (max, min)
j =1
При перехода от общей задачи линейного программирования к канонической форме вводят дополнительные неотрицательные переменные, и неравенства вида ai1 x1 + ai 2 x 2 + ... + ain x n ≤ bi , ( i = 1, 2, … , m) заменяются уравнеа
неравенства
вида
ниями
ai1 x1 + ai 2 x 2 + ... + ain x n + x n +i = bi ,
ai1 x1 + ai 2 x 2 + ... + ain x n ≥ bi - уравнениями ai1 x1 + ai 2 x 2 + ... + ain x n − x n +i = bi , ( i =
18
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1, 2, … , m).
Алгоритм симплекс-метода.
1. Составляем математическую модель задачи.
2. Приводим задачу к канонической форме: путём введения новых переменных преобразуем систему ограничений к системе уравнений, а
затем приравниваем целевую функцию её свободному члену. Свободные члены в системе ограничений должны быть неотрицательны.
3. Выделяем базисные переменные в каждом уравнении системы ограничений. Базисная переменная в данном уравнении имеет коэффициент равный единице, а в остальных уравнениях и в целевой функции
он равен нулю.
4. Составляем симплексную таблицу: записываем в первом столбце базисные переменные, во втором – свободные члены, а затем коэффициенты при переменных.
5. Получаем опорный план. Все планы получаются одинаково: небазисные переменные равны нулю, а базисные переменные и целевая
функция равны свободным членам.
6. Выбираем разрешающий столбец, то есть столбец коэффициентов
при переменной, которая на данном шаге вводится в базис. При решении задачи на максимум в строке коэффициентов при переменных
целевой функции находим наибольшее по абсолютной величине отрицательное число; при решении задачи на минимум – наибольшее
положительное число. Если разрешающий столбец найти нельзя, то
полученный план – оптимальный.
7. Находим разрешающую строку. При решении задачи на максимум
или на минимум она находится одинаково: выбирается наименьшее
из отношений свободных членов к положительным коэффициентам
разрешающего столбца. Если разрешающую строку найти нельзя, то
задача не имеет решения.
8. Находим разрешающий элемент,
стоящий на пересечении
19
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
разрешающего столбца и разрешающей строки.
9. Составляем новую симплексную таблицу, в которую вносим разрешающую строку, поделённую на разрешающий элемент. Остальные
строки находим путём получения нулей в разрешающем столбце с
помощью разрешающей строки.
10.Получаем новый план и переходим к пункту 6.
Пример 2.3.1. Требуется решить задачу линейного программирования
симплекс-методом:
L = 4x1 + 2x2 → max
≤ 5
 x1
2 x + x
 1
2 ≤ 14

 x1 + x 2 ≤ 10

x2 ≤ 8
х1 ≥ 0, х2 ≥ 0
Решение. При решении используем алгоритм.
Приведем задачу к канонической форме:
 х1
2 х
 1

 х1

+ х3
+ х2
+ х2
х2
+ х4
+ х5
+ х6
= 5
= 14
= 10
= 8
хj ≥ 0 (j=1,2,3,4,5,6)
Целевую функцию приравняем свободному члену:
L – 4х1 – 2х2 = 0 →
Выберем базисные переменные
max
Б = (х3, х4, х5, х6) и составим первую
симплексную таблицу.
Базисные Свободные х1
переменные
Члены
х3
5
1
х4
14
2
х5
10
1
х6
8
0
L
0
-4
х2 х3 х4 х5 х6
0
1
1
1
-2
1
0
0
0
0
0
1
0
0
0
0
0
1
0
0
0
0
0
1
0
Первоначальный, или опорный план данной задачи будет следующий:
Х0 = (0, 0, 5, 14, 10, 8), а значение целевой функции L0 = 0.
20
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Выбираем разрешающий столбец и разрешающую строку. Так как задача
на отыскание максимального значения L , то ищем в последней строке таблицы
наибольшее по абсолютной величине отрицательное число, это (-4), следовательно, столбец соответствующий х1 будет разрешающим. Выделим его в таблице.
Для отыскания разрешающей строки найдем min ;
5 14 10 
; ;  = 5 , это соот1 2 1 
ветствует первой строке, следовательно, она будет разрешающей. Выделим ее в
таблице. Итак, будем вводить в число базисных переменных х1 вместо х3. Получаем Б = (х1, х4, х5, х6)
Разрешающий элемент равен 1, поэтому в новую симплексную таблицу
перепишем разрешающую строку без изменения. Ко второй строке прибавим
разрешающую, умноженную на (-2). К третьей строке прибавим разрешающую,
умноженную на (-1). В четвертой строке разрешающего столбца стоит 0, поэтому перепишем ее без изменения. К последней строке прибавим разрешающую, умноженную на 4. Получили вторую симплексную таблицу и новый
план:
Базисные Свободные х1 х2 х3 х4 х5 Х6
переменные
члены
х1
5
1 0 1 0 0 0
х4
4
0 1 -2 1 0 0
х5
5
0 1 -1 0 1 0
х6
8
0 1 0 0 0 1
L
20
0 -2 4 0 0 0
Х1 = (5, 0, 0, 4, 5, 8), при этом L1 = 20. Этот план лучше предыдущего.
Можно ли его улучшить?
В строке для целевой функции есть отрицательное число (- 2), оно соответствует разрешающему столбцу. Для нахождения разрешающей строки найдем min ; ;  = 4 , это соответствует второй строке, она и будет разрешаю4 5 8
 1 1 1
щей. Следовательно будем вводить в базис х2 вместо переменной х4. Получаем
Б = (х1, х2, х5, х6) и строим следующую симплексную таблицу. Разрешающий
элемент равен 1, поэтому в новую таблицу разрешающую строку переносим без
изменения. Нули в разрешающем столбце получаем следующим образом: к
третьей и четвертой строкам прибавляем разрешающую, умноженную на (-1), а
к последней прибавляем разрешающую строку, умноженную на 2. В первой
строке разрешающего столбца стоит 0, поэтому переписываем ее без изменения. Получаем третью симплексную таблицу:
Базисные Свободные х1 х2 х3 х4 х5 х6
переменные
члены
х1
5
1 0 1 0 0 0
21
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
х2
х5
х6
L
4
1
4
28
0
0
0
0
1
0
0
0
-2
1
2
0
1
-1
-1
2
0
1
0
0
0
0
1
0
Получили новый план Х2 = (5, 4, 0, 0, 1, 4), при этом L2 = 28. Этот план
лучше предыдущего. Очевидно, что найденный план оптимальный, так как в
последней строке больше нет отрицательных чисел, и, следовательно, увеличить значение целевой функции невозможно. Максимум целевой функции Lmax
= 28 достигается при плане Х2 = (5, 4, 0, 0, 1, 4).
Ответ: Х* = (5, 4, 0, 0, 1, 4), Lmax = 28.
Вопросы для самопроверки
1. В каком виде должна быть записана математическая модель задачи перед
составлением первой симплексной таблицы?
2. Что называется опорным планом задачи линейного программирования?
3. Что называется разрешающим столбцом симплексной таблицы?
4. Как выбирается разрешающий столбец, при решении задачи на отыскание минимума целевой функции?
5. Как выбирается разрешающий столбец, при решении задачи на отыскание максимума целевой функции?
6. Как определяется разрешающая строка?
7. как находится разрешающая строка?
8. Что называется разрешающим элементом?
9. Как осуществляется переход к следующей симплексной таблице?
10. Как определить, что полученный план оптимальный?
11.Какой вывод можно сделать, если нельзя выбрать разрешающую строку?
Задачи для самостоятельного решения
Решите задачу линейного программирования симплекс-методом:
2.3.2 L = х1 – х2→ min
2.3.1. L =7х1 + 5х2 → max
2 х1
2 х
 1

 3 х1

+ 3х 2
+ х2
3х 2
≤
≤
≤
≤
19
13
18
15
 х1

3х1
3х
 1
xj ≥ 0 (j = 1, 2,)
2.3.3. L =х1 + 2х2+х3 → max
+ 3х 2
− х2
− 4х2
≤ 12
≤ 6
≤ 0
xj ≥ 0 (j = 1, 2, )
2.3.4. L =-3х1 + х2 -4 → min
22
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2 х 1

2 х 1
4 х
 1
+ х2
− х3
≤ 2
− х2
+ х2
+ 5х 3
+ х3
≤ 6
≤ 6
 х1

2 х 1
х
 1
xj ≥ 0 (j = 1, 2, 3)
х2
+ х2
− х3
− х4
≤ 6
− х3
+ х3
+ х4
≤ 2
≤ 5
2.3.7. L = 3х1 - х3 → max
− х2
2х2
+ х4
+ х3
− 2 х3
 − 2 х1

 х1
 х
 1
≤ 4
≤ 8
− 3х 3
+ 2 х3
+ 2 х3
+ х4
+ х4
+ х2
+ х2
+ х3
≤ 2
≤ 4
xj ≥ 0, (j = 1, 2, 3)
+ 2х
− 3х 3
+ х4
≤ 6
− х2
− х2
+ 2 х3
+ 2 х3
+ х4
≤ 2
≤ 5
xj ≥ 0, (j = 1, 2, 3, 4)
2.3.15. L = 2х1 + х2→ max
≤ 2
≤ 2
≤ 5
+ 3х 4
+ х3
2 х3
+ х5
≤ 5
≤ 8
≤ 10
xj ≥ 0 (j = 1, 2, 3, 4, 5)
L = -х1 – х2→ min
2.3.10.
 − х1

 х1
+ х2
− 2х2
≤ 1
≤ 2
xj ≥ 0 (j = 1, 2,)
2.3.12. L =х2 – х1 → min
2 х1

 х1
х
 1
+ х2
− х2
+ х2
+ х3
= 2
≤ 2
≤ 5
xj ≥ 0, (j = 1, 2, 3)
2.3.13. L = 2х1 + 3х2+2х3+х4 → max
2 х 1

 х1
х
 1
х2
+ 2х2
≤ 6
≤ 2
≤ 5
xj ≥ 0 (j = 1, 2, 3, 4)
2.3.11. L = 2х1 + 3х2 → max
 х1

 х1
+ х2
− 2х2
+ х2
xj ≥ 0 (j = 1, 2,)


 х1


= 5
2.3.9. L =2х1 + 3х2+2х3+х4 → max
+ 2х2
− х2
− х2
≤ 0
≤ 6
2.3.8. L = 2х3 – х4→ min
xj ≥ 0 (j = 1, 2, 3, 4)
2 х1

 х1
х
 1
− х2
+ 3х 2
2.3.6. L = х2 – х1→ min
xj ≥ 0 (j = 1, 2, 3, 4)
 х1




≤ 2
xj ≥ 0 (j = 1, 2,)
2.3.5. L =2х1 + х2+2х3 +3х4 → max
 3 х1


− х
 1
+ 2х2
2.3.14. L =5х1 – х2 → min
 2 х1

 − 5 х1
 х
 1
− 3х 2
≤
+ 9х2
− 2х2
≤ 45
≤ 4
0
xj ≥ 0, (j = 1, 2)
1.4.16. L =3х1 –6 х2+4х3 -2х4 → min
23
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
 х2



 х2
− х 2
− х1
≤ 4
х1
≤ 4
≤ 5
+ х1
− 2 х3
+ 4 х3
+ х4
− х4
= 2
= 8
≤ 0
xj ≥ 0, (j = 1, 2,)
xj ≥ 0, (j = 1, 2, 3, 4)
1.3.17. L = 4х1 + 2х2 → max
 − х1

 х1
 3х
 1
х2
+ х2


2 х 1
+ 2х2
≤
+ х2
− х2
≤ 9
≤ 15
 х1




6
xj ≥ 0, (j = 1, 2,)
1.3.18. L =х1+ х2+х3 → min
− х4
х2
х3
+ 2х4
− 2х4
− 3х 5
− 5х5
− 2 х6
= 5
+ х6
+ 6х6
= 3
= 5
xj ≥ 0, (j = 1, 2,)
2.4. Двойственные задачи линейного программирования
Каждой задаче линейного программирования можно поставить в соответствие некоторую другую задачу, которую называют двойственной. Обе эти задачи образуют пару взаимно двойственных задач.
Наиболее часто встречаются следующие пары взаимно двойственных задач:
n
L = c0 +
m
c i x j → max,
∑
j
L1 = c 0 +
=1
n
a ij x j ≤ bi , i = 1,2,...m,
∑
j
=1
x j ≥ 0, j = 1,2,..., n.
bi y i → min,
∑
i
=1
(I) и
m
a ij y i ≥ c j , j = 1,2,...n,
∑
i
(II).
=1
y i ≥ 0, i = 1,2,..., m.
В двойственных задачах коэффициенты при переменных в целевой функции и свободные члены в системе ограничений, записанные в правых частях,
меняются местами; целевая функция двойственной задачи должна минимизироваться, если в исходной она максимизировалась, и наоборот; знаки неравенств в системе ограничений изменяются на противоположные.
(I) представляет собой, например, модель задачи выпуска продукции с
максимальной прибылью L, где хj- это объём производства j-го вида продукции
(j=1, 2,…,n), аij – расход i-го вида сырья на единицу j-ой продукции; которого
имеется в наличии bi единиц (i = 1, 2,…, m); сj- прибыль при реализации j-го
вида продукции.
Задача (II), двойственная к (I), позволит определить цены уi, по которым
может быть продано сырьё, чтобы, с одной стороны, покупатель заплатил как
можно меньше (эта сумма равна L1), а, с другой стороны, продавец получил бы
за сырьё, расходуемое на каждый вид продукции доход не меньший, чем прибыль сj, получаемая от реализации этого изделия.
Имеет место следующая теорема двойственности:
Если одна из двойственных задач линейного программирования имеет
решение, то и другая задача также имеет решение, причём Lmax = L1min.
Пример 2.4.1. Из двух сортов бензина образуют для различных целей две
24
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
смеси А и В. Смесь А содержит 60% бензина первого сорта и 40% бензина второго сорта. Смесь В содержит 80% бензина первого сорта и 20% второго сорта.
Продажная цена 1 кг смеси А - 10 рублей, а смеси В – 12 рублей.
Требуется составить а) план образования смесей, при котором будет получена максимальная выручка, если в наличии имеется 50 т бензина первого
сорта и 30 т бензина второго сорта; б) двойственную задачу и найти её решение
по симплексной таблице для данной задачи.
Решение. Пусть требуется изготовить х1 т смеси А и х2 т смеси В. Из условия задачи получаем математическую модель данной задачи:
L = 10 x 1 + 12 x 2 → max ,
0,6 x 1 + 0,8 x 2 ≤ 50,

0,4 x 1 + 0,2 x 2 ≤ 30,
x j ≥ 0, j = 1,2 ,
где L - прибыль, тыс. руб.
а) Решим эту задачу симплексным методом. Преобразуем целевую функцию и приведём задачу к канонической форме:
L − 10 x 1 − 12 x 2 = 0 ,
0,6 x1 + 0,8 x 2 + x3

0,4 x1 + 0,2 x 2 +
= 50,
x 4 = 30,
Составим симплексную таблицу:
Базисные
переменные
х3
Свободные
Члены
х1
х2
х3
х4
50
0,6
0,8
1
0
х4
30
0,4
0,2
0
1
L
0
-10
-12
0
0
Найдём разрешающий столбец по наименьшему отрицательному коэффициенту в строке L. Это столбец коэффициентов при х2.
Выбираем первую строку разрешающей, так как для неё отношение свободного члена к положительному элементу разрешающего столбца минимально.
Составим вторую таблицу, в которой первая строка получена делением
разрешающей строки на разрешающий элемент 0,8; вторая есть результат сложения первой строки второй таблицы, умноженной на (-0,2) со второй строкой
первой таблицы. Строка L есть сумма соответствующей строки первой таблицы
с первой строкой второй таблицы, умноженной на 12.
25
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Базисные
переменные
х2
Свободные
Члены
х1
х2
х3
х4
62,5
0,75
1
1,25
0
х4
17,5
0,25
0
-0,25
1
L
750
-1
0
15
0
Во второй таблице разрешающий столбец х1, а разрешающая строка вторая. Поделим её на разрешающий элемент 0,25 и запишем в первой строке
третьей таблицы, а затем преобразуем её так, чтобы в столбце х1 остальные
элементы обратились в нуль. Для этого первую строку третьей таблицы умножим на (-0,75) и сложим с первой строкой второй таблицы. Строка L третьей
таблицы получается сложением соответствующей строки второй таблицы с
первой строкой третьей таблицы. В результате получаем:
Базисные
переменные
х1
Свободные
Члены
х1
х2
Х3
х4
70
1
0
-1
4
х2
10
0
1
2
-3
L
820
0
0
14
4
Так как все коэффициенты в строке L неотрицательны, то преобразования
закончены. Решение исходной задачи Lmax=820 тыс. руб.; х1=70 т, х2=10т.
б) Составим двойственную задачу.
Предприятие, занимающееся составлением смесей, имеет возможность
продать бензин, не составляя их, при этом оно желает выручить за бензин не
менее той суммы, которую оно получило бы при образовании смесей. Требуется определить, по какой цене реализовать бензин.
Пусть у1 и у2 цены 1 т бензина соответственно первого и второго сортов,
тыс. руб.
Так как смесь А содержит 60% бензина первого сорта и 40% бензина
второго сорта, то цена 1т этой смеси должна быть не меньше 10 тыс. руб., то
есть 0,6у1+0,4у2≥10.
Аналогично для смеси В имеем: 0,8у1+0,2у2≥12.
Покупатель бензина заинтересован в том, чтобы заплатить поменьше, то
есть функция L1=50у1+30у2 должна минимизироваться.
Таким образом, математическая модель двойственной задачи имеет вид:
1
L = 50 y 1 + 30 y 2 → min ,
0,6 y 1 + 0,4 y 2 ≥ 10,

0,8 y 1 + 0,2y 2 ≥ 12,
26
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
y i ≥ 0, i = 1,2.
Так как в двойственных задачах свободные члены в системе ограничений
и коэффициенты при переменных в целевой функции меняются местами, то
решение двойственной задачи можно получить из симплексных таблиц исходной задачи, потому что каждое преобразование симплексной таблицы исходной
задачи влечёт за собой преобразование таблицы для двойственной задачи, но
здесь уже возможно использование в промежуточных вычислениях недопустимых решений.
Используя последнюю симплексную таблицу и теорему двойственности,
получаем, что L1 min=820 тыс. руб. Решение двойственной задачи находим в
строке L последней симплексной таблицы в столбцах дополнительных переменных х3 и х4 : у1 =14 тыс. руб., у2 =4 тыс. руб.
Вопросы для самоконтроля
1. Как найти коэффициенты при переменных в целевой функции, а также
свободные члены в двойственной задаче?
2. Как определить тип экстремума для двойственной задачи?
3. Как определить знаки неравенств и переменных в двойственной задаче?
4. Как связаны матрицы коэффициентов при неизвестных в двойственных задачах?
5. Сформулируйте теорему двойственности.
6. Как найти решение двойственной задачи?
Задачи и упражнения для самостоятельного решения
Составить двойственные задачи для задач 2.4.1 – 2.4.2.
2.4.1. L = 2 x1 + 4 x 2 + x3 → max ,
2.4.2. L = x1 − 3 x 2 + x3 → max ,
 x1 + 2 x 2 − x3 ≤ 11,

2 x1 − x 2 + 3x3 ≤ 3,
 x + 2 x + x ≤ 12,
2
3
 1
 x1 − x2 + x3 ≤ 10,

≤ 6,
 2 x1 − x2
 x − 2 x + x ≤ 12,
2
3
 1
x j ≥ 0 , i = 1,2,3 .
x j ≥ 0 , i = 1,2,3 .
2.4.3. Площадь пашни фермерского хозяйства, которое занимается выращиванием пшеницы, ячменя и гречихи, составляет 36 га. Хозяйство располагает
700 чел. - смен трудовых ресурсов и 85 ц минеральных удобрений. Остальная
необходимая информация представлена в таблице:
27
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Показатели
Пшеница
Ячмень
Гречиха
Урожайность, ц/га
23
20
Затраты удобрений ц/га
0,5
0,4
0,8
Затраты труда, чел.-см./га
9,2
6,8
7,4
Себестоимость, тыс. руб./ц
1
0,8
1,5
Цена реализации, руб./ц
1,4
1,1
2,0
7
Требуется составить математическую модель задачи. Сформулировать
двойственную задачу и построить её модель.
2.4.4. Площадь пашни хозяйства, которое занимается выращиванием картофеля, свёклы и моркови, составляет 50 га. Хозяйство располагает 950 чел. смен трудовых ресурсов и 100 ц минеральных удобрений. Остальная необходимая информация представлена в таблице:
Показатели
Картофель Свёкла
Морковь
Урожайность, ц/га
250
200
180
Затраты удобрений ц/га
0,2
0,3
0,4
Затраты труда, чел.-см./га
9,5
7,8
7,5
Себестоимость, тыс. руб./ц
0,4
0,8
0,9
Цена реализации, руб./ц
0,9
1,3
1,5
Требуется составить математическую модель задачи. Сформулировать
двойственную задачу и построить её модель.
В задачах 2.4.5 – 2.4.10 составить двойственную задачу и найти решение
пары взаимно двойственных задач из одних и тех же симплексных таблиц.
2.4.5. L= x1 + 2 x 2 → max
2.4.6. L= 5 x1 + 6 x 2 → max
6 x1 + 2 x 2 ≤ 11
 x1 + x 2 ≤ 12
 4 x + 3x ≤ 8
 x + 3 x ≤ 24
 1
 1
2
2


 x1 + 2 x 2 ≤ 4
3 x1 + x 2 ≤ 30
 x1 , x 2 ≥ 0
 x1 , x 2 ≥ 0
28
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2.4.7. L= x1 + 2 x 2 → max
− 2 x1 + 3 x 2 ≤ 6
 x + 3 x ≤ 15
2
 1
x
x
2
+
 1
2 ≤ 15
 x − 2 x ≤ 15
2
 1
x
x
,

1 2 ≥0
2.4.9. L= 2 x1 + 3 x 2 → max
2 x1 + 2 x 2 ≤ 12
 x + 2x ≤ 8
2
 1
4
x
≤ 16
 1

4 x 2 ≤ 12

 x1 , x 2 ≥ 0
2.4.8. L= x1 + x 2 → max
2 x1 + 4 x 2 ≤ 1
 4x
≤1
 1

8x2 ≤ 1

 x1 , x 2 ≥ 0
2.4.10. L= 2 x1 + x 2 → max
− x1 + x 2 ≤ 4
 x
≤4
 1
x2 ≤ 5

 x −x ≤0
2
 1
,
x
x
 1 2 ≥0
2.5. Транспортная задача
Пример 2.5.1. Требуется составить план минимальной стоимости доставки 135 ед. груза oт трех поставщиков, у которых имеется соответственно 55, 65
и 15 ед. груза к трем потребителям. Причем первому из них требуется 35 ед.
груза, второму - 60 ед. и третьему - 40 ед. Стоимости перевозки 1 ед. груза (тарифы) приведены в таблице:
Потребители
Поставщики
В1
В2
В3
А1
1
3
6
А2
4
2
3
А3
2
1
5
Решение. Решим эту задачу методом потенциалов, алгоритм которого
предусматривает следующие этапы:
1). Условия задачи записываются в транспортную таблицу:
Bj
B1
B2
B3
ai
Ai
1
3
6
A1
55
35
20
4
2
3
A2
65
40
25
2
1
5
A3
15
15
bj
35
60
40
29
135
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Ресурсы поставщиков записывают в столбце аi, потребности потребителей – в строке bj, тарифы – в левом верхнем углу соответствующих клеток таблицы;
2). Составляется опорный план. Наиболее эффективным методом для его
получения является метод наилучших оценок. Самые низкие тарифы, равные 1,
в клетках (1,1) и (3,2), то есть наиболее выгодные (самыми дешевыми) являются поставки груза от поставщика А1 к потребителю В1 и от А3 к В2. С этих клеток начинается планирование грузоперевозок. Итак, потребителю В1 необходимо 35 ед. груза. Поставщик А1, наиболее эффективный для этого потребителя,
может удовлетворить его потребности полностью. Поэтому в клетку (1,1) записывается величина поставки 35. Для потребителя В2 наиболее эффективный поставщик А3 может обеспечить лишь часть его потребности в грузе. Поэтому в
клетку (3,2) записывается величина поставки 15, составляющая весь ресурс А3.
Недостающие 45 ед. груза обеспечивает поставщик А2, являющийся наиболее
эффективным после А3 поставщиком груза для В2. Наконец, для потребителя В3
наиболее эффективным является поставщик А2, оставшийся ресурс которого
позволяет обеспечить 20 ед. груза для В3. Недостающие 20 ед. груза можно
взять только у А1.
 35 0 20 


В результате получается опорный план X o =  0 45 20  . Суммарные
 0 15 0 


транспортные расходы (величина целевой функции задачи) в данном случае
будут равны
C0 = 1·35 + 6·20 + 2·45 + 3·20 + 1·15 = 320;
3). Полученный план проверяется на невырожденность. Невырожденным
считается вариант плана, в котором количество заполненных клеток l =
= m + n – 1, где т – число поставщиков, а п – число потребителей. Для представленного
в
транспортной
таблице
варианта
плана
имеем:
m = 3, n = 3, l = 5 = m + n – 1. Следовательно, данный вариант плана является
невырожденным.
Необходимо заметить, что в случае l< m + n – 1 невырожденности плана
добиваются, заполнением недостающих клеток нулями, причём целесообразно
выбирать клетки с меньшими тарифами.
4). План проверяется на оптимальность. С этой целью вводят потенциалы
строк Ui и потенциалы столбцов Vj. Индексы i или j потенциалов означают
номера соответствующих поставщиков или потребителей.
Для всех заполненных клеток должно выполняться условие
Ui + Vj = Сij.
Для рассматриваемого плана получаем систему уравнений:
30
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
U1 + V1 = 1,
U + V = 6,
 1 3
U 2 + V2 = 2,
U + V = 3,
3
 2
U 3 + V2 = 1.
Эта система линейных уравнений неопределенна, поскольку для нахождения 6 потенциалов имеется только 5 уравнений. Чтобы получить какое-либо
её решение, один из потенциалов полагают равным произвольному числу.
Пусть для определенности U1 = 0. Тогда остальные 6 неизвестных потенциалов
однозначно определяются из системы уравнений:
U2 = - 3, U3 = - 4, V1 = 1, V2 = 5, V3 = 6.
Полученные значения потенциалов записывает в соответствующие клетки транспортной таблицы:
Bj
B1
B2
B3
ai
Ui
Ai
1
3
6
A1
55
0
35
20
4
2
3
A2
65
-3
45
20
2
1
5
A3
15
-4
15
bj
35
60
40
135
Vj
1
5
6
муле:
Далее, для каждой незаполненной клетки определяют ее оценки по фор-
∆(i, j) = Cij – (Ui + Vj)
(2.3.2)
Для рассматриваемого плана получаются следующие оценки незаполненных клеток:
∆(1,2) = 3 - (0 + 5) = -2,
∆(2,1) = 4 - (-3 + I) = 6,
∆(3,1) = 2 - (-4 + I) = 5.
∆(3,3) = 5 - (-4 + 6) = 3.
При оптимальном плане для всех незаполненных клеток их оценки неотрицательные.
В нашем случае полученный план перевозки грузов Хо не является оптимальным и может быть улучшен путем перераспределения части груза в клетку
(1,2), имеющую отрицательную оценку, где нарушается условие оптимальности.
Примечание: если при проверке плана на оптимальность оказывается, что
несколько незаполненных клеток имеют отрицательные оценки, то груз перераспределяют в клетку с наиболее отри- цательной оценкой. Если же наи31
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
более отрицательная оценка получается у двух или более клеток, то груз перераспределяют в клетку с наименьшим среди них тарифом;
5). Составляется новый вариант плана. С этой целью для клетки (1,2), в
которой не выполняется признак оптимальности, строится «замкнутый маршрут», который представляет собой замкнутый многоугольник с прямыми углами, все вершины которого расположены в заполненных клетках, кроме одной
– (1,2).
Вершину полученного многоугольника,
расположенную в клетке нарушения оптимальности (1,2), обозначают знаком (+), следующую (-) и далее знаки чередуются. Затем
из вершин, обозначенных знаком (-), выбирается наименьшая величина поставки (в данном случае min {20;45} = 20) и она
прибавляется к запланированному объему грузоперевозки в клетках, где вершины обозначены знаком (+), и вычитается из запланированного объема грузоперевозки в клетках, где вершины обозначены знаком (-). В результате получа 35 20 0 


ется вариант плана X 1 =  0 25 40  .
 0 15 0 


Суммарные транспортные расходы (величина целевой функции) при таком плане составляют
C1 = 1·35 + 3·20 + 2·25 + 1·15 + 3·40 = 280.
При этом С1 <C0.
Результаты запишем в новую транспортную таблицу:
Bj
B1
Ai
A1
1
B2
3
35
A2
4
B3
6
20
2
3
25
A3
bj
Vj
2
1
35
V1 = -2
40
5
15
60
V2 = 0
40
V3 = 1
ai
Ui
55
3
65
2
15
1
135
280
Далее алгоритм метода потенциалов повторяется. Полученный план проверяется сначала на невырожденность, а затем – на оптимальность. В этом случае имеем:
32
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
U1 + V1 = 1,
U + V = 3,
 1 2
U 2 + V2 = 2,
U + V = 1,
2
 3
U 2 + V3 = 3.
Отсюда, полагая V2 = 0, получаем: U1 = 3, U2 = 2, U3 = 1, V1 = -2,
V3 = 1.
Оценки незаполненных клеток согласно (3,2) будут таковы:
∆(1,3) = 6 - (3 + 1) = 2,
∆(2,1) = 4 - (2 - 2) = 4,
∆(3,1) = 2 - (1 - 2) = 3,
∆(3,3) = 5 - (1 + 1) = 3.
Поскольку все оценки неотрицательные, заключаем, что найденный нами
план является оптимальным.
 35 20 0 


Ответ: X 1 =  0 25 40  ; Сmin = 280.
 0 15 0 


Алгоритм метода потенциалов применим к решению закрытых задач, когда потребности равны запасам. В противном случае задача называется открытой. Её сводят к закрытой введением фиктивного поставщика, когда потребности превышают запасы, или фиктивного потребителя, если запасы превышают потребности, причём для фиктивных поставщиков или потребителей
берётся нулевой тариф.
Вопросы для самоконтроля
1. Какие основные этапы решения транспортных задач предусматривает
алгоритм метода потенциалов?
2. Как составляется опорный план по методу наилучших оценок?
3. Какой план называется невырожденным и как вырожденный план превратить в невырожденный?
4. Как проверяется план на оптимальность по методу потенциалов?
5.Сформулируйте признак оптимальности для метода потенциалов.
6.Какие транспортные задачи называются закрытыми, какие открытыми?
7.Каким образом открытая транспортная задача приводится к закрытой?
Задачи для самостоятельной работы
Решите методом потенциалов задачи 2.5.1-2.5.4, где А = (а1; а2; …; аm) ресурсы поставщиков; В = (b1; b2; …; bn)- потребности потребителей;
33
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
 с11 с12

с
с
С =  21 22
..
..

с
 m1 сm 2
... с1n 

... с2 n 
- – матрица тарифов.
... .. 

... сmn 
2.5.1. А = (100; 150; 50)
2.5.2. А = (130; 100; 170)
В = (75; 80; 60; 85)
В = (150; 120; 80; 50)
6 7 3 5


С = 1 2 5 6
 8 10 20 1 


 3 5 7 11


С = 1 4 6 3 
 5 8 12 7 


А = (30; 40; 53)
2.5.3.
2.5.4. А = (200; 150; 50)
В = (25; 32; 25; 41)
 23 27 16 18 


С =  12 17 20 51 
 22 28 12 32 


В = (100; 50; 150; 100)
 5 1 3 4


С =  2 3 4 2
8 5 1 6


2.5.5. Рассчитать оптимальный график перевозок удобрений с трех складов в три хозяйства. На складах имеется следующее количество удобрений: на
первом – 600 т, на втором – 400 т, на третьем – 250 т. Потребности хозяйств в
удобрениях составляют 450, 360 и 440 т, соответственно. Затраты на перевозку
1 т представлены в таблице:
Хозяйства
Склады
1
2
3
1
10
9
6
2
12
13
8
3
5
7
11
2.5.6. В хозяйстве силосная масса заготовлена в трех траншеях в количестве 500, 850 и 600 т, соответственно. Эту массу предстоит развести по четырем
фермам, сезонные потребности которых определены в следующем размере:
первой требуется 400 т силоса, второй – 350 т, третьей – 700 т и четвертой – 300
т. Расстояния от траншей до ферм (км) указаны в таблице:
Фермы
Траншеи
1
2
3
4
1
3
7
2
9
2
8
5
7
8
3
5
6
4
4
34
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Составить вариант перевозки силоса, минимизирующий суммарное расстояние перевозок.
2.5.7. Составить оптимальный план транспортировки комбикормов с трех
заводов, которые могут произвести 4600, 4800 и 4000 т соответственно в четыре
хозяйства, если первому из них требуется 3200 т комбикорма, второму – 5700 т,
третьему – 3200 т и четвертому – 1500 т. Затраты на перевозку
1 т представлены в таблице:
Заводы
1
2
3
Хозяйства
1
5
8
17
2
8
10
28
3
24
20
35
4
30
32
40
2.5.8. На трех пасеках имеется 560 пчелосемей, причем на первой – 200,
на второй – 150 и на третьей – 210 пчелосемей. Требуется отвезти их для опыления на точки, расположенные в четырех местах, причем первая вмещает 150
семей, вторая – 190, третья – 100, четвертая – 120 семей. Составить оптимальный план перевозки, если расстояния от пасеки до точек (в км) даны в таблице:
Пасеки
Точки
1
2
3
4
1
6
7
4
8
2
8
3
5
8
3
5
6
11
4
2.5.9. Составить оптимальный план доставки семян из трех хранилищ, где
имеется соответственно 100, 200 и 100 ц семян, на четыре опытных поля, если
на первое из них требуется доставить 80 ц, второе – 140 ц, третье – 100 ц, четвертое – 80 ц. Затраты на перевозку 1 ц приведены в таблице:
Хранилища
Поля
1
2
3
4
1
2
5
4
6
2
8
4
3
8
3
5
1
4
5
Для задач 2.5.10- 2.5.15 требуется спланировать перевозки так, чтобы их
общая стоимость была минимальной.
На трех базах А1, А2, А3 находится однородный груз в количестве a1, a2 , a3
35
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
т. Этот груз необходимо развезти пяти потребителям В1, В2, В3, В4, В5, потребности которых в данном грузе составляют в1, в2, в3, в4, в5 т соответственно. Матрица тарифов и значения а1, а2, а3 и в1, в2, в3, в4, в5 приведены в таблице.
2.5.10
В1 В2
В3
В4
В5
Запасы (аi)
А1
200
7
9
15
4
18
А2
250
13
25
8
15
5
А3
250
5
11
6
20
12
Потребности (вj)
80 260 100 140 120
700
2.5.11
Запасы (аi)
В1 В2
В3
В4 В5
19
8
14
5
9
А1
150
6
10
5
25
11
А2
200
7
13
8
12
14
А3
150
Потребности (вj)
60 140 100 80 120
500
2.5.12
Запасы (аi)
В1
В2
В3
В4
В5
3
10
6
13
8
А1
200
7
5
11
16
4
А2
300
12
15
18
9
10
А3
300
Потребности (вj)
220 120 160 100 200
800
2.5.13.
Запасы (аi)
В1
В2 В3
В4 В5
15
8
9
11
12
А1
100
4
10
7
5
8
А2
150
6
3
4
15
20
А3
250
Потребности (вj)
100 40 140 60 160
500
2.5.14
Запасы (аi)
В1
В2
В3
В4
В5
25
9
12
6
18
А1
300
4
7
5
11
19
А2
200
10
15
18
13
8
А3
200
Потребности (вj)
120 180 100 140 160
700
2.5.15.
Запасы (аi)
В1
В2
В3 В4
В5
15
8
5
21
15
А1
150
4
12
7
8
10
А2
200
11
20
13
4
5
А3
200
Потребности (вj)
100 180 40 120
110
550
36
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3. ТЕОРИЯ ИГР
3.1. Элементы теории множеств
При решении многих теоретико-игровых задач требуются сведения из
теории множеств, которые мы здесь приведём.
Под множеством понимают некоторую совокупность объектов, называемых его элементами. Множества обозначают большими латинскими буквами: А, В, … , а их элементы малыми: a, b,… .
Множества могут быть заданы: 1)перечислением элементов:
А={a1,a2,…,an}; 2) характеристическим свойством, а именно: множество, состоящее из всех элементов, для которых выполняется свойство Р(х), обозначается {x | P(x)}.
Множество, не содержащее элементов, называется пустым и обозначается Ø. Множества, содержащие конечное число элементов, называются конечными, в противном случае – бесконечными. Число элементов множества А обозначают |А|.
Множества, состоящие из одинаковых элементов, называются равными.
Если каждый элемент множества А является также элементом множества
В, то говорят, что А включается в В, или А есть подмножество множества В, и
обозначают А ⊂ В.
Число всевозможных подмножеств множества А равно 2n, где n=|А|.
Объединением множеств А и В называют множество А  В= {x | x ∈ А или
х ∈ В}.
Пересечением множеств А и В называют множество ∩
АВ ={ x | x ∈ A и
х ∈ В}.
Разностью множеств А и В называют множество А\В={x | x ∈ A и x ∉ B}.
Дополнением множества А называют множество Ā={x| x ∉ A}.
Декартовым произведением множеств А и В называют множество A × B =
={(x,y)| x ∈ A, y ∈ B }.
Если |А|=m, |В|=n, то | A × B |=mn.
Аналогично, A1 × A2 × ...An = {( x1, x 2 ,..., x n ) | x1 ∈ A1, x 2 ∈ A2 ,..., x n ∈ An }
Пример 3.1.1. Задать множество {-1,1} характеристическим свойством.
Решение. Так как корнями уравнения х2=1 являются числа -1 и 1, то
{-1,1}={x| x2=1}.
Заметим, что это же множество может быть задано также, например,
свойством |х|=1 или х4=1.
Пример 3.1.2. Задать множество {x| x2 – 5x+6=0} перечислением элементов.
Решение. Так как корни уравнения x2 – 5x+6=0 равны 2 и 3, данное множество можно задать в виде: {2,3}.
Пример 3.1.3. Среди множеств М1={1,2,3,4}, M2={4,3,2,1}, M3={1,2,2},
M4={1,2} найти равные и определить число элементов каждого множества.
37
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Решение. М1= M2, так как состоят из одинаковых элементов, а порядок, в
котором они записаны, не существенен. M3= M4, хотя в множестве M3 элемент
2 записан дважды, так как учитываются только различные элементы. По той же
причине |M1|= |M2|=4. |M3|= |M4|=2.
Пример 1.4. Для множеств A={2,5,6} и B={2, 4} найти A  B , A  B , А\В,
В\А и A × B .
Решение. Используя определения операций над множествами, получаем:
A  B ={2,4,5,6}; A  B ={2}; А\В={5,6}; В\А={4}; A × B ={(2,2), (2,4), (5,2),
(5,4), (6,2), (6,4)}.
Вопросы для самоконтроля
Что понимают под множеством? Приведите примеры множеств.
Какие способы задания множеств Вам известны?
Какие множества называются равными?
Что называется подмножеством данного множества?
Сколько подмножеств имеет множество, состоящее их n элементов?
Что называется объединением, пересечением, разностью, дополнением
и декартовым произведением множеств?
7. Как найти число элементов в декартовом произведении конечных
множеств?
1.
2.
3.
4.
5.
6.
Задачи и упражнения для самостоятельного решения
3.1.1. Задайте следующие множества с помощью характеристического
свойства:
а) {1, 4 , 9, 16, 25}; b) {2, 4, 6, 8, 10, 12}; c){3, 6, 9, 12, 15};
d) {1, 2}; e)[1;5]; f) (-1; 4].
3.1.2. Задайте следующие множества перечислением элементов:
a) {x| (x3-1)(x-1)=0};
b){x| x2-x+25=0};
c) {x| x2-4=0};
d){x| |x|=4};
e) {x| 2x=8};
f){x| 2x+3=5}.
3.1.3. Какие из перечисленных множеств являются конечными и бесконечными? Для конечных множеств укажите число элементов.
a) {x| x>7}:
b) {x| 2< x<5, x ∈ Z};
c) {x| x2 ≤ 4};
d) {x| x2 ≤ 4, x ∈ Z }.
3.1.4. Если А-множество натуральных чисел, делящихся на три, а Вмножество натуральных чисел, сумма цифр которых делится на 3, то равны ли
эти множества? Является ли множество А подмножеством множества В?
3.1.5.Укажите множество, имеющее ровно одно подмножество; ровно два
подмножества.
38
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3.1.6. Даны следующие множества: А - множество всех четырёхугольников; В - множество всех параллелограммов, С – множество всех прямоугольников; D – множество всех ромбов; Е – множество всех квадратов; F - множество
всех ромбов с прямыми углами. Какие из этих множеств равны между собой?
Какие из них являются подмножествами других?
3.1.7. Найдите все подмножества следующих множеств и подсчитайте их
число:
a) {1}; b) {a, b}; c) Ø; d) {1, 2, 3}.
Для множеств А и В найти A  B , A  B , А\В, В\А и A × B :
a) A= {3, 5, 6, 7, 8}; B={4, 6, 7, 8};
b) A={1, 2, 3}; B={4, 5};
c) A={x | -1≤x≤5}; B={x| -3≤x≤2};
d) A={x | 1≤x≤3}; B={x| 3≤x≤5}.
3.1.9 Найдите множества
a) A∩Ø; b) A  Ø; c) A\A; d) A\ Ø; e) A∩A; f) A  A.
из то | A  B |=
3.1.10. Докажите, что если |А|= n, |В|= m, |А∩В|=k, то
=n+m-k.
3.2. Бескоалиционные игры
В теории игр рассматриваются модели принятия оптимального (в какомто смысле наилучшего) решения в условиях конфликта, представляющего собой явление, встречающееся в природе или в обществе, в котором участники
имеют несовпадающие интересы и располагают различными способами достижения своих целей.
Модели конфликтов, в которых целью каждого из игроков является получение по возможности наибольшего индивидуального выигрыша, называют
бескоалиционными играми.
Моделью бескоалиционной игры является система Г=<I, {Si } i∈I , {H i } i∈I >,
где I={1, 2,…,n} ( n≥2) – множество игроков, Si (i ∈ I)- множество стратегий
(возможных действий) i – го игрока, а Hi (i ∈ I)– функция выигрыша i – го игрока, определённая на множестве ситуаций S=S1 × S2 × … × Sn и принимающая значения в множестве действительных чисел.
Пример 3.2.1. (Спор партнёров). Два экономических партнёра договариваются о совместном проведении одного из двух мероприятий D1 и D2, каждое
из которых требует их совместного участия. В случае совместного осуществления D1 первый получает доход в одну, а второй в две денежные единицы. Наоборот, в случае осуществления D2 первый получает две, а второй – одну денежную единицу. Наконец, если они выполняют различные действия, то выигрыш каждого из них равен нулю. Составить модель бескоалиционной игры.
Решение. Здесь I={1, 2}, где игрок 1 – первый партнёр, игрок 2- второй
партнёр. S1=S2={s1,s2}, где s1 – осуществить мероприятие D1, s2 - осуществить
мероприятие D2. Функции выигрыша игроков задаются следующим образом:
H1(s1,s1)=1; H1(s1,s2)=0; H1(s2,s1)=0; H1(s2,s2)=2; H2(s1,s1)=2; H2(s1,s2)=0 H2(s2,s1)=0;
H2(s2,s2)=1.
39
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Вопросы для самоконтроля
Что понимают под конфликтом?
Что является предметом теории игр?
Что называется бескоалиционной игрой?
Что представляет собой модель бескоалиционной игры?
Какое наименьшее число игроков может участвовать в бескоалиционной игре?
6. Кто может быть игроком? Приведите примеры.
1.
2.
3.
4.
5.
Упражнения для самостоятельного решения
3.2.1(Планирование выпуска продукции). Небольшое предприятие лёгкой
промышленности может выпускать продукцию одного из трёх видов: зонты,
шляпы и плащи, при этом доход его зависит от того, каким будет летний сезон дождливым, жарким или умеренным. В дождливое лето наибольший доход
принесёт производство зонтов, меньший производство плащей и совсем малый
– производство шляп. В жаркое лето наибольший доход даст производство
шляп, средний - производство зонтов, которые можно использовать, как от дождя, так и от солнца, и меньший – производство плащей. В умеренное лето
наибольший доход от производства плащей, несколько меньший от производства шляп и еще меньший от производства зонтов. Доходы предприятия определены таблицей:
Виды продукции
Лето
Дождливое Жаркое
Умеренное
Зонты
90
60
40
Шляпы
25
100
50
Плащи
70
50
60
Готовясь к летнему сезону, экономист при отсутствии прогноза погоды
должен принять решение, какой из трёх видов продукции выпускать. Построить
модель бескоалиционной игры.
3.2.2. (Экономико-экологическая проблема). Каждое из трёх предприятий, пользующихся для технических целей водой из некоторого водоёма, может или сбрасывать её без очистки, или же использовать очистные сооружения
для отработанной воды. Особенности водоёма и технологических процессов на
предприятиях таковы, что в случае, когда неочищенную воду сбрасывает не более одного предприятия, вода в водоёме остаётся пригодной для использования,
и предприятия убытка не несут. Если же неочищенную воду сбрасывают не менее двух предприятий, то каждый пользователь воды несёт убытки в размере
трёх единиц. Стоимость использования очистных сооружений обходится предприятию в одну единицу. Построить модель бескоалиционной игры.
3.2.3. (Борьба фирм за рынки посредством рекламы). Две конкурирующие
фирмы ведут борьбу за n рынков путём затрат денежных средств на рекламу.
40
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Фонды рекламных расходов первой и второй фирм составляют суммы в а и b
рублей соответственно. Прибыль, которую можно получить от i-го рынка, равна сi>0, и распределяется она между фирмами пропорционально суммам, затраченным ими на рекламу на этом рынке. Составить модель бескоалиционной
игры двух фирм, считая выигрышем каждой их них суммарную прибыль, полученную от всех рынков.
3.2.4. (Олигополия с назначением выпусков). Цена на некоторый товар с
насыщаемым спросом убывает по формуле Се-s, где S – совокупное предложение. В предположении нулевых затрат составить модель бескоалиционной игры, если количество товара, предлагаемого на рынке i-ым производителем равно хi (i=1, 2, …n).
3.2.5. (Назначение цен в дуополии). Дуополисты поставляют на рынок
p 
взаимозаменяемую продукцию, спрос на которую равен d 1 =  2 
 p1 
α
p 
и d 2 =  1 
 p2 
β
единиц товара, произведённых соответственно первым и вторым производителем, где р1 и р2 – цены на их продукцию, α>1 и β>1. Затраты на выпуск единицы продукции, у обоих производителей не зависят от масштабов производства и равны сi (i=1. 2). Составить модель бескоалиционной игры.
3.2.6.(Аукцион неделимого товара). Трактор должен быть куплен одним
из n участников аукциона. Его ценность для i-го участника измеряется количеством денег аi (i=1, 2,…,n), которые он готов заплатить за него. Будем для определённости считать, что 0<a1≤a2 ≤…≤an. Победителем считается тот, кто
предложил наиболее высокую цену. Эта сумма выплачивается продавцу. Считая, что начальная цена, назначаемая продавцом ≤
с а 1 и при одинаковых ценах
предпочтение отдаётся тому участнику, для которого ценность товара больше,
составить модель бескоалиционной
игры, считая, что доход каждого участника равен количеству сэкономленных денег, в случае, когда трактор достался ему, и нулю в противном случае.
3.2.7. (Конкуренция на однопродуктовом рынке). n фермеров производят
зерно. Рыночная цена 1т зерна находится по формуле c =
k
x1 + ... + x n
, где k -
некоторая постоянная, а x i (i = 1,..., n ) количество зерна, которое произвёл i -ый
фермер. Составить модель бескоалиционной игры n фермеров, если себестоимость 1т зерна, произведённого i -ым фермером равна s i .
3.2.8. (Премия). Администрация фирмы стимулирует рабочего экономить
сырьё и с этой целью внедряет премиальную систему оплаты труда. Выработка
рабочего составляла N изделий в час, себестоимость изделия – S руб. Если рабочий будет экономить х кг сырья на одном изделии, то его производительность снизится на х %. Цена реализации 1 изделия составляет С рублей, стоимость 1 кг ресурса – Р руб., расценка по оплате труда за 1 изделие – К руб., размер премии за экономию 1 кг ресурса – у рублей. Составить модель бескоалиционной игры администрации и рабочего.
41
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3.3. Антагонистические игры
Бескоалиционная игра называется игрой с постоянной суммой, если сумма выигрышей всех игроков в любой ситуации равна одному и тому же числу.
Антагонистической игрой называется бескоалиционная игра двух лиц с
нулевой суммой.
Модель антагонистической игры представляет собой систему Г= <SI, S2,
H>, где SI и S2 – множества стратегий игроков, H – функция выигрыша игрока
1. Функция выигрыша игрока 2 равна (–Н), так как в антагонистической игре
один игрок выигрывает столько же, сколько проигрывает другой, и поэтому
выигрыш игрока 1 называют также проигрышем игрока 2 и наоборот.
Бескоалиционная игра называется конечной, если множество стратегий
каждого игрока конечно.
Для конечных игр обозначения стратегий игроков обычно отождествляют
с их номерами.
Конечная антагонистическая игра называется матричной игрой формата
m × n, где m – число стратегий игрока 1, а n – число стратегий игрока 2.
Матричная игра формата m × n полностью задаётся платёжной матрицей
размерности m × n , называемой также матрицей игры:
 a11 a12

a
a
А=(аij)=  21 22
...
...

a
 m1 a m 2
... a1n 

... a2n 
,
... ... 

... amn 
где m- число стратегий игрока 1, n- число стратегий игрока 2; aij -выигрыш игрока 1, при условии, что он примет стратегию с номером i , а игрок 2 примет
стратегию с номером j, то есть в ситуации (i,j).
В i-ой строке платёжной матрицы располагаются всевозможные выигрыши игрока 1, при условии, что он примет стратегию с номером i, а в её j-ом
столбце – всевозможные проигрыши игрока 2 (выигрыши игрока 1), если игрок
2 примет стратегию с номером j.
Если в антагонистической игре хотя бы один из игроков имеет бесконечное число стратегий, то игра называется бесконечной антагонистической.
 1 2 3
 , определить число
2 1 0
Пример 3.3.1. Для игры, заданной матрицей 
стратегий игрока 1 и игрока 2. Какой выигрыш получат игрок 1 и игрок 2 в ситуации (1,2)?
Решение. Игрок 1 имеет 2 стратегии, так как число строк в матрице равно
2. Игрок 2 имеет 3 стратегии, так как в матрице игры - 3 столбца. Так как в
первой строке и втором столбце матрицы находится элемент 2, то выигрыш игрока 1 в ситуации (1,2) составляет 2 единицы, а выигрыш игрока 2 равен –2
единицы, потому что сумма выигрышей игроков в любой ситуации равна нулю.
Вопросы для самоконтроля
42
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1.
2.
3.
4.
5.
6.
7.
Какая игра называется игрой с постоянной суммой?
Какая игра называется антагонистической?
Что представляет собой модель антагонистической игры?
Какая игра называется конечной?
Какая игра называется матричной?
Что называется матрицей игры?
Как можно задать матричную игру?
Упражнения для самостоятельного решения
3.3.1. (Захват рынков сбыта). Фирма А пытается вытеснить фирму В,
имеющую два рынка сбыта, с одного из них. Общая сумма, выделяемая фирмой
А на эту цель, принимается равной единице и распределяется ею между двумя
рынками. Фирма В для удержания рынков также располагает единичной суммой средств и распределяет её между рынками. Выигрыш фирмы считается
равным сумме разностей своих средств и средств противника, выделенных на
каждый рынок, взятых с коэффициентом кi (i=1,2), характеризующим важность
соответствующего рынка. Построить модель бескоалиционной игры. Доказать,
что данная игра является антагонистической. Является ли данная игра матричной?
3.3.2. (Борьба за рынки сбыта). Фирма А имеет n рынков сбыта, а фирма В
желает их захватить. На эту цель фирма В может выделить b рублей. Фирма А
для защиты своих рынков располагает суммой в а рублей. Если для захвата
рынка i фирма В выделяет хi рублей, а фирма А для защиты своего рынка выделяет уi рублей, то фирма В получит доход ki(αiхi –yi ), а фирма А имеет ki(yi -αiхi). Коэффициент ki определяет степень важности рынка i, а коэффициент α i
– степень сопротивления рынка i фирме, производящей экспансионистскую
политику. Построить модель антагонистической игры. Является ли данная игра
бесконечной антагонистической?
3.3.3. Продавец яблок с каждого проданного килограмма получает прибыль, равную а рублей. Непроданные яблоки он возвращает на склад, но при
этом терпит убыток b рублей с каждого килограмма. Спрос, то есть количество
кг яблок, требуемых покупателем, точно не известен, но может быть равен 200,
250 или 300 кг. Построить модель матричной игры и её матрицу.
3.3.4. Предприятие реализует свою продукцию в двух магазинах. В торговую инспекцию поступили сведения о том, что в этих магазинах продаётся
бракованный товар в объёме 20 и 10 единиц. Инспектирующий орган намерен
провести инспекцию с целью обнаружения брака. Так как магазины находятся
далеко друг от друга, то может быть проверен только один из них. Предприятие
узнаёт о готовящейся инспекции и решает изъять бракованный товар, но по
техническим причинам изъятие может быть проведено только в одном магазине. Считая выигрышем инспектора объём обнаруженного им бракованного товара, который также является проигрышем предприятия, составить модель матричной игры.
43
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3.3.5. Две конкурирующие фирмы могут выставить на продажу по одному
из трёх видов товаров Т1, Т2, Т3 , причём Т2 имеет некоторые преимущества по
сравнению с Т1, Т1 по сравнению с Т3 , а Т3 - с Т2. Если фирмы выставляют на
продажу товар разных видов, то фирма поставившая товар, имеющий преимущества, получает прибыль в 1 денежную единицу, а другая терпит убыток в том
же размере. Если они выставляют товар одного вида, то они лишь покрывают
убытки, и прибыль их равна нулю. Составить матрицу игры.
Для матричных игр, заданных платёжной матрицей определить а)её формат, b)число стратегий игроков; с) записать матрицу выигрышей игрока 2; d)
выигрыши игроков в ситуации (2,1):
 −1

 2
3.3.6.  − 3

 4

 0
2
5
0 −2
−1
0
1
7
2
6
7

8
4

3

1
7
 3

3.3. 7.  − 1 4
 0 −5

2
2

1 .
0 
4
1
4
0 −3
§4. Принцип максимина для матричных игр
Теория матричных игр основана на гипотезе крайней осторожности поведения игрока, который не стремится получить как можно больший выигрыш,
а лишь хочет как можно меньше проиграть, то есть игрок выбирает лучший из
возможных худших вариантов. Пусть (аij) –матрица игры формата m × n .
Нижней ценой матричной игры называется величина v= m a xm i naij .
j
i
Стратегия игрока 1, гарантирующая ему получение выигрыша не менее v, называется максиминной стратегией игрока 1.
Правило нахождения нижней цены игры и максиминной стратегии:
1) находим в каждой строке платёжной матрицы минимальный элемент и
выписываем его в отдельный столбец;
2) выбираем в построенном столбце максимальный элемент или элементы, если их окажется несколько. Он (они) и будут равны нижней цене
игры, а номера строк, в которых расположены эти элементы будут соответствовать максиминным стратегиям игрока 1.
Верхней ценой матричной игры называется величина v = m i nm ax aij .
j
i
Стратегия игрока 2, запрещающая игроку 1 получение выигрыша большего v ,
называется минимаксной стратегией.
Правило нахождения верхней цены игры и минимаксной стратегии:
1) находим в каждом столбце платёжной матрицы максимальный элемент
и выписываем его в отдельную строку;
2) выбираем в построенной строке минимальный элемент или элементы,
если их окажется несколько. Он (они) и будут равны верхней цене игры, а номера столбцов, в которых расположены эти элементы будут
соответствовать минимаксным стратегиям игрока 2.
44
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Принцип, рекомендующий игрокам применять максиминную и минимаксную стратегии, называется принципом максимина.
Принцип максимина обладает устойчивостью в том смысле, что ни одному из игроков не выгодно односторонне отклониться от него, если матричная
игра имеет седловую точку, то есть такую ситуацию (i0, j0), что элемент её платёжной матрицы ai j является одновременно минимальным в своей строке и
максимальным в своём столбце. Для того чтобы матричная игра имела седловую точку необходимо и достаточно, чтобы верхняя цена игры была равна её
нижней цене, которая называется в этом случае ценой игры, а седловая точка –
решением игры. Седловые точки матричной игры, если они существуют, образуется максиминными и минимаксными стратегиями.
Пример 4.1. Для матричной игры, заданной платёжной матрицей
0 0
4 3 5 6


 2 0 7 1 ,
5 3 4 4


найти а) нижнюю и верхнюю цены игры; б) все максиминные и
минимаксные стратегии игроков; в) цену игры и седловые точки, если они существуют.
Решение. Воспользовавшись правилами нахождения верхней и нижней
цен игры, составим столбец из минимальных элементов строк матрицы и отметим звёздочкой в нём максимальные элементы. Аналогично составим строку из
максимальных элементов столбцов матрицы и отметим минимальные элементы.
minaij
j
*
4 3 5 63


 2 0 7 1 0
 5 3 4 4 3*


maxaij 5 3* 7 6
i
Таким образом, v = v =3, и цена игры равна 3. Максиминные стратегии: 1;
3. Минимаксная – 2. Седловые точки: (1,2) и (3,2).
Вопросы для самоконтроля
1. Что называется нижней ценой игры и максиминной стратегией игрока
1?
2. Сформулировать правило нахождения нижней цены игры и максиминной стратегии.
3. Что называется верхней ценой игры минимаксной стратегией игрока
2?
4. Сформулировать правило нахождения верхней цены игры и минимаксной стратегии.
5. В чём состоит принцип максимина?
45
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
6. Что называется седловой точкой матричной игры?
7. В каком случае существует седловая точка матричной игры и какие
стратегии её образуют?
8. Что называется ценой и решением игры?
Задачи и упражнения для самостоятельного решения
Для игр, заданных матрицами, найти нижнюю и верхнюю цены игры, а
также максиминные и минимаксные стратегии:
3 6 1 4


3.4.1.  5 2 4 2  ;
1 4 3 5


 1

3.4. 2.  − 1
− 2

−1
−1
2
− 1

3 .
− 1
Проверить, имеют ли игры, заданные матрицами, седловые точки:
 1 − 3 − 2


3.4.3.  0 5 4  ;
 2
3
2 

 4

0
3.4.4. 
1

− 2

0
4
−1
1
2
1
3
0
1

2
.
0

3 
3.4.5. Для игры, описанной в 3.3.5 найти верхнюю и нижнюю цену. Убедитесь, что игра не имеет седловой точки.
3.4.6. Два фермера могут поставить на рынок продукцию либо первого,
либо второго либо третьего сорта. Если они поставили продукцию разных сортов, то тот из них, кто поставил продукцию более высокого сорта получает
прибыль в 10 тысяч рублей, а другой терпит убытки в том же размере. Если они
поставляют товар одинакового сорта, то прибыль их равна нулю. Составить
матрицу игры. Имеет ли игра седловые точки?
4.7. Конкурирующие фирмы А и В имеют возможность производить изделия одного из пяти видов, которые затем продаются на одном рынке. Доход
фирмы А, зависящий от сочетания типов изделий, произведённых обеими фирмами, задан в таблице:
1
2
3
4
5
1
0
6
15
6
10
2
13
6
5
3
8
3
11
7
8
7
9
4
4
5
16
6
14
5
8
7
17
7
7
Целью фирмы А является максимизация своего дохода, а целью фирмы В минимизация дохода конкурирующей фирмы А. В полученной матричной игре
найти седловые точки.
3.4.8. Фирма может выставить на рынок три вида товаров. В зависимости
от состояния рынка её доходы в тыс. руб. представлены в таблице.
46
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Виды
Состояния рынка
товаров
1
2
3
4
1
1
0
-2
2
2
2
1
3
1
3
-3
-2
4
-2
Какой вид товара наиболее целесообразно поставить фирме на рынок?
3.4.9.Строительство дамбы высотой 1, 2 или 3 метра составляет соответственно 1, 2 и 3 млн. рублей. Ожидаемый ущерб от наводнения, уровень которого не превосходит 1м равен 5 млн. руб., 2м – 7млн. руб. 3м – 10млн. руб. Требуется дать рекомендации относительно необходимости строительства дамбы и
её высоты, если на это мероприятие выделено 15 млн. рублей, а выигрышем
проектировщиков считать сэкономленную сумму.
3.5. Смешанное расширение матричной игры
Если матричная игра не имеет седловой точки, её решение находят в
смешанных стратегиях.
Смешанной стратегией игрока 1 называют всякий вектор Х=(х1, х2 ,…,
хm), для которого хi ≥ 0;
m
xi
∑
i
= 1 и m – число теперь называемых чистыми стра-
=1
тегий игрока 1. Аналогично определяется смешанная стратегия игрока 2.
Компоненты смешанных стратегий с содержательной точки зрения можно интерпретировать как вероятности или относительные частоты, с которыми
игрок принимает соответствующую чистую стратегию. Когда возможна физическая смесь чистых стратегий, компоненты смешанных стратегий можно рассматривать как доли, в которых следует взять соответствующие чистые стратегии.
Каждая чистая стратегия может быть отождествлена со смешанной, у которой компонента, номер которой совпадает с номером данной чистой стратегии, равна единице, а остальные – нули.
По основной теореме теории матричных игр каждая игра формата m × n
имеет решение в смешанных стратегиях, представляющее собой пару смешанных стратегий (Х*,У*), называемых также оптимальными, где Х*=(р1*,
р2*,…,рm*) и У*=(q1*, q2*,…,qn*), и удовлетворяющих условию
ХАУ*Т≤Х*АУ*Т≤Х*АУТ,
означающему невыгодность одностороннего отклонения игрока от данного решения, при этом А - матрица игры, Х и У –любые смешанные стратегии игроков. Цена игры равна величине v=Х*АУ*Т, которая представляет собой средне
ожидаемый выигрыш игрока 1 в ситуации (Х*,У*).
Пара смешанных стратегий игрока (Z1,Z2) находится в отношении доминирования, при этом первая из них называется доминирующей, а вторая - доминируемой стратегией, если его выигрыш (проигрыш) при любых действиях
противника при применении Z1 будет не меньше (не больше), чем при применении стратегии Z2 .
47
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Принцип доминирования: игрок не должен использовать доминируемые
стратегии.
Чистая стратегия i1 – игрока 1 доминируема его чистой стратегией i2, если элементы i1-ой строки платёжной матрицы не превосходят элементов её i2 –
ой строки.
Аналогично, стратегия j1 игрока 2 доминируема его чистой стратегией j2,
если элементы j2-го столбца платёжной матрицы не превосходят элементов её j1
–го столбца.
В оптимальную смешанную стратегию, доминируемая чистая стратегия
входит с нулевой вероятностью.
В матрице игры можно вычеркнуть строки и столбцы, соответствующие
доминируемым стратегиям, получив при этом игру меньшего формата. Зная
решение новой игры, можно найти решение исходной, а именно: оптимальное
решение получается добавлением нулей на месте доминируемых стратегий, а
цены этих игр одинаковы.
 1 7 2


Пример 3.5.1. Вычеркнув строки и столбцы матрицы игры  6 2 7  , со5 1 6


ответствующие доминируемым стратегиям игроков, если они существуют, получить игру меньшего формата.
Решение. Вторая стратегия игрока 1 доминирует третью, после вычерки 1 7 2
 , в которой игрок 1 уже не
вания которой, получаем матрицу игры 
6 2 7
имеет чистых доминируемых стратегий. Первая стратегия игрока 2 доминирует
 1 7
 , в которой игроки
третью, вычеркнув которую, получаем матрицу игры 
 6 2
уже не имеют доминируемых чистых стратегий.
Вопросы для самоконтроля
1. Что называется смешанной стратегией игрока?
2. Что такое чистая стратегия игрока и как её можно представить в виде
смешанной стратегии?
3. Что называется ситуацией равновесия в смешанном расширении матричной игры?
4. Сформулировать основную теорему теории матричных игр.
5. Как определяется отношение доминирования стратегий, и какая стратегия называется доминируемой и доминирующей?
6. В чём состоит принцип доминирования?
7. Как найти по матрице игры чистые доминируемые и доминирующие
стратегии игроков?
8. Как можно применить принцип доминирования при нахождении решения матричных игр?
48
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Задачи и упражнения для самостоятельного решения
3.5.1.Определить могут ли следующие векторы быть смешанными стратегиями игрока 1 в матричной игре формата 2 × 3:
a) (0,5; 0,5); b) (0,1; 0,3; 0,6); c) (0,1; 0, 7); d) (-1;2); e) (0,5; 0,8; -0,3).
3.5.2. Определить могут ли следующие векторы быть смешанными стратегиями игрока 2 в матричной игре формата 2 × 3:
a) (0,6; 0,4); b) (0,1; 0,3; 0,6); c) (0,1; 0, 7); d) (-1; 2;0); e) (0,5; 0,8; -0,3).
В задачах 5.3 –5.6
стратегии.
3

3
3.5.3. 
4

0



3.5.5. 



2
2
4
2
4
4
2
4
0
уменьшить формат игры, вычеркнув доминируемые
0

4
;
0

8 
2
3

1
2
;
1
1

1 0,5 
1
3 1,5
2
2
1
1
2

3
3.5.4. 
1

0

4
5
4
3
5
8
7
2
1

2
1

6 
5

5
3.5.6.  2

3

4
5
4
3
6
4
4
7
4
7
3
5
1
1
3
0
2

6
7 .

2

2
3.6. Методы решения матричных игр
 a11
Для матричных игр формата 2 × 2 с матрицей А=
решение Х*=(р*, 1-р*) и
 a21
a12 
 оптимальное
a22 
У*=(q*, 1-q*) находится по формулам:
a22 − a21
;
a11 − a12 − a21 + a22
a22 − a12
.
q* =
a11 − a12 − a21 + a22
p* =
(3.6.1)
(3.6.2)
При этом цена игры (выигрыш игрока 1в ситуации равновесия) равен:
v=
a11a22 − a12 a21
.
a11 − a12 − a21 + a22
(3.6.3)
Пример 3.6.1. Найти графоаналитическим методом решение игры задан 2 3 11
 .
7 5 2 
ной матрицей 
Решение. Построим на промежутке [0;1] отрезки прямых:
v=2p+7(1-p)
v=3p+5(1-p)
v=11p+2(1-p),
49
(I)
(II)
(III)
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1313
1212
1111
1111
1010
99
88
77 77
66
55 55
44
33
33
22 22
22
11
00
00
0,20,2
0,40,4
0,60,6
0,80,8
11
1,21,2
Рис.3.6.1.
задающих выигрыш v игрока 1, при условии, что игрок 2 примет чистую стратегию соответственно 1, 2 и 3. Затем построим нижнюю огибающую и найдём
её наивысшую точку М (см. рис. 3.6.1).
Так как точка М есть точка пересечения прямых (II) и (III), то, исходя из
 3 11
 , найдём решение по формулам 3.6.1, 3.6.2, 3.6.3. Цена игры:
5 2 
3 ⋅ 2 − 5 ⋅ 11
− 49
2−5 3
2 − 11 9
p* =
=
≈ 4,45 .
v=
= ; q* =
= . Оптимальная
3 + 2 − 5 − 11 − 11
− 11 11
− 11 11
3 8
9 2
стратегия игрока 1: Х*=  ,  , а игрока 2 - У*=  0, ,  , так как его чистая
 11 11 
 11 11 
матрицы 
стратегия 1 не входила в решение.
Пример 3.6.2. Найти графоаналитическим методом решение игры задан 2 7


ной матрицей  3 5  .
11 2 


Решение. Построим на промежутке [0;1] отрезки прямых:
v=2q+7(1-q)
(I`)
v=3q+5(1-q)
(II`)
v=11q+2(1-q),
(III`)
задающих выигрыш v игрока 1, при условии, что он примет чистую стратегию
соответственно 1, 2 и 3. Затем построим верхнюю огибающую и найдём её
низшую точку N (см. рис. 3.6.2). Так как точка N есть точка пересечения пря2
7
 , найдём решение по формулам
мых (I`) и (III`), то, исходя из матрицы 
11
2


3.6.1, 3.6.2, 3.6.3:
q* =
2−7 5
.
=
− 14 14
v=
2 ⋅ 2 − 7 ⋅ 11 − 73
=
≈ 5,21 ;
2 + 2 − 7 − 11 − 14
50
p* =
2 − 11 9
;
=
− 14 14
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
13
12
11
11
10
9
8
7
7
6
5
5
4
3
3
2
2
2
1
0
0
0,2
0,4
0,6
0,8
1
1,2
Рис.3.6.2.
Оптимальная стратегия игрока 1: Х*= 
9
5 
,0,  , так как его чистая стра 14 14 
5 9
тегия 2 не входила в решение, а игрока 2 - У*=  ,  .
 14 14 
Задача отыскания оптимального решения для матричной игры формата
m × n с матрицей А=(аij), в случае, когда её цена v>0 сводится к решению пары
взаимно двойственных задач линейного программирования:
n
m
L= ∑ u j (max)
L1== ∑ t i (min)
j =1
i =1

∑ aij u j ≤ 1
 j =1
 uj ≥ 0

n
и
m
∑ aij t i ≥ 1
.
 i =1
 t i ≥ 0
Если u*=(u1*, u2*,…,u*n) и t*=(t*1 , t2*,…,t*m) - оптимальные планы этих
задач, то цена игры v =L
-1
max

 n
=  ∑ u * j 

 j =1
−1
−1
1
=L
min

m
=  ∑ t * i  , а

 i =1
компоненты
оптимальных стратегий Х*=(р1*, р2*,…,рm*) и У*=(q1*, q2*,…,qn*) находятся по
формулам р*i= t*i v; q*j =u*j v.
Если элементы платёжной матрицы положительны, то цена игры v >0. В
остальных случаях ко всем элементам платёжной матрицы можно прибавить
достаточно большую константу, что не изменит оптимальных стратегий, а цену
игры увеличит на эту же величину.
 2 3 11
 , найти оптимальПример 3.6.3. Для игры, заданной матрицей 
7 5 2 
ное решение, используя методы линейного программирования.
Решение. Так как все элементы матрицы игры положительны, то цена
игры v>0. Приходим к паре взаимно двойственных задач:
51
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
L1=t1+t2 (min)
L=u1+u2+u3 (max)
2u1 + 3u 2 + 11u 3 ≤ 1

 7u1 + 5u 2 + 2u 3 ≤ 1
u ≥ 0, u ≥ 0, u ≥ 0
2
3
 1
и
 2t 1 + 7t 2 ≥ 1
 3t + 5t ≥ 1
 1
2
.

11t 1 + 2t 2 ≥ 1
 t 1 ≥ 0, t 2 ≥ 0
Решим эти задачи симплекс –методом (см. доп. литература [2] ). Для чего
приведём первую задачу к канонической форме:
2u1 + 3u 2 + 11u 3 + u 4 = 1

 7u1 + 5u 2 + 2u 3 + u 5 = 1 , где u4 ≥0 и u5 ≥ 0.
 L −u −u −u = 0
1
2
3

Составим симплексную таблицу:
БП
СЧ
u1
u2
u3
u4
u5
u4
1
2
3
11
1
0
u5
1
7
5
2
0
1
L
0
-1
-1
-1
0
0
Выберем разрешающий столбец, который соответствует наименьшему
отрицательному коэффициенту в строке L. Возьмём, например, u2. Выбираем
вторую строку разрешающей, так как для неё отношение свободного члена к
положительному элементу разрешающего столбца минимально.
Составим вторую таблицу, в которой первая строка получена делением
разрешающей строки на разрешающий элемент 5; вторая есть результат сложения первой строки второй таблицы, умноженной на(-3) с первой строкой первой таблицы. Строка L есть сумма соответствующей строки первой таблицы с
первой строкой второй таблицы.
БП
СЧ
u1
u2
u3
u4
u5
u2
0,2
1,4
1
0,4
0
0,2
u4
0,4
-2,2
0
9,8
1
-0,6
L
0,2
0,4
0
-0,6
0
0,2
Во второй таблице разрешающий столбец u3, а разрешающая строка вторая. Поделим её на разрешающий элемент 9,8 и запишем в первой строке третьей таблицы, а затем преобразуем её так, чтобы в столбце u3 остальные элементы
обратились в нуль. Для этого первую строку третьей таблицы умножим на (0,4) и сложим с первой строкой второй таблицы. Строка L третьей таблицы получается сложением соответствующей строки второй таблицы с первой строкой
этой же таблицы, умноженной на 0,6. В результате получаем таблицу
БП
СЧ
u1
u2
u3
u4
u5
u3
2/49
- 11/49
0
1
5/49
-3/49
u2
9/49
73/49
1
0
-2/49
11/49
L
11/49
13/49
0
0
3/49
8/49
Так как все коэффициенты в строке L неотрицательны, то преобразования
закончены. Из последней таблицы можно найти решение двойственных задач, а
именно: в двойственных задачах свобод- ные члены в неравенствах и коэф52
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
фициенты в целевой функции меняются местами, и поэтому решение двойственной задачи находится в строке L последней таблицы в столбцах u4 и u5. Та3 8 
9 2
u*=  0, ,  .
, ,
 49 49 
 49 49 
49
Следовательно, цена игры v = ≈4,45.
11
3 49 3
8 49 8
3 8
и Х*=  ,  .
р*1= ⋅ = ; р*2= ⋅ =
49 11 11
49 11 11
 11 11 
2 49
9 49 9
9 2
q*1=0; q*2= ⋅ = ; q*3= ⋅
и У*=  0, ,  .
49 11
49 11 11
 11 11 
ким образом, Lmax=
11
,
49
t*= 
Вопросы для самоконтроля
1. Как найти решение игры формата 2 × 2?
2. Как найти решение матричной игры графоаналитическим методом?
3. К какой паре взаимно двойственных задач линейного программирования сводится задача нахождения матричной игры?
4. Как по симплексной таблице найти решение двойственной задачи?
Задачи и упражнения для самостоятельного решения
3.6.1. Предприниматель может выставить на рынок два вида товаров.
Найти решение матричной игры, если его доходы в тыс. руб. в зависимости от
спроса определяются следующей таблицей:
Предложение
1
2
Спрос
1
2
0
2
0
4
3.6.2. (Планирование выпуска сельхозпродукции). Фермер может произвести 2 вида продукции. Если произведённая им продукция будет пользоваться
спросом, то он получит прибыль от её реализации соответственно 15 и 25 тыс.
руб. Если же продукция не будет пользоваться спросом, то он потерпит убытки
(порча, хранение и т.д.) в размере соответственно 3 и 5 тыс. руб. При неизвестном потребительский спросе требуется определить, какой тип продукции следует производить с целью максимизации среднеожидаемой гарантированной
прибыли. Истолковать решение как физическую смесь стратегий.
3.6.3. (Выбор момента поставки товара на рынок). Фирма А поставляет на
рынок клубнику в течение четырёх недель. Другая фирма В, производящая
аналогичный товар, пытается её разорить. Цена товара фиксирована. Чем позже
поставляется товар на рынок, тем выше его качество, а реализуется только товар более высокого качества. Если же на рынок одновременно поступают оба
товара, то они имеют одинаковый спрос. Построить матрицу игры. Найти и ис53
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
толковать решение игры, уменьшив её формат, используя принцип доминирования, если доход от реализации товара за одну неделю равен 4 тыс. рублей.
Решить эту же задачу, при условии, что поставки велись в течение трёх недель.
3.6.4. Найдите решение матричной игры упражнения 3.4.
3.6.5. На урожайность сахарной свёклы влияют природно-экономические
условия: У1, У2, У3, У4. Сельскохозяйственное предприятие может применить
агротехнические мероприятия Х1, Х2, Х3, Х4 . В таблице представлена зависимость урожайности свёклы (в тоннах) от природно-экономических условий:
У1
31
32
30
38
Х1
Х2
Х3
Х4
У2
33
31
34
31
У3
34
35
36
37
У4
35
38
41
40
Построить модель матричной игры. Следуя принципу доминирования,
уменьшить формат игры, а затем найти её решение, используя графоаналитический метод.
3.6.6. Фермер может засеять поле культурами К1 и К2. Его доход (в тыс.
руб.) в зависимости от сочетания погодных условий задан в таблице:
Культуры
К1
К2
1
6
1
Погодные условия
2
4
3
3
2
7
Найти решение игры графоаналитическим методом и истолковать полученное решение как физическую смесь стратегий.
3.6.7. Фирмы А и В могут вложить свой капитал в производство товаров
различных видов. Прибыль фирмы А, зависящая от сочетания типов произведённых товаров, представлена в таблице:
1
2
3
4
1
3
2
4
0
2
3
4
2
4
3
4
2
4
2
4
0
4
0
8
Считая, что цель фирмы А состоит в максимизации своей прибыли, а –
фирмы В - в разорении конкурирующей фирмы А, найти оптимальные смешанные игроков и цену игры, используя принцип доминирования.
3.6.8. Состояние рынка ценных бумаг определяется многими факторами,
которые сгруппированы в 3 состояния. Инвестор предполагает вложить свой
капитал в три вида ценных бумаг. Его доходы в зависимости от состояния рынка при вложении в один вид акций в тыс. условных единиц определяются таблицей
54
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Виды
Акций
1
2
3
1
1
-1
-2
Состояния рынка
2
-1
-1
2
3
-1
3
-1
Дать рекомендации инвестору, в каком соотношении ему следует распределить капитал с целью максимизации средне ожидаемой прибыли.
3.6.9. Сельскохозяйственное предприятие может посеять одну их трёх
культур. При отсутствии прогноза погоды требуется установить, какую из
культур сеять, чтобы максимизировать средне ожидаемый доход, если доходы
(в тыс. руб.) в зависимости от погоды заданы в таблице:
Культуры
1
2
3
Сухое
4
3
0
Лето
Нормальное Дождливое
1
3
5
2
6
8
Используя методы линейного программирования, найти решение игры и
истолковать его как физическую смесь стратегий.
3.6.10. (Выбор ассортимента). На базе торговой организации имеется 3
типа товаров. Прибыль от реализации каждого из видов товаров равна 20 тыс.
рублей. Если же товар не будет пользоваться спросом, то убытки от его хранения и порчи принесут убытки соответственно 10, 5 и 3 тыс. рублей. Построить
матрицу игры, найти её решение и истолковать его как физическую смесь стратегий.
3.6.11. (Профилактический осмотр технической системы). Техническая
система состоит из трёх блоков, отказ каждого из которых ведёт к отказу всей
системы. Для предупреждения простоя системы можно провести перед началом
её работы проверку и замену элемента одного из блоков в случае его неисправности. Отказ блоков приводит к убытку соответственно 10, 12 и 15 тыс. рублей,
что существенно превышает расходы на их профилактику. Требуется выбрать
блок для профилактического осмотра с целью минимизации средне ожидаемого
убытка.
В задачах 3.6.12 – 3.6.16 найти решение матричных игр графоаналитическим методом.
2 3 7
1 2 6
3.6.12. 
 .
 .
3.6.13. 
6
3
1
7
3
1




55
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1

2
3.6.14. 
6

3
7

3
.
1

2 
 0 4


3.6.15.  3 3  .
 4 0


1 7


3.6.16.  4 4  .
7 1


3.7. Игры с природой.
Если один из игроков, как правило, игрок 2, является стихийной силой
(например, покупательский спрос, уровни температур или влажности окружающей среды и т.д.), то такие игры называют играми с природой или средой.
Если принять гипотезу антагонизма, которая состоит в предположении,
что среда ведёт себя наихудшим образом по отношению к принимающему решение, то в случае, когда игроки имеют конечное число стратегий, к таким играм можно применить методы матричных игр, так как такую игру можно задать
матрицей выигрышей А=(аij) игрока 1. Однако возможны и другие гипотезы о
поведении среды.
Если игрок знает только, какие могут быть состояния среды, то происходит принятие решения в условиях неопределённости. Если же игрок имеет дополнительную информацию о поведении среды, например, известен прогноз
погоды или вероятности наступления тех или иных её состояний, то в этом случае говорят о принятии решения в условиях риска.
Критерии оптимальности для игр с природой в условиях неопределённости
Критерий Вальда основан на гипотезе крайнего пессимизма игрока по
отношению к поведению среды, а именно: предполагается, что среда ведёт себя
наихудшим образом по отношению к принимающему решение.
Оптимальной по данному критерию стратегией является максиминная
стратегия.
Критерий Гурвица связан с введением так называемого коэффициента
пессимизма α ( 0 ≤ α ≤ 1). Гипотеза о поведении среды состоит в том, что наихудший вариант реализуется с вероятностью α, а наилучший с вероятностью 1α.
Оптимальной по этому критерию считается та стратегия, для которой величина αm i naij + (1 − α )m a xaij является наибольшей.
j
j
Критерий Лапласа основан на гипотезе равной вероятности состояний
среды. Оптимальной по этому критерию является та стратегия, для которой величина
1
n
n
a ij
∑
j
будет наибольшей.
=1
Критерий Сэвиджа основан на преобразовании матрицы выигрышей (aij )
в так называемую матрицу сожалений (rij ) , где rij = m a xaij − aij .
i
Оптимальной по данному критерию считается минимаксная стратегия
56
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
для матрицы сожалений.
Критерий оптимальности Байеса для игр с природой в условиях риска
Если известны вероятности qj (j=1,2,…,n) наступлений соответствующих
состояний среды, то оптимальной считается та стратегия игрока 1, для которой
его средне ожидаемый выигрыш
n
aij q j
∑
j
максимален.
=1
Пример 7.1. В таблице 3.7.1 указаны доходы с 1га, полученные фермером
при производстве зерновых, подсолнечника и корнеплодов в зависимости от
уровней температур в летний период. Рассматривая данную ситуацию как игру
фермера с природой, найти его оптимальные стратегии по критериям Вальда,
Гурвица (коэффициент пессимизма α= 0,2 и α=0,5), Сэвиджа, Лапласа, а также
Байеса, используя данные многолетних наблюдений, по которым прохладный
и нормальный уровень наблюдаются с вероятностью 0,375,а тёплый –0,25.
Таблица 3.7.1
Доход с 1 га,
руб.
Уровни температур
Прохладный
Нормальный
Теплый
Зерновые
227,03
1035,41
164,10
Подсолнечник
695,94
473,97
207,56
Корнеплоды
1531,48
1052,29
-227,19
Решение.
Доход с
1 га,
руб.
З
Уровни температур
Min
Кр. Гурвица
Таблица 3.7.2
α=0,2
α=0,5
Кр.
Лапласа
1035,4
861,15
599,76
492,18
514,44
207,56
695,94
598,27
451,76
459,16
490,62
-227,19
1521,8
1179,75
652,15
785,53
912,12
Прохладный
Нормальный
Теплый
227,03
1035,41
164,10
164,10
П
695,94
473,97
207,56
К
1531,48
1052,29
-227,19
З
Матрица сожалений
1254,45 16,87
43,46
1254,45
П
835,54
578,32
0
835,54
К
0
0
434,75
434,75
Кр. Сэвиджа
Max
Кр.
Байеса
Мax
Для нахождения оптимальной стратегии по критерию Вальда используем
правило нахождения максиминной стратегии.
57
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Для нахождения оптимальных стратегий по критерию Гурвица составляем столбец из максимальных элементов строк, а затем, находим те стратегии,
для которых величина αm i naij + (1 − α )m a xaij является наибольшей.
j
j
По критерию Лапласа для оптимальных стратегий среднее арифметическое элементов строки платёжной матрицы наибольшее.
Для нахождения оптимальных стратегий по критерию Сэвиджа строим
матрицу сожалений, а затем применяем к её строкам правило нахождения минимаксной стратегии.
Решение данной задачи удобно расположить в таблице (см. таб.3.7.2).
Клетки, соответствующие оптимальным стратегиям по каждому критерию, заштрихованы. Таким образом, оптимальная по критерию Вальда стратегия 2,
выигрыш 207,56; оптимальная по критерию Гурвица (α= 0,2) стратегия 3, выигрыш 1179,75; (α=0,5) стратегия 3 выигрыш 652,15; оптимальная по критерию
Лапласа стратегия 3, выигрыш 785,53; оптимальная по критерию Сэвиджа стратегия 3, риск 434,75; по Байесу стратегия 3, выигрыш 912,12.
Пример 7.2. (О выборе уровня наценки). Продавец закупает товарысубституты (заменители) по оптовым ценам: хлеб ржаной - 3 руб. за 1 буханку,
батон - 5 руб. за 1 шт., пряники 18 руб, за 1 кг, печенье – 30 руб., за 1 кг. Возможная торговая наценка может составлять 10% - 30%. По результатам маркетинговых исследований объёмы продаж в зависимости от уровня предполагаемых доходов совокупного Покупателя представлены в таблице.
Виды продукции
Нижний
уровень Верхний
уровень Оптовая
доходов Покупателя доходов Покупателя цена
При на- При на- При на- При на- единицы
продукценке
ценке
ценке
ценке
ции, руб
10%
30%
10%
30%
Хлеб ржаной, шт.
900
1000
800
700
3
Батон, шт.
900
900
1000
1000
5
Пряники, кг
400
100
400
200
18
Печенье, кг
500
0
480
20
30
Требуется определить процент наценки, позволяющий максимизировать
средне ожидаемую прибыль Продавца.
Решение. Данная ситуация может быть рассмотрена как игра, в которой
участвуют Продавец (игрок 1) и Покупатель (игрок 2), при этом имеется в виду
совокупный покупатель (покупательский спрос). Стратегии игрока 1: сделать
наценку в 10% (стратегия 1) и 30% (стратегия 2). Состояния среды – нижний
(состояние 1) и верхний (состояние 2) уровни доходов Покупателя.
Доход Продавца в различных ситуациях определяется следующим образом:
(1,1): 900·0,3+900·0,5+400·1,8+500·3=2940;
(2,1): 1000·0,9+900,1,5+100·5,4=2490
58
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
(1,2): 0,3·800+0,5·1000+400·1,8+480·3=2900
(2,2): 700·0,9+1000·1,5+200·5,4+20·9=3390.
 2940 2900 
 .
 2790 3390 
Получаем матрицу: 
Так как интересы Продавца и Покупателя противоположны, то, используя
формулы
(6.1),
(6.2)
и
(6.3),
находим,
что
цена
игры
2940 ⋅ 3390 − 2790 ⋅ 2900 1875600
=
= 2931 руб., а оптимальное решение игро640
2940 + 3390 − 2790 − 2900
3390 − 2790
*
ка 1: Х* = (0,94; 0,06), так как р*=
≈ 0,94, а игрока 2: Y = (0.77;
640
3390 − 2900
. Это означает, что Продавец при применении
0,23), так как q*=
640
v=
стратегии 1 (наценка 10%) с вероятностью 0,94, а стратегии 2 (наценка 30%) с
вероятностью 0,06 получит средне ожидаемый доход не менее 2931 руб. даже
при условии, что уровень доходов Покупателя будет самым неблагоприятным
(нижний уровень с вероятностью 0,77, а верхний – с вероятностью 0,23).
Таким образом, если Продавец сделает наценку 10%⋅ 0,94 + 30%⋅ 0,06 ≈
11,2%, то получит наибольшую гарантированную прибыль.
Вопросы для самоконтроля
1. Что понимают под игрой с природой?
2. Чем отличается принятие решений в условиях неопределённости и в
условиях риска?
3. На каких гипотезах о поведении среды основаны критерии оптимальности Вальда, Гурвица, Лапласа, Сэвиджа и Байеса для игр с природой?
4. Какие стратегии игрока являются наилучшими по этим критериям?
Задачи и упражнения для самостоятельного решения
3.7.1. Предприниматель имеет возможность вложить свои деньги либо в
государственные ценные бумаги, либо в акции высокодоходного предприятия.
Доходы предпринимателя в зависимости от состояния экономики представлены
в таблице.
Объект
Вложения
Ценные
бумаги
Акции
Состояния экономики
Кризис
Стабильное
состояние
0
3
-5
5
Подъём
5
13
Рассматривая данную ситуацию как игру предпринимателя со средой,
оценить его стратегии по критериям Вальда, Гурвица (полагая коэффициент
59
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
пессимизма α= 0,2 и α=0,5), Сэвиджа и Лапласа.
3.7.2. Бригада рабочих должна к следующей весне построить электростанцию. В связи с надвигающейся зимой возникла проблема угольных запасов
для отопления домов. Если зима будет нормальной, то потребуется 15 т угля,
для суровой 18 т, а для мягкой – 12 т. Весной бригада переезжает на новый объект строительства, и излишки угля будут потеряны. В зависимости от того, какая будет зима – мягкая, нормальная или суровая, стоимость тонны угля соответственно составляет 10, 12, 14 денежных единиц за 1т. В настоящий момент
можно приобрести уголь по 10 денежных единиц за тонну, а остальное закупить потом. Считая доходом бригады деньги, сэкономленные от покупки угля в
данный момент, составить матрицу игры с природой и оценить стратегии бригады рабочих по критериям Вальда, Гурвица (полагая коэффициент пессимизма
α= 0,4 и α=0,8), Сэвиджа и Лапласа.
3.7.3. (Выбор проекта электростанции). Энергетическая компания должна
выбрать проект электростанции. Всего имеется 4 типа электростанций: тепловые, приплотинные, бесшлюзовые и шлюзовые. Возможности их эксплуатации
зависят от ряда неопределённых факторов, связанных с погодой, возможностями наводнения, ценами на топливо и т.д. В целом выделено 4 состояния среды.
Экономическая эффективность электростанции, определяемая как процент
прироста дохода в течение одного года эксплуатации по сравнению с затратами
в зависимости от состояний среды представлена в таблице
Типы
Электростанций
Тепловая
Приплотинная
Бесшлюзовая
Шлюзовая
Состояния среды
1
2
3
4
7
5
1
10
5
2
8
4
1
3
4
12
8
5
1
10
Оценить стратегии энергетической компании в соответствии с критериями Вальда, Лапласа и Сэвиджа.
3.7.4. На время предстоящей лыжной гонки синоптики предсказали 2 состояния погоды С1 и С2. Есть два вида мазей М1 и М2, пригодных для одного и
другого состояния погоды, вероятности удачного прохождения трассы в случае
использования их при С1 равны: 0,5 и 0,4, а при С2 – 0,3 и 0,8. Дать рекомендации лыжнику относительно выбора мази..
3.7.5. В таблице указаны доходы с 1га, полученные фермером при производстве зерновых, подсолнечника и корнеплодов в зависимости от уровней
осадков в летний период. Рассматривая данную ситуацию как игру фермера с
природой, найти его оптимальные стратегии по критериям Вальда, Гурвица
(полагая коэффициент пессимизма α= 0,5 и α=0,3), Сэвиджа, Лапласа, а также
Байеса, используя данные многолетних наблюдений, по которым влажный уровень наблюдается с вероятностью 0,25, а остальные с вероятностью 0,375.
60
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Доход с 1 га, руб.
Уровни влажности
Влажный
Средний
Сухой
Зерновые
6031,83
825,33
2,72
Подсолнечник
740,22
718,04
-81,22
Корнеплоды
1082,46
308,43
-259,77
3.7.6. Фирма может выставить на продажу 2 вида товаров, спрос на которые зависит от сочетания различных факторов (температура воздуха, дождливая погода, цены на другие товары и т.д.). Всего выделено 3 таких состояния.
Известно, что первое состояние наступает в 3 раза чаще, а второе – в 4 раза чаще, чем третье. Оценить по критерию Байеса стратегии фирмы (выбор варианта
продаваемого товара), если её доходы в зависимости от спроса в тыс. руб. заданы в таблице
Виды
Товара
1
2
Спрос
2
18
15
1
8
18
3
40
14
3.7.7. Затраты швейной фабрики в течение апреля – мая на единицу продукции составляют 8 ден. ед. на платье и 27 ден. ед. на костюм. Цена реализации соответственно равна 16 и 48 ден. ед. Маркетинговые исследования показали, что в течение этих месяцев фабрика может реализовать в условиях тёплой
погоды 600 костюмов и 1975 платьев, а при прохладной погоде – 625 платьев
и 1000 костюмов. Составить план производства платьев и костюмов с целью
максимизации средне ожидаемой величины прибыли.
3.7.8. Швейная фабрика выпускает детские брюки и костюмы, себестоимость которых составляет соответственно 10 и 25 ден. ед. Реализация будет
происходить в мае по 20 ден. ед. за брюки и по 45 ден. ед. за костюм. Специалисты по изучению спроса сделали прогноз, что в случае прохладной погоды
можно продать 500 брюк и 1200 костюмов, в случае тёплой – 600 костюмов и
2000 брюк. Обычно товар, не реализованный в течение месяца, долго лежит на
складах и не приносит дохода. Составить план производства с целью максимизации средне ожидаемого дохода.
3.7.9. Предприниматель продаёт зонтики и тёмные очки на стадионе. Его
доход во многом зависит от погоды. По опыту он знает, что может продавать
около 500 зонтов во время дождя и 100 зонтов в хорошую погоду. В последнем
случае он может также рассчитывать на продажу 1000 тёмных очков. Зонты он
покупает по 50 рублей, а продаёт по 100 рублей. Очки стоят ему 20 рублей, а
продаёт их по 50 рублей. Всё, что не продано, является чистым убытком.
61
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сколько предпринимателю выгоднее всего купить зонтов и очков?
3.7.10. Генеральный директор компании «Российский сыр», поставляющей сырную пасту в страны ближнего зарубежья, должен решить, сколько
ящиков этого продукта следует производить в течение месяца. Вероятности того, что спрос на сырную пасту за этот период будет 6, 7, 8, или 9 ящиков соответственно равны 0,1; 0,3; 0,5; 0,1. Затраты на производство одного ящика равны 45 у.е. Компания продаёт каждый ящик по 95 у.е. Сколько ящиков сырной
пасты следует производить, чтобы получить максимальную средне ожидаемую
прибыль, учитывая, что продукт не реализованный в течение месяца портится,
и компания не получает при этом дохода?
3.7.11. Спрос на некоторый товар, производимый монополистом, определяется зависимостью Q=100 – 5р + 5j, где р – цена товара, а j – достоверно неизвестный уровень дохода потребителей, который может быть равен двум денежным единицам с вероятностью 0,6 и четырём – с вероятность 0,4. Полные
затраты на производство товара определяются зависимостью 5 + 4Q+ Q2.
Сколько товара должен выпускать монополист и по какой цене его продавать,
чтобы максимизировать свою средне ожидаемую прибыль?
3.7.12. Директор магазина «Молоко» должен решить, сколько бидонов
сметаны следует закупить у производителя для торговли в течение недели, если
известно, что спрос на неё за этот период будет 7, 8, 9, или 10 бидонов, а также,
что 9 и 7 бидонов реализуются в 2 раза, а 8 – в 5 раз чаще, чем 10 бидонов. Покупка 1 бидона сметаны обходится магазину в 1000 рублей, а продаётся по цене
1600 рублей за бидон. Если сметана не продаётся в течение недели, она портится, и магазин несёт убытки. Сколько бидонов сметаны следует приобрести
для продажи?
3.8. Биматричные игры
Конечная бескоалиционная игра двух игроков называется биматричной
игрой. Она может быть задана системой <S1, S2, H1, H2>, где S1 и S2 - множества
стратегий игроков, H1 и H2 – функции их выигрышей, а также парой матриц
размерности m × n А=(аij) и В=(bij), где аij=Н1(i,j), bij= Н2(i,j), m и n- соответственно число стратегий игроков 1 и 2 или одной матрицей, элементы которой
представляют собой пары (аij, bij), при этом их компоненты имеют уже описанный смысл.
Для биматричной игры ситуация (i 0 , j 0 ) называется ситуацией равновесия
по Нэшу, если ни одному из игроков не является выгодным одностороннее отклонение от неё, то есть для любых стратегий игроков i и j aij ≤ ai j ; bi j ≤ bi j .
0
0 0
0
0 0
Пример 3.8.1. (Производство конкурирующей продукции). Два небольших предприятия общественного питания производят однотипную продукцию
и затем продают её на одном рынке. Каждое предприятие может использовать
большую или малую поточную линию. Если оба используют большую линию,
то получается перепроизводство продукции, и в результате оба предприятия
несут убытки в 9 тыс. рублей. Если одно использует большую линию, а другое
62
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
малую, то первое получает прибыль в 5 тыс. рублей, а второе только покрывает
убытки. Наконец, если оба предприятия используют малую линию, то оба получают одинаковую прибыль в 1тыс. рублей. Требуется составить модель биматричной игры и найти, если они есть, ситуации равновесия по Нэшу.
Решение. Этот конфликт моделируется биматричной игрой, в которой в
качестве игроков выступают предприятия 1 и 2, множества стратегий которых
S1=S2={1,2}, где 1 – использовать малую поточную линию, а 2 – большую. Тогда по условию Н1(1,1)=1; Н1(1,2)=0; Н1(2,1)=5; Н1(2,2)=-9; Н2(1,1)=1; Н2(1,2)=5;
Н2(2,1)=0; Н2(2,2)=-9. Эта игра может быть задана парой матриц
1 0 
 ;
5 − 9
А= 
1 5 

0 − 9
В= 
или одной матрицей
(0,5) 
 (1,1)


 (5,0) ( −9,−9) 
Непосредственной проверкой убеждаемся, что ситуациями равновесия по
Нэшу являются (1,2) и (2,1) с выигрышами соответственно (0, 5) и (5,0), так как
ни одному из игроков не является выгодным одностороннее отклонение, а для
остальных ситуаций это не так.
Если в биматричной игре отсутствует ситуация равновесия по Нэшу, то
строят смешанное расширение аналогично тому как это было сделано для матричных игр, в котором уже всегда такая ситуация существует. Для биматричных игр формата 2 × 2 она может быть найдена по тем же формулам, что и для
матричных игр, но компоненты смешанной стратегии игрока 1 находятся по
матрице выигрышей игрока 2, а для игрока 2 по матрице выигрышей игрока 1,
при этом выигрыши игроков в ситуации равновесия (Х*, У*) соответственно
равны v1=X*AУ*Т, v2=X*ВУ*Т Таким образом, в биматричных играх наблюдается «антагонизм поведения» игроков при отсутствии прямого «антагонизма
интересов».
Пример 3.8.2. Найти ситуацию равновесия в смешанных стратегиях для
биматричной игры, заданной матрицами
 − 20 4 

− 2 
 2
А= 
и
 10 − 4 
 .
− 2 2 
В= 
Решение. Непосредственной проверкой убеждаемся, что в данной игре
отсутствует ситуация равновесия в чистых стратегиях. Ситуацию равновесия в
2 7
3 11
смешанных стратегиях образуют стратегии: Х*=  ,  , У*=  ,  , так как
9 9
 14 14 
2 − ( −2)
2
3
−2−4
и q*=
. При этом средне ожидаемый вы=
=
10 + 2 + 2 + 4 9
− 20 − 2 − 2 − 4 14
3
 2 7   − 20 4   14 
Т
·
≈-1,14, а игрока 2
игрыш игрока 1 равен v1=Х*АУ* =  ,  · 
− 2  11 
9 9  2
 14 
р*=
63
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2 7  10 − 4   3 14 
 ·
v2=X*BУ*Т=  ,  · 
≈0,33.
 9 9   − 2 2  11 

14 
Вопросы для самоконтроля
Какая игра называется биматричной?
Как можно задать биматричную игру?
Что называется ситуацией равновесия по Нэшу?
Что общего между седловой точкой для матричных игр и ситуацией
равновесия по Нэшу для биматричных?
5. Как строится смешанное расширение биматричной игры?
6. Всегда ли существует ситуация равновесия в смешанном расширении?
7. Запишите формулы для нахождения ситуации равновесия в смешанном расширении.
1.
2.
3.
4.
Задачи и упражнения для самостоятельного решения
3.8.1.(Вывоз продукции). Предприятие для отправки своей продукции потребителю вывозит её на перевалочный пункт, где она грузится в машины, принадлежащие транспортному управлению. Если не вся продукция может быть
погружена, то её остаток сдаётся на склад; в этом случае расходы на хранение
продукции предприятие и транспортное управление несут поровну. Предприятие может отправить продукции в расчёте на 5 или 10 автомашин. Транспортное управление может направить на перевозку продукции обычную автоколонну (4 автомашины) или большую автоколонну (7 автомашин), две обычные автоколонны (8) или обычную и большую (11). От отправки одной машины продукции предприятие имеет доход а рублей, стоимость хранения на складе продукции, перевозимой одной автомашиной равна b рублей, а затраты транспортного управления на посылку к перевалочному пункту одной автомашины с
рублей. Составить модель биматричной игры. Найти матрицы выигрышей игроков при a=10; b=4; c=2.
3.8.2. Для игры примера 2.1 (спор партнёров) составить матрицы выигрышей игроков и найти ситуации равновесия по Нэшу.
3.8.3. (Конкурс на реализацию проекта). Две фирмы участвуют в конкурсе
на реализацию разработки некоторого проекта, причём доход от реализации
проекта составляет 10 денежных единиц. Каждая фирма может либо подать
простую заявку на участие в конкурсе (затраты равны 1 денежной единице) либо представить программу реализации проекта (затраты равны 3 денежным
единицам). Условия конкурса таковы, что в случае, когда обе фирмы выбирают
одинаковый способ действия, заказ на реализацию проекта, а также доход делится между ними пополам. Если же фирмы выбирают различные способы действий, то предпочтение отдаётся той, которая представила подробную программу. Построить модель игры и найти ситуации равновесия по Нэшу.
64
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3.8.4. (Распределение прибыли). Фирма А может выпускать изделия А1 и
А2, а фирма В – В1 и В2, которые затем продаются на одном рынке. Прибыль
этих фирм в зависимости от того являются ли эти изделия взаимно дополнительными или конкурирующими определяется таблицей:
В1
В2
А1
(1, 6)
(5,1)
А2
(3,2)
(2,3)
Найти ситуации равновесия в смешанных стратегиях. Дайте истолкование полученного решения.
3.8.5. Два предприятия по обслуживанию населения предлагают жителям
посёлка, имеющего 1000 потенциальных клиентов, 4 вида услуг. Если первое
предприятие предлагает i-ю услугу, а второе j- ю, то доля клиентов, пользующихся услугой i равна рij, а остальные клиенты выбирают услугу j. Выигрышем
предприятия считается число его клиентов. Составьте модель биматричной игры, если матрица (pij) имеет вид:
 0,6

 0,4
 0,1

 0,4

0,5
0,5
0,6
0,6
0,6
0,5
0,2
0,4
0,5 

0,6 
.
0,7 

0,6 
Покажите, что полученная биматричная игра эквивалентна некоторой
матричной игре и найдите её решение в смешенных стратегиях, используя
принцип доминирования.
Убедившись, что следующие биматричные игры не имеют ситуаций равновесия в чистых стратегиях, найдите их решение в смешанных стратегиях.
 ( −8,4) (3,−3) 
 ;
 (2,−2) ( −2,2) 
 ( −9,5) ( 4,−4) 
 .
 (3,−3) ( −3,3) 
3.8.6. 
3.8.7. 
3.8.8. Инвестор желает построить один из двух объектов на территории
города. Городская администрация может принять его предложение или отказать. Строительство первого объекта требует больших затрат инвестора, и часть
площадей оно должно передать городу. При строительстве второго объекта
возможно использование имеющихся ресурсов города. Кроме того, производятся затраты на составление проекта строительства инвестором и его оценку городской администрацией. Требуется найти решение биматричной игры инвестора и городской администрации, если их прибыли задаются матрицей выигрышей в млн. руб.
 ( −10,5) (2,−2) 

 .
 (1,−1) ( −1,1) 
65
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3.9. Классические кооперативные игры
В кооперативных играх, в отличие от бескоалиционных, игроки могут обсуждать совместные действия с целью увеличения прибыли.
Всякое подмножество К множества игроков I= {1, 2,…,n} называется
коалицией.
Классической кооперативной игрой n лиц называется система <I, V>, где I
– множество игроков, V- характеристическая функция, определённая на множестве всех коалиций игроков, принимающая значения в множестве действительных чисел и удовлетворяющая следующим условиям:
1. V(Ø)=0;
2. V(K1U K2)≥V(K1)+V(K2), если К1 ∩К2 =Ø.
Исходом кооперативной игры является делёж, который представляет собой вектор х=(х1, х2,…, хn), компоненты которого хi ∈ R и удовлетворяют следующим условиям, которые называются соответственно условиями индивидуальной и коллективной рациональности:
1. хi ≥ V(i) для всех i ∈ I;
n
2.
x i = V(I).
∑
i
=1
Делёж х называется доминирующим делёж у, если для некоторой коалиции К выполняются условия:
1. хi> yi для всех i ∈ К;
2. ∑ x i ≤ V(K).
i ∈K
Делёж, не имеющий доминирующих дележей, называется максимальным.
Множество всех максимальных дележей называется ядром кооперативной игры.
Если ядро кооперативной игры непустое, то все его дележи обладают устойчивостью в том смысле, что игрокам невыгодно их изменять, и поэтому их
можно считать решениями игры.
Ядро находят из системы неравенств V(K)≤ ∑ x i для коалиций К ⊂ I,
i ∈K
предварительно преобразовав характеристическую функцию так, чтобы V(i)=0
(для всех i ∈ I) и V(I)=1.
Пример 3.9.1. (Рынок трёх лиц). Продавец хотел бы продать лошадь не
менее, чем за 0,5 тыс. условных единиц (у.е.), а каждый из двух покупателей
хотел бы её приобрести соответственно не более, чем за 0,8 тыс. у.е. и 1,5 тыс.
у.е. Считая прибылью каждого из участников сделки сэкономленные деньги,
построить модель кооперативной игры и найти её ядро.
Решение. Здесь множество игроков I= {1, 2, 3}, где игрок 1 – продавец,
игроки 2 и 3 - покупатели. Рассмотрим всевозможные коалиции игроков: К0=
Ø, К1= {1}, К2= {2}, К3= {3}, К4= {1, 2}, К5= {1,3}, К6={2, 3}, К7={1, 2, 3}.
Так как сделка может произойти как результат соглашения продавца с
покупателем, то V(К0)= V(К1)= V(К2)= V(К3)= V(К6)= 0. Вычислим V(К4). В
случае, если сделка состоялась между продавцом и первым покупателем, то
66
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
лошадь должна быть продана по цене х тыс. у.е., где 0,5≤х≤0,8. При этом пок упатель получит прибыль (0,8-х) тыс. руб., а продавец (х-0,5) тыс. у.е., и прибыль коалиции V(К4)=(0,8-х)+(х-0,5)=0,3 тыс. у.е. Аналогично, V(К6)=(1,5х)+(х-0,5)=1. V(К7) =1, так как это максимально возможная прибыль игроков.
Ядро игры будем искать из системы линейных соотношений:
1=х1+ х2+ х3 ,
(3.9.1)
0,3≤ х1+ х2 ,
(3.9.2)
1 ≤ х1
(3.9.3)
+ х3,
х1 ≥0, х2 ≥0, х3 ≥0.
(3.9.4)
Из условий (3.9.1), (3.9.3) и (3.9.4) заключаем, что х2=0, и дележи ядра
имеют вид: (х1, 0, 1- х1), где 0,3≤ х 1≤1. Такой делёж означает, что лошадь достаётся третьему игроку за цену р= х1+0,5, при этом р≥0,8, то есть третий игрок
платит первому не меньше, чем мог бы заплатить второй.
В кооперативных играх могут быть приняты различные критерии оптимальности. Наиболее известный из них принцип справедливого дележа, который состоит в нахождении так называемого вектора Шепли, который является
дележом, предписывающим получать доходы только игрокам действительно
участвующим в игре, при этом игроки, внесшие одинаковый вклад должны получить одинаковый доход, а выигрыши игроков, участвующих в нескольких
играх должны складываться. Вектор Шепли существует для любой кооперативной игры и его компоненты могут быть найдены по формуле:
Фi(V)=
∑
K Ii K
⊂ .∈
(| K | −1)! (n − | K |)!
[V (K ) − V (K \ i )] ,
n!
где i = 1, 2,…n.
Пример 3.9.2. Для игры рынок трёх лиц найти вектор Шепли.
Решение. Так как при |K|≤1, V(K)=0, то начнём подсчёт с коалиций, содержащих два элемента.
(2 − 1)! (3 − 2)!
(3 − 1)! (3 − 3)!
[V(K4)-V(K2)+V(K5)-V(K3)]+
[ V(K7)3!
3!
(0,3 + 1) 1 11
V(K6)]=
.
+ =
6
3 20
Ф1(V) =
(2 − 1)! (3 − 2)!
(3 − 1)! (3 − 3)!
[V(K4)-V(K1)+V(K6)-V(K3)]+
[ V(K7)3!
3!
0,3 0
1
.
V(K5)]=
+ =
6 3 20
Ф2(V) =
(2 − 1)! (3 − 2)!
(3 − 1)! (3 − 3)!
[V(K5)-V(K1)+V(K6)-V(K2)]+
[ V(K7)3!
3!
1 (1 − 0,3) 2
V(K4)]= +
= .
6
3
5
Ф3(V) =
67
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Вопросы для самоконтроля
1. Чем принципиально кооперативные игры отличаются от бескоалиционных?
2. Что понимается под коалицией?
3. Сколько всевозможных коалиций могут образовать n игроков?
4. Что называется классической кооперативной игрой?
5. Какое минимальное число игроков может участвовать в кооперативной игре?
6. Что такое делёж?
7. Когда один делёж доминирует другой делёж?
8. Что называется максимальным дележом?
9. Что называется ядром кооперативной игры?
10.Как найти ядро кооперативной игры?
11.Что понимается под вектором Шепли?
12.Как найти вектор Шепли?
Задачи и упражнения для самостоятельного решения
3.9.1. Группа из трёх неквалифицированных работников выполняет некоторую однородную работу, причём каждый из работников может выполнить
одинаковый объём работы и заработать а рублей. Построить характеристическую функцию.
3.9.2. Каждый из четырёх работников имеет некоторый индивидуальный
навык, которым владеет только он один и который позволяет увеличить на некоторую сумму b заработок а каждого, кто с ним работает в коалиции. Построить характеристическую функцию.
3.9.3. Определить, являются ли векторы
дележами для игры рынок трёх лиц (пример 10.1)?
а) (0,1; 0,4; 0,5); b) (0,2; 0,4; 0,6); с) (-0,1; 0,5; 0,6)
3.9.4. Для игры рынок трёх лиц (пример 10.1) определить, доминирует ли
делёж ( 0,2; 0,3; 0,5) делёж ( 0,1; 0; 0,9).
3.9.5. (Распределение прибыли). Имеется три предприятия, специализирующиеся на выпуске комплектующих деталей А и В одинаковой стоимости,
причём изделие собирается из одной детали А и одной детали В. Возможности
предприятий по выпуску деталей указаны в таблице:
Предприятие
А
В
1
900
0
2
600
0
3
0
1000
68
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Так как ни одно из предприятий не в состоянии самостоятельно производить данное изделие, то они заключают между собой договор с последующим
распределением прибыли. Составить модель кооперативной игры и найти её
ядро, считая прибылью коалиции стоимость произведённых изделий, если
стоимость одного изделия равна с (с= 0,001) денежных единиц.
3.9.6. (Фермер и сезонные рабочие). Фермер может привлечь для уборки
урожая трёх сезонных рабочих. При участии k (0≤k≤3) рабочих будет получен
доход в k+2 денежные единицы. Требуется найти справедливую долю фермера
и сезонных рабочих в общем доходе.
3.9.7. (Однопродуктовый сбалансированный рынок). На рынке присутствуют 2 продавца и 2 покупателя, причем продавцы имеют соответственно 1 и 3
единицы одинакового товара, а каждый покупатель желает приобрести по 2
единицы этого товара, то есть спрос равен предложению. Составить модель
кооперативной игры четырёх игроков, считая выигрышем каждой коалиции
объём сделок, которые могут быть заключены между продавцами и покупателями – членами этой коалиции. Найти справедливую долю каждого игрока в
этой игре.
3.9.8. Построить характеристическую функцию и найти вектор Шепли
для игры задачи 10.7 при условии, что имеется 2 продавца и 3 покупателя, причём продавцы продают соответственно 2 и 4 единицы товара, а покупатели
предъявляют спрос соответственно в объёмах 1, 2 и 3 единиц товара.
3.9.9. Найдите вектор Шепли для характеристической функции упражнения 10.1 и 10.2.
3.9.10. (Оценка «силы» держателей акций). Акции некоторой компании
распределены между четырьмя акционерами, причём 1-ый акционер обладает
10% всех акций, 2-ой – 20%, 3-ий – 30% и 4-ый – 40%. На общем собрании акционеров решение принимается по правилу простого большинства (одна акция
равна одному голосу). Найти вектор Шепли для этой кооперативной игры, который позволит оценить «силу» акционеров при данной схеме голосования.
3.9.11. Оценить «силу» держателей акций, если в условиях задачи 10.10
решение принимается в случае, когда за него подано не менее, чем 2/3 голосов.
3.9.12. Организация состоит из председателя и трёх рядовых членов. По
уставу организации решение принимается, если «за» голосуют председатель и
ещё хотя бы один рядовой член, либо «за» голосуют все рядовые члены. Найти
вектор Шепли для данной кооперативной игры.
3.10 . Расчётно-графическая работа по теории игр
Задания для расчётно-графической работы
Задание №1
Фирма может выставить на рынок т видов товара. Рынок может находиться в п состояниях, в зависимости от которых доходы фирмы в денежных
69
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
единицах представлены матрицей размерности m × n .
Требуется составить модель матричной игры и найти
а) нижнюю цену игры и все максиминные стратегии игрока 1;
б) верхнюю цену игры и все минимаксные стратегии игрок 2;
в) цену игры и седловые точки, если они существуют;
г) рассматривая её как игру с природой, найти оптимальные стратегии игрока 1 по критериям Вальда, Гурвица (полагая коэффициент пессимизма
α= 0,2 и α=0,5), Сэвиджа и Лапласа.
2 −3
1
1
0 −3
2
1 −2
−1
2
1
 1

−2
1. 
4

 3

3.
3
 1 −2

1
0
− 2
− 2
1 −3

 2

6
5. 
2

− 3

7.
1
2
−1
1
5
7
3


2. 



4

3
0 
−1 − 3
4
3
3 −2
4
2
3
 1 −2

5
 2 −3
− 2
1 −3

 3
2 −1

 3 −1

9.  2 − 3
 2 −1

4

5
0

0 
4
1
5
0
3

4
1

0 
1

− 1
2

1
−1
2
3 −2
7 −4
3
5
4 − 7

3
0
1 − 2

2
1
3
5
2
−1
1 −1 −1
2 5 2


4. 



3 0
3 −1
3
4


6. 



−1 − 2
2
3
4 −5
−1
4
3
−1
3
2
2
4


8. 



1
2
0
2
0
1
4
1

2
2
1 − 4

1
3 
−1
1
0
1
3
3
4
4
 −1 −1

10.  4 − 5
 2 −1

4

3
2 
4

3
2

2 
2 − 5

4
5
2 − 1

3
5 
2 − 3

3
7 .
3
4 
Задание №2
Требуется найти решение матричных игр а) графо-аналитическим методом б) методами линейного программирования:
2 4 0

 1 0 4
11. 
 1 2 4

 4 2 1
 2 3 1 5

 4 1 6 0
12. 
13. 
70
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
 2 4


14.  4 0 
0 8


15. 
 8 1


17.  5 3 
 4 6


10

6
18. 
3

 2

 4 3 1

 2 5 7
1

2
4

6 
1 2 5

7 5 4
16. 
 1 8


19.  4 4 
5 0


0 3 4 7
 .
9 6 3 2
20. 
Выбор заданий осуществляется в соответствии с таблицей:
Вариант № Задание№1 Задание 2
1
1
11
2
2
12
3
3
13
4
4
14
5
5
15
6
6
16
7
7
17
8
8
18
9
9
19
10
10
20
Пример 3.10.1. (Задание 1). Фирма может выставить на рынок три вида
товара. В зависимости от состояния рынка её доходы в денежных единицах
представлены в таблице:
Виды
Состояния рынка
товаров
1
2
3
4
1
1
0
-2
2
2
2
1
3
1
3
-3
-2
4
-2
Требуется составить модель матричной игры и найти
а) нижнюю цену игры и все максиминные стратегии игрока 1;
б) верхнюю цену игры и все минимаксные стратегии игрок2;
в) цену игры и седловые точки, если они существуют;
г) рассматривая её как игру с природой, найти оптимальные стратегии игрока 1 по критериям Вальда, Гурвица, полагая коэффициент пессимизма
α= 0,2 и α=0,5, Сэвиджа и Лапласа.
Решение. Составим модель матричной игры.
Множество игроков I={1, 2}, где 1 – фирма, 2 – рынок. Множество стратегий (возможных действий) игрока 1 обозначим S1 = {1,2,3} , элементы
71
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
которого есть виды товаров. Для игрока 2 его множество стратегий
S 2 = {1,2,3,4} , элементы которого представляют собой состояния рынка, а
матрица игры, элементы которой равны доходам в денежных единицах игрока 1
в во всевозможных ситуациях (определяются парой стратегий выбранных игро-
 1

ками), равна А= 2
− 3

0
1
−2
−2 2 

3 1  . Если предположить, что среда ведёт
4 − 2 
себя наихудшим образом по отношению к принимающему решение, то игру
можно рассматривать как матричную.
а). Для нахождения нижней цены игры и максиминных стратегий игрока
1 в каждой строке платёжной матрицы выбираем минимальный элемент (наименьший возможный выигрыш игрока 1 при применении соответствующей
стратегии) и выписываем его в отдельный столбец. Затем выбираем в построенном столбце максимальный элемент или элементы, если их окажется несколько, и отметим их звёздочкой. Он (они) и будут равны нижней цене игры,
а номера строк, в которых расположены эти элементы будут соответствовать
максиминным стратегиям игрока 1. В нашем случае имеем:
minaij
j
0 −2
2 −2
 1
 *

2
1
3
1
 1

− 3 − 2
4 − 2  − 3

Таким образом, нижняя цена игры v =1, а максиминная стратегия игрока
1: i* = 2 .
б). Для нахождения верхней цены игры и минимаксных стратегий игрока
2 находим в каждом столбце платёжной матрицы максимальный элемент (наибольший возможный проигрыш игрока 2 при применении соответствующей
стратегии) и выписываем его в отдельную строку, а затем выбираем в построенной строке минимальный элемент или элементы, если их окажется несколько,
и также отметим их звёздочкой. Он (они) и будут равны верхней цене игры, а
номера столбцов, в которых расположены эти элементы будут соответствовать
минимаксным стратегиям игрока 2.
0 −2
2
 1


2
1
3
1


− 3 − 2
4 − 2 

maxaij 2
1* 4
2
i
Таким образом, верхняя цена игры v =1. Минимаксная стратегия игрока
2: j* = 2 .
72
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
в). Седловая точка- это ситуация выигрыш первого игрока в которой есть
элемент, являющийся одновременно самым маленьким в своей строке и самым
большим в своём столбце. Такая ситуация существует, если
v = v = v и образуется любой парой соответственно максиминной и минимаксной стратегий,
при этом v называют ценой игры, а седловую точку её решением, так как ни одному из игроков невыгодно отклониться от неё в одностороннем порядке.
В нашем случае v=1. Седловая точка (2, 2).
г). Поскольку игрок 2 – рынок (стихийная сила), то игру можно рассматривать как игру с природой.
Оценим стратегии игрока 1, используя Критерий Вальда, основаный на
гипотезе крайнего пессимизма игрока по отношению к поведению среды, а
именно: предполагается, что среда ведёт себя наихудшим образом по отношению к принимающему решение.
Оптимальной по данному критерию стратегией является максиминная
стратегия. В нашем случае это стратегия 2.
Виды
товаров
1
2
3
Состояния рынка minaij
maxaij
j
1
1
2
-3
2
0
1
-2
3
-2
3
4
4
2
1
-2
-2
1*
-3
Критерий Гурвица
Критерий
Лапласа
j
α =0,2
1,2
2,6*
2,6*
2
3
4
α =0,5
0
2*
0,5
0,25
1,75*
-0,75
Критерий Гурвица. Оптимальной по этому критерию считается та стратегия, для которой величина αm i naij + (1 − α )m a xaij является наибольшей.
j
j
Оценим стратегии игрока при α=0,2 и 1- α=0,8:
Для стратегии 1: 0,2 ⋅ (−2) + 0,8 ⋅ 2 = 1,2
Для стратегии 2: 0,2 ⋅ 1 + 0,8 ⋅ 3 = 2,6
Для стратегии 3: 0,2 ⋅ (−3) + 0,8 ⋅ 4 = 2,6 .
Оптимальные стратегии: 2 и 3.
Аналогично, оценим стратегии игрока при α=0,5и 1- α=0,5:
Для стратегии 1: 0,5 ⋅ (−2) + 0,5 ⋅ 2 = 0 .
Для стратегии 2: 0,5 ⋅ 1 + 0,5 ⋅ 3 = 2 .
Для стратегии 3: 0,5 ⋅ (−3) + 0,5 ⋅ 4 = 0,5 .
Оптимальная стратегия: 2.
Критерий Лапласа. Оптимальной по этому критерию является та стратегия, для которой среднее арифметическое возможных выигрышей будет наибольшим.
Для стратегии 1: (1 + 0 − 2 + 2) : 4 = 0,25 .
Для стратегии 2: (2 + 1 + 3 + 1) : 4 = 1,75 .
Для стратегии 3: (−3 − 2 + 4 − 2) : 4 = −0,75 .
Оптимальная стратегия: 2.
73
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Критерий Сэвиджа основан на преобразовании матрицы выигрышей (aij )
в матрицу рисков (rij ) , где rij = m a xaij − aij .
i
Оптимальной по данному критерию считается стратегия, минимизирующая максимальный риск.
Составим матрицу рисков и найдем минимаксную стратегию игрока 1:
Виды
товаров
Состояния рынка
1
2
Критерий
3
4
Сэвиджа
maxrij
j
1
2
3
1
0
5
1
0
3
6
1
0
0
1
4
6
1*
5
Оптимальная стратегия: 2.
Ответ: а) v =1; максиминная стратегия: 2; б) v =1; минимаксная стратегия: 2; в) цена игры 1; седловая точка (2,2); г) оптимальная по критерию Вальда
стратегия 2, выигрыш 1; оптимальные стратегии по критерию Гурвица (α= 0,2)
2 и 3, выигрыш 2,6; (α=0,5) стратегия 2 выигрыш 2; оптимальная по критерию
Лапласа стратегия 2, выигрыш 1,75; оптимальная по критерию Сэвиджа стратегия 2, наибольший риск 1.
Образец решения задания 2 дан в примерах 3.6.1, 3.6.2 и 3.6.3.
4. МОДЕЛИ ПОТРЕБИТЕЛЬСКОГО СПРОСА
4.1. Функции нескольких переменных и их дифференцирование
Примерами функций нескольких переменных, используемых в экономике, являются производственные функции, описывающие зависимость производственного результата от используемых в данном процессе ресурсов, а также
функции полезности, устанавливающие потребительскую оценку данного набора товаров.
Производственная функция K ( x, y ) = Axα y β , устанавливающая зависимость стоимости созданного продукта, от затрат труда - х и затрат капитала - у ,
где α и β – коэффициенты, называется функцией Кобба-Дугласа.
Предельная производительность труда, показывающая, сколько дополнительных единиц продукции приносит дополнительная единица затраченного
труда, – это частная производная от К(х,у) по х. Предельная фондоотдача – это
частная производная выпуска продукции по объёму фондов.
74
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Правило нахождения частных производных
Чтобы найти частную производную (первого порядка) функции нескольких переменных следует найти обыкновенную производную функции одной
переменной, считая, что все остальные переменные являются постоянными.
Частные производные от частной производной первого порядка функции
нескольких переменных называются частными производными второго порядка.
Пример 4.1.1. Найти частные производные функции первого и второго
порядка для функции z = x y в точке М(1;2).
Решение. Используем следующие правила дифференцирования: (c )′ = 0 ;
(cu )′ = cu ′ , (u ± v)′ = u ′ + v′ , (uv)′ = u ′v + uv′ , где c = const . И табличные произ1
водные ( x n )′ = nx n −1 , (a x )′ = a x ln a , (ln x) = .
x
Частные производные первого порядка:
∂z
∂z
= x y ln x .
= yx y −1 ;
∂y
∂x
Частные производные первого порядка в точке М(1;2):
 ∂z 
 ∂z 
2 −1
= 2 .   = 12 ln1 = 0 .
  = 2 ⋅1
 ∂x  M
 ∂y  M
Частные производные второго порядка:
2
y −1 ′
y −2 ∂ z
;
= ( yx y −1 )′y = x y −1 + yx y −1 ln x .
= ( yx
) x = y ( y − 1) x
∂x∂y
∂x 2
∂2z
∂2z
1
= ( x y ln x)′x = yx y −1 ln x + x y = . ( yx y −1 )′y = x y −1 + yx y −1 ln x .
x
∂y∂x
Заметим, что смешанные частные производные второго порядка в случае
∂2z
∂2z
их непрерывности равны, то есть:
.
=
∂x∂y ∂y∂x
∂2z
2
= ( x y ln x)′y = x y ln 2 x .
∂y
Частные производные второго порядка в точке М(1;2):
 ∂2z 
 2 
 2 

 = 2 ⋅ 1 ⋅ 12 − 2 = 2 ;  ∂ z  = 12 −1 + 2 ⋅ 12 −1 ln1 = 1 ;  ∂ z  = 12 ln 2 1 = 0 .
 ∂x 2 
 ∂x∂y 
 ∂y 2 

M

M

M
75
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Вопросы для самоконтроля
1. Что такое производственная функция?
2. Какой вид имеет функция Кобба-Дугласа?
3. Что такое функция полезности?
4. Сформулируйте правило нахождения частных производных функции
нескольких переменных.
5. Что называют частной производной второго порядка для функции нескольких переменных?
6. Когда смешанные частные производные равны?
Задачи для самостоятельного решения
Найдите частные производные функции:
4.1.1. z = 2 x 2 − xy + 3 y 3 .
4.1.2. z = 3 x 2 y − 3 xy 2 − 4 y + 2 x + 12 .
2
2
4.1.3. z = 5 x 3 y 2 − 3 x 2 y 2 − 4 xy + x − 7 y + 9 4.1.4. z = e x + y .
x+ y
y
4.1.5. z =
.
4.1.6. z = .
x− y
x
4.1.8. z = x 2 + y 2 .
y
4.1.10. z = xyarctg .
x
x+ y+ z
4.1.12. u = xyze
4.1.7. z = ln(2 x + 3 y ) .
4.1.9. z = 2 xy .
4.1.11. u = e xyz
Найдите частные производные второго порядка от функций:
4.1.13. z = x 3 y 2 − 2 x 2 y 3 − 3 xy + 4 x 2 − 5 y 3 + 6 .
4.1.14. z = 3 x 3 − 5 x 2 y − 7 xy + 4 x 2 − 2 y + 11 .
4.1.15. z = 3 y 5 − x 2 y 2 − 6 xy + 3 x 2 − y + 13 .
4.1.16. z = xy sin( 2 x + 3 y ) .
4.1.17. z = (2 x + y 2 ) cos( xy )
Найдите значение частных производных второго порядка в точке М(2;1)
от функций:
4.1.18. z = 2 x 3 − x 2 y − xy + 3 x 2 − y + 1 .
4.1.19. z = 3 x 2 − y 2 − 2 xy + x − 2 y + 3 .
4.1.20. Найдите предельную производительность труда , если производственный процесс описывается функцией Кобба –Дугласа K ( x, y ) = 0,001x 0,4 y 0,6 ,
если х=20 тыс. руб., у=100тыс руб.
76
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
4.2. Экстремум функции двух переменных
Функция z = f ( x, y ) имеет максимум (минимум) в точке M ( x0 , y0 ) , если
f ( x0 , y0 ) есть наибольшее (наименьшее) её значение в некоторой окрестности
этой точки.
Максимумы и минимумы функции называются экстремумами, а точка
M ( x0 , y0 ) - точкой экстремума.
Точка M ( x0 , y0 ) называется стационарной точкой функции z = f ( x, y ) ,
 ∂z 
 ∂z 
если   =   = 0 .
 ∂x  M  ∂y  M
Если M ( x0 , y0 ) - стационарная точка функции z = f ( x, y ) , а
 ∂2z 
 2 
 2 

 = A ,  ∂ z  = B и  ∂ z  = C , и ∆ = AC − B 2 , то если
 ∂x 2 
 ∂y 2 
 ∂x∂y 

M

M

M
1) ∆ > 0 , то экстремум в точке M ( x0 , y0 ) есть, при этом при A > 0 ( C > 0 ),
функция имеет минимум, а при A < 0 ( C < 0 ) – максимум;
2) ∆ < 0 , то экстремума нет;
3) ∆ = 0 , то требуются дополнительные исследования.
Пример 4.2.1. Исследуйте на экстремум функцию
z = x 2 + xy + y 2 − 2 x − y .
Решение. Вычислим частные производные функции:
∂z
∂z
= x + 2 y − 1.
= 2x + y − 2 ;
∂y
∂x
2 x + y − 2 = 0,
Решив систему уравнений: 
находим стационарную точку
x
+
2
y
−
1
=
0

М(1;0).
Найдём частные производные функции второго порядка:
∂2z
2
= 2;
∂2z
= 1;
∂x∂y
∂2z
2
=1
∂y
∂x
 ∂2z 
 ∂2z 
 ∂2z 




 = 2 вычисТеперь для A =
=1 и C = 
= 2, B =
 ∂x∂y 
 ∂x 2 
 ∂y 2 

M

M

M
лим ∆ = AC − B 2 = 3.
Поскольку ∆ > 0 и A > 0 , то в точке М функция достигает минимума.
Подставляя в исходную функцию координаты точки М, получаем:
z min = −1 .
В экономике встречаются задачи на нахождение условного экстремума, в
которых требуется найти экстремум функции при некоторых ограничениях на
её переменные.
77
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
В этом случае вводят так называемый множитель Лагранжа λ и исслед уют функцию L( x, y, λ ) = f ( x, y ) + λg ( x, y ) , где z = f ( x, y ) - исходная функция, а
g ( x, y ) = 0 - ограничение на переменные, на обычный экстремум. При этом для
0
стационарной точки вычисляют ∆ = −
∂g
∂x
∂g
∂y
∂g
∂x
∂2L
∂x 2
∂2L
∂x∂y
∂g
∂y
∂2L
.
∂x∂y
∂2L
∂y 2
Если ∆ > 0 , то в этой точке - условный минимум, а при ∆ < 0 - условный
максимум.
Пример 4.2.2. Требуется исследовать на экстремум функцию
z = 6 − 4 x − 3 y при условии x 2 + y 2 = 1.
Решение. Составим функцию L( x, y, λ ) = 6 − 4 x − 3 y + λ ( x 2 + y 2 − 1) , где
g ( x, y ) = x 2 + y 2 − 1 - ограничение на переменные.
Частные производные имеют вид:
∂L
∂L
∂L
= −3 + 2λy ;
= −4 + 2λx ;
= x 2 + y 2 − 1.
∂y
∂x
∂λ
 − 4 + 2λx = 0,

Найдем координаты стационарных точек из условия:  − 3 + 2λy = 0,
 x 2 + y 2 − 1 = 0.

Выразив х и у через λ из первых двух уравнений и подставив их в послед
2
x= ,

λ

3
нее имеем:  y =
Откуда находим λ1 = 2,5 ; x1 = 0,8 ; y1 = 0,6 и
,
λ
2

 4 + 9 = 1.
 λ2 4λ2
λ2 = −2,5 ; x2 = −0,8 ; y2 = −0,6 .
Таким образом, при λ1 = 2,5 имеем стационарную точку M 1 (0,8;0,6) , а
при λ2 = −2,5 - M 2 (−0,8;−0,6) .
∂g
∂2L
∂2L
∂2L
∂g
= 2y ;
Найдем
= 0 и их значение
= 2λ ;
= 2λ ;
= 2x ;
∂y
∂x∂y
∂x
∂y 2
∂x 2
∂g
∂g
= 1,2 ;
при
λ1 = 2,5 и стационарной точке M 1 (0,8;0,6) :
= 1,6 ;
∂y
∂x
78
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
∂2L
∂x 2
=
∂2L
∂y 2
= 5;
∂2L
= 0.
∂x∂y
0 1,6 1,2
Имеем: ∆1 = − 1,6 5 0 =12.
1,2 0 5
Таким образом, ∆1 > 0 и в точке M 1 (0,8;0,6) функция имеет условный
минимум. Подставляя координаты точки М1: в исходную функцию, вычисляем:
z min = 1 .
Аналогично, при λ2 = −2,5 в стационарной точке M 2 (−0,8;−0,6) находим: ∆ 2 = −12 . То есть, ∆ 2 < 0 и в точке M 2 (−0,8;−0,6) функция имеет условный максимум. Подставляя координаты точки М2: в исходную функцию, вычисляем: z max = 11 .
Вопросы для самоконтроля
1. Что такое максимум и минимум функции двух переменных?
2. Что называется стационарной точкой?
3. Когда функция имеет экстремум в стационарной точке?
4. Что понимают под условным экстремумом функции двух переменных?
5. Как исследовать функцию двух переменных на условный экстремум?
Задачи для самостоятельного решения
Исследуйте следующие функции на экстремум:
4.2.1. z = ( x − 1) 2 + 2 y 2 .
4.2.2. z = x 3 + y 3 − 3 xy .
4.2.3. z = 2 x 2 − 3 y 2 + 2 xy − 10 x + 16 y − 7 .
4.2.4. z = −7 x 2 − 5 y 2 + 2 xy − 34 x + 34 y + 5 .
4.2.5. z = 5 x 2 − 3 y 2 + 2 xy − 18 x − 10 y + 4 .
4.2.6. z = 2 x 2 − 3 y 2 − 2 xy + 8 x + 10 y − 6 .
4.2.7. z = −3 x 2 + 5 y 2 − 8 xy + 4 x + 26 y + 3 .
4.2.8. z = x 4 + y 4 − 2 x 2 + 4 xy − 2 y 2 .
Исследуйте условный на экстремум функции:
4.2.9. z = 2 x + y при x 2 + y 2 = 5 .
4.2.10. z = x 2 + y 2 − xy + x + y − 4 при x + y + 3 = 0 .
4.2.11. z = xy при x + y = 1 .
79
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
x y
4.2.12. z = x 2 + y 2 при + = 1 .
2 3
4.2.13. z = x 2 − y 2 при 3 x + y − 3 = 0 .
4.2.14. Предприниматель решил выделить на расширение своего дела 150
тыс. руб. Известно, что если на приобретение нового оборудования затратить х
тыс. руб., а на зарплату вновь принятых работников у тыс. руб., то прирост объ-
ёма продукции составит Q = 0,001x 0,6 y 0,4 . Как следует распределить денежные
ресурсы, чтобы прирост объёма продукции был максимальным?
4.2.15. Общие издержки производства заданы функцией
z = 0,5 x 2 + 0,4 y 2 + 0,6 xy + 700 x + 600 y + 2000 , где х и у - соответственно
количество товаров А и В. Общее количество произведённой продукции должно быть равно 500 ед. Сколько единиц товара А и В нужно производить, чтобы
издержки на их изготовление были минимальными?
80
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
СПИСОК ЛИТЕРАТУРЫ
1. Бось, В.Ю., Иоанно, А.Д., Н.Б. Уейская Экономико-математические методы: учебное пособие / В.Ю. Бось, А.Д. Иоанно, Н.Б. Уейская. ФГОУ ВПО
«Саратовский ГАУ». - Саратов. 2009.- 188с.
2. Экономико-математические методы и модели: учебное пособие /Под
ред. С.И. Макарова. – М.: КНОРУС, 2009. – 240с.
3. Уейская, Н.Б. Теоретико-игровые модели в экономике: Учебное пособие для студентов экономического факультета / Н.Б. Уейская. Саратов: Сарат.
с.-х. акад. 1996, 96с.
4. Уейская Н.Б. Задачи и упражнения по теории игр для экономистов: учеб. пособие /Н.Б. Уейская. - Изд. ФГБОУ ВПО СГАУ. Саратов, 2012. 55 с.
5. Розен В.В. Модели принятия решений в экономике. Учебное пособие./
В.В. Розен М: Книжный дом «Университет», Высшая школа, 2002. 288с.
6. Кремер Н.Ш.. Высшая математика для экономических специальностей:
Учебник и практикум. 3-е издание /Н.Ш. Кремер. Москва, Юрайт, 2010.
7.Экономико-математическое моделирование: учебник / под общ. Ред.
И.Н. Дрогобыцкого. – 2-е изд., стереотип. – М.: Изд-во «Экзамен», 2006. –
798.
81
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Правила дифференцирования
Если u(x) и v(x) –дифференцируемые функции, с=const, то
1.
2.
3.
4.
(с)′= 0.
(сu)′=cu′.
(u±v)′= u′ ± v′.
(uv)′=u′v+uv′.
′
 u  u ′v − uv ′
5.   =
.
2
v
v
Таблица производных
1. (x)′=1.
2. (хр)′= рxр-1 (р∈R).
3.( x )′ =
1
2 x
.
′
1
1
4.   = −
.
2
 x
x
5. ( sinx)′ =cosx.
6. (cosx)′ = - sinx.
1
7. (tgx)′ =
.
cos 2 x
1
8. (ctgx)′ = −
.
2
sin x
9. (ex)′ = ex.
10. (ах)′=ахlna.
1
x
11. (lnx)′ = .
1
12. (arcsinx)′=
13. (arccosx)′= 14.(arctgx)′=
1− x
1
2
.
1− x
1
1+ x2
2
.
.
Правило дифференцирования сложной функции
(f(g(x))′= ft′ (g(x))· g′(x), где t= g(x).
82
Приложение
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
СОДЕРЖАНИЕ
Введение ……………………………………………………………………………5
1.Модель Леонтьева межотраслевой экономики…………………………………5
2. Линейное программирование……………………………………………………9
2.1. Математические модели задач линейного программирования…………...9
2.2. Графический метод решения задач линейного программирования.........14
2.3. Симплекс-метод решения задач линейного программирования………...18
2.4. Двойственные задачи линейного программирования…………………….24
2.5. Транспортная задача.……………………………………………………….29
3. Теория игр………………………………………………………………………..37
3.1. Элементы теории множеств...……………………………………………..37
3.2. Бескоалиционные игры…………………………………………………….39
3.3. Антагонистические игры…………………………………………………..42
3.4. Принцип максимина для матричных игр...……………………………….44
3.5. Смешанное расширение матричной игры...………………………………47
3.6. Методы решения матричных игр..………………………………………..49
3.7. Игры с природой……………………………………………………………56
3.8. Биматричные игры...……………………………………………………….62
3.9. Классические кооперативные игры……………………………………….66
3.10. Расчётно-графическая работа по теории игр……………………………69
4. Модели потребительского спроса………………………………………………74
4.1. Функции нескольких переменных и их дифференцирование..…………74
4.2. Экстремум функции двух переменных...…………………………………77
Список литературы…………………………………………………………………81
Приложение……………………………………………………………………..82
83
1/--страниц
Пожаловаться на содержимое документа