DL-CO pset 5

1.

Consider the following integer programming problem.

$$\begin{array}{rl}\max & x_1+2x_2\\ \text{subject to}& -3x_1+4x_2\le 4\\ & 3x_1+2x_2\le 11\\ & 2x_1-x_2\le 5\\ & x_1,x_2\ge 0\\ & x_1,x_2\in \mathbb{Z}\end{array}$$

Use a figure to answer the following questions.
a) What is the optimal cost of the linear programming relaxation? What is the optimal cost of the integer programming problem?
b) What is the convex hull of the set of all solutions to the integer programming problem?

Megoldás:
b) Legyen $K:=\mathrm{conv}\{(0,0),(0,1),(2,0),(2,2),(3,1)\}$. Minden megengedett megoldása az IP feladatnak benne van $K$-ban.

2.

A company is manufacturing $k$ different products using $m$ resources. The amounts of available resources are given, together with the requirement of each of them for the different products. The selling price of the products are also known.

a) Write up an IP that aims at maximizing the total profit.
b) Adjust the model if starting the production of product $i$ requires a cost of $s_i$.

Megoldás:
a)
Legyenek $r_1,r_2,\dots ,r_m$ az alapanyagok mennyiségeit jelölő változók.
Legyen az $i$-edik termékhez szükséges alapanyag $g_i=\{y_1,\dots ,y_m\}$, ahol $y_j$ jelöli, hogy a $j$-edik alapanyagból mennyi kell (ha nulla kell akkor nem rakjuk bele)
Legyen $c_i$ az $i$-edik termék ára.
Jelölje $x_i$, hogy az $i$-edik termékből mennyit adunk el.
Ekkor a célunk az, hogy $\sum x_i\cdot c_i$ maximális legyen valamilyen feltételek mellett.
Feltétel, hogy legyen elég alapanyag az összes termékre, tehát:

$$\sum _{i:y_j\in g_i}{x}_i\cdot y_j\le r_j$$

Ez az egyenlőtlenség azt jelenti, hogy a $j$-edik alapanyagból van elég.

Tehát az IP feladat a következő:

$$\begin{array}{rl}\max & \sum _{i=1}^k{x}_i\cdot c_i\\ \text{s.t.}& \sum _{i:y_j\in g_i}{x}_i\cdot y_j\le r_j\forall j\in \{1,2,\dots ,m\}\\ \text{s.t.}& x_i\in {\mathbb{Z}}_0^{+}\forall i\in \{1,2,\dots ,k\}\end{array}$$

b)
Kellenének $z_1,\dots ,z_k$ bináris változók, ahol

$$z_i=\{\begin{array}{ll}0& \text{ha }{x}_i=0\\ 1& \text{ha }{x}_i>0\end{array}$$

Vegyük hozzá az előző IP feladatunkhoz a következő feltételt:

$$z_i\le x_i\le N\cdot z_i$$

Ahol $N$ jelöli a legnagyobb ábrázolható számot (lényegében végtelent).

Ha $x_i=0$

$$z_i\le 0\le N\cdot z_i$$

Ekkor $z_i=0$, mert csak ekkor teljesül az egyenlőtlenség, mert $z_i=1$ esetben sérül a $z_i\le x_i$ egyenlőtlenség.

Ha $x_i\ge 1$

$$z_i\le x_i\le N\cdot z_i$$

Ekkor $z_i=1$, mert ha $z_i=0$, akkor sérül az $x_i\le N\cdot z_i$ egyenlőtlenség.
Tehát valóban ponta akkor $1$ a $z_i$, ha $x_i>0$ és pont akkor $0$ ha $x_i=0$.

Jelölje $s_i$ az $i$-edik termék termelésének indításához szükséges pénzt.
Így a célfüggvény is módosul:

$$\begin{array}{rl}\max & \sum _{i=1}^k{x}_i\cdot c_i-z_i\cdot s_i\end{array}$$

Ekkor pontosan akkor vonjuk le $s_i$ pénzt az összegből, ha termelünk az $i$-edik termékből.

related: DL-CO