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

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

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

n = 3

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

c = [5, 8, 1]

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

a = [2, 3, 1]

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

b = 13

Решение

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{5}{2}, 5, 2, 1\right], \left[\frac{8}{3}, 8, 3, 2\right], \left[1, 1, 1, 3\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]

5/2 >= 8/3 >= 1 8/3 >= 5/2 >= 1

j = 1;
for element in d:
    var('y'+str(element[3])) == var('x'+str(j))
    j=j+1

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

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

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

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

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

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

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} = 1

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

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

for i in range(1,n):
    y[i] = int(bb[i-1]/d[i][2])
    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} = 0

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

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

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

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

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

print 'y =', y

y = [4, 0, 1]

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

Ответ:

x = [y[d[i][3]-1] for i in range(n) ]
print 'x =', x

x = [0, 4, 1]

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

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

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

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