# 用 scipy 求解 The Diet Problem

Formulate the following Diet Problem. Transform the formulation into LP standard form. Use some LP solver to solve the problem. Try to find the dual of the problem (optional). Suppose that we have three foods and two nutritional requirements to satisfy:

Food Cost / Serving Vitamin A Calories Maximum Servings
Corn (C) $0.18 107 72 10 2% milk (M)$0.23 500 121 10
Wheat bread (W) \$0.05 0 65 10
\ Minimum Amount Nutrient in Diet Maximum Amount in Diet
Calories (Cal) 2000 2250
Vitamin A (VA) 5000 50000

## Formulate the problem

\begin{aligned} \min\, && 0.18x_1+0.23x_2+0.05x_3 \\ \textit{s.t.}\, & 2000\le & 72x_1+121x_2+65x_3 &\le 2250 \\ & 5000\le & 107x_1+500x_2 &\le 50000 \\ & 0\le & x_1&\le 10 \\ & 0\le & x_2&\le 10 \\ & 0\le & x_3&\le 10\\ \end{aligned}

## Transform the formulation into LP standard form

$\mathbf{A}=\begin{bmatrix} 107 & 500 & 0 \\ -107& -500&0 \\ 72 & 121 & 65 \\ -72 & -121 & -65 \\ 1 & 0 & 0 \\ -1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & -1 \end{bmatrix}\\ \mathbf{b}=\left[50000,-5000,2250,-2000,10, 0, 10, 0, 10, 0\right]^T\\ \mathbf{c}=\left[0.18,0.23,0.05\right]$

## Use some LP solver to solve the problem

from scipy.optimize import linprog

if __name__ == "__main__":
A_ub = [[107, 500, 0],
[-107, -500, 0],
[72, 121, 65],
[-72, -121, -65],
[1, 0, 0],
[-1, 0, 0],
[0, 1, 0],
[0, -1, 0],
[0, 0, 1],
[0, 0, -1]]
b_ub = [50000, -5000, 2250, -2000, 10, 0, 10, 0, 10, 0]
c = [0.18, 0.23, 0.05]
print(linprog(c, A_ub, b_ub))


     con: array([], dtype=float64)
fun: 3.1500000382242486
message: 'Optimization terminated successfully.'
nit: 9
slack: array([4.47919444e+04, 2.08055583e+02, 2.49999993e+02, 7.18327624e-06,
8.05555529e+00, 1.94444471e+00, 2.22118501e-09, 1.00000000e+01,
1.78711305e-07, 9.99999982e+00])
status: 0
success: True
x: array([ 1.94444471, 10.        ,  9.99999982])