Решенные бизнес задачи — различия между версиями

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

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

Определите время, необходимое для транспортировки 60000 литров с нефтеперерабатывающего завода в центр хранения, если каждый

день отгружается максимально возможное количество.

Если мощность дуги (2,5) увеличить с 1 до 4, на сколько сократится полученное время?

📺 видео 📺

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Транспортировка_нефти.ipynb»

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

• Создание мощностей для производства этих моделей обойдется в €25000, €35000 и €300000
• Прибыль на единицу продукции составит €10, €15 и €13 соответственно.
• У компании есть три завода для производства этих моделей, но, чтобы избежать затрат, только один из них будет производить игрушки, выбор зависит от максимизации прибыли.

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

Завод      Игрушка1      Игрушка2    Игрушка3

Завод1 5 4 6 Завод2 4 2 2 Завод3 3 3 3

• Мощность завода в человеко-часах на заводах составляют 500, 600 и 630 часов в день соответственно
• Руководство решило разработать хотя бы одну из трех игрушек.
• На само производство останется 30 дней.

Надо максимизировать общую прибыль.

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Планирование_производства_рождественских_игрушек.ipynb»

📺 видео 📺

Российский олигарх решил пожертвовать E=20 единиц нового технологического оборудования для МРТ (магнитно-резонансной томографии) больницам Московской области, и решено, что каждый житель МО, должен иметь доступ к этим МРТ для диагностики.

В Московской области имеется n=25 государственных больниц.

Количество граждан, относящихся к каждой больнице, известно.

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

Наем технического персонала для использования оборудования является обязанностью администрации МО.

• В каждой больнице, где имеется оборудование необходим технический специалист. Стоимость услуг техника составляет Ct=45000.
• Если в больнице
  • один МРТ, то стоимость обслуживания C1=50000
  • больше одного МРТ, то стоимость обслуживания C2=80000
• У администрации бюджет на это все PP=2000000
• Надо, чтобы в каждом районе был хоть один МРТ.
• Чем больше граждан приписаны к больнице, тем приоритетней больница для установки МРТ — больница, имеющая больше граждан, чем какая-то другая, не может иметь меньше МРТ.
• Общее число граждан, приписанных к больнице, деленное на количество МРТ в больнице не должно быть больше М=400000.
• С другой стороны, если больница не имеет собственного МРТ, необходимо распределить граждан этой больницы к другим, имеющим МРТ. Это грустно, и конечно, порождает недовольство, возможно гражданам теперь дольше добираться до новой больницы (в худшем случае, как раз на расстояние между старой и новой больницами).
  • Но если граждане одной больницы переприписаны к другой, расстояние между этими больницами не должно превышать K=50 км (иначе совсем жестоко).

Задача состоит в том, чтобы минимизировать сумму «человеко-километров» по всем перемещенным в другие больницы гражданам.

📺 видео 📺

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Распределение_МРТ_по_больницам.ipynb»

• Участник:Philipakhiarov/Распределение МРТ по больницам

Мы должны купить N=1000 единиц товара. У нас есть три поставщика (A, B и C).

• Первый из них предлагает нам пропорциональную скидку: Три цены (pA1 $/единица, pA2 $/единица, pA3 $/единица), которые будут применяться ко всем единицам в зависимости от количества единиц, которые мы запрашиваем (pA1 > pA2 > pA3), у нас pA1=10, pA2=9, pA3=8. Рассмотрим, соответственно, три интервала: (0, A1], (A1, A2] и (A2, N], (A1=200, A2=5000).

• Второй предлагает нам инкрементную скидку: Три цены (pB1 $/единица, pB2 $/единица, pB3 $/единица, у нас pB1=9.5, pB2=9, PB3=8.5), которые применяются к единицам каждого интервала (pB1 > pB2 > pB3). Интервалы (0, B1], (B1, B2] и (B2, N], соответственно (B1=300, B2=700).

• Третий из них предлагает нам фиксированную цену pC $/единицу (pC=9) и фиксированные скидки: скидка в размере D1$ за заказ свыше C1 единиц и вторую скидку, которая добавляется к первой в размере D2$ при заказе свыше C2 единиц (C1=500, C2=800, D1=300, D2=300).

У кого сколько покупать, чтобы минимизировать стоимость покупки?

📺 видео 📺

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Управление_скидками.ipynb»

StasFomin 01:14, 28 ноября 2022 (UTC): Надо сделать модификацию задачи (генератор?), тут получились скучные цифры.

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

Очень рекомендую, для культуры, прочитать хотя бы первый и самый известный роман — «Цель»

В одном из них, в «Синдроме Стога Сена» на 40 страницах текста без малейшей романтики и лирики рассматривается в цифрах оптимизация некоторого модельного производства, и где «на пальцах» читателя убеждают, что для достижения максимальной прибыли нужно жертвовать локальными оптимумами, и принимать решения, часто интуитивно непонятные. Эту книгу десятилетия любят бизнес-тренеры, и консультанты, перерабатывают ее в тренинги…, см. например, тренинг Сергея Мартыненко или вот (→→→), свежий пост из бизнесового телеграмм-чата

Но если попробовать честно математически сформулировать эту задачу, выясняется, что даже сам Голдратт, пропустил оптимальное решение.

В докладе Стас Фомина была приведена модель на MathML и решение на GLPK (увы, вроде остались только слайды и видео), надо повторить это на Pyomo. Может где-то ее уже на Pyomo и решили (не проверял).

Всю книгу там перечитывать не обязательно, но если прочитаете — это будет совсем незря!

• Участник:Larin.dv/Иголка в стоге сена
• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Иголка_в_стоге_сена.ipynb»

📺 видео 📺

Пусть имеется набор из n=10 производственных задач.

Каждая задача имеет время выполнения.

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

Кроме того:

• Между задачами существуют условные прецеденты: Задача i должна быть обработана после j, если задача t была обработана до i. Это собрано в бинарном атрибуте A_ijt.

• Между задачами нужна перенастройка станка. Если задача i находится на позиции k, а задача j — на позиции k + 1, добавляется дополнительное машинное время, s_ij.

Цель задачи — минимизировать общее время производства.

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Планирование_задач_с_приоритетом_и_временами_перенастройки.ipynb»

📺 видео 📺

• Участник:PankratovViktor/Планирование задач с приоритетом и временами перенастройки

Пусть имеется группа из n=50 человек, с которыми будет создано m=10 рабочих групп.

Каждая группа будет состоять из фиксированного числа людей.

1	2	3	4	5	6	7	8	9	10
5	4	4	3	6	4	5	7	6	6

Некоторые люди знают друг друга.

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

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Группировка_людей.ipynb»

📺 видео 📺

• Blog:Advanced_Algorithms/Разбор_оптимизационной_задачи_«Группировка_людей»

Есть некий регион, с n=25 городами-поселками, который можно представить неориентированным графом дорожной связности, и стоит задача размещения там административных учреждений (МФЦ, госуслуги, и т.п.).

T

лимит административных расходов на эти учреждения → 150000

M

сколько максимально населения можно приписать и обслуживать этим учреждением → 70000

R

если в городе больше R=25000, можно поставить два учреждения.

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

Как обычно, верхнетреугольная матрица расстояний (пусть в километрах)

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

📺 видео 📺

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Размещение_административных_учреждений.ipynb»

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

Площадь блока составляет 25000 м2 (500м в длину на 50м в ширину).

Он собирается построить дома в два ряда (длина каждого ряда 500 м, ширина 20 м) — ну такой классический американский минигородок с одной улицей (симпсоны, саус-парк).

В середине есть участок шириной 10 м для улицы-проезда.

Застройщик должен решить сколько домов построить в каждом ряду в рамках трех моделей:

Элитка

• Отдельные элитные такие дома на участках площадью 400м2 (20м в длину 20м в ширину).

Таунхаус

Совмещенные блоки из двух домов на участках площадью 700м2 (35м в длину 20м в ширину).

Эконом-пенал

Небольшие, но раздельные эконом-домики на участках площадью 200м2 (10м в длину 20м в ширину) для каждого дома.

Стоимость строительства каждого дома равна C_i (i = 1, 2, 3).

 190000 150000 100000

Цена продажи для каждого типа дома составляет B_i.

 250000 200000 120000

Городской совет устанавливает минимальное количество домов каждого типа, m_i.

  4 4 6

• если количество таунхаус-блоков больше, чем количество элитных домов, это влечет за собой дополнительные расходы в размере CA=15000 на каждый дополнительный двухдомный блок.
• «Эконом-пенал» дома могут располагаться только в одном ряду (из двух, требования архитектора).
• Установленный потолок инвестиций составляет TI=3000000 долларов.
• Инвестиционные деньги имеют стоимость CI=3%.
• Застройщик не обязан строить весь ряд — можно строить дома в упор друг-другу, или с промежутками, или вовсе не до конца.

Предложите модель, которая максимизирует выгоду.

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Домостроительство.ipynb»
• 📺 видео 📺

После получения оценок первой оценки ВУЗ рассматривает вопрос об улучшении успеваемости своих учеников по математике.

• Оценка каждого ученика по этому предмету известна, от 0 до 10.
• Закон о персданных конечно запрещает узнать (нам, оптимизаторам) у кого какая оценка, даже под «анонимным номером», но известно, что после разбития на категории, у нас такое грубое распределение студентов:
  • v=1, «неудовлетворительно [0-5]» → 24
  • v=2, «хорошо» [5,7], → 58
  • v=3, «отлично» [7,9], → 11
  • v=4, «блестяще» [9,10] → 7

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

• Для этого, создается 15 учебных групп.
• В каждой группе может быть не более 10 учеников.
• В каждой группе по возможности нужно поместить ученика с «блестящей» оценкой.
• Если в группе нет «блестящих», в ней должно быть по крайней мере, не меньше отличников, чем и в любой группе с «блестящими».
• У группы есть «уровень» $\backslash forall\; j:\; y\_j\; =\; \backslash sum\_\{i=1\}^\{4\}\; v\_i\; x\_\{ij\}$, где x_{ij} — число студентов «уровня i» назначенных в группу «j» — мы, оптимизаторы, работаем только с «уровнями» и «группами», не с отдельными студентами.

Цель состоит в том, чтобы сбалансировать уровень оценок групп, чтобы разница минимального и максимального «уровня» у групп было минимальным.

📺 видео 📺

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Назначение_студентов_в_группы.ipynb»
• Blog:Advanced_Algorithms/Разбор_задачи_«Назначение_студентов_в_группы»

Компания рассматривает возможность производства трех своих продуктов P1, P2 и P3 в одном из мест U1, U2 и U3.

При производстве каждого продукта образуется объем загрязнения в объеме 0,5, 2 и 1 см3, соответственно, на единицу произведенной продукции, независимо от местоположения.

В таблице показаны для каждого из мест:

• удельный доход ($) от каждого продукта,
• суточная производственная мощность (единиц).
• дневная производственная мощность (единиц),
• максимальные объемы загрязнения (см3),
• штраф за превышение объема загрязнения ($/см3).

Компания, осознавая экологические проблемы, предлагает цели с порядком приоритетов:

• Приоритет 1. Максимизировать ежедневный доход.
• Приоритет 2. Не превышать максимальный уровень загрязнения местности.
• Приоритет 3. Компания не хочет тратить более $9000 в день из-за превышения уровня загрязнения.

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

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Управление_загрязняющими_продуктами.ipynb»

📺 видео 📺

• Blog:Advanced_Algorithms/Разбор_задачи_«Управление_загрязняющими_продуктами»

Дано множество из n=15 производственных задач, каждая из которых имеет…

Имеется набор 5 машин для обработки заданий.

• Все задачи должны быть обработаны.
• Задание считается обработанной, если сумма времени обработки на каждой машине равна времени выполнения задания.
• Задание может быть частично обработано не более чем на трех машинах, но всегда одна машина должна обрабатывать не менее одной трети времени выполнения задания.
• Каждое задание, которое обрабатывается на любой машине, приводит к тому, что машина затрачивает время на установку TT=100 плюс время, которое машина обрабатывает задание.

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

Для простоты: Нет необходимости учитывать перекрытие: то есть, нет необходимости

контролировать или решать, когда задача обрабатывается на машине.

📺 видео 📺

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Производство_подразделяемых_задач.ipynb»
• Участник:PankratovViktor/Производство подразделяемых задач

Представим склад на котором надо хранить какие-то артефакты.

На складе есть m мест хранения, каждое из которых поддерживает определенный вес.

m

15

Максимальный вес для места:

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

Есть n=25 артефактов.

Вес артефактов:

Некоторые артефакты совместимы — и их можно размещать в одном месте хранения, если суммарный вес не превышен. Некоторые нельзя — таблица совместимости (1=совместимы), представлена ниже.

Не факт, что вообще удастся разместить все артефакты (ну тогда лишние уедут на другие «Хранилища»), но цель — разместить максимум артефактов (в штуках), т.е. каждому артефакту назначить место, или отказать в хранении.

📺 видео 📺

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Хранение_артефактов_на_складе.ipynb»

• Участник:Robohant/Хранение артефактов на складе

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

В промышленной зоне, где он собирается открыть бизнес, есть шесть складов («i= 1…6»), доступных для аренды.

Бизнесмен начинает бизнес с 50 тонн цемента и пяти автомобилей для транспортировки.

Склады, которые он арендует, должны вмещать как цемент, так и

транспортные средства.

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

Цель состоит в том, чтобы минимизировать общую стоимость аренды на этот год.

📺 видео 📺

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Аренда_склада.ipynb»

• Есть L городов
• Есть n рабочих.
  • Каждый работник живет в определенном городе.
• Есть m рабочих центров, каждый из которых
  • расположен в определенном городе.
  • имеет минимальную и максимальную потребность в работниках.

Надо так назначить работников к производственным центрам, чтобы минимизировать полное расстояние, которое проезжают эти рабочие.

Сколько работников в каждом городе?

Расстояние между 25 городами (расстояния симметричные, представлены верхней треугольной матрицей).

Рабочие центры.

📺 видео 📺

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Распределение_рабочих_по_производственным_центрам.ipynb»

Задан набор из n=40 производственных задач, каждая из которых имеет заданное время обработки.

Стоимость станков, которые выполняют задачи, составляет C=400 за каждый.

• каждое задание обрабатывается на одном станке (не параллелится)
• и станок не может обрабатывать более пяти задач (M) за раз, в день, без отдыха.

Надо:

• чтобы все задачи обрабатывались менее чем за TT=8 ч (машины начинают работать одновременно, и нет задач продолжительностью более 8 ч).
• минимальную стоимость покупки станков.

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Покупка_станков.ipynb»
• Blog:Advanced_Algorithms/Хорошие_практики_компактных_Pyomo-формулировок_на_примере_решения_«Задачи_о_станках»
• Участник:Cherniavskii/BusinessProblems/Покупка_станков

Задан набор из n элементов, каждый из которых целое положительное число.

S = {7 8 2 5 7 1 5 5 9 9 4 3 2 2 1 3 6 3 11 12}

Как поделить их на две максимально равные части?

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Поделить_поровну.ipynb»

📺 видео 📺

• Blog:Advanced_Algorithms/Задача_о_двух_кучах_камней_и_примеры_использования_различных_ЦЛП-солверов

У нас есть 2200 долларов, которые можно инвестировать в течение следующих 5 лет.

В начале каждого года мы можем инвестировать часть денег в депозиты сроком на 1 или 2 года.

По годичным депозитам выплачивается 5% годовых, в то время как по 2-летним депозитам выплачивается 11% в конце 2-х лет.

Кроме того, в начале второго года можно вложить деньги в 3-летние облигации компании А, общая доходность которых составляет 17%.

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

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Капитальные инвестиции.ipynb»

📺 видео 📺

• Blog:Advanced_Algorithms/2022-11-27_Разбор_задачи_«Капитальные_инвестиции»_и_решения_студента

Инвестор владеет долями в различных ценных бумагах.

Более конкретно, он владеет b акций некоторых ценных бумаг A_i, \n 1 \leq i \leq n \in

Текущие цены этих ценных бумаг равны v_i.

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

то есть ценная бумага A_i принесет d_i и будет иметь новую цену w_i.

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

Необходимо обеспечить выполнение определенных условий, которым должен удовлетворять хорошо сбалансированный портфель,

таких как:

• Общий капитал портфеля не должен изменяться при корректировке; то есть общий капитал, который покупается, такой же, как и проданный.
• Портфель должен избегать чрезмерной зависимости от какой-либо одной ценности. Это условие может быть установлено путем требования, чтобы капитал, связанный с какой-либо конкретной ценной бумагой, после корректировки покупки и продажи составлял по меньшей мере определенный процент r% от текущего общего капитала портфеля.
• Общий капитал в будущем должен составлять не менее текущего капитала плюс определенный процент s% от инвестированного в настоящее время капитала.

Для нашей задачи положим r=3%; s=5%;

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Портфель_ценных_бумаг.ipynb»

📺 видео 📺

Торговцу фруктами нужно

• 16 коробок апельсинов,
• 5 коробок бананов
• 20 коробок яблок.

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

Оптовик А отправляет в каждом контейнере по

• 8 коробок апельсинов,
• 1 коробку бананов и
• 2 коробки яблок.

Оптовый продавец B отправляет

• 2 коробки апельсинов,
• одну коробку бананов,
• 7 коробок яблок в каждом контейнере.

Зная, что оптовик А находится в 150 км, а оптовик В - в 300 км, подсчитайте, сколько контейнеров нам придется купить у каждого оптовика, чтобы сэкономить время и свести к минимуму расстояние (каждый контейнер означает поездку).

📺 видео 📺

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Поставка_фруктов.ipynb»

Компания располагает

• 1000 тоннами минерала В1,
• 2000 тоннами минерала В2
• 500 тоннами B3.

Из этих материалов могут быть получены продукты A1, A2 и A3.

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

Далее подробно указывается необходимое количество каждого минерала для получения 1 тонны каждого

продукта и польза, получаемая от каждого из них.

Компания также должна учитывать:

• что он не должен производить более 10 тонн А2, поскольку на рынке не так много спроса.
• что есть компания, которая покупает минерал В2 по цене 20 долларов за тонну.

Максимизируйте прибыль компании.

• Код решения в проекте «adv2022-course-pyomo-business-optimization» в «optprob/Производство_продукта.ipynb»

📺 видео 📺