# 线性规划作业代写linear programming代考

## 代写线性规划作业linear programming

（1）线性规划的可行域总是一个凸集

（2）目标函数的可行解(包括最优解)一定出现在可行域的一个顶点上

（3）目标函数可以是直线(二维空间)或者超平面(高维空间)的线性变化，所以它的局部最优解实际上就是全局最优解

• 凸优化convex analysis
• 控制理论Control theory
• 数学方法Mathematical methods
• 优化理论 optimazation

## 线性规划的历史

The first example of a linear programming problem in $n$ variables and $n$ constraints taking $2^{n}-1$ iterations to solve was published by Klee \& Minty (1972). Several researchers, including Smale (1983), Borgwardt (1982), Borgwardt (1987a), Adler \& Megiddo (1985), and Todd (1986), have studied the average number of iterations. For a survey of probabilistic methods, the reader should consult Borgwardt (1987b).

Roughly speaking, a class of problems is said to have polynomial complexity if there is a polynomial $p$ for which every problem of “size” $n$ in the class can be solved by some algorithm in at most $p(n)$ operations. For many years it was unknown whether linear programming had polynomial complexity. The Klee-Minty examples

show that, if linear programming is polynomial, then the simplex method is not the algorithm that gives the polynomial bound, since $2^{n}$ is not dominated by any polynomial. In 1979, Khachian (1979) gave a new algorithm for linear programming, called the ellipsoid method, which is polynomial and therefore established once and for all that linear programming has polynomial complexity. The collection of all problem classes having polynomial complexity is usually denoted by $\mathcal{P}$. A class of problems is said to belong to the class $\mathcal{N} \mathcal{P}$ if, given a (proposed) solution, one can verify its optimality in a number of operations that is bounded by some polynomial in the “size” of the problem. Clearly, $\mathcal{P} \subset \mathcal{N} \mathcal{P}$ (since, if we can solve from scratch in a polynomial amount of time, surely we can verify optimality at least that fast). An important problem in theoretical computer science is to determine whether or not $\mathcal{P}$ is a strict subset of $\mathcal{N} \mathcal{P}$.

The study of how difficult it is to solve a class of problems is called complexity theory. Readers interested in pursuing this subject further should consult Garey \& Johnson (1977).

$n$ 变量和 $n$ 约束中的线性规划问题的第一个例子采用 $2^{n}-1$ 次迭代来解决，由 Klee \&薄荷糖 (1972)。几位研究人员，包括 Smale (1983)、Borgwardt (1982)、Borgwardt (1987a)、Adler \& Megiddo (1985) 和 Todd (1986) 研究了平均迭代次数。对于概率方法的调查，参考 Borgwardt 。

## 线性规划linear programming课后作业代写

maximize $4 x_{1}+x_{2}+3 x_{3}$
subject to $x_{1}+4 x_{2} \leq 1$
\begin{aligned} 3 x_{1}-x_{2}+x_{3} & \leq 3 \ x_{1}, x_{2}, x_{3} & \geq 0 \end{aligned}

Our first observation is that every feasible solution provides a lower bound on the optimal objective function value, $\zeta^{}$. For example, the solution $\left(x_{1}, x_{2}, x_{3}\right)=(1,0,0)$ tells us that $\zeta^{} \geq 4$. Using the feasible solution $\left(x_{1}, x_{2}, x_{3}\right)=(0,0,3)$, we see that $\zeta^{*} \geq 9$. But how good is this bound? Is it close to the optimal value? To answer, we need to give upper bounds, which we can find as follows. Let’s multiply the first constraint by 2 and add that to 3 times the second constraint:
\begin{aligned} 2\left(x_{1}+4 x_{2} \quad\right) & \leq 2(1) \ +3\left(3 x_{1}-x_{2}+x_{3}\right) & \leq 3(3) \ 11 x_{1}+5 x_{2}+3 x_{3} & \leq 11 \end{aligned}
Now, since each variable is nonnegative, we can compare the sum against the objective function and notice that
$$4 x_{1}+x_{2}+3 x_{3} \leq 11 x_{1}+5 x_{2}+3 x_{3} \leq 11$$