Моделирование экономических процессов

Размещено на http://www.allbest.ru/

Задача 1

Используя графический метод, найти решение следующей задачи линейного программирования:

F(x)=6х1-4х2 > extr

Решение:

Построим на плоскости Х1ОХ2 многоугольник решений - область допустимых решений задачи линейного программирования. Для этого в неравенствах системы ограничений и условиях неотрицательности переменных знаки неравенств заменим на знаки точных равенств.

графический доход дефицитный стратегия

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



Многоугольником решений задачи является шестиугольник АВСDЕF, координаты точек которого удовлетворяют условию неотрицательности переменных и неравенствам системы ограничений задачи.

Для нахождения точек экстремума (точки минимума и точки максимума) построим начальную прямую L0 (линию нулевого уровня) F(x)=0 то есть 6х1-4х2=0 и вектор (6; -4). Передвигая начальную прямую в направлении вектора (6; -4) (предварительно сдвинув её назад, найдем точки В и С - отрезка ВС (точки входа) в которых начальная прямая принимает положение опорной прямой и точку Е (точку выхода) в которой начальная прямая также принимает положение опорной прямой. Следовательно, в точках В и С (отрезка ВС) целевая функция имеет минимальное значение, а в точке Е целевая функция имеет максимальное значение.

В(0; 3); С(2; 6); Е(6; 1,2) - координаты этих точек, которые вычисляются из решения соответствующих систем:

Fmin(X)=Fmin(0; -3)=6·0-4·3=-12;

Fmin(X)=Fmin(2; 6)=6·2-4·6=-12;

Fmax(X)=Fmax(6; 12)=6·6-4·1,2=31,2;

Итак, Fmin(0; -3)=Fmin(2; 6)=-12 и Fmax(6; 12)=31,2.

Задача 2

На предприятии имеется возможность выпускать n=4 вида продукции П1, П2, П3, П4. При изготовлении используются ресурсы Р1, Р2, и Р3. Размеры допустимых затрат ресурсов ограничены соответственно величинами b1, b2, b3. Расход ресурса i-го вида на единицу продукции j-го вида составляет аij единиц. Цена единицы продукции j-го вида равна сj денежных единиц. Требуется исходные данные свести в таблицу. По таблице составить математическую модель задачи. С помощью симплексных таблиц найти план выпуска продукции по видам с учётом имеющихся ограничений ресурсов, который обеспечивал бы предприятию максимальный доход.

n=4, b1=20, b2=37, b3=30, a11=2, a12=2, a13=3, a14=0, a21=1, a22=1, a23=1, a24=2, a31=0, a32=1, a33=1, a34=4, c1=11, c2=6, c3=9, c4=6.

Решение:

Исходные данные сведём в таблицу:

Ресурсы	Расход ресурса на единицу продукции	Количество ресурсов
	П1	П2	П3	П4
Р1	2	2	3	0	20
Р2	1	1	1	2	37
Р3	0	1	1	4	30
Цена единицы продукции	11	6	9	6

Составим математическую модель задачи:

max F(X)=11х1+6х2+9х3+6х4

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

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных х5, х6, х7 (то есть приведем задачу к каноническому виду)

max F(X)=11х1+6х2+9х3+6х4+0?х5+0?х6+0?х7

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

Матрица коэффициентов А=(аij) этой системы уравнений имеет следующий вид:

Векторы A5, A6, A7 - линейно независимы, так как определитель, составленный из компонент этих векторов, отличен от нуля. Следовательно, соответствующие этим векторам переменные х5, х6, х7 являются базисными и в этой задаче определяют объемы неиспользованных ресурсов.

Решим систему уравнений относительно базисных переменных.

Функцию цели запишем в виде уравнения:

max F(X)=0-(-11х1-6х2-9х3-6х4)

Полагая, что свободные переменные х1=0, х2=0, х3=0, х4=0, получим первый опорный план Х1=(0, 0, 0, 0, 20, 37, 30), F(X1)=0, в котором базисные переменные х5=20, х6=37, х7=30. Следовательно, продукция не производится, доход равен нулю, а ресурсы не используются.

Полученный первый опорный план запишем в симплексную таблицу.

План	БП	ЗБП	х1	х2	х3	х4	х5	х6	х7	? - min (?0)
I	х5	20	2	2	3	0	1	0	0	10- min
	х6	37	1	1	1	2	0	1	0	37
	х7	30	0	1	1	4	0	0	1	-
	F(X1)	0	-11	-6	-9	-6	0	0	0	-
II	х1	10	1	1	1,5	0	0,5	0	0	-
	х6	27	0	0	-0,5	2	-0,5	1	0	13,5
	х7	30	0	1	1	4	0	0	1	7,5- min
	F(X2)	110	0	5	7,5	-6	5,5	0	0	-
III	х1	10	1	1	1,5	0	0,5	0	0	-
	х6	12	0	-0,5	-1	0	-0,5	1	-0,5	-
	х4	7,5	0	0,25	0,25	1	0	0	0,25	-
	F(X3)	155	0	6,5	9	0	5,5	0	1,5	-
-	-	Z(Y)	у4	у5	у6	у7	у1	у2	у3

Первый опорный план не оптимальный, так как в индексной строке находятся отрицательные коэффициенты:-11; -6; -9.

За ведущий столбец выберем столбец, соответствующий переменной х1, так как, сравнивая по модулю, имеем: |-11| >{|-6|, |-9|, |-6|}. Вычислим значения ?i по строкам как частное от деления и из них выберем наименьшее:

Следовательно, первая строка является ведущей.

Разрешающий элемент равен 2 и находится на пересечении ведущего столбца х1 и ведущей строки х5 и выделен в таблице.

Формируем следующую часть симплексной таблицы. Вместо переменной х5 плана I в план II войдет переменная х1. Строка, соответствующая переменной х1 в плане II, получена в результате деления всех элементов строки х5 плана I на разрешающий элемент РЭ=2. На месте разрешающего элемента в плане II получаем 1. В остальных клетках столбца х1 плана II записываем нули.

Таким образом, в новом плане II заполнены строка х1 (бывшая разрешающая) и столбец х1 (бывший разрешающий). Все остальные элементы нового плана II, включая элементы индексной строки, получены по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ=2. Во второй вершине по диагонали находится старое значение элемента СЭ. Третий и четвертый элементы А и В завершают построение прямоугольника в недостающих двух вершинах и расположены по другой диагонали. Значение нового элемента в плане II находится из выражения:



Заметим, что все элементы, расположенные на пересечении строк и столбцов, соответствующих одноименным базисным элементам, равны 1, остальные элементы столбца в базисах векторов, включая индексную строку, равны нулю.

Итак, план II сформирован, но он не оптимальный, так как в индексной строке находится отрицательный элемент -6.

Аналогично формируем план III, и он оптимальный, так как в индексной строке нет отрицательных элементов.

Оптимальный план можно записать так:

Х*=(10; 0; 0; 7,5;¦0; 12; 0);

F(X*)=155 - max.

Проверка (подстановка в каноническую систему):

Следовательно, необходимо выпускать продукции П1=10 единиц, П2=0 единиц (то есть не выпускать), П3=0 единиц (то есть не выпускать), П4=7,5 единиц. При этом предприятие получит максимальный доход в размере 155 ден. ед.

В оптимальном плане среди базисных переменных находится дополнительная переменная х6. Это указывает на то, что ресурсы второго вида недоиспользованы на 12 единиц, так как переменная х6 была введена во второе ограничение задачи. В индексной строке оптимального плана в столбцах переменных х2, х3, х5, х7 не вошедших в состав базисных, получены ненулевые элементы, поэтому оптимальный план задачи является единственным.

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

Второе ограничение неканонической задачи выполняется как строгое неравенство, то есть ресурс второго вида израсходован не полностью, остаток его в оптимальном плане х6*=12. Значит, ресурс второго вида не является дефицитным.

Составим экономико-математическую модель двойственной задачи:

Прямая задача	Двойственная задача
max F(X)=11х1+6х2+9х3+6х4	min Z(Y)=20y1+37y2+30y3

Выпишем соответствия между переменными прямой и двойственной задач:

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

Оптимальный план двойственной задачи можно записать так:

Y*=(5,5; 0; 1,5;¦0; 6,5; 9; 0);

Z(Y*)=155 - min.

Проверка (подстановка в каноническую систему):

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

Итак, увеличение первого ресурса на единицу приведёт к получению нового оптимального плана, в котором прибыль возрастает на 5,5 ден. ед. и станет равной 160,5 ден. ед.

Увеличение третьего ресурса на единицу приведёт к получению нового оптимального плана, в котором прибыль возрастает на 1,5 ден. ед. и станет равной 156,5 ден. ед.

Увеличение второго ресурса на единицу ни к чему не приведёт, ввиду его недифицитности.

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

При этом ненулевые оценки дополнительных переменных двойственной задачи, показывают, насколько будет снижать каждая изготовленная единица такой продукции достигнутый оптимальный уровень выручки. При выпуске единицы продукции второго вида прибыль предприятия снижается на 6,5 ден. ед., а при выпуске единицы продукции третьего вида прибыль предприятия снижается на 9 ден. ед.

Задача 3

Специализированный магазин "Пианино-рояли" реализует товары А и В. Продажа товаров ограничивается дефицитом некоторых видов торговых ресурсов:

Виды торговых ресурсов	Расход ресурсов на продажу партии товара	Объём ресурсов в секции
	А	В
Рабочее время продавцов, чел.-дн.	2	3	81
Площадь торгового зала, м2	5	4	116
Рабочее время подсобных рабочих, чел.-час.	1	2	40
Складская ёмкость, необходимая для хранения товара, м3	4	1	70
Прибыль от реализации одной партии товара, тыс. руб.	8	14

Требуется:

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

2. составить и решить двойственную задачу;

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

Решение:

Составим экономико-математическую модель задачи:

max F(X)=8х1+14х2

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

Для построения первого опорного плана систему неравенств приведем к системе уравнений путем введения дополнительных переменных х3, х4, х5 и х6 (то есть приведем задачу к каноническому виду):

max F(X)=8х1+14х2+0·х3+0?х4+0?х5+0?х6

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

Матрица коэффициентов А=(аij) этой системы уравнений имеет следующий вид:

Векторы A3, A4, A5, A6 - линейно независимы, так как определитель, составленный из компонент этих векторов, отличен от нуля. Следовательно, соответствующие этим векторам переменные х3, х4, х5, х6 являются базисными и в этой задаче определяют объемы неиспользованных ресурсов.

Решим систему уравнений относительно базисных переменных.

Функцию цели запишем в виде уравнения: max F(X)=0-(8х1+14х2)

Полагая, что свободные переменные х1=0, х2=0, получим первый опорный план Х1=(0, 0, 81, 116, 40, 70), F(X1)=0, в котором базисные переменные х3=81, х4=116, х5=40, х6=70. Следовательно, товары не продаются, прибыль равна нулю, а ресурсы не используются.

Полученный первый опорный план запишем в симплексную таблицу.

План	БП	ЗБП	х1	х2	х3	х4	х5	х6	? - min (?0)
I	х3	81	2	3	1	0	0	0	27
	х4	116	5	4	0	1	0	0	29
	х5	40	1	2	0	0	1	0	20-min
	х6	70	4	1	0	0	0	1	70
	F(X1)	0	-8	-14	0	0	0	0	-
II	х3	21	0,5	0	1	0	-1,5	0	42
	х4	36	3	0	0	1	-2	0	12-min
	х2	20	0,5	1	0	0	0,5	0	40
	х6	50	3,5	0	0	0	-0,5	1	14,29
	F(X2)	280	-1	0	0	0	7	0	-
III	х3	15	0	0	1	-1/6	-11/6	0	-
	х1	12	1	0	0	1/3	-2/3	0	-
	х2	14	0	1	0	-1/6	5/6	0	-
	х6	8	0	0	0	-11/6	15/6	1	-
	F(X3)	292	0	0	0	1/3	61/3	0	-
-	-	Z(Y)	y5	y6	y1	y2	y3	y4	-

Первый опорный план не оптимальный, так как в индексной строке находятся отрицательные коэффициенты:-8; -14.

За ведущий столбец выберем столбец, соответствующий переменной х2, так как, сравнивая по модулю, имеем: |-14| >|-8|. Вычислим значения ?i по строкам как частное от деления и из них выберем наименьшее:

Следовательно, третья строка является ведущей. Разрешающий элемент равен 2 и находится на пересечении ведущего столбца х2 и ведущей строки х5 и выделен в таблице.

Формируем следующую часть симплексной таблицы. Вместо переменной х5 в план II войдет переменная х2. Строка, соответствующая переменной х2 в плане II, получена в результате деления всех элементов строки х5 плана I на разрешающий элемент РЭ=2. На месте разрешающего элемента в плане II получаем 1. В остальных клетках столбца х2 плана II записываем нули.

Таким образом, в новом плане II заполнены строка х2 и столбец х2. Все остальные элементы нового плана II, включая элементы индексной строки, получены по правилу прямоугольника. Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ=2. Во второй вершине по диагонали находится старое значение элемента СЭ. Третий и четвертый элементы А и В завершают построение прямоугольника в недостающих двух вершинах и расположены по другой диагонали. Значение нового элемента в плане II находится из выражения:

Заметим, что все элементы, расположенные на пересечении строк и столбцов, соответствующих одноименным базисным элементам, равны 1, остальные элементы столбца в базисах векторов, включая индексную строку, равны нулю.

Итак, план II сформирован, но он не оптимальный, так как в индексной строке находится отрицательный элемент -2.

Аналогично формируем план III, и он оптимальный, так как в индексной строке нет отрицательных элементов.

Оптимальный план можно записать так:

Х*=(12; 14;¦15; 0; 0; 8) и F(X*)=292 - max.



Проверка (в каноническую систему):

max F(X)=8·12+14·14+0·0+0?0+0?1+0?10=96+196=292

Следовательно, необходимо продавать товара А 12 партий, В - 14 партий. При этом магазин получит максимальную прибыль в размере 292 тыс. руб.

В оптимальном плане среди базисных переменных находятся дополнительные переменные х3 и х6. Это указывает на то, что ресурсы первого и четвёртого видов недоиспользованы соответственно на 15 и 8 единиц, так как переменные х3 и х6 были введены в первое и четвёртое ограничения задачи. Иными словами, рабочее время продавцов недоиспользовано на 15 чел.-дн., а складская ёмкость, необходимая для хранения товара недоиспользована на 8 м3. В индексной строке оптимального плана в столбцах переменных х4, х5 не вошедших в состав базисных, получены ненулевые элементы, поэтому оптимальный план задачи является единственным.

Для неканонической задачи: второе и третье ограничения задачи выполняются как равенства. Это означает, что ресурсы второго и третьего видов полностью используются в оптимальном плане, являются дефицитными. Первое и четвёртое ограничения задачи выполняются как неравенства. Это означает, что ресурсы первого и четвёртого видов полностью не используются в оптимальном плане, и не являются дефицитными, остатки их в оптимальном плане х3*=15 и х6*=8.

Составим экономико-математическую модель двойственной задачи:

Прямая задача	Двойственная задача
max F(X)=8х1+14х2	min Z(Y)=81y1+116y2+40y3+70y4

Выпишем соответствия между переменными прямой и двойственной задач:

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

Оптимальный план двойственной задачи можно записать так:

Y*=(0; 1/3; 61/3 ; 0;¦0; 0) и Z(Y*)=292 - min.

Проверка (в каноническую систему):



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

Итак, увеличение второго ресурса на единицу, то есть площади торгового зала на 1 м³ приведёт к получению нового оптимального плана, в котором прибыль возрастает на 1/3=0,3333 тыс. руб. и станет равной 292,3333 тыс. руб.

Увеличение третьего ресурса на единицу, то есть рабочего времени подсобных рабочих на 1 чел.-час. приведёт к получению нового оптимального плана, в котором прибыль возрастает на 61/3=6,3333 тыс. руб. и станет равной 298,3333 тыс. руб.

Увеличение первого или четвёртого ресурса на единицу ни к чему не приведёт, ввиду их недифицитности.

Задача 4

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

	В1	В2	В3	В4	ai
A1	2	2	3	4	20
A2	4	5	4	7	30
A3	6	7	3	5	80
A4	3	5	7	4	30
bj	10	50	60	40

Решение:

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

?ai=20+30+80+30=160;

?bj=10+50+60+40=160

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

Занесем исходные данные в распределительную таблицу:

план I	В1	В2	В3	В4
	10	50	60	40
А1	2	2	3	4
20
А2	4	5	4	7
30
А3	6	7	3	5
80
А4	3	5	7	4
30

Метод "северо-западного угла". Будем распределять груз, начиная с загрузки левой верхней, условно называемой северо-западной, клетки А1В1, двигаясь затем от нее по строке вправо или по столбцу вниз. В клетку А1В1 занесем меньшее из чисел а1, b1, т.е. x11=min{а1, b1}.

Если а1>b1, то x11=b1 и первый потребитель В1 будет полностью удовлетворен. В дальнейшем первый столбец таблицы в расчет не принимается, то есть выходит из рассмотрения.

Двигаясь вправо по первой строке таблицы, заносим в соседнюю клетку А1В2 меньшее из чисел а1-b1, и b2, т.е. x12=min{а1-b1, b2}. Заполнив, таким образом клетку А1В2, переходим к загрузке следующей клетки по второй строке либо по второму столбцу. Процесс распределения по второй, третьей и последующим строкам (столбцам) производится аналогично распределению по первой строке или первому столбцу до тех пор, пока не исчерпаются ресурсы.

Последней заполняется клетка АmВn.

метод северо-западного угла	В1	В2	В3	В4
	10	50	60	40
А1	2	2	3	4
20	10	10	-	-
А2	4	5	4	7
30	-	30	-	-
А3	6	7	3	5
80	-	10	60	10
А4	3	5	7	4
30	-	-	-	30

Метод "минимального элемента" или метод наименьшей стоимости". Просматриваются тарифы из распределительной таблицы, и в первую очередь заполняется клетка с минимальным значением тарифа. При этом в клетку записывается максимально возможное значение поставки. Затем из рассмотрения исключают строку, соответствующую поставщику, запасы которого полностью израсходованы, или столбец, соответствующий потребителю, спрос которого полностью удовлетворен. После этого из оставшихся клеток таблицы снова выбирают клетку с наименьшим тарифом. Процесс распределения заканчивается, когда все запасы поставщиков исчерпаны, а спрос потребителей полностью удовлетворен. В результате получаем опорный план, который должен содержать m+n-1 загруженных клеток.

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

Так бывает, когда полностью исчерпывается запас груза и полностью удовлетворяется спрос (вырожденная задача). В этом случае в свободные клетки надо записать число 0 - "нуль-загрузку", условно считая такую клетку занятой. Однако число 0 записывается в те свободные клетки, которые не образуют циклов с ранее занятыми клетками.

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

метод наименьшей стоимости	В1	В2	В3	В4
	10	50	60	40
А1	2	2	3	4
20	10	10	-	-
А2	4	5	4	7
30	-	30	-	-
А3	6	7	3	5
80	-	10	60	10
А4	3	5	7	4
30	-	-	-	30

Среди тарифов из всей таблицы наименьшим является с11=2=с12=2, поэтому в клетку A1B1 направляем максимально возможный груз. Он равен min{20, 10}=10. Тогда х11=10 и из пункта А1 не вывезено 10 единиц груза, а потребность в грузе пункта В1 удовлетворена полностью. Таким образом, столбец В1 выходит из рассмотрения.

Далее аналогично, из оставшихся тарифов наименьшим является с12=2, поэтому в клетку A1B2 направляем максимально возможный груз. Он равен min{10, 50}=10. Тогда х12=10 и из пункта А1 вывезен груз полностью, а потребность пункта В2 не удовлетворена на 40 единиц груза. Таким образом, строка А1 выходит из рассмотрения.

Далее аналогично,

с33=3 - min х33= min{80, 60}=60;

с44=4 - min х44= min{30, 40}=30;

с22=5 - min х22= min{30, 40}=30;

с34=5 - min х34= min{20, 10}=10;

х32= min{10, 10}=10;

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

Определяем значение целевой функции первого опорного плана.

F(X1)=10•2+10•2+30•5+10•7+60•3+10•5+30•4=610

F(X1)=610 ден. ед.

Метод Фогеля. В распределительной таблице по строкам и столбцам определяется разность между двумя наименьшими тарифами. Отмечается наибольшая разность знаком . Далее в строке (столбце) с наибольшей разностью заполняется клетка с наименьшим тарифом. Строки (столбцы) с нулевым остатком груза в дальнейшем в расчет не принимаются. На каждом этапе загружается только одна клетка. Распределение груза производится, как и ранее.

метод Фогеля	В1	В2	В3	В4	I	II	III
	10	50	60	40
А1	2	2	3	4	0	-	-
20	-	20	-	-
А2	4	5	4	7	0	0	1
30	-	30	-	-
А3	6	7	3	5	2	2	1
80	-	-	60	20
А4	3	5	7	4	1	1	1
30	10	-	-	20
I	1	3	0	0
II	1	0	1	1
III	1	0	-	1

Проверим оптимальность опорного плана I, построенного методом наименьшей стоимости, методом потенциалов:

Подсчитаем число занятых клеток таблицы, их 7, как и должно быть



m+n-1=4+4-1=7.

Следовательно, опорный план I является невырожденным.

план I	В1	В2	В3	В4	потенциалы
	10	50	60	40	?i
А1	2	2	3	4	?1=0
20	10	10	-	-
А2	4	5	4	7	?2=3
30	-	30	-	-
А3	6	7	3	5	?3=5
80	-	10	60	10
А4	3	5	7	4	?4=4
30	-	-	-	30
?j	?1=2	?2=2	?3=-2	?4=0

Найдем потенциалы ?i, ?j по занятым клеткам таблицы, в которых ?i+?j=cij, полагая, что ?1=0, решим систему уравнений:

Занесем найденные значения потенциалов в таблицу и вычислим оценки свободных клеток по формуле:

?ij=cij-(?i+?j):

?13=3-(0-2)=5;

?14=4-(0+0)=4;

?21=4-(3+2)=-1;

?23=4-(3-2)=3;

?24=7-(3+0)=4;

?31=6-(5+2)=-1;

?41=3-(4+2)=-3;

?42=5-(4+2)=-1;

?43=7-(4-2)=5.

Первый опорный план I не является оптимальным, так как среди оценок свободных клеток есть отрицательные: ?21=-1; ?31=-1; ?41=-3 и ?42=-1, поэтому переходим к его улучшению. Выбираем наибольшую по модулю отрицательную оценку свободной клетки ?41=-3.

Для клетки А4В1 с отрицательной оценкой свободной клетки построим цикл перераспределения груза:

А4В1 - А4В4 - А3В4 - А3В2 - А1В2 - А1В1 - А4В1.

Для этого в перспективную клетку А4В1 поставим знак "+", а в остальных вершинах четырёхугольника чередующиеся знаки "-", "+", "-". Из чисел, стоящих в минусовых клетках, выбираем наименьшее, то есть ?1=min{10, 10, 30}=10. Прибавляем ?1=10 к объемам грузов, стоящих в плюсовых клетках, и вычитаем ?1=10 из объемов грузов, стоящих в минусовых клетках. В результате получен новый опорный план II.



Определяем значение целевой функции второго опорного плана.

F(X2)=20•2+30•5+60•3+20•5+10•3+20•4=580 (или F(X2)=F(X1)+?41· ?1=610-3·10=580)

F(X2)=580 ден. ед.

Проверим оптимальность опорного плана II методом потенциалов:

Подсчитаем число занятых клеток таблицы, их 6, а должно быть m+n-1=4+4-1=7. Следовательно, опорный план I является вырожденным. Поэтому, будем считать, например клетку А2В1 не пустой, а заполненной нулём.

Найдем потенциалы ?i, ?j по занятым клеткам таблицы, в которых ?i+?j=cij, полагая, что ?1=0, решим систему уравнений:

план II	В1	В2	В3	В4	потенциалы
	10	50	60	40	?i
А1	2	2	3	4	?1=0
20	-	20	-	-
А2	4	5	4	7	?2=3
30	0	30	-	-
А3	6	7	3	5	?3=3
80	-	-	60	20
А4	3	5	7	4	?4=2
30	10	-	-	20
?j	?1=1	?2=2	?3=0	?4=2



Занесем найденные значения потенциалов в таблицу и вычислим оценки свободных клеток по формуле:

?ij=cij-(?i+?j)

?11=2-(0+1)=1;

?13=3-(0+0)=3;

?14=4-(0+2)=2;

?23=4-(3+0)=1;

?24=7-(3+2)=2;

?31=6-(3+1)=2;

?32=7-(3+2)=2;

?42=5-(2+2)=1;

?43=7-(2+0)=5;

Второй опорный план II является оптимальным, так как среди оценок свободных клеток нет отрицательных.

Оптимальный план можно записать следующим образом:

F(X*)=580 ден. ед.

Анализ плана:

ь из пункта А1 необходимо 20 единиц груза направить в пункт В2;

ь из пункта А2 необходимо 30 единиц груза направить в пункт В2;

ь из пункта А3 необходимо 60 единиц груза направить в пункт В3 и 20 единиц груза направить в пункт В4;

ь из пункта А4 необходимо 10 единиц груза направить в пункт В1 и 20 единиц груза направить в пункт В4;

При этом суммарные затраты на перевозку грузов будут минимальными и составят 580 ден.ед.

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

Задача 5

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

Решение:

1. Рассмотрим платёжную матрицу:

	П1	П2	П3	П4	П5
А1	9	1	4	3	1	1
А2	5	3	1	2	1	1
А3	3	6	2	3	6	2
А4	1	2	7	5	8	1
А5	7	2	5	4	3	2
	9	6	7	5	8



Цена игры лежит в диапазоне 2???5

Найдём решение игры.

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

1. Критерий Вальде:

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

Критерий является пессимистическим, считается, что природа будет действовать наихудшим для человека образом.

Итак, целесообразно использовать стратегию А3 - р(0; 0; 1; 0; 0) или А5 - р(0; 0; 0; 0; 1)

2. Критерий максимума:

Рекомендуется применять максимаксную стратегию. Он достигается из условия: .

Критерий является оптимистическим, считается, что природа будет действовать наилучшим для человека образом.

	П1	П2	П3	П4	П5
А1	9	1	4	3	1	9
А2	5	3	1	2	1	5
А3	3	6	2	3	6	6
А4	1	2	7	5	8	8
А5	7	2	5	4	3	7

=max(9; 5; 6; 8; 7)=9.



Итак, целесообразно использовать стратегию А1 - р(1; 0; 0; 0; 0).

3. Критерий Гурвица:

Критерий придерживается некоторой промежуточной позиции, учитывающей возможность как наихудшего, так и наилучшего для человека поведения природы. Он достигается из условия: . На оказывает влияние степень ответственности лица, принимающего решение по выбору стратегии. Чем хуже последствия ошибочных решений, больше желания застраховаться, тем ближе к единице. При =1 критерий Гурвица превращается в критерий Вальде. При =0 критерий Гурвица превращается в критерий максимума. Для определённости примем степень оптимизма, например, =0,6,

	П1	П2	П3	П4	П5		0,6		0,4	hi
А1	9	1	4	3	1	1	0,6	9	3,6	4,2
А2	5	3	1	2	1	1	0,6	5	2	2,6
А3	3	6	2	3	6	2	1,2	6	2,4	3,6
А4	1	2	7	5	8	1	0,6	8	3,2	3,8
А5	7	2	5	4	3	2	1,2	7	2,8	4

Итак, целесообразно использовать стратегию А1 - р(1; 0; 0; 0; 0).

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

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



	П1	П2	П3	П4	П5
А1	9	1	4	3	1
А2	5	3	1	2	1
А3	3	6	2	3	6
А4	1	2	7	5	8
А5	7	2	5	4	3
	9	6	7	5	8

Составим матрицу рисков:

	П1	П2	П3	П4	П5
А1	0	5	3	2	7	7
А2	4	3	6	3	7	7
А3	6	0	5	2	2	6
А4	8	4	0	0	0	8
А5	2	4	2	1	5	5

Итак, целесообразно использовать стратегию А4 - р(0; 0; 0; 1; 0).

Если вероятности состояний природы известны:

5. Критерий Байеса:

а) Рекомендуется выбирать за оптимальную стратегию ту чистую стратегию, при которой максимизируется средний выигрыш. Он достигается из условия:

	П1	П2	П3	П4	П5	М(Аi)
А1	0,3	0,2	0,1	0,2	0,2	9·0,3+1·0,2+4·0,1+3·0,2+1·0,2=
	9	1	4	3	1	4,1
А2	0,4	0,1	0,2	0,2	0,1	5·0,4+3·0,1+1·0,2+2·0,2+1·0,1=
	5	3	1	2	1	3,0
А3	0,2	0,3	0,2	0,1	0,2	3·0,2+6·0,3+2·0,2+3·0,1+6·0,2=
	3	6	2	3	6	4,3
А4	0,1	0,1	0,2	0,2	0,4	9·0,1+1·0,1+4·0,2+3·0,2+1·0,4=
	1	2	7	5	8	5,9
А5	0,2	0,2	0,2	0,2	0,2	7·0,2+2·0,2+5·0,2+4·0,2+3·0,2=
	7	2	5	4	3	4,2

А затем определим максимальное значение этого показателя, которое и указывает на оптимальное решение:

maxМ(Аi)=М(А1)=5,9.

Итак, целесообразно использовать стратегию А4 - р(0; 0; 0; 1; 0).

б) Рекомендуется выбирать за оптимальную стратегию ту чистую стратегию, при которой минимизируется средний риск. Он достигается из условия:

	П1	П2	П3	П4	П5	М(Ri)
А1	0,3	0,2	0,1	0,2	0,2	0·0,3+5·0,2+3·0,1+2·0,2+7·0,2=
	9/0	1/5	4/3	3/2	1/7	3,1
А2	0,4	0,1	0,2	0,2	0,1	4·0,4+3·0,1+6·0,2+3·0,2+7·0,1=
	5/4	3/3	1/6	2/3	1/7	4,4
А3	0,2	0,3	0,2	0,1	0,2	6·0,2+0·0,3+5·0,2+2·0,1+2·0,2=
	3/6	6/0	2/5	3/2	6/2	2,8
А4	0,1	0,1	0,2	0,2	0,4	8·0,1+4·0,1+0·0,2+0·0,2+0·0,4=
	1/8	2/4	7/0	5/0	8/0	1,2
А5	0,2	0,2	0,2	0,2	0,2	2·0,2+4·0,2+2·0,2+1·0,2+5·0,2=
	7/2	2/4	5/2	4/1	3/5	2,8
	9	6	7	5	8



А затем определим минимальное значение этого показателя, которое и указывает на оптимальное решение:

minМ(Ri)=М(R4)=1,2.

Итак, целесообразно использовать стратегию А4 - р(0; 0; 0; 1; 0).

Аналогично, критерию Байеса, по Лапласу принимаем вероятности состояний природы равными между собой, то есть q1=q2=q3=q4=q5=0,2. Оптимальной по Лапласу является стратегия А4.

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