Topic: Solution needed for a optimization problems

[sysuwzx]

Hello i'm coming again~ this is the question~    x₁~x₈ are required to meet the following inequality condition：
①、1/x₁+2/x₂+3/x₃+4/x₄+5/x₅+6/x₆+7/x₇+8/x₈≤18
②、x₁≥x₂≥x₃≥x₄≥x₅≥x₆≥x₇≥x₈
and  x₁ to x₈ must be chosen in the list '(1 2 3 4 5 6 7 8 ).
③、the sum of 100x₁+200x₂+300x₃+400x₄+500x₅+600x₆+700x₇+800x₈  is expected to get the minimum
Anyone get a good idea to get the desired x₁ to x₈ ? the list '(1 2 3 4 5 6 7 8 ) is just an simple example, it's more complicated in actual jobs.
Thanks in advance.

[ribarm]

I don't understand, you gave condition 2...
You just sort numbers from your initial list...
Am I missing something?

[sysuwzx]

I don't understand, you gave condition 2...
You just sort numbers from your initial list...
Am I missing something?

Sorry, my fault. x1 to x8 can be any number in the list  '(1 2 3 4 5 6 7 8 ). For example, since x1≥x2≥..≥x8, x1 can be 8, x2 can be 7, x3 can be 6, ...., etc. Also, x1 can be 8, x2 can be 6, x3 can be 6, x4 can be 5, x5 can be 5, x6 can be 4, x7 can be 4, x8 can be 4. In other words, x1 to x8 are in descending order and can be Repeatable.

[ribarm]

You take min. from '(1 2 3 4 5 6 7 8 )... x1=x2=x3=...=x8=1...
Now you check first condition <= 18... This is not true, so you take second min. number x1=x2=x3=...=x8=2...
And so on...
When first condition is met <=18, then your third result will be minimal 100x1+200x2+300x3+...+800x8...

This is how I now understood it...

[ribarm]

Here you go, but better checking is <= 17... Then you'll know that it works as desired - with your example (<= 18) result list is : '(2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0)

Code - Auto/Visual Lisp: [Select]

1. (defun summult-x1-xn ( lst / k )
2.   (setq k 0)
3.   (apply '+ (mapcar '(lambda ( x ) (* (setq k (+ k 100)) x)) lst))
4. )
5.  
6. (defun sumdiv-x1-xn ( lst / k )
7.   (setq k 0)
8.   (apply '+ (mapcar '(lambda ( x ) (/ (float (setq k (1+ k))) x)) lst))
9. )
10.  
11. (defun sum-x1-xn ( lst )
12.   (apply '+ lst)
13. )
14.  
15. ;; Solution not correct - initial list (1 2 3 4 5 6 7 8) chk number - 21 => result list (2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0) which is not correct - summult-x1-xn => 7200
16. ;; for list (3 3 3 2 2 2 2 1), sumdiv-x1-xn => 21, summult-x1-xn => 7000 which is < than 7200
17.  
18. ;; Solution correct for simple : sum-x1-xn => 16 < 18 [ (8*2.0) < (3*3.0+4*2.0+1.0) ]
19.  
20. (defun c:test ( / x lst xx chkineqsumdivnum loop k p pp lstn lstnn )
21.   (initget 1)
22.   (setq x (getreal "\nFirst number - minimal one : "))
23.   (setq lst (cons x lst))
24.   (while
25.     (and
26.       (setq xx (getreal (strcat "\nNext number - must be > than : " (rtos (car lst)) " <ENTER - FINISH LIST INPUT> : ")))
27.       (if xx
28.         (if (< xx (car lst))
29.           t
30.           (setq lst (cons xx lst))
31.         )
32.       )
33.     )
34.   )
35.   (setq lst (reverse lst))
36.   (initget 1)
37.   (setq chkineqsumdivnum (getreal "\nSpecify checking number for sum division inequality condition : "))
38.   (setq loop t k 0)
39.   (while loop
40.     (if (null p)
41.       (setq p 0)
42.       (setq p (1+ p))
43.     )
44.     (setq pp 0)
45.     (repeat (length lst)
46.       (if (>= (- p (setq pp (1+ pp))) 0)
47.         (setq lstn (cons (nth (1+ k) lst) lstn))
48.         (setq lstn (cons (nth k lst) lstn))
49.       )
50.     )
51.     (setq lstn (reverse lstn))
52.     (if (vl-every 'numberp lstn)
53.       (if (> (sumdiv-x1-xn lstn) chkineqsumdivnum)
54.         (progn
55.           (if (= p (1- (length lst)))
56.             (setq k (1+ k) p nil)
57.           )
58.           (setq lstn nil)
59.         )
60.         (progn
61.           (if (= p (1- (length lst)))
62.             (setq k (1+ k) p nil)
63.           )
64.           (setq lstnn (cons lstn lstnn))
65.           (setq lstn nil)
66.         )
67.       )
68.       (setq loop nil)
69.     )
70.   )
71.   (if (vl-some '(lambda ( x ) (vl-every 'numberp x)) lstnn)
72.     (progn
73.       (setq lstnn (vl-sort (vl-remove-if '(lambda ( x ) (vl-some 'null x)) lstnn) '(lambda ( a b ) (if (= (summult-x1-xn a) (summult-x1-xn b)) (< (sumdiv-x1-xn a) (sumdiv-x1-xn b)) (< (summult-x1-xn a) (summult-x1-xn b))))))
74.       (prompt "\nResult list : ") (princ (car lstnn))
75.       (prompt "\nDivision sum : ") (princ (sumdiv-x1-xn (car lstnn)))
76.       (prompt "\nMinimal multiplication sum : ") (princ (summult-x1-xn (car lstnn)))
77.       (textscr)
78.     )
79.     (prompt "\nInput list don't satisfy sum division inequality condition...")
80.   )
81.   (princ)
82. )
83.  
84. (defun c:test-simple-sum ( / x lst xx chkineqsumdivnum loop k p pp lstn lstnn )
85.   (initget 1)
86.   (setq x (getreal "\nFirst number - minimal one : "))
87.   (setq lst (cons x lst))
88.   (while
89.     (and
90.       (setq xx (getreal (strcat "\nNext number - must be > than : " (rtos (car lst)) " <ENTER - FINISH LIST INPUT> : ")))
91.       (if xx
92.         (if (< xx (car lst))
93.           t
94.           (setq lst (cons xx lst))
95.         )
96.       )
97.     )
98.   )
99.   (setq lst (reverse lst))
100.   (initget 1)
101.   (setq chkineqsumdivnum (getreal "\nSpecify checking number for sum division inequality condition : "))
102.   (setq loop t k 0)
103.   (while loop
104.     (if (null p)
105.       (setq p 0)
106.       (setq p (1+ p))
107.     )
108.     (setq pp 0)
109.     (repeat (length lst)
110.       (if (>= (- p (setq pp (1+ pp))) 0)
111.         (setq lstn (cons (nth (1+ k) lst) lstn))
112.         (setq lstn (cons (nth k lst) lstn))
113.       )
114.     )
115.     (setq lstn (reverse lstn))
116.     (if (vl-every 'numberp lstn)
117.       (if (> (sumdiv-x1-xn lstn) chkineqsumdivnum)
118.         (progn
119.           (if (= p (1- (length lst)))
120.             (setq k (1+ k) p nil)
121.           )
122.           (setq lstn nil)
123.         )
124.         (progn
125.           (if (= p (1- (length lst)))
126.             (setq k (1+ k) p nil)
127.           )
128.           (setq lstnn (cons lstn lstnn))
129.           (setq lstn nil)
130.         )
131.       )
132.       (setq loop nil)
133.     )
134.   )
135.   (if (vl-some '(lambda ( x ) (vl-every 'numberp x)) lstnn)
136.     (progn
137.       (setq lstnn (vl-sort (vl-remove-if '(lambda ( x ) (vl-some 'null x)) lstnn) '(lambda ( a b ) (if (= (sum-x1-xn a) (sum-x1-xn b)) (< (sumdiv-x1-xn a) (sumdiv-x1-xn b)) (< (sum-x1-xn a) (sum-x1-xn b))))))
138.       (prompt "\nResult list : ") (princ (car lstnn))
139.       (prompt "\nDivision sum : ") (princ (sumdiv-x1-xn (car lstnn)))
140.       (prompt "\nMinimal simple sum : ") (princ (sum-x1-xn (car lstnn)))
141.       (textscr)
142.     )
143.     (prompt "\nInput list don't satisfy sum division inequality condition...")
144.   )
145.   (princ)
146. )
147.  

HTH., M.R.

[ribarm]

Actually the code is wrong...

This is my test :

Code: [Select]

Command: (sumdiv-x1-xn '(3 3 3 2 2 2 2 1))
21.0
Command: (summult-x1-xn '(3 3 3 2 2 2 2 1))
7000
Command: TEST
First number - minimal one : 1
Next number - must be > than : 1.00000000 <ENTER - FINISH LIST INPUT> : 2
Next number - must be > than : 2.00000000 <ENTER - FINISH LIST INPUT> : 3
Next number - must be > than : 3.00000000 <ENTER - FINISH LIST INPUT> : 4
Next number - must be > than : 4.00000000 <ENTER - FINISH LIST INPUT> : 5
Next number - must be > than : 5.00000000 <ENTER - FINISH LIST INPUT> : 6
Next number - must be > than : 6.00000000 <ENTER - FINISH LIST INPUT> : 7
Next number - must be > than : 7.00000000 <ENTER - FINISH LIST INPUT> : 8
Next number - must be > than : 8.00000000 <ENTER - FINISH LIST INPUT> :
Specify checking number for sum division inequality condition : 21
Result list : (2.0 2.0 2.0 2.0 2.0 2.0 2.0 2.0)
Minimal multiplication sum : 7200.0

Sorry, but I can't think of something better for now...
Regards...

[EDIT : But my code is correct for expected minimal simple sum : x1+x2+x3+x4+x5+x6+x7+x8 ; 2*8 < 3*3+4*2+1 ; 16 < 18]
, so 3rd condition - multiplication sum is somewhat unusual and directly in opposition to first 2 conditions...
Perhaps you should consider changing 3rd condition to something that supports first 2 equations...
And this simple sum is what I assumed as correct while composing list of numbers from maximal number to minimal - first minimal sum was what I assumed, so firstly numbers in list should be minimal as much as possible taking in consideration that second condition must be satisfied...

[ribarm]

BTW. This reminds me on Lottery... You have to take in consideration every possible permutation with repetitions in descending order then apply (summult-x1-xn) sub to this permutation, construct list with pairs (((permutation1) sum1) ((permutation2) sum2) ... ) and then sort this list by min. sum (lambda ( a b ) (< (cadr a) (cadr b)))... Then result is (caar lst)...
Finding all permutations with repetitions in descending order I leave to you, smart guy...

[sysuwzx]

BTW. This reminds me on Lottery... You have to take in consideration every possible permutation with repetitions in descending order then apply (summult-x1-xn) sub to this permutation, construct list with pairs (((permutation1) sum1) ((permutation2) sum2) ... ) and then sort this list by min. sum (lambda ( a b ) (< (cadr a) (cadr b)))... Then result is (caar lst)...
Finding all permutations with repetitions in descending order I leave to you, smart guy...

Thanks for your code all the same! If it comes to x100, i think my computer will blow up.....Previously i want to try the genetic algorithm ( one kind of optimization algorithms ), but i'm not familiar with that, either...i took a fast look for some relevant example and it seems the output did not match the descending condition.

[ribarm]

For 8 elements, after thinking for a while, I believe you have :
2*8+6*8+10*8+15*8*3+21*8*4+8*7*4+8+1=1409 permutations...

My formula for n=3 and n=4 :

n*(n-1)*(n-2)+n+1 ; this part is repeating in all cases, but as n grows there are additional permutations that also influence total sum and formula is little different : n*(n-1)*(n-3)+n+1 for n=5 and n=6 and n*(n-1)*(n-4)+n+1 for n=7 and n=8

- 3 : p=3*2*1+3+1=10
- 4 : p=3*4+4*3*2+4+1=41
- 5 : p=2*5+6*5+5*4*2+5+1=86
- 6 : p=2*6+6*6+10*6*2+6*5*3+6+1=265
- 7 : p=2*7+6*7+10*7+15*7*3+7*6*3+7+1=575
- 8 : p=2*8+6*8+10*8+15*8*3+21*8*4+8*7*4+8+1=1409