运筹学（Operation）是近代应用数学的一个分支。它把具体的问题进行数学抽象，然后用像是统计学、数学模型和算法等方法加以解决，以此来寻找复杂问题中的最佳或近似最佳的解答。
作为专业的留学生服务机构，Assignmentexpert™多年来已为美国、英国、加拿大、澳洲等留学热门地的学生提供专业的学术服务，包括但不限于论文代写，A作业代写，Dissertation代写，Report代写，Paper代写，Presentation代写，网课代修等等。为涵盖高中，本科，研究生等海外留学生提供辅导服务，辅导学科包括数学，物理，统计，化学，金融，经济学，会计学等全球99%专业科目。写作团队既有专业英语母语作者，也有海外名校硕博留学生，每位写作老师都拥有过硬的语言能力，专业的学科背景和学术写作经验。我们承诺100%原创，100%专业，100%准时，100%满意。
my-assignmentexpert愿做同学们坚强的后盾，助同学们顺利完成学业，同学们如果在学业上遇到任何问题，请联系my-assignmentexpert™，我们随时为您服务！
运筹学代写
Extensive experience with the simplex procedure applied to problems from various fields, and having various values of $n$ and $m$, has indicated that the method can be expected to converge to an optimum solution in about $m$, or perhaps $3 \mathrm{~m} / 2$, iterations. Thus, particularly if $m$ is much smaller than $n$, that is, if the matrix $\mathbf{A}$ has far fewer rows than columns, only a small fraction of the columns would enter the basis during the course of optimization. However, in a rare worst case (see Chap. 5) the simplex method does need $2^{m}$ iterations to reach the optimum.
To explain this phenomena, we provide an efficiency analysis in this section based on the characteristic property of the basic feasible solution of the constraints. We establish a worst-case iteration upper bound for the simplex method that polyproperty.
Define a characteristic property of a basic feasible solution
Definition (Basic Value Distribution) For a basic feasible solutions, $\mathbf{x}{\mathbf{B}}$, of an LP problem, the sum of its basic variable values is bounded above $\Delta$ (i.e., $\mathbf{1}^{T} \mathbf{x}{\mathbf{B}} \leq \Delta$ ) and its smallest entry is bounded below by $\delta$ (i.e., $\min \left(\mathbf{x}{\mathbf{B}}\right) \geq \delta$ ) for some positive constants $\Delta$ and $\delta$. This property implies that the basic feasible solution is nondegenerate. Clearly, $\Delta / \delta \geq m$, and, when $\Delta / \delta$ is smaller, the basic variable values are more evenly distributed. For the rest materials of this section, we assume that every basic feasible solution has this $(\Delta, \delta)$ property for the linear program in the standard form. We leave the following example as an exercise. Example Consider the dual example 5 of Markov Decision Process in Sect. 3.1. Then every basic feasible solution has the basic value distribution $(\Delta, \delta)$ property with $$ \Delta=\frac{m}{1-\gamma} \quad \text { and } \quad \delta=1 $$ 115 In addition, we abuse notations and also use $\mathbf{B}$ to denote the index set of basic variables and $\mathbf{D}$ to denote the index set of nonbasic variables. Similarly, $\mathbf{B}^{}$ and $\mathbf{D}^{}$ also denote the index sets of optimal basic and nonbasic variables, respectively. We
4.6 Efficiency Analysis of the Simplex Method
first introduce a lemma indicating that the objective gap is reduced at a geometric rate depending on the ratio of $\frac{\delta}{\Delta}$.
Lemma 1 For a feasible linear program in the standard form, let every basic feasible. solution (extreme point) generated by the simplex method have the basic value distribution $(\Delta, \delta)$ property. Then starting from any basic feasible solution $\mathbf{x}^{k}$ with basis $\mathbf{B}^{k}$, the next basic feasible solution, denoted by $\mathbf{x}^{k+1}$ with basis $\mathbf{B}^{k+1}$, has an objective value reduction
$$
\frac{\mathbf{c}^{T} \mathbf{x}^{k+1}-z^{}}{\mathbf{c}^{T} \mathbf{x}^{k}-z^{}} \leq 1-\frac{\delta}{\Delta}
$$
where $z^{}$ represents the minimal objective value of the linear program. Proof Let $\mathbf{r}^{k}$ and $\mathbf{r}^{}$ be the reduced cost vectors corresponding to current basic feasible $\mathbf{x}^{k}$ and optimal solution $\mathbf{x}^{}$, respectively. Note that both $\left(\mathbf{r}^{k}\right)^{T} \mathbf{x}^{k}=0$ and $\left(\mathbf{r}^{}\right)^{T} \mathbf{x}^{}=0$ from complementary slackness. Recall that the incoming variable $x{e}$ is selected such that
$$ r_{e}^{k}=\min {j \in \mathbf{D}^{k}}\left{r{j}^{k}\right}<0, $$ where $\left(\mathbf{r}^{k}\right)^{T}=\mathbf{c}^{T}-\left(\mathbf{y}^{k}\right)^{T} A$ and $\left(\mathbf{y}^{k}\right)^{T}=\mathbf{c}{\mathbf{B}^{k}}^{T}\left(\mathbf{B}^{k}\right)^{-1}$ is the dual solution vector at the current step. Thus, $$ \begin{aligned} \mathbf{c}^{T} \mathbf{x}^{k}-z^{} &=\mathbf{c}^{T} \mathbf{x}^{k}-\mathbf{c}^{T} \mathbf{x}^{} \ &=\left(\mathbf{r}^{k}\right)^{T} \mathbf{x}^{k}-\left(\mathbf{r}^{k}\right)^{T} \mathbf{x}^{} \ &=-\left(\mathbf{r}^{k}\right)^{T} \mathbf{x}^{} \leq-r{e}^{k} \cdot \mathbf{1}^{T} \mathbf{x}^{} \leq\left|r_{e}^{k}\right| \cdot \Delta . \end{aligned} $$ the current step. Thus,
$$
=-\left(\mathbf{r}^{k}\right)^{T} \mathbf{x}^{} \leq-r_{e}^{k} \cdot \mathbf{1}^{T} \mathbf{x}^{} \leq\left|r_{e}^{k}\right| \cdot \Delta .
$$
On the other hand, we have
$$
\begin{aligned}
\mathbf{c}^{T} \mathbf{x}^{k+1}-\mathbf{c}^{T} \mathbf{x}^{k} &=\left(\mathbf{r}^{k}\right)^{T} \mathbf{x}^{k+1}-\left(\mathbf{r}^{k}\right)^{T} \mathbf{x}^{k} \
&=\left(\mathbf{r}^{k}\right)^{T} \mathbf{x}^{k+1}=\sum_{j=1}^{n} r_{j}^{k} \cdot x_{j}^{k+1}=r_{e}^{k} \cdot x_{e}^{k+1} \leq r_{e}^{k} \cdot \delta
\end{aligned}
$$
where we have used facts $\left(\mathbf{r}^{k}\right)^{T} \mathbf{x}^{k}=0$ and only one term is nonzero in the summation. Thus
$$
\left(\mathbf{c}^{T} \mathbf{x}^{k+1}-z^{}\right)-\left(\mathbf{c}^{T} \mathbf{x}^{k}-z^{}\right)=\mathbf{c}^{T} \mathbf{x}^{k+1}-\mathbf{c}^{T} \mathbf{x}^{k} \leq r_{e}^{k} \cdot \delta=-\left|r_{e}^{k}\right| \cdot \delta
$$
or
$$
\frac{\mathbf{c}^{T} \mathbf{x}^{k+1}-z^{}}{\mathbf{c}^{T} \mathbf{x}^{k}-z^{}} \leq 1-\frac{\left|r_{e}^{k}\right| \cdot \delta}{\mathbf{c}^{T} \mathbf{x}^{k}-z^{*}} \leq 1-\frac{\delta}{\Delta}
$$
将单纯形程序应用于各个领域的问题以及具有不同的 $n$ 和 $m$ 值的广泛经验表明，该方法可以预期收敛到大约 $m$，或者可能是 $3 的最优解。 mathrm{~m} / 2$，迭代。因此，特别是如果 $m$ 远小于 $n$，也就是说，如果矩阵 $\mathbf{A}$ 的行数远少于列数，则在计算过程中只有一小部分列会进入基优化。然而，在罕见的最坏情况下（参见第 5 章），单纯形法确实需要 $2^{m}$ 次迭代才能达到最优。
为了解释这种现象，我们在本节中基于约束的基本可行解的特性提供了效率分析。我们为多属性的单纯形法建立了最坏情况的迭代上限。
定义基本可行解的特征属性
定义（基本值分布） 对于 LP 问题的基本可行解 $\mathbf{x}{\mathbf{B}}$，其基本变量值之和在 $\Delta$ 以上有界（即， $\mathbf{1}^{T} \mathbf{x}{\mathbf{B}} \leq \Delta$ ），它的最小入口以 $\delta$ 为界（即 $\min \left( \mathbf{x}{\mathbf{B}}\right) \geq \delta$ ) 对于一些正常数 $\Delta$ 和 $\delta$。 这个性质意味着基本可行解是非退化的。显然，$\Delta / \delta \geq m$，并且当$\Delta / \delta$ 更小时，基本变量值分布更均匀。对于本节的其余材料，我们假设每个基本可行解都具有标准形式的线性程序的 $(\Delta, \delta)$ 属性。 我们将以下示例留作练习。 示例 考虑 Sect 中马尔可夫决策过程的对偶示例 5。 3.1。那么每个基本可行解都具有基本价值分布 $(\Delta, \delta)$ 属性 $$ \Delta=\frac{m}{1-\gamma} \quad \text { 和 } \quad \delta=1 $$ 115 此外，我们滥用符号，还使用 $\mathbf{B}$ 表示基本变量的索引集，使用 $\mathbf{D}$ 表示非基本变量的索引集。类似地，$\mathbf{B}^{}$ 和 $\mathbf{D}^{}$ 也分别表示最优基本变量和非基本变量的索引集。我们
4.6 单纯形法的效率分析
首先引入一个引理，表明目标差距以几何速率减小，具体取决于 $\frac{\delta}{\Delta}$ 的比率。
引理 1 对于标准形式的可行线性规划，令每个基本可行。单纯形法生成的解（极值点）具有基本值分布$(\Delta, \delta)$性质。然后从任何基本可行解 $\mathbf{x}^{k}$ 开始，以 $\mathbf{B}^{k}$ 为基础，下一个基本可行解，记为 $\mathbf{x}^{k+ 1}$ 有基础 $\mathbf{B}^{k+1}$，有一个客观的价值减少
$$
\frac{\mathbf{c}^{T} \mathbf{x}^{k+1}-z^{}}{\mathbf{c}^{T} \mathbf{x}^{k}- z^{}} \leq 1-\frac{\delta}{\Delta}
$$
其中 $z^{}$ 表示线性规划的最小目标值。 证明 令 $\mathbf{r}^{k}$ 和 $\mathbf{r}^{}$ 为当前基本可行 $\mathbf{x}^{k}$ 和最优解 $ 对应的缩减成本向量\mathbf{x}^{}$，分别。注意 $\left(\mathbf{r}^{k}\right)^{T} \mathbf{x}^{k}=0$ 和 $\left(\mathbf{r}^{}\对）^{T} \mathbf{x}^{}=0$ 来自互补松弛。 回想一下，选择传入变量 $x{e}$ 使得
$$ r_{e}^{k}=\min {j \in \mathbf{D}^{k}}\left{r{j}^{k}\right}<0, $$ 其中$\left(\mathbf{r}^{k}\right)^{T}=\mathbf{c}^{T}-\left(\mathbf{y}^{k}\right)^{T} A$ 和 $\left(\mathbf{y}^{k}\right)^{T}=\mathbf{c}{\mathbf{B}^{k}}^{T}\left(\mathbf {B}^{k}\right)^{-1}$ 是当前步骤的对偶解向量。因此，$$ \begin{aligned} \mathbf{c}^{T} \mathbf{x}^{k}-z^{} &=\mathbf{c}^{T} \mathbf{x}^ {k}-\mathbf{c}^{T} \mathbf{x}^{} \ &=\left(\mathbf{r}^{k}\right)^{T} \mathbf{x} ^{k}-\left(\mathbf{r}^{k}\right)^{T} \mathbf{x}^{} \ &=-\left(\mathbf{r}^{k} \right)^{T} \mathbf{x}^{} \leq-r{e}^{k} \cdot \mathbf{1}^{T} \mathbf{x}^{} \leq\左|r_{e}^{k}\右| \cdot \三角洲。 \end{aligned} $$ 当前步骤。因此，
$$
=-\left(\mathbf{r}^{k}\right)^{T} \mathbf{x}^{} \leq-r_{e}^{k} \cdot \mathbf{1}^{ T} \mathbf{x}^{} \leq\left|r_{e}^{k}\right| \cdot \三角洲。
$$
另一方面，我们有
$$
\开始{对齐}
\mathbf{c}^{T} \mathbf{x}^{k+1}-\mathbf{c}^{T} \mathbf{x}^{k} &=\left(\mathbf{r}^ {k}\right)^{T} \mathbf{x}^{k+1}-\left(\mathbf{r}^{k}\right)^{T} \mathbf{x}^{k} \
&=\left(\mathbf{r}^{k}\right)^{T} \mathbf{x}^{k+1}=\sum_{j=1}^{n} r_{j}^{ k} \cdot x_{j}^{k+1}=r_{e}^{k} \cdot x_{e}^{k+1} \leq r_{e}^{k} \cdot \delta
\end{对齐}
$$
其中我们使用了事实 $\left(\mathbf{r}^{k}\right)^{T} \mathbf{x}^{k}=0$ 并且只有一项在求和中是非零的。因此
$$
\left(\mathbf{c}^{T} \mathbf{x}^{k+1}-z^{}\right)-\left(\mathbf{c}^{T} \mathbf{x} ^{k}-z^{}\right)=\mathbf{c}^{T} \mathbf{x}^{k
运筹学代考
什么是运筹学代写
运筹学（OR）是一种解决问题和决策的分析方法，在组织管理中很有用。在运筹学中，问题被分解为基本组成部分，然后通过数学分析按定义的步骤解决。
运筹学的过程大致可以分为以下几个步骤：
- 确定需要解决的问题。
- 围绕问题构建一个类似于现实世界和变量的模型。
- 使用模型得出问题的解决方案。
- 在模型上测试每个解决方案并分析其成功。
- 实施解决实际问题的方法。
与运筹学交叉的学科包括统计分析、管理科学、博弈论、优化理论、人工智能和复杂网络分析。所有这些学科的目标都是解决某一个现实中出现的复杂问题或者用数学的方法为决策提供指导。 运筹学的概念是在二战期间由参与战争的数学家们提出的。二战后，他们意识到在运筹学中使用的技术也可以被应用于解决商业、政府和社会中的问题。
运筹学代写的三个特点
所有运筹学解决实际问题的过程中都具有三个主要特征：
- 优化——运筹学的目的是在给定的条件下达到某一机器或者模型的最佳性能。优化还涉及比较不同选项和缩小潜在最佳选项的范围。
- 模拟—— 这涉及构建模型，以便在应用解决方案刀具体的复杂大规模问题之前之前尝试和测试简单模型的解决方案。
- 概率和统计——这包括使用数学算法和数据挖掘来发现有用的信息和潜在的风险，做出有效的预测并测试可能的解决方法。
运筹学领域提供了比普通软件和数据分析工具更强大的决策方法。此外，运筹学可以根据特定的业务流程或用例进行定制，以确定哪些技术最适合解决问题。
运筹学可以应用于各种活动，比如：计划和时间管理（Planning and Time Management），城乡规划（Urban and Rural Planning），企业资源计划（ERP）与供应链管理（Supply Chain Management）等等。 如有代写代考需求，欢迎同学们联系Assignmentexpert™，我们期待为你服务！
