Здравствуйте, angelicablednova!

Пусть произведено x[sub]1[/sub] изделий A и x[sub]2[/sub] изделий B (эти величины должны быть целыми и неотрицательными). Тогда будет израсходовано 13x[sub]1[/sub]+2x[sub]2[/sub] кг сырья первого вида (но не более 260 кг), 4x[sub]1[/sub]+4x[sub]2[/sub] кг сырья второго вида (но не более 124 кг) и 3x[sub]1[/sub]+14x[sub]2[/sub] кг сырья третьего вида (но не более 280 кг). Если стоимость единицы изделий A и B составляет 12 и 10 рублей соответственно, то стоимость готовой продукции будет равна 12x[sub]1[/sub]+10x[sub]2[/sub] руб. Требуется установить, при каких x[sub]1[/sub] и x[sub]2[/sub] она будет наибольшей.

Таким образом, имеем задачу линейного программирования: необходимо найти максимальное значение целевой функции F = 12x[sub]1[/sub]+10x[sub]2[/sub] [$8594$] max при системе ограничений:

x[sub]1[/sub][$8805$]0, x[sub]2[/sub][$8805$]0.

Перейдём к канонической форме, то есть приведём систему неравенств к системе уравнений путём введения дополнительных базисных переменных x[sub]3[/sub], x[sub]4[/sub], x[sub]5[/sub]:

(дополнительные переменные обозначают неиспользованные остатки сырья). Полагая свободные переменные x[sub]1[/sub], x[sub]2[/sub] равными 0, получим начальный опорный план X = (0, 0, 260, 124, 280).

Составим симплекс-таблицу:
[table]
[row][col]Базис[/col][col]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][col][/col][/row]
[row][col]x₃[/col][col]13[/col][col]2[/col][col]1[/col][col]0[/col][col]0[/col][col]260[/col][/row]
[row][col]x₄[/col][col]4[/col][col]4[/col][col]0[/col][col]1[/col][col]0[/col][col]124[/col][/row]
[row][col]x₅[/col][col]3[/col][col]14[/col][col]0[/col][col]0[/col][col]1[/col][col]280[/col][/row]
[row][col]F(X)[/col][col]-12[/col][col]-10[/col][col]0[/col][col]0[/col][col]0[/col][col]0[/col][/row]
[/table]Этот опорный план допустим, так как все свободные члены (260, 124, 280) положительны, но неоптимален, так как в индексной строке F(X) есть отрицательные коэффициенты.
Наибольший по модулю отрицательный коэффициент в индексной строке равен -12. Соответствующая ему переменная x[sub]1[/sub] будет новой базисной переменной, а соответствующий столбец - ведущим. Найдём частные от деления свободных членов на коэффициенты ведущего столбца: (260/13, 124/4, 280/3) = (20, 31, 280/3). Наименьшее среди них неотрицательное значение равно 20. Соответствующая ему переменная x[sub]3[/sub] будет новой свободной переменной, а соответствующая строка - ведущей:
[table]
[row][col]Базис[/col][col silver]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][col][/col][/row]
[row][col silver]x₃[/col][col gray]13[/col][col silver]2[/col][col silver]1[/col][col silver]0[/col][col silver]0[/col][col silver]260[/col][/row]
[row][col]x₄[/col][col silver]4[/col][col]4[/col][col]0[/col][col]1[/col][col]0[/col][col]124[/col][/row]
[row][col]x₅[/col][col silver]3[/col][col]14[/col][col]0[/col][col]0[/col][col]1[/col][col]280[/col][/row]
[row][col]F(X)[/col][col silver]-12[/col][col]-10[/col][col]0[/col][col]0[/col][col]0[/col][col]0[/col][/row]
[/table]Разрешающий элемент, находящийся на пересечении ведущего столбца и ведущей строки, равен 13. Заменяем строку x[sub]3[/sub] на строку x[sub]1[/sub], для чего делим все её элементы на разрешающий элемент:
[table]
[row][col]Базис[/col][col silver]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][col][/col][/row]
[row][col silver]x₁[/col][col gray]1[/col][col silver]2/13[/col][col silver]1/13[/col][col silver]0[/col][col silver]0[/col][col silver]20[/col][/row]
[row][col]x₄[/col][col silver]4[/col][col]4[/col][col]0[/col][col]1[/col][col]0[/col][col]124[/col][/row]
[row][col]x₅[/col][col silver]3[/col][col]14[/col][col]0[/col][col]0[/col][col]1[/col][col]280[/col][/row]
[row][col]F(X)[/col][col silver]-12[/col][col]-10[/col][col]0[/col][col]0[/col][col]0[/col][col]0[/col][/row]
[/table]Исключаем новую базисную переменную x[sub]1[/sub] из остальных строк, для чего вычитаем из них строку x[sub]1[/sub], умноженную на соответствующий элемент столбца x[sub]1[/sub] (4 для x[sub]4[/sub], 3 для x[sub]5[/sub] и -12 для F(X)):
[table]
[row][col]Базис[/col][col]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][col][/col][/row]
[row][col]x₁[/col][col]1[/col][col]2/13[/col][col]1/13[/col][col]0[/col][col]0[/col][col]20[/col][/row]
[row][col]x₄[/col][col]0[/col][col]44/13[/col][col]-4/13[/col][col]1[/col][col]0[/col][col]44[/col][/row]
[row][col]x₅[/col][col]0[/col][col]176/13[/col][col]-3/13[/col][col]0[/col][col]1[/col][col]220[/col][/row]
[row][col]F(X)[/col][col]0[/col][col]-106/13[/col][col]12/13[/col][col]0[/col][col]0[/col][col]240[/col][/row]
[/table]Получаем новый опорный план X = (20, 0, 0, 44, 220). Он допустим, так как все свободные члены (20, 44, 220) положительны, но неоптимален, так как в индексной строке F(X) есть отрицательный коэффициент -106/13 в столбце x[sub]2[/sub]. Других отрицательных коэффициентов нет, поэтому переменная x[sub]2[/sub] будет новой базисной переменной, а соответствующий столбец - ведущим. Найдём частные от деления свободных членов на коэффициенты ведущего столбца: (20/(2/13), 44/(44/13), 220/(176/13)) = (130, 13, 65/4). Наименьшее среди них неотрицательное значение равно 13. Соответствующая ему переменная x[sub]4[/sub] будет новой свободной переменной, а соответствующая строка - ведущей:
[table]
[row][col]Базис[/col][col]x₁[/col][col silver]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][col][/col][/row]
[row][col]x₁[/col][col]1[/col][col silver]2/13[/col][col]1/13[/col][col]0[/col][col]0[/col][col]20[/col][/row]
[row][col silver]x₄[/col][col silver]0[/col][col gray]44/13[/col][col silver]-4/13[/col][col silver]1[/col][col silver]0[/col][col silver]44[/col][/row]
[row][col]x₅[/col][col]0[/col][col silver]176/13[/col][col]-3/13[/col][col]0[/col][col]1[/col][col]220[/col][/row]
[row][col]F(X)[/col][col]0[/col][col silver]-106/13[/col][col]12/13[/col][col]0[/col][col]0[/col][col]240[/col][/row]
[/table]Разрешающий элемент равен 44/13. Заменяем строку x[sub]4[/sub] на строку x[sub]2[/sub], разделив все её элементы на разрешающий элемент:
[table]
[row][col]Базис[/col][col]x₁[/col][col silver]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][col][/col][/row]
[row][col]x₁[/col][col]1[/col][col silver]2/13[/col][col]1/13[/col][col]0[/col][col]0[/col][col]20[/col][/row]
[row][col silver]x₂[/col][col silver]0[/col][col gray]1[/col][col silver]-1/11[/col][col silver]13/44[/col][col silver]0[/col][col silver]13[/col][/row]
[row][col]x₅[/col][col]0[/col][col silver]176/13[/col][col]-3/13[/col][col]0[/col][col]1[/col][col]220[/col][/row]
[row][col]F(X)[/col][col]0[/col][col silver]-106/13[/col][col]12/13[/col][col]0[/col][col]0[/col][col]240[/col][/row]
[/table]Исключаем новую базисную переменную x[sub]2[/sub] из остальных строк, для чего вычитаем из них строку x[sub]2[/sub], умноженную на соответствующий элемент столбца x[sub]2[/sub] (2/13 для x[sub]1[/sub], 176/13 для x[sub]5[/sub] и -106/13 для F(X)):
[table]
[row][col]Базис[/col][col]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][col][/col][/row]
[row][col]x₁[/col][col]1[/col][col]0[/col][col]1/11[/col][col]-1/22[/col][col]0[/col][col]18[/col][/row]
[row][col]x₂[/col][col]0[/col][col]1[/col][col]-1/11[/col][col]13/44[/col][col]0[/col][col]13[/col][/row]
[row][col]x₅[/col][col]0[/col][col]0[/col][col]1[/col][col]-4[/col][col]1[/col][col]64[/col][/row]
[row][col]F(X)[/col][col]0[/col][col]0[/col][col]2/11[/col][col]53/22[/col][col]0[/col][col]346[/col][/row]
[/table]Получаем новый опорный план X = (18, 13, 0, 0, 64). Он допустим, так как все свободные члены (18, 13, 64) положительны, и оптимален, так как в индексной строке F(X) нет отрицательных коэффициентов. Оптимальный план можно записать как x[sub]1[/sub] = 18, x[sub]2[/sub] = 13, то есть при изготовлении 18 изделий A и 13 изделий B их стоимость будет наибольшей и равна 346 руб. При этом x[sub]3[/sub] = x[sub]4[/sub] = 0, но x[sub]5[/sub] = 64, то есть сырьё первого и второго вида будут израсходованы полностью, остаток же сырья третьего типа составит 64 кг.