1310-Исходные данные.sagews

Исходные данные

Размерность вектора:

n = 5

Эффективности решений:

c = [2, 4, 2, 6, 5]

Вектор условных объёмов:

a = [3, 2, 1, 3, 4]

Суммарный условный объём ранца:

b = 9

var('E') == sum(c[i-1]*var('x'+str(i)) for i in range(1, n+1));

\newcommand{\Bold}[1]{\mathbf{#1}}E = 2 \, x_{1} + 4 \, x_{2} + 2 \, x_{3} + 6 \, x_{4} + 5 \, x_{5}

sum(a[i-1]*var('x'+str(i)) for i in range(1, n+1)) <= b

\newcommand{\Bold}[1]{\mathbf{#1}}3 \, x_{1} + 2 \, x_{2} + x_{3} + 3 \, x_{4} + 4 \, x_{5} \leq 9

Решение

0. Предварительный этап

а) Проверка существования тривиального решения

if (sum(a) < b):
    print("Решение тривиально (все x=1, дальнейшие выкладки не имеют смысла)")
else:
    print("Тривиальное решение не найдено")

Тривиальное решение не найдено

б) Проверка существования хотя бы одного решения

if ( min(a) < b ):
    print("Решение существует")
else:
    print("Решения не существует (все x=0, дальнейшие выкладки не имеют смысла)")

Решение существует

в) Ранжирование элементов по убыванию предельной эффективности

d = [ [c[i], c[i], a[i], i+1] for i in range(n) ]; d

\newcommand{\Bold}[1]{\mathbf{#1}}\left[\left[2, 2, 3, 1\right], \left[4, 4, 2, 2\right], \left[2, 2, 1, 3\right], \left[6, 6, 3, 4\right], \left[5, 5, 4, 5\right]\right]

for i in range(n-1):
    print d[i][0], " ", 
print d[n-1][0]
d.sort(reverse=True);
for i in range(n-1):
    print d[i][0], ">=", 
print d[n-1][0]

2 4 2 6 5 6 >= 5 >= 4 >= 2 >= 2

anew = vector([d[i][2] for i in range(n)])
cnew = vector([d[i][1] for i in range(n)])
j = 1;
for element in d:
    var('y'+str(j)) == var('x'+str(element[3]))
    j=j+1

\newcommand{\Bold}[1]{\mathbf{#1}}y_{1} = x_{4}

\newcommand{\Bold}[1]{\mathbf{#1}}y_{2} = x_{5}

\newcommand{\Bold}[1]{\mathbf{#1}}y_{3} = x_{2}

\newcommand{\Bold}[1]{\mathbf{#1}}y_{4} = x_{1}

\newcommand{\Bold}[1]{\mathbf{#1}}y_{5} = x_{3}

var('E') == sum(cnew[i-1]*var('y'+str(i)) for i in range(1, n+1));

\newcommand{\Bold}[1]{\mathbf{#1}}E = 6 \, y_{1} + 5 \, y_{2} + 4 \, y_{3} + 2 \, y_{4} + 2 \, y_{5}

sum(anew[i-1]*var('x'+str(i)) for i in range(1, n+1)) <= b

\newcommand{\Bold}[1]{\mathbf{#1}}3 \, x_{1} + 4 \, x_{2} + 2 \, x_{3} + 3 \, x_{4} + x_{5} \leq 9

г) Оценка количество ненулевых элементов решения

a1 = a; a1.sort(reverse=True); a1
s = 0; r = 0;
for i in range(n):
    s = s + a1[i]
    r = r + 1
    if (sum(a) - s <= b):
        break
num_nonzero = n-r; num_nonzero

\newcommand{\Bold}[1]{\mathbf{#1}}4

Общее количество вариантов решения:

l = [int(i < num_nonzero) for i in range(n)]
k = number_of_permutations(l); k

\newcommand{\Bold}[1]{\mathbf{#1}}5

1. Генерируется соответствующее количество возможных вариантов решения в порядке общего убывания суммарной эффективности

m = matrix(permutations(l));
mm = matrix(SR, k, n+2)
for i in range(k):
    for j in range(n):
        mm[i,j] = m[i,j]
for i in range(k):
    mm[i,n] = list(mm[i, range(n)]*anew)[0]
    if (mm[i,n] <= b):
        mm[i,n+1] = list(mm[i, range(n)]*cnew)[0]
    else:
        mm[i,n+1] = NaN
mm.subdivide(None, n)
mm

\newcommand{\Bold}[1]{\mathbf{#1}}\left(ParseError: KaTeX parse error: Expected '\right', got 'EOF' at end of input: …& 1 \end{array}\right) & \left($$\begin{array}{rr} 12 & NaN \\ 10 & NaN \\ 11 & NaN \\ 9 & 14 \\ 10 & NaN \end{array}$$\right) \end{array}\right)

Решение с максимальной эффективностью:

y_to_check=[];
for i in range(k):
    if (mm[i, n+1] != NaN):
        y_to_check=list(mm[i,range(n)][0])
        break;
print 'y =', y_to_check

y = [1, 0, 1, 1, 1]

2. Проверка решения на оптимальность

M_plus = [];
M_minus = [];
for i in range(n):
    if (y_to_check[i]==1):
        pass;
        M_plus.append(cnew[i])
    else:
        M_minus.append(cnew[i])
M_plus.sort()
print "M+ =", M_plus
print "M- =", M_minus

M+ = [2, 2, 4, 6] M- = [5]

is_opt = False
if (len(M_plus)>1):
    is_opt = (M_plus[0] + M_plus[1] > max(M_minus) )
else:
    is_opt = ( min(M_plus) > max(M_minus) )
if is_opt:
    print("Решение оптимально")
    y = y_to_check
else:
    print("Существует лучшее решение")

Существует лучшее решение

Улучшение решения

for r in range(r+1,n):
    if is_opt: break
    num_nonzero = n-r
    l = [int(i < num_nonzero) for i in range(n)]
    k = number_of_permutations(l);
    m = matrix(permutations(l));
    mm = matrix(SR, k, n+2)
    for i in range(k):
        for j in range(n):
            mm[i,j] = m[i,j]
    for i in range(k):
        mm[i,n] = list(mm[i, range(n)]*anew)[0]
        if (mm[i,n] <= b):
            mm[i,n+1] = list(mm[i, range(n)]*cnew)[0]
        else:
            mm[i,n+1] = NaN
    mm.subdivide(None, n)
    mm
    y_to_check=[];
    for i in range(k):
        if (mm[i, n+1] != NaN):
            y_to_check=list(mm[i,range(n)][0])
            break;
    print 'y =', y_to_check
    M_plus = [];
    M_minus = [];
    for i in range(n):
        if (y_to_check[i]==1):
            pass;
            M_plus.append(cnew[i])
        else:
            M_minus.append(cnew[i])
    M_plus.sort()
    print "M+ =", M_plus
    print "M- =", M_minus
    is_opt = False
    if (len(M_plus)>1):
        is_opt = (M_plus[0] + M_plus[1] > max(M_minus) )
    else:
        is_opt = ( min(M_plus) > max(M_minus) )
    if is_opt:
        print("Решение оптимально")
        y = y_to_check
    else:
        print("Существует лучшее решение")

\newcommand{\Bold}[1]{\mathbf{#1}}\left(ParseError: KaTeX parse error: Expected '\right', got 'EOF' at end of input: …& 1 \end{array}\right) & \left($$\begin{array}{rr} 9 & 15 \\ 10 & NaN \\ 8 & 13 \\ 8 & 12 \\ 6 & 12 \\ 7 & 10 \\ 9 & 11 \\ 7 & 11 \\ 8 & 9 \\ 6 & 8 \end{array}$$\right) \end{array}\right)

y = [1, 1, 1, 0, 0] M+ = [4, 5, 6] M- = [2, 2] Решение оптимально

3. Обратное переобозначение переменных

Ответ:

x = [0 for _ in range(n) ]; j = 0
for element in d:
    x[element[3]-1] = y[j]; j=j+1
print 'x =', x

x = [0, 1, 0, 1, 1]

При значении критерия:

Emax = vector(x)*vector(c);
var('E_max') == Emax

\newcommand{\Bold}[1]{\mathbf{#1}}E_{\mbox{max}} = 15