Интернет-журнал «НАУКОВЕДЕНИЕ» Том 7, №4 (июль - август 2015) http://naukovedenie.ru publishing@naukovedenie.ru

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

1

http://naukovedenie.ru 60EVN415

Интернет-журнал «НАУКОВЕДЕНИЕ» Том 7, №4 (июль - август 2015) http://naukovedenie.ru publishing@naukovedenie.ru

1

http://naukovedenie.ru 60EVN415

УДК 330.45

НОУ ВПО «Российский новый университет»

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

Барышев А.В.

Россия

Ранее мы рассмотрели вопрос использования надстройки поиск решения Excel (версии 2007-2013) для поиска альтернативных оптимальных решений в задачах линейного программирования [1]. В этой работе был предложен эвристический способ поиска альтернативных оптимальных решений, позволяющий выявить наибольшее число альтернатив и сократить время их поиска, при этом полученный результат может быть выражен дробными числами. Однако в некоторых задачах переменные, входящие в целевую функцию должны быть выражены целыми числами. Если произвести округление дробных чисел до ближайших целых значений, то полученное решение может стать неоптимальным или же выйти из области допустимых значений. В связи с этим в настоящей работе исследована возможность применения ранее предложенного нами способа «перестановки ограничений» [1] для поиска целочисленных оптимальных решений, поскольку наличие альтернатив является важным моментом для принятия управленческих решений. Однако, в литературе, например [2-10], описываются либо теоретические аспекты поиска целочисленных оптимальных решений либо поиск безальтернативного целочисленного оптимального решения. Нахождение способа поиска альтернативных целочисленных оптимальных решений с помощью excel обусловливает актуальность и практическую ценность настоящей работы.

Как указывалось ранее, при использовании симплексного метода надстройки «поиск решения» excel в задачах линейного программирования в качестве признаков, указывающих на существование оптимальных альтернативных решений, является наличие в отчете по устойчивости нулей «в таблице «Изменяемые ячейки» в столбцах «Допустимое увеличение» и «Допустимое уменьшение»…» [2]. Можно предположить, что, если задача линейного программирования имеет альтернативные решения, то и задача целочисленного программирования может иметь альтернативные оптимальные решения. С этой целью исследуем вопрос применения способа «перестановки ограничений» для поиска целочисленных альтернативных оптимальных решений. Кроме того, для выявления особенностей решения рассмотрим примеры, представленные в статье [1].

Пример 1. Найти максимум целевой функции

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

Введем данные в таблицу Excel из примера 1 [1].

Рисунок 1. Фрагмент листа Excel, заполненный данными из формул (1) и (2) [1] Переходим к использованию «надстройки поиск решения».

Через меню «данные» и «поиск решения» входим в окно «параметры поиска решения». Задаем абсолютный адрес ячейки целевой функции, вид оптимума, диапазон изменяемых ячеек (ограничиваем целыми значениями), задаем ограничения и метод решения задачи (см. рис. 2).

Рисунок 2. Окно «параметры поиска решения» (получено автором)

В целях проведения исследования будем использовать как симплексный метод, так и метод ОПГ. Далее с помощью кнопки «параметры» переходим в одноименное окно (см. рис. 3).

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

Например, установим параметры поиска:

1. Точность ограничения - 0.001.

2. Максимальное время (в секундах) - 100.

3. Число итераций - 100.

4. Максимальное число допустимых решений (установим, например) - 4.

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

Поиск решения осуществляется после задания начальных значений нажатием кнопки «найти решение» окна «параметры поиска решения».

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

Рисунок 3. Окно параметры поиска решения MS Excel (получено автором)

Таблица 1 Поиск альтернативных решений целевой функции (1) симплексным методом (составлено автором)

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

Изменим симплексный метод решения на метод обобщенного приведенного градиента (ОПГ). Результаты поместим в таблицу 2.

Таблица 2 Поиск целочисленных альтернативных решений целевой функции (1) методом ОПГ (составлено автором)

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

Пример 2. Найти максимум целевой функции [1]:

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

,

Подобно примеру 1 вводим данные выражений (3) и (4) в таблицу Excel (рис. 4).

Рисунок 4. Фрагмент листа Excel, заполненный данными (3) и (4) [1]

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

Таблица 3 Поиск целочисленных альтернативных решений целевой функции (3) методом ОПГ (составлено автором)

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

На основании изложенного материала можно сделать следующие выводы:

1. Начинать поиск альтернативных целочисленных решений необходимо с решения задачи линейного программирования с помощью симплексного метода надстройки Excel «поиск решения», получив при этом отчет об устойчивости. Если в отчете по устойчивости «в таблице «Изменяемые ячейки» в столбцах «Допустимое увеличение» и «Допустимое уменьшение»…» есть нули, то необходимо искать целочисленные альтернативные оптимальные решения.

2. Поиск целочисленных альтернативных оптимальных решений можно производить методом обобщенного приведенного градиента (ОПГ) с помощью способа «перестановки ограничений». Это позволит не использовать случайный поиск.

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

Литература

1. Барышев А.В., Федотова Е.Л. К вопросу использования надстройки Excel «поиск решения» в задачах линейного программирования // Интернет-журнал «НАУКОВЕДЕНИЕ» Том 7, №2 (2015)

2. Минько А.А. Принятие решений с помощью Excel. Просто как дважды два. - М.: Эксмо, 2007. - 240 с. 3. Агальцов В.П. Математические методы в программировании: учебник. - М.: ИД «ФОРУМ», 2010. - 240 с.

4. Исследование операций в экономике: учебник для академического бакалавриата / Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман; под. ред. Н.Ш. Кремера. - М.: Издательство Юрайт. 2014. - 438 с.

5. Экономико-математические методы и модели: учебник для бакалавров/п, В.Н. Сотников; под. ред. проф. А.М. Попова. - М.: Издательство Юрайт. 2011. - 479 с.

6. Созонов С.В. Разработка моделей оптимизации производственной программы промышленного предприятия на основе формулирования целевых функций / Экономические науки. 2010. Т. 67. №6. С. 231-235.

7. Колоколов А.А., Заозерская Л.А. Построение и анализ оценок числа итераций для алгоритмов целочисленного программирования с использованием метода регулярных разбиений / Известия вузов. Математика. 2014, №1, c. 41-54.

8. Логинов В.Н. Управленческие решения: модели и методы: Учебное пособие. - М.: Издательство «Альфа-Пресс», 2011. - 184 с.

9. Методы оптимизации: практикум / Б.В. Соболь, Б.Ч. Месхи, Г.И. Каныгин. - Ростов н/Д: Феникс, 2009. - 380 с.

10. Леоненков А.В. Решение задач оптимизации в среде MS Excel. - СПб.: БХВ - Петербург, 2005. - 704 с.

Аннотация

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

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

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

Обычно для решения задач целочисленного программирования используется надстройка Excel «поиск решения». Однако не все предлагаемые ею методы равнозначны при поиске целочисленных альтернативных оптимальных решений. Кроме того, эффективность поиска зависит от начального приближения целевой функции. Поэтому целью настоящей работы являются выбор наиболее эффективного метода поиска альтернативных оптимальных решений задач целочисленного программирования с помощью надстройки «поиск решения» Excel (версии 2007-2013) и исследование возможности и особенности применения способа «перестановки ограничений» для задания начального приближения целевой функции.

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

Ключевые слова: надстройка Excel «поиск решения»; задачи целочисленного программирования; альтернативные оптимальные решения; симплексный метод; метод обобщенного приведенного градиента; целевая функция; ограничения; начальное приближение целевой функции.

Linear programming approach is widely used in case of the full certainty where an optimal decision must be found. Some of decision making problems variables in the objective function which must be expressed in whole numbers.

The optimality of a found decision mostly depends on the number of existing alternatives and their scientific feasibility. In some cases there can be several alternative optimal solutions in whole numbers for a single decision problem. Finding the best one of these alternatives is a quite difficult and hard-working process.

Often Microsoft Excel Solver Add-in is used to solve linear programming decision problems in whole numbers. However not all of its techniques are equal when finding an optimal solution for a decision problem in whole. Further, the efficiency of finding a solution depends on initial approximation of the objective function. Therefore, the aim of this paper is to choose the most efficient method for finding optimal solutions of linear programming problems in whole numbers using Microsoft Excel (versions 2007-2013) Solver Add-in and to evaluate the ability of using «constraints swapping» methods for initializing the objective function.

This paper compares the efficiency of simplex and generalized reduced gradient methods in Microsoft Excel for finding alternative optimal solutions of linear programming problems in whole number and evaluates the ability of using «constraints swapping» for initializing the objective function.

Keywords: Microsoft Excel Solver; linear programming problems; alternative optimal solutions; simplex method; generalized reduced gradient method; objective function.

Размещено на Allbest.ru