《高等运筹学》复习题手写解答 Advanced Operations Research: Final Exam:Review Exercises

Nonlinear Program 非线性规划

Problem 29.
Suppose $p<1,p\neq 0$ . Show that the function of
$f(x) ={( \sum_{i=1}^nx_i^p)}^{1/p}$ with $domf = R^n_{++}$ is concave.

Solution

Problem 18.
Let $?$ be a subset of $E^n$ and let $f \in C^2$ be a function on $?$. If $x^?$ is a relative minimum point of $f$ over $?$, then for any $d\in E^n$ that is a feasible direction at $x^?$ we have

1. $\triangledown f(x^*)d\geq 0$
2. if $\triangledown f(x^*)d=0$, then $d^T\triangledown^2 f(x^*)d\geq 0$

Solution
Problem 4.
Find the minimum number of $c$, such that any local optimal solution is a global optimal solution for the following nonlinear program of $P4$.
$P4) \max \ f(x) = ?c?x^2_1 + x_1x_2 + 2x_1 ? \frac{1}{2}x_2^2 \\ s.t. \ \ x_1 ≤ 2$
Solution

KKT condition KKT条件

Problem 3.
Show the KKT condition for the nonlinear program of $P3$, and try to solve it with the KKT conditions.
$P3) \ \max{ \ ?2x^2_1 ?2x_1x_2 ?x^2_2 + 10x_1 + 10x_2} \\ s.t. \ \ \ x^2_1 + x^2_2 ≤ 5 \\ \ \ \ \ \ \ \ 3x_1 + x_2 ≤ 6$
Solution

Golden section method 黄金分割法

Problem 16.
For the problem $\min{f(x)}$ over $x\in [a,b]$, we use golden section method to solve it. Please prove the convergence ratio is $0.618$.

Solution

Newton’s method 牛顿法

Problem 17.
For one dimension nonlinear problem $\min f(x)$ over $x\in [a,b]$, we use Newton’s Method to solve it. Please prove the convergence ratio of Newton’s method is at least two.

Solution

Gradient steepest descent/ ascent method 梯度下降/上升法

*Problem 4.
$\max \ f(x) = ?\frac{1}{2}x^2_1 + x_1x_2 + 2x_1 ? \frac{1}{2}x_2^2 \\$ Use the gradient steepest ascent method to find the optimal solution of above nonlinear program, with the start point $x_0 = (0,4)^T$.

Solution

Integer Programming 整数规划

Branch and bound 分支定界法

Problem 1.
Use branch and bound method to solve $P1)$.
Note that at each branching node, you can use graphic method to get the (local) upper bound for each node.
Draw the branch and bound tree, and point out the Node Program, GLB and LUB clearly.
$P1) \max{\ \ \ 13x_1+5x_2}\\ s.t. \ \ 3x_1+2x_2\leq 6.5\\ -2x_1+3x_2\leq 8\\ x_1,x_2\geq0,integers$
Solution

branch and bound tree

Gomory cutting plane algorithm 割平面法/ Column generation 列生成算法

Problem 26.
$\min \textbf{\textit{c}}^T\textbf{\textit{x}}\\ s.t. \textbf{\textit{Ax}}=\textbf{\textit{b}}\\ \textbf{\textit{x}}\in integer$For above $IP$, suppose now we have a basic feasible solution corresponding to basis matrix $\textbf{\textit{B}}$ and Non-basis $\textbf{\textit{N}}$, i.e., $\textbf{\textit{A}} = (\textbf{\textit{B}},\textbf{\textit{N}})$, and let $a_{ij} = (\textbf{\textit{B}}^{?1}\textbf{\textit{A}}_j)_i$and $a_{i0} = (\textbf{\textit{B}}^{?1}\textbf{\textit{b}})_i$. Prove:
$x_i+\sum_{j\in \textbf{\textit{N}}}\left \lfloor a_{ij} \right \rfloor x_{j}\leq \left \lfloor a_{i0} \right \rfloor$
Solution

Problem 12.
Use the Gomory cutting plane algorithm to solve the following integer linear programming.
$\min \ \ x_1 ?2x_2\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ s.t. \ \ ?4x_1 + 6x_2 ≤ 9 \\ x_1 + x_2 ≤ 4 \\ \ \ \ \ \ \ \ \ \ \ \ \ \ x_1,x_2 ≥ 0, integers$
Solution

Problem 28.
$IP)\min{c^Tx} \\ s.t.\ \ Ax = b \\ x ≥ 0 \ and \in integers$For above $IP$, denote $A = [a_1,a_2,··· ,a_n]$ by columns. Let $k<n$, denote $A_k = [a_1,a_2,··· ,a_k]$.
$IPR)\min{c^Tx} \\ s.t.\ \ Ax = b \\ \ \ \ \ \ \ x ≥ 0$ $IPR_k)\min{c^Tx} \\ s.t.\ \ A_kx = b \\ \ \ \ \ \ \ x ≥ 0$Suppose $x_k^*$, and $x^?$ is the optimal solution for subproblem $IPR_k)$ and $IPR$ respectively, and objectives of $OBJ_{IPR_k}$, $OBJ_{IPR}$ correspondingly. Let $S = \{a_1,a_2,··· ,a_n\}$, B is the basis related to $x^?_k$ for $IPR_k.
$PP)\min c_a ?c_BB^{?1}a\\ s.t.\ \ a \in S$Please prove: If $OBJ_{PP} ≥ 0$, then $OBJ_{IPR_k} = OBJ_{IPR}$

Solution

Dynamic programming 动态规划

IP 有整数约束

Problem 8.
Use dynamic programming method to solve the following integer programming.
$\max {\ \ 2x_1 + 3x_2 + x_3 + 2x_4}\\ \ \ \ \ \ \ \ \ \ \ \ \ s.t. \ \ \ 5x_1 + 7x_2 + 6x_3 + 5x_4 ≤ 14\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ x_1,x_2,x_3,x_4 ≥ 0, integers$Note that you need to point out recursive formula clearly, and write down calculation steps clearly.

Solution

LP 无整数约束

*Problem 8.
Use dynamic programming method to solve the following linear programming.
$\max {\ \ 2x_1 + 3x_2 + x_3 + 2x_4}\\ \ \ \ \ \ \ \ \ \ \ \ \ s.t. \ \ \ 5x_1 + 7x_2 + 6x_3 + 5x_4 ≤ 14\\ \ \ \ \ x_1,x_2,x_3,x_4 ≥ 0,$Note that you need to point out recursive formula clearly, and write down calculation steps clearly.

Solution

Linear programming 线性规划

Central path 中心路径法（内点法）

Problem 25.
Let $(x(\mu),y(\mu),s(\mu))$ be the central path of
$x?s = \mu e\\ Ax = b\\ A^Ty + s = c\\ x ≥ 0,s ≥ 0$ Then prove:
(a) The central path point $(x(\mu),y(\mu),s(\mu))$ is bounded for $0 < \mu ≤ \mu_0$ and any given $0 < \mu < ∞$.
(b) For $0 < {\mu}'< \mu$,
$c^Tx( {\mu}') ≤ c^Tx(\mu)\ \ and\ \ b^Ty( {\mu}') ≥ b^Ty(?)$Furthermore, if $x( {\mu}')\neq x(\mu)$ and $y( {\mu}')\neq y(\mu)$.
$c^Tx( {\mu}') < c^Tx(\mu)\ \ and\ \ b^Ty( {\mu}') > b^Ty(?)$
Solution

Problem 11.
Compute the central path for the following linear programming.
$\min{\ x_1} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \\ s.t. \ \ x_1 + x_2 + x_3 = 2$
Solution

Karmarkar算法（内点法）

Problem 6.
What are the differences between Karmarkar method and Simplex method for linear programming? Please show the logics of them clearly. Possibly you can use figures to show what your idea.

Solution

Eliposoid method 椭球法（外点法）

Problem 7.
Use ellipsoid method solve:
$\max \ \ 0 \\ s.t. \ \ x_1 + 5x_2 ≤ 7 \\ \ \ \ \ \ \ \ \ x_1 + 2x_2 ≥ 6 \\ \ \ \ \ x_1,x_2 ≥ 0 .$The initial Ellipsoid is taken to be $E(0,100×I_{2×2})$.
You only need to give THREE STEPS

Solution

Transportation problem & unimodular matrix 运输问题与幺模矩阵

Problem 20.
For transportation problem stated as follows.
There are m origins that contain various amounts of a commodity that must be shipped to $n$ destinations to meet demand requirements. Specially, origin $i$ contains an amount $a_i$, and destination $j$ has a requirement of amount $b_i$. It is assumed that the system is balanced in the sense that total supply equals total demand. There is unit cost $c_{ij}$ associated with the shipping of the commodity from origin $i$ to destination $j$. The problem is to find the shipping pattern between origins and destinations that satisfies all the requirements and minimized the total shipping cost.
(1) build an mixed integer linear programming model for above problem.
(2) If the row and column sums of a transportation problem are integers, then the basic variables in any basic solution are integers. 如果运输问题的行和列的和是整数，证明所有基可行解的基变量为整数。

Problem 21.
A matrix $\textbf{\textit{A}}$ is said to be totally unimodular if the determinant of every square submatrix formed from it has value $0,+1$ or $?1$. （完全幺模矩阵的各阶子式均为0,1或-1）
(1) Show that the matrix $\textbf{\textit{A}}$ defining the equality constraints of a transportation prolblem is totally unimodular. 证明运输问题的系数矩阵是完全幺模的。
(2) In the system of equations $\textbf{\textit{Ax}}=\textbf{\textit{b}}$, assume that $\textbf{\textit{A}}$ is totally unimodular and that all elements of $\textbf{\textit{A}}$ and $\textbf{\textit{b}}$ are integers. Show that all basic solutions have integer components.
与Problem20(2)的区别在于：此时 $\textbf{\textit{A}}$是任意矩阵，秩不再是 $m+n-1$

Solution

Graph Theory 图论

Maximum flow 最大流

Problem 9.
Use the Ford-Fulkerson method to solve decide the maximum flow for the following network problem.

Solution

附原题