Реализация игрушечной модели как задачи линейного программирования

Реализация игрушечной модели как задачи линейного программирования ⇐ Python

1 сообщение • Страница 1 из 1

Anonymous

Реализация игрушечной модели как задачи линейного программирования

Цитата

Сообщение Anonymous » 12 май 2026, 09:53

Я пытаюсь реализовать следующую игрушечную модель как задачу линейного программирования и с нетерпением жду ответа, не пропустил ли я что-нибудь.
Рассмотрим следующую игрушечную модель с тремя фабриками A, B и C, производящими продукты foo и bar.

foo
бар

A
80
20

B
20
40

C
10
5

Мы хотим увеличить общий выпуск систем foo и bar на 50 и 25.
Фабрики не могут уменьшить их выпуск.
Соотношение foo и bar на фабрику фиксировано (например, фабрика A производит 80 единиц foo на 20 единиц бара).
Мы хотим минимизировать относительное изменение выпуска на фабрике.
Если я правильно понимаю, я могу решить этот вопрос с помощью линейного программирования.
Целевая функция: минимизировать z = sum(x_i^*/w_i), где x_i^* — это новый выход для каждой фабрики, а w_i — это базовый выход для каждой фабрики. Обратите внимание, что x_i^* — переменная, а w_i — фиксированная.
Далее, чтобы реализовать эту целевую функцию в linprog, нам нужно переписать целевую функцию в виде c^t @ x:

Код: Выделить всё

minimize z = sum(1/w_i * x_i^*)

, так что c^t = [1/w_a, 1/w_b, 1/w_c] и x = [x_a^*, x_b^*, x_c^*].
Кроме того, нам нужно добавить ограничение, согласно которому новый вывод будет foo = 50 и bar = 25. Для этого транспонируем исходную таблицу, чтобы получить вид:

Код: Выделить всё

array([[80, 20, 10],[20, 40, 5]]) @ [x_a^*, x_b^*, x_c^*] = [50, 25]

Обратите внимание, что, поскольку нам нужно точно соответствовать этому новому выводу, мы используем A_eq и b_eq (вместо A_ub и b_ub).
Более того, обратите внимание, что нам не нужно определять ограничение, чтобы соотношение foo и bar было фиксированным, поскольку переменные решения касаются общего объема выпуска на фабрику, а не вывода на фабрику для каждого продукта индивидуально.
Наконец, сформулировав ограничение как изменение выходных данных (вместо новых выходных значений foo = 110 + 50 = 160 и bar = 65+ 25 = 90 ), мы можем использовать границы по умолчанию, используемые linprog, где переменные решения неотрицательны. Другими словами, нам не нужно явно добавлять ограничение, согласно которому фабрики не могут уменьшать свои вывод.
Я считаю, что это дает нам все, что нам нужно:

Код: Выделить всё

import numpy as np
import pandas as pd
from scipy.optimize import linprog

# Toy model.
df_base = pd.DataFrame([[80, 20], [20, 40], [10, 5]])

# Additional output of foo and bar.
df_scen_s = pd.DataFrame(np.array([50, 25]))

# Get total output per factory: w1, w2, w3.
df_base_s = df_base.sum(axis=1)

# Get coefficients: 1/w1, 1/w2, 1/w3.
df_base_s_inv = 1 / df_base_s

# Linear objective function.
ar_c = df_base_s_inv.values

# Constraint to match new output exactly.
ar_base = df_base.T.values
ar_scen_s = df_scen_s.values

result = linprog(ar_c, A_eq=ar_base, b_eq=ar_scen_s)

print(result.x)

>>> [0.53571429 0.35714286 0.        ]

Здесь мы видим, что фабрика A увеличила выпуск на 54%, а фабрика B — на 36%, в то время как фабрика C не пострадала (выпуск остается на уровне 100%).
Если моя интерпретация этой игрушечной модели в задаче линейного программирования верна, я наблюдаю следующее:
Кажется, что изменение выпуска не распределяется по фабрикам (т.е. фабрика C не затрагивается). Если бы я захотел это сделать, я считаю, что мне нужно пересмотреть целевую функцию, однако я не сразу понимаю, как это сделать.
Интересно, можно ли это сделать с помощью линейного программирования или мне нужно использовать, например, квадратичное программирование, где целевая функция будет выглядеть примерно так: минимизировать z = sum(((x_i^*-w_i)/w_i)^2)), т.е. сумму наименьших квадратов.
РЕДАКТИРОВАТЬ 1:
Моя интуиция целевой функции заключалась в следующем: на фабрику A меньше всего влияют абсолютные изменения, за ней следует фабрика B, затем C. Другими словами, если бы я увеличил выпуск в общей сложности на 10 единиц, A увеличит выпуск на 10%, B на 17% и C на 67%. Таким образом, это будет способствовать увеличению выпуска продукции завода A, затем B, затем C.
Чтобы проверить свою интуицию, я изменил целевую функцию на c^t @ x = [1, 1, 1] @ x. Другими словами, сейчас менять выпуск продукции каждого завода — это одинаково плохо. Это не изменило результат.
Далее я серьезно оштрафовал выходные данные фабрики A: c^t @ x = [10, 1, 1] @ x. Это изменило выпуск на [0, 0, 5], т. е. заводы A и B остаются на уровне 100 %, а завод C увеличивает выпуск на 500 %.
Эту новую целевую функцию можно интерпретировать следующим образом. Скажем, вместо того, чтобы стремиться к минимизации относительных изменений на фабрику, мы стремимся минимизировать общие затраты, при этом фабрика A действительно дорога в эксплуатации, а фабрики B и C одинаково дешевы. Теперь мы бы предпочли передать всю увеличенную производительность фабрике C.
Кроме того, если я правильно понимаю, это подчеркивает, что линейное программирование находит решения в вершинах пространства решений, и, сильно наказывая фабрику A, я заставляю решатель перейти на другую вершину.
Более того, кажется, что целевая функция в этом случае довольно устойчива, поскольку изменения коэффициентов целевой функции, похоже, не влияют на результат, только в крайних случаях.

1778568820

Anonymous

foo
бар

A
80
20

B
20
40

C
10
5

Мы хотим увеличить общий выпуск систем foo и bar на 50 и 25.
Фабрики не могут уменьшить их выпуск.
Соотношение foo и bar на фабрику фиксировано (например, фабрика A производит 80 единиц foo на 20 единиц бара).
Мы хотим минимизировать относительное изменение выпуска на фабрике.
Если я правильно понимаю, я могу решить этот вопрос с помощью линейного программирования.
Целевая функция: минимизировать z = sum(x_i^*/w_i), где x_i^* — это новый выход для каждой фабрики, а w_i — это базовый выход для каждой фабрики. Обратите внимание, что x_i^* — переменная, а w_i — фиксированная.
Далее, чтобы реализовать эту целевую функцию в linprog, нам нужно переписать целевую функцию в виде c^t @ x:
[code]minimize z = sum(1/w_i * x_i^*)[/code] , так что c^t = [1/w_a, 1/w_b, 1/w_c] и x = [x_a^*, x_b^*, x_c^*].
Кроме того, нам нужно добавить ограничение, согласно которому новый вывод будет foo = 50 и bar = 25. Для этого транспонируем исходную таблицу, чтобы получить вид:
[code]array([[80, 20, 10],[20, 40, 5]]) @ [x_a^*, x_b^*, x_c^*] = [50, 25][/code]
Обратите внимание, что, поскольку нам нужно точно соответствовать этому новому выводу, мы используем A_eq и b_eq (вместо A_ub и b_ub).
Более того, обратите внимание, что нам не нужно определять ограничение, чтобы соотношение foo и bar было фиксированным, поскольку переменные решения касаются общего объема выпуска на фабрику, а не вывода на фабрику для каждого продукта индивидуально.
Наконец, сформулировав ограничение как изменение выходных данных (вместо новых выходных значений foo = 110 + 50 = 160 и bar = 65+ 25 = 90 ), мы можем использовать границы по умолчанию, используемые linprog, где переменные решения неотрицательны. Другими словами, нам не нужно явно добавлять ограничение, согласно которому фабрики не могут уменьшать свои вывод.
Я считаю, что это дает нам все, что нам нужно:
[code]import numpy as np
import pandas as pd
from scipy.optimize import linprog

# Toy model.
df_base = pd.DataFrame([[80, 20], [20, 40], [10, 5]])

# Additional output of foo and bar.
df_scen_s = pd.DataFrame(np.array([50, 25]))

# Get total output per factory: w1, w2, w3.
df_base_s = df_base.sum(axis=1)

# Get coefficients: 1/w1, 1/w2, 1/w3.
df_base_s_inv = 1 / df_base_s

# Linear objective function.
ar_c = df_base_s_inv.values

# Constraint to match new output exactly.
ar_base = df_base.T.values
ar_scen_s = df_scen_s.values

result = linprog(ar_c, A_eq=ar_base, b_eq=ar_scen_s)

print(result.x)

>>> [0.53571429 0.35714286 0. ]
[/code]
Здесь мы видим, что фабрика A увеличила выпуск на 54%, а фабрика B — на 36%, в то время как фабрика C не пострадала (выпуск остается на уровне 100%).
Если моя интерпретация этой игрушечной модели в задаче линейного программирования верна, я наблюдаю следующее:
Кажется, что изменение выпуска не распределяется по фабрикам (т.е. фабрика C не затрагивается). Если бы я захотел это сделать, я считаю, что мне нужно пересмотреть целевую функцию, однако я не сразу понимаю, как это сделать.
Интересно, можно ли это сделать с помощью линейного программирования или мне нужно использовать, например, квадратичное программирование, где целевая функция будет выглядеть примерно так: минимизировать z = sum(((x_i^*-w_i)/w_i)^2)), т.е. сумму наименьших квадратов.
РЕДАКТИРОВАТЬ 1:
Моя интуиция целевой функции заключалась в следующем: на фабрику A меньше всего влияют абсолютные изменения, за ней следует фабрика B, затем C. Другими словами, если бы я увеличил выпуск в общей сложности на 10 единиц, A увеличит выпуск на 10%, B на 17% и C на 67%. Таким образом, это будет способствовать увеличению выпуска продукции завода A, затем B, затем C.
Чтобы проверить свою интуицию, я изменил целевую функцию на c^t @ x = [1, 1, 1] @ x. Другими словами, сейчас менять выпуск продукции каждого завода — это одинаково плохо. Это не изменило результат.
Далее я серьезно оштрафовал выходные данные фабрики A: c^t @ x = [10, 1, 1] @ x. Это изменило выпуск на [0, 0, 5], т. е. заводы A и B остаются на уровне 100 %, а завод C увеличивает выпуск на 500 %.
Эту новую целевую функцию можно интерпретировать следующим образом. Скажем, вместо того, чтобы стремиться к минимизации относительных изменений на фабрику, мы стремимся минимизировать общие затраты, при этом фабрика A действительно дорога в эксплуатации, а фабрики B и C одинаково дешевы. Теперь мы бы предпочли передать всю увеличенную производительность фабрике C.
Кроме того, если я правильно понимаю, это подчеркивает, что линейное программирование находит решения в вершинах пространства решений, и, сильно наказывая фабрику A, я заставляю решатель перейти на другую вершину.
Более того, кажется, что целевая функция в этом случае довольно устойчива, поскольку изменения коэффициентов целевой функции, похоже, не влияют на результат, только в крайних случаях.