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

Определение новой базисной переменной.

max(3,4,0,-1,0) = 4

x0 = -12+3x1+4x2-x4

x3 = 3-2x1-x2

x5 = 12-3x1-4x2+x4

В качестве новой переменной выбираем x2.

 Определение новой свободной переменной. Вычислим значения Di по всем уравнениям для этой переменной:bi /ai2 и из них выберем наименьшее:

min (3 : 1 , 12 : 4 ) = 3

Вместо переменной x5 в план войдет переменная x2.

Выразим переменную x2 через x5

x2 = 3-3/4x1+1/4x4-1/4x5

и подставим во все выражения.

x0 = -12+3x1+4(3-3/4x1+1/4x4-1/4x5)-x4

x3 = 3-2x1-(3-3/4x1+1/4x4-1/4x5)

После приведения всех подобных, получаем новую систему, эквивалентную прежней: 
x0 = 0-x5

x3 = 0-5/4x1-1/4x4+1/4x5

x2 = 3-3/4x1+1/4x4-1/4x5

Полагая небазисные переменные x = (3, 2) равными нулю, получим новый допустимый вектор и значение целевой функции:

x = (0, 0, 0, 0, 1), x0 = 0

Выражение для x0 не содержит положительных элементов. Найден оптимальный план.

x0 = 0-x5

x3 = 0-5/4x1-1/4x4+1/4x5

x2 = 3-3/4x1+1/4x4-1/4x5

На этом первый этап симплекс-метода завершен. Переходим ко второму этапу. Удаляем переменные с искусственными переменными.

x3 = 0-5/4x1-1/4x4

x2 = 3-3/4x1+1/4x4

Выразим базисные переменные:

x2 = 3-3/4x1+1/4x4

которые подставим в целевую функцию:

F(X) = 3x1 + 2(3-3/4x1+1/4x4)

Или

F(X) = 6+3/2x1+1/2x4

Получаем новую систему переменных.

x0 = 6+3/2x1+1/2x4

x3 = 0-5/4x1-1/4x4

x2 = 3-3/4x1+1/4x4

В выражении для x0 присутствуют отрицательные элементы. Следовательно, текущий план неоптимален

Определение новой базисной переменной.

max(3/2,0,0,1/2) = 3/2

x0 = 6+3/2x1+1/2x4

x3 = 0-5/4x1-1/4x4

x2 = 3-3/4x1+1/4x4

В качестве новой переменной выбираем x1.

Определение новой свободной переменной. Вычислим значения Di по всем уравнениям для этой переменной:bi /ai1 и из них выберем наименьшее:

min (0 : 11/4 , 3 : 3/4 ) = 0

Вместо переменной x3 в план войдет переменная x1.

Выразим переменную x1 через x3

x1 = 0-4/5x3-1/5x4

и подставим во все выражения.

x0 = 6+11/2(0-4/5x3-1/5x4)+1/2x4

x2 = 3-3/4(0-4/5x3-1/5x4)+1/4x4

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

x0 = 6-6/5x3+1/5x4

x1 = 0-4/5x3-1/5x4

x2 = 3+3/5x3+2/5x4

Полагая небазисные переменные x = (1, 2) равными нулю, получим новый допустимый вектор и значение целевой функции:

x = (0, 0, 6/5, -1/5), x0 = 6

В выражении для x0 присутствуют отрицательные элементы. Следовательно, текущий план неоптимален

Определение новой базисной переменной.

max(0,0,-6/5,1/5) = 1/5

x0 = 6-6/5x3+1/5x4

x1 = 0-4/5x3-1/5x4

x2 = 3+3/5x3+2/5x4

В качестве новой переменной выбираем x4.

Определение новой свободной переменной. Вычислим значения Di по всем уравнениям для этой переменной: bi /ai4 и из них выберем наименьшее: 
min (0 : 1/5 , - ) = 0

Вместо переменной x1 в план войдет переменная x4.

Выразим переменную x4 через x1

x4 = 0-5x1-4x3

и подставим во все выражения.

x0 = 6-11/5x3+1/5(0-5x1-4x3)

x2 = 3+3/5x3+2/5(0-5x1-4x3)

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

x0 = 6-x1-2x3

x4 = 0-5x1-4x3

x2 = 3-2x1-x3

Полагая небазисные переменные x = (4, 2) равными нулю, получим новый допустимый вектор и значение целевой функции:

x = (1, 0, 2, 0), x0 = 6

Выражение для x0 не содержит положительных элементов. Найден оптимальный план.

Окончательный вариант системы уравнений:

x0 = 6-x1-2x3

x4 = 0-5x1-4x3

x2 = 3-2x1-x3

Так как в оптимальном решении отсутствуют искусственные переменные (они равны нулю), то данное решение является допустимым. 
Оптимальный план можно записать так:

x2 = 3

z(X) = 2×3 = 6

 

 

 

 

 

Задание №2. Экстремальные задачи. Конечномерные гладкие задачи с равенствами

 

ЗАДАЧА 2.4.    

Решение.

Решение. Функция Лагранжа

.

Необходимое условие локального экстремума:

 

Если l0= 0, то l¹ 0. Тогда из предыдущих уравнений вытекает, что    х1=x2 = 0, но эта точка не является допустимой. Полагаем l0= -1.

Для того чтобы система имела ненулевое решение коэффициенты при переменных должны быть пропорциональны:

1. l=-2

Положив х1 = 2с, получим х2 = -3с, где с-константа

Подставляя х1, х2 в ограничение  , получаем что

16с2+ 9с2=25, с= -1 или с=1

Соответственно имеем две стационарные точки (2; -3),(-2; 3)

2. l=4,25

Положив х1 = 3с, получим х2 = 8с, где с-константа

Подставляя х1, х2 в ограничение  , получаем что

36с2+ 64с2=25, с= -0,5 или с=0,5

Соответственно имеем еще две стационарные точки (-1,5; -4),(1,5; 4)

По теореме Вейерштрасса (в силу компактности эллипса) существуют решения задач на максимум и минимум. Рассматривая значения функционала в стационарных точках, получаем: ,

 

(-1,5;-4)Î absmax, Smах = 106,25;

(1,5;4)Î absmax, Smах = 106,25;

(2;-3)Î absmin, Smin = -50;

(-2;3)Î absmin, Smin = -50.

 

 

Задание №3. Теория игр. Дерево решений

 

ЗАДАЧА3.5. Магазин «Молоко» продает в розницу молочные продукты. Директор магазина должен определить, сколько бидонов сметаны следует закупить у производителя для торговли в течении недели. Вероятность того, что спрос на сметану в течение недели будет 7,8,9 или 10 бидонов, равны соответственно 0,2; 0,2; 0,5 и 0,1. Покупка одного бидона сметаны обходится магазину в 70 руб., а продается сметана по цене 110 руб. за бидон. Если сметана не продается в течение недели, она портится, и магазин несет убытки. Сколько бидонов сметаны желательно приобретать для продажи? Какова ожидаемая стоимостная ценность этого решения?

Решение. Пользуясь исходными данными, строим матрицу игры. Стратегиями игрока 1 (Магазин «Молоко») являются различное количество закупки бидонов сметаны, которые ему, возможно, следует производить. Состояниями природы выступают величины спроса на аналогичное число бидонов сметаны.

Вычислим, например, показатель прибыли, которую получит производитель, если он закупил 8 бидонов, а спрос будет только на 7.

Каждый бидон продается по 110 руб. Магазин продал 7, а закупил 8 бидоновв. Следовательно, выручка будет 7*110, а издержки производства 8 ящиков 8*70. Итого прибыль от указанного сочетания спроса и предложения будет равна: 7*110 - 8*70 = 210руб. Аналогично производятся расчеты при других сочетаниях спроса и предложения.

Средняя ожидаемая прибыль находится как математическое ожидание :

В итоге получим следующую платежную матрицу в игре с природой (табл. 1). Как видим, наибольшая средняя ожидаемая прибыль равна 298 руб. Она отвечает покупке 8 бидонов сметаны.

 

 

Спрос       Покупка бидонов	7	8	9	10	Средняя ожидаемая прибыль
pj	0,2	0,2	0,5	0,1
7	280	280	280	280	280
8	210	320	320	320	298
9	140	250	360	360	294
10	70	180	290	400	235

 

Выводы: по результатам рассмотрения желательно покупать для продажи 8 бидонов сметаны. Ожидаемая стоимостная ценность этого решения – 298 руб. 
Задание № 4. Портфели. Эффективная граница множества инвестиционных возможностей при разрешении коротких продаж

ЗАДАЧА 7.2. Даны ценные бумаги трех видов с ожидаемыми доходностями    и , ковариационная матрица доходностей которых имеет вид

1. Найти множество портфелей, определяющих эффективную границу Г(Ω3).
2. Записать уравнение эффективной границы Г(Ω3).
3. Изобразить эффективную границу на рисунке.

Решение.

Эффективная граница Г (Wn) совпадает с множеством точек вида (smin (r), r) при r ³ r*, где r* - ожидаемая доходность допустимого портфеля с наименьшим риском.

Чтобы найти портфель с наименьшей дисперсией доходности при ожидаемой доходности, равной r, необходимо решить систему линейных уравнений:

 

Все портфели с наименьшей дисперсией доходности при заданной ожидаемой доходности имеют следующий вид:

где а1, ..., аn; b1 ,…, bn - некоторые числа.

Если портфели и определяют инвестиционные возможности из множества {(smin (r), r) }, то

À ( , ) = {(smin (r), r) }.

Эффективная граница Г (Wn) задается уравнением вида

причем если r(L) = n, а среди ожидаемых доходностей имеются несовпадающие, то А > 0, В < 0 и В2 - 4АС < 0.

ssQsQsQsQQQQQQQ

sQQQQQsQQsQQQQQ

Для решения данной задачи запишем функцию Лагранжа:

L =+ l×(QQQ+ l×(×Q×Q×Q

Переходим к теореме Куна-Такера:

¶¶QQQQQQQ

Существуют  числа и (i = 1, 2, 3),не зависящие от r,такие, что вектор

Qmin(r) =   - это множество портфелей с наименьшим риском при заданной доходности, которое является оптимальным решением системыДля оптимальности решения данной задачи необходимо и достаточно соблюдение следующих условий:

 

Чтобы решить систему, перейдем к методу Гаусса :

Вычисления проводим в Excel, выделяя для коэффициента r отдельный столбец:

 

 

Множество инвестиционных возможностей {(min(r), r)} определяется уравнением:

Г (Ω3)  = = (Ar2 + Br + C)1/2 , гдеА> 0, B<0 0, B2 – 4AC<0

A = = ×× + ×××* + ××× + ×××  = 100/17=5,8824

B =

C = =11/51= 0,2157

B2 – 4AC= -0,4349

Ожидаемая доходность допустимого портфеля с наименьшим риском:

* = -B/2A = 0,183137255

r³ -0,19

Эффективная граница множества инвестиционных возможностей:

(Ω3) = (5,8824r2 -2,2353r +  0,2157)1/2

Ответ