Контрольная работа по «Экономическо-математическому моделированию»

 

Задание 1

 На одном и  том  же оборудовании предприятие  должно выпускать пять видов  продукции партиями. Издержки переналадок  при переходе от одного вида  продукции к другому представлены  матрицей  , где затраты на переналадку оборудования при переходе от выпуска i-го вида продукции к выпуску j-го вида продукции. Методом ветвей и границ (алгоритм Литтла) найти последовательность запуска партий продукции в производство, при котором будут минимальны суммарные потери от переналадок.

                                                                                                  

 

Решение:

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

Для каждого нуля матрицы  выписана его степень:

По степеням нулей определяем, что наиболее вероятной дугой  гамильтонова контура является l(1, 5). В связи с этим рассматриваем две матрицы :

 

 

 

                             

Матрица C₁ (1,5) оказалась приведенной , а   оказалась не  приведенной. Константы приведения для полученных  приведенных матриц соответственно будут Так как , то далее рассматриваем,  матрицу :

 

                                       

  По степеням нулей  определяем, что наиболее вероятной  дугой гамильтонова контура является  например дуга l(5, 4). В связи с этим рассматриваем две матрицы , которые после приведения принимают вид:

 

 

 

 

 

 

 

 

 

 

 

 

Константы приведения для  них  . Так как то далее рассматриваем матрицу, например, C₂(5,4):

 

 

 

 

 

 

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

 

 

 

 

 

 
Константы приведения для них  . Так как , то далее рассматриваем матрицу, например, :

                              

 Из матрицы C₃(3, 2) определяем последние две дуги гамильтонова контура: l(2, 1) и l(4, 3). Так как значение меньше значений , (k = 1, 2, 3) альтернативных вариантов, именно, то получено оптимальное решение задачи, состоящее из дуг (1, 5), (5, 4), (4, 3), (3, 2), (2, 1). Из этих дуг составляем замкнутый гамильтонов контур: . Это означает следующее. Если запуск партии продукции начинается с 1-го вида продукции, то после 1-го вида должна начаться переналадка оборудования на выпуск 5-го вида продукции, после 5-го – 4-й, после 4-го –    3-й вид продукции;  после 3-го начать переналадку на выпуск продукции 2-го вида, а затем вернуться снова на выпуск продукции 1-го вида. Сумма затрат на переналадку составит L = 9+10+10+11+10=50.

Задание 2

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

Решение:

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

В нашем случае, количество чистых стратегий игрока А равно 4 . Количество чистых стратегий игрока В равно 4 .

Что думает игрок А?

Если я выберу стратегию  A1 ,то при любом действии игрока B, я гарантирую себе выигрыш -3 ,т.е. потеряю не более 3 ден. ед.

Если я выберу стратегию  A2 ,то при любом действии игрока B, я гарантирую себе выигрыш -4 ,т.е. потеряю не более 4 ден.ед.

Если я выберу стратегию  A3 ,то при любом действии игрока B, я гарантирую себе выигрыш -1 ,т.е. потеряю не более 1 ден.ед.

Если я выберу стратегию  A4 ,то при любом действии игрока B, я гарантирую себе выигрыш -4 ,т.е. потеряю не более 4 ден.ед.

		Стратегии игрока В				Минимаьный элемент в  строке
		В1	В2	В3	В4
Стратегия игрока А	А1	-1	-3	0	3	-3
	А2	-2	-4	0	-1	-4
	А3	1	0	2	-1	-1
	А4	-2	2	3	-4	-4

Игрок А использует логику, которая гарантирует ему максимальный выигрыш вне зависимости от поведения  игрока В.

 Свой выбор, игрок  А остановит на стратегии A4, которая обеспечит ему выигрыш -1, т.е. потерю не более 1 ден.ед.

 Значение  равное -1, называется нижней ценой  игры.

Что думает игрок B?

Если я выберу стратегию  B1 ,то при любом действии игрока A, я гарантирую себе проигрыш 1 ,т.е. потеряю не более 1 ден.ед.

Если я выберу стратегию  B2 ,то при любом действии игрока A, я гарантирую себе проигрыш 2 ,т.е. потеряю не более 2 ден.ед.

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

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

		Стратегии игрока В				Минимаьный элемент в  строке
		В1	В2	В3	В4
Стратегия игрока А	А1	-1	-3	0	3	-3
	А2	-2	-4	0	-1	-4
	А3	1	0	2	-1	-1
	А4	-2	2	3	-4	-4
Максимальный элемент  в столбце		1	2	3	3

Игрок В использует логику, которая гарантирует ему минимальный  проигрыш вне зависимости от поведения  игрока А.

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

 Значение  равное 1, называется верхней ценой игры.

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

Смешанной стратегией игрока А называется применение чистых стратегий  A1 , A2 , A3 , A4 c вероятностями p1 , p2 , p3 , p4 .

Смешанную стратегию первого  игрока обозначают как вектор:

 P = ( p1 , p2 , p3 , p4 ) , где p1 + p2 + p3 + p4 = 1  и   (p1, p2, p3, p4) ≥ 0

Смешанной стратегией игрока B называется применение чистых стратегий B1 , B2 , B3 , B4 c вероятностями q1 , q2 , q3 , q4 .

 Смешанную стратегию  второго игрока обозначают как  вектор:

 Q = ( q1 , q2 , q3 , q4 ) , где q1 + q2 + q3 + q4 = 1  и   (q1, q2, q3, q4)≥ 0

Оптимальное решение игры (или просто - решение игры) - это  пара оптимальных смешанных стратегий

P* ( p*1 , p*2 , p*3 , p*4 ) и Q* ( q*1 , q*2 , q*3 , q*4 )

обладающих следующим  свойством:

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

Выигрыш игрока А равный проигрышу игрока В , соответствующий  оптимальному решению, называется ценой игры v.

Цена игры больше либо равна  нижней цены игры и меньше или равна  верхней цены игры.

В нашем случае : -1≤  v≤  1.

		Стратегии игрока В
		В1	В2	В3	В4
Стратегия игрока А	А1	-1	-3	0	3
	А2	-2	-4	0	-1
	А3	1	0	2	-1
	А4	-2	2	3	-4

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

Стратегия A3 является доминирующей над стратегией A2 , т.к. каждый элемент строки 3 больше или равен соответствующего элемента строки 2. Игроку А заведомо не выгодно пользоваться стратегией A2. Удаляем стратегию A2 из рассмотрения .

Стратегии игрока А		Стратегии игрока В
		В1	В2	В3	В4
	А1	-1	-3	0	3
	А3	1	0	2	-1
	А4	-2	2	3	-4

 

Стратегия B1 является доминирующей над стратегией B3 , т.к. каждый элемент столбца 1 меньше или равен соответствующего элемента столбца 3. Игроку B заведомо не выгодно пользоваться стратегией B3. Удаляем стратегию B3 из рассмотрения .

Стратегии игрока А		Стратегии игрока В
		В1	В2	В4
	А1	-1	-3	3
	А3	1	0	-1
	А4	-2	2	-4

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

P* = ( р*1 , 0 , p*3 , p*4 ) ,

 Q* = ( q*1 , q*2 , 0 , q*4 ).

 В нашей задаче, значение  цены игры определяется неравенством 

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

В нашем случае , прибавим 4 к каждому элементу матрицы. Тогда, цена исходной игры v = v1 -4, где v1 - цена игры получившийся матрицы.

Стратегии игрока А		Стратегии игрока В
		В2	В3	В4
	А1	1	0	2
	А2	0	1	3
	А4	2	4	1

Если P* = ( p*1 , 0 , p*3 , p*4 ) и Q* = ( q*1 , q*2 , 0 , q*4 ) являются оптимальным решением, то должны выполняться две следующие системы неравенств: