标签: linear-programming

我正在研究一个编程问题,它归结为一组方程和不等式:

x[0]*a[0] + x[1]*a[1] + ... x[n]*a[n] >= D
x[0]*b[0] + x[1]*b[1] + ... x[n]*b[n] =  C

我想解决的价值X,这将使的绝对最低C,考虑到输入D和列表,并A与B包括a[0 - n]和b[0 - n ].

我目前在Python中正在解决这个问题,但问题一般是与语言无关.

澄清更新:系数x[0 - n]仅限于非负整数集.

我试图挑选最好的幻想足球队给出不同的约束.我的目标是选择最大化其预测点总和的玩家.

限制是:

1)团队必须包括:

-1 QB

-2个RB

-2 WRs

-1 TE

2)球员的风险不得超过6

3)球员费用总和不得超过300.

我怎样才能做到这一点？R中优化这些约束的最佳包/功能是什么？在给定这些约束的情况下,函数调用的最大化是什么？仅供参考,我将搜索100-300名玩家.

提前致谢!这是一个小示例数据集:

name <- c("Aaron Rodgers","Tom Brady","Arian Foster","Ray Rice","LeSean McCoy","Calvin Johnson","Larry Fitzgerald","Wes Welker","Rob Gronkowski","Jimmy Graham")

pos <- c("QB","QB","RB","RB","RB","WR","WR","WR","TE","TE")

pts <- c(167, 136, 195, 174, 144, 135, 89, 81, 114, 111) 

risk <- c(2.9, 3.4, 0.7, 1.1, 3.5, 5.0, 6.7, 4.7, 3.7, 8.8) 

cost <- c(60, 47, 63, 62, 40, 60, 50, 35, 40, 40) 

mydata <- data.frame(name, pos, pts, risk, cost) 

我正在尝试使用整数线性编程(ILP)实现问题的解决方案.由于问题是NP难的,我想知道Simplex Method提供的解决方案是否是最优的？任何人都可以使用Simplex方法评论ILP的最优性或指向某些来源.是否有其他算法可以为ILP问题提供最佳解决方案？

编辑:我正在寻找对ILP的任何算法(单纯形法,分支和界限和切割平面)获得的解的最优性的是/否答案.

我问了一个问题,可以在这里找到:
计算最佳组合

并且已经建议线性编程.我已经查找了线性编程和Simplex方法.但是我遇到的所有例子都有不等式约束,这些约束使用松弛变量转换成等式.然后,单纯形法交换基本变量和非基本变量以获得最优解.

但我的问题是:

最小化:
x1 + x2 + ... + xn

受制于:
a1*x1 + a1*x2 + a1*x3 + ... + a1*xn = c1;
a2*x1 + a2*x2 + a2*x3 + ... + a2*xn = c2;
a3*x1 + a3*x2 + a3*x3 + ... + a3*xn = c3;

现在我不知道如何在这里应用单纯形法,因为我这里没有任何基本变量.
我也不能只求解线性方程,因为我有n个变量和3个方程.
有人可以建议我一个出路吗？

我正在尝试使用整数规划优化目标函数，我必须Max在我的函数中使用运算符，我想知道有什么办法可以解决这个问题吗？

实际上，我的问题类似于在整数线性程序中使用最小值/最大值，但在某些方面有所不同：

• 所有变量都是二进制的。
• 请注意，x4和x5出现在两个地方。
• 一种可能的解决方案是使用辅助变量，如类似问题的答案，但在我的示例中使用此解决方案时，我感到困惑。

例子：

最小化 (c1 * x1) + (c2 * x2) + (c3 * x3) + Max(c4 * x4, c5 * x5) + (c6 * x4) + (c7 * x5)

受
一些平等和不平等的约束

可再现的例子:

我描述了一个简单的0/1-背包问题lpSolveAPI在ř,它应该返回2级的解决方案:

library(lpSolveAPI)

lp_model= make.lp(0, 3)
set.objfn(lp_model, c(100, 100, 200))
add.constraint(lp_model, c(100,100,200), "<=", 350)
lp.control(lp_model, sense= "max")
set.type(lp_model, 1:3, "binary")

lp_model
solve(lp_model)
get.variables(lp_model)
get.objective(lp_model)
get.constr.value((lp_model))
get.total.iter(lp_model)
get.solutioncount(lp_model)

问题:

但get.solutioncount(lp_model)表明1找到了解决方案:

> lp_model
Model name: 
           C1   C2   C3         
Maximize  100  100  200         
R1        100  100  200  <=  350
Kind      Std  Std  Std         
Type      Int  Int  Int         
Upper       1    1    1         
Lower       0    0    0         
> solve(lp_model)
[1] 0
> get.variables(lp_model)
[1] 1 …

Commons-math（版本2.2）具有LP解算器。

在这里，我找到了以下示例代码：

import java.util.ArrayList;
import java.util.Collection;

import org.apache.commons.math.optimization.GoalType;
import org.apache.commons.math.optimization.OptimizationException;
import org.apache.commons.math.optimization.RealPointValuePair;
import org.apache.commons.math.optimization.linear.LinearConstraint;
import org.apache.commons.math.optimization.linear.LinearObjectiveFunction;
import org.apache.commons.math.optimization.linear.Relationship;
import org.apache.commons.math.optimization.linear.SimplexSolver;

@SuppressWarnings("deprecation")
public class Main {
    @SuppressWarnings({ "rawtypes", "unchecked"})
    public static void main(String[] args) {
        //describe the optimization problem
        LinearObjectiveFunction f = new LinearObjectiveFunction(new double[] { 3, 5}, 0);

        Collection constraints = new ArrayList();
        constraints.add(new LinearConstraint(new double[] { 2, 8}, Relationship.LEQ, 13));
        constraints.add(new LinearConstraint(new double[] { 5, -1}, Relationship.LEQ, 11));

        constraints.add(new LinearConstraint(new double[] { 1, 0}, Relationship.GEQ, 0));
        constraints.add(new LinearConstraint(new …

我发现很难将Excel Solver模型转换为python pulp语法.在我的模型中,我正在优化每个部门的HC和OT变量,目标是最小化OT变量的总和.约束要求HC变量总和不超过92,并且总生产(=E2*C2*D2 + F2*C2在下面的电子表格中)满足每部门要求(下面的Excel电子表格的"输入"列).下面显示的Excel求解器公式非常有效.

问题

1. 如何在纸浆中编写目标函数(在Excel F7 = SUM(F2:F6)中)？
2. 约束E7 <= 92
3. 约束G2:G6> = B2:B6
4. 我有两个决策变量HC和OT.在下面的python代码中,我只创建了一个变量.

之前

解决之后

import pulp
import numpy as np
import pandas as pd

idx = [0, 1, 2, 3, 4]

d = {'Dept': pd.Series(['Receiving', 'Picking', 'PPicking', 'QC', 'Packing'], index=idx),
     'Target': pd.Series([61,94,32,63,116], index=idx),
     'Hrs/day': pd.Series([7.75, 7.75, 7.75, 7.75, 7.75], index=idx),
     'Prod': pd.Series([11733, 13011, 2715, 13682, 14194], index=idx),
     'HC': pd.Series([24,18,6,28,16], index=idx), 
     'OT': pd.Series([0,0,42,0,0], index=idx)}

df = pd.DataFrame(d)

# …

我最近一直在使用 Python 进行线性编程，并且我使用 PuLP 创建了我的第一个优化算法。

我正在处理生产过程的调度问题。目标是通过为一天中的每个小时创建一个理想的生产计划，并为一年中的所有天创建这个计划，从而最大限度地降低每天的生产成本。

我遇到的问题是算法的执行需要很长时间（几个小时）并且经常卡住。另外，我感觉随着时间的推移它会变慢。

我希望得到有关如何提高代码性能的建议。

我对这个问题的处理方法：

• 定义我的最小化问题以创建一整天的最佳时间表。
• 循环我的代码以在一年中的所有 365 天运行此优化。
• 在每个循环结束时，我采用当天优化的生产计划并将其附加到数据帧，因此最后我有一个包含一年中所有日子的生产计划的数据帧。

我正在处理 3 个生产资产（'a'、'l' 和 'o'），每个资产都有几种生产模式。我将每个资产模式组合定义为一个“选项”，总共产生 14 个选项。每个选项每小时都在变化，并且有一个整数值（生产量）和一个二进制值（开/关），产生大约 14 x 2 x 24 = 672 个变量。该问题包含大约 1250 个约束。

我的代码有 200 多行，所以我有点犹豫要不要在这里分享所有内容，但我将在下面分享最重要的部分。

定义供应选项：

def set_supplyoptions():
cols = ['option', 'min_capacity', 'max_capacity']
options_list = [{'option':'o', 'min_capacity': 0, 'max_capacity':146},
                {'option':'l30', 'min_capacity': 0, 'max_capacity':30},
                {'option':'l50', 'min_capacity': 31, 'max_capacity':50},
                {'option':'l90', 'min_capacity': 51, 'max_capacity':90},
                {'option':'l150', 'min_capacity': 91, 'max_capacity':150},
                {'option':'l230', 'min_capacity': 151, 'max_capacity':230},
                {'option':'a15', 'min_capacity': 0, 'max_capacity':15},
                {'option':'a30', 'min_capacity': 0, 'max_capacity':30},
                {'option':'a45', 'min_capacity': 0, 'max_capacity':45}, …

我试图找到一个矩阵的解决方案，其中我知道行和列的总和以及单元格可以具有的最大值。我想找到在限制范围内的可能解决方案。我已经尝试了各种方法，例如构建所有单元格值的数组并按顺序从每个单元格中挑选，但无论我尝试什么，我总是遇到问题，即我用完了单元格的值。我也尝试了递归算法，但我只能得到第一个结果，或者没有得到任何解决方案。我想我必须用回溯算法来做到这一点？没有把握...

任何帮助或指示将不胜感激。

行总和 A、B、C，列总和 X、Y、Z 以及每个的最大值？众所周知。所有值都是正整数。

    C1 | C2 | C3 
-----------------
R1 | ? | ?  | ? | A
-----------------
R2 | ? | ?  | ? | B
-----------------
R3 | ? | ?  | ? | C
-----------------
     X | Y | Z