# 线性规划模型

## 单纯形法

$x_{j} \geq 0 \qquad j=1,2, \cdots, n$

$$C_B$$ $$b$$ $$X_{B}$$ $$X_N$$ $$X_S$$
0 $$X_S$$ $$b$$ $$B$$ $$N$$ $$I$$
$$c_{j} - z_{j}$$ $$C_{B}$$ $$C_{N}$$ 0

$$C_B$$ $$b$$ $$X_{B}$$ $$X_N$$ $$X_S$$
$$C_B$$ $$X_s$$ $$B^{-1}b$$ $$I$$ $$B^{-1}N$$ $$B^{-1}$$
$$c_{j} - z_{j}$$ 0 $$C_{N}-C_{B}B^{-1}N$$ $$-C_{B}B^{-1}$$

## 对偶问题

$y_{i} \geq 0 \qquad i=1,2, \cdots, m$

# Cutting Stock Problem

$x_{i} \geq 0$

$2 x_{2} \geq 20$

$2 x_{3} \geq 18$

$2 y_2 \leq 1$

$2 y_3 \leq 1$