Симплексный метод в Excel

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

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

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

• Если ваша цель и ограничения являются линейными функциями переменных решения, вы можете быть уверены, что найдете глобально оптимальное решение достаточно быстро, учитывая размер вашей модели. Это задача линейного программирования; это также задача выпуклой оптимизации (поскольку все линейные функции выпуклы). Метод Simplex LP Solving предназначен для решения этих задач.
• Если ваша цель и ограничения являются гладкими нелинейными функциями переменных решения, время решения будет больше. Если проблема выпуклая, вы можете быть уверены, что найдете глобально оптимальное решение, но если она невыпуклая, вы можете ожидать только локально оптимальное решение — и даже его может быть трудно найти. Метод нелинейного решения GRG предназначен для решения этих задач.
• Если ваша цель и ограничения являются негладкими и невыпуклыми функциями переменных решения (например, если вы используете функции ЕСЛИ, ВЫБРАТЬ и ПРОСМОТР, аргументы которых зависят для переменных решения), лучшее, на что вы можете надеяться, — это «хорошее» решение (лучшее, чем начальные значения переменных), а не локально или глобально оптимальное решение. Метод эволюционного решения предназначен для решения этих задач.
• Вы можете использовать целые, двоичные и любые другие ограничения для переменных со всеми тремя методами решения. Однако эти ограничения делают задачу невыпуклой и намного более трудной для решения.

С помощью метода решения Simplex LP вы можете найти глобально оптимальное решение за достаточное время, но вам, возможно, придется согласиться на решение, которое «близко к оптимальному», найденное за более разумное время. С методами нелинейного и эволюционного решения GRG следует ожидать «хорошего», но не доказуемо оптимального решения.

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

В этой статье представлено описание линейного программирования, показано, как его можно выполнить с помощью бесплатной надстройки Solver для Microsoft Excel, и показано его использование на примере из управленческого учета.

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

• Переменные решения. Переменные решения часто неизвестны при первоначальном подходе к проблеме. Эти переменные обычно представляют собой идентифицируемые «вещи» или входные данные, которыми может управлять менеджер (например, сколько стиральных машин каждой конкретной модели необходимо произвести).Таким образом, цель состоит в том, чтобы определить те значения, которые максимизируют или минимизируют целевую функцию.
• Целевая функция: это математическая функция, которая включает переменные решения для выражения целей менеджера. Цель менеджера — либо максимизировать, либо минимизировать целевую функцию.
• Ограничения. Это математические функции, которые включают переменные решения для выражения границ возможных решений.
• Границы переменных. Переменные решения редко могут принимать любые значения (от минус бесконечности до плюс бесконечности). Вместо этого они обычно имеют границы (например, ≥ 0).

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

Прежде чем мы продолжим, важно отметить, что эта статья не является исчерпывающим курсом по линейному программированию. Вместо этого это введение в тему и то, как можно использовать надстройку Excel Solver, чтобы помочь с этим типом сложной проблемы.

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

Математическое представление бизнес-задачи Beacon

Пример из управленческого учета

Beacon Co. – производитель стиральных машин. В настоящее время она продает две модели стиральных машин: Arkel и Kallex. В начале каждого производственного цикла компания Beacon должна решить, сколько единиц каждой стиральной машины производить с учетом доступных ресурсов. В предстоящем производственном цикле Beacon сталкивается с ключевыми ограничениями ресурсов. В частности, в наличии всего 3132 часа рабочей силы, 1440 футов резиновых шлангов и 200 бочек.

Продажа каждого устройства Arkel приносит компании прибыль в размере 350 долларов США, а продажа каждого устройства Kallex приносит компании прибыль в размере 300 долларов США. В то же время, для производства каждого блока Arkel требуется 18 часов труда, 6 футов резинового шланга и 1 барабан, а для производства каждого блока Kallex требуется 12 часов труда, 8 футов резинового шланга и 1 барабан. Подробная информация о соответствующих фактах представлена ​​в таблице «Сводная информация о производстве стиральных машин».

Основываясь на этих фактах и ​​предположении, что 100 % продукции будет продано, компания Beacon должна решить, сколько единиц каждой стиральной машины нужно произвести в предстоящем производственном цикле, чтобы максимизировать прибыль.

Сводка производства стиральных машин

Выполнение линейного программирования в Excel

Первым шагом в линейном программировании является разработка математического представления бизнес-задачи и ее моделирование в электронной таблице. Математически проблема в примере может быть представлена, как показано на диаграмме «Математическое представление бизнес-задачи Beacon», где X₁ и X₂ представляют собой переменные решения, которые это количество произведенных единиц Arkel и Kallex соответственно.

Далее мы реализуем математическую модель в электронной таблице Excel. См. таблицу «Модель электронной таблицы» для используемой модели электронной таблицы и таблицу «Формулы Excel» для получения подробной информации о формулах, используемых в модели.

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

При настройке Решателя в Excel необходимо выбрать метод решения. На выбор предлагается три метода или алгоритма:

• Нелинейный GRG
• Эволюционный
• Симплекс LP

GRG Nonlinear и Evolutionary лучше всего подходят для нелинейных задач, а Simplex LP ограничена только линейными задачами.

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

Из двух нелинейных методов решения GRG Nonlinear является самым быстрым. Однако за эту скорость приходится идти на компромисс.

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

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

Эволюционный алгоритм более надежен, чем нелинейный GRG, потому что он с большей вероятностью найдет глобально оптимальное решение. Однако этот метод решения также ОЧЕНЬ медленный.

Позвольте мне объяснить, почему:

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

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

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

Затем оценивается вторая популяция и выбирается победитель для создания третьей популяции.

Мы надеемся, что диаграмма ниже прояснит ситуацию.

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

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

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

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

Хорошим компромиссом между скоростью нелинейного алгоритма GRG и надежностью эволюционного алгоритма является нелинейный многозапуск GRG. Вы можете включить эту опцию в окне «Параметры решателя» на вкладке «Нелинейный GRG».

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

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

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

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

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

С помощью симплекс-метода решаем задачу поиска минимума абсолютных отклонений между наблюдаемыми значениями y и прогнозируемыми значениями y.

в задачу линейного программирования минимизации с учетом ограничений

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

Пример 1. Повторите пример 1 метода наименьших квадратов для множественной регрессии с использованием LAD-регрессии.

Мы повторяем данные из примера 1 в диапазоне A3:E14 на рис. 1 вместе с настройкой, необходимой для использования симплексного метода Excel Solver.

Рисунок 1. Данные и настройка для симплексного метода

Здесь ячейка D4 содержит формулу =$F$15+MMULT(A4:B4,$F$16:$F$17), E4 содержит =C4-D4, G4 содержит =-F4, а F19 содержит =СУММ(F4: Ф14). Ячейки в диапазоне F4:F14, представляющие начальные предположения, равны 1, как и коэффициенты регрессии в диапазоне F15:F17. Мы могли бы заменить эти догадки некоторыми другими значениями. Обратите внимание, что мы размещаем ячейки коэффициентов прямо под ячейками, чтобы у нас был непрерывный диапазон ячеек, которые будут изменены во время работы алгоритма Решателя.

Теперь мы выбираем Data > Analysis|Solver и заполняем диалоговое окно, которое появляется, как показано на рисунке 2.

Рисунок 2. Диалоговое окно "Решатель"

Обратите внимание, что мы хотим минимизировать значение в ячейке F19, которая будет содержать сумму абсолютного значения отклонения между наблюдаемыми значениями y (столбец C) и значениями, предсказанными регрессионной моделью (столбец D). Минимизация осуществляется путем варьирования значений диапазона F4:F14, содержащих абсолютные отклонения, а также диапазона F15:F17, содержащего коэффициенты регрессии.

Мы указываем ограничения для процесса оптимизации обычным способом, за исключением того, что на этот раз мы комбинируем ограничения, такие как E4 Рисунок 3. Результаты LAD-регрессии

Регрессионная модель LAD

Цена = 7,667 + 4,333 * Цвет + 2,778 * Качество

Поскольку у нас есть две независимые переменные, как отмечалось ранее, по крайней мере три элемента данных будут иметь нулевую невязку, а именно в строках 8, 10 и 11.

Одна из проблем с использованием симплексного метода в Excel заключается в том, что он ограничен 100 ограничениями, а это означает, что он будет поддерживать только модели LAD с не более чем 50 элементами данных.

Читайте также:

  
• Программа c windows system32 amdihk32 dll не предназначена для запуска
  
• Пропустить все ошибки в Excel
  
• Как убрать жирный курсор в Word
  
• Где найти Visual C на компьютере
  
• Excel vba выбирает ячейки по условию