При решении проблемы оптимизации нам доступно множество инструментов / программ. Я исследовал несколько из них. Я постараюсь показать то же самое для вашего прочтения в надежде, что мое исследование сэкономит вам время и поможет выбрать тот, который лучше всего соответствует вашим потребностям.
Я попытаюсь решить базовую проблему распределения ресурсов, используя все инструменты, которые я выбрал для изучения. Вот моя проблема -
Магазин халвы должен найти оптимальное количество каждого вида халвы для производства, чтобы максимизировать прибыль. Ниже представлены четыре халвы, которые предлагает магазин -
а. Фруктово-ореховая (FN) Халва
б. Смерть от халвы (DH)
c. Куттанад Халва (KH)
d. Керала Черная Халва (KBH)
Для изготовления этих 4 разновидностей халвы используются 5 различных основных ингредиентов. Количество ингредиентов, необходимое на 1 кг халвы, указано в таблице ниже вместе с соответствующей прибылью на кг.
Спрос на халвас FN, DH, KH и KBH составляет 250 кг, 120 кг, 90 кг и 550 кг соответственно. Доступность сырья: майда, сахар, фрукты и орехи, кокосовое молоко и топленое масло - 500 кг, 450 кг, 75 кг, 300 кг и 200 кг соответственно.
Давайте посмотрим, как наша формулировка будет выглядеть на бумаге для указанной выше задачи оптимизации -
Переменные решения
FN = Количество произведенной фруктовой и ореховой халвы
DH = количество произведенной халвы
KH = количество куттанадской халвы, которое будет произведено
KBH = Количество производимой керальской черной халвы
Ограничения
Ограничения спроса
FN < = 250
DH <= 120
KH <= 90
KBH ‹= 550
Ограничения предложения
Майда
0,2 DH + 0,3 FN + 0,4 KBH + 0,4 KH ‹= 500
Сахар
0,5 DH + 0,4 FN + 0,8 KBH + 0,8 KH ‹= 450
Фрукты и орехи
0,3 DH + 0,4 FN + 0,1 KBH + 0,1 KH ‹= 75
Кокосовое молоко
0,3 DH + 0,2 FN + 0,5 KBH + 0,6 KH ‹= 300
Топленое масло
0,5 DH + 0,5 FN + 0,8 KBH + 0,4 KH ‹= 200
Целевая функция
Максимум: 50 * DH + 45 * FN + 10 * KBH + 60 * KH
Приступим к изучению наших инструментов.
Excel
Excel - это наиболее широко используемый инструмент для большинства аналитических задач. В Excel есть плагин решателя, который можно использовать для решения задач оптимизации за нас. Он имеет параметры как симплексного, так и целочисленного программирования. Для целочисленного программирования в Excel используется нелинейный алгоритм GRG. Для этой проблемы мы будем использовать симплексный алгоритм, хотя и симплексный, и GRG в этом случае дадут одинаковый результат.
Вот как наш ввод будет выглядеть в excel -
Переменные решения выделены желтым, а целевая функция - оранжевым. Спрос на каждую халву указан внизу. Эти ячейки будут сравниваться с желтыми, которые представляют собой переменные нашего решения. Необходимое сырье для каждой халвы указано в ячейках ниже. Эти ячейки помогут нам определить общее количество каждого использованного сырья. Мы определим общее количество используемого сырья, умножив количество производимой халвы на необходимое сырье. Например, формула требования для Maida (ячейка H6): «= СУММПРОИЗВ ($ C $ 3: $ F $ 3, C6: F6)»
Затем мы переходим на вкладку «Данные» - ›Решатель
(Если вы не видите Solver, установите надстройку с вкладки File- ›Options)
Вот как будут выглядеть наши параметры решателя -
H15 - это наша прибыль, которую мы хотим максимизировать, изменяя количество произведенной халвы (ячейки C3 - F3), с учетом ограничений спроса и предложения, как указано в окне ограничений. Когда мы нажимаем «решить», мы получаем вот такой результат -
Вышеуказанный результат интерпретируется следующим образом:
Оптимальный производственный план - произвести 75 кг FN, 120 кг DH, 90 кг KH и 0 кг KBH. Общая прибыль при соблюдении вышеуказанного оптимального плана составит 14775. Количество сырья, используемого для достижения этого оптимального производственного плана, составляет 82,5 кг майды, 162 кг сахара, 75 кг фруктов и орехов, 105 кг кокосового молока и 133,5 кг топленого масла. .
Python
Сообщество Python - одно из самых агрессивных сообществ с открытым исходным кодом на сегодняшний день. У нас есть плагины и пакеты Python для всего, от статистического анализа до обслуживания систем. Излишне говорить, что у них тоже есть пакет для оптимизации.
В python мы можем использовать библиотеку под названием «PULP». Код для объявления нашей рецептуры в целлюлозе будет следующим:
my_lp_problem = pulp.LpProblem("Halva",pulp.LpMaximize)
FN = pulp.LpVariable('FN', lowBound=0, cat='Continuous')
DH = pulp.LpVariable('DH', lowBound=0, cat='Continuous')
KH = pulp.LpVariable('KH', lowBound=0, cat='Continuous')
KBH = pulp.LpVariable('KBH', lowBound=0, cat='Continuous')
# Objective function
my_lp_problem += 45 * FN + 50 * DH + 60 * KH + 10 * KBH, "Profit"
# Constraints
my_lp_problem += FN<=250
my_lp_problem += DH<=120
my_lp_problem += KH<=90
my_lp_problem += KBH<=550
my_lp_problem += 0.3*FN+0.2*DH+0.4*KH+0.4*KBH<=500
my_lp_problem += 0.4*FN+0.5*DH+0.8*KH+0.8*KBH<=450
my_lp_problem += 0.4*FN+0.3*DH+0.1*KH+0.1*KBH<=75
my_lp_problem += 0.2*FN+0.3*DH+0.6*KH+0.5*KBH<=300
my_lp_problem += 0.5*FN+0.5*DH+0.4*KH+0.8*KBH<=200
my_lp_problem
Результат для приведенного выше кода будет следующим:
Мы можем решить вышеуказанную формулировку и посмотреть, есть ли у нее оптимальное решение или нет, используя приведенный ниже фрагмент кода:
my_lp_problem.solve() pulp.LpStatus[my_lp_problem.status]
Как только мы получим результат «Оптимальный», мы можем продолжить и распечатать значения для наших переменных решения, используя этот код -
for variable in my_lp_problem.variables():
print("{} = {}".format(variable.name, variable.varValue))
Мы получим следующий результат -
DH = 120.0 FN = 75.0 KBH = 0.0 KH = 90.0
Мы можем напечатать нашу оптимальную прибыль и количество необходимого сырья, используя следующие данные:
print (pulp.value(my_lp_problem.objective))
FN =FN.varValue
DH =DH.varValue
KH =KH.varValue
KBH=KBH.varValue
M=0.3*FN+0.2*DH+0.4*KH+0.4*KBH
S=0.4*FN+0.5*DH+0.8*KH+0.8*KBH
F=0.4*FN+0.3*DH+0.1*KH+0.1*KBH
C=0.2*FN+0.3*DH+0.6*KH+0.5*KBH
G=0.5*FN+0.5*DH+0.4*KH+0.8*KBH
print('Raw material required:-')
print('Maida = '+str(M))
print('Sugar = '+str(S))
print('Fruits and Nuts = '+str(F))
print('Coconut Milk = '+str(C))
print('Ghee = '+str(G))
Мы получим следующий результат
14775.0 Raw material required:- Maida = 82.5 Sugar = 162.0 Fruits and Nuts = 75.0 Coconut Milk = 105.0 Ghee = 133.5
Понятно, что интерпретация полученного результата остается прежней.
CPLEX
Теперь мы подошли к одному из самых мощных инструментов оптимизации; IBM CPLEX. Хотя в нашем небольшом примере мы не увидим никакой разницы в скорости вычислений этих инструментов, когда у нас много переменных, ограничений и нужно выполнить некоторые тяжелые вычисления, CPLEX является предпочтительным инструментом из-за его прочной задней части. инженерное дело.
В CPLEX вы можете иметь свои данные как часть вашей модели (файл .mod) или как часть файла .dat, в котором ваши данные объявлены в нескольких массивах, а код вызывает каждый элемент в массивах один за другим. Я использовал второй подход.
Вот как будет выглядеть наш код для приведенной выше формулировки -
{string} Products = ...;
{string} Components = ...;
float Availability[Products][Components] = ...;
float Profit[Products] = ...;
float Stock[Components] = ...;
float Demand[Products]=...;
dvar float+ Production[Products];
dvar float+ ProfitFrom[Products];
maximize
sum( p in Products )
Profit[p] * Production[p];
subject to {
forall( c in Components )
ct1:
sum( p in Products )
Availability[p][c] * Production[p] <= Stock[c];
ct2:
forall( p in Products )
Production[p]<=Demand[p];
ct3:
forall( p in Products )
ProfitFrom[p] <=Profit[p] * Production[p];
ct4:
forall( p in Products )
ProfitFrom[p] >= Profit[p] * Production[p];
}
Результат будет выглядеть, как показано ниже -
Production = [75 120 90 0]; ProfitFrom = [3375 6000 5400 0];
Интерпретация приведенного выше результата будет -
Оптимальный производственный план - произвести 75 кг FN, 120 кг DH, 90 кг KH и 0 кг KBH. Соответствующая прибыль составит 3375 индийских рупий от FN, 6000 индийских рупий от DH, 5400 индийских рупий от KH и 0 индийских рупий от KBH, что добавляет нас к 14775 индийским рупиям, как указано выше.
GAMS
GAMS - один из ведущих поставщиков инструментов для отрасли оптимизации и первая программная система, в которой язык математической алгебры сочетается с традиционными концепциями программирования для эффективного описания и решения задач оптимизации.
Как и в случае с CPLEX, мы можем использовать данные как часть нашей формулировки отдельных. Я выбрал первый подход к GAMS.
Вот как будет выглядеть код GAMS для приведенной выше формулировки -
*Halva
Positive variables
FN Fruits and nuts Halva
DH Death by Halva
KH Kuttanad Halva
KBH Kerala Black Halva;
Variable
Profit Profit;
Equations obj, FHDemand, DHDemand, KHDemand, KBHDemand, MaidaSupply, SugarSupply, FruitNutSupply, CoconutMilkSupply, GheeSupply;
obj.. Profit =E= 45*FN+50*DH+60*KH+10*KBH;
FHDemand.. FN =L= 250;
DHDemand.. DH =L= 120;
KHDemand.. KH =L= 90;
KBHDemand.. KBH =L= 550;
MaidaSupply.. 0.2*DH + 0.3*FN + 0.4*KBH + 0.4*KH =L= 500;
SugarSupply.. 0.5*DH + 0.4*FN + 0.8*KBH + 0.8*KH =L= 450;
FruitNutSupply.. 0.3*DH + 0.4*FN + 0.1*KBH + 0.1*KH =L= 75;
CoconutMilkSupply.. 0.3*DH + 0.2*FN + 0.5*KBH + 0.6*KH =L= 300;
GheeSupply.. 0.5*DH + 0.5*FN + 0.8*KBH + 0.4*KH =L= 200;
Model HalvaLP /all/;
Solve HalvaLP using LP maximizing Profit;
Display FN.L,DH.L,KH.L,KBH.L,Profit.L;
Несмотря на то, что он генерирует огромные результаты, это было бы нашим интересным результатом -
Интерпретация вышеприведенного вывода будет такой же, как и для excel.
Я надеюсь, это поможет вам. :)
