Контрольная работа по "Прикладной математике"

 

Решение.

 

Для решения транспортной задачи применяем метод потенциалов.

Исходные данные задачи имеют вид: А (а₁, а₂, а₃) = (45, 55, 70); В (b₁, b₂, b₃) = (59, 27, 40, 35);

Общий объем производства больше, чем требуется всем магазинам , т.е. имеем открытую модель транспортной задачи. Для превращения ее в закрытую вводим фиктивный пункт потребления с объемом потребления 170-161 = 9 ед., при этом тарифы на перевозку в этот пункт будут равны нулю.

 

Первое базисное допустимое решение строится по методу северо-западного  угла:

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

L₁ = 45 ·1 + 14 · 3 + 27 · 2 + 14 · 4 + 26 · 3 + 35 · 1 + 9 · 0 = 310 ед.

 

Вычисление потенциалов    Вычисление оценок всех свободных клеток

D11=0	q1+ p1-c11=0	q1+0-1=0	q1=1		D31=q1+p3-c31=1+1-4= -2
D21=0	q1+p2-c21=0	1+p2-3=0	p2=2		D12=q2+p1-c12=0+0-3= -3
D22=0	q2+p2-c22=0	q2+2-2=0	q2=0		D13=q3+p1-c13=2+0-2=0
D23=0	q3+p2-c23=0	q3+2-4=0	q3=2		D14=q4+p1-c14=0+0-2= -2
D33=0	q3+p3-c33=0	2+ p3-3=0	p3=1		D15=q5+p1-c15= -1+0-0= -1
D34=0	q4+p3-c34=0	q4+1-1=0	q4=0		D25=q5+p2-c25= -1+2-0= 1
D35=0	q5+p3-c35=0	q5+1-0=0	q5= -1

Находим в транспортной таблице наибольшую положительную  оценку свободной клетки D_ij.  В нашем случае – это одна единственная клетка с₂₅=1. Оценка свободной клетки D_ij показывает, насколько уменьшатся суммарные расходы по перевозке груза, если поставить единицу груза от i-го производителя j-му потребителю (перераспределив остальные поставки так, чтобы сохранился баланс по строкам и столбцам).

 

Для найденной свободной  клетки 25 строим цикл пересчета:

 

14			®	14-ρ	ρ	® ρmax=9	5	9
26	35	9		26+ρ	9-ρ		35

 

Получаем второе базисное допустимое решение:

 

 

L₂ = 45 ·1 + 14 · 3 + 27 · 2 + 5 · 4 + 9 · 0 + 35 · 3 + 35 · 1 = 301 ед.

 

Все оценки свободных  клеток £ 0, следовательно, мы получили оптимальное базисное допустимое решение:

 

 

 

 

 

 

 

 

 

 

 

Динамическое  программирование. Распределение капитальных  вложений.

 

Пусть производственное объединение состоит из четырех  предприятий (n=4). Общая сумма капитальных  вложений равна 700 тыс. рублей (b=700), выделяемые предприятиям суммы кратны 100 тыс. рублей. Значения функций f_j(x_j) приведены в таблице 4.1., где, например, число 38 означает, что если третье предприятие получит 600 тыс. руб. капитальных вложений, то прирост прибыли на этом предприятии составит 38 тыс. руб.

 

Таблица 4.1.

xj	0	100	200	300	400	500	600	700
f1(x1)	0	10	20	30	38	43	49	52
f2(x2)	0	13	25	37	47	55	61	66
f3(x3)	0	6	13	20	27	33	38	41
f4(x4)	0	24	36	42	46	48	48	49

 

 

Решение.

 

Прежде всего заполняем  табл. 4.2. Значения f₂(x₂) складываем со значениями F₁(x - x₂) = f₁(x- x₂) и на каждой северо-восточной диагонали находим наибольшее число, которое отмечаем звездочкой и указываем соответствующее значение .

 

Табл. 4.2.

 

 

 

 Заполняем таблицу  4.3.

 

Табл. 4.3.

x	0	100	200	300	400	500	600	700
F2(x)	0	13	25	37	47	57	67	77
	0	100	200	300	300/400	300/400	300/400	400

 

 

 

Продолжая процесс, табулируем функции F₃(x), (x)  (см. Табл. 4.4. и 4.5.) и т.д.

 

Табл. 4.4.

 

 

Табл. 4.5.

 

x	0	100	200	300	400	500	600	700
F3(x)	0	13	25	37	47	57	67	77
	0	0	0	0	0	0	0	0

 

В табл. 4.6. заполняем только одну диагональ для значения x= 700.

Табл. 4.6.

 

 

Наибольшее число на этой диагонали:

 

Z_max = 93 тыс. руб.,

 

причем четвертому предприятию  должно быть выделено:

 

 тыс. руб.

 

На долю остальных  трех предприятий остается 500 тыс. руб. Из Таб. 4.5. видно, что третьему предприятию  должно быть выделено:

 

 тыс. руб.

 

 

Продолжая обратный процесс, находим:

 

1) тыс. руб.

 

2) тыс. руб.

  На долю первого предприятия остается:

 

1) тыс. руб.

 

2) тыс. руб.

 

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

 

1)

 

2)

 

Оно обеспечивает производственному  объединению наибольший воможный прирост прибыли 93 тыс. руб.

 

Проверка выполнения равенства:

 

 

1)

 

2)

 

 

 

 

 

 

 

 

 

 

 

 

               

 

     Теория игр

 

 

Игроки	B1	B2	B3	B4	a = min(Ai)
A1	-1	-3	-5	0	-5
A2	2	0	2	-1	-1
b = max(Bi)	2	0	2	0

 

 

 

 

 

 

Находим гарантированный  выигрыш, определяемый нижней ценой  игры a = max(ai) = -1, которая указывает на максимальную чистую стратегию A2. 
Верхняя цена игры b = min(bj) = 0. 
Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах -1 <= y <= 0. Находимо решение игры в смешанных стратегиях. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии)

В матрице присутствуют отрицательные элементы. Для упрощения  расчетов добавим к элементам  матрицы (5). Такая замена не изменит  решения игры, изменится только ее цена.

4	2	0			5
7	5	7	4

 
Решим задачу геометрическим методом, который включает в себя следующие  этапы: 
1. В декартовой системе координат по оси абсцисс откладывается отрезок, длина которого равна 1. Левый конец отрезка (точка х = 0) соответствует стратегии A₁, правый - стратегии A₂ (x = 1). Промежуточные точки х соответствуют вероятностям некоторых смешанных стратегий S₁ = (p₁,p₂). 
2. На левой оси ординат откладываются выигрыши стратегии A₁. На линии, параллельной оси ординат, из точки 1 откладываются выигрыши стратегии A₂. 
Решение игры (2 x n) проводим с позиции игрока A, придерживающегося максиминной стратегии. Доминирующихся и дублирующих стратегий ни у одного из игроков нет. 
Максиминной оптимальной стратегии игрока A соответствует точка N, лежащая на пересечении прямых B₂B₂ и B₄B₄, для которых можно записать следующую систему уравнений: 
y = 2 + (5 - 2)p₂ 
y = 5 + (4 - 5)p₂ 
Откуда 
p₁ = ¹/₄ 
p₂ = ³/₄ 
Цена игры, y = 4¹/₄

 

Оптимальные стратегии  игрока А: Sа ( _{1/4 ; 3/4 )}

 
Теперь можно найти минимаксную  стратегию игрока B, записав соответствующую систему уравнений, исключив стратегию B₁,B₃, которая дает явно больший проигрыш игроку B, и, следовательно, q₁ = 0,q₃ = 0. 

2q₂+5q₄ = y 
5q₂+4q₄ = y 
q₂+q₄ = 1 
или 
2q₂+5q₄ = 4¹/₄ 
5q₂+4q₄ = 4¹/₄ 
q₂+q₄ = 1 
Решая эту систему, находим: 
q₂ = ¹/₄ 
q₄ = ^¾

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 
Поскольку ранее к элементам матрицы  было прибавлено число 5, то вычтем это число из цены игры. 
Цена игры: y = 4¹/₄ - 5 = ^-3/₄

Оптимальные стратегии  игрока B: SB ( 0; ¼; 0; 3/4)