Linear programming

[Anonymous No.10129155]

What's the answer /sci ?
No really any help will be appreciated

[Anonymous No.10129195]

The packages should be dropped at (9, 5) and (3, 4).

[Anonymous No.10129211]

>>10129155
>Minimize the walkted distance.
>Walked distance = sum of distances people from each village must walk
>The distance someone from any village walks is the minimum of the distance from the village to one of the two packages

[Anonymous No.10129215]

>>10129155
Why would you send packages with aids?
And what do they mean by 300 constraints and variables?

[Anonymous No.10129219]

Are you sure this is linear programming? I'm not a pro but I don't think the total Euclidean distance the villagers must walk is a linear function of the package coordinates.

[Anonymous No.10129241]

Find (p, q) and (r, s) to minimize the following where 1 <= (p, q), (r, s) <= 9
[eqn]
\min \{\sqrt{(p - 5)^2 + (q - 1)^2}, \sqrt{(r - 5)^2 + (s - 1)^2}\}\\ + \min \{\sqrt{(p - 5)^2 + (q - 2)^2}, \sqrt{(r - 5)^2 + (s - 2)^2}\}\\ + \min \{\sqrt{(p - 9)^2 + (q - 2)^2}, \sqrt{(r - 9)^2 + (s - 2)^2}\}\\ + \min \{\sqrt{(p - 10)^2 + (q - 2)^2}, \sqrt{(r - 10)^2 + (s - 2)^2}\}\\ + \min \{\sqrt{(p - 1)^2 + (q - 3)^2}, \sqrt{(r - 1)^2 + (s - 3)^2}\}\\ + \min \{\sqrt{(p - 6)^2 + (q - 3)^2}, \sqrt{(r - 6)^2 + (s - 3)^2}\}\\ + \min \{\sqrt{(p - 8)^2 + (q - 3)^2}, \sqrt{(r - 8)^2 + (s - 3)^2}\}\\ + \min \{\sqrt{(p - 9)^2 + (q - 3)^2}, \sqrt{(r - 9)^2 + (s - 3)^2}\}\\ + \min \{\sqrt{(p - 10)^2 + (q - 3)^2}, \sqrt{(r - 10)^2 + (s - 3)^2}\}\\ + \min \{\sqrt{(p - 2)^2 + (q - 4)^2}, \sqrt{(r - 2)^2 + (s - 4)^2}\}\\ + \min \{\sqrt{(p - 7)^2 + (q - 4)^2}, \sqrt{(r - 7)^2 + (s - 4)^2}\}\\ + \min \{\sqrt{(p - 10)^2 + (q - 4)^2}, \sqrt{(r - 10)^2 + (s - 4)^2}\}\\ + \min \{\sqrt{(p - 2)^2 + (q - 5)^2}, \sqrt{(r - 2)^2 + (s - 5)^2}\}\\ + \min \{\sqrt{(p - 9)^2 + (q - 5)^2}, \sqrt{(r - 9)^2 + (s - 5)^2}\}\\ + \min \{\sqrt{(p - 8)^2 + (q - 6)^2}, \sqrt{(r - 8)^2 + (s - 6)^2}\}\\ + \min \{\sqrt{(p - 2)^2 + (q - 7)^2}, \sqrt{(r - 2)^2 + (s - 7)^2}\}\\ + \min \{\sqrt{(p - 2)^2 + (q - 8)^2}, \sqrt{(r - 2)^2 + (s - 8)^2}\}\\ + \min \{\sqrt{(p - 6)^2 + (q - 8)^2}, \sqrt{(r - 6)^2 + (s - 8)^2}\}\\ + \min \{\sqrt{(p - 8)^2 + (q - 10)^2}, \sqrt{(r - 8)^2 + (s - 10)^2}\}\\ + \min \{\sqrt{(p - 10)^2 + (q - 10)^2}, \sqrt{(r - 10)^2 + (s - 10)^2}\}
[/eqn]

[Anonymous No.10129248]

>>10129241
Wrong!
You forgot to mention that p,q,r,s must be integers.

If it gets graded by the same cunts as my tests were you would get 0 points for that exercise.

[Anonymous No.10129256]

>>10129241
You just restated the problem, retard

[Anonymous No.10129288]

>>10129155
An unweighted average and min max. Notation is fucked but its mile above whatever faggotry a pajeet uses.

[Anonymous No.10129802]

LP noob here: what constraints would you even use here?

[Anonymous No.10129809]

>>10129155
i don't know how to do this shit. it's probably something related to your text book. i'd just do it naively in a non-mathy way.
1) 2 packages, A and B, 100 positions each. take the cross product.
2) for each package cross product result, {AsubP, BsubP} where P is 1 -> 10000, evaluate the summation of villages where N is 1 -> 20, of min[distance(AsubP, VsubN), distance(BsubP , VsubN)]

probably i get an F. also is it 200,000 constraints this way?

[Anonymous No.10129812]

>>10129809
also
3) take the smallest of those summations

[Anonymous No.10130545]

>>10129288
lol no, you're placing the n outside the bound of the summation. In addition, it's not obvious what is z and honestly the result of the summation doesn't give you any point. A better alternative would be
Let [math] M = (\mathbb{N}^2, d)[/math] be an euclidean [math]2[/math]-space
Let [math] A \subset \mathbb{N}^2 [/math] such that [math] A = \{(1, 5), (2, 5) , \dots, (8, 10), (10,10)\}[/math]
[math] \exists P \in \mathbb{N}^2: \forall Q \in \mathbb{R}^2: \sum_{a \in A} d(a, P) \leq \sum_{a \in A} d(a, Q)[/math]
Now this but applied to two points, which could use the self-evident property illustrated in the image above

[Anonymous No.10130547]

>>10130545
forgot to include the image

[Anonymous No.10130571]

>>10129155

we have several "clusters" where it's obvious what the shortest path is
2 first columns: 5.414km
last row: 2km
cluster on the upper right: (mind you, it's better not to walk diagonally so I'm avoiding it as much as possible): 15.898 km

now we have to calculate the shortest paths between the clusters (I'll call them A, B and C and they are in the order I named them):

A,B=4km for the lower end and 4.828km for the upper edge, but since the aid is infinite we obviously take the shorter one
B,C obviously 2.828

summed up my shortest path would amount to 3+5.414+15.898+4+2.828=31.14km

[Anonymous No.10130576]

>>10130571
actually scratch that, you drop the first somewhere in cluster a and it doesn't cross over to b, and package 2 distributes for B and C amounting to 5.414+2+2.828+15.898=26.14

[Anonymous No.10130591]

somebody write the code in CPLEX see what turns out

[Anonymous No.10130621]

>>10129256
so you mean it's been modeled mathematically?

[Anonymous No.10130636]

>>10130621
The original problem was already mathematical

[Anonymous No.10130637]

>>10129155
Its impossible

[Anonymous No.10130641]

>>10130621
No, the original problem already stated that we want to find 2 coordinates that minimizes the walked distance. He just restated the same problem, but in a much messier way

[Anonymous No.10130643]

D8 and E2 with a walked distance of 51.25km

[Anonymous No.10130656]

>>10129248
then your graders are retards that create artificial obstacles. I would spit in their faces and drop the program.

[Anonymous No.10130659]

>>10130656
Illiterate nigger

[Anonymous No.10130686]

>>10129155
realize that damaged villages with adjacent tiles can't be skipped or reduced

this leaves us with 6 points in a graph with the distances
2,414 (C1)
1 (G2)
13.07 (A5)
0 (H6, J8, J10)
From here on I will call the points by the coordinates i named above, don't take this as the literal distances between the coordinates

now let's include the shortest distances between the points that make sense

C1-G2=2
G2-H6=4
H6-A5=2.828
H6-J8=2.828
J8-10=2

let's minimize some more and add up the distances where there's only one path from point A to B

we are left with
C1 = 5.414
A5 = 14.484
J8 = 2

and 2 paths to take:
H2-H6 (4)
H6-J8(2.828)

we can eliminate one of those paths by dropping one box on C1 and the other on A5 or J10, doesnt really matter, which leaves us with a total distance of
5.414+14.484+2+2.828=24.726km

[Anonymous No.10131345]

>>10130643
in the case of finding a concrete solution, that's correct.

[Anonymous No.10131607]

>>10131345
lol no
literally the poster above you managed to do it with a distance less than half of that

[Anonymous No.10131623]

>>10130686
he's right, you know

[Anonymous No.10131624]

>>10131607
that poster is wrong. besides, there are 20 villages... do you really think the average distance per village is 1.2km?

[Anonymous No.10131638]

>>10131624
>the average distance per village
to what? the nearest village? sounds about right
look at this picture retard >>10131623

[Anonymous No.10131646]

>>10131638
where the problem state that packages walk themselves through a tour villages?
>retard

[Anonymous No.10131649]

>>10131646

[Anonymous No.10131678]

>>10131649
i feel bad that you'll probably never understand the depths of your own stupidity

[Anonymous No.10131694]

>>10131678
The solution to minimize walked distance is not for each village to walk to the package and back, but for the package to be passed around village to village. It's called "outside the box" thinking

[Anonymous No.10131702]

>>10131694
or air drop multiple bits of aid so that you don't even need to pass the aid. but you're literally changing the problem itself to make it easier, you're solving an entirely different problem.

[Anonymous No.10131716]

>>10131702
Three problem says you are airdropping 2 packages. The problem doesn't say anything about how the villagers are walking. I didn't change the problem. I assumed the villagers are walking in the most optimal way, whereas you assumed that the villagers are retarded

[Anonymous No.10131721]

>>10131702
The problem says you are airdropping 2 packages. The problem doesn't say anything about how the villagers are walking. I didn't change the problem. I assumed the villagers are walking in the most optimal way, whereas you assumed that the villagers are retarded

[Anonymous No.10131739]

>>10131721
right, because villagers in J10 are going to sit with thumbs up their butts until 14 other villages decide to give up their gibs.

[Anonymous No.10131748]

>>10131739
Yes, because the problem says to minimize the distance walked. They walk less that way

[Anonymous No.10131772]

>>10129155
idk, something like
>plot a point at mean coords of villages
>draw a line through that point that cuts the villages into 2 equal groups
>put packages at mean village coords of each group
>round the points to get an intager
probably flawed, but might be an ok starting point for optimisation

[Anonymous No.10131797]

>>10131739
>>10131702
>>10131646

[Anonymous No.10133614]

>>10129256
welcome to linear programming