Методы оптимальных решений

 

C=[С_ij]_mxn

a_i = b_j – условие разрешимости (в противном случае задача не решается).

Задачи, в которых выполняется  это условие, называются «закрытыми транспортными задачами», в противном  случае – «открытыми».

Для того чтобы перейти  от открытой транспортной задачи к  закрытой вводят либо фиктивного поставщика, либо фиктивного потребителя.

Если  a_i > b_j – то вводится фиктивный поставщик.

Если  a_i < b_j – то вводится фиктивный потребитель.

a_i = 80

b_j = 80

a_i = b_j ®закрытая транспортная задача 

 

 

 

Используем метод минимальной  стоимости:

 

	Bj	B1			B2			B3			B4
Ai	bj ai	15			15			25			25
A1	a1=21			30			24		21	11				12
A2	a2=19			26		15	4		4	29				20
A3	a3=15			27			14			14			15	10
A4	a4=25		15	6			14			28			10	8

 

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

 

.

Значение целевой функции:

2.4 Решение транспортной задачи методом потенциалов

Количество ненулевых элементов в решении транспортной задачи Х₀ равно 6, ранг матрицы rang X = m + n – 1 = 4 + 4 – 1= 7. Поскольку 6 < 7, то решение Х₀ невырождено, поэтому вводим нулевые поставки.

Таблица 2.3 – Решение транспортной задачи методом потенциалов

 

bj ai		1	2	3	4	ui
		15	15	25	25
1	21	30	24	11 21	12 0	0
2	19	26	4 15	29 4	20	18
3	15	27	14	14	10 15	-2
4	25	6 15	14	28	8 10	-4
vj		10	-14	11	12

Вычисляем оценки свободных  клеток:

D₁₁ = -20< 0,

 D₁₂ = -38< 0,

D₂₁ = 2 ˃ 0,

D₂₄= 10 ˃ 0,

D₃₁ = -19 < 0,

D₃₂ = –30 < 0,

D₃₃ = -5< 0,

D₄₂= –32< 0,

D₄₃ = -32 < 0,

 

Оценка клетки  D₂₄ = 10, D₂₁ =2 следовательно, решение неоптимальное. Перейдем к другому опорному решению для уменьшения значения целевой функции.

 

 

bj ai		1	2	3	4	ui
		15	15	25	25
1	21	30	24	11 21	12	0
2	19	26	4 15	29	20 4	13
3	15	27	14	14 4	10 11	3
4	25	6 15	14	28	8 10	1
vj		5	-9	11	7

 

D₁₁ = -25< 0, 

 D₁₂ = -32< 0,

D₁₃ = -5 < 0,

D₂₁= -8< 0,

D₂₃ = -5 < 0,

D₃₁ = –19 < 0,

D₃₂ = -20< 0,

D₄₂= –22< 0,

D₄₃ = -16 < 0,

Все оценки свободных  клеток отрицательные, следовательно, решение Х₁ оптимально.

Таким образом, решение транспортной задачи:

,

Решение транспортной задачи в EXEL:

 

 

 

 

 

 

 

 

 

 

 

 

 

3. Обоснование  ценовой стратегии

Предприятие может выпускать m видов продукции, получая при этом прибыль (убытки), зависящие от спроса. Спрос может принимать n состояний. Известна матрица Н прибыли (убытка), которую получит предприятие при выпуске i-й продукции при j-м состоянии спроса.

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

3.1 Проверка игры на наличие решения в чистых стратегиях

Определим нижнюю цену игры – α. Нижняя цена игры α — это  максимальный выигрыш, который мы можем  гарантировать себе, в игре против разумного противника, если на протяжении всей игры будем использовать одну и только одну стратегию (такая стратегия называется "чистой").

Найдем в каждой строке платежной матрицы минимальный  элемент и запишем его в  дополнительный столбец 

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

 

Таблица 3.1 – Поиск нижней цены игры

Стратегии "A"	Стратегии "B"				Минимумы строк
	B1	B2	B3	В4           В5
A1	8	4	2	7                    2	2
A2	2	6	8	9                   5	5*
A3	6	2	2	5                    2	2

 

В нашем случае нижняя цена игры равна: α = 5, и для того чтобы гарантировать себе выигрыш не хуже чем 5 мы должны придерживаться стратегии А2.

Определим верхнюю цену игры - β

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

Найдем в каждом столбце  платежной матрицы максимальный элемент и запишем его в  дополнительную строку снизу

Затем найдем минимальный  элемент дополнительной строки (отмечен  плюсом), это и будет верхняя  цена игры.

 

Таблица 3.2 – Поиск верхней цены игры

Стратегии "A"	Стратегии "B"				Минимумы строк
	B1	B2	B3	В4          В5
A1	8	4	2	7               2
A2	2	6	8	9               5
A3	6	2	2	5              2
Максимумы столбцов	8	6	8	9             5*

 

В нашем случае верхняя цена игры равна: β =5, и для того чтобы гарантировать себе проигрыш не хуже чем 1 противник ( игрок "B") должен придерживаться стратегии B5.

Сравним нижнюю и верхнюю  цены игры, в данной задаче они  совпадают, т.е. α = β. Это значит, что игра имеет решение в так называемых "чистых", максимальных стратегиях.

 

Проверка

 

V(H)=5;  X*=(0;1;0),   Y*=(0;0;0;0;1)

 

 

 

 

 

 

 

 

 

 

 

 

3.2 Сведение исходной игры к задачам линейного программирования и решение в среде Microsoft Exсel

Сведем исходную игру к ПЗЛП И ДЗЛП:

Решение ПЗЛП И ДЗЛП в среде Microsoft Exсel

 

 

 

 

 

 

V(H)=

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                  Динамическое программирование.

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

Исходные данные:

Таблица 4.1 – Исходные данные

Объем капиталовложений xi (тыс. руб.)	Прирост выпуска продукции fj(xi) в зависимости от объема капиталовложений (тыс. руб.)
	предприятие 1	предприятие 2	предприятие 3
0	0	0	0
100	40	50	30
200	50	80	50
300	110	90	90
400	120	150	110
500	170	190	180
600	180	210	220
700	210	220	240

Математическая модель задачи.

Определить х^* = ( , , …, , …, ), обеспечивающий максимум целевой функции

и удовлетворяющий условиям

,

 

Математическая модель задачи варианта 10:

при ограничениях:

,

.

Условная оптимизация.

Максимально возможный  доход, который может быть получен  с предприятий (с k-го по n-е), определяется с помощью функции Беллмана:

,

где С_k – количество средств, инвестируемых в k-е предприятие, 0≤ С_k ≤ В.

На первом шаге условной оптимизации при k = n функция Беллмана представляет собой прибыль только с n-го предприятия. При этом на его инвестирование может остаться количество средств С_n, 0 ≤ С_n ≤ В. Чтобы получить максимум прибыли с этого предприятия, можно вложить в него все эти средства, т.е. F_n(С_n) = f_n(С_n) и х_n = С_n.