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

Здесь рассматриваются следующие темы:

Формулировка задачи линейной оптимизации
Решение задачи линейной оптимизации с помощью инструмента "Поиск Решения"
Учет различных ограничений при решении задач линейной оптимизации
Теневые цены.

1

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

Управленческая проблема

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

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

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

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

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

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

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

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

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

2

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

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

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

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

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

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

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

3

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

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

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

Построение математической модели

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

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

Реализация построенной модели в таблице MS Excel

Реализация математической модели в Excel

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

Действительно Михалыч прав! Остатки склада уменьшатся по сравнению с текущим планом на 5,5 тонн, прибыль увеличится почти на 1,5 млн. рублей. Правда, не хватит 5 кг карамели (о том, почему ячека К7 стала красной, смотрите здесь.
Можно выписывать Михалычу премию!
Но может есть вариант получше?

Применение надстройки "Поиск решения" MS Excel к решению задач оптимизации

Для решения задач оптимизации используется надстройка MS Excel Поиск решения.
Введите целевую функцию, переменные и ограничения надстройки в панель Поиска решения и получите результат.

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

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

Прибыль увеличилась на 6,4 миллиона рублей;
Заработан неплохой бонус: почти 1,3 миллиона рублей;
Остатки склада сырья уменьшились до 1,2 тонн.

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

Получите решение в целых числах. Как сильно изменилось решение?

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

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

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

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

Прибыль уменьшилась почти на 100 тыс. рублей.
Заработанный бонус уменьшился на 19 тыс. рублей.
Можно надеяться, что имидж фабрики не пострадает, и чьи-то амбиции будут удовлетворены.

Хороший результат!
Но нет ли лучшего решения?

Вернитесь к первоначальному решению (без "Золотого Батончика"), получите отчет об устойчивости и проанализируйте его.

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

Ячейки переменных
Ограничения

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

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

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

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

Сырье

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

Запасы сырья

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

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

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

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

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

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

Поиск решение, находит новое оптимальное решение, которое может очень сильно отличаться от найденного ранее.

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

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

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

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

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

Максимум

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

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

Минимум

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

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

Значение

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

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

Для того, чтобы "Золотой батончик" попал в оптимальный план необходимо поднять отпукную цену хотя бы на 19, а лучше на 20 рублей.Тоже можно достичь, если снизить издержки его производства.
Для попадания в план "Райского вкуса" и "Первого фанта" отпускная цена должна быть увеличена на 144 руб. и 92 руб. соответственно.
Если отпускную цену "Сибирской белочки" снизить на 24 руб. (или увеличить издержки на ее производство на эту величину), то эта конфета исчезнет из оптимального плана.

Изменение отпускной цены (или рост издержек) на два продукта всего лишь на величину меньше 3% ставит под сомнение включение этих прдуктов в оптимальный план производства! Однако, на все эти показатели молодой человек влиять никак не может, поэтому предложил отцу план, в которой вкличил выпуск 5 тонн "Золотого батончика".

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

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

Решение, учитывающее ограничения: "Ореховый звон" не более 50 тонн, "Золотой батончик" не менее 5 тонн.

Решение, учитывающее ограничения по двум продуктам

Фабрика потеряет в прибыли 1,2 млн. рублей.
Остатки сырья на складе возрастут почти до 6 тонн.
Бонус уменьшится почти на 250 тыс. рублей.

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

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

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

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

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

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

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

Ограничения

ресурсы, которые используются не полностью (выделены зеленым). Финансовые вложения в такие ресурсы не дадут максимальную отдачу на вложенный рубль.
дефицитные ресурcы (выделены красным). Финансовые вложения в такие ресурсы оправданы.
наиболее дефицитный ресурс (сахар) принесет максимальную отдачу на вложенный рубль.

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

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

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

Существует ресурс, увеличение финансирования которого значительно увеличивает прибыль.
Потратив на дозакупку 1 тонны сахара всего 50 тыс. рублей, можно получить увеличение прибыли на 518 тыс.рублей.
Бонус даже за вычетом расходов на дозакупку сахара составил чуть менее 1,09 миллиона рублей.

А что если дополнительно профинансировать и другие дефицитные ресурсы?

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

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

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

Изменение рабочей таблицы в Excel. Новые столбцы.

Изменения в настройках Поиска решения

Найденное оптимальное решение

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

А сколько нужно потратить на дозакупку этого ресурса? Что будет ограничивать объемы этой закупки?

Исследуйте найденное решение на предмет увеличения финансирования ресурса.

Итоговая таблица результатов увеличения финансирования ресурсов

Сводка показателей при увеличении финансирования ресурсов

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

График зависимости реального размера бонуса от вложения в ресурсы

График зависимости размера бонуса от вложений

Бизнес растет;
Растет производство, увеличивается прибыль.

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

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

Продукт	Ореховый звон	Райский вкус	Золотой батончик	Сибирская белочка	Поздний вечер	Первый фант
Нетто вес одной коробки,кг	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 год

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

На главную

Материалы лекций

Фишки MS Excel