Оптимальным решением задачи линейного программирования называется

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

Для поиска по сайту, попробуйте Edit | Find на странице [Ctrl + f]. Введите слово или фразу в диалоговом окне, например

parameter » илиlinear » , если первое появление слова/фразы не то. Что вы ищете. Попробуйте Find Next.


МЕНЮ

  1. Введение и Краткое изложение
  2. Процесс Оптимизации-Моделирования
  3. Составные части оптимизационных задач и их классификация
  4. Линейное программирование (LP)
  5. Двойная проблема: Ее Конструктивные и экономические последствия
  6. Изучение оптимальной Стратегии
  7. Проблема Поиска цели
  8. Используйте Свои Знания. Чтобы улучшить то. Что Вы узнали (PDF)
  9. Решатели линейной оптимизации для загрузки (бесплатно)

Сопутствующие Сайты:


Составные части оптимизационных задач и их классификация

  1. Введение
  2. Двухуровневая Оптимизация
  3. Комбинаторная оптимизация
  4. Удовлетворение ограничений
  5. Выпуклая программа
  6. Анализ охвата данных
  7. Динамическое программирование
  8. Эволюционные и генетические методы
  9. Дробная программа
  10. Теория игр
  11. Геометрическая программа
  12. Глобальная Оптимизация
  13. Эвристическая Оптимизация
  14. Линейно Ограниченная Глобальная Оптимизация
  15. Линейная программа
  16. Метаэвристика
  17. Многоуровневая Оптимизация
  18. Мультиобъективная Программа
  19. Программа недвоичных ограничений
  20. Невыпуклая программа
  21. Негладкая программа
  22. Онлайн-Оптимизация
  23. Оптимизация роя частиц
  24. Квадратичная программа
  25. Разделяемая программа
  26. Интеллект роя


Линейное программирование (LP)

  1. Введение
  2. Процесс постановки задачи LP и его приложения
  3. Метод графического решения (двумерные решения)
  4. Связи между ЛП и системами уравнений: Алгебраический метод
  5. Расширение до более высоких измерений
  6. Численный Пример: Транспортная задача
  7. Как решить линейную систему уравнений с помощью LP-решателей?


Двойная проблема: Ее Конструктивные и экономические последствия

  1. Двойная проблема: Конструкция и ее значения
  2. Двойная проблема проблемы плотника

  3. Управленческая Ошибка Округления
  4. Расчет теневых цен
  5. Поведение изменения значений RHS от оптимального значения


Изучение оптимальной стратегии:
Чувствительность. Специфичность. Структурность и анализ

  1. Работа с неопределенностями и сценарное моделирование
  2. Вычисление диапазонов чувствительности для задач малых размеров
  3. Маржинальный Анализ и Определение Приоритетов Факторов
  4. Что такое 100% Правило (область чувствительности)
  5. Добавление нового ограничения
  6. Удаление ограничения
  7. Замена ограничения
  8. Изменения коэффициентов ограничений
  9. Добавление переменной (например. Введение нового продукта)

  10. Удаление переменной (например. Завершение продукта)
  11. Проблема Оптимального Распределения Ресурсов
  12. Определение наименьшей чистой прибыли Продукта
  13. Min Max & Max Min Вычисление за один запуск
  14. Проблема Осуществимости: Целевые Показатели

Введение и Краткое изложение

Проблемы принятия решений можно разделить на две категории: детерминированные и вероятностные модели принятия решений. В детерминированных моделях хорошие решения приводят к хорошим результатам. Вы получаете то. Что ожидаете; следовательно. Результат детерминирован (то есть без риска).

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

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

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

Модель-это репрезентация реальности. Которая отражает Фотография-это модель реальности. Изображенной на картине. Кровяное давление может быть использовано в качестве модели здоровья человека. Пилотная маркетинговая кампания может быть использована для моделирования реакции людей на новый продукт.

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

Поскольку модель отражает только определенные аспекты реальности. Она может быть неуместна для использования в конкретном приложении. Поскольку она может захватывать неправильные элементы реальности. Температура является моделью климатических условий. Но может быть неуместной. Если вас интересует барометрическое давление. Фотография человека является моделью этого человека. Но дает мало информации о его или ее академических достижениях. Уравнение. Которое предсказывает годовой объем продаж конкретного продукта. Является моделью этого продукта. Но имеет мало значения. Если нас интересует себестоимость продукции на единицу.

Таким образом. Полезность модели зависит от того аспекта реальности. Который она представляет.

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

Полезная модель-это та. Которая фиксирует соответствующие элементы реальности с приемлемой точностью.

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

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

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

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

Эффективность результатов применения любой методики оптимизации во многом зависит от того. В какой степени модель представляет собой исследуемую систему.

Чтобы определить те условия. Которые приведут к решению системной задачи. Аналитик должен сначала определить критерий. С помощью которого производительность системы можно измерить. Этот критерий часто называют мерой эффективности системы или мерой эффективности. В бизнес-приложениях мерой эффективности часто являются затраты или прибыль. В то время как в государственных приложениях чаще используется соотношение выгод и затрат.

Математическая (то есть аналитическая) модель. Описывающая поведение меры эффективности. Называется целевой функцией. Если целевая функция должна описывать поведение меры эффективности. Она должна фиксировать связь между этой мерой и теми переменными. Которые вызывают ее изменение. Системные переменные можно классифицировать как переменные принятия решений и параметры. Переменная принятия решения-это переменная. Которая может непосредственно контролироваться лицом. Принимающим решение. Есть также некоторые параметры. Значения которых могут быть неопределенными для лица. Принимающего решение. Это требует анализа чувствительности после нахождения наилучшей стратегии. На практике математические уравнения редко фиксируют точную связь между всеми системными переменными и мерой эффективности. Вместо этого аналитик OR/MS/DS должен стремиться определить переменные. Которые наиболее существенно влияют на меру эффективности. А затем попытаться логически определить математическую связь между этими переменными и мерой эффективности. Эта математическая зависимость является целевой функцией. Которая используется для оценки эффективности исследуемой системы.

Формулировка значимой целевой функции обычно является утомительной и разочаровывающей задачей. Попытки разработать целевую функцию могут потерпеть неудачу. Неудача может произойти из-за того. Что аналитик выбрал неверный набор переменных для включения в модель. Поскольку он не смог определить правильную связь между этими переменными и мерой эффективности. Возвращаясь к чертежной доске. Аналитик пытается обнаружить дополнительные переменные. Которые могут улучшить его модель. Отбрасывая те, которые. По-видимому. Имеют мало или вообще не имеют отношения. Однако, действительно ли эти факторы улучшают модель. Можно определить только после разработки и тестирования новых моделей. Включающих дополнительные переменные. Весь процесс выбора переменных. Отбраковки и формулирования модели может потребовать многократного повторения. Прежде чем будет разработана удовлетворительная целевая функция. Аналитик надеется добиться некоторого улучшения модели на каждой итерации. Хотя обычно это не так. Конечному успеху чаще предшествует череда неудач и небольших успехов.

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

Математическая модель предлагает аналитику инструмент. Которым он может манипулировать в своем анализе исследуемой системы. Не нарушая саму систему. Например, предположим. Что была разработана математическая модель для прогнозирования годового объема продаж в зависимости от цены продажи единицы. Если известны производственные затраты на единицу продукции. То можно легко рассчитать общую годовую прибыль по любой данной цене продажи. Однако, чтобы определить цену продажи для получения максимальной общей прибыли. В модель могут быть введены различные значения цены продажи по одному. Полученные продажи отмечаются. И общая прибыль за год вычисляется для каждого значения исследуемой отпускной цены. Методом проб и ошибок аналитик может определить цену продажи. Которая максимизирует общую годовую прибыль. К сожалению. Такой подход не гарантирует. Что вы получите оптимальную или лучшую цену. Потому что возможности попробовать их все огромны. Метод проб и ошибок является простым примером для последовательное мышление. Методологии решения оптимизационных задач основаны на одновременное мышление это приводит к оптимальному решению. Пошаговый подход называется алгоритм оптимизационного решения.

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

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

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

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

Дальнейшие показания:
Ackoff R., Ackoff’s Best: His Classic Writings on Management, Wiley, 1999.
Бендер Э., Введение в математическое моделирование, Dover Pubns, 2000.
Fdida S., and G. Pujolle, Modeling Techniques and Performance Evaluation, Elsevier Science, 1987.
Gershenfeld N., The Nature of Mathematical Modeling, Cambridge Univ. Pr., 1998.


Процесс Оптимизации-Моделирования

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

Оптимизационное моделирование требует соответствующего времени. Общая процедура. Которая может быть использована в технологическом цикле моделирования. Заключается в следующем: (1) описании проблемы. (2) предписании решения и (3) управлении проблемой путем непрерывной оценки/обновления оптимального решения при одновременном изменении параметров и структуры задачи. Очевидно, что среди этих общих шагов всегда есть петли обратной связи.

Математическая постановка задачи: Как только вы обнаружите проблему. Подумайте и поймите ее. Чтобы адекватно описать проблему в письменной форме. Разработайте математическую модель или структуру для воссоздания реальности с целью разработки/использования алгоритма оптимизационного решения. Формулировка проблемы должна быть проверена до того. Как будет предложено решение. Хорошая математическая формулировка для оптимизации должна быть как инклюзивной (т. е. включающей в себя то. Что относится к задаче). Так и эксклюзивной (т. е. исключающей то. Что не относится к задаче).

Найдите оптимальное решение: Это идентификация алгоритма решения и стадии его реализации. Единственный хороший план это реализованный план, который остается реализованным!

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

Анализ После принятия Решения: Эти действия включают в себя обновление оптимального решения для того. Чтобы контролировать проблему. В этом постоянно меняющемся мире крайне важно периодически обновлять оптимальное решение любой конкретной задачи оптимизации. Модель. Которая была валидной. Может потерять валидность из-за изменения условий, став. Таким образом. Неточным представлением реальности и отрицательно влияя на способность лица. Принимающего решения. Принимать правильные решения. Созданная вами оптимизационная модель должна быть способна справляться с изменениями.

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

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


Дальнейшие показания:
Бероги Г., Моделирование решений в управлении политикой: Введение в аналитические концепции, Бостон. Kluwer Academic Publishers, 1999.
Camm J., and J. Evans, Management Science: Modeling, Analysis. And Interpretation, South-Western College Pub., 1999.


Составные части оптимизационных задач и их классификация

Суть всех деловых решений. Независимо от того. Принимаются ли они для фирмы или отдельного человека. Заключается в том. Чтобы найти такой курс действий. Который принесет вам наибольшую прибыль.

Человечество уже давно ищет или делает вид. Что ищет лучшие способы выполнения повседневных жизненных задач. На протяжении всей человеческой истории человек сначала искал более эффективные источники пищи. А затем искал материалы. Силу и господство над физической средой. Однако сравнительно поздно в истории человечества общие вопросы стали количественно формулироваться сначала в словах. А затем перерастать в символические обозначения. Одним из распространенных аспектов этих общих вопросов был поиск В большинстве случаев менеджеры стремятся лишь к некоторому повышению уровня производительности или к решению Следует подчеркнуть. Что эти слова обычно не имеют точного значения.

Предпринимались попытки описать сложные человеческие и социальные ситуации. Чтобы иметь смысл. Задача должна быть записана в математическом выражении. Содержащем одну или несколько переменных. В которых должны быть определены значения переменных. Тогда возникает вопрос. Какие значения должны иметь эти переменные. Чтобы математическое выражение имело максимально возможное числовое значение (максимизация) или минимально возможное числовое значение (минимизация). Этот процесс максимизации или минимизации называется оптимизацией.

Оптимизация. Также называемая математическим программированием. Помогает найти ответ. Который дает наилучший результат-тот. Который достигает наибольшей прибыли. Производительности или счастья, или тот. Который достигает наименьших затрат. Потерь или дискомфорта. Часто эти проблемы связаны с наиболее эффективным использованием ресурсов. Включая деньги, время. Оборудование, персонал. Инвентарь и многое другое. Задачи оптимизации часто классифицируются как линейные или нелинейные. В зависимости от того. Является ли отношение в задаче линейным по отношению к переменным. Существует множество программных пакетов для решения задач оптимизации. Например, LINDO или ваш WinQSB решают линейные модели программ и жаргон и что’sBest! решайте нелинейные и линейные задачи.

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

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

Задачи оптимизации состоят из трех основных компонентов:

  1. Целевая функция. Которую мы хотим минимизировать или максимизировать. То есть величина. Которую вы хотите максимизировать или минимизировать. Называется целевой функцией. Большинство оптимизационных задач имеют единую целевую функцию, а если нет. То их часто можно переформулировать так. Чтобы они ее выполняли. Два интересных исключения из этого правила:

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

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

  2. Управляемые входы — это набор переменных решения. Влияющих на значение целевой функции. В производственной задаче переменные могут включать распределение различных доступных ресурсов или труд. Затраченный на каждый вид деятельности. Переменные принятия решений очень важны. Если нет переменных. Мы не можем определить целевую функцию и ограничения задачи.
  3. Неконтролируемые входы называются параметрами. Входные значения могут быть фиксированными числами. Связанными с конкретной проблемой. Мы называем эти значения параметрами модели. Часто вам придется решать несколько
  4. Ограничения — это отношения между переменными решения и параметрами. Набор ограничений позволяет некоторым переменным решения принимать определенные значения и исключать другие. Для производственной задачи нет смысла тратить отрицательное количество времени на какую-либо деятельность. Поэтому мы ограничиваем все переменные Ограничения не всегда существенны. На самом деле область неограниченной оптимизации-это большая и важная область. Для которой доступно множество алгоритмов и программного обеспечения. На практике ответы. Имеющие здравый смысл относительно лежащей в основе физической или экономической проблемы. Часто не могут быть получены без установления ограничений на переменные. Принимающие решения.

Допустимые и оптимальные решения: Значение решения для переменных решения. Где выполняются все ограничения. Называется допустимым решением. Большинство алгоритмов решения исходят из того. Что сначала находят возможное решение. Затем стремятся улучшить его и, наконец. Меняют переменные решения. Чтобы перейти от одного возможного решения к другому возможному решению. Этот процесс повторяется до тех пор. Пока целевая функция не достигнет своего максимума или минимума. Этот результат называется оптимальным решением.

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

Существует более 4000 алгоритмов решения различных оптимизационных задач. Широко используются алгоритмы решения задач. Разработанные для следующих математических программ: выпуклых программ. Сепарабельных программ. Квадратичных программ и геометрических программ.

Линейная программа

Линейное программирование имеет дело с классом оптимизационных задач. Где и целевая функция. Подлежащая оптимизации. И все ограничения линейны в терминах переменных решения.

Краткая история линейного программирования:

  1. В 1762 году Лагранж решил прослеживаемые задачи оптимизации с простыми ограничениями равенства.
  2. В 1820 году Гаусс решил линейную систему уравнений с помощью того. Что теперь называют каузальной элиминацией. В 1866 году Вильгельм Йордан переосмыслил метод нахождения наименьших квадратов ошибок как меру добродетели. Теперь он называется методом Гаусса-Джордана.
  3. В 1945 году появился цифровой компьютер.
  4. В 1947 году Данциг изобрел симплексные методы.
  5. В 1968 году Фиакко и Маккормик представили Метод внутренних точек.
  6. В 1984 году Кармаркар применил Внутренний метод для решения линейных программ. Добавив свой инновационный анализ.

Линейное программирование оказалось чрезвычайно мощным инструментом как в моделировании реальных задач. Так и в качестве широко применимой математической теории. Однако многие интересные задачи оптимизации нелинейны. Изучение таких задач включает в себя разнообразное сочетание линейной алгебры. Многомерного исчисления. Численного анализа и вычислительных методов. Важные области включают разработку вычислительных алгоритмов (включая методы внутренних точек для линейного программирования). Геометрию и анализ выпуклых множеств и функций. А также изучение специально структурированных задач. Таких как квадратичное программирование. Нелинейная оптимизация обеспечивает фундаментальное понимание математического анализа и широко используется в различных областях. Таких как инженерное проектирование. Регрессионный анализ. Управление запасами. Геофизические исследования и экономика.

Квадратичная программа

Квадратичная программа (QP) представляет собой область оптимизации. Широкий диапазон применимости которой уступает только линейным программам. Большое разнообразие приложений естественным образом попадает в форму QP. Кинетическая энергия снаряда является квадратичной функцией его скорости. Регрессия наименьших квадратов с боковыми ограничениями была смоделирована как QP. Некоторые проблемы в планировании производства. Анализе местоположения. Эконометрике. Активационном анализе в задаче химических смесей. А также в управлении финансовым портфелем и выборе часто рассматриваются как QP. Существует множество алгоритмов решения. Доступных для случая с ограниченным дополнительным условием. Когда целевая функция выпукла.

Удовлетворение ограничений

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

Выпуклая программа

Выпуклая программа (CP) охватывает широкий класс оптимизационных задач. Когда целевая функция выпукла. А допустимая область является выпуклым множеством. Обоих этих допущений достаточно. Чтобы гарантировать. Что локальный минимум является глобальным минимумом.

Анализ охвата данных

Анализ охвата данных (DEA) — это показатель эффективности. Основанный на методах пограничного анализа из экономической и финансовой литературы. Методы анализа Frontier efficiency (output/input) определяют границу наилучшей практики performance frontier. Которая относится к максимальным выходам. Которые могут быть получены из заданного набора входных данных по отношению к выборке единиц принятия решений с использованием сопоставимого процесса преобразования входных данных в выходные. Сила DEA частично зависит от того. Что это непараметрический подход. Который не требует спецификации какой-либо функциональной формы отношений между входами и выходами. Выход DEA сводит несколько показателей производительности к одному для использования методов линейного программирования. Взвешивание показателей эффективности реагирует на полезность лица. Принимающего решение.

Динамическое программирование

Динамическое программирование (DP)-это, по сути. Рекурсия снизу вверх. Когда вы храните ответы в таблице. Начиная с базового случая(ов) и заканчивая все большими и большими параметрами с использованием рекурсивного правила(ов). Вы будете использовать эту технику вместо рекурсии. Когда вам нужно вычислить решения всех подзадач. И рекурсивное решение будет многократно решать некоторые подзадачи. Хотя в целом DP способен решать множество разнообразных задач. В большинстве случаев он может потребовать огромного компьютерного хранилища.

Разделяемая программа

Сепарабельная программа (SP) включает в себя частный случай выпуклых программ. Где целевая функция и ограничения являются сепарабельными функциями. То есть каждый член включает в себя только одну переменную.

Геометрическая программа

Геометрическая программа (ГП) относится к невыпуклому программированию и имеет множество применений. В частности. В задачах инженерного проектирования.

Дробная программа

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

Эвристическая Оптимизация

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

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

Общие подходы включают. Но не ограничиваются ими:

  1. сравнение качества решения с оптимумом на эталонных задачах с известными оптимумами. Среднее отличие от оптимума, частота. С которой эвристика находит оптимум.
  2. сравнение качества решения с наиболее известной границей для эталонных задач. Оптимальные решения которых не могут быть определены.
  3. сравнение вашей эвристики с опубликованной эвристикой для одного и того же типа задачи. Разница в качестве решения для данного времени выполнения и. Если это уместно. Ограничение памяти.
  4. профилирование среднего качества решения как функции времени выполнения. Например. Построение среднего значения и либо минимального и максимального. Либо 5-го и 95-го процентилей значения решения как функции времени-это предполагает. Что у вас есть несколько сопоставимых экземпляров эталонной задачи.

Глобальная Оптимизация

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

Невыпуклая программа

Невыпуклая программа (NC) охватывает все задачи нелинейного программирования. Которые не удовлетворяют предположениям выпуклости. Однако даже если вам удастся найти локальный минимум. Нет никакой гарантии. Что он также будет глобальным минимумом. Поэтому не существует алгоритма. Который гарантировал бы нахождение оптимального решения для всех таких задач.

Негладкая программа

Негладкие программы (NSP) содержат функции. Для которых не существует первой производной. НСП возникают в нескольких важных областях науки и техники. Включая контактные явления в статике и динамике или эффекты расслоения в композитах. Эти приложения требуют рассмотрения несложности и невыпуклости.

Метаэвристика

Большинство метаэвристик создано для решения задач дискретной комбинаторной оптимизации. Однако для практического применения в инженерии обычно требуются методы. Которые обрабатывают непрерывные переменные или различные непрерывные и дискретные переменные. Как следствие. Большая исследовательская работа была сосредоточена на подгонке нескольких хорошо известных метаэвристик. Таких как Имитационный отжиг (SA). Поиск Табу (TS). Генетические алгоритмы (GA). Оптимизация муравьиной колонии (ACO). К непрерывным случаям. Общая метаэвристика направлена на преобразование дискретных областей применения в непрерывные посредством:

  • Методологические разработки, направленные на адаптацию некоторых метаэвристик, особенно SA, TS, GA, ACO, GRASP. Variable neighborhood search. Guided local search. Scatter search. К задачам с непрерывными или дискретными/непрерывными переменными.
  • Теоретические и экспериментальные исследования по метаэвристике. Адаптированной к непрерывной оптимизации, например. Анализ сходимости. Методология оценки производительности. Генераторы тестовых случаев. Обработка ограничений и т. Д.
  • Программные реализации и алгоритмы метаэвристики. Адаптированные к непрерывной оптимизации.
  • Реальные приложения дискретной метаэвристики. Адаптированные к непрерывной оптимизации.
  • Сравнение производительности дискретной метаэвристики (адаптированной к непрерывной оптимизации) с эффективностью конкурентных подходов, например. Оптимизации роя частиц (PSO). Оценки алгоритмов распределения (EDA). Эволюционных стратегий (ES). Специально созданных для непрерывной оптимизации.

Многоуровневая Оптимизация

Во многих процессах принятия решений существует иерархия лиц. Принимающих решения. И в этой иерархии решения принимаются на разных уровнях. Многоуровневая оптимизация фокусируется на всей иерархической структуре. Область многоуровневой оптимизации стала хорошо известной и важной областью исследований. Иерархические структуры можно найти в таких научных дисциплинах. Как окружающая среда. Экология, биология. Химическая инженерия, механика. Теория классификации. Базы данных. Проектирование сетей, транспорт. Цепочки поставок. Теория игр и экономика. Более того, постоянно появляются новые приложения.

Мультиобъективная Программа

Мультиобъективная программа (МП). Известная также как Целевая программа. — это когда одна объективная характеристика оптимизационной задачи заменяется несколькими целями. При решении МП можно представить некоторые цели как ограничения. Которые должны быть выполнены. В то время как другие цели могут быть взвешены. Чтобы составить составную единую целевую функцию.

Множественная объективная оптимизация отличается от единичного объективного случая несколькими способами:

  1. Обычное значение оптимума не имеет смысла в множественном объективном случае. Так как решение. Оптимизирующее все цели одновременно. В общем случае нецелесообразно; вместо этого запускается поиск осуществимого решения. Дающего наилучший компромисс между целями на множестве. Так называемых. Эффективных решений;
  2. Определение наилучшего компромиссного решения требует учета предпочтений. Выраженных лицом. Принимающим решение;
  3. Многочисленные задачи. Встречающиеся в реальных задачах. Часто являются математическими функциями противоположных форм.
  4. Ключевым элементом модели программирования целей является функция достижения. То есть функция. Измеряющая степень минимизации переменных нежелательных отклонений целей. Рассматриваемых в модели.

Бизнес-Приложение: При управлении кредитным портфелем прогнозирование поведения владельца кредитной карты является ключом к снижению риска банкротства. Учитывая набор атрибутов для основных аспектов владельцев кредитных карт и предопределенных классов поведения расходов. Можно построить классификационную модель. Используя линейное программирование нескольких критериев для обнаружения моделей поведения владельцев кредитных карт.

Программа недвоичных ограничений

На протяжении многих лет сообщество программистов с ограничениями уделяло значительное внимание моделированию и решению задач с использованием бинарных ограничений. Только недавно небинарные ограничения привлекли внимание из-за растущего числа реальных приложений. Недвоичное ограничение-это ограничение. Которое определяется для k переменных. Где k обычно больше двух. Недвоичное ограничение можно рассматривать как более глобальное. Моделирование задачи как недвоичного ограничения имеет два основных преимущества: оно облегчает выражение задачи; и это обеспечивает более мощное распространение ограничений по мере того. Как становится доступной более глобальная информация.

Успех в составлении расписания. Планировании и маршрутизации доказал. Что использование недвоичных ограничений является перспективным направлением исследований. На самом деле все большее число сотрудников OR/MS/DS считают. Что эта тема имеет решающее значение для того. Чтобы сделать технологию ограничений реалистичным способом моделирования и решения реальных проблем.

Двухуровневая Оптимизация

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

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

Комбинаторная оптимизация

Комбинаторный обычно означает. Что пространство состояний дискретно (например, символы. Не обязательно числа). Это пространство может быть конечными или неопределимыми множествами. Например, дискретная задача является комбинаторной. Задачи, в которых пространство состояний полностью упорядочено. Часто могут быть решены путем сопоставления их целым числам и применения Если пространство состояний неупорядочено или только частично упорядочено. Эти методы не работают. Это означает. Что эвристические методы становятся необходимыми, например. Имитация отжига.

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

Эволюционные методы

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

Генетические алгоритмы (ГАС) стали высокоэффективным инструментом для решения сложных оптимизационных задач. Однако его теоретическая основа все еще довольно фрагментарна.

Оптимизация роя частиц

Оптимизация роя частиц (PSO) — это стохастический алгоритм оптимизации на основе популяции. Вместо конкуренции/отбора. Как, скажем. В Эволюционных вычислениях. PSO использует сотрудничество. В соответствии с парадигмой. Иногда называемой Такие системы. Как правило. Состоят из популяции простых взаимодействующих агентов без какого-либо централизованного контроля и вдохновлены случаями. Которые можно найти в природе. Такими как колонии муравьев, стаи птиц. Выпас животных. Формирование бактерий. Стайка рыб и т. Д.

Существует множество вариантов PSO. Включая ограниченные. Мультиобъективные и дискретные или комбинаторные версии. И приложения были разработаны с использованием PSO во многих областях.

Интеллект роя

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

Swarm Intelligence-это инновационная распределенная интеллектуальная парадигма для решения оптимизационных задач. Которая первоначально черпала свое вдохновение из биологических примеров роения. Скопления и выпаса животных у позвоночных. Интеллектуальный анализ данных-это аналитический процесс. Предназначенный для изучения больших объемов данных в поисках последовательных паттернов и/или систематических связей между переменными. А затем для проверки полученных результатов путем применения обнаруженных паттернов к новым подмножествам данных.

Онлайн-Оптимизация

Независимо от того. Должны ли быть сокращены затраты. Максимизирована прибыль или разумно использованы ограниченные ресурсы. Методы оптимизации доступны для руководства процессом принятия решений. В онлайн-оптимизации основной проблемой являются неполные данные и научная проблема: насколько хорошо может работать онлайн-алгоритм? Можно ли гарантировать качество решения. Даже не зная заранее всех данных? В оптимизация в реальном времени существует дополнительное требование: решения должны быть рассчитаны очень быстро по отношению к рассматриваемым временным рамкам.

Дальнейшие показания:
Abraham A., C. Grosan and V. Ramos, Swarm Intelligence, Springer Verlag, 2006. Она посвящена применению роевого интеллекта в интеллектуальном анализе данных с использованием различных интеллектуальных подходов.
Charnes A., Cooper W., Lewin A.. And L. Seiford, Data Envelopment Analysis: Theory, Methodology and Applications, Kluwer Academic Publications, 1994.
Dempe S., Foundation of Bilevel Programming, Kluwer, 2002.
Diwekar U., Introduction to Applied Optimization, Kluwer Academic Publishers, 2003. Охватывает практически все вышеперечисленные техники.
Liu B., and A. Esogbue, Критерии принятия решений и оптимальные процессы инвентаризации, Клувер, 1999.
Luenberger D. В, линейное и нелинейное Программирование, издательством Kluwer академические издатели, 2003.
Миллер Р., оптимизации: основы и приложения, М., 1999.
MigdalasA., Пардалос п.. И П. Varbrand, многоуровневая оптимизация: алгоритмы и приложения, Клювер, 1998.
Ривз К. и Ж. Роу, генетические алгоритмы: принципы и перспективы, Клувер, 2002.
Родин Р., оптимизации в исследовании операций, Прентис-Холл. Нью-Джерси, 2000.

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


Линейное программирование

Линейное программирование часто является любимой темой как для преподавателей. Так и для студентов. Возможность введения LP с использованием графического подхода. Относительная простота метода решения. Широкая доступность программных пакетов LP и широкий спектр приложений делают LP доступным даже для студентов с относительно слабым математическим образованием. Кроме того, LP предоставляет прекрасную возможность представить идею анализа

Линейное программирование (ЛП) — это математическая процедура определения оптимального распределения дефицитных ресурсов. LP-это процедура. Которая нашла практическое применение практически во всех аспектах бизнеса. От рекламы до планирования производства. Наиболее типичными объектами анализа ЛП являются задачи планирования транспортировки. Распределения и совокупного производства. В нефтяной промышленности, например. Менеджер по обработке данных в крупной нефтяной компании недавно подсчитал. Что от 5 до 10 процентов компьютерного времени фирмы было посвящено обработке LP и LP-подобных моделей.

Линейное программирование имеет дело с классом задач программирования. Где как целевая функция. Подлежащая оптимизации, линейна. Так и все отношения между переменными. Соответствующими ресурсам, линейны. Впервые эта проблема была сформулирована и решена в конце 1940-х годов. Редко когда новая математическая техника находила такое широкое практическое применение в бизнесе. Коммерции и промышленности и одновременно получала столь основательную теоретическую разработку за столь короткий промежуток времени. Сегодня эта теория успешно применяется к проблемам бюджетирования капитала. Проектирования рационов питания. Сохранения ресурсов. Стратегических игр. Прогнозирования экономического роста и транспортных систем. В самое последнее время теория линейного программирования также помогла разрешить и унифицировать многие выдающиеся приложения.

Для читателя важно с самого начала понять. Что В первом случае это означает планировать и организовывать. Как в он программирует вас своим решением. В то время как в последнем случае это означает написание кодов для выполнения вычислений. Обучение одному виду программирования имеет очень мало прямого отношения к другому. На самом деле термин Этой путаницы иногда удается избежать. Используя термин линейная оптимизация как синоним линейного программирования.

Любая задача LP состоит из целевой функции и набора ограничений. В большинстве случаев ограничения исходят из среды. В которой вы работаете для достижения своей цели. Когда вы хотите достичь желаемой цели, вы поймете. Что окружающая среда устанавливает некоторые ограничения (то есть трудности. Ограничения) в выполнении вашего желания или цели. Вот почему такие религии. Как буддизм. Среди прочих. Предписывают жить воздержанной жизнью. Ни желания, ни боли Можете ли вы принять этот совет в отношении вашей бизнес-цели?

Что такое функция: Функция-это вещь. Которая что-то делает. Например, кофемолка-это функция. Которая превращает кофейные зерна в порошок. (Целевая) функция отображает и переводит входную область (называемую допустимой областью) в выходной диапазон с двумя конечными значениями. Называемыми максимальным и минимальным значениями.

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

  1. Целевая функция должна быть линейный То есть проверьте. Все ли переменные имеют степень 1 и они складываются или вычитаются (не делятся и не умножаются)
  2. Цель должна быть либо максимизация. Либо минимизация линейной функции. Цель должна отражать цель лица. Принимающего решение
  3. То ограничения также должны быть линейными Причем ограничение должно быть следующих форм ( £, ³, или =. То есть LP-ограничения всегда замкнуты).

Например, следующая задача не является LP: Max X, subject to X 1. Эта очень простая задача не имеет решения.

Как всегда, нужно быть осторожным. Классифицируя задачу оптимизации как задачу LP. У меня к вам вопрос. Является ли следующая проблема проблемой LP?

Макс. X2
при условии:
X1 + X2 £ 0
X12 — 4 £ 0

Хотя второе ограничение выглядит
X1 ³ -2 и X2 £ 2.
Следовательно. Приведенная выше проблема действительно является проблемой LP.

Для большинства проблем LP можно подумать о двух важных классах объектов: первый-это ограниченные ресурсы. Такие как земля. Мощность завода или объем продаж; второй-это такие виды деятельности. Как Каждый вид деятельности потребляет или, возможно. Вносит дополнительный объем ресурсов. Должна быть объективная функция. То есть способ отличить плохое от хорошего. От еще лучшего решения. Проблема заключается в том. Чтобы определить наилучшее сочетание уровней активности. Которые не используют больше ресурсов. Чем фактически доступны. Многие менеджеры сталкиваются с этой задачей каждый день. К счастью, когда вводится хорошо сформулированная модель. Программное обеспечение линейного программирования помогает определить лучшую комбинацию.

Симплексный метод является широко используемым алгоритмом решения для решения линейных программ. Алгоритм-это ряд шагов. Которые позволят выполнить определенную задачу.


Процесс постановки задачи LP и его приложения

Чтобы сформулировать проблему LP. Я рекомендую использовать следующие рекомендации после тщательного прочтения постановки проблемы несколько раз.

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

  1. Каковы переменные. Принимающие решения? То есть, что такое управляемые входы? Определите переменные решения точно. Используя описательные имена. Помните. Что контролируемые входные данные также известны как контролируемые действия. Переменные принятия решений и действия принятия решений.
  2. Каковы параметры? То есть, каковы неконтролируемые входы? Обычно это заданные постоянные числовые значения. Точно определите параметры. Используя описательные имена.
  3. Какова цель? Что такое целевая функция? Кроме того, чего хочет владелец проблемы? Как цель связана с переменными его решения? Это проблема максимизации или минимизации? Цель представляет собой цель лица,принимающего решение.
  4. Каковы ограничения? То есть какие требования должны быть выполнены? Должен ли я использовать ограничение типа неравенства или равенства? Каковы связи между переменными? Запишите их в словах. Прежде чем облечь в математическую форму.

Узнайте. Что выполнимая область не имеет ничего или мало общего с целевой функцией (min или max) Эти две части в любой формулировке ЛП исходят в основном из двух различных и различных источников. Целевая функция настраивается на выполнение желания (цели) лица. Принимающего решение. В то время как ограничения. Формирующие возможную область. Обычно исходят из среды лица. Принимающего решение. Накладывающей некоторые ограничения/условия на достижение его цели.

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


Проблема Плотника:
Распределение Дефицитных Ресурсов Между Конкурентными Средствами

Во время пары сеансы мозгового штурма с плотником (нашим клиентом) он сказал нам, что он. Исключительно. Делает столы и стулья. Продает все столы и стулья. Которые он делает на рынке. Однако не имеет стабильного дохода и хочет сделать все возможное.

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

Задача плотника состоит в том. Чтобы выяснить. Сколько столов и стульев делать в неделю; но сначала должна быть установлена целевая функция:

Так как общая стоимость это сумма постоянных затрат (F) и переменных затрат на единицу продукции. Умноженная на количество произведенных единиц. Следовательно. Задача решения состоит в том. Чтобы найти X1 и X2 такими, что:

Максимизировать 9X1 + 6X2 – [(1.5X1 + X2) + (2.5X1 + 2X2) + F1 + F2],

где X1 и X2 обозначают количество столов и стульев; стоимостные термины в скобках-это соответственно сырье и трудозатраты. F1 и F2-это постоянные затраты на два продукта соответственно. Без потери общности и какого-либо влияния на оптимальное решение поставим F1 = 0 и F2 = 0. Целевая функция сводится к следующей функции чистой прибыли:

Максимизировать 5X1 + 3X2

То есть чистый доход (скажем. В долларах или десятках долларов) от продажи Х1 столов и Х2 стульев.

Сдерживающими факторами. Которые обычно приходят извне, являются ограничения на труд (это ограничение исходит от его семьи) и сырьевые ресурсы (это ограничение исходит от запланированных поставок). Время изготовления стола и стула измеряется в разное время суток и оценивается в 2 часа и 1 час соответственно. Общее количество рабочих часов в неделю составляет всего 40 часов. Сырье, необходимое для стола и стула. Составляет 1 и 2 единицы соответственно. Общий объем поставок сырья составляет 50 единиц в неделю. Таким образом. Формулировка ЛП является:

Максимизировать 5 X1 + 3 X2

В зависимости от:
2 X1 + X2 £ 40 трудовое ограничение
X1 + 2 X2 £ 50 материальное ограничение
и оба X1, X2 неотрицательны.

Это математическая модель для плотницкой проблемы. То переменные решения, т. е., управляемые входы являются X1 и X2. Выход для этой модели составляет общий чистый доход 5 Х1 + 3 Х2. Все функции, используемые в этой модели линейный (переменная решения имеет мощность, равную 1). Коэффициенты этих ограничений называются Технологические факторы (матрица). Период обзора составляет одну неделю, соответствующий период, в течение которого неконтролируемые входы (все параметры, такие как 5, 50, 2,..) с меньшей вероятностью изменяются (колеблются). Даже при таком коротком горизонте планирования мы должны выполнить анализ реагировать на любые изменения в этих входах. Чтобы контролируйте проблему, т. е. обновите предписанное решение.

Обратите внимание, что, поскольку плотник не выходит из бизнеса в конце горизонта планирования, мы добавили условия, что оба X1, X2 должны быть неотрицательными. Вместо требований. Что X1 и X2 должны быть положительными целыми числами. Условия неотрицательности также известны как Опять же. Линейная программа была бы хороша для этой задачи. Если бы плотник собирался продолжать производить эти продукты. Частичные предметы просто будут считаться незавершенным производством и в конечном итоге станут готовыми товарами, скажем. На следующей неделе.

Мы можем попробовать решать для X1 и X2 перечислите возможные решения для каждого из них и выберите пару (X1, X2). Которая максимизирует 5X1 + 3X2 (чистый доход). Однако перечисление всех возможных альтернатив отнимает слишком много времени. И если альтернативы не перечислены исчерпывающе. Мы не можем быть уверены, что пара. Которую мы выбираем (в качестве решения). Является лучшей из всех альтернатив. Этот способ решения проблемы известен как . Более эффективные и действенные методологии. Известные как Методы Решения задач линейного программирования они основаны на одновременном мышлении и коммерчески доступны в более чем 400 различных программных пакетах со всего мира.

То оптимальное решение, т. е., оптимальная стратегия, состоит в том. Чтобы сделать X1 = 10 столов и X2 = 20 стульев. Мы можем программа еженедельные занятия плотника состояли в том. Чтобы сделать 10 столов и 20 стульев. При такой (оптимальной) стратегии чистая прибыль составляет 110 долларов. Этот предписанное решение это было неожиданностью для плотника. Так как из-за большего чистого дохода от продажи стола (5 долларов) он делал больше столов. Чем стульев!

Нанять или Нет? Предположим. Плотник может нанять кого — нибудь в помощь за 2 доллара в час. Это, кроме того. Почасовая заработная плата. Которую он/она в настоящее время платит; в противном случае 2 доллара намного ниже текущей минимальной заработной платы в США. Стоит ли нанимать плотника, и если да. То на сколько часов?

Пусть X3-количество дополнительных часов. Тогда модифицированная задача:

Максимизировать 5 X1 + 3 X2 — 2 X3

В зависимости от:
2 X1 + X2 £ 40 + X3 ограничение труда с неизвестными дополнительными часами
X1 + 2 X2 £ 50 материальное ограничение

При этом новом условии мы увидим, что оптимальное решение X1 = 50, X2 = 0, X3 = 60, с оптимальным чистым доходом в 130 долларов. Поэтому плотника следует нанять на 60 часов. А как насчет найма только на 40 часов? Ответ на этот и другие типы вопросов

В качестве упражнения используйте программное обеспечение LP. Чтобы найти наибольший диапазон значений X. Удовлетворяющий следующему неравенству с двумя абсолютными значениями:

| 3X– 4 | — | 2X – 1 | £ 2


Проблема Замены продукта

Фирма. Берущая цену. Продает S единиц своего продукта по рыночной цене p. Политика руководства заключается в замене дефектных единиц без дополнительной платы. В порядке поступления. В первую очередь. Пока имеются запасные единицы. Поскольку руководство не хочет рисковать. Совершая одну и ту же ошибку дважды. Оно производит единицы. Которые продает на рынок. На одной машине. Более того, он производит сменные агрегаты. Обозначенные X, на второй. Более качественной машине. Постоянные затраты. Связанные с эксплуатацией обеих машин. Переменные затраты и восстановительные затраты даны как функция краткосрочных затрат C(X) = 100 + 20S + 30X.

Точная вероятность того. Что блок будет неисправен, равна r. Однако, действуя из осторожности. Руководство всегда недооценивает надежность своего продукта. Тем не менее, это накладывает условие, что X ³ r.S. Спрос на продукт фирмы задается S(r) = 10000e-0,2 р. Следовательно. Задача решения заключается в максимизации функции чистой прибыли P(X):

Максимизировать P(X) = 100000p e— 0,2 р — 100 — 20S — 30X,
при условии: X ³ р. С.

Как мы узнаем. Решения задач LP находятся в вершинах допустимой области. Таким образом. Чистая прибыль P(X) будет максимизирована. Если руководство установит X = r.S.


Проблема С Диетой

Предположим. Что единственные продукты. Доступные в вашем местном магазине. — это картофель и стейк. Решение о том. Сколько из каждой еды покупать. Должно приниматься исключительно по диетическим и экономическим соображениям. У нас есть информация о питании и стоимости в следующей таблице:

  На единицу
картофеля
На единицу
стейка
Минимальные
требования
Единицы углеводов 3 1 8
Единицы витаминов 4 3 19
Единицы белков 1 3 7
Удельная стоимость 25 50  

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

  1. Сформулируйте задачу в терминах линейных неравенств и целевой функции.
  2. Решите задачу геометрически.
  3. Объясните, как соотношение затрат 2:1 (стейк к картофелю) диктует. Что решение должно быть там. Где вы сказали.
  4. Найдите соотношение затрат. Которое позволило бы перенести оптимальное решение на другой выбор количества пищевых единиц. Но при этом все равно потребовало бы покупки как стейка. Так и картофеля.
  5. Найдите соотношение затрат. Которое диктовало бы покупку только одного из двух продуктов. Чтобы минимизировать затраты.

а) Мы начинаем с установления ограничений для задачи. Первое ограничение представляет собой минимальную потребность в углеводах. Которая составляет 8 единиц за некоторое неизвестное количество времени. 3 единицы могут быть потреблены на единицу картофеля и 1 единица может быть потреблена на единицу стейка. Второе ограничение представляет собой минимальную потребность в витаминах. Которая составляет 19 единиц. 4 единицы можно потреблять на единицу картофеля и 3 единицы можно потреблять на единицу стейка. Третье ограничение представляет собой минимальное требование к белкам. Которое составляет 7 единиц. 1 единица может быть потреблена на единицу картофеля и 3 единицы могут быть потреблены на единицу стейка. Четвертое и пятое ограничения представляют собой тот факт. Что все возможные решения должны быть неотрицательными. Потому что мы не можем купить отрицательные величины.

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

{3X1 + X2 ³ 8, 4X1+ 3X2 ³ 19, X1+ 3X2 ³ 7, X1³ 0, X2 ³ 0};

Затем мы построим набор решений неравенств. Чтобы получить допустимую область возможностей.

в) Соотношение стоимости стейка к картофелю 2:1 диктует. Что решение должно быть здесь. Так как в целом мы можем видеть. Что одна единица стейка немного менее питательна. Чем одна единица картофеля. Кроме того, в одной категории. Где стейк превосходит картофель по полезности (белки). Необходимо всего 7 полных единиц. Таким образом. Легче выполнить эти единицы. Не покупая значительного количества стейка. Поскольку стейк стоит дороже. Покупка большего количества картофеля для удовлетворения этих потребностей в питании более логична.

г) Теперь мы выбираем новое соотношение затрат. Которое переместит оптимальное решение на другой выбор количества пищевых единиц. И стейк, и картофель все равно будут куплены. Но будет найдено другое решение. Давайте попробуем соотношение затрат 5:2.

г) Теперь мы выбираем новое соотношение затрат. Которое переместит оптимальное решение на другой выбор количества пищевых единиц. И стейк, и картофель все равно будут куплены. Но будет найдено другое решение. Давайте попробуем соотношение затрат 5:2.

г) Теперь мы выбираем новое соотношение затрат. Которое переместит оптимальное решение на другой выбор количества пищевых единиц. И стейк, и картофель все равно будут куплены. Но будет найдено другое решение. Давайте попробуем соотношение затрат 5:2.

Таким образом. Оптимальным решением для такого соотношения затрат является покупка 8 стейков и никакого картофеля в единицу времени для удовлетворения минимальных потребностей в питании.


Проблема Смешивания

Bryant’s Pizza. Inc. — производитель замороженной пиццы. Компания получает чистый доход в размере $1,00 за каждую обычную пиццу и $1,50 за каждую произведенную пиццу класса люкс. В настоящее время фирма имеет 150 фунтов тестовой смеси и 50 фунтов посыпочной смеси. Каждая обычная пицца использует 1 фунт тестовой смеси и 4 унции (16 унций= 1 фунт) начинки. Каждая роскошная пицца использует 1 фунт тестовой смеси и 8 унций начинки. Исходя из прошлого спроса в неделю. Брайант может продать не менее 50 обычных пицц и не менее 25 роскошных. Задача состоит в том. Чтобы определить количество обычных и роскошных пицц. Которые компания должна сделать. Чтобы максимизировать чистую прибыль. Сформулируйте эту задачу как задачу LP.

Пусть X1 и X2-число обычных и роскошных пицц. Тогда формулировка LP является:

Максимизировать X1 + 1.5 X2

При условии:
X1 + X2 £ 150
0.25 X1 + 0.5 X2 £ 50
Х1 ³ 50
Х2 ³ 25
X1 ³ 0, X2 ³ 0


Другие общие применения LP

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

Финансы: Проблема инвестора может быть проблемой выбора портфеля. В общем, количество различных портфелей может быть намного больше. Чем показывает пример. Можно добавить еще и различные виды ограничений. Другая проблема решения связана с определением сочетания финансирования для ряда продуктов. Когда имеется более одного метода финансирования. Целью может быть максимизация общей прибыли. Когда прибыль для данного продукта зависит от метода финансирования. Например, финансирование может осуществляться за счет внутренних средств. Краткосрочных долговых обязательств или промежуточного финансирования (амортизированные кредиты). Могут существовать ограничения на доступность каждого из вариантов финансирования. А также финансовые ограничения. Требующие определенных отношений между вариантами финансирования для удовлетворения условий банковских кредитов или промежуточного финансирования. Также могут быть ограничения на производственные мощности для продуктов. Переменными. Принимающими решение. Будет являться количество единиц каждого продукта. Которое будет финансироваться по каждому варианту финансирования.

Управление производством и операциями: Довольно часто в обрабатывающей промышленности данное сырье может быть превращено в самые разнообразные продукты. Например, в нефтяной промышленности сырая нефть перерабатывается в бензин, керосин. Бытовое топливо и различные сорта моторного масла. Учитывая нынешнюю норму прибыли на каждый продукт. Задача состоит в том. Чтобы определить количество каждого продукта. Которое должно быть произведено. Это решение подчиняется многочисленным ограничениям. Таким как ограничения на мощности различных нефтеперерабатывающих предприятий. Доступность сырья. Спрос на каждый продукт и любая государственная политика в отношении выпуска определенных продуктов. Аналогичные проблемы существуют и в химической и пищевой промышленности.

человеческие ресурсы: Проблемы планирования персонала также могут быть проанализированы с помощью линейного программирования. Например, в телефонной отрасли спрос на услуги монтажников-ремонтников носит сезонный характер. Задача состоит в том. Чтобы определить количество ремонтно-монтажного персонала и линейного ремонтного персонала, которое должно быть в рабочей силе каждый месяц, где сводятся к минимуму общие затраты на наем, увольнение. Сверхурочную работу и регулярную заработную плату. Набор ограничений включает в себя ограничения на требования к услугам. Которые должны быть удовлетворены. Использование сверхурочных. Профсоюзные соглашения и наличие квалифицированных работников для найма. Этот пример противоречит предположению о делимости; однако уровни рабочей силы для каждого месяца обычно достаточно велики. Чтобы округление до ближайшего целого числа в каждом случае не наносило ущерба. При условии. Что ограничения не нарушаются.

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

Распределение: Другое применение линейного программирования относится к области распределения. Рассмотрим случай. Когда имеется m фабрик. Которые должны отгружать товары на n складов. Данная фабрика могла производить отгрузки на любое количество складов. Учитывая стоимость отгрузки одной единицы продукции с каждой фабрики на каждый склад. Задача состоит в том. Чтобы определить схему отгрузки (количество единиц. Которые каждая фабрика отгружает на каждый склад). Которая минимизирует общие затраты. Это решение подчиняется ограничениям. Что спрос на каждом заводе не может отгружать больше продукции. Чем он способен произвести.


Метод Графического Решения

Процедура графического метода решения задач LP:

  1. Является ли проблема LP? Да, если и только если:

    Все переменные имеют степень 1, и они складываются или вычитаются (не делятся и не умножаются). Ограничение должно быть следующих форм ( £, ³, или =. То есть LP-ограничения всегда замкнуты). И целью должна быть либо максимизация. Либо минимизация.

    Например, следующая задача не является LP: Max X, subject to X 1. Эта очень простая задача не имеет решения.

  2. Могу ли я использовать графический метод? Да, если число решающих переменных равно 1 или 2.
  3. Используйте Миллиметровую Бумагу. Изобразите каждое ограничение одно за другим. Притворившись. Что они являются равенствами (притворившись. Что все £ и ³, are = ). А затем постройте линию. Нарисуйте прямую линию в системе координат на графической бумаге. Система координат имеет две оси: горизонтальную ось. Называемую осью x (абсцисса). И вертикальную ось. Называемую осью y (ордината). Оси пронумерованы. Обычно от нуля до наибольшего значения. Ожидаемого для каждой переменной.
  4. По мере создания каждой линии разделите область на 3 части относительно каждой линии. Чтобы определить допустимую область для этого конкретного ограничения. Выберите точку по обе стороны линии и подключите ее координаты к ограничению. Если она удовлетворяет условию. То эта сторона выполнима; в противном случае другая сторона выполнима. Для ограничений равенства возможны только точки на прямой.
  5. Отбросьте стороны. Которые неосуществимы.

    После того как все ограничения будут нанесены на график. У вас должна быть непустая (выпуклая) выполнимая область. Если только проблема не является невыполнимой.

  6. К сожалению. Некоторые границы допустимых областей. Описанные в вашем учебнике, неверны. См., например, рисунки. Изображенные на стр. Почти все неравенства должны быть заменены на равенство. Верно?

  7. Создайте (по крайней мере) две строки iso-значения из целевой функции. Установив целевую функцию на любые два различных числа. Постройте график полученных линий. Перемещая эти линии параллельно. Вы найдете оптимальный угол (крайнюю точку). Если он существует.

    В общем случае. Если допустимая область находится в пределах первого квадранта системы координат (т. Е. Если X1 и X2 ³ 0), то для задач максимизации вы перемещаете целевую функцию iso-значения параллельно самой себе далеко от исходной точки (0. 0) при этом по крайней мере общую точку с допустимой областью. Однако для задач минимизации верно обратное. То есть вы перемещаете цель iso-значения параллельно себе ближе к исходной точке, имея при этом по крайней мере общую точку с допустимой областью. Общая точка обеспечивает оптимальное решение.

Классификация возможных точек: : Допустимые точки любой непустой LP-допустимой области могут быть классифицированы как внутренние области. Границы или вершины. Как показано на следующем рисунке:


Точка B на приведенном выше двумерном рисунке, например. Является граничной точкой допустимого множества. Потому что каждый маленький круг. Центрированный в точке B. Как бы мал он ни был. Содержит как точки. Некоторые в множестве. Так и некоторые точки вне множества. Точка I является внутренней точкой, потому что оранжевый круг и все меньшие круги. А также некоторые большие; содержит исключительно точки в наборе. Совокупность граничных точек. Принадлежащих одному набору. Называется граничной линией (отрезком). Например отрезком линии cd. Пересечения граничных линий (отрезков) называются вершинами, если это возможно. Она называется угловой точкой. В трехмерном пространстве и выше круги становятся сферами и гиперсферами.

Знайте. Что ограничения LP обеспечивают вершины и угловые точки. Один вершина является пересечением 2-линий или вообще n-гиперплоскостей в задачах LP с n-решающими переменными. Один угловая точка это вершина. Которая также выполнима.

Численный Пример: Задача Плотника

Максимизировать 5 X1 + 3 X2

В зависимости от:
2 X1 + X2 £ 40
Х1 + 2 Х2 £ 50
и оба X1, X2 неотрицательны.

Типичный 2-Мерный LP

Примечание: Существует альтернатива подходу к целевой функции Iso-value с проблемами. Которые имеют мало ограничений и ограниченную допустимую область. Сначала найдите все угловые точки. Которые называются крайними точками. Затем оцените целевую функцию в крайних точках. Чтобы найти оптимальное значение и оптимальное решение.

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

Значение целевой функции в каждом углу (т. Е.) Точка
Выбор лица. Принимающего решение Координаты Угловой точки Функция Чистого Дохода
Количество столов или стульев X1, X2 5 X1 + 3 X2
Не делайте ни Стола, ни Стула 0, 0 0
Сделать Все Таблицы Вы Можете 20, 0 100
Сделайте Все Стулья, Которые Вы Можете 0, 25 75
Сделайте Смешанные Продукты 10, 20 110

Поскольку целью является максимизация, из приведенной выше таблицы мы считываем оптимальное значение, равное 110, которое достижимо. Если плотник следует оптимальной стратегии X1 = 10 и X2 = 20.

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

Основным недостатком графического метода является то. Что он ограничивается решением задач LP только с 1 или 2 переменными решения. Однако главный и полезный вывод. Который мы легко наблюдаем из графических методов. Заключается в следующем:

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

Доказательство этого утверждения следует из результатов следующих двух фактов:

Факт № 1: Допустимая область любой линейной программы всегда является выпуклым множеством.

Поскольку все ограничения являются линейными. Допустимая область (F. R.) является полигоном. Более того, этот многоугольник является выпуклым множеством. В любой задаче LP выше двумерной границы FR являются частями гиперплоскостей. И Fr в этом случае называется многогранниками. Которые также выпуклы. Выпуклое множество-это такое. Что если вы выберете из него две выполнимые точки. То все точки на отрезке прямой. Соединяющем эти две точки. Также будут выполнимы. Доказательство того. Что ФР линейных программ всегда являются выпуклыми множествами. Следует из противоречия. На следующих рисунках приведены примеры двух типов множеств: невыпуклого и выпуклого.


Множество допустимых областей в любой линейной программе называется многогранником, если оно ограничено. То называется многогранником.

Факт № 2: Iso-значение целевой функции линейной программы всегда является линейной функцией.

Этот факт вытекает из природы целевой функции в любой задаче LP. На следующих рисунках показаны два типичных вида изозначных целевых функций.


Из приведенных выше двух фактов следует. Что если линейная программа имеет непустую. Ограниченную допустимую область. То оптимальным решением всегда является одна из угловых точек.

Чтобы преодолеть недостаток графического метода. Мы будем использовать этот полезный и практический вывод при разработке алгебраического метода. Применимого к многомерным задачам LP.

Выпуклость допустимой области для линейных программ облегчает решение задач LP. Из-за этого свойства и линейности целевой функции решение всегда является одной из вершин. Более того, поскольку число вершин ограничено. Нужно найти все возможные вершины. А затем оценить целевую функцию в этих вершинах. Чтобы найти оптимальную точку.

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

К счастью, большинство задач оптимизации бизнеса имеют линейные ограничения. Поэтому LP так популярен. Сегодня на рынке существует более 400 компьютерных пакетов. Решающих задачи LP. Большинство из них основаны на поиске вершин. То есть прыжках из одной вершины в соседнюю в поисках оптимальной точки.

Вы уже заметили, что, граф системы неравенств и/или равенств называется допустимой областью Эти два представления, графические и алгебраические эквивалентны друг другу. Что означает. Что координата любой точки. Удовлетворяющей ограничениям. Находится в допустимой области. А координата любой точки в допустимой области удовлетворяет всем ограничениям.

Численный пример: Найдите систему ограничений. Представляющую следующую допустимую область.


На приведенном выше рисунке система координат показана серым цветом на заднем плане. Построив уравнения граничных линий допустимой области. Мы можем проверить. Что следующая система неравенств действительно представляет собой указанную выше допустимую область:

X1 ³ -1
X2 £ 1
X1 — X2 £ 1


Связи между LP и системами уравнений: Алгебраический метод

Как отмечал Джордж Данциг. Линейное программирование-это строго Основными решениями линейной программы являются решения систем уравнений. Состоящих из ограничений в положении привязки. Не все базовые решения удовлетворяют всем ограничениям задачи. Те, которые действительно отвечают всем ограничениям. Называются основные возможные решения Основные выполнимые решения точно соответствуют крайние точки из посильного региона.

Например, для задачи Карпентераможно вычислить все основные решения . Взяв любые два уравнения и решив их одновременно, а затем. Используя ограничения других уравнений. Проверить выполнимость этого решения. Если это возможно. То это решение является базовым возможным решением. Которое обеспечивает координаты угловой точки допустимой области. Чтобы проиллюстрировать эту процедуру. Рассмотрим ограничения Плотника в положении привязки (т. Е. Все со знаком=).:

2X1 + X2 = 40
X1 + 2X2 = 50
X1 = 0
X2 = 0

Здесь мы имеем 4 уравнения с 2 неизвестными. В терминах 42 = 4! / [2! (4-2)!] = 6 основные решения. Решая шесть результирующих систем уравнений, мы имеем:

Шесть Основных Решений с Четырьмя Основными выполнимыми Решениями

X1 X2 5X1 + 3X2
10 20 110*
0 40 неосуществимо
20 0 100
0 25 75
50 0 неосуществимо
0 0 0

Четыре из приведенных выше базовых решений являются базовыми допустимыми решениями. Удовлетворяющими всем ограничениям. Принадлежащим координатам вершин ограниченной допустимой области. Включив основное допустимое решение в целевую функцию. Мы вычисляем оптимальное значение. Таким образом. Из приведенной выше таблицы мы видим, что оптимальным решением является X1 = 10, X2 = 20 с оптимальным значением $110. Вышеприведенный подход может быть применен при решении задач более высокой размерности LP при условии. Что оптимальное решение ограничено.

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

Дальнейшие показания:
Arsham H, Links Among a Linear System of Equations, Matrix Inversion, and Linear Program Solver Routines, Journal of Mathematical Education in Science and Technology, 29(5), 764-769, 1998.
Данциг Г., Линейное программирование и расширения, стр. 21, The Rand-Princeton U. Press, 1963.


Расширение до более высоких измерений

Графический метод ограничен в решении задач LP. Имеющих одну или две переменные решения. Однако он дает четкую иллюстрацию того. Где находятся допустимые и невыполнимые области. А также вершины. Визуальное понимание проблемы помогает более рационально мыслить. Например, мы узнали, что: Если программа LP имеет ограниченное оптимальное решение. То оптимальным решением всегда является одна из вершин ее допустимой области (угловая точка). Что нужно сделать. Так это найти все точки пересечения (вершины). А затем исследовать. Какая из всех возможных вершин обеспечивает оптимальное решение. Используя понятия аналитической геометрии. Мы преодолеем эту ограниченность человеческого зрения. Алгебраический метод предназначен для распространения результатов графического метода на многомерную задачу LP. Как показано в следующем численном примере.

Численный Пример: Транспортная задача

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

Рассмотрим модель с 2 источниками и 2 пунктами назначения. Предложение и спрос в каждом месте происхождения (например, склад) O1, O2 и месте назначения (например. Рынок) D1 и D2 вместе с удельными транспортными затратами суммируются в следующей таблице.

Матрица Удельных транспортных Затрат
D1 D2 Поставка
O1 20 30 200
O2 10 40 100
Требовать 150 150 300

Пусть Xij обозначает объем отгрузки от источника i до пункта назначения j. ЛП постановка задачи минимизации общих транспортных затрат заключается в следующем:

Мин 20Х11 + 30Х12 + 10Х21 + 40Х22

при условии:
X11 + X12 = 200
X21 + X22 = 100
X11 + X21 = 150
X12 + X22 = 150
все Xij ³ 0

Обратите внимание. Что допустимая область ограничена. Поэтому можно использовать алгебраический метод. Поскольку эта транспортная проблема является сбалансированной (общее предложение = общий спрос). Все ограничения находятся в форме равенства. Более того, любое из ограничений является избыточным (добавляя любые два ограничения и вычитая другое. Мы получаем оставшееся). Давайте удалим последнее ограничение. Поэтому проблема сводится к:

Мин 20Х11 + 30Х12 + 10Х21 + 40Х22

при условии:
X11 + X12 = 200
X21 + X22 = 100
X11 + X21 = 150
все Xij ³ 0

Эта проблема LP не может быть решена графическим методом. Однако алгебраический метод не имеет ограничений на размерность LP. Ограничения уже находятся в положении привязки (равенства).

Обратите внимание. Что у нас есть m=3 ограничения равенства с (четырьмя подразумеваемыми неотрицательными) переменными решения. Следовательно. Из этих четырех переменных существует не более m=3 переменных с положительным значением. А остальные должны быть на нулевом уровне. Например, установив любую из переменных в свою очередь равным нулю. Мы получим:

X11 X12 X21 X22 Общая Стоимость Транспортировки
0 200 150 -50
неосуществимо
200 0 -50 150 неосуществимо
150 50 0 100 8500
50 150 100 0 6500*

Теперь, установив любую одну (или несколько) переменных равными нулю. Легко увидеть. Проверив ограничения. Что все другие решения неосуществимы. Таким образом. Из приведенной выше таблицы мы получаем оптимальную стратегию: Х11 = 50, Х12 = 150, Х21 = 100 и Х22 = 0, с наименьшими общими транспортными затратами в размере 6500 долларов.

Возможно, вам захочется запустить эту проблему с помощью модуля Net.Exe в вашем пакете WinQSB. Чтобы проверить эти результаты для себя.

Обратите внимание. Что в приведенном выше примере существует m=3 ограничений (исключая условия неотрицательности) и n=4 переменных принятия решений. Оптимальная отгрузка указывает на то. Что менеджер не должен отправлять какую-либо отгрузку из одного источника в один пункт назначения. Оптимальное решение состоит не более чем из 3 положительных переменных решения. Которые равны числу ограничений. Если менеджер отгружает товар из каждого источника в каждый пункт назначения. То результат не является оптимальным.

Приведенные выше результаты. Найденные в приведенном выше примере. Алгебраическим методом можно обобщить. В следующем основном экономическом результате:

Учитывая LP. Имеющую ограниченную допустимую область. С m ограничениями (исключая любые знаковые ограничения. Такие как условия неотрицательности) и n переменными решения. Если n> m тогда не более m решающих переменных имеют положительное значение при оптимальном решении. А остальные (т. Е. n-m) решающих переменных должны быть установлены на нулевом уровне. Этот результат справедлив. Если задача имеет ограниченное единственное оптимальное решение.

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

Численный пример: Найти оптимальное решение следующей производственной задачи с n=3 продуктами и m=1 (ресурсным) ограничением:

Максимизировать 3X1 + 2X2 + X3

При условии: 4X1 + 2X2 + 3X3 £ 12
все переменные Xi ³ 0

Поскольку допустимая область ограничена. Следуя алгебраическому методу. Устанавливая все ограничения в положении привязки. Мы имеем следующую систему уравнений:

4X1 + 2X2 + 3X3 = 12
X1 = 0
X2 = 0
X3 = 0

(Основные) решения. Полученные из этой системы уравнений. Суммируются в следующей таблице.

X1 X2 X3 Итого Чистая Прибыль
0 0 4 4
0 6 0 12*
3 0 0 9
0 0 0 0

Таким образом. Оптимальной стратегией является X1 = 0, X2 = 6, X3 = 0 с максимальной чистой прибылью в размере 12 долларов.

Результат, приведенный в приведенной выше таблице. Согласуется с применением приведенного выше основного экономического результата. Другими словами. Оптимальное решение можно найти. Установив по крайней мере n — m = 3 — 1 = 2 переменные решения равны нулю:

Для крупномасштабных задач LP со многими ограничениями алгебраический метод включает в себя решение многих линейных систем уравнений. Когда задача LP имеет много переменных и ограничений. Решение многих систем уравнений вручную может стать очень утомительным. Даже для очень масштабных задач это невыполнимая задача. Поэтому нам нужен компьютер. Чтобы делать вычисления за нас. Одним из алгоритмических и компьютеризированных подходов является Симплексный метод, что является эффективной и действенной реализацией алгебраического метода. Существует более 400 решателей LP. Все из которых используют симплексный метод. Включая ваше программное обеспечение. При решении задачи ЛП с помощью компьютерных пакетов оптимальное решение обеспечивает ценную информацию. Такую как диапазоны анализа чувствительности.

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

Для получения более подробной информации и численных примеров посетите веб-сайт


Как решить линейную систему уравнений с помощью LP-решателей?

В Алгебраическом методе решения задач LP мы должны решить некоторые системы уравнений. Существует связь между решателями LP и системами решателей уравнений. Предположим. У нас есть очень большая система уравнений. Которую мы хотели бы решить. И пакет решателей LP. Но у нас все еще нет компьютерного пакета решателей для системы уравнений. Вопрос заключается в следующем: Следующие шаги описывают процесс решения любой линейной системы уравнений с использованием доступного LP-решателя.

1 — Поскольку некоторые решатели LP требуют. Чтобы все переменные были неотрицательными. Замените каждую переменную Xi = Yi- T везде.
2 — Создайте фиктивную цель. Такую как минимизация T.
3 — Ограничения задачи LP являются уравнениями в системе после подстановок. Описанных в шаге 1.

Численный пример: Решите следующую систему уравнений

2X1 + X2 = 3
X1 -X2 = 3

Поскольку пакет WinQSB принимает LP в различных форматах ( в отличие от Lindo). Решение этой проблемы с помощью WinQSB является простым:

Во — первых, создайте LP с фиктивной целевой функцией, такой как Max X1, при условии 2X1 + X2 = 3, X1-X2 = 3 и как X1, так и X2 неограниченный в знаке Затем введите этот LP в модуль LP/ILP. Чтобы получить решение. Сгенерированное решение равно X1= 2, X2= -1, что легко проверить подстановкой.

Однако если вы используете любой LP-решатель. Который по умолчанию требует (например, Lindo). Чтобы все переменные были неотрицательными. Вам нужно сделать некоторые приготовления. Чтобы удовлетворить этому требованию: Сначала замените X1 = Y1 — T и X2 = Y2 — T в обоих уравнениях. Нам также нужна целевая функция. Пусть у нас есть фиктивная целевая функция. Такая как минимизация T. В результате получается следующий LP:

Мин Т

При условии:
2Y1 + Y2 — 3T = 3,
Y1 — Y2 = 3.

Используя любой LP-решатель, такой как Линдо, мы находим оптимальное решение Y1 = 3, Y2 = 0, T = 1. Теперь подставим это LP — решение в оба преобразования X1 = Y1 — T и X2 = Y2-T. Следовательно, решение системы уравнений равно X1 = 3 — 1 = 2, X2 = 0 — 1 = -1, что легко проверить подстановкой.


Двойная проблема: Конструкция и ее смысл

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

—————————————————————————
Конструкция Двойной Задачи

Цель: Максимальная (например, прибыль)
Типы ограничений:
£ разумное ограничение
= Ограниченное ограничение

³ необычная константа.
Цель: Минимум (например. Стоимость)
Типы ограничений:
³ разумное ограничение
= Ограниченная константа.
£ необычная константа.
Типы переменных:
³ 0 разумное условие
… un-Restricted in sign
£ 0 необычное состояние

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

Построение Двойной Задачи:

— Если первичное является проблемой максимизации. То его двойственное является проблемой минимизации (и наоборот).

— Используйте тип переменной одной задачи. Чтобы найти тип ограничения другой задачи.

— Используйте тип ограничения одной задачи. Чтобы найти тип переменной другой задачи.

— Элементы RHS одной задачи становятся коэффициентами целевой функции другой задачи (и наоборот).

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

Вы можете проверить свои правила двойных конструкций с помощью пакета WinQSB.

Численные Примеры:

Рассмотрим следующую основную проблему:

мин x1-2×2
при условии:
x1+x2 ³ 2,
x1-x2 £ -1,
x2 ³ 3,
и x1, x2 ³ 0.

Следуя приведенному выше правилу построения. Двойная проблема заключается в следующем::

макс. 2u1 — u2 + 3u3 при
условии:
u1 + u2 £ 1,
u1 — u2 + u3 £ -2,
u1 ³ 0,
u2 £ 0
и u3 ³ 0

Двойственность проблемы плотника:

Максимизировать 5X1 + 3X2

При условии:
2X1 + X2 £ 40
X1 + 2X2 £ 50
Х1 ³ 0
X2 ³ 0

Его двойственность такова:

Минимизировать 40U1 + 50U2

При условии:
2U1 + U2 ³ 5
U1 + 2U2 ³ 3
U1 ³ 0
U2 ³ 0

Приложения: Двойственность можно использовать в самых разных приложениях, включая:

— Возможно, более эффективно решить двойственное. Чем первичное.

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

— Если ограничение в одной задаче не является обязательным (то есть значение LHS совпадает со значением RHS). То связанная переменная в другой задаче равна нулю. Если переменная решения в одной задаче не равна нулю. То связанное с ней ограничение в другой задаче является обязательным. Эти результаты известны как комплементарные условия слабости (CSC).

— Получить диапазон чувствительности РХС одной задачи из диапазона чувствительности стоимостного коэффициента в другой задаче и наоборот.

Эти результаты подразумевают единственно возможные комбинации первичных и двойственных свойств как показано в следующей таблице:

Возможные комбинации Первичных и Двойственных Свойств
Первичная проблема Условие Подразумевает Двойная проблема
Выполнимая; ограниченная цель « Выполнимая; ограниченная цель
Осуществимая; неограниченная цель ® Неосуществимо
Неосуществимо ¬ Осуществимая; неограниченная цель
Неосуществимо « Неосуществимо
Несколько решений « Вырожденное решение
Вырожденное решение « Несколько решений

Обратите внимание. Что почти все решатели LP производят диапазон чувствительности для последних двух случаев; однако эти диапазоны недопустимы. По этой причине вы должны убедиться. Что решение является уникальным и невырожденным при анализе и применении диапазонов чувствительности.

Дальнейшие показания:
Arsham H., An Artificial-Free Simplex Algorithm for General LP Models, Mathematical and Computer Modeling, Vol. 25, No. 1, 107-123, 1997.
Benjamin A., Sensible Rules for Remembering Duals-S-O-B Method, SIAM Review, Vol. 37, No. 1, 85-87, 1995.
Chambers R., Applied Production Analysis: A Dual Approach, Cambridge University Press, 1988.


Двойственная проблема проблемы Плотника и ее интерпретация

В этом разделе мы построим Двойственную задачу задачи Плотника и дадим ее экономическую интерпретацию.

В задаче Плотника неконтролируемыми входными параметрами являются следующие:

Неконтролируемые Входы
Стол Стул Доступно
Труд 2 1 40
исходный материал 1 2 50
чистый доход 5 3

и его формулировка LP как:

Максимизировать 5 X1 + 3 X2

В зависимости от:
2 X1 + X2 £ 40 трудовое ограничение
X1 + 2 X2 £ 50 материальное ограничение
и оба X1, X2 неотрицательны.

Где X1 и X2-количество столов и стульев. Которые нужно сделать.

Предположим. Плотник хочет купить страховку для своего чистого дохода. Пусть U1 = сумма в долларах. Выплачиваемая Плотнику за каждый потерянный рабочий час (например. Из-за болезни). И U2 = сумма в долларах. Выплачиваемая Плотнику за каждую потерянную единицу сырья (например. Из-за пожара).

Страховой офицер пытается свести к минимуму общую сумму в размере $(40U1 + 50U2). Выплачиваемую Столяру страховой компанией. Однако Плотник будет устанавливать ограничения (то есть условия). Настаивая на том. Чтобы страховая компания покрыла все его убытки. Которые являются его чистым доходом. Поскольку он не может производить продукцию. Поэтому проблема страховой компании заключается в том, что:

Минимизировать 40 U1 + 50 U2
При условии:
2U1 + 1U2 ³ 5 Чистый доход от таблицы
1U1 + 2U2 ³ 3 Чистый доход от стула
и U1, U2 неотрицательны.

Реализация этой задачи на вашем компьютерном пакете показывает. Что оптимальным решением является U1 = $7/3 и U2 = $1/3 с оптимальным значением $110 (сумма. Которую Плотник ожидает получить). Это гарантирует. Что Плотник может спокойно управлять своей жизнью. Единственная стоимость-это премия. Которую будет взимать страховая компания.

Теневая цена Единица измерения: Обратите внимание. Что единица измерения теневой цены RHS-это единица измерения первичной цели. Деленная на единицу измерения RHS. Например, для задачи Плотников U1 = [$/week] / hours/week] = $/hour. Таким образом

U1 = 7/3 $/час. А U2 = 1/3 $/единица сырья.

Как видите, проблема страховой компании тесно связана с исходной проблемой.

В терминологии моделирования OR/MS/DS исходная проблема называется Первичной проблемой. В то время как связанная с ней проблема называется ее Двойной проблемой.

В Задаче Плотника и ее Двойственной задаче Оптимальное значение для обеих задач всегда одно и то же. Этот факт называется Равновесие (взято из теории комплементарности. Равновесия экономических систем и эффективности в смысле Парето) между Первичными и Двойственными проблемами. Следовательно, нет никакого разрыва дуальности в линейном программировании.

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

7/3 [ 2X1 + X2 £ 40]
1/3 [ X1 + 2X2 £ 50]
_____________________
5X1 + 3X2 £ 110

Обратите внимание. Что результирующая слева-это целевая функция первичной задачи. И эта нижняя граница для нее является жесткой. Так как оптимальное значение равно 110.

Управленческие Ошибки Округления

Вы должны быть осторожны. Когда округляете значение теневых цен. Например, теневая цена ограничения ресурса в приведенной выше задаче составляет 8/3; поэтому, если вы хотите купить больше этого ресурса. Вы не должны платить больше. Чем $2,66. Всякий раз. Когда вы хотите продать какую-либо единицу этого ресурса. Вы не должны продавать ее по цене ниже 2,67 доллара.

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

Расчет теневых цен

Ты уже знаешь что теневые цены являются решением двойной проблемы Вот числовой пример.

Вычислите теневую цену для обоих ресурсов в следующей задаче LP:

Макс -X1 + 2X2
S. T. X1 + X2 £ 5
Х1 + 2Х2 £ 6
и оба X1, X2 неотрицательные

Решение этой основной задачи (с использованием, например, графического метода) — X1 = 0, X2 = 3, с остатком S1 = 2 первого ресурса. В то время как второй ресурс полностью используется, S2 = 0.

Теневые цены являются решением двойной проблемы:

Мин 5U1 + 6U2
S. T. U1 + U2 ³ -1
U1 + 2U2 ³ 2
и оба U1 и U2 неотрицательны.

Решение двойной задачи (с использованием, например, графического метода) заключается в U1 = 0, U2 = 1, которые являются теневыми ценами на первый и второй ресурс соответственно. Обратите внимание. Что всякий раз. Когда слабина/избыток ограничения ненулевая. Теневая цена. Связанная с этим RHS этого ограничения. Всегда равна нулю; однако обратное утверждение может не выполняться. В этом численном примере S1 = 2 (т. Е. Слабое значение RHS1 первичного). Которое не равно нулю; поэтому U1 равно нулю. Как и ожидалось.

Рассмотрим следующую проблему:

Макс. X1 + X2
при условии:
X1 £ 1
X2 £ 1
Х1 + Х2 £ 2
все переменные решения ³ 0.

Используя свой компьютерный пакет, вы можете убедиться. Что теневая цена третьего ресурса равна нулю, а при оптимальном решении X1 = 1, X2 = 1 остатка этого ресурса нет.


Поведение изменения значений RHS от оптимального значения

Изучить направленные изменения оптимального значения по отношению к изменениям РХС (при отсутствии избыточных ограничений и всех РХС ³0), мы различаем следующие два случая:

Случай I: Проблема максимизации

Для £ ограничение: Изменение происходит в том же направлении. То есть увеличение значения RHS не приводит к уменьшению оптимального значения. Оно увеличивается или остается неизменным в зависимости от того. Является ли ограничение обязательным или необязательным.

Для ³ ограничение: Изменение происходит в обратном направлении. То есть увеличение значения RHS не приводит к увеличению оптимального значения. Оно уменьшается или остается неизменным в зависимости от того. Является ли ограничение обязательным или необязательным.

For = constraint: Изменение может быть в любом направлении (см. раздел Больше-для-меньше).

Случай II: Проблема минимизации

Для £ ограничение типа: Изменение происходит в обратном направлении. То есть, увеличение значения RHS не увеличивает оптимальное значение (скорее. Оно уменьшается или не изменяется в зависимости от того. Является ли ограничение ограничением привязки или нет).

Для ³ ограничение типа: Изменение происходит в том же направлении. То есть увеличение значения RHS не уменьшает оптимальное значение (скорее. Увеличивается или не изменяется в зависимости от того. Является ли ограничение обязательным или необязательным).

For = constraint: Изменение может быть в любом направлении (см. раздел Больше-для-меньше).


Работа с неопределенностями и Сценарное моделирование

Бизнес-среда часто непредсказуема и неопределенна из-за таких факторов. Как экономические изменения. Государственное регулирование. Зависимость от субподрядчиков и поставщиков и т. Д. Менеджеры часто оказываются в динамичной. Неустроенной среде. Где даже краткосрочные планы должны постоянно пересматриваться и постепенно корректироваться. Все это требует менталитета. Ориентированного на изменения. Чтобы справиться с неопределенностью. Помните. Что неожиданность не является элементом надежного решения.

Менеджеры используют математические и вычислительные конструкции (модели) для различных установок и целей. Часто для того. Чтобы получить представление о возможных результатах одного или нескольких курсов действий. Это может касаться финансовых инвестиций. Выбора (стоит ли/сколько) страховать. Производственной практики и воздействия на окружающую среду. Использование моделей ущербно из-за неизбежного наличия неопределенностей. Которые возникают на разных этапах; при построении и подтверждении самой модели. А также при ее использовании. Его использование часто является виновником.

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

Численный пример: Рассмотрим следующую проблему:

Макс 6X1 + 4.01X2 при
условии:
X1 + 2X2 £ 16
3Х1 + 2Х2 £ 24
все переменные принятия решений ³ 0.

Оптимальное решение (Х1 = 4, Х2 = 6). Но при незначительном изменении целевой функции можно получить совершенно другое оптимальное решение. Например, если мы изменим его на 6X1 + 3.99X2, то оптимальным решением будет (X1 = 8, X2 = 0). То есть при уменьшении второго коэффициента на 0,5% решение резко меняется! Поэтому оптимальное решение не является стабильным по отношению к этому входному параметру.

Анализ чувствительности не является типичным термином. Используемым в эконометрике для метода исследования реакции решения на возмущения параметров. В эконометрике процесс изменения значения параметра в модели для того. Чтобы увидеть его индивидуальное влияние на показатель эффективности. Называется сравнительная статика или сравнительная динамика, в зависимости от типа рассматриваемой модели.

Неопределенность в модели может иметь различные истоки в различных задачах принятия решений. Это может быть связано либо с неполной информацией. Либо с колебаниями в самой проблеме. Либо с непредсказуемыми изменениями в будущем. Современные подходы к борьбе с неопределенностями включают в себя:

Сценарный анализ: При таком подходе предполагаются сценарии (например. Определенные комбинации возможных значений неопределенного параметра) и решается задача для каждого из них. Решая задачу многократно для различных сценариев и изучая полученные решения. Менеджер наблюдает за чувствительностью и эвристически принимает решение о приближении. Которое является субъективным.

Анализ наихудшего случая: Этот метод пытается учесть наличие запаса прочности в проблеме на стадии планирования.

Подход Монте-Карло: Стохастические модели предполагают. Что неопределенность известна по ее статистическому распределению.

Анализ чувствительности против Стохастическое программирование: Анализ чувствительности (SA) и формулировки стохастического программирования (SP) являются двумя основными подходами. Используемыми для работы с неопределенностью. SA-это процедура постоптимальности. Не имеющая возможности влиять на решение. Он используется для исследования влияния неопределенности на рекомендации модели. Формулировка СП. С другой стороны. Вводит вероятностную информацию о данных задачи. Хотя и с первыми моментами (т. е. ожидаемыми значениями) распределения целевой функции по отношению к неопределенности. При этом игнорируются оценки риска лиц. Принимающих решения. Характеризующиеся дисперсией. Или коэффициентом вариации.

Можно бороться с неопределенностью более Этот подход называется различными названиями. Такими как Идея состоит в том. Чтобы субъективно составить ранжированный список неопределенностей более высокого уровня. Которые. По-видимому. Могут оказать большее влияние на конечный результат картирования. Это делается перед масштабированием деталей какого-либо конкретного
Элементы проблемы Плотника

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

Управленческие Ошибки Округления: Вы должны быть очень осторожны. Когда вы округляете значение пределов диапазонов чувствительности. Чтобы быть действительным. Верхний предел и нижний предел должны быть округлены соответственно вниз и вверх.

Для построения области анализа чувствительности. Позволяющей анализировать любые типы изменений. В том числе зависимые. Независимые и многократные изменения как значений RHS. Так и стоимостных коэффициентов LP, посетите Построение области общей чувствительности.

Дальнейшие показания:
Аршам Х., алгоритмы чувствительность информацию в дискретно-событийное имитационное моделирование систем, имитационное моделирование теория и практика, 6(1), 1-22, 1998.
Аршам Х., возмущения анализ общей ЛП моделей: единый подход к чувствительности, параметрических, толерантность и многое другое-для-менее анализ, Математическое и компьютерное моделирование, 13(3), 79-102, 1990.
Кувелис п. и Г. Ю., надежные дискретная оптимизация и ее применения, издательством Kluwer академические издатели, 1997. Приводится всестороннее обсуждение мотиваций источников неопределенности при оптимизации.


Вычисление диапазонов чувствительности для задач малых размеров

Чтобы вычислить диапазоны чувствительности для задач LP с не более чем 2 переменными решения и/или не более чем 2 ограничениями. Вы можете попробовать следующий простой в использовании подход.

Единственное ограничение заключается в том. Что никакое ограничение равенства не допускается Наличие ограничения равенства является случаем вырождения, поскольку каждое ограничение равенства, например X1 + X2 = 1, означает два одновременных ограничения: X1 + X2 £ 1 и X1 + X2 ³ 1. Число обязательных ограничений в таком случае будет больше. Чем число переменных решения. Это известно как вырожденная ситуация. Для которой обычный анализ чувствительности может быть недействительным.

Диапазон чувствительности затрат для задач LP с двумя переменными решения

Что касается проблемы Плотника. То изменение прибыли по каждому продукту изменяет наклон целевой функции iso-value. Для Для больших изменений оптимальное решение перемещается в другую точку. Затем мы должны изменить формацию и решить новую задачу.

Задача состоит в том. Чтобы найти диапазон для каждого стоимостного коэффициента c(j) переменной Xj такой. Чтобы текущее оптимальное решение, т. е. Текущая крайняя точка (угловая точка). Оставалась оптимальной.

Для 2-мерной задачи LP вы можете попробовать следующий подход. Чтобы узнать величину увеличения/уменьшения любого из коэффициентов целевой функции (также известных как коэффициенты затрат. Исторически сложилось так. Что во время Второй мировой войны первой проблемой ЛП была проблема минимизации затрат) с целью поддержания обоснованности текущего оптимального решения. Единственное условие. Необходимое для такого подхода. Заключается в том. Что никакое ограничение равенства не допускается, так как это приводит к случаю вырождения, для которого обычный анализ чувствительности может быть недействительным.

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

Шаг 2: Возмущение jth коэффициент затрат по параметру cj (это неизвестное количество изменений).

Шаг 3: Постройте одно уравнение. Соответствующее каждому связывающему ограничению. Следующим образом:

(Возмущенная стоимость Cj)/ коэффициент Xj в ограничении = Коэффициент другой переменной в целевой функции /коэффициент этой переменной ограничения.

Шаг 4: Величина допустимого увеличения равна наименьшему положительному cj. А допустимого уменьшения-наибольшему отрицательному cj. Полученному на шаге 3.

Обратите внимание. Что если нет положительного (отрицательного) cj. То величина увеличения (уменьшения) неограниченна.

Предупреждения:

  1. Помните. Что вы должны никогда не делите на ноль Практика деления на ноль является распространенной ошибкой. Встречающейся в некоторых учебниках. Например, во
    Введении в науку управления,
    Taylor III. B.tice Hall,
    автор. К сожалению. Делит на ноль. В модуле A: Метод симплексного решения, стр. A26-A27, где вычисляется необходимое отношение столбцов в симплексном методе.
    Для получения дополнительной информации об этом и других распространенных заблуждениях посетите веб-сайт Нулевая сага и путаница с числами . Вот вам вопрос: какие из нижеследующих правил верны и почему?
    а) любое число. Деленное на ноль. Не определено;
    б) ноль. Деленный на любое число. Равен нулю;
    в) любое число. Деленное само на себя, равно 1.
  2. Определение диапазона чувствительности к затратам графическим методом: Широко распространено мнение. Что можно вычислить диапазон чувствительности к затратам. Заключив в скобки (возмущенный) наклон целевой функции (iso-value) по наклонам двух линий. Возникающих в результате связывающих ограничений. Этот графический метод. Основанный на наклоне. Для вычисления диапазонов чувствительности описан в популярных учебниках. Таких как Anderson et al., (2007). Lawrence and Pasternack (2002) и Taylor (2010).

    К сожалению. Они вводят в заблуждение. Следовало бы предупредить. Что их подход не является общим и работает тогда и только тогда. Когда коэффициенты не меняют знак.

    В LP с 2 переменными и ограничениями неравенства предположим. Что у нас есть уникальный невырожденный оптимум на пересечении двух линий. Как показано на следующем рисунке. Тогда диапазон объективных коэффициентов. Для которых это решение остается оптимальным. Задается наклонами двух прямых.

    Ниже приведен контрпример. Это указывает на то. Что нужно быть осторожным. Чтобы утверждать. Что коэффициенты не меняют знак.

    Контрпример: Maximixe 5X1 + 3X2
    X1 + X2£ 2,
    X1 — X2£ 0,
    X1³ 0, X2³ 0.

Проблема плотника:

Максимизировать 5X1 + 3X2

При условии:
2X1 + X2 £ 40
X1 + 2X2 £ 50
Х1 ³ 0
X2 ³ 0

Вычисление допустимого увеличения/уменьшения на C1 = 5: Ограничения привязки являются первым и вторым. Возмущая этот коэффициент затрат на c1, мы имеем 5 + c1. На шаге 3 мы имеем:

(5 + c1)/2 = 3/1 для первого ограничения и (5 + c1)/1 = 3/2 для второго ограничения. Решая эти два уравнения. Мы имеем: с1 = 1 и с1 = -3,5. Допустимое увеличение равно 1, а допустимое уменьшение-1,5. Пока первый коэффициент затрат С1 остается в пределах интервала [ 5 — 3.5, 5 + 1] = [1.5. 6]шнее оптимальное решение остается.

Аналогично для второго коэффициента затрат C2 = 3 имеем диапазон чувствительности [2,5, 10].

В качестве другого примера рассмотрим более раннюю проблему:

Максимизировать 5X1 + 3X2

При условии:
X1 + X2 £ 2
Х1 — Х2 £ 0
X1 ³ 0
X2 ³ 0

Вычисление допустимого увеличения/уменьшения на C1 = 5: связующими ограничениями являются первое и второе. Возмущая этот коэффициент затрат на c1, мы имеем 5 + c1. На шаге 3 мы имеем:

(5 + c1)/1 = 3/1 для первого ограничения и (5 + c1)/1 = 3/(-1) для второго ограничения. Решая эти два уравнения. Мы имеем: с1 = -2 и с1 = -8. Допустимое уменьшение равно 2, а допустимое увеличение-неограниченно. Поскольку первый коэффициент затрат С1 остается в интервале [ 5 — 2, 5 + ¥] = [3, ¥], текущее оптимальное решение остается оптимальным.

Аналогично, для второго стоимостного коэффициента C2 = 3 мы имеем диапазон чувствительности
[3 — 8, 3 + 2] = [-5, 5].

Для построения области анализа чувствительности. Позволяющей анализировать любые типы изменений. В том числе зависимые. Независимые и многократные изменения как значений RHS. Так и стоимостных коэффициентов LP, посетите Построение области общей чувствительности.

Диапазон чувствительности RHS для задач LP с не более чем двумя ограничениями

Что касается проблемы Плотника. То для небольших изменений в обоих ресурсах оптимальная стратегия (т. Е. Сделать смешанный продукт) остается в силе. Для больших изменений эта оптимальная стратегия движется. И Плотник должен либо сделать все столы или стулья. Которые он может. Это кардинальное изменение стратегии. Поэтому мы должны пересмотреть формулировку и решить новую проблему.

Помимо приведенной выше необходимой информации. Нам также интересно знать. Сколько Плотник может продать (или купить) каждый ресурс по То есть. Насколько мы можем увеличить или уменьшить RHS(i) для фиксированного i. Сохраняя при этом действительность текущей теневой цены RHS(i)? То есть. Насколько мы можем увеличить или уменьшить RHS(i) для фиксированного i при сохранении текущего оптимального решения двойной задачи?

Исторически теневая цена определялась как улучшение значения целевой функции на единицу прироста в правой части. Поскольку проблема часто ставилась в виде улучшения максимизации прибыли (то есть увеличения).

Кроме того, знайте. Что для любого RHS теневая цена (также известная как ее предельное значение) — это величина изменения оптимальной стоимости пропорционально изменение одной единицы измерения для этого конкретного RHS. Однако в некоторых случаях не разрешается изменять RHS на такую большую величину. Диапазон чувствительности для RHS обеспечивает значения для которых теневая цена имеет такое экономическое значение и остается неизменной.

Как далеко мы можем увеличить или уменьшить каждый отдельный RHS. Чтобы сохранить действительность теневых цен? Этот вопрос эквивалентен вопросу о том. Каков диапазон чувствительности коэффициента затрат в двойной задаче.

Двойственность проблемы Плотника такова:

Минимизировать 40U1 + 50U2

При условии:
2U1 + U2 ³ 5
U1 + 2U2 ³ 3
U1 ³ 0
U2 ³ 0

Оптимальное решение-U1 = 7/3 и U2 = 1/3 (которые являются теневыми ценами).

Проблема плотника:

Максимизировать 5X1 + 3X2

При условии:
2X1 + X2 £ 40
X1 + 2X2 £ 50
Х1 ³ 0
X2 ³ 0

Вычисление дальности действия для RHS1: Поэтому первые два ограничения являются обязательными:

(40 + r1)/2 = 50/1 и (40 + r1) / 1 = 50/2.

Решение этих двух уравнений дает: r1 = 60 и r1 = -15. Таким образом, диапазон чувствительности для первого RHS в задаче плотника равен: [40-15, 40 + 60] = [25, 100].

Аналогично, для второго RHS мы получаем: [50 — 30, 50 + 30] = [20, 80].

Для построения области анализа чувствительности. Позволяющей анализировать любые типы изменений. Включая зависимые. Независимые и многократные изменения как значений RHS. Так и стоимостных коэффициентов LP. Посетите сайт Построения общих областей чувствительности.

Дальнейшие показания:
Лоуренс, младший. Б. Pasternack, прикладная теория управления: моделирование. Анализ таблиц и коммуникации для принятия решений, Джон Уайли и сыновья, 2002.
Андерсон Д., Суини Д., Уильямс т., введение в научный менеджмент, Западный издатель, 2007.
Тейлор III, в Б. Введение в науку управления, Прентис-Холл, 2006.


Маржинальный Анализ и Определение Приоритетов Факторов

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

Маржинальный анализ: Маржинальный анализ-это понятие. Используемое в микроэкономике. Где предельное изменение какого-либо параметра может представлять интерес для лица. Принимающего решение. Предельное изменение-это соотношение очень малого прибавления или вычитания к общему количеству некоторого параметра. Маржинальный анализ-это анализ взаимосвязей между такими изменениями по отношению к показателю эффективности. Примерами маржинального анализа являются: предельные издержки; предельный доход; предельный продукт; предельная норма замещения; предельная склонность к сбережению и т. д. При оптимизации маржинальный анализ используется главным образом для объяснения различных изменений параметров и их влияния на оптимальное значение. Анализ чувствительности. Т. е. анализ влияния малых вариаций параметров системы на выходные показатели. Может быть изучен путем вычисления производных выходных показателей по отношению к параметру.

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

Расстановка приоритетов факторов на основе диапазонов чувствительности: Рассмотрим проблему Плотника:

Максимизировать 5X1 + 3X2

При условии:
2X1 + X2 £ 40
X1 + 2X2 £ 50
Х1 ³ 0

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

Приоритизация факторов с использованием диапазонов чувствительности

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

Влияние изменения РХС на оптимальное значение


Что такое 100% Правило (область чувствительности)

Диапазон чувствительности. Представленный в предыдущем разделе. Представляет собой тип анализа Рассмотрим задачу Плотника; предположим. Что мы хотим найти одновременное допустимое увеличение RHS ( r1, р2 ³ 0). Существует простой метод, известный здесь как

Р1/60 + r2/30 £ 1, 0 £ Р1 £ 60, 0 £ Р2 £ 30.

В приведенном выше, 60 и 30 являются допустимыми повышениями для RHS. Основанными на применении обычного анализа чувствительности. То есть всякий раз. Когда первый и второй RHS увеличиваются на r1 и р2, соответственно. Пока это неравенство сохраняется. Теневые цены для значений RHS остаются неизменными. Обратите внимание. Что это достаточное условие. Так как в случае нарушения вышеуказанного условия теневые цены могут измениться или остаться прежними. Термин Общая сумма таких изменений не должна превышать 100%.

Применяя правило 100% к трем другим возможным изменениям в RHS, мы имеем:

Р1/(-15) + r2/(-30) £ 1, -15 £ Р1 £ 0, -30 £ Р2 £ 0.
Р1/(60) + r2/(-30) £ 1, 0 £ Р1 £ 60, -30 £ Р2 £ 0.
Р1/(-15) + r2/(30) £ 1, -15 £ Р1 £ 0, 0 £ Р2 £ 30.

На следующем рисунке показана область чувствительности для обоих значений RHS как результаты применения правила 100% для задачи Плотника.


С геометрической точки зрения заметим, что многогранник с вершинами (60, 0), (0, 30), (-15. 0),-30) на приведенном выше рисунке является лишь подмножеством большей области чувствительности для изменений обоих значений RHS. Поэтому оставаться в пределах этой области чувствительности-лишь достаточное (но не необходимое) условие для поддержания актуальности текущих теневых цен.

Аналогичные результаты можно получить и для одновременного изменения коэффициентов затрат. Например, предположим. Что мы хотим найти одновременное допустимое уменьшение C1 и увеличивается в С2. То есть сумма изменений обоих коэффициентов затрат на c1 £ 0 и c2 ³ 0.
Правило 100% гласит. Что текущая основа остается оптимальной при условии, что:

с1/(-3.5) + c2/7 £ 1, -3.5 £ с1 £ 0, 0 £ с2£ 7.

Где 3.5 и 7-допустимые уменьшение и увеличение коэффициента затрат С1 и С2 соответственно . Что мы обнаружили ранее при применении обычного анализа чувствительности.

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

В качестве другого численного примера рассмотрим следующую задачу:

Максимизировать 5X1 + 3X2

В зависимости от:
X1 + X2 £ 2
Х1 — Х2 £ 0
X1 ³ 0
X2 ³ 0

Возможно, вы помните. Что мы уже вычислили диапазоны чувствительности с одним изменением за раз для этой задачи в разделе Диапазон чувствительности для первого стоимостного коэффициента составляет [ 5 — 2, 5 + ¥] = [3, ¥], в то время как для второго стоимостного коэффициента это [3 — 8, 3 + 2] = [-5, 5]. Вы должны быть в состоянии воспроизвести фигуру. Аналогичную приведенной выше. Изображающую все другие возможности увеличения/уменьшения значений обоих коэффициентов затрат в результате применения правила 100%. Сохраняя при этом текущее оптимальное решение этой задачи.

Применение правила 100%. Представленного здесь. Является общим и может быть распространено на любую проблему LP большого размера. По мере того как размер проблемы становится больше. Этот тип области чувствительности становится меньше и. Следовательно. Менее полезным для менеджеров. Существуют более мощные (обеспечивающие как необходимые. Так и достаточные условия) и полезные менеджерам методы для зависимого (или независимого) одновременного изменения параметров.

Для построения области анализа чувствительности. Позволяющей анализировать любые типы изменений. В том числе зависимые. Независимые и многократные изменения как значений RHS. Так и стоимостных коэффициентов LP, посетите Построение области общей чувствительности.


Добавление нового ограничения

Процесс: Вставьте текущее оптимальное решение в новое добавленное ограничение. Если ограничение не нарушено. То новое ограничение не влияет на оптимальное решение. В противном случае для получения нового оптимального решения необходимо решить новую задачу.


Удаление ограничения

Процесс: Определите, является ли ограничение обязательным (то есть активным. Важным) ограничением, найдя. Равна ли его слабая/прибавочная стоимость нулю. В случае привязки удаление. Скорее всего. Изменит текущее оптимальное решение. Удалите ограничение и повторно решите проблему. В противном случае (если это не обязательное ограничение) удаление не повлияет на оптимальное решение.


Замена ограничения

Предположим. Мы заменим ограничение новым ограничением. Каков эффект этого обмена?
Процесс: Определите, является ли старое ограничение обязательным (т. Е. активным. Важным) ограничением, выяснив. Является ли его слабая/избыточная стоимость нулевой. В случае связывания замена. Скорее всего. Повлияет на текущее оптимальное решение. Замените ограничение и устраните проблему. В противном случае (если это не связывающее ограничение) определите. Удовлетворяет ли текущее решение новому ограничению. Если это произойдет. То этот обмен не повлияет на оптимальное решение. В противном случае (если текущее решение не удовлетворяет новому ограничению) замените старое ограничение новым и решите проблему.


Изменения коэффициентов ограничений

Любые изменения коэффициентов ограничений могут привести к значительным изменениям номинальной (исходной) задачи. Любые такие изменения логически подпадают под анализ чувствительности. Однако это не те изменения. Которые могут быть проанализированы с использованием информации. Генерируемой оптимальным решением. С такими изменениями лучше всего справиться. Решив модифицированную задачу заново.


Добавление переменной (например. Введение нового продукта)

Коэффициент новой переменной в целевой функции и теневые цены ресурсов дают информацию о предельной стоимости ресурсов и. Зная потребности в ресурсах. Соответствующие новой переменной. Можно принять решение, например. Является ли новый продукт прибыльным или нет.

Процесс: Вычислите, каковы будут ваши потери. Если вы произведете новый продукт. Используя теневые ценовые значения (т. Е. То, что идет на производство нового продукта). Затем сравните его с чистой прибылью. Если прибыль меньше или равна сумме убытка. То НЕ производите новый продукт. В противном случае выгодно производить новый продукт. Выяснение уровня производства нового продукта решает новую проблему.


Удаление переменной (например. Завершение работы продукта)

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


Задача Оптимального Распределения Ресурсов

Поскольку ресурсы всегда скудны. Менеджеры озабочены проблемой оптимального распределения ресурсов. Вы вспомните в Формулировка задачи Плотника состоит в том. Что мы рассматриваем оба ресурса как параметры. То есть как заданные фиксированные числовые значения:

Максимизировать 5 X1 + 3 X2

При условии:
2 X1 + X2 £ 40 ограничение труда
X1 + 2 X2 £ 50 материальное ограничение
и оба X1, X2 неотрицательны.

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

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

Пусть выделенное количество часов равно R. Которое мы хотим использовать при определении его оптимального значения. Поэтому математическая модель должна найти R1 такой, что:

Максимизировать 5 X1 + 3 X2

В зависимости от:
2 X1 + X2 £ R1 трудовое ограничение
X1 + 2 X2 £ 50 материальное ограничение
и все переменные X1, X2 и R1 неотрицательны.

Теперь мы рассматриваем R1 не как параметр. А как переменную. Принимающую решение. То есть максимизация происходит по всем трем переменным: X1, X2 и R1:

Максимизировать 5 X1 + 3 X2

При условии:
2 X1 + X2 — R1 £ 0 ограничение труда
X1 + 2 X2 £ 50 материальное ограничение
и все переменные X1, X2 и R1 неотрицательны.

При использовании программного обеспечения LP оптимальным решением является X1 = 50, X2 = 0 с оптимальным распределением рабочей силы R1 = 100 часов. Это приносит оптимальное значение $250.

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

Допустимое увеличение количества часов составляет 100 — 40 = 60 часов. Что дает дополнительные 250 — 110 = 140.

Используя эту информацию. Мы можем даже получить теневую цену на этот ресурс. Теневая цена-это скорость изменения оптимального значения по отношению к изменению RHS. Поэтому (250 — 110)/(100 — 40) = 140/60 = 7/3, что является теневой ценой RHS1, как мы обнаружили другими методами в предыдущих разделах.


Определение Наименьшей чистой прибыли продукта

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

Возможно, вы помните. Что в Мы рассматривали и чистую прибыль ($5 и $3) как неконтролируемые исходные ресурсы. То есть ценности. Определяемые рынком:

Максимизировать 5 X1 + 3 X2

При условии:
2 X1 + X2 £ 40 трудовое ограничение
X1 + 2 X2 £ 50 материальное ограничение
, и оба X1, X2 неотрицательны.

Это имеет оптимальную стратегию X1 =10, X2 = 20 с оптимальным значением $110.

Предположим. Плотник хочет знать наименьшее значение первого коэффициента в целевой функции. Которое в настоящее время составляет 5 долларов. Чтобы сделать все еще прибыльным производство первого продукта (т. Е. Таблиц).

Предположим. Что наименьшая чистая прибыль составляет c1 долларов; следовательно. Задача состоит в том. Чтобы найти c1 такой, что:

Максимизировать c1 X1 + 3 X2

При условии:
2 X1 + X2 £ 40 ограничение труда
X1 + 2 X2 £ 50 материальное ограничение
И все переменные X1, X2, c1 неотрицательны.

Двойная проблема проблемы Плотника теперь:

Минимизировать 40 U1 + 50 U2
При условии:
2U1 + 1U1 ³ c1 Чистая прибыль по таблице
1U1 + 2U2 ³ 3 Чистая прибыль от стула
И U1, U2, c1 неотрицательны.

Теперь мы рассматриваем чистую прибыль с1 как переменную. Принимающую решение. Минимизация происходит по всем трем переменным: X1, X2 и c1:

Минимизировать 40 U1 + 50 U2
При условии:
2U1 + 1U1 — c1 ³ 0
1U1 + 2U2 ³ 3
И U1, U2, c1 неотрицательны.

Реализация этой задачи на вашем компьютере показывает. Что оптимальным решением является U1 = $7/3, U2 = $1/3 и c1 = $1,5.

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


Min Max и Max Min Вычисление за один запуск

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

В качестве приложения предположим. Что в Задача Плотника, без потери общности, мы имеем три рынка с целевыми функциями 5X1 + 3X2, 7X1 + 2X2 и 4X1 + 4X2 соответственно. Плотник заинтересован в том. Чтобы знать худший рынок. То есть решение следующей задачи:

Проблема Min Max:

При условии:
2 X1 + X2 £ 40
Х1 + 2 Х2 £ 50
и оба X1, X2 неотрицательны.

Задача Min Max эквивалентна:

Макс y

При условии:
y £ 5×1 + 3X2
y £ 7X1 + 2X2
y £ 4X1 + 4X2
2X1 + X2 £ 40
X1 + 2X2 £ 50
И все переменные X1, X2, y неотрицательны.

Если вы перенесете все переменные в левую часть ограничений и реализуете эту задачу в своем компьютерном пакете, то оптимальным решением будет X1 = 10, X2 = 20, y = 110 долларов. Это означает. Что первый и второй рынки являются худшими (потому что первое и второе ограничения являются обязательными). Принося только 110 долларов чистой прибыли.

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


Проблема Осуществимости: Целевые Показатели

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

Хотя некоторые лица. Принимающие решения. Предпочли бы оптимальную. Однако в большинстве практических ситуаций лицо. Принимающее решение. Стремится к удовлетворению или внесению дополнительных изменений. А не к оптимизации. Это так, потому что человеческий разум имеет ограниченную рациональность и. Следовательно. Не может постичь все альтернативы. В инкрементном подходе к принятию решений. менеджер делает только небольшие шаги. Или постепенные шаги. Удаляясь от существующей системы. Обычно это достигается Эта проблема называется Поэтому целью является для достижения глобального улучшения до уровня. Который является достаточно хорошим. Учитывая текущую информацию и ресурсы.

Компоненты целеполагающих решений
Одна из причин. Заставляющих бизнес-менеджера переоценивать важность оптимальной стратегии. Заключается в том. Что организации часто используют показатели в качестве Большинство менеджеров обращают внимание на такие показатели. Как прибыль. Денежный поток. Цена акций и т. Д., чтобы указать на выживание. А не на цель оптимизации.

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

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

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

Численный Пример

Рассмотрим пример 1 в разделе Инициализация симплексного метода сопутствующего сайта для этого сайта. Вместо максимизации мы теперь хотим достичь цели 4. То есть,

Цель: -X1 + 2X2 = 4
при условии:
X1 + X2 ³ 2,
-X1 + X2 ³ 1,
X2 £ 3,
и X1, X2 ³ 0.

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

X1 + X2 — S1 = 2, -X1 + X2 — S2 = 1, X2 + S3 = 3 и
X1, X2, S1, S2, S3 ³ 0.

Решение X1 = 2, X2 = 3, S1 = 3, S2 = 0 и S3 = 0.

Для получения более подробной информации об алгоритмах решения посетите веб-сайт Artificial-variable Free Solution Algorithms.

Дальнейшие показания:
Borden T., and W. Banta, (Ed.), Using Performance Indicators to Guide Strategic Decision Making, Jossey-Bass Pub., 1994.
Эйлон С., Искусство счета: Анализ критериев эффективности, Academic Press, 1984.


Заявление об авторском праве: Добросовестное использование материалов, представленных на этом веб-сайте . В соответствии с Руководящими принципами 1996 года по добросовестному использованию учебных мультимедийныхматериалов допускается только в некоммерческих и аудиторных целях.
Этот сайт может быть зеркально отображен (включая эти уведомления) на любом сервере с открытым доступом. Все файлы доступны по адресу http://home.ubalt.edu/ntsbarsh/Business-stat для зеркального отражения.

Пожалуйста, напишите мне свои замечания. Предложения и проблемы. Спасибо.

Этот сайт был запущен 2/25/1994 года. И его интеллектуальные материалы были тщательно пересмотрены на ежегодной основе. Текущая версия-это 9-яth Издание. Все внешние ссылки проверяются раз в месяц.