МЕТОДЫ ОПТИМИЗАЦИИ

В чем заключается работа управленца? Если очень кратко, то создать такие условия, чтобы организация, в которой трудится управленец, получила максимум прибыли, рентабельности, производительности труда, минимум издержек, себестоимости, затрат и т. д. То есть имеется некоторый итоговый показатель, для которого нужно добиться максимального или минимального (оптимального) значения. Математические методы решения подобных задач называются методами оптимизации. Рассмотрим некоторые из них.

Методы оптимального программирования

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

Функцию, экстремальное значение которой нужно найти в условиях экономических возможностей, называют целевой, показателем эффективности или критерием оптимальности. Экономические возможности формализуются в виде системы ограничений. Все это составляет математическую модель. Математическая модель задачи — это отражение оригинала в виде функций, уравнений, неравенств, цифр и т. д. Модель задачи математического программирования включает:

• 1) совокупность неизвестных величин, действуя на которые, систему можно совершенствовать. Их называют планом задачи (вектором управления, решением, управлением, стратегией, поведением и др.);
• 2) целевую функцию (функцию цели, показатель эффективности, критерий оптимальности, функционал задачи и др.). Целевая функция позволяет выбрать наилучший из множества возможных вариантов. Наилучший вариант доставляет целевой функции экстремальное значение. Это могут быть: прибыль, объем выпуска или реализации, затраты производства, издержки обращения, уровень обслуживания или дефицитности, число комплектов, отходы ит. д.

Эти условия следуют из ограниченности ресурсов, которыми располагает общество в любой момент времени, из необходимости удовлетворения насущных потребностей, из условий производственных и технологических процессов. Ограниченными являются не только материальные, финансовые и трудовые ресурсы. Таковыми могут быть возможности технического, технологического и вообще научного потенциала. Нередко потребности превышают возможности их удовлетворения. Математически ограничения выражаются в виде уравнений и неравенств. Их совокупность образует область допустимых решений (область экономических возможностей). План, удовлетворяющий системе ограничений задачи, называется допустимым. Допустимый план, доставляющий функции цели экстремальное значение, называется оптимальным. Оптимальное решение, вообще говоря, не обязательно единственно, возможны случаи, когда оно не существует, имеется конечное или бесчисленное множество оптимальных решений. Линейное программирование — раздел оптимального программирования, применяемый при разработке методов отыскания экстремума линейных функций нескольких переменных при линейных дополнительных ограничениях, налагаемых на переменные.

Задачи оптимального и в том числе линейного программирования решаются в EXCEL с помощью специальной надстройки «Поиск решения» («Solver Add - in¹»). Рассмотрим решение таких задач на примерах. Сначала рассмотрим общую методику решения оптимизационных задач на ЭВМ, а затем перейдем к конкретным экономическим задачам.

ПРИМЕР 2.1.1. Решить на ЭВМ задачу линейного программирования, которая имеет вид

2х_х + 3х₂ -х₃ —> шах;

ЗХ] + х₂ — х₃ < 17;

<2х, + 4х₉ + х₃ < 15;

Зх₉ —4х₃ > 5;

Xj _{2 3} > 0; X] —целое .

РЕШЕНИЕ. Предварительно необходимо в электронной таблице подготовить исходные данные. Для этого, запустив MS Excel, выделим первую строчку под переменные. В ячейке А1 введем подпись «Переменные» и назначим под переменные х,,х₂,х₃ ячейки Bl, С1 и D1. Введем в эти ячейки любые произвольные числа, например единицы. Во второй строке определим целевую функцию. В ячейке А2 введем подпись «Целевая» и в соседней В2 введем формулу, зависящую от переменных «=2*B1+3*C1-D1» (для ввода ссылок на ячейку достаточно щелкнуть мышью по ней, кавычки не вводить). Нажав Enter, получим результат 4. В третью строку вводим левые части основной системы ограничений. В АЗ вводим подпись «Ограничения» и в ВЗ ставим курсор и вводим в виде формулы левую часть ограничения Зх, +х₂ -х₃ < 17 : «=3*B1+C1-D1». Аналогично в ячейки СЗ и D3 вводим левые части других ограничений соответственно: «=2*B1+4*C1+D1» и «=3*C1-4*D1». Подготовительный этап закончен.

Вызываем надстройку ПОИСК РЕШЕНИЯ (Solver Add - in). При работе в «EXCEL 2003» или ранней версии заходим в меню СЕРВИС, выбираем НАДСТРОЙКИ и проверяем наличие флажка напротив «Поиск решения», ¹ Здесь и далее названия элементов программы приведены и на английском языке.

«ОК», заходим вновь в меню СЕРВИС, выбираем ПОИСК РЕШЕНИЯ. При работе в «EXCEL 2007» или более поздней версии нажимаем левой кнопкой мыши по круглой кнопке “Office” в верхнем левом углу экрана или заходим в меню «Файл» (для версии 2010 и выше), внизу выбираем «Параметры Excel», слева выбираем НАДСТРОЙКИ, нажимаем кнопку «Перейти» внизу окна и в открывшемся окне проверяем наличие флажка напротив «Поиск решения», «ОК». В меню ДАННЫЕ выбираем ПОИСК РЕШЕНИЯ.

Откроется окно поиска решения. В нем ставим окно в поле «Установить целевую» (Set Target Cell) и далее щелкаем мышью по ячейке В2 с целевой функцией. В окне появится $В$2. Далее проверяем, что флажок ниже поля стоит напротив надписи «Равной максимальному значению» (Equal to ... Max ... Value of: ). После ставим курсор в поле «Изменяя ячейки» (By Changing Cell) и обводим ячейки с переменными Bl, С1 и D1. В поле появится $B$1:$D$1. В нижней части окна находится поле «Ограничения» (Subject to the Constraints). Для того чтобы ввести ограничения, нажимаем кнопку «Добавить» (Add), откроется окно «Добавление ограничения» (Add Constraints). В левом поле «Ссылка на ячейку» (Cell Reference) вводим ссылку на левую часть первого ограничения — ячейку ВЗ, в центральном окне определяем знак < и в правом «Ограничения» (Constraints) набираем правую часть ограничения — число 17. Нажимаем «ОК», видим, что ограничение появилось в окне. Нажимаем вновь «Добавить» (Add), вводим «СЗ» «<« и «15». Вновь нажимаем «Добавить» (Add), вводим «D3» «>« и «5». Для ввода дополнительных ограничений х_{{ 2 3} > 0; х, — целое Вновь нажимаем «Добавить» (Add), ставим курсор в левое поле и обводим ячейки Bl, С1 и D1 (результат $B$1:$D$1), в среднем окне ставим «>» и в правом число 0. Снова «Добавить» (Add), в левое поле вводим В1, а в центральном выбираем «цел.» (int.). В правом окне появится «целое» (integer). Все ограничения введены. Для запуска вычислений нажимаем кнопку «Выполнить» (Solve). Появляется надпись, что решение найдено (Solver Found a Solution). Выбираем «Сохранить найденное решение» (Keep Solver Solution) и «ОК», получаем результат: в ячейках Bl, С1 и D1 видны значения переменных х₁₅х₂,х₃, соответствующие оптимальному решению: 4; 1,75 и 0.

В ячейке В2 — значение целевой функции: 13,25.

ПРИМЕР 2.1.2. Найти максимум функции Z = Зх^-4х₂+Зх₃ при ограничениях:

4х_} +3х₂ +2х₃ <8;

х₁₂₃-целые.

РЕШЕНИЕ. Вводим на отдельном листе в ячейки от А1 до С1 произвольные значения, например единицы. В ячейку А2 вводим целевую функцию

«=3*А1*А1-4*В1+3*С1*С1*С1» (кавычки не вводить), в ячейку АЗ вводим левую часть основного ограничения «=4*А1+3*В1+2*С1». Вызываем, как в предыдущем примере, «Поиск решения (Solver...)». Ссылка на целевую ячейку (Set Target Cell) — А2, стремится к максимуму. Изменяемые ячейки (By Changing Cell)— А1-С1. Ограничения (Subject to the Constraints): $A$3<8; $A$l:$C$l>0; $A$1:$C$1 — целое (int). Запуская надстройку, получаем оптимальное решение: х* =0; =0; х^ =4. Целевая функция при этом равна

Z* =192.

ПРИМЕР 2.1.3. Рассмотрим решение ЗАДАЧИ ОПРЕДЕЛЕНИЯ ОПТИМАЛЬНОГО АССОРТИМЕНТА ПРОДУКЦИИ.

Фирма производит и продает два типа товаров. Фирма получает прибыль в размере 12 тыс. р. от производства и продажи каждой единицы товара 1 и в размере 4 тыс. р. от производства и продажи каждой единицы товара 2. Фирма состоит из трех подразделений. Затраты труда (чел.-дни) на производство этих товаров в каждом из подразделений указаны в табл. 2.1.1.

Таблица 2.1.1

Руководство рассчитало, что в следующем месяце фирма будет располагать следующими возможностями обеспечения производства трудозатратами: 800 чел.-дней в подразделении 1; 600 — в подразделении 2 и 2000 — в подразделении 3. Сколько единиц товара 1 и товара 2 нужно выпустить, чтобы суммарная полученная прибыль была максимальна?

РЕШЕНИЕ. Для решения задачи составляем математическую модель. Пусть х, — количество товара 1, х₂ — количество товара 2. Целевая функция и ограничения имеют вид

12х, + 4х₂ —>тах;

x_t +2х₂ <800;

< x_t + Зх₂ < 600;

2x_t + Зх₂ <2000 ;

х! ₂ > 0; х j ₂ - целое .

Вводим на новом листе в А1 слово «Переменные», в В1 и С1 вводим единицы, в А2 слово «Целевая», в В2 «=12*В1+4*С1», в АЗ слово «Ограничения», в ВЗ «=В1+2*С1», в СЗ «=В1+3*С1», в D3 «=2*В1+3*С1». Вызываем «Поиск решения (Solver...)». В поле «Установить целевую» (Set Target Cell) делаем ссылку на В2. Далее нужно проверить, что флажок ниже поля стоит напротив надписи «Равной максимальному значению» (Equal to ... Max ... Value of:). После ставим курсор в поле «Изменяя ячейки» (By Changing Cell) и обводим ячейки с переменными В1 и С1. В нижней части окна находится поле «Ограничения» (Subject to the Constraints). Для того чтобы ввести ограничения, нажимаем кнопку «Добавить» (Add), откроется окно «Добавление ограничения» (Add Constraints). В левом поле «Ссылка на ячейку» (Cell Reference) вводим ссылку на левую часть первого ограничения — ячейку ВЗ, в центральном окне определяем знак < и в правом «Ограничения» (Constraints) набираем правую часть ограничения — число 800. Нажимаем «ОК», видим, что ограничение появилось в окне. Нажимаем вновь «Добавить» (Add), вводим «СЗ» «<« и «600». Вновь нажимаем «Добавить» (Add), вводим «D3» «<« и «2000». Для ввода дополнительных ограничений х₁₂ >0; х₁₂ — целое вновь нажимаем «Добавить» (Add), ставим курсор в левое поле и обводим ячейки В1 и С1, в среднем окне ставим «>« и в правом число 0. Снова «Добавить» (Add), в левом поле обводим В1 и С1, а в центральном выбираем «цел.» (int.). В правом окне появится «целое» (integer). Все ограничения введены. Для запуска вычислений нажимаем кнопку «Выполнить» (Solve). Появляется надпись, что решение найдено (Solver Found a Solution). Выбираем «Сохранить найденное решение» (Keep Solver Solution) и «ОК», видим результат: в ячейках Bl, С1 приведены значения переменных x_t,x₂, соответствующие оптимальному решению: 600 и 0. В ячейки В2 — значение целевой функции: 7200. Следовательно, оптимально выпускать товар 1 в количестве 600 единиц, а товар 2 не выпускать. Ожидается прибыль 7200 тыс. р.

ПРИМЕР 2.1.4. ТРАНСПОРТНАЯ ЗАДАЧА.

Приведем решение транспортной задачи. Компания «Стройгранит» производит добычу строительной щебенки и имеет на территории региона три карьера. Запасы щебенки на карьерах соответственно равны 800, 900 и 600 тыс. тонн. Четыре строительные организации, проводящие строительные работы на разных объектах этого же региона, дали заказ на поставку соответственно 300, 600, 650 и 500 тыс. тонн щебенки. Стоимость перевозки 1 тыс. тонн щебенки с каждого карьера на каждый объект приведены в табл. 2.1.2.

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

Таблица 2.1.2

РЕШЕНИЕ. Данная транспортная задача является открытой, так как запасы поставщиков 800 + 900 + 600 = 2300 больше спроса потребителей

300 + 600 + 650 + 500 = 2050. Математическая модель ЗЛП в данном случае имеет вид

Ху; i = 1,2,3; j = 1,2,3,4 — количество щебенки, перевозимой с /-го карьера на j-u объект. Тогда целевая функция равна

8х_и +4х₁₂ +х₁₃ +7х₁₄ + Зх₂₁ + 2х₂₂ +7х₂₃ + Зх₂₄ +

+ 13х₃₁ +5х₃₂ +11х₃₃ + 8х₃₄ -^-min .

Ограничения имеют вид

Хи + х₁₂ + х₁₃ +х₁₄ <800;

х₂₁ +х₂₂ +х₂₃ +х₂₄ < 900;

х₃₁ ^+хз2 ^{+ х}зз +^х 34 —600;

<х_и + х₂₁ + х₃₁ =300;

^Х12 ^+Х22 ^+Х32 ⁼ 600 ;

^х1з ^+х2з + ^хзз =650;

х ] 4 4- х ₂₄ + х ₃₄ = 500 ,

>0.

Решение проводится по аналогии с предыдущими примерами. Следует отметить, что в задаче число переменных, для которых проводится решение, равно 3 х 4 = 12, поэтому для исключения ошибок ввода данных стоит ввести переменные х₍₇ не в строку, а в прямоугольную таблицу из 3-х строк и 4-х столбцов, а затем при вводе ограничений использовать строки и столбцы этой таблицы.

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

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

Пусть a,j — прибыль, полученная инвестором от j-ro проекта при условии, что в него было вложено i финансовых пакетов (z = 0, 1, ..., т j = 1,2, ... , к). Назовем А = а,;матрицей прибылей, причем ее элементы не обязательно должны быть целыми. Очевидно, что aoj = 0. Необходимо так распределить финансовые пакеты по проектам, чтобы суммарная прибыль (равная сумме прибылей от каждого проекта) была максимальна.

Введем переменные:

[1, если в j - й проект вложено не менее i финансовых пакетов;

^ха ~ 1

[0, если в j - й проект вложено менее i финансовых пакетов,

i = 1,2, ...,nv,j = 1,2, ...,к.

Для построения целевой функции введем матрицу эффективности ДА = ДЛу = ci- — a_t__xj _f которая имеет смысл дополнительной прибыли, полученной от вложения в у-й проект одного дополнительного инвестиционного пакета. Для решения введем еще одну матрицу Дх„ = х- i = 2,3, ...,т;

j = 1,2, ..., к. Модель задачи будет иметь вид

'^xij ->max;

z=i 7=1

' m к

) '=1 >1

kXjj <0; x- <1; Ху >0; х- - целое .

При нахождении переменных X- при оптимальном решении инвестиции т

* т * *

I j, дающие наибольшую прибыль, будут равны * j — 2^^xij ?

z=l

ПРИМЕР 2.1.5. Инвестору предложили вложить имеющиеся средства в количестве 12 д. е. в один или несколько из 5 имеющихся проектов, кратно одной д. е., но не более 7 д. е. в один проект. Матрица прибылей А приведена в табл. 2.1.3.

Таблица 2.1.3

Как оптимально распределить денежные средства по проектам так, чтобы суммарная прибыль была максимальной (решить на ЭВМ)?

РЕШЕНИЕ. Открываем лист электронной таблицы EXCEL и вводим исходные данные согласно рис. 2.1.1.

Рис. 2.1.1

Исходные данные содержат матрицу А, взятую из условия, матрицу переменных х, значения которых могут быть любыми числами, на рис. 2.1.1 это единицы, остальные матрицы рассчитываем. Ставим курсор в ячейку 15 и вводим в нее формулу «=В5-В6». Автозаполнением распространяем эту формулу на всю таблицу, то есть на ячейки 15-М11. Ставим курсор в 115 и вводим формулу «=В15-В16». Автозаполнением распространяем эту формулу на всю таблицу, то есть на ячейки I15-M20. Вводим целевую функцию и сумму переменных. Ставим курсор в В23 и вводим функцию «=СУММПРОИЗВ» (I5:M11;B15:F21), а затем ставим курсор в D23 и вводим «=СУММ(В15:Г21)», где функции «суммпроизв» и «сумм» можно вызвать с помощью мастера функций в категории «Математические».

Вызываем надстройку ПОИСК РЕШЕНИЯ (Solver Add - in). При работаете в «EXCEL 2003» или ранней версии заходим в меню СЕРВИС, выбираем НАДСТРОЙКИ и проверяем наличие флажка напротив «Поиск решения», «ОК», заходим вновь в меню СЕРВИС, выбираем ПОИСК РЕШЕНИЯ. Если Вы работаете в «EXCEL 2007» или более поздней версии, то нажимаем левой кнопкой мыши по круглой кнопке “Office” в верхнем левом углу экрана, внизу выбираем «Параметры Excel», слева выбираем НАДСТРОЙКИ, нажимаем кнопку «Перейти» внизу окна и в открывшемся окне проверяем наличие флажка напротив «Поиск решения», «ОК». В меню ДАННЫЕ выбираем ПОИСК РЕШЕНИЯ.

В открывшемся окне ставим курсор в поле «Установить целевую» (Set Target Cell), щелкаем мышью по ячейке В23 с целевой функцией. Далее проверяем, что флажок ниже поля стоит напротив надписи «Равной максимальному значению» (Equal to ... Max ... Value of:). После ставим курсор в поле «Изменяя ячейки» (By Changing Cell) и обводим ячейки с переменными B15-F21.

Для того чтобы ввести ограничения, нажимаем кнопку «Добавить» (Add), открывается окно «Добавление ограничения» (Add Constraints). В левом поле «Ссылка на ячейку» (Cell Reference) вводим ссылку на левую часть первого ограничения — обводим ячейки I15-M20, в центральном окне определяем знак < и в правом «Ограничения» (Constraints): 0. Нажимаем вновь «Добавить» (Add), обводим диапазон «B15:F21», «<« и «1». Нажимаем «Добавить» (Add), вводим «B15:F21», «>» и «0». Вновь «Добавить» (Add), «B15:F21», в среднем поле выбираем «цел.» (в правом появится «целое»). Выбираем «Добавить» (Add), вводим «D23», «<« и «Е1».

Для запуска вычислений нажимаем кнопку «Выполнить» (Solve). Через некоторое время появляется надпись, что решение найдено (Solver Found a Solution). Выбираем «Сохранить найденное решение» (Keep Solver Solution) и «ОК». На последнем этапе ставим курсор в 123 и вводим функцию «=СУММ(В15:В21)», автозаполняем результат на I23-M23. Видим результат в ячейках I23-M23. Он говорит о том, что оптимальное вложение средств — 4 в первый проект, по 2 во второй и третий, 3 в четвертый и 1 д. е. в пятый. Целевая функция, равная суммарной прибыли при оптимальном решении, равна 60 д. е.