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

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

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

n = 5

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

c = [2, 4, 5, 1, 3]

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

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

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

b = 8

Решение

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

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

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

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

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

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

\newcommand{\Bold}[1]{\mathbf{#1}}\left[\left[\frac{2}{3}, 2, 3, 1\right], \left[2, 4, 2, 2\right], \left[\frac{5}{2}, 5, 2, 3\right], \left[\frac{1}{3}, 1, 3, 4\right], \left[\frac{3}{4}, 3, 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/3 >= 2 >= 5/2 >= 1/3 >= 3/4 5/2 >= 2 >= 3/4 >= 2/3 >= 1/3

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_{3}

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

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

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

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

1. Определение количества вариантов решения $y_1$

y = [0 for _ in range(n) ]
y[0] = int( b - d[0][2] >= 0 );
var('y'+str(1)) == y[0]

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

bb = [0 for _ in range(n) ]
dE = [0 for _ in range(n) ]
if (y[0] > 0):
    bb[0] = b - d[0][2]*y[0]
    dE[0] = d[0][1]*y[0]
    var('b'+str(1)) == bb[0]
    var('Delta_E'+str(1)) == dE[0]

\newcommand{\Bold}[1]{\mathbf{#1}}b_{1} = 6

\newcommand{\Bold}[1]{\mathbf{#1}}\Delta_{E_{1}} = 5

2. Повторение пункта 1) для всех оставшихся переменных

for i in range(1,n):
    y[i] = int ( bb[i-1] - d[i][2] >= 0)
    var('y'+str(i+1)) == y[i]
    if (y[i] > 0):
        bb[i] = bb[i-1] - d[i][2]*y[i]
        dE[i] = d[i][1]*y[i]
    else:
        bb[i] = bb[i-1]
        dE[i] = 0
    var('b'+str(i+1)) == bb[i]
    var('Delta_E'+str(i+1)) == dE[i]
    if bb[i]==0: break

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

\newcommand{\Bold}[1]{\mathbf{#1}}b_{2} = 4

\newcommand{\Bold}[1]{\mathbf{#1}}\Delta_{E_{2}} = 4

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

\newcommand{\Bold}[1]{\mathbf{#1}}b_{3} = 0

\newcommand{\Bold}[1]{\mathbf{#1}}\Delta_{E_{3}} = 3

print 'y =', y

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

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, 1, 0, 1]

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

Emax = sum(dE);
var('E_max') == Emax

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

Решение является приблизительным.