Здравствуйте, Посетитель - 399158!

Пусть произведено x[sub]1[/sub] изделий первого вида и x[sub]2[/sub] изделий второго вида (эти величины должны быть целыми и неотрицательными). Тогда будет израсходовано 10x[sub]1[/sub]+70x[sub]2[/sub] тонн стали (но не более 560 тонн), 20x[sub]1[/sub]+50x[sub]2[/sub] килограмм цветных металлов (но не более 510 кг) и 200x[sub]1[/sub]+100x[sub]2[/sub] станкочасов (но не более 3100). Если прибыль от продажи изделий первого и второго вида составляет 5 и 8 соответственно, то суммарная прибыль будет равна 5x[sub]1[/sub]+8x[sub]2[/sub]. Требуется установить, при каких x[sub]1[/sub] и x[sub]2[/sub] она будет наибольшей.

Таким образом, имеем задачу линейного программирования: необходимо найти максимальное значение целевой функции F = 5x[sub]1[/sub]+8x[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, 560, 510, 3100).

1. Составим симплекс-таблицу:
[table]
[row][col]Базис[/col][col][/col][col]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][/row]
[row][col]x₃[/col][col]560[/col][col]10[/col][col]70[/col][col]1[/col][col]0[/col][col]0[/col][/row]
[row][col]x₄[/col][col]510[/col][col]20[/col][col]50[/col][col]0[/col][col]1[/col][col]0[/col][/row]
[row][col]x₅[/col][col]3100[/col][col]200[/col][col]100[/col][col]0[/col][col]0[/col][col]1[/col][/row]
[row][col]F(X)[/col][col]0[/col][col]-5[/col][col]-8[/col][col]0[/col][col]0[/col][col]0[/col][/row]
[/table]
Этот опорный план допустим, так как все свободные члены (560, 510, 3100) положительны, но неоптимален, так как в индексной строке F(X) есть отрицательные коэффициенты.
Наибольший по модулю отрицательный коэффициент в индексной строке равен -8. Соответствующая ему переменная x[sub]2[/sub] будет новой базисной переменной, а соответствующий столбец - ведущим. Найдём частные от деления свободных членов на коэффициенты ведущего столбца: (560/70, 510/70, 3100/200) = (8, 51/5, 31). Наименьшее среди них неотрицательное значение равно 8. Соответствующая ему переменная x[sub]3[/sub] будет новой свободной переменной, а соответствующая строка - ведущей:
[table]
[row][col]Базис[/col][col][/col][col]x₁[/col][col silver]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][/row]
[row][col silver]x₃[/col][col silver]560[/col][col silver]10[/col][col gray]70[/col][col silver]1[/col][col silver]0[/col][col silver]0[/col][/row]
[row][col]x₄[/col][col]510[/col][col]20[/col][col silver]50[/col][col]0[/col][col]1[/col][col]0[/col][/row]
[row][col]x₅[/col][col]3100[/col][col]200[/col][col silver]100[/col][col]0[/col][col]0[/col][col]1[/col][/row]
[row][col]F(X)[/col][col]0[/col][col]-5[/col][col silver]-8[/col][col]0[/col][col]0[/col][col]0[/col][/row]
[/table]
Разрешающий элемент, находящийся на пересечении ведущего столбца и ведущей строки, равен 70. Заменяем строку x[sub]3[/sub] на строку x[sub]2[/sub], для чего делим все её элементы на разрешающий элемент:
[table]
[row][col]Базис[/col][col][/col][col]x₁[/col][col silver]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][/row]
[row][col silver]x₂[/col][col silver]8[/col][col silver]1/7[/col][col gray]1[/col][col silver]1/70[/col][col silver]0[/col][col silver]0[/col][/row]
[row][col]x₄[/col][col]510[/col][col]20[/col][col silver]50[/col][col]0[/col][col]1[/col][col]0[/col][/row]
[row][col]x₅[/col][col]3100[/col][col]200[/col][col silver]100[/col][col]0[/col][col]0[/col][col]1[/col][/row]
[row][col]F(X)[/col][col]0[/col][col]-5[/col][col silver]-8[/col][col]0[/col][col]0[/col][col]0[/col][/row]
[/table]
Исключаем новую базисную переменную x[sub]2[/sub] из остальных строк, для чего вычитаем из них строку x[sub]2[/sub], умноженную на соответствующий элемент столбца x[sub]2[/sub] (50 для x[sub]4[/sub], 100 для x[sub]5[/sub] и -8 для F(X)):
[table]
[row][col]Базис[/col][col][/col][col]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][/row]
[row][col]x₂[/col][col]8[/col][col]1/7[/col][col]1[/col][col]1/70[/col][col]0[/col][col]0[/col][/row]
[row][col]x₄[/col][col]110[/col][col]90/7[/col][col]0[/col][col]-5/7[/col][col]1[/col][col]0[/col][/row]
[row][col]x₅[/col][col]2300[/col][col]1300/7[/col][col]0[/col][col]-10/7[/col][col]0[/col][col]1[/col][/row]
[row][col]F(X)[/col][col]64[/col][col]-27/7[/col][col]0[/col][col]4/35[/col][col]0[/col][col]0[/col][/row]
[/table]
2. Получаем новый опорный план X = (0, 8, 0, 110, 2300). Он допустим, так как все свободные члены (8, 110, 2300) положительны, но неоптимален, так как в индексной строке F(X) есть отрицательный коэффициент -27/7 в столбце x[sub]1[/sub]. Других отрицательных коэффициентов нет, поэтому переменная x[sub]1[/sub] будет новой базисной переменной, а соответствующий столбец - ведущим. Найдём частные от деления свободных членов на коэффициенты ведущего столбца: (8/(1/7), 110/(90/7), 2300/(1300/7)) = (56, 77/9, 161/13). Наименьшее среди них неотрицательное значение равно 77/9. Соответствующая ему переменная x[sub]4[/sub] будет новой свободной переменной, а соответствующая строка - ведущей:
[table]
[row][col]Базис[/col][col][/col][col silver]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][/row]
[row][col]x₂[/col][col]8[/col][col silver]1/7[/col][col]1[/col][col]1/70[/col][col]0[/col][col]0[/col][/row]
[row][col silver]x₄[/col][col silver]110[/col][col gray]90/7[/col][col silver]0[/col][col silver]-5/7[/col][col silver]1[/col][col silver]0[/col][/row]
[row][col]x₅[/col][col]2300[/col][col silver]1300/7[/col][col]0[/col][col]-10/7[/col][col]0[/col][col]1[/col][/row]
[row][col]F(X)[/col][col]64[/col][col silver]-27/7[/col][col]0[/col][col]4/35[/col][col]0[/col][col]0[/col][/row]
[/table]
Разрешающий элемент равен 90/7. Заменяем строку x[sub]4[/sub] на строку x[sub]1[/sub], разделив все её элементы на разрешающий элемент:
[table]
[row][col]Базис[/col][col][/col][col silver]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][/row]
[row][col]x₂[/col][col]8[/col][col silver]1/7[/col][col]1[/col][col]1/70[/col][col]0[/col][col]0[/col][/row]
[row][col silver]x₁[/col][col silver]77/9[/col][col gray]1[/col][col silver]0[/col][col silver]-1/18[/col][col silver]7/90[/col][col silver]0[/col][/row]
[row][col]x₅[/col][col]2300[/col][col silver]1300/7[/col][col]0[/col][col]-10/7[/col][col]0[/col][col]1[/col][/row]
[row][col]F(X)[/col][col]64[/col][col silver]-27/7[/col][col]0[/col][col]4/35[/col][col]0[/col][col]0[/col][/row]
[/table]
Исключаем новую базисную переменную x[sub]1[/sub] из остальных строк, для чего вычитаем из них строку x[sub]1[/sub], умноженную на соответствующий элемент столбца x[sub]1[/sub] (1/7 для x[sub]2[/sub], 1300/7 для x[sub]5[/sub] и -27/7 для F(X)):
[table]
[row][col]Базис[/col][col][/col][col]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][/row]
[row][col]x₂[/col][col]61/9[/col][col]0[/col][col]1[/col][col]1/45[/col][col]-1/90[/col][col]0[/col][/row]
[row][col]x₁[/col][col]77/9[/col][col]1[/col][col]0[/col][col]-1/18[/col][col]7/90[/col][col]0[/col][/row]
[row][col]x₅[/col][col]6400/9[/col][col]0[/col][col]0[/col][col]80/9[/col][col]-130/9[/col][col]1[/col][/row]
[row][col]F(X)[/col][col]97[/col][col]0[/col][col]0[/col][col]-1/10[/col][col]3/10[/col][col]0[/col][/row]
[/table]
3. Получаем новый опорный план X = (77/9, 61/9, 0, 0, 6400/9). Он допустим, так как все свободные члены (77/9, 61/9, 6400/9) положительны, но неоптимален, так как в индексной строке F(X) есть отрицательный коэффициент -1/10 в столбце x[sub]3[/sub]. Других отрицательных коэффициентов нет, поэтому переменная x[sub]3[/sub] будет новой базисной переменной, а соответствующий столбец - ведущим. Найдём частные от деления свободных членов на коэффициенты ведущего столбца: ((61/9)/(1/45), (77/9)/(-1/18), (6400/9)/(80/9)) = (305, -154, 80). Наименьшее среди них неотрицательное значение равно 80. Соответствующая ему переменная x[sub]5[/sub] будет новой свободной переменной, а соответствующая строка - ведущей:
[table]
[row][col]Базис[/col][col][/col][col]x₁[/col][col]x₂[/col][col silver]x₃[/col][col]x₄[/col][col]x₅[/col][/row]
[row][col]x₂[/col][col]61/9[/col][col]0[/col][col]1[/col][col silver]1/45[/col][col]-1/90[/col][col]0[/col][/row]
[row][col]x₁[/col][col]77/9[/col][col]1[/col][col]0[/col][col silver]-1/18[/col][col]7/90[/col][col]0[/col][/row]
[row][col silver]x₅[/col][col silver]6400/9[/col][col silver]0[/col][col silver]0[/col][col gray]80/9[/col][col silver]-130/9[/col][col silver]1[/col][/row]
[row][col]F(X)[/col][col]97[/col][col]0[/col][col]0[/col][col silver]-1/10[/col][col]3/10[/col][col]0[/col][/row]
[/table]
Разрешающий элемент равен 80/9. Заменяем строку x[sub]5[/sub] на строку x[sub]3[/sub], разделив все её элементы на разрешающий элемент:
[table]
[row][col]Базис[/col][col][/col][col]x₁[/col][col]x₂[/col][col silver]x₃[/col][col]x₄[/col][col]x₅[/col][/row]
[row][col]x₂[/col][col]61/9[/col][col]0[/col][col]1[/col][col silver]1/45[/col][col]-1/90[/col][col]0[/col][/row]
[row][col]x₁[/col][col]77/9[/col][col]1[/col][col]0[/col][col silver]-1/18[/col][col]7/90[/col][col]0[/col][/row]
[row][col silver]x₃[/col][col silver]80[/col][col silver]0[/col][col silver]0[/col][col gray]1[/col][col silver]-13/8[/col][col silver]9/80[/col][/row]
[row][col]F(X)[/col][col]97[/col][col]0[/col][col]0[/col][col silver]-1/10[/col][col]3/10[/col][col]0[/col][/row]
[/table]
Исключаем новую базисную переменную x[sub]3[/sub] из остальных строк, для чего вычитаем из них строку x[sub]3[/sub], умноженную на соответствующий элемент столбца x[sub]3[/sub] (1/45 для x[sub]2[/sub], -1/18 для x[sub]1[/sub] и -1/10 для F(X)):
[table]
[row][col]Базис[/col][col][/col][col]x₁[/col][col]x₂[/col][col]x₃[/col][col]x₄[/col][col]x₅[/col][/row]
[row][col]x₂[/col][col]5[/col][col]0[/col][col]1[/col][col]0[/col][col]1/40[/col][col]-1/400[/col][/row]
[row][col]x₁[/col][col]13[/col][col]1[/col][col]0[/col][col]0[/col][col]-8/315[/col][col]1/160[/col][/row]
[row][col]x₃[/col][col]80[/col][col]0[/col][col]0[/col][col]1[/col][col]-13/8[/col][col]9/80[/col][/row]
[row][col]F(X)[/col][col]105[/col][col]0[/col][col]0[/col][col]0[/col][col]11/80[/col][col]9/800[/col][/row]
[/table]
4. Получаем новый опорный план X = (13, 5, 80, 0, 0). Он допустим, так как все свободные члены (13, 5, 80) положительны, и оптимален, так как в индексной строке F(X) нет отрицательных коэффициентов. Оптимальный план можно записать как x[sub]1[/sub] = 13, x[sub]2[/sub] = 5, то есть при изготовлении 13 изделий первого вида и 5 изделий второго прибыль от их реализации будет максимальна и равна 105. При этом x[sub]4[/sub] = x[sub]5[/sub] = 0, то есть ресурс цветных металлов и станкочасов будет израсходован полностью (без остатка), но x[sub]3[/sub] = 80, то есть остаток по стали составит 80 тонн. Действительно, на изготовление 13 изделий первого вида и 5 изделий второго вида будет израсходовано 10[$183$]13+70[$183$]5 = 480 тонн стали, 20[$183$]13+50[$183$]5 = 510 килограмм цветных металлов и 200[$183$]13+100[$183$]5 = 3100 станкочасов.