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

№1.

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

Он знает, что объемы продаж зависят от спроса. Оптовый поставщик поставляет масло по цене 20 руб. за одну упаковку и только тремя партиями: 100 упаковок, 1500 упаковок и 3000 упаковок. Продавец масла продает его по цене 60 руб. за одну упаковку. Продавец масла предполагает, что если спрос будет низкий, то объем продаж масла составит 100 упак., если средний, то 2000 упак., если высокий, то 3000 упак.

1. Составьте платежную матрицу продавца масла, отражающую его прибыль и убытки от продажи масла.
2. Составьте матрицу рисков.
3. Каким будет оптимальное решение продавца масла, т.е. какой объем партии ему следует закупить у оптового поставщика, если неизвестно какой спрос на масло будет завтра и он использует для принятия решения:

• а) критерий Лапласа,

• б) максиминный критерий Вальда,
• в) максимаксный критерий,
• г) критерий минимаксного риска Сэвиджа.

4.  Каким будет оптимальное решение продавца при известных вероятностях спроса на масло завтра: для низкого спроса 0,3, для среднего 0,4, для высокого спроса 0,3, если продавец использует критерий (1) максимального ожидаемого выигрыша или (2) минимального ожидаемого риска.

Решение:

Игроки	Р1  (спрос на подсолнечное масло)
Р2 (продавец)	стратегии	100 упак.	2000 упак.	3000 упак.	Min по строкам
	низкий	4000
	средний		-20000
	высокий			120000
	Max по строкам

По данным платежной матрицы продавец никогда не получит прибыли меньше 4 тыс. руб. Если стратегия В (спрос) совпадет с выбранной стратегией, то прибыль А (выигрыш) будет составлять 4,0 или 12,0 тыс. руб. Следовательно, А может обеспечить себе наибольшую прибыль, если будет попеременно принимать то стратегию А, то стратегию В. Такая стратегия называется смешанной, а ее элементы (А и В) – чистыми стратегиями.

Критерий Лапласа.

Критерий основан на предположении, что каждый вариант развития ситуации равновероятен. Поэтому для принятия решения необходимо рассчитать функцию полезности и выбрать ту альтернативу, для которой функция полезности максимальна. Данный критерий определяет оптимальное решение по минимальной функции полезности.

F1 = (45 + 30 + 50 + 80) / 4 = 51,25

F2 = (75 + 70 + 90 + 80) / 4 = 78,75

F3 = (60 + 40 + 50 + 70) / 4 = 55,0

F4 = (10 + 20 + 30 + 40) / 4 = 25,0

Следует выбрать альтернативу F4.

Критерий Вальда

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

a1 = 45;  a2 = 70;  a3 = 40;  a4 = 10

Видно, что наилучшим из наихудших показателей обладает альтернатива А2, для нее  a2 = 70

Критерий Сэвиджа

Он основан на принципе минимизации потерь, связанных с тем, что принято не оптимальное решение. Для решения составляется матрица потреь, которая называется матрицей рисков.

Матрица рисков имеет вид:

	В1	В2	В3	В4
А1	35	10	20	40
А2	65	60	60	40
А3	50	20	20	30
А4	0	0	0	0

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

b1 = 65;  b2 = 60;  b3 = 60;  b4 = 40

Принимаем альтернативу, соответствующую минимальному значению b, b4 = 40, т.е. А4

Критерий Гурвица

На уровне полезности a=0,5 функции полезности равны

F1 = 30*0.5 + 80*0.5 = 55,0

F2 = 70*0.5 + 90*0.5 = 80,0

F3 = 40*0.5 + 70*0.5 = 55,0

F4 = 10*0,5 + 40*0.5 = 25,0

Принимаем альтернативу А4 с наименьшей функцией полезности.

 

№2. 

Фирма принимает решение о стратегии замены оборудования. Считается, что замена может осуществляться в начале любого года (практически моментально), причем частичная замена оборудования невозможна. Стоимость приобретения нового оборудования и замены старого оборудования на новое составляет 6 миллионов рублей.

После замены оборудования, эксплуатировавеся до этого t лет, реализуется по цене, которая определяется формулой R (t)=0,20*(10 – t) миллионов рублей. Известно, что прибыль от реализации продукции, произведённой за год, определяется формулой F(t) = 5 – t миллионов рублей. Планирование производится на 7 лет. Определить оптимальную стратегию замены оборудования при условии, что в начальный момент времени имеется оборудование, прослужившее 1 год.

Решение:

Для упрощения расчетов заменим функцию r(t) стоимости продукции на функцию доходов: r(t) = r(t) - u(t). 
r(0) = 2 - 5 = -3 
r(1) = 1.8 - 4 = -2.2 
r(2) = 1.6 - 3 = -1.4 
r(3) = 1.4 - 2 = -0.6 
r(4) = 1.2 - 1 = 0.2 
r(5) = 1.0 - 0 = 1 
r(6) = 0.8 - 0 = 0.8 
r(7) = 0.6 - 0 = 0.6 
I этап. Условная оптимизация (k = 7,6,5,4,3,2,1). 
Переменной управления на k-м шаге является логическая переменная, которая может принимать одно из двух значений: сохранить (С) или заменить (З) оборудование в начале k-го года. 
1-й шаг: k = 7. Для 1-го шага возможные состояния системы t = 1,2,3,4,5,6,7, а функциональные уравнения имеют вид: 
F7(t) = max(r(t), (C); S(t) - P + r(0), (З) ) 
F7(1) = max(-2.2 ; 6 - 6 + -3) = -2.2 (C) 
F7(2) = max(-1.4 ; 6 - 6 + -3) = -1.4 (C) 
F7(3) = max(-0.6 ; 6 - 6 + -3) = -0.6 (C) 
F7(4) = max(0.2 ; 6 - 6 + -3) = 0.2 (C) 
F7(5) = max(1 ; 6 - 6 + -3) = 1 (C) 
F7(6) = max(0.8 ; 6 - 6 + -3) = 0.8 (C) 
F7(7) = max(0.6 ; 6 - 6 + -3) = 0.6 (C) 
2-й шаг: k = 6. Для 2-го шага возможные состояния системы t = 1,2,3,4,5,6, а функциональные уравнения имеют вид: 
F6(t) = max(r(t) + F7(t+1) ; S(t) - P + r(0) + F7(1)) 
F6(1) = max(-2.2 + -1.4 ; 6 - 6 + -3 + -2.2) = -3.6 (C) 
F6(2) = max(-1.4 + -0.6 ; 6 - 6 + -3 + -2.2) = -2 (C) 
F6(3) = max(-0.6 + 0.2 ; 6 - 6 + -3 + -2.2) = -0.4 (C) 
F6(4) = max(0.2 + 1 ; 6 - 6 + -3 + -2.2) = 1.2 (C) 
F6(5) = max(1 + 0.8 ; 6 - 6 + -3 + -2.2) = 1.8 (C) 
F6(6) = max(0.8 + 0.6 ; 6 - 6 + -3 + -2.2) = 1.4 (C) 
3-й шаг: k = 5. Для 3-го шага возможные состояния системы t = 1,2,3,4,5, а функциональные уравнения имеют вид: 
F5(t) = max(r(t) + F6(t+1) ; S(t) - P + r(0) + F6(1)) 
F5(1) = max(-2.2 + -2 ; 6 - 6 + -3 + -3.6) = -4.2 (C) 
F5(2) = max(-1.4 + -0.4 ; 6 - 6 + -3 + -3.6) = -1.8 (C) 
F5(3) = max(-0.6 + 1.2 ; 6 - 6 + -3 + -3.6) = 0.6 (C) 
F5(4) = max(0.2 + 1.8 ; 6 - 6 + -3 + -3.6) = 2 (C) 
F5(5) = max(1 + 1.4 ; 6 - 6 + -3 + -3.6) = 2.4 (C) 
4-й шаг: k = 4. Для 4-го шага возможные состояния системы t = 1,2,3,4, а функциональные уравнения имеют вид: 
F4(t) = max(r(t) + F5(t+1) ; S(t) - P + r(0) + F5(1)) 
F4(1) = max(-2.2 + -1.8 ; 6 - 6 + -3 + -4.2) = -4 (C) 
F4(2) = max(-1.4 + 0.6 ; 6 - 6 + -3 + -4.2) = -0.8 (C) 
F4(3) = max(-0.6 + 2 ; 6 - 6 + -3 + -4.2) = 1.4 (C) 
F4(4) = max(0.2 + 2.4 ; 6 - 6 + -3 + -4.2) = 2.6 (C) 
5-й шаг: k = 3. Для 5-го шага возможные состояния системы t = 1,2,3, а функциональные уравнения имеют вид: 
F3(t) = max(r(t) + F4(t+1) ; S(t) - P + r(0) + F4(1)) 
F3(1) = max(-2.2 + -0.8 ; 6 - 6 + -3 + -4) = -3 (C) 
F3(2) = max(-1.4 + 1.4 ; 6 - 6 + -3 + -4) = 0 (C) 
F3(3) = max(-0.6 + 2.6 ; 6 - 6 + -3 + -4) = 2 (C) 
6-й шаг: k = 2. Для 6-го шага возможные состояния системы t = 1,2, а функциональные уравнения имеют вид: 
F2(t) = max(r(t) + F3(t+1) ; S(t) - P + r(0) + F3(1)) 
F2(1) = max(-2.2 + 0 ; 6 - 6 + -3 + -3) = -2.2 (C) 
F2(2) = max(-1.4 + 2 ; 6 - 6 + -3 + -3) = 0.6 (C) 
7-й шаг: k = 1. Для 7-го шага возможные состояния системы t = 1, а функциональные уравнения имеют вид: 
F1(t) = max(r(t) + F2(t+1) ; S(t) - P + r(0) + F2(1)) 
F1(1) = max(-2.2 + 0.6 ; 6 - 6 + -3 + -2.2) = -1.6 (C) 
Результаты вычислений по уравнениям Беллмана Fk(t) приведены в таблице, в которой k - год эксплуатации, а t - возраст оборудования.

k / t	1	2	3	4	5	6	7
1	-1.6	0	0	0	0	0	0
2	-2.2	0.6	0	0	0	0	0
3	-3	0	2	0	0	0	0
4	-4	-0.8	1.4	2.6	0	0	0
5	-4.2	-1.8	0.6	2	2.4	0	0
6	-3.6	-2	-0.4	1.2	1.8	1.4	0
7	-2.2	-1.4	-0.6	0.2	1	0.8	0.6

 
В таблице выделено значение функции, соответствующее состоянию (З) - замена оборудования. 
II этап. Безусловная оптимизация (k = 7,6,5,4,3,2,1) 
Безусловная оптимизация начинается с шага при k = 1. Максимальной возможный доход от эксплуатации оборудования за годы с 1-го по 8-й составляет F1(1) = -1.6. Этот оптимальный выигрыш достигается, если на первом году не производить замены оборудования. 
К началу 2-го года возраст оборудования увеличится на единицу и составит: t2 = t1 + 1 = 1 + 1 = 2. 
Оптимальное управление при k = 2, x2(2) = (C), т.е. максимум дохода за годы с 2-го по 7-й достигается, если оборудование сохраняется, т.е. не заменяется. 
К началу 3-го года возраст оборудования увеличится на единицу и составит: t3 = t2 + 1 = 2 + 1 = 3. 
Оптимальное управление при k = 3, x3(3) = (C), т.е. максимум дохода за годы с 3-го по 7-й достигается, если оборудование сохраняется, т.е. не заменяется. 
К началу 4-го года возраст оборудования увеличится на единицу и составит: t4 = t3 + 1 = 3 + 1 = 4. 
Оптимальное управление при k = 4, x4(4) = (C), т.е. максимум дохода за годы с 4-го по 7-й достигается, если оборудование сохраняется, т.е. не заменяется. 
К началу 5-го года возраст оборудования увеличится на единицу и составит: t5 = t4 + 1 = 4 + 1 = 5. 
Оптимальное управление при k = 5, x5(5) = (C), т.е. максимум дохода за годы с 5-го по 7-й достигается, если оборудование сохраняется, т.е. не заменяется. 
К началу 6-го года возраст оборудования увеличится на единицу и составит: t6 = t5 + 1 = 5 + 1 = 6. 
Оптимальное управление при k = 6, x6(6) = (C), т.е. максимум дохода за годы с 6-го по 7-й достигается, если оборудование сохраняется, т.е. не заменяется. 
К началу 7-го года возраст оборудования увеличится на единицу и составит: t7 = t6 + 1 = 6 + 1 = 7. 
Оптимальное управление при k = 7, x7(7) = (C), т.е. максимум дохода за годы с 7-го по 7-й достигается, если оборудование сохраняется, т.е. не заменяется. 
Таким образом, за 7 лет эксплуатации оборудования нет необходимости производить замену.

 

ИТОГОВАЯ КОНТРОЛЬНАЯ РАБОТА

 

Задача 2

Найти и изобразить в декартовой системе координат области выпуклости и вогнутости функции:

F(x, y) = (х – 1)3 – 6*х*у + у3

Выпуклы ли построенные области

Решение:

График дифференцируемой функции называется выпуклым в интервале [a, b], если в этом интервале он расположен ниже любой своей касательной.

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

Теорема (достаточный признак вогнутости или выпуклости графика). Если для функции f(x) во всех точках интервала [a, b]

то кривая y = f(x) вогнута в этом интервале; если же

во всех точках интервала ]a, b[, то кривая выпукла в этом интервале.

Определим значение производной

F’(x) = 3*(x – 1)2*1 – 6*y

F’(y) = -6*x + 3*y2

Очевидно, что в обоих случаях функции f(x) во всех точках интервала [a, b]

а следовательно, кривая y = f(x) вогнута в этом интервале;

  
Задача 3.

Задачу нелинейного программирования

 при 

Необходимо:

1. Привести к стандартному виду.
2. Изобразить допустимое множество и линии уровня целевой функции; решить задачу графически.
3. Проверить, выполняются ли условия теоремы Вейерштрасса о существовании решения.
4. На рисунке проверить выполнение условий Куна-Таккера в угловых точках допустимого множества (т.е. в точках, в которых число активных ограничений не меньше числа переменных) и в точках касания линии уровня целевой функции с границами допустимой области.
5. Найти точки, в которых условия Куна-Таккера выполняются, и определить, какие из ограничений являются активными в таких точках.
6. Выписать условия Куна-Таккера в найденных точках и рассчитать значения двойственных переменных.
7. Сделать обоснованный вывод о наличии или отсутствии локального (глобального) максимума во всех рассмотренных точках.

Решение:

Приведем задачу к стандартному виду:

 при 

Ясно, что оптимальное решение этой задачи есть Покажем, что условие линейной независимости не выполняется в точке оптимума.

Так как  то I = {1, 3}. Далее

Видно, что векторы  и  линейно зависимы, т. е. условие линейной независимости в точке Х* = (1, 0) не выполняется.