变量矩阵的线性规划问题
原文作者 Paolo Serafini 单位 University of Udine, Italy Department of Mathematical and Computer Science
摘要：我们考虑的线性规划(连续或整数)问题是：矩阵的某些值是决策参数。如果变量是非负的，那么这个问题直接分成两个阶段解决。结果显示正是因为这些变量使其成为NP难问题。文章最后得到了一个强对偶结果。
关键词：线性规划；变量； 决策参数
- 概要
有一些线性规划问题给定的约束条件并不准确但是可以限定在某些区域里，可以考虑引入决策参数。不同于输入数据的情况下，假定这些未知变量属于一些置信区间，在此区间内不会对其发生影响。这种类型的灵敏度分析可以参考[ 3 ]，[ 4 ]，[ 5 ]，[ 6 ]和[ 8 ]。
在本文中，我们处理了如下的情况：由于一些数据可以在引入决策参数之后固定到精确值。在这个意义上，我们选择引入参数，而不是直接处理这些变量。饮食问题（在[ 4 ]中同时也考虑到了区间数据）是这类问题的一个实例，它由营养物质（y），成分（x）、菜肴（z）组成。成分（x)和营养物质（y）代表的数据可以通过矩阵 联系在一起。成份（x）和菜肴（y）代表的数据都是通过矩阵组成的食谱联系在一起。变量z通常是整数，配方R中的数据通常可以在一定范围变化，并且不会影响这道菜的味道。因此，我们要考虑作为决策变量不只有Y，X和Z，还要考虑矩阵R，因为通过R可以很好的去帮助处理一些变异的数据。
一般混合问题提出了这样的数据变异。如果变化是独立的，且在每个数据项的变量都是非负的，并没有直接的成本矩阵中的条目，那么这个非线性模型，可以分两个阶段通过线性规划求解。如果目标函数包括变量矩阵，那么就成为NP-难问题。据我们所知，这一分析，虽然简单，目前却没有相关的文献研究得到这个结论。
本文的组织如下：在第2节中展示了主要结果，在第3节中提出了一种特别的方式去计算矩阵的条目，在第4节中用一个小例子说明程序，用第5节中所介绍的直接成本关于矩阵的条目，使NP-难问题，终于在第6节得到一个对偶结果。
定理1：如果，则.
证明：如果，那么一定存在一个矩阵A，使得，并且A满足,因此，在和中，唯一存在，即。同理可证另一个，所以得到.
如果，我们已经在之前的（4）中证明了存在这样一个矩阵A。设和是两个矩阵的第i行。根据连续性可以知道这个过程中一定存在一个满足一定函数关系的点x（定义的函数，当,）设为变量（满足且）。设为一个单独的变量。因为满足，此时，只要把合并在一起就能得到矩阵A。
这个证明方式对于其他情况都适用。因此，如果P是一个凸变量，那么X也被限定在这一类中。
如果没有假定X是非负的，那么X一般不是凸变量。在一个简单的例子中，，X从一边变成了另一边。在接下来的结果中出现的这个问题通常很难解决：
定理2：一般的，问题（1）属于NP-难问题。
证明：已知，因此任何的0—1的线性规划问题可以轻易地被转化为一个的线性规划问题，同时每一行可以被转化成，当。
可以从定理1的证明得到，在数据输入时一定存在的一个可行矩阵A，因此接下来应该加入限定条件使得变量非负从而不影响结果，这就需要在这以转变中使得矩阵依靠其他因素发生变化。
在一些特定的可能相关的问题中。例如，他们可能是代表相同的物理量，因此他们必须承担相同的值。如果这项是在不同的行也不能保证这样一个可行矩阵的存在，这里使用的方法显然不奏效。然而，有这类的问题可以很容易地找到替代的模式。例如，假设一个特定的列，并且必须保持他们的相互比值（这可以切实相关），使得可行，如果，并且， 根据d的范围和的定义，我们可以用使得可行，如果来代替，并且得到区间。
- 计算变量矩阵
这个定理根据（3）的x的解决可以计算得到，使得,可行。但是，从（3）中解得的矩阵并不满足（4）的要求。但是因为我们可以找到很多灵活的方法去解决（4），所以我们可以考虑是不是能找到满足特殊情况的矩阵A。一个简单的要求就是将这个矩阵尽可能的靠近规定的值（举个例子:=）。朝着这个目标可以有几个可供选择的方法可以利用。
首先先观察这个问题是不是可以被分解成独立的问题，一个就是考虑行，此外，我们不需要计算合在一起的量（即：）同时他们都是不相关的，因为所有的值相加为零。为了记数，我们把所有的值都计算出来。
一个可能的方法就是基于去求最小值去解决问题
所以接下来我们就得到一个线性规划的问题（对每个）。
这里也许存在一个更好的二次目标函数（更少受变量矩阵的影响），例如：
这些都是连续二次背包问题，连续二次背包问题被布鲁克[2]第一次提出，后来被[ 1 ]和[ 7 ]作为单独的问题，独立出来。在[ 2 ]指出的问题是可以直接解决的为问题。因此，第二阶段在充分考虑矩阵的条目数量的基础上是可以解决线性时间的问题的。
- 一个例子
为了对程序进行说明，我们引入了一个例子。
首先让我们考虑以下多个求和的问题。
当时，
，，
与矩阵的条目的优选值。第一阶段包括在解决如下问题时：
得到结果，。为了计算(只计算变化矩阵，我们运用二次模型，利用布鲁克运算法则得到
- 在矩阵项中的成本系数
我们已经描述了不考虑直接成本的变量矩阵模型。这并不意味着改变一个矩阵项的值不会产生其他影响，引入我们的饮食问题，即以菜肴作为例子，y就是营养物质，x就是成分，而z就是菜，被和组合在一起，可变数据是在R中， R的变化间接影响了x，而x的改变决定了其是否能进入目标函数。
如果我们想评估对于一些优先矩阵，在无论如何改变矩阵元素下的可能性成本，那么我们可以衡量对于x的变化的影响|。
然而，如果我们不需要直接的成本系数矩阵的条目，这要求成为NP-难的问题。为了证明这个事实，我们考虑认识以下这个0-1的线性规划问题：是否存在一个，使得我们要将此问题转化如下：给定一个数k，一个矩阵A，通过指定一些条目来使其上下界发生变化，即，其中在一个特定的M中，成本系数，，，，是否存在，使得，并且
变换如下：首先我们考虑通过进行一个中间转换。因为，是成立的，相当于
（5）
是可行的，其中1是一个单位矩阵。现在让我们考虑以下特殊情况：
（6）
思考是否（6）的解与目标函数值至少满足。
让我们假设对于（6）有这样一个解决方案。注意到每个的总和的上限是，达到这个值的同时有或者。对和所有容许的值都有。这就意味着对于每对，在的总和，肯定能达到。因此，如果有一个解决方案的值是至少（实际上等于）这一定存在，这意味着有一个可行的方案可以解决。
假设现在有一个可行的解决方案解决，这显然对（6）提供了一个值为的解决方案。
6、二元分析
让我们考虑以下对偶的问题
（7）
如果是矩阵的集合，可以允许使用在（7）中，然后问题（1）（在尊重（7）的基础上）就转化为
注意到可以等价地表示为
所以我们有：
当时，定义
极大极小定理不能由于缺乏应用函数的凸性（始终认为是不平等）。如果 ，
我们有
注意到可以等价为
（8）
我们通常可以证明，因此再接下来两个问题中得到一个强二元的结果
定理3：。
证明：我们之前已经证明了
对偶得到
（9）
这足以表明投影到子空间在（9）的可行集与（8）的可行集一致。让和在（9）中可行。然后对任何的，我们有
相反，让在（8）中可行。设和来自特定的矩阵，通过定义其对角元素为单位矩阵有
然后定义
因此有
在之前的不等关系中得到
在这个结果的最佳的双变量和计算求解的观点（3）（P非负）提供一个可变，证明是解决问题（8）和以下对偶最优的问题的最优解答。
（10）
其中是在程序的第二阶段获得最终的矩阵。
外文文献出处：乌迪内大学数学系，意大利
剩余内容已隐藏，支付完成后下载完整资料
英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[287106]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
课题毕业论文、开题报告、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
