Обоснование эффективности предлагаемых мероприятий

Как известно, стимулирование сбыта содействует расширению продаж товара. Так, для предприятия ЗАО р НП «СОМЗ» разрабатываемая маркетинговая политика направлена на ряд мероприятий, способствующих продвижению продукции, как на внутреннем, так и на внешнем рынках. Одним из таких мероприятий является активная рекламная деятельность, организованная как собственными силами предприятия, так и сторонними рекламными организациями. В ходе рекламных мероприятий руководство предприятия ЗАО р НП «СОМЗ» должно четко контролировать расходы, т. е. распределение рекламного бюджета. Приведем пример с использованием метода линейного программирования, основанного на симплекс-методе, для решения задачи по оптимизации использования рекламного бюджета предприятия.

Предприятие осуществляет рекламу выпускаемой продукции двумя способами через радиосеть и через телевидение. Стоимость рекламы на радио обходится фирме в 5 у.е., а стоимость телерекламы — в 100 у.е. за минуту.

Предприятие готово тратить на рекламу по 1000 у.е. в месяц. Так же известно, что предприятие готово рекламировать свою продукцию по радио по крайней мере в 2 раза чаще, чем по телевидению .

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

Задача заключается в правильном распределении финансовых средств предприятия.

Математическое описание задачи:

X1 — время потраченное на радиорекламу;

Х2 — время потраченное на телерекламу;

Z — целевая функция, отражающая максимальный сбыт от 2-ух видов рекламы.

Х1=>0, Х2=>0, Z=>0 ;

Max Z = XI+25X2;

5X1 + 100X2 <=1000;

XI -2X2 => О Использование графического способа удобно только при решении задач ЛП с двумя переменными. При большем числе переменных необходимо применение алгебраического аппарата. В данной главе рассматривается общий метод решения задач ЛП, называемый симплекс-методом .

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

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

Все ограничения записываются в виде равенств с неотрицательной правой частью ;

Значения всех переменных модели неотрицательны;

Целевая функция подлежит максимизации или минимизации.

Покажем, каким образом любую линейную модель можно привести к стандартной.

Ограничения:

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

Например, в левую часть исходного ограничения 5X1 + 100X2 <= 1000.

вводится остаточная переменная S1 > 0, в результате чего исходное неравенство обращается в равенство:

5X1 + 100X2 + 81 = 1000, S1 => 0.

Если исходное ограничение определяет расход некоторого ресурса, переменную S1 следует интерпретировать как остаток, или неиспользованную часть, данного ресурса .

Рассмотрим исходное ограничение другого типа:

XI — 2X2 => 0.

Так как левая часть этого ограничения не может быть меньше правой, для обращения исходного неравенства в равенство вычтем из его левой части избыточную переменную S2 > 0. В результате получим:

XI — 2X2 — S2 = 0, S2 => 0.

2. Правую часть равенства всегда можно сделать неотрицательной, умножая обе части на -1 .

Например: равенство XI — 2X2 — S2 = 0 эквивалентно равенству.

• -XI + 2X2 + S2 = 0
• 3. Знак неравенства изменяется на противоположный при умножении обеих частей на -1 .

Например можно вместо 2 — 4, неравенство.

XI — 2X2 0.

Целевая функция линейной оптимизационной модели, представлена в стандартной форме, может подлежать как максимизации, так и минимизации. В некоторых случаях оказывается полезным изменить исходную целевую функцию .

Максимизация некоторой функции эквивалентна минимизации той же функции, взятой с противоположным знаком, и наоборот. Например максимизация функции Z = XI +25X2.

эквивалентна минимизации функции (-Z) = -XI — 25X2.

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

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

Максимизировать.

Z = X1 + 25X2+ 0S1+0S2.

При ограничениях.

• 5X1 + 100X2+ S1 = 1000
• -XI + 2X2 +S2−0

Х1=>0, Х2=>0, Sl=>0, S2=>0.

Симплекс-алгоритм состоит из следующих шагов:

Шаг 0. Используя линейную модель стандартной формы, определяют начальное допустимое базисное решение путем приравнивания к нулю п — т (небазисных) переменных.

Шаг 1. Из числа текущих небазисных (равных нулю) переменных выбирается включаемая в новый базис переменная, увеличение которой обеспечивает улучшение значения целевой функции. Если такой переменной нет, вычисления прекращаются, так как текущее базисное решение оптимально. В противном случае осуществляется переход к шагу 2.

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

Шаг 3. Находится новое базисное решение, соответствующее новым составам небазисных и базисных переменных. Осуществляется переход к шагу 1. Поясним процедуры симплекс-метода на примере решения нашей задачи.

Сначала необходимо представить целевую функцию и ограничения модели в стандартной форме:

ZXI — 25Х2+08,-08₂= 0 (Целевая функция).

• 5X1 + 100X2+ S1=1000 (Ограничение)
• -XI + 2X2+ S2 = 0 (Ограничение)

В качестве начального пробного решения используется решение систем уравнений, в которой две переменные принимаются равными нулю. Это обеспечивает единственность и допустимость получаемого решения. В рассматриваемом случае очевидно, что подстановка XI = Х2 = 0 сразу же приводит к следующему результату: S1 = 1000, S2 = 0. Преобразовав уравнение целевой функции так, чтобы его правая часть стала равной нулю, можно убедиться в том, что правые части уравнений целевой функции и ограничений полностью характеризуют начальное решение. Это имеет место во всех случаях, когда начальный базис состоит из остаточных переменных. Полученные результаты представлены в симплекс-таблице 4.10.

Таблица 4.10

Симплекс таблица полученных результатов.

Определим, является ли полученное пробное решение наилучшим (оптимальным). Анализируя Z — уравнение, нетрудно заметить, что обе небазисные переменные XI и Х2, равные нулю, имеют отрицательные коэффициенты. Всегда выбирается переменная с большим абсолютным значением отрицательного коэффициента (в Z — уравнение), так как практический опыт вычислений показывает, что в этом случае оптимум достигается быстрее.

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

Новое уравнение = Предыдущее уравнение — [Коэффициент].

[ ведущего столбца]? (Новая ведущая строка).

[предыдущего уравнения].

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

Применяя к исходной таблице процедуру 1, мы делим S2 — уравнение на ведущий элемент, равный 1 .

Чтобы составить новую симплекс-таблицу, выполним необходимые вычислительные процедуры типа 2.

1. Новое Z — уравнение .

старое Z — уравнение: (1 -1 -25 0 0 0).

• (-(-25)? (0 -½ 1 0 ½ 0)
• (1 -13.5 0 0 12.5 0)
• 2. Новое S1 — уравнение

старое S₁-уравнение: (0 5 100 1 0 1000).

• (-100)?(0 -½ 1 О ½ 0)
• (0 55 0 1 -50 1000)

Новая симплекс-таблица будет иметь вид, табл. 4.11.

Таблица 4.11

Симплекс — таблица базисная.

В новом решении X1 = 0 и S2= 0. Значение Z не изменяется.

Заметим, что новая симплекс-таблица обладает такими же характеристиками, как и предыдущая: только небазисные переменные X) и S₂ равны нулю, а значения базисных переменных, как и раньше, представлены в столбце «Решение». Это в точности соответствует результатам, получаемым при использовании метода Гаусса—Жордана.

Из последней таблицы следует, что на очередной итерации в соответствии с условием оптимальности в качестве вводимой переменной следует выбрать X1, так как коэффициент при этой переменной в Z-уравнении равен -13.5. Исходя из условия допустимости, определяем, что исключаемой переменной будет S1. Отношения, фигурирующие в правой части таблицы, показывают, что в новом базисном решении значение включаемой переменной X1 будет равно ¹⁰⁰⁰/55 (- минимальному отношению). Это приводит к увеличению целевой функции на (¹⁰⁰⁰/₅₅)? (-13^1/₂) = (245⁵/₁₁).

К получению симплекс-таблицы, соответствующей новой итерации, приводят следующие вычислительные операции метода Гаусса—Жордана.

1) Новое ведущее S1- уравнение = Предыдущее S1 — уравнение / (55).

• 2) Новое Z — уравнение = Предыдущее Z — уравнение — (-13¹/₂)? Новое / ведущее уравнение:
  • (1 -13¹/₂ 0 0 12¹/₂ 0)
  • -(-13¹/₂)?(0 10 ¹/₅₅ —⁵⁰/₅₅ ¹⁰⁰⁰/₅₅)
  • (1 0 0 ²⁷/₁₁₀ ⁵/₂₂ 245⁵/₁₁)
• 3) Новое Х₂ — уравнение = Предыдущее Х₂ — уравнение — (-¹/₂)? Новое ведущее уравнение:
  • (0 —¹/₂ 1 0 ¹/₂ 0)
  • — (- ¹/₂)? (0 1 0 ¹/₅₅ —⁵⁰/₅₅ ¹⁰⁰⁰/₅₅)
  • (0 0 1 ¹/₁₁₀ ¹/₂₂ 9¹/₁₁)

В результате указанных преобразований получим следующую симплекс-таблицу (таб. 4.12).

Таблица 4.12

Симплекс — таблица преобразованная.

В новом базисном решении X1=¹⁰⁰⁰/₅₅ и X2=9¹/₁₁. Значение Z увеличилось с 0 (предыдущая симплекс-таблица) до 245⁵/₁₁ (последняя симплекс-таблица).

Этот результирующий прирост целевой функции обусловлен увеличением X1 от 0 до ¹⁰⁰⁰/55, так как из Z — строки предыдущей симплекс-таблицы следует, что возрастанию данной переменной на единицу соответствует увеличение целевой функции на (-13 ¹/₂).

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

С точки зрения практического использования результатов решения задач ЛП классификация переменных, предусматривающая их разделение на базисные и небазисные, не имеет значения и при анализе данных, характеризующих оптимальное решение, может не учитываться. Переменные, отсутствующие в столбце «Базисные переменные», обязательно имеют нулевое значение. Значения остальных переменных приводятся в столбце «Решение». При интерпретации результатов оптимизации в нашей задаче нас прежде всего интересует количество времени, которое закажет наша фирма на радио и телевидение, т. е. значения управляемых переменных X1 и Х2. Используя данные, содержащиеся в симплекс-таблице для оптимального решения, основные результаты можно представить в следующем виде (табл. 4.13):

Таблица 4.13

Оптимальное решение.

Заметим, что Z = X1 + 25Х2 = 1000/55 + 25? 91/11 = 2455/11. Это решение соответствует данным заключительной симплекс-таблицы.

А следовательно, для завода необходимо рекламировать в месяц продукцию по телевидению 18,2 мин., а по радио 0,82 мин. Данное отношение является оптимальным, так как позволит извлечь максимальную прибыль в размере 111,4 у.е. от рекламируемых изделий.