Метод линейной оптимизации

На этой странице вы узнаете, как построить математическую модель задачи и найти её оптимальное решение. Вы научитесь использовать надстройку "Поиск Решения", читать и анализировать Отчет об устойчивости. Вы будете понимать, в какие продукты (ресурсы) имеет смыл вкладывать деньги для получения лучших результатов, а в какие не имеет смысла.

1

Формулировка математической модели для принятия решения

?
Управленческая проблема
стрелка вниз

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

Это - параметры системы

стрелка вправо

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

Это - переменные Xi

стрелка вправо

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

Это - целевая функция

стрелка вправо

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

Это - ограничения

стрелка вниз

!
Решение и анализ решения

2

Непосредственные задачи оптимизации

Программа-минимум:

Мгновенно вычислять целевую функцию P и другие ключевые показатели при любых интересующих значениях переменных решения (параметров управления) x1, x2, x3...
(Вычисления типа “что, если”)

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

Программа-максимум:

Быстро находить такие значения параметров управления (переменных) x1, x2, x3..., при которых целевая функция P оптимальна, т.е. достигает максимума или минимума (смотря, что интереснее) и все ограничения (требования) удовлетворены.
(Задача оптимизации)

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

3

Кейс: На кондитерской фабрике "Алиса"

Ситуация на фабрике

Кондитерская фабрика «Алиса» должна закрыть цех шоколадных конфет на 2-3 месяца для замены оборудования. Ежедневно цех выпускает 6 видов шоколадных конфет и имеет запасы сырья примерно на 25 суток работы.

технологическая карта фабрики

Директор

Директор за столом Какую продукцию выпустить, чтобы осталось минимум сырья и получить максимальную прибыль?
При выполнении плана Михалыча останется 25 тонн сырья. Это лучше, чем при текущем плане.
Служебная записка
Построение математической модели

Какие данные являютя параметрами системы?

Какие из них можно принять за переменные?

Что принять за целевую функцию?

Выражение для вычисления целевой функции

Сформулировать ограничения

Реализация построенной модели в таблице MS Excel
Реализация математической модели в Excel Математическая модель с формулами
скрепка Проверьте текщий план производства. На сколько дней работы цеха хватит остатков сырья?

Проверка плана Михалыча

Итак, путем подбра параметра, легко установить, что при текущем плане производства через 20 дней работы цеха закончится карамель и останется примерно 30,5 тонн остального сырья. При этом прибыль составит около 25,7 млн. рублей.
А что предлагает Михалыч?
Отказаться от текущего плана, выпустить по 20 тонн каждого продукта, и дополнительно 1,5 тонн конфет "Последний фант". Что при этом удастся выиграть?
Решение Михалыча
Действительно Михалыч прав! Остатки склада уменьшатся по сравнению с текущим планом на 5,5 тонн, прибыль увеличится почти на 1,5 млн. рублей. Правда, не хватит 5 кг карамели (о том, почему ячека К7 стала красной, смотрите здесь.
Можно выписывать Михалычу премию!
Но может есть вариант получше?

Плоды просвящения

Директор за столом Хорошо, если ты уверен, что можешь сделать лучший план, дерзай!
Если твое решение даст больше прибыли, чем план Михалыча, 20% от этой прибавки твои.
Сын директора Папа, в 21 веке такие задачи решают не калькуляторе, а на ноутбуке методом линейной оптимизации.
Если хочешь, я сделаю лучший план.
Применение надстройки "Поиск решения" MS Excel к решению задач оптимизации
скрепка Для решения задач оптимизации используется надстройка MS Excel Поиск решения.
Введите целевую функцию, переменные и ограничения надстройки в панель Поиска решения и получите результат.

Решение, полученное после запуска надстройки

Решение задачи с помощью Поиска решения

Формулы и значения, введеные в поля диалогового окна надстройки Поиск решения.

Данные на панели Поиск решения
Отличный результат!
Но смущает точность расчета "до граммов". Возможно ли получить план выпуска в целых числах?
скрепка Получите решение в целых числах. Как сильно изменилось решение?

Для получения целочисленного решения в надстройке Поиск решения добавим новое ограниечение:

панель Добавление ограничения надстройки Поиск решения

Как видно, решение изменилось незначительно.

панель Добавление ограничения надстройки Поиск решения

Сценарии "что - если ..."

Мы все так любим батончик ...

скрепка Добавьте требование обязательного выпуска не менее 5 тонн конфеты "Золотой батончик".

Фигура молодого человека План получился хорошим! Но почему компьютер отказался выпускать «Золотой Батончик»?
Эта конфета - один из лучших продуктов фабрики. Из-за отсутствия "Батончика" на полках магазинов может пострадать имидж фабрики. Не только я, но и вся моя тусовка любит эту конфету!

Решение, учитывающее требование обязательного выпуска не менее 5 тонн конфеты "Золотой батончик"

Решение, учитывающее выпуск батончика
Хороший результат!
Но нет ли лучшего решения?

Отчет об устойчивости (Sensitivity Report)

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

Панель Результаты поиска
Фигура молодого человека На занятиях по количественным методам в менеджменте, препод все время твердил об анализе полученного оптимального решения на чувствительность к изменениям:
малые изменения величины запасов могут привести к радикальному изменению плана почти без изменения целевого показателя!
Что покажет отчет об устойчивости?
скрепка Вернитесь к первоначальному решению (без "Золотого Батончика"), получите отчет об устойчивости и проанализируйте его.

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

Здесь указаны все продукты

Искомые переменные (план производства)

Удельная прибыль

Данные в этих столбцах показывают, имеет ли смысл менять удельную прибыль и если да, то на сколько

Your browser does not support the HTML5 canvas tag.

Сырье

Расход сырья при найденных переменных

Запасы сырья

Данные в этих столбцах показывают, имеет ли смысл менять запасы сырья и если да, то на сколько

Таблица Ячейки переменных показывает, какие коэффициенты целевой функции имеет смысл менять и на сколько.

Влияние изменений коэффициентов целевой функции. Основные выводы:

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

Если продукт включен в оптимальный план, т.е. переменная Xj > 0

Если продукт не вошел в оптимальный план, т.е. переменная Xj = 0

При этом оптимизировали целевую функцию До:

Всегда имеется верхний и нижний предел для изменения соответствующего коэффициента целевой функции, кроме случая, когда на переменную наложено прямое ограничение:
Xj < a или Xj > b

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

Допустимое уменьшение равно 1Е+30 (бесконечно большое число). Можно как угодно уменьшать целевые коэффициенты - продукт все равно не войдет в оптимальный план.

Допустимое увеличение показывает, насколько нужно увеличить соответствующий целевой коэффициент (прибыль по смыслу), чтобы продукт вошел в оптимальный план.

Допустимое уменьшение показывает, насколько нужно снизить соответствующий целевой коэффициент (издержку по смыслу), чтобы продукт вошел в оптимальный план.

Допустимое увеличение может быть как угодно велико - продукт все равно не войдет в оптимальный план.

Допустимое уменьшение и Допустимое увеличение теряют смысл.

Величина противоположная допустимому увеличению (или уменьшению при минимизации) называется Приведенная (Нормированная) стоимость. Приведенная стоимость показывает, насколько действующая цена продукта ниже минимальной цены (или издержки выше максимальных), при которой продукт выгодно включить в оптимальный план.
    Анализ отчета об устойчивости показал:
  • Для того, чтобы "Золотой батончик" попал в оптимальный план необходимо поднять отпукную цену хотя бы на 19, а лучше на 20 рублей.Тоже можно достичь, если снизить издержки его производства.
  • Для попадания в план "Райского вкуса" и "Первого фанта" отпускная цена должна быть увеличена на 144 руб. и 92 руб. соответственно.
  • Если отпускную цену "Сибирской белочки" снизить на 24 руб. (или увеличить издержки на ее производство на эту величину), то эта конфета исчезнет из оптимального плана.
Изменение отпускной цены (или рост издержек) на два продукта всего лишь на величину меньше 3% ставит под сомнение включение этих прдуктов в оптимальный план производства! Однако, на все эти показатели молодой человек влиять никак не может, поэтому предложил отцу план, в которой вкличил выпуск 5 тонн "Золотого батончика".

Рыночные ограничения

Когда казалось, что все позади, пришло СМС ...

Смс от директора по маркетингу
скрепка Найдите новое решение, учитывающее пожелание отдела маркетинга.
Ораничение по "Золотому батончику" следует сохранить.
Решение, учитывающее ограничения: "Ореховый звон" не более 50 тонн, "Золотой батончик" не менее 5 тонн.
Решение, учитывающее ограничения по двум продуктам
Конечно, все эти потери удручающие. Но пренебрегать рыночными ограничениями неразумно! План производства и расчет прибыли по нему получаются обоснованными только, если эксперты признают соответствующий ему план продаж реалистичным.
Но все ли возможности исчерпаны?

Отчет об устойчивости. Таблица Ограничения.

Таблица Ограничения в отчете об устойчивости наглядно демонстрирует, какие ресурсы и на сколько имеет смысл менять.

Колонка Тень Цена. Что это?

Теневые цены Yi показывают, как меняется целевая функция P при не большом изменении количества ресурсов Δbi: ΔP = Yi * Δbi.
Эти оценки верны только в пределах постоянства теневой цены (при этом численные значения переменных решения Xj, конечно изменяются). Пределы изменения Δbi, в которых теневая цена остается одинаковой, также даны в таблице Ограничения ( столбцы Допустимое увеличение и Допустимое уменьшение количества ресурса).
Причем, если ресурс используется полностью (дефицитный ресурс), существует как верхний, так и нижний предел. Если же ресурс используется не полностью, верхний предел устойчивости равен бесконечности (Excel пишет 1Е+30, что означает 10+30, для программы – это практическая бесконечность).

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

Почему бы не использовать новую возможность?

Молодой человек Дефицитный ресурс - сахар!
Что если его дозакупить?

В соответствии с формулой
ΔP = Yi * Δbi
при Δbi = 1000 кг
(1000 кг - 50000 руб/50 руб/кг)
можно ожидать
ΔP = 518,5 * 1000 = 518,5 тыс. руб.
Или иначе
ΔP = 10,37 * 50000 = 518,5 тыс. руб.
Решение: Дозакупить 1 тонну сахара, потратив 50 тыс. руб. из бонуса!

Оптимаьный план при выполнении решения дозакупить 1 тонну сахара
Решение при добавлении ресурса
А что если дополнительно профинансировать и другие дефицитные ресурсы?
скрепка Найдите решение, отвечающее на вопрос:
сколько каждого вида сырья нужно закупить и сколько конфет разного вида произвести, чтобы максимизировать прибыль?

Добавляем переменные и инвестируем в ресурсы

Изменение рабочей таблицы в Excel. Новые столбцы.
Формулы в добавленных столбцах
Изменения в настройках Поиска решения
Изменение настроек поиска решения
Найденное оптимальное решение
План, учитывающий дозакупку сырья
А сколько нужно потратить на дозакупку этого ресурса? Что будет ограничивать объемы этой закупки?
скрепка Исследуйте найденное решение на предмет увеличения финансирования ресурса.
Итоговая таблица результатов увеличения финансирования ресурсов
Сводка показателей при увеличении финансирования ресурсов

Какие можно сделать выводы из данных таблицы?

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

План, кратный упаковке отгружаемой продукции

Директор за столом Хорошо, ты меня убедил. Фабрика принимает твой план. Можешь вложить 100 тыс. из своего бонуса и купить еще 2 тонны сахара.
Но твой план должен учесть, что продукция отгружается коробками, а не килограммами. Жду окончательного решения!
Продукт Ореховый звон Райский вкус Золотой батончик Сибирская белочка Поздний вечер Первый фант
Нетто вес одной коробки,кг 10 8 6 10 8 6
Решение, учитывающее условие: результат должен быть кратен заданным значениям

Добавим нужные данные в таблицу Excel. Теперь переменные: число упаковок каждого продукта, и эти числа должны быть целыми.

Решение в коробках

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

Продаем неиспользуемое сырье

А что если продать остатки сырья?

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

Как учесть стоимость остатков сырья?

Для учета стоимости остатков нужно изменить целевую функцию. Потому что полную стоимость сырья имеет смысл сопоставлять только с выручкой.
Выручка в данной ситуации может быть и более разумным целевым показателем, поскольку деньги на закупку ресурсов уже потрачены и максимизация прибыли – это максимизация чисто формального показателя. В то время как выручка как раз показывает, сколько денег мы можем извлечь из уже имеющихся ресурсов.
Подсчитать выручку не сложно, нужно план перемножить не на прибыль, а на отпускные цены (B13)
= СУММПРОИЗВ (C9:H9;C13:H13)
.
Кейс Алиса. Учет выручки.
Теперь целевой ячейкой будет B13 (Выручка). После замены целевой ячеки в Поиске Решений и выполния оптимизации, получится новый план выпуска, в результате которого выручка подрастет, а прибыль уменьшится.
Кейс Алиса. Выручка, план оптимизации.
Для учета стоимости остатков сырья в ячейку >К13 = СУММПРОИЗВ ( К4:К8; В4:В8 )
Для учета стоимости активов: Выручка + Стоимость остатков сырья введем в ячеку К15 формулу:
= СУММ( В13+К13 )
Кейс Алиса. Продажа остатков склада
Найдем решение оптимизмрующее активы (Выручка + продажа остатков склада).
Для этого в Поиске Решения в качестве целевой ячейки укажем ячейку К15 и получим окончательное решение.
Кейс Алиса. Продажа остатков склада. Оптимальное решение

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

4

Историческая справка

Канторович Леонид Витальевич (6 (19) января 1912, Санкт-Петербург — 7 апреля 1986, Москва)
Кантарович Леонид Витальевич В 1926 году в возрасте четырнадцати лет поступил в Ленинградский университет. Окончил математический факультет (1930), учился в аспирантуре университета, c 1932 года преподаватель, в 1934 стал профессором, в 1935 году ему присвоена ученая степень доктора физико-математических наук без защиты диссертации.
В 1938 году консультировал фанерный трест по проблеме эффективного использования лущильных станков. Канторович понял, что дело сводится к задаче максимизации линейной формы многих переменных при наличии большого числа ограничений в форме линейных равенств и неравенств. Он модифицировал метод разрешающих множителей Лагранжа для ее решения и понял, что к такого рода задачам сводится колоссальное количество проблем экономики.
В 1939 году опубликовал работу «Математические методы организации и планирования производства», в которой описал задачи экономики, поддающиеся открытому им математическому методу и, тем самым, заложил основы линейного программирования.
В 1949 году стал лауреатом Сталинской премии «за работы по функциональному анализу». 28 марта 1958 года избран членом-корреспондентом АН СССР (экономика и статистика). С 1958 года возглавляет кафедру вычислительной математики. Одновременно возглавлял отдел приближенных вычислений Математического института им. Стеклова Ленинградского отделения АН СССР. В середине 1948 года по распоряжению И. В. Сталина, расчетная группа Канторовича была подключена к разработке ядерного оружия.
С 1960 года жил в Новосибирске, где создал и возглавил Математико-экономическое отделение Института математики СО АН СССР и кафедру вычислительной математики Новосибирского университета. 26 июня 1964 года избран академиком АН СССР (математика). За разработку метода линейного программирования и экономических моделей удостоен в 1965 году вместе с академиком В. С. Немчиновым и профессором В. В. Новожиловым Ленинской премии.
С 1971 года работал в Москве, в Институте управления народным хозяйством Государственного комитета Совета Министров СССР по науке и технике.
1975 год — Нобелевская премия по экономике (совместно с Т. Купмансом «за вклад в теорию оптимального распределения ресурсов»). С 1976 работал во ВНИИ системных исследований Госплана СССР и АН СССР.

Джордж Бернард Данциг (англ. George Bernard Dantzig; 8 ноября 1914 — 13 мая 2005) — математик, разработавший симплексный алгоритм (симплекс-метод). Считается «отцом линейного программирования» (наряду с советским математиком Л. В. Канторовичем).
Джорж Бернард Данциг Ему были присуждены: Национальная Медаль Науки (National Medal of Science) в 1975, Приз Джона фон Неймана (John von Neumann Theory Prize) в 1974. Он был членом Национальной Академии Наук (National Academy of Sciences), Национальной технической Академии (National Academy of Engineering), и американской Академии Искусств и Наук (American Academy of Arts and Sciences).
Он получил степень бакалавра по математике и физике в Университете Мэриленд (University of Maryland) в 1936, степень магистра математики в Университете Мичиган (University of Michigan) и доктора философии в Беркли (UC Berkeley) в 1946.
Отец Данцига, Тобиас Данциг, был российским (латвийским) математиком, который учился у Анри Пуанкаре (Henri Poincaré) в Париже, затем эмигрировал в Соединенные Штаты.

Данциг и Кантарович Тьяллинг Купманс, Джордж Данциг, Леонид Канторович, 1975 год