有一位农民种植水稻、麦子和玉米,这三种作物的单位收益分别是,每单位的水稻、麦子和玉米需要单位的肥料和单位的农药,假设该农民总共有单位的肥料和单位的农药,那么每种作物各种植多少才能收益最大?

  上述问题可以形式化成一个线性规划,设三种作物种植的单位分别是,那么要求解的就是 \begin{align*} \min_{x_1, x_2, x_3} & \quad - s_1 x_1 - s_2 x_2 - s_3 x_3 \\ \st & \quad f_1 x_1 + f_2 x_2 + f_3 x_3 \le f \\ & \quad p_1 x_1 + p_2 x_2 + p_3 x_3 \le p \\ & \quad x_1 \ge 0, ~ x_2 \ge 0, ~ x_3 \ge 0 \end{align*}

  Lagrange对偶函数为 \begin{align*} L & = - s_1 x_1 - s_2 x_2 - s_3 x_3 + y_1 (f_1 x_1 + f_2 x_2 + f_3 x_3 - f) \\ & \qquad \qquad + y_2 (p_1 x_1 + p_2 x_2 + p_3 x_3 - p) - z_1 x_1 - z_2 x_2 - z_3 x_3 \end{align*} 令关于的偏导数为零可得 \begin{align*} \frac{\partial L}{\partial x_1} & = - s_1 + y_1 f_1 + y_2 p_1 - z_1 = 0 \Longrightarrow y_1 f_1 + y_2 p_1 = s_1 + z_1 \ge s_1 \\ \frac{\partial L}{\partial x_2} & = - s_2 + y_1 f_2 + y_2 p_2 - z_2 = 0 \Longrightarrow y_1 f_2 + y_2 p_2 = s_2 + z_2 \ge s_2 \\ \frac{\partial L}{\partial x_3} & = - s_3 + y_1 f_3 + y_2 p_3 - z_3 = 0 \Longrightarrow y_1 f_3 + y_2 p_3 = s_3 + z_3 \ge s_3 \end{align*} 故对偶问题为 \begin{align*} \max_{y_1, y_2} & \quad - y_1 f - y_2 p \\ \st & \quad y_1 f_1 + y_2 p_1 \ge s_1 \\ & \quad y_1 f_2 + y_2 p_2 \ge s_2 \\ & \quad y_1 f_3 + y_2 p_3 \ge s_3 \\ & \quad y_1 \ge 0, ~ y_2 \ge 0 \end{align*}

  现在有一位商人,想从农民的手上收购肥料和农药,他开给农民的肥料和农药的单价分别是,那么就是商人收购全部单位肥料和单位农药的总开销,约束是指相对于农民自己种第种作物,不如直接卖肥料和农药更划算。所以对偶问题描述的是,对商人来说,肥料和农药的单价各为多少,才能使得农民愿意卖且自己的开销最小。

  根据弱对偶有,即 \begin{align*} s_1 x_1 + s_2 x_2 + s_3 x_3 \le y_1 f + y_2 p \end{align*} 所以弱对偶说的是在农民不贱卖资源的情况下,再精明的商人也无法让自己的最小开销低于农民的最大收益,最精明的商人是使得两者相等,即强对偶成立。

Copyright © Avanti 2020 all right reserved,powered by Gitbook文件最后修改时间: 2021-06-19 10:20:29

results matching ""

    No results matching ""