111. Модели оптимизации в анализе экономических показателей

1934 г. – Канторович Леонид Витальевич предложил модель оптимизации

Z = (z₁*x₁+z₂*x₂+….+z_nx_n) max

прод. 1 прод.2

при a₁₁*x₁ + a₁₂*x₂ +…+ a_1n*x_n ≤ b₁ - по 1-ому ресурсу

a ₂₁*x₁ + a₂₂*x₂ + …+a_2n*x_n ≤ b₂ - по 2-ому ресурсу

…

a _m1*x₁ + a_m2*x₂ +…+ a_mn*x_n ≤ b_m

x_j ≥0 , j=

Данциг и Симплекс разработали симплекс-метод.

Задача: торговая фирма реализует четыре вида продукции. Выделены три вида ресурсов для выполнения торговых операций. Заданы нормативы затрат этих ресурсов на единицу товарооборота и объёмы ресурсов, а также ожидаемая прибыль на прогнозируемый период. Требуется определить прогноз деятельности фирмы на указанный период с целью получения фирмой максимальной прибыли, а также определить стратегии фирмы в использовании имеющихся ресурсов разной квалификации

Ресурсы	Нормативы затрат ресурсов на единицу товара				Объём
	Товар 1	Товар 2	Товар 3	Товар 4
Низкоквалиф.труд, чел.-мин.	10	5	5	1	50 000
Высококвалиф.труд, чел.-мин.	6	6	2	2	36 000
Площадь торг.залов, дм2	4,5	18	1,5	6	81 000
Ожидаемая прибыль, руб.	0,8	0,9	1	0,7

1. Составляем модель оптимизации

Введем следующие обозначения: i – порядковый номер (индекс) строки (вида ресурса) (от 1 до 3)

j - порядковый номер (индекс) столбца (товара) (от 1 до 4)

x_j - искомый объём продаж

Модель задачи состоит из трёх частей (целевая функция, условия, неотрицательность переменных) и имеет следующий вид:

1. Максимизация прибыли от продажи четырех товаров

Z = (0,8х₁+0,9*x₂+ x₃ + 0,7x₄) max

2. При выполнении следующих условий

10x₁ + 5x₂ + 5x₃ + x₄ ≤ 50 000

6x₁ + 6x₂ + 2x₃ + 2x₄ ≤ 36 000

4,5x₁ + 18x₂ + 1,5x₃ + 6x₄ ≤ 81 000

3. x_j ≥ 0 ( j от 1 до 4)

2. Приводим модель к каноническому виду: все неравенства заменяем на равенства посредством ввода в модель дополнительных переменных.

x₁ - x₄– действительные переменные

10x₁ + 5x₂ + 5x₃ + x₄ + x₅ = 50 000

6x₁ + 6x₂ + 2x₃ + 2x₄ + x₆ = 36 000

4,5x₁ + 18x₂ + 1,5x₃ + 6x₄ + x₇ = 81 000

3. Строим исходную симплекс – таблицу для решения задачи

	V	x1	x2	x3	x4	x5	x6	x7
x5	50 000	10	5	5	1	1	0	0
x6	36 000	6	6	2	2	0	1	0
x7	81 000	4,5	18	1,5	6	0	0	0
z	0	-0,8	-0,9	-1	-0,7	0	0	0

По законам математики в исходной таблице все числа в целевой строке записываются с отрицательным знаком.

Алгоритм решения задач симплекс-методом

Находят допустимые решения, которые посредством последующих пересчетов таблицы доводят до оптимальных.

Допустимыми называют решения, удовлетворяющие условиям 2) и 3), оптимальными – удовлетворяющие всем трем условиям модели.

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

При решении сначала определяют вспомогательную информацию:

- разрешающий столбец - по наибольшей абсолютной величине отрицательного числа, стоящего в целевой строке таблицы (в нашем примере это -1)

- разрешающая строка – по наименьшему частному от деления свободного коэффициента (объема ресурса) на соответствующий элемент разрешающего столбца. В нашем примере – это первая строка.

- разрешающий элемент – на пересечении разрешающих столбца и строки (в нашем случае это 5)

Разрешающий столбец показывает, какие переменные поменяются местами в названии строки и столбца в новой симплекс-таблице.

Числа в новой симплекс-таблице на месте бывшей разрешающей строки находим путем деления каждого числа разрешающей строки исходной симплекс-таблицы на разрешающий элемент. Остальные числа на месте бывшего разрешающего столбца будут «0».

	V	x1	x2	x5	x4	x5	x6	x7
x3	10 000	2	1	1	0,2	0,2	0	0
x6				0
x7				0
z				0

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

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

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

ПРИМЕР: Рассчитаем число, которое должно стоять в клетке

5 0 000	10	5	5
клетка	6	6	2

Число в рассчитываемой клетке =

В результате получаем новую симплекс-таблицу:

	V	x1	x2	x5	x4	x5	x6	x7
x3	10 000	2	1	1	0,2	0,2	0	0
x6	16 000	2	4	0	1,6	-0,4	1	0
x7	66 000	1,5	16,5	0	5,7	-0,3	0	1
z	10 000	1,2	0,1	0	-0,5	0,2	0	0

Критерий оптимальности – отсутствие отрицательных элементов в целевой строке.

Решения читаются в базисе (два левых столбца) и в целевой строке.

Анализ полученного решения

1. Решение не оптимально

2. Согласно полученному решению фирма продает только 3-ий товар в количестве 10 000. Если в базис вошла действительная переменная, это значит, что во 2-ом столбце стоит её величина, а также, что соответствующий этой строке ресурс израсходован полностью (в нашем случае – низкоквалифицированный труд). Если в базисе остались дополнительные переменные, то во 2-ом столбце стоит величина недоиспользованного соответствующего ресурса (16000 неспользованных единиц высококвалифицированного труда и 66000 единиц площади торговых залов).

3. Полученная прибыль - 10000

Поскольку решение не оптимально, строим новую таблицу

	V	x1	x2	x5	x6	x5	x6	x7
x3	8 000	1,75	0,5	1	0	0,25	-0,12	0
x4	10 000	1,25	2,5	0	1	-0,25	0,63	0
x7	9 000	5,73	2,25	0	0	1,125	3,5	1
z	15 000	1,8	1,35	0	0	0,075	0,312	0

Оценки 1 рес. 2 рес. 3 рес.

Экономико-математический анализ решения

1) решение оптимально

2) фирма должна продавать товар 3 в объёме 8000 единиц и товар 4 в объёме 10000 единиц

3) ресурсы 1 и 2 израсходованы полностью, а 3-ий остался в объёме 9000

4) фирма получит прибыль 15000

ПРОВЕРКА: 50000 - 5 * 8000 – 1 * 10000 = 0, т.е. 1ый ресурс израсходован полностью

36000 - 2 * 8000 – 2 * 10000 = 0, т.е. 1ый ресурс израсходован полностью

81000 – 1,5 * 8000 – 6 * 10000 = 9000, т.е. осталось 9000 ед.3-его ресурса

5) Число 1,8 в целевой строке показывает, что если будет продана 1 ед. 1-ого товара, то функционал (максимальная прибыль) задачи уменьшится на 1,8 рубля. Соответственно, если будет продана 1 ед. 2-ого товара, то прибыль уменьшится на 1,35 рубля.

6) Числа в столбцах Х5, Х6: «0» - от дополнительных переменных прибыли не будет

7) Последние три цифры в целевой строке имеют особый экономический смысл. Их называют оценки ресурсов, двойственные оценки, оценки Канторовича.

Оценки ресурсов имеют несколько свойств:

1. оценка ресурса – мера дефицитности ресурса. Если она = 0, то соответствующий ресурс недефицитен, если не = 0, то ресурс дефицитен. Как правило, чем > величина оценки, тем острее дефицитность ресурса.

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

Напишем к исходной модели двойственную:

1. Если в исходной функционал стремился к максимуму, то в двойственной – наоборот, к минимуму

2. Знаки ≤ меняются на ≥

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

Z = (50 000 * у₁ + 36 000 * у₂ + 81 000 * у₃) min

Критерий (не)выгодности продажи товара

10y₁ + 6y₂ + 4,5y₃ ≥ 0.8

5y₁ + 6y₂ + 1,8y₃ ≥ 0.9

5y₁ + 2y₂ + 1,5y₃ ≥ 1

y₁ + 2y₂ + 6y₃ ≥ 0.7

Для 3-его и 4-ого товара в первых двух строках получится равенство. Для 1-ого и 2-ого товара равенства не будет!