polimd/polimd_archived/operations_research/lesson_02.md

Operations Research

Enrico Malucelli

6 October 2015

Introduction

Exercise: How to invest a budget

###Steps

1. decisions

2. constraints

####Solution #####Variables $x_i$= amount of money invested (i=1...5), $x_i \ge 0$ #####constraints $\sum x_i \le 137$

$x_1 \le 40$

$x_2 \le 12$

$x_3 \le 130$

$x_4 \le 5$

$x_5 \le 400$ #####target $x_1/40*3.2+x_2/12*1.5+x_3/130*4.2+x_4/5*0.7+x_5/400*17$

####Alternative solution $y_1$=share of bond $y_1=x_1/availability$ $0 \le y_1\le1$ $i=1$

$$40y_1+12y_2+130y_3+5y_4+400y_5\le137$$ $$max32y_1+15y_2+4.2y_3+0.7y_4+17y_5$$

We can divide each bonus for the total of the earning so we can get an index of the best investment. $$8\%y_1+125\%y_2+3.2\%y_3+14\%y_4+4.25\%y_5$$

We notice that the $y_2$ is the best investment, and we should buy as much as we can of that kind.

example: $y_4=1$ $y_2=1$ $y_1=1$ $y_5=...$ ####Algorithm generalization $$\sum c_i y_i$$ $$\sum a_i y_i \le b$$ $$0\le y_i \le 1 i=1 \mu$$ Sort indicates by non decreasing $C_i/a_i$ cosider the variables in the Order: $$y_i=\begin{cases} 1,& if &b \ge a_i\ b/a_i,& if &b < a_i \end{cases}$$ $$b-y_ia_i$$

###Logical variables Can assume only the values ${0,1}$ ####example: A burglar sneaks into a jewelry and his bag can hold 8kg, what must he steal?

	object	1	2	3	4	5	6
value	$v_i$	7	2	4	5	4	1
weight	$w_i$	5	3	2	3	1	1

####solution Contrary to the previous problem (in which we had infinite solutions, like any fraction), in this problem we have at most $2^6$ solutions, maybe not all of them are feasible.

x_i = 1 if the burglar has taken, 0 otherwise

$$max \sum v_i x_i$$ $$\sum w_i x_i \le b(=8)$$

If we apply the same algorithm as before, we can calculate the value_for_weight factor of every object and choose the best ones. #####However this is not the best solution ####Logical variable, Complement $$x'_i=1-x_i$$ ####Other types of variables ####Integer Variables ####Discrete value variables In most cases we select the value of a variable within a finite set e.g.: the memory size of a computer, the capacity of a telecommunication link. $$x\in { v_1,v_2,...,v_r}$$ #####formulas $$s_i=\begin{cases} 1,& x=v_i\ 0,& \end{cases}$$ ###example: diet |food|pasta|rice|steak|carrots|potatoes|pear| |----|-----|----|-----|-------|--------|----| |calories per hg|300|250|200|70|180|100 ####Minimum required calories: 700 We can transform all the inequalities to be less or equal

And later we need to transform our inequalities into equalities